ark-r1cs-std/r1cs-std/src/fields/fp/mod.rs
r1cs-std/src/fields/fp/mod.rsRaw
1use algebra::{bytes::ToBytes, FpParameters, PrimeField};
2use r1cs_core::{lc, ConstraintSystemRef, LinearCombination, Namespace, SynthesisError, Variable};
3
4use core::borrow::Borrow;
5
6use crate::fields::{FieldOpsBounds, FieldVar};
7use crate::{boolean::AllocatedBit, 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(&self) -> Result<Vec<Boolean<F>>, SynthesisError> {
342 let bits = self.to_non_unique_bits()?;
343 Boolean::enforce_in_field(&bits)?;
344 Ok(bits)
345 }
346
347 fn to_non_unique_bits(&self) -> Result<Vec<Boolean<F>>, SynthesisError> {
348 let cs = self.cs.clone();
349 let num_bits = F::Params::MODULUS_BITS;
350 use algebra::BitIterator;
351 let bit_values = match self.value {
352 Some(value) => {
353 let mut field_char = BitIterator::new(F::characteristic());
354 let mut tmp = Vec::with_capacity(num_bits as usize);
355 let mut found_one = false;
356 for b in BitIterator::new(value.into_repr()) {
357 // Skip leading bits
358 found_one |= field_char.next().unwrap();
359 if !found_one {
360 continue;
361 }
362
363 tmp.push(Some(b));
364 }
365
366 assert_eq!(tmp.len(), num_bits as usize);
367
368 tmp
369 }
370 None => vec![None; num_bits as usize],
371 };
372
373 let mut bits = vec![];
374 for b in bit_values {
375 bits.push(AllocatedBit::new_witness(cs.clone(), || b.get())?);
376 }
377
378 let mut lc = LinearCombination::zero();
379 let mut coeff = F::one();
380
381 for bit in bits.iter().rev() {
382 lc += (coeff, bit.variable());
383
384 coeff.double_in_place();
385 }
386
387 lc = lc - &self.variable;
388
389 cs.enforce_constraint(lc!(), lc!(), lc)?;
390
391 Ok(bits.into_iter().map(Boolean::from).collect())
392 }
393}
394
395impl<F: PrimeField> ToBytesGadget<F> for AllocatedFp<F> {
396 /// Outputs the unique byte decomposition of `self` in *little-endian*
397 /// form.
398 fn to_bytes(&self) -> Result<Vec<UInt8<F>>, SynthesisError> {
399 let bytes = self.to_non_unique_bytes()?;
400 Boolean::enforce_in_field(
401 &bytes.iter()
402 .flat_map(|b| b.into_bits_le())
403 // This reverse maps the bits into big-endian form, as required by `enforce_in_field`.
404 .rev()
405 .collect::<Vec<_>>(),
406 )?;
407
408 Ok(bytes)
409 }
410
411 fn to_non_unique_bytes(&self) -> Result<Vec<UInt8<F>>, SynthesisError> {
412 let cs = self.cs.clone();
413 let byte_values = match self.value {
414 Some(value) => to_bytes![&value.into_repr()]
415 .unwrap()
416 .into_iter()
417 .map(Some)
418 .collect::<Vec<_>>(),
419 None => {
420 let default = F::default();
421 let default_len = to_bytes![&default].unwrap().len();
422 vec![None; default_len]
423 }
424 };
425
426 let bytes = UInt8::new_witness_vec(cs.clone(), &byte_values)?;
427
428 let mut lc = LinearCombination::zero();
429 let mut coeff = F::one();
430
431 for bit in bytes.iter().flat_map(|b| b.bits.clone()) {
432 match bit {
433 Boolean::Is(bit) => {
434 lc += (coeff, bit.variable());
435 coeff.double_in_place();
436 }
437 Boolean::Constant(_) | Boolean::Not(_) => unreachable!(),
438 }
439 }
440
441 lc = lc - &self.variable;
442
443 cs.enforce_constraint(lc!(), lc!(), lc)?;
444
445 Ok(bytes)
446 }
447}
448
449impl<F: PrimeField> CondSelectGadget<F> for AllocatedFp<F> {
450 #[inline]
451 fn conditionally_select(
452 cond: &Boolean<F>,
453 true_val: &Self,
454 false_val: &Self,
455 ) -> Result<Self, SynthesisError> {
456 match cond {
457 Boolean::Constant(true) => Ok(true_val.clone()),
458 Boolean::Constant(false) => Ok(false_val.clone()),
459 _ => {
460 let cs = cond.cs().unwrap();
461 let result = Self::new_witness(cs.clone(), || {
462 cond.value()
463 .and_then(|c| if c { true_val } else { false_val }.value.get())
464 })?;
465 // a = self; b = other; c = cond;
466 //
467 // r = c * a + (1 - c) * b
468 // r = b + c * (a - b)
469 // c * (a - b) = r - b
470 cs.enforce_constraint(
471 cond.lc(),
472 lc!() + true_val.variable - false_val.variable,
473 lc!() + result.variable - false_val.variable,
474 )?;
475
476 Ok(result)
477 }
478 }
479 }
480}
481
482/// Uses two bits to perform a lookup into a table
483/// `b` is little-endian: `b[0]` is LSB.
484impl<F: PrimeField> TwoBitLookupGadget<F> for AllocatedFp<F> {
485 type TableConstant = F;
486 fn two_bit_lookup(b: &[Boolean<F>], c: &[Self::TableConstant]) -> Result<Self, SynthesisError> {
487 debug_assert_eq!(b.len(), 2);
488 debug_assert_eq!(c.len(), 4);
489 if let Some(cs) = b.cs() {
490 let result = Self::new_witness(cs.clone(), || {
491 let lsb = b[0].value()? as usize;
492 let msb = b[1].value()? as usize;
493 let index = lsb + (msb << 1);
494 Ok(c[index])
495 })?;
496 let one = Variable::One;
497 cs.enforce_constraint(
498 lc!() + b[1].lc() * (c[3] - &c[2] - &c[1] + &c[0]) + (c[1] - &c[0], one),
499 lc!() + b[0].lc(),
500 lc!() + result.variable - (c[0], one) + b[1].lc() * (c[0] - &c[2]),
501 )?;
502
503 Ok(result)
504 } else {
505 unreachable!("must provide a way to obtain a ConstraintSystemRef")
506 }
507 }
508}
509
510impl<F: PrimeField> ThreeBitCondNegLookupGadget<F> for AllocatedFp<F> {
511 type TableConstant = F;
512
513 fn three_bit_cond_neg_lookup(
514 b: &[Boolean<F>],
515 b0b1: &Boolean<F>,
516 c: &[Self::TableConstant],
517 ) -> Result<Self, SynthesisError> {
518 debug_assert_eq!(b.len(), 3);
519 debug_assert_eq!(c.len(), 4);
520
521 if let Some(cs) = b.cs() {
522 let result = Self::new_witness(cs.clone(), || {
523 let lsb = b[0].value()? as usize;
524 let msb = b[1].value()? as usize;
525 let index = lsb + (msb << 1);
526 let intermediate = c[index];
527
528 let is_negative = b[2].value()?;
529 let y = if is_negative {
530 -intermediate
531 } else {
532 intermediate
533 };
534 Ok(y)
535 })?;
536
537 let y_lc = b0b1.lc() * (c[3] - &c[2] - &c[1] + &c[0])
538 + b[0].lc() * (c[1] - &c[0])
539 + b[1].lc() * (c[2] - &c[0])
540 + (c[0], Variable::One);
541 cs.enforce_constraint(
542 y_lc.clone() + y_lc.clone(),
543 b[2].lc(),
544 y_lc.clone() - result.variable,
545 )?;
546
547 Ok(result)
548 } else {
549 unreachable!("must provide a way to obtain a ConstraintSystemRef")
550 }
551 }
552}
553
554impl<F: PrimeField> AllocVar<F, F> for AllocatedFp<F> {
555 fn new_variable<T: Borrow<F>>(
556 cs: impl Into<Namespace<F>>,
557 f: impl FnOnce() -> Result<T, SynthesisError>,
558 mode: AllocationMode,
559 ) -> Result<Self, SynthesisError> {
560 let ns = cs.into();
561 let cs = ns.cs();
562 if mode == AllocationMode::Constant {
563 let v = *f()?.borrow();
564 let lc = cs.new_lc(lc!() + (v, Variable::One))?;
565 Ok(Self::new(Some(v), lc, cs))
566 } else {
567 let mut value = None;
568 let value_generator = || {
569 value = Some(*f()?.borrow());
570 value.ok_or(SynthesisError::AssignmentMissing)
571 };
572 let variable = if mode == AllocationMode::Input {
573 cs.new_input_variable(value_generator)?
574 } else {
575 cs.new_witness_variable(value_generator)?
576 };
577 Ok(Self::new(value, variable, cs.clone()))
578 }
579 }
580}
581
582impl<F: PrimeField> FieldVar<F, F> for FpVar<F> {
583 fn constant(f: F) -> Self {
584 Self::Constant(f)
585 }
586
587 fn zero() -> Self {
588 Self::Constant(F::zero())
589 }
590
591 fn one() -> Self {
592 Self::Constant(F::one())
593 }
594
595 fn double(&self) -> Result<Self, SynthesisError> {
596 match self {
597 Self::Constant(c) => Ok(Self::Constant(c.double())),
598 Self::Var(v) => Ok(Self::Var(v.double()?)),
599 }
600 }
601
602 fn negate(&self) -> Result<Self, SynthesisError> {
603 match self {
604 Self::Constant(c) => Ok(Self::Constant(-*c)),
605 Self::Var(v) => Ok(Self::Var(v.negate())),
606 }
607 }
608
609 fn square(&self) -> Result<Self, SynthesisError> {
610 match self {
611 Self::Constant(c) => Ok(Self::Constant(c.square())),
612 Self::Var(v) => Ok(Self::Var(v.square()?)),
613 }
614 }
615
616 /// Enforce that `self * other == result`.
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 fn square_equals(&self, result: &Self) -> Result<(), SynthesisError> {
635 use FpVar::*;
636 match (self, result) {
637 (Constant(_), Constant(_)) => Ok(()),
638 (Constant(f), Var(r)) => {
639 let cs = r.cs.clone();
640 let v = AllocatedFp::new_witness(cs, || Ok(f))?;
641 v.square_equals(&r)
642 }
643 (Var(v), Constant(f)) => {
644 let cs = v.cs.clone();
645 let r = AllocatedFp::new_witness(cs, || Ok(f))?;
646 v.square_equals(&r)
647 }
648 (Var(v1), Var(v2)) => v1.square_equals(v2),
649 }
650 }
651
652 fn inverse(&self) -> Result<Self, SynthesisError> {
653 match self {
654 FpVar::Var(v) => v.inverse().map(FpVar::Var),
655 FpVar::Constant(f) => f.inverse().get().map(FpVar::Constant),
656 }
657 }
658
659 /// Returns (self / denominator), but requires fewer constraints than
660 /// self * denominator.inverse()
661 /// It is up to the caller to ensure that denominator is non-zero,
662 /// since in that case the result is unconstrained.
663 fn mul_by_inverse(&self, denominator: &Self) -> Result<Self, SynthesisError> {
664 use FpVar::*;
665 match (self, denominator) {
666 (Constant(s), Constant(d)) => Ok(Constant(*s / *d)),
667 (Var(s), Constant(d)) => Ok(Var(s.mul_constant(d.inverse().get()?))),
668 (Constant(s), Var(d)) => Ok(Var(d.inverse()?.mul_constant(*s))),
669 (Var(s), Var(d)) => Ok(Var(d.inverse()?.mul(s))),
670 }
671 }
672
673 fn frobenius_map(&self, power: usize) -> Result<Self, SynthesisError> {
674 match self {
675 FpVar::Var(v) => v.frobenius_map(power).map(FpVar::Var),
676 FpVar::Constant(f) => {
677 let mut f = *f;
678 f.frobenius_map(power);
679 Ok(FpVar::Constant(f))
680 }
681 }
682 }
683
684 fn frobenius_map_in_place(&mut self, power: usize) -> Result<&mut Self, SynthesisError> {
685 *self = self.frobenius_map(power)?;
686 Ok(self)
687 }
688}
689
690/****************************************************************************/
691/****************************************************************************/
692
693impl_ops!(
694 FpVar<F>,
695 F,
696 Add,
697 add,
698 AddAssign,
699 add_assign,
700 |this: &'a FpVar<F>, other: &'a FpVar<F>| {
701 use FpVar::*;
702 match (this, other) {
703 (Constant(c1), Constant(c2)) => Constant(*c1 + *c2),
704 (Constant(c), Var(v)) | (Var(v), Constant(c)) => Var(v.add_constant(*c)),
705 (Var(v1), Var(v2)) => Var(v1.add(v2)),
706 }
707 },
708 |this: &'a FpVar<F>, other: F| { this + &FpVar::Constant(other) },
709 F: PrimeField,
710);
711
712impl_ops!(
713 FpVar<F>,
714 F,
715 Sub,
716 sub,
717 SubAssign,
718 sub_assign,
719 |this: &'a FpVar<F>, other: &'a FpVar<F>| {
720 use FpVar::*;
721 match (this, other) {
722 (Constant(c1), Constant(c2)) => Constant(*c1 - *c2),
723 (Var(v), Constant(c)) => Var(v.sub_constant(*c)),
724 (Constant(c), Var(v)) => Var(v.sub_constant(*c).negate()),
725 (Var(v1), Var(v2)) => Var(v1.sub(v2)),
726 }
727 },
728 |this: &'a FpVar<F>, other: F| { this - &FpVar::Constant(other) },
729 F: PrimeField
730);
731
732impl_ops!(
733 FpVar<F>,
734 F,
735 Mul,
736 mul,
737 MulAssign,
738 mul_assign,
739 |this: &'a FpVar<F>, other: &'a FpVar<F>| {
740 use FpVar::*;
741 match (this, other) {
742 (Constant(c1), Constant(c2)) => Constant(*c1 * *c2),
743 (Constant(c), Var(v)) | (Var(v), Constant(c)) => Var(v.mul_constant(*c)),
744 (Var(v1), Var(v2)) => Var(v1.mul(v2)),
745 }
746 },
747 |this: &'a FpVar<F>, other: F| {
748 if other.is_zero() {
749 FpVar::zero()
750 } else {
751 this * &FpVar::Constant(other)
752 }
753 },
754 F: PrimeField
755);
756
757/****************************************************************************/
758/****************************************************************************/
759
760impl<F: PrimeField> EqGadget<F> for FpVar<F> {
761 fn is_eq(&self, other: &Self) -> Result<Boolean<F>, SynthesisError> {
762 match (self, other) {
763 (Self::Constant(c1), Self::Constant(c2)) => Ok(Boolean::Constant(c1 == c2)),
764 (Self::Constant(c), Self::Var(v)) | (Self::Var(v), Self::Constant(c)) => {
765 let cs = v.cs.clone();
766 let c = AllocatedFp::new_constant(cs, c)?;
767 c.is_eq(v)
768 }
769 (Self::Var(v1), Self::Var(v2)) => v1.is_eq(v2),
770 }
771 }
772
773 #[inline]
774 fn conditional_enforce_equal(
775 &self,
776 other: &Self,
777 should_enforce: &Boolean<F>,
778 ) -> Result<(), SynthesisError> {
779 match (self, other) {
780 (Self::Constant(_), Self::Constant(_)) => Ok(()),
781 (Self::Constant(c), Self::Var(v)) | (Self::Var(v), Self::Constant(c)) => {
782 let cs = v.cs.clone();
783 let c = AllocatedFp::new_constant(cs, c)?;
784 c.conditional_enforce_equal(v, should_enforce)
785 }
786 (Self::Var(v1), Self::Var(v2)) => v1.conditional_enforce_equal(v2, should_enforce),
787 }
788 }
789
790 #[inline]
791 fn conditional_enforce_not_equal(
792 &self,
793 other: &Self,
794 should_enforce: &Boolean<F>,
795 ) -> Result<(), SynthesisError> {
796 match (self, other) {
797 (Self::Constant(_), Self::Constant(_)) => Ok(()),
798 (Self::Constant(c), Self::Var(v)) | (Self::Var(v), Self::Constant(c)) => {
799 let cs = v.cs.clone();
800 let c = AllocatedFp::new_constant(cs, c)?;
801 c.conditional_enforce_not_equal(v, should_enforce)
802 }
803 (Self::Var(v1), Self::Var(v2)) => v1.conditional_enforce_not_equal(v2, should_enforce),
804 }
805 }
806}
807
808impl<F: PrimeField> ToBitsGadget<F> for FpVar<F> {
809 /// Outputs the unique bit-wise decomposition of `self` in *big-endian*
810 /// form.
811 fn to_bits(&self) -> Result<Vec<Boolean<F>>, SynthesisError> {
812 match self {
813 Self::Constant(c) => UInt8::constant_vec(&to_bytes![c].unwrap()).to_bits(),
814 Self::Var(v) => v.to_bits(),
815 }
816 }
817
818 fn to_non_unique_bits(&self) -> Result<Vec<Boolean<F>>, SynthesisError> {
819 match self {
820 Self::Constant(c) => UInt8::constant_vec(&to_bytes![c].unwrap()).to_non_unique_bits(),
821 Self::Var(v) => v.to_non_unique_bits(),
822 }
823 }
824}
825
826impl<F: PrimeField> ToBytesGadget<F> for FpVar<F> {
827 /// Outputs the unique byte decomposition of `self` in *little-endian*
828 /// form.
829 fn to_bytes(&self) -> Result<Vec<UInt8<F>>, SynthesisError> {
830 match self {
831 Self::Constant(c) => Ok(UInt8::constant_vec(&to_bytes![c].unwrap())),
832 Self::Var(v) => v.to_bytes(),
833 }
834 }
835
836 fn to_non_unique_bytes(&self) -> Result<Vec<UInt8<F>>, SynthesisError> {
837 match self {
838 Self::Constant(c) => Ok(UInt8::constant_vec(&to_bytes![c].unwrap())),
839 Self::Var(v) => v.to_non_unique_bytes(),
840 }
841 }
842}
843
844impl<F: PrimeField> CondSelectGadget<F> for FpVar<F> {
845 #[inline]
846 fn conditionally_select(
847 cond: &Boolean<F>,
848 true_value: &Self,
849 false_value: &Self,
850 ) -> Result<Self, SynthesisError> {
851 match cond {
852 Boolean::Constant(true) => Ok(true_value.clone()),
853 Boolean::Constant(false) => Ok(false_value.clone()),
854 _ => {
855 match (true_value, false_value) {
856 (Self::Constant(t), Self::Constant(f)) => {
857 let is = AllocatedFp::from(cond.clone());
858 let not = AllocatedFp::from(cond.not());
859 // cond * t + (1 - cond) * f
860 Ok(is.mul_constant(*t).add(¬.mul_constant(*f)).into())
861 }
862 (_, _) => {
863 let cs = cond.cs().unwrap();
864 let true_value = match true_value {
865 Self::Constant(f) => AllocatedFp::new_constant(cs.clone(), f)?,
866 Self::Var(v) => v.clone(),
867 };
868 let false_value = match false_value {
869 Self::Constant(f) => AllocatedFp::new_constant(cs.clone(), f)?,
870 Self::Var(v) => v.clone(),
871 };
872 cond.select(&true_value, &false_value).map(Self::Var)
873 }
874 }
875 }
876 }
877 }
878}
879
880/// Uses two bits to perform a lookup into a table
881/// `b` is little-endian: `b[0]` is LSB.
882impl<F: PrimeField> TwoBitLookupGadget<F> for FpVar<F> {
883 type TableConstant = F;
884
885 fn two_bit_lookup(b: &[Boolean<F>], c: &[Self::TableConstant]) -> Result<Self, SynthesisError> {
886 debug_assert_eq!(b.len(), 2);
887 debug_assert_eq!(c.len(), 4);
888 if b.cs().is_some() {
889 AllocatedFp::two_bit_lookup(b, c).map(Self::Var)
890 } else {
891 let lsb = b[0].value()? as usize;
892 let msb = b[1].value()? as usize;
893 let index = lsb + (msb << 1);
894 Ok(Self::Constant(c[index]))
895 }
896 }
897}
898
899impl<F: PrimeField> ThreeBitCondNegLookupGadget<F> for FpVar<F> {
900 type TableConstant = F;
901
902 fn three_bit_cond_neg_lookup(
903 b: &[Boolean<F>],
904 b0b1: &Boolean<F>,
905 c: &[Self::TableConstant],
906 ) -> Result<Self, SynthesisError> {
907 debug_assert_eq!(b.len(), 3);
908 debug_assert_eq!(c.len(), 4);
909
910 if b.cs().or(b0b1.cs()).is_some() {
911 AllocatedFp::three_bit_cond_neg_lookup(b, b0b1, c).map(Self::Var)
912 } else {
913 let lsb = b[0].value()? as usize;
914 let msb = b[1].value()? as usize;
915 let index = lsb + (msb << 1);
916 let intermediate = c[index];
917
918 let is_negative = b[2].value()?;
919 let y = if is_negative {
920 -intermediate
921 } else {
922 intermediate
923 };
924 Ok(Self::Constant(y))
925 }
926 }
927}
928
929impl<F: PrimeField> AllocVar<F, F> for FpVar<F> {
930 fn new_variable<T: Borrow<F>>(
931 cs: impl Into<Namespace<F>>,
932 f: impl FnOnce() -> Result<T, SynthesisError>,
933 mode: AllocationMode,
934 ) -> Result<Self, SynthesisError> {
935 if mode == AllocationMode::Constant {
936 Ok(Self::Constant(*f()?.borrow()))
937 } else {
938 AllocatedFp::new_variable(cs, f, mode).map(Self::Var)
939 }
940 }
941}