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 #[tracing::instrument(target = "r1cs")]
720 fn frobenius_map(&self, power: usize) -> Result<Self, SynthesisError> {
721 match self {
722 FpVar::Var(v) => v.frobenius_map(power).map(FpVar::Var),
723 FpVar::Constant(f) => {
724 let mut f = *f;
725 f.frobenius_map(power);
726 Ok(FpVar::Constant(f))
727 }
728 }
729 }
730
731 #[tracing::instrument(target = "r1cs")]
732 fn frobenius_map_in_place(&mut self, power: usize) -> Result<&mut Self, SynthesisError> {
733 *self = self.frobenius_map(power)?;
734 Ok(self)
735 }
736}
737
738impl_ops!(
739 FpVar<F>,
740 F,
741 Add,
742 add,
743 AddAssign,
744 add_assign,
745 |this: &'a FpVar<F>, other: &'a FpVar<F>| {
746 use FpVar::*;
747 match (this, other) {
748 (Constant(c1), Constant(c2)) => Constant(*c1 + *c2),
749 (Constant(c), Var(v)) | (Var(v), Constant(c)) => Var(v.add_constant(*c)),
750 (Var(v1), Var(v2)) => Var(v1.add(v2)),
751 }
752 },
753 |this: &'a FpVar<F>, other: F| { this + &FpVar::Constant(other) },
754 F: PrimeField,
755);
756
757impl_ops!(
758 FpVar<F>,
759 F,
760 Sub,
761 sub,
762 SubAssign,
763 sub_assign,
764 |this: &'a FpVar<F>, other: &'a FpVar<F>| {
765 use FpVar::*;
766 match (this, other) {
767 (Constant(c1), Constant(c2)) => Constant(*c1 - *c2),
768 (Var(v), Constant(c)) => Var(v.sub_constant(*c)),
769 (Constant(c), Var(v)) => Var(v.sub_constant(*c).negate()),
770 (Var(v1), Var(v2)) => Var(v1.sub(v2)),
771 }
772 },
773 |this: &'a FpVar<F>, other: F| { this - &FpVar::Constant(other) },
774 F: PrimeField
775);
776
777impl_ops!(
778 FpVar<F>,
779 F,
780 Mul,
781 mul,
782 MulAssign,
783 mul_assign,
784 |this: &'a FpVar<F>, other: &'a FpVar<F>| {
785 use FpVar::*;
786 match (this, other) {
787 (Constant(c1), Constant(c2)) => Constant(*c1 * *c2),
788 (Constant(c), Var(v)) | (Var(v), Constant(c)) => Var(v.mul_constant(*c)),
789 (Var(v1), Var(v2)) => Var(v1.mul(v2)),
790 }
791 },
792 |this: &'a FpVar<F>, other: F| {
793 if other.is_zero() {
794 FpVar::zero()
795 } else {
796 this * &FpVar::Constant(other)
797 }
798 },
799 F: PrimeField
800);
801
802/// *************************************************************************
803/// *************************************************************************
804
805impl<F: PrimeField> EqGadget<F> for FpVar<F> {
806 #[tracing::instrument(target = "r1cs")]
807 fn is_eq(&self, other: &Self) -> Result<Boolean<F>, SynthesisError> {
808 match (self, other) {
809 (Self::Constant(c1), Self::Constant(c2)) => Ok(Boolean::Constant(c1 == c2)),
810 (Self::Constant(c), Self::Var(v)) | (Self::Var(v), Self::Constant(c)) => {
811 let cs = v.cs.clone();
812 let c = AllocatedFp::new_constant(cs, c)?;
813 c.is_eq(v)
814 }
815 (Self::Var(v1), Self::Var(v2)) => v1.is_eq(v2),
816 }
817 }
818
819 #[tracing::instrument(target = "r1cs")]
820 fn conditional_enforce_equal(
821 &self,
822 other: &Self,
823 should_enforce: &Boolean<F>,
824 ) -> Result<(), SynthesisError> {
825 match (self, other) {
826 (Self::Constant(_), Self::Constant(_)) => Ok(()),
827 (Self::Constant(c), Self::Var(v)) | (Self::Var(v), Self::Constant(c)) => {
828 let cs = v.cs.clone();
829 let c = AllocatedFp::new_constant(cs, c)?;
830 c.conditional_enforce_equal(v, should_enforce)
831 }
832 (Self::Var(v1), Self::Var(v2)) => v1.conditional_enforce_equal(v2, should_enforce),
833 }
834 }
835
836 #[tracing::instrument(target = "r1cs")]
837 fn conditional_enforce_not_equal(
838 &self,
839 other: &Self,
840 should_enforce: &Boolean<F>,
841 ) -> Result<(), SynthesisError> {
842 match (self, other) {
843 (Self::Constant(_), Self::Constant(_)) => Ok(()),
844 (Self::Constant(c), Self::Var(v)) | (Self::Var(v), Self::Constant(c)) => {
845 let cs = v.cs.clone();
846 let c = AllocatedFp::new_constant(cs, c)?;
847 c.conditional_enforce_not_equal(v, should_enforce)
848 }
849 (Self::Var(v1), Self::Var(v2)) => v1.conditional_enforce_not_equal(v2, should_enforce),
850 }
851 }
852}
853
854impl<F: PrimeField> ToBitsGadget<F> for FpVar<F> {
855 #[tracing::instrument(target = "r1cs")]
856 fn to_bits_le(&self) -> Result<Vec<Boolean<F>>, SynthesisError> {
857 match self {
858 Self::Constant(_) => self.to_non_unique_bits_le(),
859 Self::Var(v) => v.to_bits_le(),
860 }
861 }
862
863 #[tracing::instrument(target = "r1cs")]
864 fn to_non_unique_bits_le(&self) -> Result<Vec<Boolean<F>>, SynthesisError> {
865 use ark_ff::BitIteratorLE;
866 match self {
867 Self::Constant(c) => Ok(BitIteratorLE::new(&c.into_repr())
868 .take((F::Params::MODULUS_BITS) as usize)
869 .map(Boolean::constant)
870 .collect::<Vec<_>>()),
871 Self::Var(v) => v.to_non_unique_bits_le(),
872 }
873 }
874}
875
876impl<F: PrimeField> ToBytesGadget<F> for FpVar<F> {
877 /// Outputs the unique byte decomposition of `self` in *little-endian*
878 /// form.
879 #[tracing::instrument(target = "r1cs")]
880 fn to_bytes(&self) -> Result<Vec<UInt8<F>>, SynthesisError> {
881 match self {
882 Self::Constant(c) => Ok(UInt8::constant_vec(&ark_ff::to_bytes![c].unwrap())),
883 Self::Var(v) => v.to_bytes(),
884 }
885 }
886
887 #[tracing::instrument(target = "r1cs")]
888 fn to_non_unique_bytes(&self) -> Result<Vec<UInt8<F>>, SynthesisError> {
889 match self {
890 Self::Constant(c) => Ok(UInt8::constant_vec(&ark_ff::to_bytes![c].unwrap())),
891 Self::Var(v) => v.to_non_unique_bytes(),
892 }
893 }
894}
895
896impl<F: PrimeField> ToConstraintFieldGadget<F> for FpVar<F> {
897 #[tracing::instrument(target = "r1cs")]
898 fn to_constraint_field(&self) -> Result<Vec<FpVar<F>>, SynthesisError> {
899 Ok(vec![self.clone()])
900 }
901}
902
903impl<F: PrimeField> CondSelectGadget<F> for FpVar<F> {
904 #[tracing::instrument(target = "r1cs")]
905 fn conditionally_select(
906 cond: &Boolean<F>,
907 true_value: &Self,
908 false_value: &Self,
909 ) -> Result<Self, SynthesisError> {
910 match cond {
911 Boolean::Constant(true) => Ok(true_value.clone()),
912 Boolean::Constant(false) => Ok(false_value.clone()),
913 _ => {
914 match (true_value, false_value) {
915 (Self::Constant(t), Self::Constant(f)) => {
916 let is = AllocatedFp::from(cond.clone());
917 let not = AllocatedFp::from(cond.not());
918 // cond * t + (1 - cond) * f
919 Ok(is.mul_constant(*t).add(¬.mul_constant(*f)).into())
920 }
921 (..) => {
922 let cs = cond.cs();
923 let true_value = match true_value {
924 Self::Constant(f) => AllocatedFp::new_constant(cs.clone(), f)?,
925 Self::Var(v) => v.clone(),
926 };
927 let false_value = match false_value {
928 Self::Constant(f) => AllocatedFp::new_constant(cs, f)?,
929 Self::Var(v) => v.clone(),
930 };
931 cond.select(&true_value, &false_value).map(Self::Var)
932 }
933 }
934 }
935 }
936 }
937}
938
939/// Uses two bits to perform a lookup into a table
940/// `b` is little-endian: `b[0]` is LSB.
941impl<F: PrimeField> TwoBitLookupGadget<F> for FpVar<F> {
942 type TableConstant = F;
943
944 #[tracing::instrument(target = "r1cs")]
945 fn two_bit_lookup(b: &[Boolean<F>], c: &[Self::TableConstant]) -> Result<Self, SynthesisError> {
946 debug_assert_eq!(b.len(), 2);
947 debug_assert_eq!(c.len(), 4);
948 if b.is_constant() {
949 let lsb = usize::from(b[0].value()?);
950 let msb = usize::from(b[1].value()?);
951 let index = lsb + (msb << 1);
952 Ok(Self::Constant(c[index]))
953 } else {
954 AllocatedFp::two_bit_lookup(b, c).map(Self::Var)
955 }
956 }
957}
958
959impl<F: PrimeField> ThreeBitCondNegLookupGadget<F> for FpVar<F> {
960 type TableConstant = F;
961
962 #[tracing::instrument(target = "r1cs")]
963 fn three_bit_cond_neg_lookup(
964 b: &[Boolean<F>],
965 b0b1: &Boolean<F>,
966 c: &[Self::TableConstant],
967 ) -> Result<Self, SynthesisError> {
968 debug_assert_eq!(b.len(), 3);
969 debug_assert_eq!(c.len(), 4);
970
971 if b.cs().or(b0b1.cs()).is_none() {
972 // We only have constants
973
974 let lsb = usize::from(b[0].value()?);
975 let msb = usize::from(b[1].value()?);
976 let index = lsb + (msb << 1);
977 let intermediate = c[index];
978
979 let is_negative = b[2].value()?;
980 let y = if is_negative {
981 -intermediate
982 } else {
983 intermediate
984 };
985 Ok(Self::Constant(y))
986 } else {
987 AllocatedFp::three_bit_cond_neg_lookup(b, b0b1, c).map(Self::Var)
988 }
989 }
990}
991
992impl<F: PrimeField> AllocVar<F, F> for FpVar<F> {
993 fn new_variable<T: Borrow<F>>(
994 cs: impl Into<Namespace<F>>,
995 f: impl FnOnce() -> Result<T, SynthesisError>,
996 mode: AllocationMode,
997 ) -> Result<Self, SynthesisError> {
998 if mode == AllocationMode::Constant {
999 Ok(Self::Constant(*f()?.borrow()))
1000 } else {
1001 AllocatedFp::new_variable(cs, f, mode).map(Self::Var)
1002 }
1003 }
1004}