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