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 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 // The high level logic is as follows:
425 // We want to check that self - other != 0. We do this by checking that
426 // (self - other).inverse() exists. In more detail, we check the following:
427 // If `should_enforce == true`, then we set `multiplier = (self - other).inverse()`,
428 // and check that (self - other) * multiplier == 1. (i.e., that the inverse exists)
429 //
430 // If `should_enforce == false`, then we set `multiplier == 0`, and check that
431 // (self - other) * 0 == 0, which is always satisfied.
432 let multiplier = Self::new_witness(self.cs.clone(), || {
433 if should_enforce.value()? {
434 (self.value.get()? - other.value.get()?).inverse().get()
435 } else {
436 Ok(F::zero())
437 }
438 })?;
439
440 self.cs.enforce_constraint(
441 lc!() + self.variable - other.variable,
442 lc!() + multiplier.variable,
443 should_enforce.lc(),
444 )?;
445 Ok(())
446 }
447}
448
449/// *************************************************************************
450/// *************************************************************************
451
452impl<F: PrimeField> ToBitsGadget<F> for AllocatedFp<F> {
453 /// Outputs the unique bit-wise decomposition of `self` in *little-endian*
454 /// form.
455 ///
456 /// This method enforces that the output is in the field, i.e.
457 /// it invokes `Boolean::enforce_in_field_le` on the bit decomposition.
458 #[tracing::instrument(target = "r1cs")]
459 fn to_bits_le(&self) -> Result<Vec<Boolean<F>>, SynthesisError> {
460 let bits = self.to_non_unique_bits_le()?;
461 Boolean::enforce_in_field_le(&bits)?;
462 Ok(bits)
463 }
464
465 #[tracing::instrument(target = "r1cs")]
466 fn to_non_unique_bits_le(&self) -> Result<Vec<Boolean<F>>, SynthesisError> {
467 let cs = self.cs.clone();
468 use ark_ff::BitIteratorBE;
469 let mut bits = if let Some(value) = self.value {
470 let field_char = BitIteratorBE::new(F::characteristic());
471 let bits: Vec<_> = BitIteratorBE::new(value.into_bigint())
472 .zip(field_char)
473 .skip_while(|(_, c)| !c)
474 .map(|(b, _)| Some(b))
475 .collect();
476 assert_eq!(bits.len(), F::MODULUS_BIT_SIZE as usize);
477 bits
478 } else {
479 vec![None; F::MODULUS_BIT_SIZE as usize]
480 };
481
482 // Convert to little-endian
483 bits.reverse();
484
485 let bits: Vec<_> = bits
486 .into_iter()
487 .map(|b| Boolean::new_witness(cs.clone(), || b.get()))
488 .collect::<Result<_, _>>()?;
489
490 let mut lc = LinearCombination::zero();
491 let mut coeff = F::one();
492
493 for bit in bits.iter() {
494 lc = &lc + bit.lc() * coeff;
495
496 coeff.double_in_place();
497 }
498
499 lc = lc - &self.variable;
500
501 cs.enforce_constraint(lc!(), lc!(), lc)?;
502
503 Ok(bits)
504 }
505}
506
507impl<F: PrimeField> ToBytesGadget<F> for AllocatedFp<F> {
508 /// Outputs the unique byte decomposition of `self` in *little-endian*
509 /// form.
510 ///
511 /// This method enforces that the decomposition represents
512 /// an integer that is less than `F::MODULUS`.
513 #[tracing::instrument(target = "r1cs")]
514 fn to_bytes(&self) -> Result<Vec<UInt8<F>>, SynthesisError> {
515 let num_bits = F::BigInt::NUM_LIMBS * 64;
516 let mut bits = self.to_bits_le()?;
517 let remainder = core::iter::repeat(Boolean::constant(false)).take(num_bits - bits.len());
518 bits.extend(remainder);
519 let bytes = bits
520 .chunks(8)
521 .map(|chunk| UInt8::from_bits_le(chunk))
522 .collect();
523 Ok(bytes)
524 }
525
526 #[tracing::instrument(target = "r1cs")]
527 fn to_non_unique_bytes(&self) -> Result<Vec<UInt8<F>>, SynthesisError> {
528 let num_bits = F::BigInt::NUM_LIMBS * 64;
529 let mut bits = self.to_non_unique_bits_le()?;
530 let remainder = core::iter::repeat(Boolean::constant(false)).take(num_bits - bits.len());
531 bits.extend(remainder);
532 let bytes = bits
533 .chunks(8)
534 .map(|chunk| UInt8::from_bits_le(chunk))
535 .collect();
536 Ok(bytes)
537 }
538}
539
540impl<F: PrimeField> ToConstraintFieldGadget<F> for AllocatedFp<F> {
541 #[tracing::instrument(target = "r1cs")]
542 fn to_constraint_field(&self) -> Result<Vec<FpVar<F>>, SynthesisError> {
543 Ok(vec![self.clone().into()])
544 }
545}
546
547impl<F: PrimeField> CondSelectGadget<F> for AllocatedFp<F> {
548 #[inline]
549 #[tracing::instrument(target = "r1cs")]
550 fn conditionally_select(
551 cond: &Boolean<F>,
552 true_val: &Self,
553 false_val: &Self,
554 ) -> Result<Self, SynthesisError> {
555 match cond {
556 Boolean::Constant(true) => Ok(true_val.clone()),
557 Boolean::Constant(false) => Ok(false_val.clone()),
558 _ => {
559 let cs = cond.cs();
560 let result = Self::new_witness(cs.clone(), || {
561 cond.value()
562 .and_then(|c| if c { true_val } else { false_val }.value.get())
563 })?;
564 // a = self; b = other; c = cond;
565 //
566 // r = c * a + (1 - c) * b
567 // r = b + c * (a - b)
568 // c * (a - b) = r - b
569 cs.enforce_constraint(
570 cond.lc(),
571 lc!() + true_val.variable - false_val.variable,
572 lc!() + result.variable - false_val.variable,
573 )?;
574
575 Ok(result)
576 },
577 }
578 }
579}
580
581/// Uses two bits to perform a lookup into a table
582/// `b` is little-endian: `b[0]` is LSB.
583impl<F: PrimeField> TwoBitLookupGadget<F> for AllocatedFp<F> {
584 type TableConstant = F;
585 #[tracing::instrument(target = "r1cs")]
586 fn two_bit_lookup(b: &[Boolean<F>], c: &[Self::TableConstant]) -> Result<Self, SynthesisError> {
587 debug_assert_eq!(b.len(), 2);
588 debug_assert_eq!(c.len(), 4);
589 let result = Self::new_witness(b.cs(), || {
590 let lsb = usize::from(b[0].value()?);
591 let msb = usize::from(b[1].value()?);
592 let index = lsb + (msb << 1);
593 Ok(c[index])
594 })?;
595 let one = Variable::One;
596 b.cs().enforce_constraint(
597 lc!() + b[1].lc() * (c[3] - &c[2] - &c[1] + &c[0]) + (c[1] - &c[0], one),
598 lc!() + b[0].lc(),
599 lc!() + result.variable - (c[0], one) + b[1].lc() * (c[0] - &c[2]),
600 )?;
601
602 Ok(result)
603 }
604}
605
606impl<F: PrimeField> ThreeBitCondNegLookupGadget<F> for AllocatedFp<F> {
607 type TableConstant = F;
608
609 #[tracing::instrument(target = "r1cs")]
610 fn three_bit_cond_neg_lookup(
611 b: &[Boolean<F>],
612 b0b1: &Boolean<F>,
613 c: &[Self::TableConstant],
614 ) -> Result<Self, SynthesisError> {
615 debug_assert_eq!(b.len(), 3);
616 debug_assert_eq!(c.len(), 4);
617 let result = Self::new_witness(b.cs(), || {
618 let lsb = usize::from(b[0].value()?);
619 let msb = usize::from(b[1].value()?);
620 let index = lsb + (msb << 1);
621 let intermediate = c[index];
622
623 let is_negative = b[2].value()?;
624 let y = if is_negative {
625 -intermediate
626 } else {
627 intermediate
628 };
629 Ok(y)
630 })?;
631
632 let y_lc = b0b1.lc() * (c[3] - &c[2] - &c[1] + &c[0])
633 + b[0].lc() * (c[1] - &c[0])
634 + b[1].lc() * (c[2] - &c[0])
635 + (c[0], Variable::One);
636 // enforce y * (1 - 2 * b_2) == res
637 b.cs().enforce_constraint(
638 y_lc.clone(),
639 b[2].lc() * F::from(2u64).neg() + (F::one(), Variable::One),
640 lc!() + result.variable,
641 )?;
642
643 Ok(result)
644 }
645}
646
647impl<F: PrimeField> AllocVar<F, F> for AllocatedFp<F> {
648 fn new_variable<T: Borrow<F>>(
649 cs: impl Into<Namespace<F>>,
650 f: impl FnOnce() -> Result<T, SynthesisError>,
651 mode: AllocationMode,
652 ) -> Result<Self, SynthesisError> {
653 let ns = cs.into();
654 let cs = ns.cs();
655 if mode == AllocationMode::Constant {
656 let v = *f()?.borrow();
657 let lc = cs.new_lc(lc!() + (v, Variable::One))?;
658 Ok(Self::new(Some(v), lc, cs))
659 } else {
660 let mut value = None;
661 let value_generator = || {
662 value = Some(*f()?.borrow());
663 value.ok_or(SynthesisError::AssignmentMissing)
664 };
665 let variable = if mode == AllocationMode::Input {
666 cs.new_input_variable(value_generator)?
667 } else {
668 cs.new_witness_variable(value_generator)?
669 };
670 Ok(Self::new(value, variable, cs))
671 }
672 }
673}
674
675impl<F: PrimeField> FieldVar<F, F> for FpVar<F> {
676 fn constant(f: F) -> Self {
677 Self::Constant(f)
678 }
679
680 fn zero() -> Self {
681 Self::Constant(F::zero())
682 }
683
684 fn one() -> Self {
685 Self::Constant(F::one())
686 }
687
688 #[tracing::instrument(target = "r1cs")]
689 fn double(&self) -> Result<Self, SynthesisError> {
690 match self {
691 Self::Constant(c) => Ok(Self::Constant(c.double())),
692 Self::Var(v) => Ok(Self::Var(v.double()?)),
693 }
694 }
695
696 #[tracing::instrument(target = "r1cs")]
697 fn negate(&self) -> Result<Self, SynthesisError> {
698 match self {
699 Self::Constant(c) => Ok(Self::Constant(-*c)),
700 Self::Var(v) => Ok(Self::Var(v.negate())),
701 }
702 }
703
704 #[tracing::instrument(target = "r1cs")]
705 fn square(&self) -> Result<Self, SynthesisError> {
706 match self {
707 Self::Constant(c) => Ok(Self::Constant(c.square())),
708 Self::Var(v) => Ok(Self::Var(v.square()?)),
709 }
710 }
711
712 /// Enforce that `self * other == result`.
713 #[tracing::instrument(target = "r1cs")]
714 fn mul_equals(&self, other: &Self, result: &Self) -> Result<(), SynthesisError> {
715 use FpVar::*;
716 match (self, other, result) {
717 (Constant(_), Constant(_), Constant(_)) => Ok(()),
718 (Constant(_), Constant(_), _) | (Constant(_), Var(_), _) | (Var(_), Constant(_), _) => {
719 result.enforce_equal(&(self * other))
720 }, // this multiplication should be free
721 (Var(v1), Var(v2), Var(v3)) => v1.mul_equals(v2, v3),
722 (Var(v1), Var(v2), Constant(f)) => {
723 let cs = v1.cs.clone();
724 let v3 = AllocatedFp::new_constant(cs, f).unwrap();
725 v1.mul_equals(v2, &v3)
726 },
727 }
728 }
729
730 /// Enforce that `self * self == result`.
731 #[tracing::instrument(target = "r1cs")]
732 fn square_equals(&self, result: &Self) -> Result<(), SynthesisError> {
733 use FpVar::*;
734 match (self, result) {
735 (Constant(_), Constant(_)) => Ok(()),
736 (Constant(f), Var(r)) => {
737 let cs = r.cs.clone();
738 let v = AllocatedFp::new_witness(cs, || Ok(f))?;
739 v.square_equals(&r)
740 },
741 (Var(v), Constant(f)) => {
742 let cs = v.cs.clone();
743 let r = AllocatedFp::new_witness(cs, || Ok(f))?;
744 v.square_equals(&r)
745 },
746 (Var(v1), Var(v2)) => v1.square_equals(v2),
747 }
748 }
749
750 #[tracing::instrument(target = "r1cs")]
751 fn inverse(&self) -> Result<Self, SynthesisError> {
752 match self {
753 FpVar::Var(v) => v.inverse().map(FpVar::Var),
754 FpVar::Constant(f) => f.inverse().get().map(FpVar::Constant),
755 }
756 }
757
758 #[tracing::instrument(target = "r1cs")]
759 fn frobenius_map(&self, power: usize) -> Result<Self, SynthesisError> {
760 match self {
761 FpVar::Var(v) => v.frobenius_map(power).map(FpVar::Var),
762 FpVar::Constant(f) => {
763 let mut f = *f;
764 f.frobenius_map(power);
765 Ok(FpVar::Constant(f))
766 },
767 }
768 }
769
770 #[tracing::instrument(target = "r1cs")]
771 fn frobenius_map_in_place(&mut self, power: usize) -> Result<&mut Self, SynthesisError> {
772 *self = self.frobenius_map(power)?;
773 Ok(self)
774 }
775}
776
777impl_ops!(
778 FpVar<F>,
779 F,
780 Add,
781 add,
782 AddAssign,
783 add_assign,
784 |this: &'a FpVar<F>, other: &'a FpVar<F>| {
785 use FpVar::*;
786 match (this, other) {
787 (Constant(c1), Constant(c2)) => Constant(*c1 + *c2),
788 (Constant(c), Var(v)) | (Var(v), Constant(c)) => Var(v.add_constant(*c)),
789 (Var(v1), Var(v2)) => Var(v1.add(v2)),
790 }
791 },
792 |this: &'a FpVar<F>, other: F| { this + &FpVar::Constant(other) },
793 F: PrimeField,
794);
795
796impl_ops!(
797 FpVar<F>,
798 F,
799 Sub,
800 sub,
801 SubAssign,
802 sub_assign,
803 |this: &'a FpVar<F>, other: &'a FpVar<F>| {
804 use FpVar::*;
805 match (this, other) {
806 (Constant(c1), Constant(c2)) => Constant(*c1 - *c2),
807 (Var(v), Constant(c)) => Var(v.sub_constant(*c)),
808 (Constant(c), Var(v)) => Var(v.sub_constant(*c).negate()),
809 (Var(v1), Var(v2)) => Var(v1.sub(v2)),
810 }
811 },
812 |this: &'a FpVar<F>, other: F| { this - &FpVar::Constant(other) },
813 F: PrimeField
814);
815
816impl_ops!(
817 FpVar<F>,
818 F,
819 Mul,
820 mul,
821 MulAssign,
822 mul_assign,
823 |this: &'a FpVar<F>, other: &'a FpVar<F>| {
824 use FpVar::*;
825 match (this, other) {
826 (Constant(c1), Constant(c2)) => Constant(*c1 * *c2),
827 (Constant(c), Var(v)) | (Var(v), Constant(c)) => Var(v.mul_constant(*c)),
828 (Var(v1), Var(v2)) => Var(v1.mul(v2)),
829 }
830 },
831 |this: &'a FpVar<F>, other: F| {
832 if other.is_zero() {
833 FpVar::zero()
834 } else {
835 this * &FpVar::Constant(other)
836 }
837 },
838 F: PrimeField
839);
840
841/// *************************************************************************
842/// *************************************************************************
843
844impl<F: PrimeField> EqGadget<F> for FpVar<F> {
845 #[tracing::instrument(target = "r1cs")]
846 fn is_eq(&self, other: &Self) -> Result<Boolean<F>, SynthesisError> {
847 match (self, other) {
848 (Self::Constant(c1), Self::Constant(c2)) => Ok(Boolean::Constant(c1 == c2)),
849 (Self::Constant(c), Self::Var(v)) | (Self::Var(v), Self::Constant(c)) => {
850 let cs = v.cs.clone();
851 let c = AllocatedFp::new_constant(cs, c)?;
852 c.is_eq(v)
853 },
854 (Self::Var(v1), Self::Var(v2)) => v1.is_eq(v2),
855 }
856 }
857
858 #[tracing::instrument(target = "r1cs")]
859 fn conditional_enforce_equal(
860 &self,
861 other: &Self,
862 should_enforce: &Boolean<F>,
863 ) -> Result<(), SynthesisError> {
864 match (self, other) {
865 (Self::Constant(_), Self::Constant(_)) => Ok(()),
866 (Self::Constant(c), Self::Var(v)) | (Self::Var(v), Self::Constant(c)) => {
867 let cs = v.cs.clone();
868 let c = AllocatedFp::new_constant(cs, c)?;
869 c.conditional_enforce_equal(v, should_enforce)
870 },
871 (Self::Var(v1), Self::Var(v2)) => v1.conditional_enforce_equal(v2, should_enforce),
872 }
873 }
874
875 #[tracing::instrument(target = "r1cs")]
876 fn conditional_enforce_not_equal(
877 &self,
878 other: &Self,
879 should_enforce: &Boolean<F>,
880 ) -> Result<(), SynthesisError> {
881 match (self, other) {
882 (Self::Constant(_), Self::Constant(_)) => Ok(()),
883 (Self::Constant(c), Self::Var(v)) | (Self::Var(v), Self::Constant(c)) => {
884 let cs = v.cs.clone();
885 let c = AllocatedFp::new_constant(cs, c)?;
886 c.conditional_enforce_not_equal(v, should_enforce)
887 },
888 (Self::Var(v1), Self::Var(v2)) => v1.conditional_enforce_not_equal(v2, should_enforce),
889 }
890 }
891}
892
893impl<F: PrimeField> ToBitsGadget<F> for FpVar<F> {
894 #[tracing::instrument(target = "r1cs")]
895 fn to_bits_le(&self) -> Result<Vec<Boolean<F>>, SynthesisError> {
896 match self {
897 Self::Constant(_) => self.to_non_unique_bits_le(),
898 Self::Var(v) => v.to_bits_le(),
899 }
900 }
901
902 #[tracing::instrument(target = "r1cs")]
903 fn to_non_unique_bits_le(&self) -> Result<Vec<Boolean<F>>, SynthesisError> {
904 use ark_ff::BitIteratorLE;
905 match self {
906 Self::Constant(c) => Ok(BitIteratorLE::new(&c.into_bigint())
907 .take((F::MODULUS_BIT_SIZE) as usize)
908 .map(Boolean::constant)
909 .collect::<Vec<_>>()),
910 Self::Var(v) => v.to_non_unique_bits_le(),
911 }
912 }
913}
914
915impl<F: PrimeField> ToBytesGadget<F> for FpVar<F> {
916 /// Outputs the unique byte decomposition of `self` in *little-endian*
917 /// form.
918 #[tracing::instrument(target = "r1cs")]
919 fn to_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_bytes(),
923 }
924 }
925
926 #[tracing::instrument(target = "r1cs")]
927 fn to_non_unique_bytes(&self) -> Result<Vec<UInt8<F>>, SynthesisError> {
928 match self {
929 Self::Constant(c) => Ok(UInt8::constant_vec(&ark_ff::to_bytes![c].unwrap())),
930 Self::Var(v) => v.to_non_unique_bytes(),
931 }
932 }
933}
934
935impl<F: PrimeField> ToConstraintFieldGadget<F> for FpVar<F> {
936 #[tracing::instrument(target = "r1cs")]
937 fn to_constraint_field(&self) -> Result<Vec<FpVar<F>>, SynthesisError> {
938 Ok(vec![self.clone()])
939 }
940}
941
942impl<F: PrimeField> CondSelectGadget<F> for FpVar<F> {
943 #[tracing::instrument(target = "r1cs")]
944 fn conditionally_select(
945 cond: &Boolean<F>,
946 true_value: &Self,
947 false_value: &Self,
948 ) -> Result<Self, SynthesisError> {
949 match cond {
950 Boolean::Constant(true) => Ok(true_value.clone()),
951 Boolean::Constant(false) => Ok(false_value.clone()),
952 _ => {
953 match (true_value, false_value) {
954 (Self::Constant(t), Self::Constant(f)) => {
955 let is = AllocatedFp::from(cond.clone());
956 let not = AllocatedFp::from(cond.not());
957 // cond * t + (1 - cond) * f
958 Ok(is.mul_constant(*t).add(¬.mul_constant(*f)).into())
959 },
960 (..) => {
961 let cs = cond.cs();
962 let true_value = match true_value {
963 Self::Constant(f) => AllocatedFp::new_constant(cs.clone(), f)?,
964 Self::Var(v) => v.clone(),
965 };
966 let false_value = match false_value {
967 Self::Constant(f) => AllocatedFp::new_constant(cs, f)?,
968 Self::Var(v) => v.clone(),
969 };
970 cond.select(&true_value, &false_value).map(Self::Var)
971 },
972 }
973 },
974 }
975 }
976}
977
978/// Uses two bits to perform a lookup into a table
979/// `b` is little-endian: `b[0]` is LSB.
980impl<F: PrimeField> TwoBitLookupGadget<F> for FpVar<F> {
981 type TableConstant = F;
982
983 #[tracing::instrument(target = "r1cs")]
984 fn two_bit_lookup(b: &[Boolean<F>], c: &[Self::TableConstant]) -> Result<Self, SynthesisError> {
985 debug_assert_eq!(b.len(), 2);
986 debug_assert_eq!(c.len(), 4);
987 if b.is_constant() {
988 let lsb = usize::from(b[0].value()?);
989 let msb = usize::from(b[1].value()?);
990 let index = lsb + (msb << 1);
991 Ok(Self::Constant(c[index]))
992 } else {
993 AllocatedFp::two_bit_lookup(b, c).map(Self::Var)
994 }
995 }
996}
997
998impl<F: PrimeField> ThreeBitCondNegLookupGadget<F> for FpVar<F> {
999 type TableConstant = F;
1000
1001 #[tracing::instrument(target = "r1cs")]
1002 fn three_bit_cond_neg_lookup(
1003 b: &[Boolean<F>],
1004 b0b1: &Boolean<F>,
1005 c: &[Self::TableConstant],
1006 ) -> Result<Self, SynthesisError> {
1007 debug_assert_eq!(b.len(), 3);
1008 debug_assert_eq!(c.len(), 4);
1009
1010 if b.cs().or(b0b1.cs()).is_none() {
1011 // We only have constants
1012
1013 let lsb = usize::from(b[0].value()?);
1014 let msb = usize::from(b[1].value()?);
1015 let index = lsb + (msb << 1);
1016 let intermediate = c[index];
1017
1018 let is_negative = b[2].value()?;
1019 let y = if is_negative {
1020 -intermediate
1021 } else {
1022 intermediate
1023 };
1024 Ok(Self::Constant(y))
1025 } else {
1026 AllocatedFp::three_bit_cond_neg_lookup(b, b0b1, c).map(Self::Var)
1027 }
1028 }
1029}
1030
1031impl<F: PrimeField> AllocVar<F, F> for FpVar<F> {
1032 fn new_variable<T: Borrow<F>>(
1033 cs: impl Into<Namespace<F>>,
1034 f: impl FnOnce() -> Result<T, SynthesisError>,
1035 mode: AllocationMode,
1036 ) -> Result<Self, SynthesisError> {
1037 if mode == AllocationMode::Constant {
1038 Ok(Self::Constant(*f()?.borrow()))
1039 } else {
1040 AllocatedFp::new_variable(cs, f, mode).map(Self::Var)
1041 }
1042 }
1043}
1044
1045impl<'a, F: PrimeField> Sum<&'a FpVar<F>> for FpVar<F> {
1046 fn sum<I: Iterator<Item = &'a FpVar<F>>>(iter: I) -> FpVar<F> {
1047 let mut sum_constants = F::zero();
1048 let sum_variables = FpVar::Var(AllocatedFp::<F>::addmany(iter.filter_map(|x| match x {
1049 FpVar::Constant(c) => {
1050 sum_constants += c;
1051 None
1052 },
1053 FpVar::Var(v) => Some(v),
1054 })));
1055
1056 let sum = sum_variables + sum_constants;
1057 sum
1058 }
1059}
1060
1061#[cfg(test)]
1062mod test {
1063 use crate::alloc::{AllocVar, AllocationMode};
1064 use crate::eq::EqGadget;
1065 use crate::fields::fp::FpVar;
1066 use crate::R1CSVar;
1067 use ark_relations::r1cs::ConstraintSystem;
1068 use ark_std::{UniformRand, Zero};
1069 use ark_test_curves::bls12_381::Fr;
1070
1071 #[test]
1072 fn test_sum_fpvar() {
1073 let mut rng = ark_std::test_rng();
1074 let cs = ConstraintSystem::new_ref();
1075
1076 let mut sum_expected = Fr::zero();
1077
1078 let mut v = Vec::new();
1079 for _ in 0..10 {
1080 let a = Fr::rand(&mut rng);
1081 sum_expected += &a;
1082 v.push(
1083 FpVar::<Fr>::new_variable(cs.clone(), || Ok(a), AllocationMode::Constant).unwrap(),
1084 );
1085 }
1086 for _ in 0..10 {
1087 let a = Fr::rand(&mut rng);
1088 sum_expected += &a;
1089 v.push(
1090 FpVar::<Fr>::new_variable(cs.clone(), || Ok(a), AllocationMode::Witness).unwrap(),
1091 );
1092 }
1093
1094 let sum: FpVar<Fr> = v.iter().sum();
1095
1096 sum.enforce_equal(&FpVar::Constant(sum_expected)).unwrap();
1097
1098 assert!(cs.is_satisfied().unwrap());
1099 assert_eq!(sum.value().unwrap(), sum_expected);
1100 }
1101}