ark-r1cs-std/r1cs-std/src/fields/fp/mod.rs
r1cs-std/src/fields/fp/mod.rsRaw
1use algebra::{BigInteger, FpParameters, PrimeField};
2use r1cs_core::{lc, ConstraintSystemRef, LinearCombination, Namespace, SynthesisError, Variable};
3
4use core::borrow::Borrow;
5
6use crate::fields::{FieldOpsBounds, FieldVar};
7use crate::{prelude::*, Assignment, ToConstraintFieldGadget, Vec};
8
9mod cmp;
10
11/// Represents a variable in the constraint system whose
12/// value can be an arbitrary field element.
13#[derive(Debug, Clone)]
14#[must_use]
15pub struct AllocatedFp<F: PrimeField> {
16 pub(crate) value: Option<F>,
17 /// The allocated variable corresponding to `self` in `self.cs`.
18 pub variable: Variable,
19 /// The constraint system that `self` was allocated in.
20 pub cs: ConstraintSystemRef<F>,
21}
22
23impl<F: PrimeField> AllocatedFp<F> {
24 /// Constructs a new `AllocatedFp` from a (optional) value, a low-level Variable,
25 /// and a `ConstraintSystemRef`.
26 pub fn new(value: Option<F>, variable: Variable, cs: ConstraintSystemRef<F>) -> Self {
27 Self {
28 value,
29 variable,
30 cs,
31 }
32 }
33}
34
35/// Represent variables corresponding to a field element in `F`.
36#[derive(Clone, Debug)]
37#[must_use]
38pub enum FpVar<F: PrimeField> {
39 /// Represents a constant in the constraint system, which means that
40 /// it does not have a corresponding variable.
41 Constant(F),
42 /// Represents an allocated variable constant in the constraint system.
43 Var(AllocatedFp<F>),
44}
45
46impl<F: PrimeField> R1CSVar<F> for FpVar<F> {
47 type Value = F;
48
49 fn cs(&self) -> ConstraintSystemRef<F> {
50 match self {
51 Self::Constant(_) => ConstraintSystemRef::None,
52 Self::Var(a) => a.cs.clone(),
53 }
54 }
55
56 fn value(&self) -> Result<Self::Value, SynthesisError> {
57 match self {
58 Self::Constant(v) => Ok(*v),
59 Self::Var(v) => v.value(),
60 }
61 }
62}
63
64impl<F: PrimeField> From<Boolean<F>> for FpVar<F> {
65 fn from(other: Boolean<F>) -> Self {
66 if let Boolean::Constant(b) = other {
67 Self::Constant(F::from(b as u8))
68 } else {
69 // `other` is a variable
70 let cs = other.cs();
71 let variable = cs.new_lc(other.lc()).unwrap();
72 Self::Var(AllocatedFp::new(
73 other.value().ok().map(|b| F::from(b as u8)),
74 variable,
75 cs,
76 ))
77 }
78 }
79}
80
81impl<F: PrimeField> From<AllocatedFp<F>> for FpVar<F> {
82 fn from(other: AllocatedFp<F>) -> Self {
83 Self::Var(other)
84 }
85}
86
87impl<'a, F: PrimeField> FieldOpsBounds<'a, F, Self> for FpVar<F> {}
88impl<'a, F: PrimeField> FieldOpsBounds<'a, F, FpVar<F>> for &'a FpVar<F> {}
89
90impl<F: PrimeField> AllocatedFp<F> {
91 /// Constructs `Self` from a `Boolean`: if `other` is false, this outputs `zero`, else it outputs `one`.
92 pub fn from(other: Boolean<F>) -> Self {
93 let cs = other.cs();
94 let variable = cs.new_lc(other.lc()).unwrap();
95 Self::new(other.value().ok().map(|b| F::from(b as u8)), variable, cs)
96 }
97
98 /// Returns the value assigned to `self` in the underlying constraint system
99 /// (if a value was assigned).
100 pub fn value(&self) -> Result<F, SynthesisError> {
101 self.cs.assigned_value(self.variable).get()
102 }
103
104 /// Outputs `self + other`.
105 ///
106 /// This does not create any constraints.
107 #[tracing::instrument(target = "r1cs")]
108 pub fn add(&self, other: &Self) -> Self {
109 let value = match (self.value, other.value) {
110 (Some(val1), Some(val2)) => Some(val1 + &val2),
111 (..) => None,
112 };
113
114 let variable = self
115 .cs
116 .new_lc(lc!() + self.variable + other.variable)
117 .unwrap();
118 AllocatedFp::new(value, variable, self.cs.clone())
119 }
120
121 /// Outputs `self - other`.
122 ///
123 /// This does not create any constraints.
124 #[tracing::instrument(target = "r1cs")]
125 pub fn sub(&self, other: &Self) -> Self {
126 let value = match (self.value, other.value) {
127 (Some(val1), Some(val2)) => Some(val1 - &val2),
128 (..) => None,
129 };
130
131 let variable = self
132 .cs
133 .new_lc(lc!() + self.variable - other.variable)
134 .unwrap();
135 AllocatedFp::new(value, variable, self.cs.clone())
136 }
137
138 /// Outputs `self * other`.
139 ///
140 /// This requires *one* constraint.
141 #[tracing::instrument(target = "r1cs")]
142 pub fn mul(&self, other: &Self) -> Self {
143 let product = AllocatedFp::new_witness(self.cs.clone(), || {
144 Ok(self.value.get()? * &other.value.get()?)
145 })
146 .unwrap();
147 self.cs
148 .enforce_constraint(
149 lc!() + self.variable,
150 lc!() + other.variable,
151 lc!() + product.variable,
152 )
153 .unwrap();
154 product
155 }
156
157 /// Output `self + other`
158 ///
159 /// This does not create any constraints.
160 #[tracing::instrument(target = "r1cs")]
161 pub fn add_constant(&self, other: F) -> Self {
162 if other.is_zero() {
163 self.clone()
164 } else {
165 let value = self.value.map(|val| val + other);
166 let variable = self
167 .cs
168 .new_lc(lc!() + self.variable + (other, Variable::One))
169 .unwrap();
170 AllocatedFp::new(value, variable, self.cs.clone())
171 }
172 }
173
174 /// Output `self - other`
175 ///
176 /// This does not create any constraints.
177 #[tracing::instrument(target = "r1cs")]
178 pub fn sub_constant(&self, other: F) -> Self {
179 self.add_constant(-other)
180 }
181
182 /// Output `self * other`
183 ///
184 /// This does not create any constraints.
185 #[tracing::instrument(target = "r1cs")]
186 pub fn mul_constant(&self, other: F) -> Self {
187 if other.is_one() {
188 self.clone()
189 } else {
190 let value = self.value.map(|val| val * other);
191 let variable = self.cs.new_lc(lc!() + (other, self.variable)).unwrap();
192 AllocatedFp::new(value, variable, self.cs.clone())
193 }
194 }
195
196 /// Output `self + self`
197 ///
198 /// This does not create any constraints.
199 #[tracing::instrument(target = "r1cs")]
200 pub fn double(&self) -> Result<Self, SynthesisError> {
201 let value = self.value.map(|val| val.double());
202 let variable = self.cs.new_lc(lc!() + self.variable + self.variable)?;
203 Ok(Self::new(value, variable, self.cs.clone()))
204 }
205
206 /// Output `-self`
207 ///
208 /// This does not create any constraints.
209 #[tracing::instrument(target = "r1cs")]
210 pub fn negate(&self) -> Self {
211 let mut result = self.clone();
212 result.negate_in_place();
213 result
214 }
215
216 /// Sets `self = -self`
217 ///
218 /// This does not create any constraints.
219 #[tracing::instrument(target = "r1cs")]
220 pub fn negate_in_place(&mut self) -> &mut Self {
221 self.value.as_mut().map(|val| *val = -(*val));
222 self.variable = self.cs.new_lc(lc!() - self.variable).unwrap();
223 self
224 }
225
226 /// Outputs `self * self`
227 ///
228 /// This requires *one* constraint.
229 #[tracing::instrument(target = "r1cs")]
230 pub fn square(&self) -> Result<Self, SynthesisError> {
231 Ok(self.mul(self))
232 }
233
234 /// Outputs `result` such that `result * self = 1`.
235 ///
236 /// This requires *one* constraint.
237 #[tracing::instrument(target = "r1cs")]
238 pub fn inverse(&self) -> Result<Self, SynthesisError> {
239 let inverse = Self::new_witness(self.cs.clone(), || {
240 Ok(self.value.get()?.inverse().unwrap_or(F::zero()))
241 })?;
242
243 self.cs.enforce_constraint(
244 lc!() + self.variable,
245 lc!() + inverse.variable,
246 lc!() + Variable::One,
247 )?;
248 Ok(inverse)
249 }
250
251 /// This is a no-op for prime fields.
252 #[tracing::instrument(target = "r1cs")]
253 pub fn frobenius_map(&self, _: usize) -> Result<Self, SynthesisError> {
254 Ok(self.clone())
255 }
256
257 /// Enforces that `self * other = result`.
258 ///
259 /// This requires *one* constraint.
260 #[tracing::instrument(target = "r1cs")]
261 pub fn mul_equals(&self, other: &Self, result: &Self) -> Result<(), SynthesisError> {
262 self.cs.enforce_constraint(
263 lc!() + self.variable,
264 lc!() + other.variable,
265 lc!() + result.variable,
266 )
267 }
268
269 /// Enforces that `self * self = result`.
270 ///
271 /// This requires *one* constraint.
272 #[tracing::instrument(target = "r1cs")]
273 pub fn square_equals(&self, result: &Self) -> Result<(), SynthesisError> {
274 self.cs.enforce_constraint(
275 lc!() + self.variable,
276 lc!() + self.variable,
277 lc!() + result.variable,
278 )
279 }
280
281 /// Outputs the bit `self == other`.
282 ///
283 /// This requires three constraints.
284 #[tracing::instrument(target = "r1cs")]
285 pub fn is_eq(&self, other: &Self) -> Result<Boolean<F>, SynthesisError> {
286 Ok(self.is_neq(other)?.not())
287 }
288
289 /// Outputs the bit `self != other`.
290 ///
291 /// This requires three constraints.
292 #[tracing::instrument(target = "r1cs")]
293 pub fn is_neq(&self, other: &Self) -> Result<Boolean<F>, SynthesisError> {
294 let is_not_equal = Boolean::new_witness(self.cs.clone(), || {
295 Ok(self.value.get()? != other.value.get()?)
296 })?;
297 let multiplier = self.cs.new_witness_variable(|| {
298 if is_not_equal.value()? {
299 (self.value.get()? - other.value.get()?).inverse().get()
300 } else {
301 Ok(F::one())
302 }
303 })?;
304
305 // Completeness:
306 // Case 1: self != other:
307 // ----------------------
308 // constraint 1:
309 // (self - other) * multiplier = is_not_equal
310 // => (non_zero) * multiplier = 1 (satisfied, because multiplier = 1/(self - other)
311 //
312 // constraint 2:
313 // (self - other) * not(is_not_equal) = 0
314 // => (non_zero) * not(1) = 0
315 // => (non_zero) * 0 = 0
316 //
317 // Case 2: self == other:
318 // ----------------------
319 // constraint 1:
320 // (self - other) * multiplier = is_not_equal
321 // => 0 * multiplier = 0 (satisfied, because multiplier = 1
322 //
323 // constraint 2:
324 // (self - other) * not(is_not_equal) = 0
325 // => 0 * not(0) = 0
326 // => 0 * 1 = 0
327 //
328 // --------------------------------------------------------------------
329 //
330 // Soundness:
331 // Case 1: self != other, but is_not_equal = 0.
332 // --------------------------------------------
333 // constraint 1:
334 // (self - other) * multiplier = is_not_equal
335 // => non_zero * multiplier = 0 (only satisfiable if multiplier == 0)
336 //
337 // constraint 2:
338 // (self - other) * not(is_not_equal) = 0
339 // => (non_zero) * 1 = 0 (impossible)
340 //
341 // Case 2: self == other, but is_not_equal = 1.
342 // --------------------------------------------
343 // constraint 1:
344 // (self - other) * multiplier = is_not_equal
345 // 0 * multiplier = 1 (unsatisfiable)
346 self.cs.enforce_constraint(
347 lc!() + self.variable - other.variable,
348 lc!() + multiplier,
349 is_not_equal.lc(),
350 )?;
351 self.cs.enforce_constraint(
352 lc!() + self.variable - other.variable,
353 is_not_equal.not().lc(),
354 lc!(),
355 )?;
356 Ok(is_not_equal)
357 }
358
359 /// Enforces that self == other if `should_enforce.is_eq(&Boolean::TRUE)`.
360 ///
361 /// This requires one constraint.
362 #[tracing::instrument(target = "r1cs")]
363 pub fn conditional_enforce_equal(
364 &self,
365 other: &Self,
366 should_enforce: &Boolean<F>,
367 ) -> Result<(), SynthesisError> {
368 self.cs.enforce_constraint(
369 lc!() + self.variable - other.variable,
370 lc!() + should_enforce.lc(),
371 lc!(),
372 )
373 }
374
375 /// Enforces that self != other if `should_enforce.is_eq(&Boolean::TRUE)`.
376 ///
377 /// This requires one constraint.
378 #[tracing::instrument(target = "r1cs")]
379 pub fn conditional_enforce_not_equal(
380 &self,
381 other: &Self,
382 should_enforce: &Boolean<F>,
383 ) -> Result<(), SynthesisError> {
384 let multiplier = Self::new_witness(self.cs.clone(), || {
385 if should_enforce.value()? {
386 (self.value.get()? - other.value.get()?).inverse().get()
387 } else {
388 Ok(F::zero())
389 }
390 })?;
391
392 self.cs.enforce_constraint(
393 lc!() + self.variable - other.variable,
394 lc!() + multiplier.variable,
395 should_enforce.lc(),
396 )?;
397 Ok(())
398 }
399}
400
401/****************************************************************************/
402/****************************************************************************/
403
404impl<F: PrimeField> ToBitsGadget<F> for AllocatedFp<F> {
405 /// Outputs the unique bit-wise decomposition of `self` in *little-endian*
406 /// form.
407 ///
408 /// This method enforces that the output is in the field, i.e.
409 /// it invokes `Boolean::enforce_in_field_le` on the bit decomposition.
410 #[tracing::instrument(target = "r1cs")]
411 fn to_bits_le(&self) -> Result<Vec<Boolean<F>>, SynthesisError> {
412 let bits = self.to_non_unique_bits_le()?;
413 Boolean::enforce_in_field_le(&bits)?;
414 Ok(bits)
415 }
416
417 #[tracing::instrument(target = "r1cs")]
418 fn to_non_unique_bits_le(&self) -> Result<Vec<Boolean<F>>, SynthesisError> {
419 let cs = self.cs.clone();
420 use algebra::BitIteratorBE;
421 let mut bits = if let Some(value) = self.value {
422 let field_char = BitIteratorBE::new(F::characteristic());
423 let bits: Vec<_> = BitIteratorBE::new(value.into_repr())
424 .zip(field_char)
425 .skip_while(|(_, c)| !c)
426 .map(|(b, _)| Some(b))
427 .collect();
428 assert_eq!(bits.len(), F::Params::MODULUS_BITS as usize);
429 bits
430 } else {
431 vec![None; F::Params::MODULUS_BITS as usize]
432 };
433
434 // Convert to little-endian
435 bits.reverse();
436
437 let bits: Vec<_> = bits
438 .into_iter()
439 .map(|b| Boolean::new_witness(cs.clone(), || b.get()))
440 .collect::<Result<_, _>>()?;
441
442 let mut lc = LinearCombination::zero();
443 let mut coeff = F::one();
444
445 for bit in bits.iter() {
446 lc = &lc + bit.lc() * coeff;
447
448 coeff.double_in_place();
449 }
450
451 lc = lc - &self.variable;
452
453 cs.enforce_constraint(lc!(), lc!(), lc)?;
454
455 Ok(bits)
456 }
457}
458
459impl<F: PrimeField> ToBytesGadget<F> for AllocatedFp<F> {
460 /// Outputs the unique byte decomposition of `self` in *little-endian*
461 /// form.
462 ///
463 /// This method enforces that the decomposition represents
464 /// an integer that is less than `F::MODULUS`.
465 #[tracing::instrument(target = "r1cs")]
466 fn to_bytes(&self) -> Result<Vec<UInt8<F>>, SynthesisError> {
467 let num_bits = F::BigInt::NUM_LIMBS * 64;
468 let mut bits = self.to_bits_le()?;
469 let remainder = core::iter::repeat(Boolean::constant(false)).take(num_bits - bits.len());
470 bits.extend(remainder);
471 let bytes = bits
472 .chunks(8)
473 .map(|chunk| UInt8::from_bits_le(chunk))
474 .collect();
475 Ok(bytes)
476 }
477
478 #[tracing::instrument(target = "r1cs")]
479 fn to_non_unique_bytes(&self) -> Result<Vec<UInt8<F>>, SynthesisError> {
480 let num_bits = F::BigInt::NUM_LIMBS * 64;
481 let mut bits = self.to_non_unique_bits_le()?;
482 let remainder = core::iter::repeat(Boolean::constant(false)).take(num_bits - bits.len());
483 bits.extend(remainder);
484 let bytes = bits
485 .chunks(8)
486 .map(|chunk| UInt8::from_bits_le(chunk))
487 .collect();
488 Ok(bytes)
489 }
490}
491
492impl<F: PrimeField> ToConstraintFieldGadget<F> for AllocatedFp<F> {
493 #[tracing::instrument(target = "r1cs")]
494 fn to_constraint_field(&self) -> Result<Vec<FpVar<F>>, SynthesisError> {
495 Ok(vec![self.clone().into()])
496 }
497}
498
499impl<F: PrimeField> CondSelectGadget<F> for AllocatedFp<F> {
500 #[inline]
501 #[tracing::instrument(target = "r1cs")]
502 fn conditionally_select(
503 cond: &Boolean<F>,
504 true_val: &Self,
505 false_val: &Self,
506 ) -> Result<Self, SynthesisError> {
507 match cond {
508 Boolean::Constant(true) => Ok(true_val.clone()),
509 Boolean::Constant(false) => Ok(false_val.clone()),
510 _ => {
511 let cs = cond.cs();
512 let result = Self::new_witness(cs.clone(), || {
513 cond.value()
514 .and_then(|c| if c { true_val } else { false_val }.value.get())
515 })?;
516 // a = self; b = other; c = cond;
517 //
518 // r = c * a + (1 - c) * b
519 // r = b + c * (a - b)
520 // c * (a - b) = r - b
521 cs.enforce_constraint(
522 cond.lc(),
523 lc!() + true_val.variable - false_val.variable,
524 lc!() + result.variable - false_val.variable,
525 )?;
526
527 Ok(result)
528 }
529 }
530 }
531}
532
533/// Uses two bits to perform a lookup into a table
534/// `b` is little-endian: `b[0]` is LSB.
535impl<F: PrimeField> TwoBitLookupGadget<F> for AllocatedFp<F> {
536 type TableConstant = F;
537 #[tracing::instrument(target = "r1cs")]
538 fn two_bit_lookup(b: &[Boolean<F>], c: &[Self::TableConstant]) -> Result<Self, SynthesisError> {
539 debug_assert_eq!(b.len(), 2);
540 debug_assert_eq!(c.len(), 4);
541 let result = Self::new_witness(b.cs(), || {
542 let lsb = usize::from(b[0].value()?);
543 let msb = usize::from(b[1].value()?);
544 let index = lsb + (msb << 1);
545 Ok(c[index])
546 })?;
547 let one = Variable::One;
548 b.cs().enforce_constraint(
549 lc!() + b[1].lc() * (c[3] - &c[2] - &c[1] + &c[0]) + (c[1] - &c[0], one),
550 lc!() + b[0].lc(),
551 lc!() + result.variable - (c[0], one) + b[1].lc() * (c[0] - &c[2]),
552 )?;
553
554 Ok(result)
555 }
556}
557
558impl<F: PrimeField> ThreeBitCondNegLookupGadget<F> for AllocatedFp<F> {
559 type TableConstant = F;
560
561 #[tracing::instrument(target = "r1cs")]
562 fn three_bit_cond_neg_lookup(
563 b: &[Boolean<F>],
564 b0b1: &Boolean<F>,
565 c: &[Self::TableConstant],
566 ) -> Result<Self, SynthesisError> {
567 debug_assert_eq!(b.len(), 3);
568 debug_assert_eq!(c.len(), 4);
569 let result = Self::new_witness(b.cs(), || {
570 let lsb = usize::from(b[0].value()?);
571 let msb = usize::from(b[1].value()?);
572 let index = lsb + (msb << 1);
573 let intermediate = c[index];
574
575 let is_negative = b[2].value()?;
576 let y = if is_negative {
577 -intermediate
578 } else {
579 intermediate
580 };
581 Ok(y)
582 })?;
583
584 let y_lc = b0b1.lc() * (c[3] - &c[2] - &c[1] + &c[0])
585 + b[0].lc() * (c[1] - &c[0])
586 + b[1].lc() * (c[2] - &c[0])
587 + (c[0], Variable::One);
588 b.cs().enforce_constraint(
589 y_lc.clone() + y_lc.clone(),
590 b[2].lc(),
591 y_lc.clone() - result.variable,
592 )?;
593
594 Ok(result)
595 }
596}
597
598impl<F: PrimeField> AllocVar<F, F> for AllocatedFp<F> {
599 fn new_variable<T: Borrow<F>>(
600 cs: impl Into<Namespace<F>>,
601 f: impl FnOnce() -> Result<T, SynthesisError>,
602 mode: AllocationMode,
603 ) -> Result<Self, SynthesisError> {
604 let ns = cs.into();
605 let cs = ns.cs();
606 if mode == AllocationMode::Constant {
607 let v = *f()?.borrow();
608 let lc = cs.new_lc(lc!() + (v, Variable::One))?;
609 Ok(Self::new(Some(v), lc, cs))
610 } else {
611 let mut value = None;
612 let value_generator = || {
613 value = Some(*f()?.borrow());
614 value.ok_or(SynthesisError::AssignmentMissing)
615 };
616 let variable = if mode == AllocationMode::Input {
617 cs.new_input_variable(value_generator)?
618 } else {
619 cs.new_witness_variable(value_generator)?
620 };
621 Ok(Self::new(value, variable, cs.clone()))
622 }
623 }
624}
625
626impl<F: PrimeField> FieldVar<F, F> for FpVar<F> {
627 fn constant(f: F) -> Self {
628 Self::Constant(f)
629 }
630
631 fn zero() -> Self {
632 Self::Constant(F::zero())
633 }
634
635 fn one() -> Self {
636 Self::Constant(F::one())
637 }
638
639 #[tracing::instrument(target = "r1cs")]
640 fn double(&self) -> Result<Self, SynthesisError> {
641 match self {
642 Self::Constant(c) => Ok(Self::Constant(c.double())),
643 Self::Var(v) => Ok(Self::Var(v.double()?)),
644 }
645 }
646
647 #[tracing::instrument(target = "r1cs")]
648 fn negate(&self) -> Result<Self, SynthesisError> {
649 match self {
650 Self::Constant(c) => Ok(Self::Constant(-*c)),
651 Self::Var(v) => Ok(Self::Var(v.negate())),
652 }
653 }
654
655 #[tracing::instrument(target = "r1cs")]
656 fn square(&self) -> Result<Self, SynthesisError> {
657 match self {
658 Self::Constant(c) => Ok(Self::Constant(c.square())),
659 Self::Var(v) => Ok(Self::Var(v.square()?)),
660 }
661 }
662
663 /// Enforce that `self * other == result`.
664 #[tracing::instrument(target = "r1cs")]
665 fn mul_equals(&self, other: &Self, result: &Self) -> Result<(), SynthesisError> {
666 use FpVar::*;
667 match (self, other, result) {
668 (Constant(_), Constant(_), Constant(_)) => Ok(()),
669 (Constant(_), Constant(_), _) | (Constant(_), Var(_), _) | (Var(_), Constant(_), _) => {
670 result.enforce_equal(&(self * other))
671 } // this multiplication should be free
672 (Var(v1), Var(v2), Var(v3)) => v1.mul_equals(v2, v3),
673 (Var(v1), Var(v2), Constant(f)) => {
674 let cs = v1.cs.clone();
675 let v3 = AllocatedFp::new_constant(cs.clone(), f).unwrap();
676 v1.mul_equals(v2, &v3)
677 }
678 }
679 }
680
681 /// Enforce that `self * self == result`.
682 #[tracing::instrument(target = "r1cs")]
683 fn square_equals(&self, result: &Self) -> Result<(), SynthesisError> {
684 use FpVar::*;
685 match (self, result) {
686 (Constant(_), Constant(_)) => Ok(()),
687 (Constant(f), Var(r)) => {
688 let cs = r.cs.clone();
689 let v = AllocatedFp::new_witness(cs, || Ok(f))?;
690 v.square_equals(&r)
691 }
692 (Var(v), Constant(f)) => {
693 let cs = v.cs.clone();
694 let r = AllocatedFp::new_witness(cs, || Ok(f))?;
695 v.square_equals(&r)
696 }
697 (Var(v1), Var(v2)) => v1.square_equals(v2),
698 }
699 }
700
701 #[tracing::instrument(target = "r1cs")]
702 fn inverse(&self) -> Result<Self, SynthesisError> {
703 match self {
704 FpVar::Var(v) => v.inverse().map(FpVar::Var),
705 FpVar::Constant(f) => f.inverse().get().map(FpVar::Constant),
706 }
707 }
708
709 /// Returns (self / denominator), but requires fewer constraints than
710 /// self * denominator.inverse()
711 /// It is up to the caller to ensure that denominator is non-zero,
712 /// since in that case the result is unconstrained.
713 #[tracing::instrument(target = "r1cs")]
714 fn mul_by_inverse(&self, denominator: &Self) -> Result<Self, SynthesisError> {
715 use FpVar::*;
716 match (self, denominator) {
717 (Constant(s), Constant(d)) => Ok(Constant(*s / *d)),
718 (Var(s), Constant(d)) => Ok(Var(s.mul_constant(d.inverse().get()?))),
719 (Constant(s), Var(d)) => Ok(Var(d.inverse()?.mul_constant(*s))),
720 (Var(s), Var(d)) => Ok(Var(d.inverse()?.mul(s))),
721 }
722 }
723
724 #[tracing::instrument(target = "r1cs")]
725 fn frobenius_map(&self, power: usize) -> Result<Self, SynthesisError> {
726 match self {
727 FpVar::Var(v) => v.frobenius_map(power).map(FpVar::Var),
728 FpVar::Constant(f) => {
729 let mut f = *f;
730 f.frobenius_map(power);
731 Ok(FpVar::Constant(f))
732 }
733 }
734 }
735
736 #[tracing::instrument(target = "r1cs")]
737 fn frobenius_map_in_place(&mut self, power: usize) -> Result<&mut Self, SynthesisError> {
738 *self = self.frobenius_map(power)?;
739 Ok(self)
740 }
741}
742
743/****************************************************************************/
744/****************************************************************************/
745
746impl_ops!(
747 FpVar<F>,
748 F,
749 Add,
750 add,
751 AddAssign,
752 add_assign,
753 |this: &'a FpVar<F>, other: &'a FpVar<F>| {
754 use FpVar::*;
755 match (this, other) {
756 (Constant(c1), Constant(c2)) => Constant(*c1 + *c2),
757 (Constant(c), Var(v)) | (Var(v), Constant(c)) => Var(v.add_constant(*c)),
758 (Var(v1), Var(v2)) => Var(v1.add(v2)),
759 }
760 },
761 |this: &'a FpVar<F>, other: F| { this + &FpVar::Constant(other) },
762 F: PrimeField,
763);
764
765impl_ops!(
766 FpVar<F>,
767 F,
768 Sub,
769 sub,
770 SubAssign,
771 sub_assign,
772 |this: &'a FpVar<F>, other: &'a FpVar<F>| {
773 use FpVar::*;
774 match (this, other) {
775 (Constant(c1), Constant(c2)) => Constant(*c1 - *c2),
776 (Var(v), Constant(c)) => Var(v.sub_constant(*c)),
777 (Constant(c), Var(v)) => Var(v.sub_constant(*c).negate()),
778 (Var(v1), Var(v2)) => Var(v1.sub(v2)),
779 }
780 },
781 |this: &'a FpVar<F>, other: F| { this - &FpVar::Constant(other) },
782 F: PrimeField
783);
784
785impl_ops!(
786 FpVar<F>,
787 F,
788 Mul,
789 mul,
790 MulAssign,
791 mul_assign,
792 |this: &'a FpVar<F>, other: &'a FpVar<F>| {
793 use FpVar::*;
794 match (this, other) {
795 (Constant(c1), Constant(c2)) => Constant(*c1 * *c2),
796 (Constant(c), Var(v)) | (Var(v), Constant(c)) => Var(v.mul_constant(*c)),
797 (Var(v1), Var(v2)) => Var(v1.mul(v2)),
798 }
799 },
800 |this: &'a FpVar<F>, other: F| {
801 if other.is_zero() {
802 FpVar::zero()
803 } else {
804 this * &FpVar::Constant(other)
805 }
806 },
807 F: PrimeField
808);
809
810/****************************************************************************/
811/****************************************************************************/
812
813impl<F: PrimeField> EqGadget<F> for FpVar<F> {
814 #[tracing::instrument(target = "r1cs")]
815 fn is_eq(&self, other: &Self) -> Result<Boolean<F>, SynthesisError> {
816 match (self, other) {
817 (Self::Constant(c1), Self::Constant(c2)) => Ok(Boolean::Constant(c1 == c2)),
818 (Self::Constant(c), Self::Var(v)) | (Self::Var(v), Self::Constant(c)) => {
819 let cs = v.cs.clone();
820 let c = AllocatedFp::new_constant(cs, c)?;
821 c.is_eq(v)
822 }
823 (Self::Var(v1), Self::Var(v2)) => v1.is_eq(v2),
824 }
825 }
826
827 #[tracing::instrument(target = "r1cs")]
828 fn conditional_enforce_equal(
829 &self,
830 other: &Self,
831 should_enforce: &Boolean<F>,
832 ) -> Result<(), SynthesisError> {
833 match (self, other) {
834 (Self::Constant(_), Self::Constant(_)) => Ok(()),
835 (Self::Constant(c), Self::Var(v)) | (Self::Var(v), Self::Constant(c)) => {
836 let cs = v.cs.clone();
837 let c = AllocatedFp::new_constant(cs, c)?;
838 c.conditional_enforce_equal(v, should_enforce)
839 }
840 (Self::Var(v1), Self::Var(v2)) => v1.conditional_enforce_equal(v2, should_enforce),
841 }
842 }
843
844 #[tracing::instrument(target = "r1cs")]
845 fn conditional_enforce_not_equal(
846 &self,
847 other: &Self,
848 should_enforce: &Boolean<F>,
849 ) -> Result<(), SynthesisError> {
850 match (self, other) {
851 (Self::Constant(_), Self::Constant(_)) => Ok(()),
852 (Self::Constant(c), Self::Var(v)) | (Self::Var(v), Self::Constant(c)) => {
853 let cs = v.cs.clone();
854 let c = AllocatedFp::new_constant(cs, c)?;
855 c.conditional_enforce_not_equal(v, should_enforce)
856 }
857 (Self::Var(v1), Self::Var(v2)) => v1.conditional_enforce_not_equal(v2, should_enforce),
858 }
859 }
860}
861
862impl<F: PrimeField> ToBitsGadget<F> for FpVar<F> {
863 #[tracing::instrument(target = "r1cs")]
864 fn to_bits_le(&self) -> Result<Vec<Boolean<F>>, SynthesisError> {
865 match self {
866 Self::Constant(_) => self.to_non_unique_bits_le(),
867 Self::Var(v) => v.to_bits_le(),
868 }
869 }
870
871 #[tracing::instrument(target = "r1cs")]
872 fn to_non_unique_bits_le(&self) -> Result<Vec<Boolean<F>>, SynthesisError> {
873 use algebra::BitIteratorLE;
874 match self {
875 Self::Constant(c) => Ok(BitIteratorLE::without_trailing_zeros(&c.into_repr())
876 .map(Boolean::constant)
877 .collect::<Vec<_>>()),
878 Self::Var(v) => v.to_non_unique_bits_le(),
879 }
880 }
881}
882
883impl<F: PrimeField> ToBytesGadget<F> for FpVar<F> {
884 /// Outputs the unique byte decomposition of `self` in *little-endian*
885 /// form.
886 #[tracing::instrument(target = "r1cs")]
887 fn to_bytes(&self) -> Result<Vec<UInt8<F>>, SynthesisError> {
888 match self {
889 Self::Constant(c) => Ok(UInt8::constant_vec(&to_bytes![c].unwrap())),
890 Self::Var(v) => v.to_bytes(),
891 }
892 }
893
894 #[tracing::instrument(target = "r1cs")]
895 fn to_non_unique_bytes(&self) -> Result<Vec<UInt8<F>>, SynthesisError> {
896 match self {
897 Self::Constant(c) => Ok(UInt8::constant_vec(&to_bytes![c].unwrap())),
898 Self::Var(v) => v.to_non_unique_bytes(),
899 }
900 }
901}
902
903impl<F: PrimeField> ToConstraintFieldGadget<F> for FpVar<F> {
904 #[tracing::instrument(target = "r1cs")]
905 fn to_constraint_field(&self) -> Result<Vec<FpVar<F>>, SynthesisError> {
906 Ok(vec![self.clone()])
907 }
908}
909
910impl<F: PrimeField> CondSelectGadget<F> for FpVar<F> {
911 #[tracing::instrument(target = "r1cs")]
912 fn conditionally_select(
913 cond: &Boolean<F>,
914 true_value: &Self,
915 false_value: &Self,
916 ) -> Result<Self, SynthesisError> {
917 match cond {
918 Boolean::Constant(true) => Ok(true_value.clone()),
919 Boolean::Constant(false) => Ok(false_value.clone()),
920 _ => {
921 match (true_value, false_value) {
922 (Self::Constant(t), Self::Constant(f)) => {
923 let is = AllocatedFp::from(cond.clone());
924 let not = AllocatedFp::from(cond.not());
925 // cond * t + (1 - cond) * f
926 Ok(is.mul_constant(*t).add(¬.mul_constant(*f)).into())
927 }
928 (_, _) => {
929 let cs = cond.cs();
930 let true_value = match true_value {
931 Self::Constant(f) => AllocatedFp::new_constant(cs.clone(), f)?,
932 Self::Var(v) => v.clone(),
933 };
934 let false_value = match false_value {
935 Self::Constant(f) => AllocatedFp::new_constant(cs.clone(), f)?,
936 Self::Var(v) => v.clone(),
937 };
938 cond.select(&true_value, &false_value).map(Self::Var)
939 }
940 }
941 }
942 }
943 }
944}
945
946/// Uses two bits to perform a lookup into a table
947/// `b` is little-endian: `b[0]` is LSB.
948impl<F: PrimeField> TwoBitLookupGadget<F> for FpVar<F> {
949 type TableConstant = F;
950
951 #[tracing::instrument(target = "r1cs")]
952 fn two_bit_lookup(b: &[Boolean<F>], c: &[Self::TableConstant]) -> Result<Self, SynthesisError> {
953 debug_assert_eq!(b.len(), 2);
954 debug_assert_eq!(c.len(), 4);
955 if b.is_constant() {
956 let lsb = usize::from(b[0].value()?);
957 let msb = usize::from(b[1].value()?);
958 let index = lsb + (msb << 1);
959 Ok(Self::Constant(c[index]))
960 } else {
961 AllocatedFp::two_bit_lookup(b, c).map(Self::Var)
962 }
963 }
964}
965
966impl<F: PrimeField> ThreeBitCondNegLookupGadget<F> for FpVar<F> {
967 type TableConstant = F;
968
969 #[tracing::instrument(target = "r1cs")]
970 fn three_bit_cond_neg_lookup(
971 b: &[Boolean<F>],
972 b0b1: &Boolean<F>,
973 c: &[Self::TableConstant],
974 ) -> Result<Self, SynthesisError> {
975 debug_assert_eq!(b.len(), 3);
976 debug_assert_eq!(c.len(), 4);
977
978 if !b.cs().or(b0b1.cs()).is_none() {
979 // We only have constants
980
981 let lsb = usize::from(b[0].value()?);
982 let msb = usize::from(b[1].value()?);
983 let index = lsb + (msb << 1);
984 let intermediate = c[index];
985
986 let is_negative = b[2].value()?;
987 let y = if is_negative {
988 -intermediate
989 } else {
990 intermediate
991 };
992 Ok(Self::Constant(y))
993 } else {
994 AllocatedFp::three_bit_cond_neg_lookup(b, b0b1, c).map(Self::Var)
995 }
996 }
997}
998
999impl<F: PrimeField> AllocVar<F, F> for FpVar<F> {
1000 fn new_variable<T: Borrow<F>>(
1001 cs: impl Into<Namespace<F>>,
1002 f: impl FnOnce() -> Result<T, SynthesisError>,
1003 mode: AllocationMode,
1004 ) -> Result<Self, SynthesisError> {
1005 if mode == AllocationMode::Constant {
1006 Ok(Self::Constant(*f()?.borrow()))
1007 } else {
1008 AllocatedFp::new_variable(cs, f, mode).map(Self::Var)
1009 }
1010 }
1011}