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