ark-r1cs-std/r1cs-std/src/fields/fp/mod.rs
r1cs-std/src/fields/fp/mod.rsRaw
1use algebra::{bytes::ToBytes, FpParameters, PrimeField};
2use r1cs_core::{
3 ConstraintSystem,
4 ConstraintVar::{self, *},
5 LinearCombination, SynthesisError,
6};
7
8use core::borrow::Borrow;
9
10use crate::{boolean::AllocatedBit, prelude::*, Assignment, Vec};
11
12pub mod cmp;
13
14#[derive(Debug)]
15pub struct FpGadget<F: PrimeField> {
16 pub value: Option<F>,
17 pub variable: ConstraintVar<F>,
18}
19
20impl<F: PrimeField> FpGadget<F> {
21 #[inline]
22 pub fn from<CS: ConstraintSystem<F>>(mut cs: CS, value: &F) -> Self {
23 Self::alloc(cs.ns(|| "from"), || Ok(*value)).unwrap()
24 }
25
26 fn is_constant(&self) -> bool {
27 match &self.variable {
28 // If you don't do alloc_constant, you are guaranteed to get a variable,
29 // hence we assume that all variables are not the constant variable.
30 // Technically this omits recognizing some constants.
31 // E.g. given variables w,x,y,z with constraints:
32 // w = x + 1
33 // y = -x + 1
34 // and then created the variable z = w + y,
35 // this would not recognize that z is in fact a constant.
36 // Since this is an edge case, this is left as a TODO.
37 Var(_v) => false,
38 LC(l) => l.is_constant(),
39 }
40 }
41}
42
43impl<F: PrimeField> ToConstraintFieldGadget<F> for FpGadget<F> {
44 fn to_constraint_field<CS: ConstraintSystem<F>>(
45 &self,
46 _cs: CS,
47 ) -> Result<Vec<FpGadget<F>>, SynthesisError> {
48 Ok(vec![self.clone()])
49 }
50}
51
52impl<F: PrimeField> FieldGadget<F, F> for FpGadget<F> {
53 type Variable = ConstraintVar<F>;
54
55 #[inline]
56 fn get_value(&self) -> Option<F> {
57 self.value
58 }
59
60 #[inline]
61 fn get_variable(&self) -> Self::Variable {
62 self.variable.clone()
63 }
64
65 #[inline]
66 fn zero<CS: ConstraintSystem<F>>(_cs: CS) -> Result<Self, SynthesisError> {
67 let value = Some(F::zero());
68 Ok(FpGadget {
69 value,
70 variable: ConstraintVar::zero(),
71 })
72 }
73
74 #[inline]
75 fn one<CS: ConstraintSystem<F>>(_cs: CS) -> Result<Self, SynthesisError> {
76 let value = Some(F::one());
77 Ok(FpGadget {
78 value,
79 variable: CS::one().into(),
80 })
81 }
82
83 #[inline]
84 fn conditionally_add_constant<CS: ConstraintSystem<F>>(
85 &self,
86 mut _cs: CS,
87 bit: &Boolean,
88 coeff: F,
89 ) -> Result<Self, SynthesisError> {
90 let value = match (self.value, bit.get_value()) {
91 (Some(v), Some(b)) => Some(if b { v + &coeff } else { v }),
92 (..) => None,
93 };
94 Ok(FpGadget {
95 value,
96 variable: LC(bit.lc(CS::one(), coeff)) + &self.variable,
97 })
98 }
99
100 #[inline]
101 fn add<CS: ConstraintSystem<F>>(
102 &self,
103 mut _cs: CS,
104 other: &Self,
105 ) -> Result<Self, SynthesisError> {
106 let value = match (self.value, other.value) {
107 (Some(val1), Some(val2)) => Some(val1 + &val2),
108 (..) => None,
109 };
110
111 Ok(FpGadget {
112 value,
113 variable: &self.variable + &other.variable,
114 })
115 }
116
117 fn double<CS: ConstraintSystem<F>>(&self, _cs: CS) -> Result<Self, SynthesisError> {
118 let value = self.value.map(|val| val.double());
119 let mut variable = self.variable.clone();
120 variable.double_in_place();
121 Ok(FpGadget { value, variable })
122 }
123
124 fn double_in_place<CS: ConstraintSystem<F>>(
125 &mut self,
126 _cs: CS,
127 ) -> Result<&mut Self, SynthesisError> {
128 self.value.as_mut().map(|val| val.double_in_place());
129 self.variable.double_in_place();
130 Ok(self)
131 }
132
133 #[inline]
134 fn sub<CS: ConstraintSystem<F>>(
135 &self,
136 mut _cs: CS,
137 other: &Self,
138 ) -> Result<Self, SynthesisError> {
139 let value = match (self.value, other.value) {
140 (Some(val1), Some(val2)) => Some(val1 - &val2),
141 (..) => None,
142 };
143
144 Ok(FpGadget {
145 value,
146 variable: &self.variable - &other.variable,
147 })
148 }
149
150 #[inline]
151 fn negate<CS: ConstraintSystem<F>>(&self, cs: CS) -> Result<Self, SynthesisError> {
152 let mut result = self.clone();
153 result.negate_in_place(cs)?;
154 Ok(result)
155 }
156
157 #[inline]
158 fn negate_in_place<CS: ConstraintSystem<F>>(
159 &mut self,
160 _cs: CS,
161 ) -> Result<&mut Self, SynthesisError> {
162 self.value.as_mut().map(|val| *val = -(*val));
163 self.variable.negate_in_place();
164 Ok(self)
165 }
166
167 #[inline]
168 fn mul<CS: ConstraintSystem<F>>(
169 &self,
170 mut cs: CS,
171 other: &Self,
172 ) -> Result<Self, SynthesisError> {
173 // Apply constant folding if it applies
174 // unwrap is used, because these values are guaranteed to exist.
175 if other.is_constant() {
176 return self.mul_by_constant(cs, &other.get_value().unwrap());
177 } else if self.is_constant() {
178 return other.mul_by_constant(cs, &self.get_value().unwrap());
179 }
180
181 let product = Self::alloc(cs.ns(|| "mul"), || {
182 Ok(self.value.get()? * &other.value.get()?)
183 })?;
184 cs.enforce(
185 || "mul_constraint",
186 |lc| &self.variable + lc,
187 |lc| &other.variable + lc,
188 |lc| &product.variable + lc,
189 );
190 Ok(product)
191 }
192
193 #[inline]
194 fn add_constant<CS: ConstraintSystem<F>>(
195 &self,
196 _cs: CS,
197 other: &F,
198 ) -> Result<Self, SynthesisError> {
199 let value = self.value.map(|val| val + other);
200 Ok(FpGadget {
201 value,
202 variable: self.variable.clone() + (*other, CS::one()),
203 })
204 }
205
206 #[inline]
207 fn add_constant_in_place<CS: ConstraintSystem<F>>(
208 &mut self,
209 _cs: CS,
210 other: &F,
211 ) -> Result<&mut Self, SynthesisError> {
212 self.value.as_mut().map(|val| *val += other);
213 self.variable += (*other, CS::one());
214 Ok(self)
215 }
216
217 #[inline]
218 fn mul_by_constant<CS: ConstraintSystem<F>>(
219 &self,
220 cs: CS,
221 other: &F,
222 ) -> Result<Self, SynthesisError> {
223 let mut result = self.clone();
224 result.mul_by_constant_in_place(cs, other)?;
225 Ok(result)
226 }
227
228 #[inline]
229 fn mul_by_constant_in_place<CS: ConstraintSystem<F>>(
230 &mut self,
231 mut _cs: CS,
232 other: &F,
233 ) -> Result<&mut Self, SynthesisError> {
234 self.value.as_mut().map(|val| *val *= other);
235 self.variable *= *other;
236 Ok(self)
237 }
238
239 #[inline]
240 fn inverse<CS: ConstraintSystem<F>>(&self, mut cs: CS) -> Result<Self, SynthesisError> {
241 let inverse = Self::alloc(cs.ns(|| "inverse"), || {
242 let result = self.value.get()?;
243 let inv = result.inverse().expect("Inverse doesn't exist!");
244 Ok(inv)
245 })?;
246
247 let one = CS::one();
248 cs.enforce(
249 || "inv_constraint",
250 |lc| &self.variable + lc,
251 |lc| &inverse.variable + lc,
252 |lc| lc + one,
253 );
254 Ok(inverse)
255 }
256
257 fn frobenius_map<CS: ConstraintSystem<F>>(
258 &self,
259 _: CS,
260 _: usize,
261 ) -> Result<Self, SynthesisError> {
262 Ok(self.clone())
263 }
264
265 fn frobenius_map_in_place<CS: ConstraintSystem<F>>(
266 &mut self,
267 _: CS,
268 _: usize,
269 ) -> Result<&mut Self, SynthesisError> {
270 Ok(self)
271 }
272
273 fn mul_equals<CS: ConstraintSystem<F>>(
274 &self,
275 mut cs: CS,
276 other: &Self,
277 result: &Self,
278 ) -> Result<(), SynthesisError> {
279 cs.enforce(
280 || "mul_constraint",
281 |lc| &self.variable + lc,
282 |lc| &other.variable + lc,
283 |lc| &result.variable + lc,
284 );
285 Ok(())
286 }
287
288 fn square_equals<CS: ConstraintSystem<F>>(
289 &self,
290 mut cs: CS,
291 result: &Self,
292 ) -> Result<(), SynthesisError> {
293 cs.enforce(
294 || "sqr_constraint",
295 |lc| &self.variable + lc,
296 |lc| &self.variable + lc,
297 |lc| &result.variable + lc,
298 );
299 Ok(())
300 }
301
302 fn cost_of_mul() -> usize {
303 1
304 }
305
306 fn cost_of_mul_equals() -> usize {
307 1
308 }
309
310 fn cost_of_inv() -> usize {
311 1
312 }
313}
314
315impl<F: PrimeField> PartialEq for FpGadget<F> {
316 fn eq(&self, other: &Self) -> bool {
317 self.value.is_some() && other.value.is_some() && self.value == other.value
318 }
319}
320
321impl<F: PrimeField> Eq for FpGadget<F> {}
322
323impl<F: PrimeField> EqGadget<F> for FpGadget<F> {}
324
325impl<F: PrimeField> ConditionalEqGadget<F> for FpGadget<F> {
326 #[inline]
327 fn conditional_enforce_equal<CS: ConstraintSystem<F>>(
328 &self,
329 mut cs: CS,
330 other: &Self,
331 condition: &Boolean,
332 ) -> Result<(), SynthesisError> {
333 let difference = self.sub(cs.ns(|| "difference"), other)?;
334 let one = CS::one();
335 let one_const = F::one();
336 cs.enforce(
337 || "conditional_equals",
338 |lc| &difference.variable + lc,
339 |lc| lc + &condition.lc(one, one_const),
340 |lc| lc,
341 );
342 Ok(())
343 }
344
345 fn cost() -> usize {
346 1
347 }
348}
349
350impl<F: PrimeField> NEqGadget<F> for FpGadget<F> {
351 #[inline]
352 fn enforce_not_equal<CS: ConstraintSystem<F>>(
353 &self,
354 mut cs: CS,
355 other: &Self,
356 ) -> Result<(), SynthesisError> {
357 let a_minus_b = self.sub(cs.ns(|| "A - B"), other)?;
358 a_minus_b.inverse(cs.ns(|| "Enforce inverse exists"))?;
359 Ok(())
360 }
361
362 fn cost() -> usize {
363 1
364 }
365}
366
367impl<F: PrimeField> ToBitsGadget<F> for FpGadget<F> {
368 /// Outputs the unique bit-wise decomposition of `self` in *big-endian*
369 /// form.
370 fn to_bits<CS: ConstraintSystem<F>>(&self, mut cs: CS) -> Result<Vec<Boolean>, SynthesisError> {
371 let bits = self.to_non_unique_bits(&mut cs)?;
372 Boolean::enforce_in_field::<_, _, F>(&mut cs, &bits)?;
373 Ok(bits)
374 }
375
376 fn to_non_unique_bits<CS: ConstraintSystem<F>>(
377 &self,
378 mut cs: CS,
379 ) -> Result<Vec<Boolean>, SynthesisError> {
380 let num_bits = F::Params::MODULUS_BITS;
381 use algebra::BitIterator;
382 let bit_values = match self.value {
383 Some(value) => {
384 let mut field_char = BitIterator::new(F::characteristic());
385 let mut tmp = Vec::with_capacity(num_bits as usize);
386 let mut found_one = false;
387 for b in BitIterator::new(value.into_repr()) {
388 // Skip leading bits
389 found_one |= field_char.next().unwrap();
390 if !found_one {
391 continue;
392 }
393
394 tmp.push(Some(b));
395 }
396
397 assert_eq!(tmp.len(), num_bits as usize);
398
399 tmp
400 }
401 None => vec![None; num_bits as usize],
402 };
403
404 let mut bits = vec![];
405 for (i, b) in bit_values.into_iter().enumerate() {
406 bits.push(AllocatedBit::alloc(cs.ns(|| format!("bit {}", i)), || {
407 b.get()
408 })?);
409 }
410
411 let mut lc = LinearCombination::zero();
412 let mut coeff = F::one();
413
414 for bit in bits.iter().rev() {
415 lc += (coeff, bit.get_variable());
416
417 coeff.double_in_place();
418 }
419
420 lc = &self.variable - lc;
421
422 cs.enforce(|| "unpacking_constraint", |lc| lc, |lc| lc, |_| lc);
423
424 Ok(bits.into_iter().map(Boolean::from).collect())
425 }
426}
427
428impl<F: PrimeField> ToBytesGadget<F> for FpGadget<F> {
429 /// Outputs the unique byte decomposition of `self` in *little-endian*
430 /// form.
431 fn to_bytes<CS: ConstraintSystem<F>>(&self, mut cs: CS) -> Result<Vec<UInt8>, SynthesisError> {
432 let bytes = self.to_non_unique_bytes(&mut cs)?;
433 Boolean::enforce_in_field::<_, _, F>(
434 &mut cs,
435 &bytes.iter()
436 .flat_map(|byte_gadget| byte_gadget.into_bits_le())
437 // This reverse maps the bits into big-endian form, as required by `enforce_in_field`.
438 .rev()
439 .collect::<Vec<_>>(),
440 )?;
441
442 Ok(bytes)
443 }
444
445 fn to_non_unique_bytes<CS: ConstraintSystem<F>>(
446 &self,
447 mut cs: CS,
448 ) -> Result<Vec<UInt8>, SynthesisError> {
449 let byte_values = match self.value {
450 Some(value) => to_bytes![&value.into_repr()]?
451 .into_iter()
452 .map(Some)
453 .collect::<Vec<_>>(),
454 None => {
455 let default = F::default();
456 let default_len = to_bytes![&default].unwrap().len();
457 vec![None; default_len]
458 }
459 };
460
461 let bytes = UInt8::alloc_vec(cs.ns(|| "Alloc bytes"), &byte_values)?;
462
463 let mut lc = LinearCombination::zero();
464 let mut coeff = F::one();
465
466 for bit in bytes
467 .iter()
468 .flat_map(|byte_gadget| byte_gadget.bits.clone())
469 {
470 match bit {
471 Boolean::Is(bit) => {
472 lc += (coeff, bit.get_variable());
473 coeff.double_in_place();
474 }
475 Boolean::Constant(_) | Boolean::Not(_) => unreachable!(),
476 }
477 }
478
479 lc = &self.variable - lc;
480
481 cs.enforce(|| "unpacking_constraint", |lc| lc, |lc| lc, |_| lc);
482
483 Ok(bytes)
484 }
485}
486
487impl<F: PrimeField> CondSelectGadget<F> for FpGadget<F> {
488 #[inline]
489 fn conditionally_select<CS: ConstraintSystem<F>>(
490 mut cs: CS,
491 cond: &Boolean,
492 true_value: &Self,
493 false_value: &Self,
494 ) -> Result<Self, SynthesisError> {
495 if let Boolean::Constant(cond) = *cond {
496 if cond {
497 Ok(true_value.clone())
498 } else {
499 Ok(false_value.clone())
500 }
501 } else {
502 let result = Self::alloc(cs.ns(|| ""), || {
503 cond.get_value()
504 .and_then(|cond| if cond { true_value } else { false_value }.get_value())
505 .get()
506 })?;
507 // a = self; b = other; c = cond;
508 //
509 // r = c * a + (1 - c) * b
510 // r = b + c * (a - b)
511 // c * (a - b) = r - b
512 let one = CS::one();
513 cs.enforce(
514 || "conditionally_select",
515 |_| cond.lc(one, F::one()),
516 |lc| (&true_value.variable - &false_value.variable) + lc,
517 |lc| (&result.variable - &false_value.variable) + lc,
518 );
519
520 Ok(result)
521 }
522 }
523
524 fn cost() -> usize {
525 1
526 }
527}
528/// Uses two bits to perform a lookup into a table
529/// `b` is little-endian: `b[0]` is LSB.
530impl<F: PrimeField> TwoBitLookupGadget<F> for FpGadget<F> {
531 type TableConstant = F;
532 fn two_bit_lookup<CS: ConstraintSystem<F>>(
533 mut cs: CS,
534 b: &[Boolean],
535 c: &[Self::TableConstant],
536 ) -> Result<Self, SynthesisError> {
537 debug_assert!(b.len() == 2);
538 debug_assert!(c.len() == 4);
539
540 let result = Self::alloc(cs.ns(|| "Allocate lookup result"), || {
541 match (b[0].get_value().get()?, b[1].get_value().get()?) {
542 (false, false) => Ok(c[0]),
543 (false, true) => Ok(c[2]),
544 (true, false) => Ok(c[1]),
545 (true, true) => Ok(c[3]),
546 }
547 })?;
548 let one = CS::one();
549 cs.enforce(
550 || "Enforce lookup",
551 |lc| lc + b[1].lc(one, c[3] - &c[2] - &c[1] + &c[0]) + (c[1] - &c[0], one),
552 |lc| lc + b[0].lc(one, F::one()),
553 |lc| result.get_variable() + lc + (-c[0], one) + b[1].lc(one, c[0] - &c[2]),
554 );
555
556 Ok(result)
557 }
558
559 fn cost() -> usize {
560 1
561 }
562}
563
564impl<F: PrimeField> ThreeBitCondNegLookupGadget<F> for FpGadget<F> {
565 type TableConstant = F;
566
567 fn three_bit_cond_neg_lookup<CS: ConstraintSystem<F>>(
568 mut cs: CS,
569 b: &[Boolean],
570 b0b1: &Boolean,
571 c: &[Self::TableConstant],
572 ) -> Result<Self, SynthesisError> {
573 debug_assert!(b.len() == 3);
574 debug_assert!(c.len() == 4);
575
576 let result = Self::alloc(cs.ns(|| "Allocate lookup result"), || {
577 let y = match (b[0].get_value().get()?, b[1].get_value().get()?) {
578 (false, false) => c[0],
579 (false, true) => c[2],
580 (true, false) => c[1],
581 (true, true) => c[3],
582 };
583 if b[2].get_value().get()? {
584 Ok(-y)
585 } else {
586 Ok(y)
587 }
588 })?;
589
590 let one = CS::one();
591 let y_lc = b0b1.lc(one, c[3] - &c[2] - &c[1] + &c[0])
592 + b[0].lc(one, c[1] - &c[0])
593 + b[1].lc(one, c[2] - &c[0])
594 + (c[0], one);
595 cs.enforce(
596 || "Enforce lookup",
597 |_| y_lc.clone() + y_lc.clone(),
598 |lc| lc + b[2].lc(one, F::one()),
599 |_| -result.get_variable() + y_lc.clone(),
600 );
601
602 Ok(result)
603 }
604
605 fn cost() -> usize {
606 2
607 }
608}
609
610impl<F: PrimeField> Clone for FpGadget<F> {
611 fn clone(&self) -> Self {
612 Self {
613 value: self.value.clone(),
614 variable: self.variable.clone(),
615 }
616 }
617}
618
619impl<F: PrimeField> AllocGadget<F, F> for FpGadget<F> {
620 #[inline]
621 fn alloc_constant<T, CS: ConstraintSystem<F>>(_cs: CS, t: T) -> Result<Self, SynthesisError>
622 where
623 T: Borrow<F>,
624 {
625 let value = t.borrow().clone();
626 Ok(Self {
627 value: Some(value),
628 variable: LinearCombination::from((value, CS::one())).into(),
629 })
630 }
631
632 #[inline]
633 fn alloc<FN, T, CS: ConstraintSystem<F>>(
634 mut cs: CS,
635 value_gen: FN,
636 ) -> Result<Self, SynthesisError>
637 where
638 FN: FnOnce() -> Result<T, SynthesisError>,
639 T: Borrow<F>,
640 {
641 let mut value = None;
642 let variable = cs.alloc(
643 || "alloc",
644 || {
645 let tmp = *value_gen()?.borrow();
646 value = Some(tmp);
647 Ok(tmp)
648 },
649 )?;
650 Ok(FpGadget {
651 value,
652 variable: Var(variable),
653 })
654 }
655
656 #[inline]
657 fn alloc_input<FN, T, CS: ConstraintSystem<F>>(
658 mut cs: CS,
659 value_gen: FN,
660 ) -> Result<Self, SynthesisError>
661 where
662 FN: FnOnce() -> Result<T, SynthesisError>,
663 T: Borrow<F>,
664 {
665 let mut value = None;
666 let variable = cs.alloc_input(
667 || "alloc",
668 || {
669 let tmp = *value_gen()?.borrow();
670 value = Some(tmp);
671 Ok(tmp)
672 },
673 )?;
674 Ok(FpGadget {
675 value,
676 variable: Var(variable),
677 })
678 }
679}