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