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