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