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