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