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