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