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