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