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