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