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, 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> CondSelectGadget<F> for AllocatedFp<F> {
436 #[inline]
437 #[tracing::instrument(target = "r1cs")]
438 fn conditionally_select(
439 cond: &Boolean<F>,
440 true_val: &Self,
441 false_val: &Self,
442 ) -> Result<Self, SynthesisError> {
443 match cond {
444 Boolean::Constant(true) => Ok(true_val.clone()),
445 Boolean::Constant(false) => Ok(false_val.clone()),
446 _ => {
447 let cs = cond.cs().unwrap();
448 let result = Self::new_witness(cs.clone(), || {
449 cond.value()
450 .and_then(|c| if c { true_val } else { false_val }.value.get())
451 })?;
452 // a = self; b = other; c = cond;
453 //
454 // r = c * a + (1 - c) * b
455 // r = b + c * (a - b)
456 // c * (a - b) = r - b
457 cs.enforce_constraint(
458 cond.lc(),
459 lc!() + true_val.variable - false_val.variable,
460 lc!() + result.variable - false_val.variable,
461 )?;
462
463 Ok(result)
464 }
465 }
466 }
467}
468
469/// Uses two bits to perform a lookup into a table
470/// `b` is little-endian: `b[0]` is LSB.
471impl<F: PrimeField> TwoBitLookupGadget<F> for AllocatedFp<F> {
472 type TableConstant = F;
473 #[tracing::instrument(target = "r1cs")]
474 fn two_bit_lookup(b: &[Boolean<F>], c: &[Self::TableConstant]) -> Result<Self, SynthesisError> {
475 debug_assert_eq!(b.len(), 2);
476 debug_assert_eq!(c.len(), 4);
477 if let Some(cs) = b.cs() {
478 let result = Self::new_witness(cs.clone(), || {
479 let lsb = usize::from(b[0].value()?);
480 let msb = usize::from(b[1].value()?);
481 let index = lsb + (msb << 1);
482 Ok(c[index])
483 })?;
484 let one = Variable::One;
485 cs.enforce_constraint(
486 lc!() + b[1].lc() * (c[3] - &c[2] - &c[1] + &c[0]) + (c[1] - &c[0], one),
487 lc!() + b[0].lc(),
488 lc!() + result.variable - (c[0], one) + b[1].lc() * (c[0] - &c[2]),
489 )?;
490
491 Ok(result)
492 } else {
493 unreachable!("must provide a way to obtain a ConstraintSystemRef")
494 }
495 }
496}
497
498impl<F: PrimeField> ThreeBitCondNegLookupGadget<F> for AllocatedFp<F> {
499 type TableConstant = F;
500
501 #[tracing::instrument(target = "r1cs")]
502 fn three_bit_cond_neg_lookup(
503 b: &[Boolean<F>],
504 b0b1: &Boolean<F>,
505 c: &[Self::TableConstant],
506 ) -> Result<Self, SynthesisError> {
507 debug_assert_eq!(b.len(), 3);
508 debug_assert_eq!(c.len(), 4);
509
510 if let Some(cs) = b.cs() {
511 let result = Self::new_witness(cs.clone(), || {
512 let lsb = usize::from(b[0].value()?);
513 let msb = usize::from(b[1].value()?);
514 let index = lsb + (msb << 1);
515 let intermediate = c[index];
516
517 let is_negative = b[2].value()?;
518 let y = if is_negative {
519 -intermediate
520 } else {
521 intermediate
522 };
523 Ok(y)
524 })?;
525
526 let y_lc = b0b1.lc() * (c[3] - &c[2] - &c[1] + &c[0])
527 + b[0].lc() * (c[1] - &c[0])
528 + b[1].lc() * (c[2] - &c[0])
529 + (c[0], Variable::One);
530 cs.enforce_constraint(
531 y_lc.clone() + y_lc.clone(),
532 b[2].lc(),
533 y_lc.clone() - result.variable,
534 )?;
535
536 Ok(result)
537 } else {
538 unreachable!("must provide a way to obtain a ConstraintSystemRef")
539 }
540 }
541}
542
543impl<F: PrimeField> AllocVar<F, F> for AllocatedFp<F> {
544 fn new_variable<T: Borrow<F>>(
545 cs: impl Into<Namespace<F>>,
546 f: impl FnOnce() -> Result<T, SynthesisError>,
547 mode: AllocationMode,
548 ) -> Result<Self, SynthesisError> {
549 let ns = cs.into();
550 let cs = ns.cs();
551 if mode == AllocationMode::Constant {
552 let v = *f()?.borrow();
553 let lc = cs.new_lc(lc!() + (v, Variable::One))?;
554 Ok(Self::new(Some(v), lc, cs))
555 } else {
556 let mut value = None;
557 let value_generator = || {
558 value = Some(*f()?.borrow());
559 value.ok_or(SynthesisError::AssignmentMissing)
560 };
561 let variable = if mode == AllocationMode::Input {
562 cs.new_input_variable(value_generator)?
563 } else {
564 cs.new_witness_variable(value_generator)?
565 };
566 Ok(Self::new(value, variable, cs.clone()))
567 }
568 }
569}
570
571impl<F: PrimeField> FieldVar<F, F> for FpVar<F> {
572 fn constant(f: F) -> Self {
573 Self::Constant(f)
574 }
575
576 fn zero() -> Self {
577 Self::Constant(F::zero())
578 }
579
580 fn one() -> Self {
581 Self::Constant(F::one())
582 }
583
584 #[tracing::instrument(target = "r1cs")]
585 fn double(&self) -> Result<Self, SynthesisError> {
586 match self {
587 Self::Constant(c) => Ok(Self::Constant(c.double())),
588 Self::Var(v) => Ok(Self::Var(v.double()?)),
589 }
590 }
591
592 #[tracing::instrument(target = "r1cs")]
593 fn negate(&self) -> Result<Self, SynthesisError> {
594 match self {
595 Self::Constant(c) => Ok(Self::Constant(-*c)),
596 Self::Var(v) => Ok(Self::Var(v.negate())),
597 }
598 }
599
600 #[tracing::instrument(target = "r1cs")]
601 fn square(&self) -> Result<Self, SynthesisError> {
602 match self {
603 Self::Constant(c) => Ok(Self::Constant(c.square())),
604 Self::Var(v) => Ok(Self::Var(v.square()?)),
605 }
606 }
607
608 /// Enforce that `self * other == result`.
609 #[tracing::instrument(target = "r1cs")]
610 fn mul_equals(&self, other: &Self, result: &Self) -> Result<(), SynthesisError> {
611 use FpVar::*;
612 match (self, other, result) {
613 (Constant(_), Constant(_), Constant(_)) => Ok(()),
614 (Constant(_), Constant(_), _) | (Constant(_), Var(_), _) | (Var(_), Constant(_), _) => {
615 result.enforce_equal(&(self * other))
616 } // this multiplication should be free
617 (Var(v1), Var(v2), Var(v3)) => v1.mul_equals(v2, v3),
618 (Var(v1), Var(v2), Constant(f)) => {
619 let cs = v1.cs.clone();
620 let v3 = AllocatedFp::new_constant(cs.clone(), f).unwrap();
621 v1.mul_equals(v2, &v3)
622 }
623 }
624 }
625
626 /// Enforce that `self * self == result`.
627 #[tracing::instrument(target = "r1cs")]
628 fn square_equals(&self, result: &Self) -> Result<(), SynthesisError> {
629 use FpVar::*;
630 match (self, result) {
631 (Constant(_), Constant(_)) => Ok(()),
632 (Constant(f), Var(r)) => {
633 let cs = r.cs.clone();
634 let v = AllocatedFp::new_witness(cs, || Ok(f))?;
635 v.square_equals(&r)
636 }
637 (Var(v), Constant(f)) => {
638 let cs = v.cs.clone();
639 let r = AllocatedFp::new_witness(cs, || Ok(f))?;
640 v.square_equals(&r)
641 }
642 (Var(v1), Var(v2)) => v1.square_equals(v2),
643 }
644 }
645
646 #[tracing::instrument(target = "r1cs")]
647 fn inverse(&self) -> Result<Self, SynthesisError> {
648 match self {
649 FpVar::Var(v) => v.inverse().map(FpVar::Var),
650 FpVar::Constant(f) => f.inverse().get().map(FpVar::Constant),
651 }
652 }
653
654 /// Returns (self / denominator), but requires fewer constraints than
655 /// self * denominator.inverse()
656 /// It is up to the caller to ensure that denominator is non-zero,
657 /// since in that case the result is unconstrained.
658 #[tracing::instrument(target = "r1cs")]
659 fn mul_by_inverse(&self, denominator: &Self) -> Result<Self, SynthesisError> {
660 use FpVar::*;
661 match (self, denominator) {
662 (Constant(s), Constant(d)) => Ok(Constant(*s / *d)),
663 (Var(s), Constant(d)) => Ok(Var(s.mul_constant(d.inverse().get()?))),
664 (Constant(s), Var(d)) => Ok(Var(d.inverse()?.mul_constant(*s))),
665 (Var(s), Var(d)) => Ok(Var(d.inverse()?.mul(s))),
666 }
667 }
668
669 #[tracing::instrument(target = "r1cs")]
670 fn frobenius_map(&self, power: usize) -> Result<Self, SynthesisError> {
671 match self {
672 FpVar::Var(v) => v.frobenius_map(power).map(FpVar::Var),
673 FpVar::Constant(f) => {
674 let mut f = *f;
675 f.frobenius_map(power);
676 Ok(FpVar::Constant(f))
677 }
678 }
679 }
680
681 #[tracing::instrument(target = "r1cs")]
682 fn frobenius_map_in_place(&mut self, power: usize) -> Result<&mut Self, SynthesisError> {
683 *self = self.frobenius_map(power)?;
684 Ok(self)
685 }
686}
687
688/****************************************************************************/
689/****************************************************************************/
690
691impl_ops!(
692 FpVar<F>,
693 F,
694 Add,
695 add,
696 AddAssign,
697 add_assign,
698 |this: &'a FpVar<F>, other: &'a FpVar<F>| {
699 use FpVar::*;
700 match (this, other) {
701 (Constant(c1), Constant(c2)) => Constant(*c1 + *c2),
702 (Constant(c), Var(v)) | (Var(v), Constant(c)) => Var(v.add_constant(*c)),
703 (Var(v1), Var(v2)) => Var(v1.add(v2)),
704 }
705 },
706 |this: &'a FpVar<F>, other: F| { this + &FpVar::Constant(other) },
707 F: PrimeField,
708);
709
710impl_ops!(
711 FpVar<F>,
712 F,
713 Sub,
714 sub,
715 SubAssign,
716 sub_assign,
717 |this: &'a FpVar<F>, other: &'a FpVar<F>| {
718 use FpVar::*;
719 match (this, other) {
720 (Constant(c1), Constant(c2)) => Constant(*c1 - *c2),
721 (Var(v), Constant(c)) => Var(v.sub_constant(*c)),
722 (Constant(c), Var(v)) => Var(v.sub_constant(*c).negate()),
723 (Var(v1), Var(v2)) => Var(v1.sub(v2)),
724 }
725 },
726 |this: &'a FpVar<F>, other: F| { this - &FpVar::Constant(other) },
727 F: PrimeField
728);
729
730impl_ops!(
731 FpVar<F>,
732 F,
733 Mul,
734 mul,
735 MulAssign,
736 mul_assign,
737 |this: &'a FpVar<F>, other: &'a FpVar<F>| {
738 use FpVar::*;
739 match (this, other) {
740 (Constant(c1), Constant(c2)) => Constant(*c1 * *c2),
741 (Constant(c), Var(v)) | (Var(v), Constant(c)) => Var(v.mul_constant(*c)),
742 (Var(v1), Var(v2)) => Var(v1.mul(v2)),
743 }
744 },
745 |this: &'a FpVar<F>, other: F| {
746 if other.is_zero() {
747 FpVar::zero()
748 } else {
749 this * &FpVar::Constant(other)
750 }
751 },
752 F: PrimeField
753);
754
755/****************************************************************************/
756/****************************************************************************/
757
758impl<F: PrimeField> EqGadget<F> for FpVar<F> {
759 #[tracing::instrument(target = "r1cs")]
760 fn is_eq(&self, other: &Self) -> Result<Boolean<F>, SynthesisError> {
761 match (self, other) {
762 (Self::Constant(c1), Self::Constant(c2)) => Ok(Boolean::Constant(c1 == c2)),
763 (Self::Constant(c), Self::Var(v)) | (Self::Var(v), Self::Constant(c)) => {
764 let cs = v.cs.clone();
765 let c = AllocatedFp::new_constant(cs, c)?;
766 c.is_eq(v)
767 }
768 (Self::Var(v1), Self::Var(v2)) => v1.is_eq(v2),
769 }
770 }
771
772 #[tracing::instrument(target = "r1cs")]
773 fn conditional_enforce_equal(
774 &self,
775 other: &Self,
776 should_enforce: &Boolean<F>,
777 ) -> Result<(), SynthesisError> {
778 match (self, other) {
779 (Self::Constant(_), Self::Constant(_)) => Ok(()),
780 (Self::Constant(c), Self::Var(v)) | (Self::Var(v), Self::Constant(c)) => {
781 let cs = v.cs.clone();
782 let c = AllocatedFp::new_constant(cs, c)?;
783 c.conditional_enforce_equal(v, should_enforce)
784 }
785 (Self::Var(v1), Self::Var(v2)) => v1.conditional_enforce_equal(v2, should_enforce),
786 }
787 }
788
789 #[tracing::instrument(target = "r1cs")]
790 fn conditional_enforce_not_equal(
791 &self,
792 other: &Self,
793 should_enforce: &Boolean<F>,
794 ) -> Result<(), SynthesisError> {
795 match (self, other) {
796 (Self::Constant(_), Self::Constant(_)) => Ok(()),
797 (Self::Constant(c), Self::Var(v)) | (Self::Var(v), Self::Constant(c)) => {
798 let cs = v.cs.clone();
799 let c = AllocatedFp::new_constant(cs, c)?;
800 c.conditional_enforce_not_equal(v, should_enforce)
801 }
802 (Self::Var(v1), Self::Var(v2)) => v1.conditional_enforce_not_equal(v2, should_enforce),
803 }
804 }
805}
806
807impl<F: PrimeField> ToBitsGadget<F> for FpVar<F> {
808 #[tracing::instrument(target = "r1cs")]
809 fn to_bits_le(&self) -> Result<Vec<Boolean<F>>, SynthesisError> {
810 match self {
811 Self::Constant(_) => self.to_non_unique_bits_le(),
812 Self::Var(v) => v.to_bits_le(),
813 }
814 }
815
816 #[tracing::instrument(target = "r1cs")]
817 fn to_non_unique_bits_le(&self) -> Result<Vec<Boolean<F>>, SynthesisError> {
818 use algebra::BitIteratorLE;
819 match self {
820 Self::Constant(c) => Ok(BitIteratorLE::without_trailing_zeros(&c.into_repr())
821 .map(Boolean::constant)
822 .collect::<Vec<_>>()),
823 Self::Var(v) => v.to_non_unique_bits_le(),
824 }
825 }
826}
827
828impl<F: PrimeField> ToBytesGadget<F> for FpVar<F> {
829 /// Outputs the unique byte decomposition of `self` in *little-endian*
830 /// form.
831 #[tracing::instrument(target = "r1cs")]
832 fn to_bytes(&self) -> Result<Vec<UInt8<F>>, SynthesisError> {
833 match self {
834 Self::Constant(c) => Ok(UInt8::constant_vec(&to_bytes![c].unwrap())),
835 Self::Var(v) => v.to_bytes(),
836 }
837 }
838
839 #[tracing::instrument(target = "r1cs")]
840 fn to_non_unique_bytes(&self) -> Result<Vec<UInt8<F>>, SynthesisError> {
841 match self {
842 Self::Constant(c) => Ok(UInt8::constant_vec(&to_bytes![c].unwrap())),
843 Self::Var(v) => v.to_non_unique_bytes(),
844 }
845 }
846}
847
848impl<F: PrimeField> CondSelectGadget<F> for FpVar<F> {
849 #[tracing::instrument(target = "r1cs")]
850 fn conditionally_select(
851 cond: &Boolean<F>,
852 true_value: &Self,
853 false_value: &Self,
854 ) -> Result<Self, SynthesisError> {
855 match cond {
856 Boolean::Constant(true) => Ok(true_value.clone()),
857 Boolean::Constant(false) => Ok(false_value.clone()),
858 _ => {
859 match (true_value, false_value) {
860 (Self::Constant(t), Self::Constant(f)) => {
861 let is = AllocatedFp::from(cond.clone());
862 let not = AllocatedFp::from(cond.not());
863 // cond * t + (1 - cond) * f
864 Ok(is.mul_constant(*t).add(¬.mul_constant(*f)).into())
865 }
866 (_, _) => {
867 let cs = cond.cs().unwrap();
868 let true_value = match true_value {
869 Self::Constant(f) => AllocatedFp::new_constant(cs.clone(), f)?,
870 Self::Var(v) => v.clone(),
871 };
872 let false_value = match false_value {
873 Self::Constant(f) => AllocatedFp::new_constant(cs.clone(), f)?,
874 Self::Var(v) => v.clone(),
875 };
876 cond.select(&true_value, &false_value).map(Self::Var)
877 }
878 }
879 }
880 }
881 }
882}
883
884/// Uses two bits to perform a lookup into a table
885/// `b` is little-endian: `b[0]` is LSB.
886impl<F: PrimeField> TwoBitLookupGadget<F> for FpVar<F> {
887 type TableConstant = F;
888
889 #[tracing::instrument(target = "r1cs")]
890 fn two_bit_lookup(b: &[Boolean<F>], c: &[Self::TableConstant]) -> Result<Self, SynthesisError> {
891 debug_assert_eq!(b.len(), 2);
892 debug_assert_eq!(c.len(), 4);
893 if b.cs().is_some() {
894 AllocatedFp::two_bit_lookup(b, c).map(Self::Var)
895 } else {
896 let lsb = usize::from(b[0].value()?);
897 let msb = usize::from(b[1].value()?);
898 let index = lsb + (msb << 1);
899 Ok(Self::Constant(c[index]))
900 }
901 }
902}
903
904impl<F: PrimeField> ThreeBitCondNegLookupGadget<F> for FpVar<F> {
905 type TableConstant = F;
906
907 #[tracing::instrument(target = "r1cs")]
908 fn three_bit_cond_neg_lookup(
909 b: &[Boolean<F>],
910 b0b1: &Boolean<F>,
911 c: &[Self::TableConstant],
912 ) -> Result<Self, SynthesisError> {
913 debug_assert_eq!(b.len(), 3);
914 debug_assert_eq!(c.len(), 4);
915
916 if b.cs().or(b0b1.cs()).is_some() {
917 AllocatedFp::three_bit_cond_neg_lookup(b, b0b1, c).map(Self::Var)
918 } else {
919 let lsb = usize::from(b[0].value()?);
920 let msb = usize::from(b[1].value()?);
921 let index = lsb + (msb << 1);
922 let intermediate = c[index];
923
924 let is_negative = b[2].value()?;
925 let y = if is_negative {
926 -intermediate
927 } else {
928 intermediate
929 };
930 Ok(Self::Constant(y))
931 }
932 }
933}
934
935impl<F: PrimeField> AllocVar<F, F> for FpVar<F> {
936 fn new_variable<T: Borrow<F>>(
937 cs: impl Into<Namespace<F>>,
938 f: impl FnOnce() -> Result<T, SynthesisError>,
939 mode: AllocationMode,
940 ) -> Result<Self, SynthesisError> {
941 if mode == AllocationMode::Constant {
942 Ok(Self::Constant(*f()?.borrow()))
943 } else {
944 AllocatedFp::new_variable(cs, f, mode).map(Self::Var)
945 }
946 }
947}