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_inv() -> usize {
274 1
275 }
276}
277
278impl<F: PrimeField> PartialEq for FpGadget<F> {
279 fn eq(&self, other: &Self) -> bool {
280 self.value.is_some() && other.value.is_some() && self.value == other.value
281 }
282}
283
284impl<F: PrimeField> Eq for FpGadget<F> {}
285
286impl<F: PrimeField> EqGadget<F> for FpGadget<F> {}
287
288impl<F: PrimeField> ConditionalEqGadget<F> for FpGadget<F> {
289 #[inline]
290 fn conditional_enforce_equal<CS: ConstraintSystem<F>>(
291 &self,
292 mut cs: CS,
293 other: &Self,
294 condition: &Boolean,
295 ) -> Result<(), SynthesisError> {
296 let difference = self.sub(cs.ns(|| "difference"), other)?;
297 let one = CS::one();
298 let one_const = F::one();
299 cs.enforce(
300 || "conditional_equals",
301 |lc| &difference.variable + lc,
302 |lc| lc + &condition.lc(one, one_const),
303 |lc| lc,
304 );
305 Ok(())
306 }
307
308 fn cost() -> usize {
309 1
310 }
311}
312
313impl<F: PrimeField> NEqGadget<F> for FpGadget<F> {
314 #[inline]
315 fn enforce_not_equal<CS: ConstraintSystem<F>>(
316 &self,
317 mut cs: CS,
318 other: &Self,
319 ) -> Result<(), SynthesisError> {
320 let a_minus_b = self.sub(cs.ns(|| "A - B"), other)?;
321 a_minus_b.inverse(cs.ns(|| "Enforce inverse exists"))?;
322 Ok(())
323 }
324
325 fn cost() -> usize {
326 1
327 }
328}
329
330impl<F: PrimeField> ToBitsGadget<F> for FpGadget<F> {
331 /// Outputs the unique bit-wise decomposition of `self` in *big-endian*
332 /// form.
333 fn to_bits<CS: ConstraintSystem<F>>(&self, mut cs: CS) -> Result<Vec<Boolean>, SynthesisError> {
334 let bits = self.to_non_unique_bits(&mut cs)?;
335 Boolean::enforce_in_field::<_, _, F>(&mut cs, &bits)?;
336 Ok(bits)
337 }
338
339 fn to_non_unique_bits<CS: ConstraintSystem<F>>(
340 &self,
341 mut cs: CS,
342 ) -> Result<Vec<Boolean>, SynthesisError> {
343 let num_bits = F::Params::MODULUS_BITS;
344 use algebra::BitIterator;
345 let bit_values = match self.value {
346 Some(value) => {
347 let mut field_char = BitIterator::new(F::characteristic());
348 let mut tmp = Vec::with_capacity(num_bits as usize);
349 let mut found_one = false;
350 for b in BitIterator::new(value.into_repr()) {
351 // Skip leading bits
352 found_one |= field_char.next().unwrap();
353 if !found_one {
354 continue;
355 }
356
357 tmp.push(Some(b));
358 }
359
360 assert_eq!(tmp.len(), num_bits as usize);
361
362 tmp
363 },
364 None => vec![None; num_bits as usize],
365 };
366
367 let mut bits = vec![];
368 for (i, b) in bit_values.into_iter().enumerate() {
369 bits.push(AllocatedBit::alloc(cs.ns(|| format!("bit {}", i)), || {
370 b.get()
371 })?);
372 }
373
374 let mut lc = LinearCombination::zero();
375 let mut coeff = F::one();
376
377 for bit in bits.iter().rev() {
378 lc += (coeff, bit.get_variable());
379
380 coeff.double_in_place();
381 }
382
383 lc = &self.variable - lc;
384
385 cs.enforce(|| "unpacking_constraint", |lc| lc, |lc| lc, |_| lc);
386
387 Ok(bits.into_iter().map(Boolean::from).collect())
388 }
389}
390
391impl<F: PrimeField> ToBytesGadget<F> for FpGadget<F> {
392 /// Outputs the unique byte decomposition of `self` in *little-endian*
393 /// form.
394 fn to_bytes<CS: ConstraintSystem<F>>(&self, mut cs: CS) -> Result<Vec<UInt8>, SynthesisError> {
395 let bytes = self.to_non_unique_bytes(&mut cs)?;
396 Boolean::enforce_in_field::<_, _, F>(
397 &mut cs,
398 &bytes.iter()
399 .flat_map(|byte_gadget| byte_gadget.into_bits_le())
400 // This reverse maps the bits into big-endian form, as required by `enforce_in_field`.
401 .rev()
402 .collect::<Vec<_>>(),
403 )?;
404
405 Ok(bytes)
406 }
407
408 fn to_non_unique_bytes<CS: ConstraintSystem<F>>(
409 &self,
410 mut cs: CS,
411 ) -> Result<Vec<UInt8>, SynthesisError> {
412 let byte_values = match self.value {
413 Some(value) => to_bytes![&value.into_repr()]?
414 .into_iter()
415 .map(Some)
416 .collect::<Vec<_>>(),
417 None => {
418 let default = F::default();
419 let default_len = to_bytes![&default].unwrap().len();
420 vec![None; default_len]
421 },
422 };
423
424 let bytes = UInt8::alloc_vec(cs.ns(|| "Alloc bytes"), &byte_values)?;
425
426 let mut lc = LinearCombination::zero();
427 let mut coeff = F::one();
428
429 for bit in bytes
430 .iter()
431 .flat_map(|byte_gadget| byte_gadget.bits.clone())
432 {
433 match bit {
434 Boolean::Is(bit) => {
435 lc += (coeff, bit.get_variable());
436 coeff.double_in_place();
437 },
438 Boolean::Constant(_) | Boolean::Not(_) => unreachable!(),
439 }
440 }
441
442 lc = &self.variable - lc;
443
444 cs.enforce(|| "unpacking_constraint", |lc| lc, |lc| lc, |_| lc);
445
446 Ok(bytes)
447 }
448}
449
450impl<F: PrimeField> CondSelectGadget<F> for FpGadget<F> {
451 #[inline]
452 fn conditionally_select<CS: ConstraintSystem<F>>(
453 mut cs: CS,
454 cond: &Boolean,
455 true_value: &Self,
456 false_value: &Self,
457 ) -> Result<Self, SynthesisError> {
458 if let Boolean::Constant(cond) = *cond {
459 if cond {
460 Ok(true_value.clone())
461 } else {
462 Ok(false_value.clone())
463 }
464 } else {
465 let result = Self::alloc(cs.ns(|| ""), || {
466 cond.get_value()
467 .and_then(|cond| if cond { true_value } else { false_value }.get_value())
468 .get()
469 })?;
470 // a = self; b = other; c = cond;
471 //
472 // r = c * a + (1 - c) * b
473 // r = b + c * (a - b)
474 // c * (a - b) = r - b
475 let one = CS::one();
476 cs.enforce(
477 || "conditionally_select",
478 |_| cond.lc(one, F::one()),
479 |lc| (&true_value.variable - &false_value.variable) + lc,
480 |lc| (&result.variable - &false_value.variable) + lc,
481 );
482
483 Ok(result)
484 }
485 }
486
487 fn cost() -> usize {
488 1
489 }
490}
491/// Uses two bits to perform a lookup into a table
492/// `b` is little-endian: `b[0]` is LSB.
493impl<F: PrimeField> TwoBitLookupGadget<F> for FpGadget<F> {
494 type TableConstant = F;
495 fn two_bit_lookup<CS: ConstraintSystem<F>>(
496 mut cs: CS,
497 b: &[Boolean],
498 c: &[Self::TableConstant],
499 ) -> Result<Self, SynthesisError> {
500 debug_assert!(b.len() == 2);
501 debug_assert!(c.len() == 4);
502
503 let result = Self::alloc(cs.ns(|| "Allocate lookup result"), || {
504 match (b[0].get_value().get()?, b[1].get_value().get()?) {
505 (false, false) => Ok(c[0]),
506 (false, true) => Ok(c[2]),
507 (true, false) => Ok(c[1]),
508 (true, true) => Ok(c[3]),
509 }
510 })?;
511 let one = CS::one();
512 cs.enforce(
513 || "Enforce lookup",
514 |lc| lc + b[1].lc(one, c[3] - &c[2] - &c[1] + &c[0]) + (c[1] - &c[0], one),
515 |lc| lc + b[0].lc(one, F::one()),
516 |lc| result.get_variable() + lc + (-c[0], one) + b[1].lc(one, c[0] - &c[2]),
517 );
518
519 Ok(result)
520 }
521
522 fn cost() -> usize {
523 1
524 }
525}
526
527impl<F: PrimeField> ThreeBitCondNegLookupGadget<F> for FpGadget<F> {
528 type TableConstant = F;
529
530 fn three_bit_cond_neg_lookup<CS: ConstraintSystem<F>>(
531 mut cs: CS,
532 b: &[Boolean],
533 b0b1: &Boolean,
534 c: &[Self::TableConstant],
535 ) -> Result<Self, SynthesisError> {
536 debug_assert!(b.len() == 3);
537 debug_assert!(c.len() == 4);
538
539 let result = Self::alloc(cs.ns(|| "Allocate lookup result"), || {
540 let y = match (b[0].get_value().get()?, b[1].get_value().get()?) {
541 (false, false) => c[0],
542 (false, true) => c[2],
543 (true, false) => c[1],
544 (true, true) => c[3],
545 };
546 if b[2].get_value().get()? {
547 Ok(-y)
548 } else {
549 Ok(y)
550 }
551 })?;
552
553 let one = CS::one();
554 let y_lc = b0b1.lc(one, c[3] - &c[2] - &c[1] + &c[0])
555 + b[0].lc(one, c[1] - &c[0])
556 + b[1].lc(one, c[2] - &c[0])
557 + (c[0], one);
558 cs.enforce(
559 || "Enforce lookup",
560 |_| y_lc.clone() + y_lc.clone(),
561 |lc| lc + b[2].lc(one, F::one()),
562 |_| -result.get_variable() + y_lc.clone(),
563 );
564
565 Ok(result)
566 }
567
568 fn cost() -> usize {
569 2
570 }
571}
572
573impl<F: PrimeField> Clone for FpGadget<F> {
574 fn clone(&self) -> Self {
575 Self {
576 value: self.value.clone(),
577 variable: self.variable.clone(),
578 }
579 }
580}
581
582impl<F: PrimeField> AllocGadget<F, F> for FpGadget<F> {
583 #[inline]
584 fn alloc<FN, T, CS: ConstraintSystem<F>>(
585 mut cs: CS,
586 value_gen: FN,
587 ) -> Result<Self, SynthesisError>
588 where
589 FN: FnOnce() -> Result<T, SynthesisError>,
590 T: Borrow<F>,
591 {
592 let mut value = None;
593 let variable = cs.alloc(
594 || "alloc",
595 || {
596 let tmp = *value_gen()?.borrow();
597 value = Some(tmp);
598 Ok(tmp)
599 },
600 )?;
601 Ok(FpGadget {
602 value,
603 variable: Var(variable),
604 })
605 }
606
607 #[inline]
608 fn alloc_input<FN, T, CS: ConstraintSystem<F>>(
609 mut cs: CS,
610 value_gen: FN,
611 ) -> Result<Self, SynthesisError>
612 where
613 FN: FnOnce() -> Result<T, SynthesisError>,
614 T: Borrow<F>,
615 {
616 let mut value = None;
617 let variable = cs.alloc_input(
618 || "alloc",
619 || {
620 let tmp = *value_gen()?.borrow();
621 value = Some(tmp);
622 Ok(tmp)
623 },
624 )?;
625 Ok(FpGadget {
626 value,
627 variable: Var(variable),
628 })
629 }
630}