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