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 crate::{prelude::*, test_constraint_system::TestConstraintSystem};
219 use algebra::{fields::Field, BitIterator};
220 use r1cs_core::ConstraintSystem;
221
222 fn field_test<FE: Field, ConstraintF: Field, F: FieldGadget<FE, ConstraintF>, CS: ConstraintSystem<ConstraintF>>(
223 mut cs: CS,
224 a: F,
225 b: F,
226 ) {
227 let a_native = a.get_value().unwrap();
228 let b_native = b.get_value().unwrap();
229
230 let zero = F::zero(cs.ns(|| "zero")).unwrap();
231 let zero_native = zero.get_value().unwrap();
232 zero.enforce_equal(&mut cs.ns(|| "zero_equals?"), &zero)
233 .unwrap();
234 assert_eq!(zero, zero);
235
236 let one = F::one(cs.ns(|| "one")).unwrap();
237 let one_native = one.get_value().unwrap();
238 assert_eq!(one, one);
239 one.enforce_equal(&mut cs.ns(|| "one_equals?"), &one)
240 .unwrap();
241 assert_ne!(one, zero);
242
243 let one_dup = zero.add(cs.ns(|| "zero_plus_one"), &one).unwrap();
244 one_dup
245 .enforce_equal(&mut cs.ns(|| "one_plus_zero_equals"), &one)
246 .unwrap();
247 assert_eq!(one_dup, one);
248
249 let two = one.add(cs.ns(|| "one_plus_one"), &one).unwrap();
250 two.enforce_equal(&mut cs.ns(|| "two_equals?"), &two)
251 .unwrap();
252 assert_eq!(two, two);
253 assert_ne!(zero, two);
254 assert_ne!(one, two);
255
256 // a == a
257 assert_eq!(a, a);
258
259 // a + 0 = a
260 let a_plus_zero = a.add(cs.ns(|| "a_plus_zero"), &zero).unwrap();
261 assert_eq!(a_plus_zero, a);
262 assert_eq!(a_plus_zero.get_value().unwrap(), a_native);
263 a_plus_zero
264 .enforce_equal(&mut cs.ns(|| "a_plus_zero_equals?"), &a)
265 .unwrap();
266
267 // a - 0 = a
268 let a_minus_zero = a.sub(cs.ns(|| "a_minus_zero"), &zero).unwrap();
269 assert_eq!(a_minus_zero, a);
270 assert_eq!(a_minus_zero.get_value().unwrap(), a_native);
271 a_minus_zero
272 .enforce_equal(&mut cs.ns(|| "a_minus_zero_equals?"), &a)
273 .unwrap();
274
275 // a - a = 0
276 let a_minus_a = a.sub(cs.ns(|| "a_minus_a"), &a).unwrap();
277 assert_eq!(a_minus_a, zero);
278 assert_eq!(a_minus_a.get_value().unwrap(), zero_native);
279 a_minus_a
280 .enforce_equal(&mut cs.ns(|| "a_minus_a_equals?"), &zero)
281 .unwrap();
282
283 // a + b = b + a
284 let a_b = a.add(cs.ns(|| "a_plus_b"), &b).unwrap();
285 let b_a = b.add(cs.ns(|| "b_plus_a"), &a).unwrap();
286 assert_eq!(a_b, b_a);
287 assert_eq!(a_b.get_value().unwrap(), a_native + &b_native);
288 a_b.enforce_equal(&mut cs.ns(|| "a+b == b+a"), &b_a)
289 .unwrap();
290
291 // (a + b) + a = a + (b + a)
292 let ab_a = a_b.add(cs.ns(|| "a_b_plus_a"), &a).unwrap();
293 let a_ba = a.add(cs.ns(|| "a_plus_b_a"), &b_a).unwrap();
294 assert_eq!(ab_a, a_ba);
295 assert_eq!(ab_a.get_value().unwrap(), a_native + &b_native + &a_native);
296 ab_a.enforce_equal(&mut cs.ns(|| "a+b + a == a+ b+a"), &a_ba)
297 .unwrap();
298
299 let b_times_a_plus_b = a_b.mul(cs.ns(|| "b * (a + b)"), &b).unwrap();
300 let b_times_b_plus_a = b_a.mul(cs.ns(|| "b * (b + a)"), &b).unwrap();
301 assert_eq!(b_times_b_plus_a, b_times_a_plus_b);
302 assert_eq!(
303 b_times_a_plus_b.get_value().unwrap(),
304 b_native * &(b_native + &a_native)
305 );
306 assert_eq!(
307 b_times_a_plus_b.get_value().unwrap(),
308 (b_native + &a_native) * &b_native
309 );
310 assert_eq!(
311 b_times_a_plus_b.get_value().unwrap(),
312 (a_native + &b_native) * &b_native
313 );
314 b_times_b_plus_a
315 .enforce_equal(&mut cs.ns(|| "b*(a+b) == b * (b+a)"), &b_times_a_plus_b)
316 .unwrap();
317
318 // a * 0 = 0
319 assert_eq!(a.mul(cs.ns(|| "a_times_zero"), &zero).unwrap(), zero);
320
321 // a * 1 = a
322 assert_eq!(a.mul(cs.ns(|| "a_times_one"), &one).unwrap(), a);
323 assert_eq!(
324 a.mul(cs.ns(|| "a_times_one2"), &one)
325 .unwrap()
326 .get_value()
327 .unwrap(),
328 a_native * &one_native
329 );
330
331 // a * b = b * a
332 let ab = a.mul(cs.ns(|| "a_times_b"), &b).unwrap();
333 let ba = b.mul(cs.ns(|| "b_times_a"), &a).unwrap();
334 assert_eq!(ab, ba);
335 assert_eq!(ab.get_value().unwrap(), a_native * &b_native);
336
337 // (a * b) * a = a * (b * a)
338 let ab_a = ab.mul(cs.ns(|| "ab_times_a"), &a).unwrap();
339 let a_ba = a.mul(cs.ns(|| "a_times_ba"), &ba).unwrap();
340 assert_eq!(ab_a, a_ba);
341 assert_eq!(ab_a.get_value().unwrap(), a_native * &b_native * &a_native);
342
343 let aa = a.mul(cs.ns(|| "a * a"), &a).unwrap();
344 let a_squared = a.square(cs.ns(|| "a^2")).unwrap();
345 a_squared
346 .enforce_equal(&mut cs.ns(|| "a^2 == a*a"), &aa)
347 .unwrap();
348 assert_eq!(aa, a_squared);
349 assert_eq!(aa.get_value().unwrap(), a_native.square());
350
351 let aa = a
352 .mul_by_constant(cs.ns(|| "a * a via mul_by_const"), &a.get_value().unwrap())
353 .unwrap();
354 a_squared
355 .enforce_equal(&mut cs.ns(|| "a^2 == a*a via mul_by_const"), &aa)
356 .unwrap();
357 assert_eq!(aa, a_squared);
358 assert_eq!(aa.get_value().unwrap(), a_native.square());
359
360 let a_b2 = a
361 .add_constant(cs.ns(|| "a + b via add_const"), &b.get_value().unwrap())
362 .unwrap();
363 a_b.enforce_equal(&mut cs.ns(|| "a + b == a + b via add_const"), &a_b2)
364 .unwrap();
365 assert_eq!(a_b, a_b2);
366
367 let a_inv = a.inverse(cs.ns(|| "a_inv")).unwrap();
368 a_inv
369 .mul_equals(cs.ns(|| "check_equals"), &a, &one)
370 .unwrap();
371 assert_eq!(
372 a_inv.get_value().unwrap(),
373 a.get_value().unwrap().inverse().unwrap()
374 );
375 assert_eq!(a_inv.get_value().unwrap(), a_native.inverse().unwrap());
376 // a * a * a = a^3
377 let bits = BitIterator::new([0x3])
378 .map(|bit| Boolean::constant(bit))
379 .collect::<Vec<_>>();
380 assert_eq!(
381 a_native * &(a_native * &a_native),
382 a.pow(cs.ns(|| "test_pow"), &bits)
383 .unwrap()
384 .get_value()
385 .unwrap()
386 );
387
388 // a * a * a = a^3
389 let mut constants = [FE::zero(); 4];
390 for c in &mut constants {
391 *c = rand::random();
392 println!("Current c[i]: {:?}", c);
393 }
394 let bits = [Boolean::constant(false), Boolean::constant(true)];
395 let lookup_result =
396 F::two_bit_lookup(cs.ns(|| "Lookup"), &bits, constants.as_ref()).unwrap();
397 assert_eq!(lookup_result.get_value().unwrap(), constants[2]);
398
399 let negone: FE = rand::random();
400
401 let n = F::alloc(&mut cs.ns(|| "alloc new var"), || Ok(negone)).unwrap();
402 let _ = n.to_bytes(&mut cs.ns(|| "ToBytes")).unwrap();
403 let _ = n.to_bytes_strict(&mut cs.ns(|| "ToBytes Strict")).unwrap();
404 }
405
406 fn random_frobenius_tests<
407 FE: Field,
408 ConstraintF: Field,
409 F: FieldGadget<FE, ConstraintF>,
410 CS: ConstraintSystem<ConstraintF>,
411 >(
412 mut cs: CS,
413 maxpower: usize,
414 ) {
415 let mut rng = XorShiftRng::from_seed([0x5dbe6259, 0x8d313d76, 0x3237db17, 0xe5bc0654]);
416 for i in 0..(maxpower + 1) {
417 let mut a = FE::rand(&mut rng);
418 let mut a_gadget = F::alloc(cs.ns(|| format!("a_gadget_{:?}", i)), || Ok(a)).unwrap();
419 a_gadget = a_gadget
420 .frobenius_map(cs.ns(|| format!("frob_map_{}", i)), i)
421 .unwrap();
422 a.frobenius_map(i);
423
424 assert_eq!(a_gadget.get_value().unwrap(), a);
425 }
426 }
427
428 #[test]
429 fn bls12_377_field_gadgets_test() {
430 use crate::fields::bls12_377::{Fq12Gadget, Fq2Gadget, Fq6Gadget, FqGadget};
431 use algebra::fields::bls12_377::{Fq, Fq12, Fq2, Fq6};
432
433 let mut cs = TestConstraintSystem::<Fq>::new();
434
435 let mut rng = XorShiftRng::from_seed([0x5dbe6259, 0x8d313d76, 0x3237db17, 0xe5bc0653]);
436
437 let a = FqGadget::alloc(&mut cs.ns(|| "generate_a"), || Ok(Fq::rand(&mut rng))).unwrap();
438 let b = FqGadget::alloc(&mut cs.ns(|| "generate_b"), || Ok(Fq::rand(&mut rng))).unwrap();
439 field_test(cs.ns(|| "test_fq"), a, b);
440 if !cs.is_satisfied() {
441 println!("{:?}", cs.which_is_unsatisfied().unwrap());
442 }
443
444 let c = Fq2Gadget::alloc(&mut cs.ns(|| "generate_c"), || Ok(Fq2::rand(&mut rng))).unwrap();
445 let d = Fq2Gadget::alloc(&mut cs.ns(|| "generate_d"), || Ok(Fq2::rand(&mut rng))).unwrap();
446 field_test(cs.ns(|| "test_fq2"), c, d);
447 random_frobenius_tests::<Fq2, _, Fq2Gadget, _>(cs.ns(|| "test_frob_fq2"), 13);
448 if !cs.is_satisfied() {
449 println!("{:?}", cs.which_is_unsatisfied().unwrap());
450 }
451
452 let a = Fq6Gadget::alloc(&mut cs.ns(|| "generate_e"), || Ok(Fq6::rand(&mut rng))).unwrap();
453 let b = Fq6Gadget::alloc(&mut cs.ns(|| "generate_f"), || Ok(Fq6::rand(&mut rng))).unwrap();
454 field_test(cs.ns(|| "test_fq6"), a, b);
455 random_frobenius_tests::<Fq6, _, Fq6Gadget, _>(cs.ns(|| "test_frob_fq6"), 13);
456 if !cs.is_satisfied() {
457 println!("{:?}", cs.which_is_unsatisfied().unwrap());
458 }
459
460 let c =
461 Fq12Gadget::alloc(&mut cs.ns(|| "generate_g"), || Ok(Fq12::rand(&mut rng))).unwrap();
462 let d =
463 Fq12Gadget::alloc(&mut cs.ns(|| "generate_h"), || Ok(Fq12::rand(&mut rng))).unwrap();
464 field_test(cs.ns(|| "test_fq12"), c, d);
465 random_frobenius_tests::<Fq12, _, Fq12Gadget, _>(cs.ns(|| "test_frob_fq12"), 13);
466 if !cs.is_satisfied() {
467 println!("Here!");
468 println!("{:?}", cs.which_is_unsatisfied().unwrap());
469 }
470
471 assert!(cs.is_satisfied());
472 }
473
474 #[test]
475 fn jubjub_field_gadgets_test() {
476 use crate::fields::jubjub::FqGadget;
477 use algebra::fields::jubjub::fq::Fq;
478
479 let mut cs = TestConstraintSystem::<Fq>::new();
480
481 let mut rng = thread_rng();
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 assert!(cs.is_satisfied());
490 }
491
492 #[test]
493 fn edwards_field_gadgets_test() {
494 use crate::fields::edwards_bls12::FqGadget;
495 use algebra::fields::edwards_bls12::fq::Fq;
496
497 let mut cs = TestConstraintSystem::<Fq>::new();
498
499 let mut rng = thread_rng();
500
501 let a = FqGadget::alloc(&mut cs.ns(|| "generate_a"), || Ok(Fq::rand(&mut rng))).unwrap();
502 let b = FqGadget::alloc(&mut cs.ns(|| "generate_b"), || Ok(Fq::rand(&mut rng))).unwrap();
503 field_test(cs.ns(|| "test_fq"), a, b);
504 if !cs.is_satisfied() {
505 println!("{:?}", cs.which_is_unsatisfied().unwrap());
506 }
507 assert!(cs.is_satisfied());
508 }
509}