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