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