ark-r1cs-std/r1cs-std/src/fields/mod.rs
r1cs-std/src/fields/mod.rsRaw
1use algebra::{fields::BitIterator, Field};
2use core::fmt::Debug;
3use r1cs_core::{ConstraintSystem, SynthesisError};
4
5use crate::{prelude::*, Assignment};
6
7pub mod fp;
8pub mod fp12;
9pub mod fp2;
10pub mod fp3;
11pub mod fp4;
12pub mod fp6_2over3;
13pub mod fp6_3over2;
14
15pub trait FieldGadget<F: Field, ConstraintF: Field>:
16 Sized
17 + Clone
18 + EqGadget<ConstraintF>
19 + NEqGadget<ConstraintF>
20 + ConditionalEqGadget<ConstraintF>
21 + ToBitsGadget<ConstraintF>
22 + AllocGadget<F, ConstraintF>
23 + ToBytesGadget<ConstraintF>
24 + CondSelectGadget<ConstraintF>
25 + TwoBitLookupGadget<ConstraintF, TableConstant = F>
26 + ThreeBitCondNegLookupGadget<ConstraintF, TableConstant = F>
27 + Debug
28{
29 type Variable: Clone + Debug;
30
31 fn get_value(&self) -> Option<F>;
32
33 fn get_variable(&self) -> Self::Variable;
34
35 fn zero<CS: ConstraintSystem<ConstraintF>>(_: CS) -> Result<Self, SynthesisError>;
36
37 fn one<CS: ConstraintSystem<ConstraintF>>(_: CS) -> Result<Self, SynthesisError>;
38
39 fn conditionally_add_constant<CS: ConstraintSystem<ConstraintF>>(
40 &self,
41 _: CS,
42 _: &Boolean,
43 _: F,
44 ) -> Result<Self, SynthesisError>;
45
46 fn add<CS: ConstraintSystem<ConstraintF>>(
47 &self,
48 _: CS,
49 _: &Self,
50 ) -> Result<Self, SynthesisError>;
51
52 fn add_in_place<CS: ConstraintSystem<ConstraintF>>(
53 &mut self,
54 cs: CS,
55 other: &Self,
56 ) -> Result<&mut Self, SynthesisError> {
57 *self = self.add(cs, other)?;
58 Ok(self)
59 }
60
61 fn double<CS: ConstraintSystem<ConstraintF>>(&self, cs: CS) -> Result<Self, SynthesisError> {
62 self.add(cs, &self)
63 }
64
65 fn double_in_place<CS: ConstraintSystem<ConstraintF>>(
66 &mut self,
67 cs: CS,
68 ) -> Result<&mut Self, SynthesisError> {
69 *self = self.double(cs)?;
70 Ok(self)
71 }
72
73 fn sub<CS: ConstraintSystem<ConstraintF>>(
74 &self,
75 _: CS,
76 _: &Self,
77 ) -> Result<Self, SynthesisError>;
78
79 fn sub_in_place<CS: ConstraintSystem<ConstraintF>>(
80 &mut self,
81 cs: CS,
82 other: &Self,
83 ) -> Result<&mut Self, SynthesisError> {
84 *self = self.sub(cs, other)?;
85 Ok(self)
86 }
87
88 fn negate<CS: ConstraintSystem<ConstraintF>>(&self, _: CS) -> Result<Self, SynthesisError>;
89
90 #[inline]
91 fn negate_in_place<CS: ConstraintSystem<ConstraintF>>(
92 &mut self,
93 cs: CS,
94 ) -> Result<&mut Self, SynthesisError> {
95 *self = self.negate(cs)?;
96 Ok(self)
97 }
98
99 fn mul<CS: ConstraintSystem<ConstraintF>>(
100 &self,
101 _: CS,
102 _: &Self,
103 ) -> Result<Self, SynthesisError>;
104
105 fn mul_in_place<CS: ConstraintSystem<ConstraintF>>(
106 &mut self,
107 cs: CS,
108 other: &Self,
109 ) -> Result<&mut Self, SynthesisError> {
110 *self = self.mul(cs, other)?;
111 Ok(self)
112 }
113
114 fn square<CS: ConstraintSystem<ConstraintF>>(&self, cs: CS) -> Result<Self, SynthesisError> {
115 self.mul(cs, &self)
116 }
117
118 fn square_in_place<CS: ConstraintSystem<ConstraintF>>(
119 &mut self,
120 cs: CS,
121 ) -> Result<&mut Self, SynthesisError> {
122 *self = self.square(cs)?;
123 Ok(self)
124 }
125
126 fn mul_equals<CS: ConstraintSystem<ConstraintF>>(
127 &self,
128 mut cs: CS,
129 other: &Self,
130 result: &Self,
131 ) -> Result<(), SynthesisError> {
132 let actual_result = self.mul(cs.ns(|| "calc_actual_result"), other)?;
133 result.enforce_equal(&mut cs.ns(|| "test_equals"), &actual_result)
134 }
135
136 fn square_equals<CS: ConstraintSystem<ConstraintF>>(
137 &self,
138 mut cs: CS,
139 result: &Self,
140 ) -> Result<(), SynthesisError> {
141 let actual_result = self.square(cs.ns(|| "calc_actual_result"))?;
142 result.enforce_equal(&mut cs.ns(|| "test_equals"), &actual_result)
143 }
144
145 fn add_constant<CS: ConstraintSystem<ConstraintF>>(
146 &self,
147 _: CS,
148 _: &F,
149 ) -> Result<Self, SynthesisError>;
150
151 fn add_constant_in_place<CS: ConstraintSystem<ConstraintF>>(
152 &mut self,
153 cs: CS,
154 other: &F,
155 ) -> Result<&mut Self, SynthesisError> {
156 *self = self.add_constant(cs, other)?;
157 Ok(self)
158 }
159
160 fn sub_constant<CS: ConstraintSystem<ConstraintF>>(
161 &self,
162 cs: CS,
163 fe: &F,
164 ) -> Result<Self, SynthesisError> {
165 self.add_constant(cs, &(-(*fe)))
166 }
167
168 fn sub_constant_in_place<CS: ConstraintSystem<ConstraintF>>(
169 &mut self,
170 cs: CS,
171 other: &F,
172 ) -> Result<&mut Self, SynthesisError> {
173 self.add_constant_in_place(cs, &(-(*other)))
174 }
175
176 fn mul_by_constant<CS: ConstraintSystem<ConstraintF>>(
177 &self,
178 _: CS,
179 _: &F,
180 ) -> Result<Self, SynthesisError>;
181
182 fn mul_by_constant_in_place<CS: ConstraintSystem<ConstraintF>>(
183 &mut self,
184 cs: CS,
185 other: &F,
186 ) -> Result<&mut Self, SynthesisError> {
187 *self = self.mul_by_constant(cs, other)?;
188 Ok(self)
189 }
190
191 fn inverse<CS: ConstraintSystem<ConstraintF>>(
192 &self,
193 mut cs: CS,
194 ) -> Result<Self, SynthesisError> {
195 let one = Self::one(&mut cs.ns(|| "one"))?;
196 let inverse = Self::alloc(&mut cs.ns(|| "alloc inverse"), || {
197 self.get_value().and_then(|val| val.inverse()).get()
198 })?;
199 self.mul_equals(cs.ns(|| "check inv"), &inverse, &one)?;
200 Ok(inverse)
201 }
202
203 fn frobenius_map<CS: ConstraintSystem<ConstraintF>>(
204 &self,
205 _: CS,
206 power: usize,
207 ) -> Result<Self, SynthesisError>;
208
209 fn frobenius_map_in_place<CS: ConstraintSystem<ConstraintF>>(
210 &mut self,
211 cs: CS,
212 power: usize,
213 ) -> Result<&mut Self, SynthesisError> {
214 *self = self.frobenius_map(cs, power)?;
215 Ok(self)
216 }
217
218 /// Accepts as input a list of bits which, when interpreted in big-endian
219 /// form, are a scalar.
220 #[inline]
221 fn pow<CS: ConstraintSystem<ConstraintF>>(
222 &self,
223 mut cs: CS,
224 bits: &[Boolean],
225 ) -> Result<Self, SynthesisError> {
226 let mut res = Self::one(cs.ns(|| "Alloc result"))?;
227 for (i, bit) in bits.iter().enumerate() {
228 res = res.square(cs.ns(|| format!("Double {}", i)))?;
229 let tmp = res.mul(cs.ns(|| format!("Add {}-th base power", i)), self)?;
230 res = Self::conditionally_select(
231 cs.ns(|| format!("Conditional Select {}", i)),
232 bit,
233 &tmp,
234 &res,
235 )?;
236 }
237 Ok(res)
238 }
239
240 fn pow_by_constant<S: AsRef<[u64]>, CS: ConstraintSystem<ConstraintF>>(
241 &self,
242 mut cs: CS,
243 exp: S,
244 ) -> Result<Self, SynthesisError> {
245 let mut res = self.clone();
246 let mut found_one = false;
247
248 for (i, bit) in BitIterator::new(exp).enumerate() {
249 if found_one {
250 res = res.square(cs.ns(|| format!("square for bit {:?}", i)))?;
251 }
252
253 if bit {
254 if found_one {
255 res = res.mul(cs.ns(|| format!("mul for bit {:?}", i)), self)?;
256 }
257 found_one = true;
258 }
259 }
260
261 Ok(res)
262 }
263
264 fn cost_of_mul() -> usize;
265
266 fn cost_of_mul_equals() -> usize {
267 Self::cost_of_mul() + <Self as EqGadget<ConstraintF>>::cost()
268 }
269
270 fn cost_of_inv() -> usize {
271 Self::cost_of_mul_equals()
272 }
273}
274
275#[cfg(test)]
276pub(crate) mod tests {
277 use rand::{self, SeedableRng};
278 use rand_xorshift::XorShiftRng;
279
280 use crate::{prelude::*, test_constraint_system::TestConstraintSystem, Vec};
281 use algebra::{test_rng, BitIterator, Field, UniformRand};
282 use r1cs_core::ConstraintSystem;
283
284 #[allow(dead_code)]
285 pub(crate) fn field_test<FE: Field, ConstraintF: Field, F: FieldGadget<FE, ConstraintF>>() {
286 let mut cs = TestConstraintSystem::<ConstraintF>::new();
287
288 let mut rng = test_rng();
289 let a_native = FE::rand(&mut rng);
290 let b_native = FE::rand(&mut rng);
291 let a = F::alloc(&mut cs.ns(|| "generate_a"), || Ok(a_native)).unwrap();
292 let b = F::alloc(&mut cs.ns(|| "generate_b"), || Ok(b_native)).unwrap();
293
294 let zero = F::zero(cs.ns(|| "zero")).unwrap();
295 let zero_native = zero.get_value().unwrap();
296 zero.enforce_equal(&mut cs.ns(|| "zero_equals?"), &zero)
297 .unwrap();
298 assert_eq!(zero, zero);
299
300 let one = F::one(cs.ns(|| "one")).unwrap();
301 let one_native = one.get_value().unwrap();
302 assert_eq!(one, one);
303 one.enforce_equal(&mut cs.ns(|| "one_equals?"), &one)
304 .unwrap();
305 assert_ne!(one, zero);
306
307 let one_dup = zero.add(cs.ns(|| "zero_plus_one"), &one).unwrap();
308 one_dup
309 .enforce_equal(&mut cs.ns(|| "one_plus_zero_equals"), &one)
310 .unwrap();
311 assert_eq!(one_dup, one);
312
313 let two = one.add(cs.ns(|| "one_plus_one"), &one).unwrap();
314 two.enforce_equal(&mut cs.ns(|| "two_equals?"), &two)
315 .unwrap();
316 assert_eq!(two, two);
317 assert_ne!(zero, two);
318 assert_ne!(one, two);
319
320 // a == a
321 assert_eq!(a, a);
322
323 // a + 0 = a
324 let a_plus_zero = a.add(cs.ns(|| "a_plus_zero"), &zero).unwrap();
325 assert_eq!(a_plus_zero, a);
326 assert_eq!(a_plus_zero.get_value().unwrap(), a_native);
327 a_plus_zero
328 .enforce_equal(&mut cs.ns(|| "a_plus_zero_equals?"), &a)
329 .unwrap();
330
331 // a - 0 = a
332 let a_minus_zero = a.sub(cs.ns(|| "a_minus_zero"), &zero).unwrap();
333 assert_eq!(a_minus_zero, a);
334 assert_eq!(a_minus_zero.get_value().unwrap(), a_native);
335 a_minus_zero
336 .enforce_equal(&mut cs.ns(|| "a_minus_zero_equals?"), &a)
337 .unwrap();
338
339 // a - a = 0
340 let a_minus_a = a.sub(cs.ns(|| "a_minus_a"), &a).unwrap();
341 assert_eq!(a_minus_a, zero);
342 assert_eq!(a_minus_a.get_value().unwrap(), zero_native);
343 a_minus_a
344 .enforce_equal(&mut cs.ns(|| "a_minus_a_equals?"), &zero)
345 .unwrap();
346
347 // a + b = b + a
348 let a_b = a.add(cs.ns(|| "a_plus_b"), &b).unwrap();
349 let b_a = b.add(cs.ns(|| "b_plus_a"), &a).unwrap();
350 assert_eq!(a_b, b_a);
351 assert_eq!(a_b.get_value().unwrap(), a_native + &b_native);
352 a_b.enforce_equal(&mut cs.ns(|| "a+b == b+a"), &b_a)
353 .unwrap();
354
355 // (a + b) + a = a + (b + a)
356 let ab_a = a_b.add(cs.ns(|| "a_b_plus_a"), &a).unwrap();
357 let a_ba = a.add(cs.ns(|| "a_plus_b_a"), &b_a).unwrap();
358 assert_eq!(ab_a, a_ba);
359 assert_eq!(ab_a.get_value().unwrap(), a_native + &b_native + &a_native);
360 ab_a.enforce_equal(&mut cs.ns(|| "a+b + a == a+ b+a"), &a_ba)
361 .unwrap();
362
363 let b_times_a_plus_b = a_b.mul(cs.ns(|| "b * (a + b)"), &b).unwrap();
364 let b_times_b_plus_a = b_a.mul(cs.ns(|| "b * (b + a)"), &b).unwrap();
365 assert_eq!(b_times_b_plus_a, b_times_a_plus_b);
366 assert_eq!(
367 b_times_a_plus_b.get_value().unwrap(),
368 b_native * &(b_native + &a_native)
369 );
370 assert_eq!(
371 b_times_a_plus_b.get_value().unwrap(),
372 (b_native + &a_native) * &b_native
373 );
374 assert_eq!(
375 b_times_a_plus_b.get_value().unwrap(),
376 (a_native + &b_native) * &b_native
377 );
378 b_times_b_plus_a
379 .enforce_equal(&mut cs.ns(|| "b*(a+b) == b * (b+a)"), &b_times_a_plus_b)
380 .unwrap();
381
382 // a * 0 = 0
383 assert_eq!(a.mul(cs.ns(|| "a_times_zero"), &zero).unwrap(), zero);
384
385 // a * 1 = a
386 assert_eq!(a.mul(cs.ns(|| "a_times_one"), &one).unwrap(), a);
387 assert_eq!(
388 a.mul(cs.ns(|| "a_times_one2"), &one)
389 .unwrap()
390 .get_value()
391 .unwrap(),
392 a_native * &one_native
393 );
394
395 // a * b = b * a
396 let ab = a.mul(cs.ns(|| "a_times_b"), &b).unwrap();
397 let ba = b.mul(cs.ns(|| "b_times_a"), &a).unwrap();
398 assert_eq!(ab, ba);
399 assert_eq!(ab.get_value().unwrap(), a_native * &b_native);
400
401 // (a * b) * a = a * (b * a)
402 let ab_a = ab.mul(cs.ns(|| "ab_times_a"), &a).unwrap();
403 let a_ba = a.mul(cs.ns(|| "a_times_ba"), &ba).unwrap();
404 assert_eq!(ab_a, a_ba);
405 assert_eq!(ab_a.get_value().unwrap(), a_native * &b_native * &a_native);
406
407 let aa = a.mul(cs.ns(|| "a * a"), &a).unwrap();
408 let a_squared = a.square(cs.ns(|| "a^2")).unwrap();
409 a_squared
410 .enforce_equal(&mut cs.ns(|| "a^2 == a*a"), &aa)
411 .unwrap();
412 assert_eq!(aa, a_squared);
413 assert_eq!(aa.get_value().unwrap(), a_native.square());
414
415 let aa = a
416 .mul_by_constant(cs.ns(|| "a * a via mul_by_const"), &a.get_value().unwrap())
417 .unwrap();
418 a_squared
419 .enforce_equal(&mut cs.ns(|| "a^2 == a*a via mul_by_const"), &aa)
420 .unwrap();
421 assert_eq!(aa, a_squared);
422 assert_eq!(aa.get_value().unwrap(), a_native.square());
423
424 let a_b2 = a
425 .add_constant(cs.ns(|| "a + b via add_const"), &b.get_value().unwrap())
426 .unwrap();
427 a_b.enforce_equal(&mut cs.ns(|| "a + b == a + b via add_const"), &a_b2)
428 .unwrap();
429 assert_eq!(a_b, a_b2);
430
431 let a_inv = a.inverse(cs.ns(|| "a_inv")).unwrap();
432 a_inv
433 .mul_equals(cs.ns(|| "check_equals"), &a, &one)
434 .unwrap();
435 assert_eq!(
436 a_inv.get_value().unwrap(),
437 a.get_value().unwrap().inverse().unwrap()
438 );
439 assert_eq!(a_inv.get_value().unwrap(), a_native.inverse().unwrap());
440 // a * a * a = a^3
441 let bits = BitIterator::new([0x3])
442 .map(Boolean::constant)
443 .collect::<Vec<_>>();
444 assert_eq!(
445 a_native * &(a_native * &a_native),
446 a.pow(cs.ns(|| "test_pow"), &bits)
447 .unwrap()
448 .get_value()
449 .unwrap()
450 );
451
452 // a * a * a = a^3
453 assert_eq!(
454 a_native * &(a_native * &a_native),
455 a.pow_by_constant(cs.ns(|| "test_constant_pow"), &[3])
456 .unwrap()
457 .get_value()
458 .unwrap()
459 );
460
461 // a * a * a = a^3
462 let mut constants = [FE::zero(); 4];
463 for c in &mut constants {
464 *c = UniformRand::rand(&mut test_rng());
465 println!("Current c[i]: {:?}", c);
466 }
467 let bits = [Boolean::constant(false), Boolean::constant(true)];
468 let lookup_result =
469 F::two_bit_lookup(cs.ns(|| "Lookup"), &bits, constants.as_ref()).unwrap();
470 assert_eq!(lookup_result.get_value().unwrap(), constants[2]);
471
472 let negone: FE = UniformRand::rand(&mut test_rng());
473
474 let n = F::alloc(&mut cs.ns(|| "alloc new var"), || Ok(negone)).unwrap();
475 let _ = n.to_bytes(&mut cs.ns(|| "ToBytes")).unwrap();
476 let _ = n
477 .to_non_unique_bytes(&mut cs.ns(|| "ToBytes Strict"))
478 .unwrap();
479
480 let ab_false = a
481 .conditionally_add_constant(
482 cs.ns(|| "Add bool with coeff false"),
483 &Boolean::constant(false),
484 b_native,
485 )
486 .unwrap();
487 assert_eq!(ab_false.get_value().unwrap(), a_native);
488 let ab_true = a
489 .conditionally_add_constant(
490 cs.ns(|| "Add bool with coeff true"),
491 &Boolean::constant(true),
492 b_native,
493 )
494 .unwrap();
495 assert_eq!(ab_true.get_value().unwrap(), a_native + &b_native);
496
497 if !cs.is_satisfied() {
498 println!("{:?}", cs.which_is_unsatisfied().unwrap());
499 }
500 assert!(cs.is_satisfied());
501 }
502
503 #[allow(dead_code)]
504 pub(crate) fn frobenius_tests<
505 FE: Field,
506 ConstraintF: Field,
507 F: FieldGadget<FE, ConstraintF>,
508 >(
509 maxpower: usize,
510 ) {
511 let mut cs = TestConstraintSystem::<ConstraintF>::new();
512 let mut rng = XorShiftRng::seed_from_u64(1231275789u64);
513 for i in 0..=maxpower {
514 let mut a = FE::rand(&mut rng);
515 let mut a_gadget = F::alloc(cs.ns(|| format!("a_gadget_{:?}", i)), || Ok(a)).unwrap();
516 a_gadget = a_gadget
517 .frobenius_map(cs.ns(|| format!("frob_map_{}", i)), i)
518 .unwrap();
519 a.frobenius_map(i);
520
521 assert_eq!(a_gadget.get_value().unwrap(), a);
522 }
523
524 assert!(cs.is_satisfied());
525 }
526}