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