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