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