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