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