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