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 b.cs().enforce_constraint(
598 y_lc.clone() + y_lc.clone(),
599 b[2].lc(),
600 y_lc - result.variable,
601 )?;
602
603 Ok(result)
604 }
605}
606
607impl<F: PrimeField> AllocVar<F, F> for AllocatedFp<F> {
608 fn new_variable<T: Borrow<F>>(
609 cs: impl Into<Namespace<F>>,
610 f: impl FnOnce() -> Result<T, SynthesisError>,
611 mode: AllocationMode,
612 ) -> Result<Self, SynthesisError> {
613 let ns = cs.into();
614 let cs = ns.cs();
615 if mode == AllocationMode::Constant {
616 let v = *f()?.borrow();
617 let lc = cs.new_lc(lc!() + (v, Variable::One))?;
618 Ok(Self::new(Some(v), lc, cs))
619 } else {
620 let mut value = None;
621 let value_generator = || {
622 value = Some(*f()?.borrow());
623 value.ok_or(SynthesisError::AssignmentMissing)
624 };
625 let variable = if mode == AllocationMode::Input {
626 cs.new_input_variable(value_generator)?
627 } else {
628 cs.new_witness_variable(value_generator)?
629 };
630 Ok(Self::new(value, variable, cs))
631 }
632 }
633}
634
635impl<F: PrimeField> FieldVar<F, F> for FpVar<F> {
636 fn constant(f: F) -> Self {
637 Self::Constant(f)
638 }
639
640 fn zero() -> Self {
641 Self::Constant(F::zero())
642 }
643
644 fn one() -> Self {
645 Self::Constant(F::one())
646 }
647
648 #[tracing::instrument(target = "r1cs")]
649 fn double(&self) -> Result<Self, SynthesisError> {
650 match self {
651 Self::Constant(c) => Ok(Self::Constant(c.double())),
652 Self::Var(v) => Ok(Self::Var(v.double()?)),
653 }
654 }
655
656 #[tracing::instrument(target = "r1cs")]
657 fn negate(&self) -> Result<Self, SynthesisError> {
658 match self {
659 Self::Constant(c) => Ok(Self::Constant(-*c)),
660 Self::Var(v) => Ok(Self::Var(v.negate())),
661 }
662 }
663
664 #[tracing::instrument(target = "r1cs")]
665 fn square(&self) -> Result<Self, SynthesisError> {
666 match self {
667 Self::Constant(c) => Ok(Self::Constant(c.square())),
668 Self::Var(v) => Ok(Self::Var(v.square()?)),
669 }
670 }
671
672 /// Enforce that `self * other == result`.
673 #[tracing::instrument(target = "r1cs")]
674 fn mul_equals(&self, other: &Self, result: &Self) -> Result<(), SynthesisError> {
675 use FpVar::*;
676 match (self, other, result) {
677 (Constant(_), Constant(_), Constant(_)) => Ok(()),
678 (Constant(_), Constant(_), _) | (Constant(_), Var(_), _) | (Var(_), Constant(_), _) => {
679 result.enforce_equal(&(self * other))
680 } // this multiplication should be free
681 (Var(v1), Var(v2), Var(v3)) => v1.mul_equals(v2, v3),
682 (Var(v1), Var(v2), Constant(f)) => {
683 let cs = v1.cs.clone();
684 let v3 = AllocatedFp::new_constant(cs, f).unwrap();
685 v1.mul_equals(v2, &v3)
686 }
687 }
688 }
689
690 /// Enforce that `self * self == result`.
691 #[tracing::instrument(target = "r1cs")]
692 fn square_equals(&self, result: &Self) -> Result<(), SynthesisError> {
693 use FpVar::*;
694 match (self, result) {
695 (Constant(_), Constant(_)) => Ok(()),
696 (Constant(f), Var(r)) => {
697 let cs = r.cs.clone();
698 let v = AllocatedFp::new_witness(cs, || Ok(f))?;
699 v.square_equals(&r)
700 }
701 (Var(v), Constant(f)) => {
702 let cs = v.cs.clone();
703 let r = AllocatedFp::new_witness(cs, || Ok(f))?;
704 v.square_equals(&r)
705 }
706 (Var(v1), Var(v2)) => v1.square_equals(v2),
707 }
708 }
709
710 #[tracing::instrument(target = "r1cs")]
711 fn inverse(&self) -> Result<Self, SynthesisError> {
712 match self {
713 FpVar::Var(v) => v.inverse().map(FpVar::Var),
714 FpVar::Constant(f) => f.inverse().get().map(FpVar::Constant),
715 }
716 }
717
718 /// Returns (self / denominator), but requires fewer constraints than
719 /// self * denominator.inverse()
720 /// It is up to the caller to ensure that denominator is non-zero,
721 /// since in that case the result is unconstrained.
722 #[tracing::instrument(target = "r1cs")]
723 fn mul_by_inverse(&self, denominator: &Self) -> Result<Self, SynthesisError> {
724 use FpVar::*;
725 match (self, denominator) {
726 (Constant(s), Constant(d)) => Ok(Constant(*s / *d)),
727 (Var(s), Constant(d)) => Ok(Var(s.mul_constant(d.inverse().get()?))),
728 (Constant(s), Var(d)) => Ok(Var(d.inverse()?.mul_constant(*s))),
729 (Var(s), Var(d)) => Ok(Var(d.inverse()?.mul(s))),
730 }
731 }
732
733 #[tracing::instrument(target = "r1cs")]
734 fn frobenius_map(&self, power: usize) -> Result<Self, SynthesisError> {
735 match self {
736 FpVar::Var(v) => v.frobenius_map(power).map(FpVar::Var),
737 FpVar::Constant(f) => {
738 let mut f = *f;
739 f.frobenius_map(power);
740 Ok(FpVar::Constant(f))
741 }
742 }
743 }
744
745 #[tracing::instrument(target = "r1cs")]
746 fn frobenius_map_in_place(&mut self, power: usize) -> Result<&mut Self, SynthesisError> {
747 *self = self.frobenius_map(power)?;
748 Ok(self)
749 }
750}
751
752impl_ops!(
753 FpVar<F>,
754 F,
755 Add,
756 add,
757 AddAssign,
758 add_assign,
759 |this: &'a FpVar<F>, other: &'a FpVar<F>| {
760 use FpVar::*;
761 match (this, other) {
762 (Constant(c1), Constant(c2)) => Constant(*c1 + *c2),
763 (Constant(c), Var(v)) | (Var(v), Constant(c)) => Var(v.add_constant(*c)),
764 (Var(v1), Var(v2)) => Var(v1.add(v2)),
765 }
766 },
767 |this: &'a FpVar<F>, other: F| { this + &FpVar::Constant(other) },
768 F: PrimeField,
769);
770
771impl_ops!(
772 FpVar<F>,
773 F,
774 Sub,
775 sub,
776 SubAssign,
777 sub_assign,
778 |this: &'a FpVar<F>, other: &'a FpVar<F>| {
779 use FpVar::*;
780 match (this, other) {
781 (Constant(c1), Constant(c2)) => Constant(*c1 - *c2),
782 (Var(v), Constant(c)) => Var(v.sub_constant(*c)),
783 (Constant(c), Var(v)) => Var(v.sub_constant(*c).negate()),
784 (Var(v1), Var(v2)) => Var(v1.sub(v2)),
785 }
786 },
787 |this: &'a FpVar<F>, other: F| { this - &FpVar::Constant(other) },
788 F: PrimeField
789);
790
791impl_ops!(
792 FpVar<F>,
793 F,
794 Mul,
795 mul,
796 MulAssign,
797 mul_assign,
798 |this: &'a FpVar<F>, other: &'a FpVar<F>| {
799 use FpVar::*;
800 match (this, other) {
801 (Constant(c1), Constant(c2)) => Constant(*c1 * *c2),
802 (Constant(c), Var(v)) | (Var(v), Constant(c)) => Var(v.mul_constant(*c)),
803 (Var(v1), Var(v2)) => Var(v1.mul(v2)),
804 }
805 },
806 |this: &'a FpVar<F>, other: F| {
807 if other.is_zero() {
808 FpVar::zero()
809 } else {
810 this * &FpVar::Constant(other)
811 }
812 },
813 F: PrimeField
814);
815
816/// *************************************************************************
817/// *************************************************************************
818
819impl<F: PrimeField> EqGadget<F> for FpVar<F> {
820 #[tracing::instrument(target = "r1cs")]
821 fn is_eq(&self, other: &Self) -> Result<Boolean<F>, SynthesisError> {
822 match (self, other) {
823 (Self::Constant(c1), Self::Constant(c2)) => Ok(Boolean::Constant(c1 == c2)),
824 (Self::Constant(c), Self::Var(v)) | (Self::Var(v), Self::Constant(c)) => {
825 let cs = v.cs.clone();
826 let c = AllocatedFp::new_constant(cs, c)?;
827 c.is_eq(v)
828 }
829 (Self::Var(v1), Self::Var(v2)) => v1.is_eq(v2),
830 }
831 }
832
833 #[tracing::instrument(target = "r1cs")]
834 fn conditional_enforce_equal(
835 &self,
836 other: &Self,
837 should_enforce: &Boolean<F>,
838 ) -> Result<(), SynthesisError> {
839 match (self, other) {
840 (Self::Constant(_), Self::Constant(_)) => Ok(()),
841 (Self::Constant(c), Self::Var(v)) | (Self::Var(v), Self::Constant(c)) => {
842 let cs = v.cs.clone();
843 let c = AllocatedFp::new_constant(cs, c)?;
844 c.conditional_enforce_equal(v, should_enforce)
845 }
846 (Self::Var(v1), Self::Var(v2)) => v1.conditional_enforce_equal(v2, should_enforce),
847 }
848 }
849
850 #[tracing::instrument(target = "r1cs")]
851 fn conditional_enforce_not_equal(
852 &self,
853 other: &Self,
854 should_enforce: &Boolean<F>,
855 ) -> Result<(), SynthesisError> {
856 match (self, other) {
857 (Self::Constant(_), Self::Constant(_)) => Ok(()),
858 (Self::Constant(c), Self::Var(v)) | (Self::Var(v), Self::Constant(c)) => {
859 let cs = v.cs.clone();
860 let c = AllocatedFp::new_constant(cs, c)?;
861 c.conditional_enforce_not_equal(v, should_enforce)
862 }
863 (Self::Var(v1), Self::Var(v2)) => v1.conditional_enforce_not_equal(v2, should_enforce),
864 }
865 }
866}
867
868impl<F: PrimeField> ToBitsGadget<F> for FpVar<F> {
869 #[tracing::instrument(target = "r1cs")]
870 fn to_bits_le(&self) -> Result<Vec<Boolean<F>>, SynthesisError> {
871 match self {
872 Self::Constant(_) => self.to_non_unique_bits_le(),
873 Self::Var(v) => v.to_bits_le(),
874 }
875 }
876
877 #[tracing::instrument(target = "r1cs")]
878 fn to_non_unique_bits_le(&self) -> Result<Vec<Boolean<F>>, SynthesisError> {
879 use ark_ff::BitIteratorLE;
880 match self {
881 Self::Constant(c) => Ok(BitIteratorLE::new(&c.into_repr())
882 .take((F::Params::MODULUS_BITS) as usize)
883 .map(Boolean::constant)
884 .collect::<Vec<_>>()),
885 Self::Var(v) => v.to_non_unique_bits_le(),
886 }
887 }
888}
889
890impl<F: PrimeField> ToBytesGadget<F> for FpVar<F> {
891 /// Outputs the unique byte decomposition of `self` in *little-endian*
892 /// form.
893 #[tracing::instrument(target = "r1cs")]
894 fn to_bytes(&self) -> Result<Vec<UInt8<F>>, SynthesisError> {
895 match self {
896 Self::Constant(c) => Ok(UInt8::constant_vec(&ark_ff::to_bytes![c].unwrap())),
897 Self::Var(v) => v.to_bytes(),
898 }
899 }
900
901 #[tracing::instrument(target = "r1cs")]
902 fn to_non_unique_bytes(&self) -> Result<Vec<UInt8<F>>, SynthesisError> {
903 match self {
904 Self::Constant(c) => Ok(UInt8::constant_vec(&ark_ff::to_bytes![c].unwrap())),
905 Self::Var(v) => v.to_non_unique_bytes(),
906 }
907 }
908}
909
910impl<F: PrimeField> ToConstraintFieldGadget<F> for FpVar<F> {
911 #[tracing::instrument(target = "r1cs")]
912 fn to_constraint_field(&self) -> Result<Vec<FpVar<F>>, SynthesisError> {
913 Ok(vec![self.clone()])
914 }
915}
916
917impl<F: PrimeField> CondSelectGadget<F> for FpVar<F> {
918 #[tracing::instrument(target = "r1cs")]
919 fn conditionally_select(
920 cond: &Boolean<F>,
921 true_value: &Self,
922 false_value: &Self,
923 ) -> Result<Self, SynthesisError> {
924 match cond {
925 Boolean::Constant(true) => Ok(true_value.clone()),
926 Boolean::Constant(false) => Ok(false_value.clone()),
927 _ => {
928 match (true_value, false_value) {
929 (Self::Constant(t), Self::Constant(f)) => {
930 let is = AllocatedFp::from(cond.clone());
931 let not = AllocatedFp::from(cond.not());
932 // cond * t + (1 - cond) * f
933 Ok(is.mul_constant(*t).add(¬.mul_constant(*f)).into())
934 }
935 (..) => {
936 let cs = cond.cs();
937 let true_value = match true_value {
938 Self::Constant(f) => AllocatedFp::new_constant(cs.clone(), f)?,
939 Self::Var(v) => v.clone(),
940 };
941 let false_value = match false_value {
942 Self::Constant(f) => AllocatedFp::new_constant(cs, f)?,
943 Self::Var(v) => v.clone(),
944 };
945 cond.select(&true_value, &false_value).map(Self::Var)
946 }
947 }
948 }
949 }
950 }
951}
952
953/// Uses two bits to perform a lookup into a table
954/// `b` is little-endian: `b[0]` is LSB.
955impl<F: PrimeField> TwoBitLookupGadget<F> for FpVar<F> {
956 type TableConstant = F;
957
958 #[tracing::instrument(target = "r1cs")]
959 fn two_bit_lookup(b: &[Boolean<F>], c: &[Self::TableConstant]) -> Result<Self, SynthesisError> {
960 debug_assert_eq!(b.len(), 2);
961 debug_assert_eq!(c.len(), 4);
962 if b.is_constant() {
963 let lsb = usize::from(b[0].value()?);
964 let msb = usize::from(b[1].value()?);
965 let index = lsb + (msb << 1);
966 Ok(Self::Constant(c[index]))
967 } else {
968 AllocatedFp::two_bit_lookup(b, c).map(Self::Var)
969 }
970 }
971}
972
973impl<F: PrimeField> ThreeBitCondNegLookupGadget<F> for FpVar<F> {
974 type TableConstant = F;
975
976 #[tracing::instrument(target = "r1cs")]
977 fn three_bit_cond_neg_lookup(
978 b: &[Boolean<F>],
979 b0b1: &Boolean<F>,
980 c: &[Self::TableConstant],
981 ) -> Result<Self, SynthesisError> {
982 debug_assert_eq!(b.len(), 3);
983 debug_assert_eq!(c.len(), 4);
984
985 if b.cs().or(b0b1.cs()).is_none() {
986 // We only have constants
987
988 let lsb = usize::from(b[0].value()?);
989 let msb = usize::from(b[1].value()?);
990 let index = lsb + (msb << 1);
991 let intermediate = c[index];
992
993 let is_negative = b[2].value()?;
994 let y = if is_negative {
995 -intermediate
996 } else {
997 intermediate
998 };
999 Ok(Self::Constant(y))
1000 } else {
1001 AllocatedFp::three_bit_cond_neg_lookup(b, b0b1, c).map(Self::Var)
1002 }
1003 }
1004}
1005
1006impl<F: PrimeField> AllocVar<F, F> for FpVar<F> {
1007 fn new_variable<T: Borrow<F>>(
1008 cs: impl Into<Namespace<F>>,
1009 f: impl FnOnce() -> Result<T, SynthesisError>,
1010 mode: AllocationMode,
1011 ) -> Result<Self, SynthesisError> {
1012 if mode == AllocationMode::Constant {
1013 Ok(Self::Constant(*f()?.borrow()))
1014 } else {
1015 AllocatedFp::new_variable(cs, f, mode).map(Self::Var)
1016 }
1017 }
1018}