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.clone();
246 let mut found_one = false;
247
248 for (i, bit) in BitIterator::new(exp).enumerate() {
249 if found_one {
250 res = res.square(cs.ns(|| format!("square for bit {:?}", i)))?;
251 }
252
253 if bit {
254 if found_one {
255 res = res.mul(cs.ns(|| format!("mul for bit {:?}", i)), self)?;
256 }
257 found_one = true;
258 }
259 }
260
261 Ok(res)
262 }
263
264 fn cost_of_mul() -> usize;
265
266 fn cost_of_mul_equals() -> usize {
267 Self::cost_of_mul() + <Self as EqGadget<ConstraintF>>::cost()
268 }
269
270 fn cost_of_inv() -> usize {
271 Self::cost_of_mul_equals()
272 }
273}
274
275#[cfg(test)]
276pub(crate) mod tests {
277 use rand::{self, SeedableRng};
278 use rand_xorshift::XorShiftRng;
279
280 use crate::{prelude::*, test_constraint_system::TestConstraintSystem, Vec};
281 use algebra::{test_rng, BitIterator, Field, UniformRand};
282 use r1cs_core::ConstraintSystem;
283
284 #[allow(dead_code)]
285 pub(crate) fn field_test<FE: Field, ConstraintF: Field, F: FieldGadget<FE, ConstraintF>>() {
286 let mut cs = TestConstraintSystem::<ConstraintF>::new();
287
288 let mut rng = test_rng();
289 let a_native = FE::rand(&mut rng);
290 let b_native = FE::rand(&mut rng);
291 let a = F::alloc(&mut cs.ns(|| "generate_a"), || Ok(a_native)).unwrap();
292 let b = F::alloc(&mut cs.ns(|| "generate_b"), || Ok(b_native)).unwrap();
293 let b_const = F::alloc_constant(&mut cs.ns(|| "generate_b_as_constant"), b_native).unwrap();
294
295 let zero = F::zero(cs.ns(|| "zero")).unwrap();
296 let zero_native = zero.get_value().unwrap();
297 zero.enforce_equal(&mut cs.ns(|| "zero_equals?"), &zero)
298 .unwrap();
299 assert_eq!(zero, zero);
300
301 let one = F::one(cs.ns(|| "one")).unwrap();
302 let one_native = one.get_value().unwrap();
303 assert_eq!(one, one);
304 one.enforce_equal(&mut cs.ns(|| "one_equals?"), &one)
305 .unwrap();
306 assert_ne!(one, zero);
307
308 let one_dup = zero.add(cs.ns(|| "zero_plus_one"), &one).unwrap();
309 one_dup
310 .enforce_equal(&mut cs.ns(|| "one_plus_zero_equals"), &one)
311 .unwrap();
312 assert_eq!(one_dup, one);
313
314 let two = one.add(cs.ns(|| "one_plus_one"), &one).unwrap();
315 two.enforce_equal(&mut cs.ns(|| "two_equals?"), &two)
316 .unwrap();
317 assert_eq!(two, two);
318 assert_ne!(zero, two);
319 assert_ne!(one, two);
320
321 // a == a
322 assert_eq!(a, a);
323
324 // a + 0 = a
325 let a_plus_zero = a.add(cs.ns(|| "a_plus_zero"), &zero).unwrap();
326 assert_eq!(a_plus_zero, a);
327 assert_eq!(a_plus_zero.get_value().unwrap(), a_native);
328 a_plus_zero
329 .enforce_equal(&mut cs.ns(|| "a_plus_zero_equals?"), &a)
330 .unwrap();
331
332 // a - 0 = a
333 let a_minus_zero = a.sub(cs.ns(|| "a_minus_zero"), &zero).unwrap();
334 assert_eq!(a_minus_zero, a);
335 assert_eq!(a_minus_zero.get_value().unwrap(), a_native);
336 a_minus_zero
337 .enforce_equal(&mut cs.ns(|| "a_minus_zero_equals?"), &a)
338 .unwrap();
339
340 // a - a = 0
341 let a_minus_a = a.sub(cs.ns(|| "a_minus_a"), &a).unwrap();
342 assert_eq!(a_minus_a, zero);
343 assert_eq!(a_minus_a.get_value().unwrap(), zero_native);
344 a_minus_a
345 .enforce_equal(&mut cs.ns(|| "a_minus_a_equals?"), &zero)
346 .unwrap();
347
348 // a + b = b + a
349 let a_b = a.add(cs.ns(|| "a_plus_b"), &b).unwrap();
350 let b_a = b.add(cs.ns(|| "b_plus_a"), &a).unwrap();
351 assert_eq!(a_b, b_a);
352 assert_eq!(a_b.get_value().unwrap(), a_native + &b_native);
353 a_b.enforce_equal(&mut cs.ns(|| "a+b == b+a"), &b_a)
354 .unwrap();
355
356 // (a + b) + a = a + (b + a)
357 let ab_a = a_b.add(cs.ns(|| "a_b_plus_a"), &a).unwrap();
358 let a_ba = a.add(cs.ns(|| "a_plus_b_a"), &b_a).unwrap();
359 assert_eq!(ab_a, a_ba);
360 assert_eq!(ab_a.get_value().unwrap(), a_native + &b_native + &a_native);
361 ab_a.enforce_equal(&mut cs.ns(|| "a+b + a == a+ b+a"), &a_ba)
362 .unwrap();
363
364 let b_times_a_plus_b = a_b.mul(cs.ns(|| "b * (a + b)"), &b).unwrap();
365 let b_times_b_plus_a = b_a.mul(cs.ns(|| "b * (b + a)"), &b).unwrap();
366 assert_eq!(b_times_b_plus_a, b_times_a_plus_b);
367 assert_eq!(
368 b_times_a_plus_b.get_value().unwrap(),
369 b_native * &(b_native + &a_native)
370 );
371 assert_eq!(
372 b_times_a_plus_b.get_value().unwrap(),
373 (b_native + &a_native) * &b_native
374 );
375 assert_eq!(
376 b_times_a_plus_b.get_value().unwrap(),
377 (a_native + &b_native) * &b_native
378 );
379 b_times_b_plus_a
380 .enforce_equal(&mut cs.ns(|| "b*(a+b) == b * (b+a)"), &b_times_a_plus_b)
381 .unwrap();
382
383 // a * 0 = 0
384 assert_eq!(a.mul(cs.ns(|| "a_times_zero"), &zero).unwrap(), zero);
385
386 // a * 1 = a
387 assert_eq!(a.mul(cs.ns(|| "a_times_one"), &one).unwrap(), a);
388 assert_eq!(
389 a.mul(cs.ns(|| "a_times_one2"), &one)
390 .unwrap()
391 .get_value()
392 .unwrap(),
393 a_native * &one_native
394 );
395
396 // a * b = b * a
397 let ab = a.mul(cs.ns(|| "a_times_b"), &b).unwrap();
398 let ba = b.mul(cs.ns(|| "b_times_a"), &a).unwrap();
399 assert_eq!(ab, ba);
400 assert_eq!(ab.get_value().unwrap(), a_native * &b_native);
401
402 let ab_const = a.mul(cs.ns(|| "a_times_b_const"), &b_const).unwrap();
403 let b_const_a = b_const.mul(cs.ns(|| "b_const_times_a"), &a).unwrap();
404 assert_eq!(ab_const, b_const_a);
405 assert_eq!(ab_const, ab);
406 assert_eq!(ab_const.get_value().unwrap(), a_native * &b_native);
407
408 // (a * b) * a = a * (b * a)
409 let ab_a = ab.mul(cs.ns(|| "ab_times_a"), &a).unwrap();
410 let a_ba = a.mul(cs.ns(|| "a_times_ba"), &ba).unwrap();
411 assert_eq!(ab_a, a_ba);
412 assert_eq!(ab_a.get_value().unwrap(), a_native * &b_native * &a_native);
413
414 let aa = a.mul(cs.ns(|| "a * a"), &a).unwrap();
415 let a_squared = a.square(cs.ns(|| "a^2")).unwrap();
416 a_squared
417 .enforce_equal(&mut cs.ns(|| "a^2 == a*a"), &aa)
418 .unwrap();
419 assert_eq!(aa, a_squared);
420 assert_eq!(aa.get_value().unwrap(), a_native.square());
421
422 let aa = a
423 .mul_by_constant(cs.ns(|| "a * a via mul_by_const"), &a.get_value().unwrap())
424 .unwrap();
425 a_squared
426 .enforce_equal(&mut cs.ns(|| "a^2 == a*a via mul_by_const"), &aa)
427 .unwrap();
428 assert_eq!(aa, a_squared);
429 assert_eq!(aa.get_value().unwrap(), a_native.square());
430
431 let a_b2 = a
432 .add_constant(cs.ns(|| "a + b via add_const"), &b.get_value().unwrap())
433 .unwrap();
434 a_b.enforce_equal(&mut cs.ns(|| "a + b == a + b via add_const"), &a_b2)
435 .unwrap();
436 assert_eq!(a_b, a_b2);
437
438 let a_inv = a.inverse(cs.ns(|| "a_inv")).unwrap();
439 a_inv
440 .mul_equals(cs.ns(|| "check_equals"), &a, &one)
441 .unwrap();
442 assert_eq!(
443 a_inv.get_value().unwrap(),
444 a.get_value().unwrap().inverse().unwrap()
445 );
446 assert_eq!(a_inv.get_value().unwrap(), a_native.inverse().unwrap());
447 // a * a * a = a^3
448 let bits = BitIterator::new([0x3])
449 .map(Boolean::constant)
450 .collect::<Vec<_>>();
451 assert_eq!(
452 a_native * &(a_native * &a_native),
453 a.pow(cs.ns(|| "test_pow"), &bits)
454 .unwrap()
455 .get_value()
456 .unwrap()
457 );
458
459 // a * a * a = a^3
460 assert_eq!(
461 a_native * &(a_native * &a_native),
462 a.pow_by_constant(cs.ns(|| "test_constant_pow"), &[3])
463 .unwrap()
464 .get_value()
465 .unwrap()
466 );
467
468 // a * a * a = a^3
469 let mut constants = [FE::zero(); 4];
470 for c in &mut constants {
471 *c = UniformRand::rand(&mut test_rng());
472 println!("Current c[i]: {:?}", c);
473 }
474 let bits = [Boolean::constant(false), Boolean::constant(true)];
475 let lookup_result =
476 F::two_bit_lookup(cs.ns(|| "Lookup"), &bits, constants.as_ref()).unwrap();
477 assert_eq!(lookup_result.get_value().unwrap(), constants[2]);
478
479 let negone: FE = UniformRand::rand(&mut test_rng());
480
481 let n = F::alloc(&mut cs.ns(|| "alloc new var"), || Ok(negone)).unwrap();
482 let _ = n.to_bytes(&mut cs.ns(|| "ToBytes")).unwrap();
483 let _ = n
484 .to_non_unique_bytes(&mut cs.ns(|| "ToBytes Strict"))
485 .unwrap();
486
487 let ab_false = a
488 .conditionally_add_constant(
489 cs.ns(|| "Add bool with coeff false"),
490 &Boolean::constant(false),
491 b_native,
492 )
493 .unwrap();
494 assert_eq!(ab_false.get_value().unwrap(), a_native);
495 let ab_true = a
496 .conditionally_add_constant(
497 cs.ns(|| "Add bool with coeff true"),
498 &Boolean::constant(true),
499 b_native,
500 )
501 .unwrap();
502 assert_eq!(ab_true.get_value().unwrap(), a_native + &b_native);
503
504 if !cs.is_satisfied() {
505 println!("{:?}", cs.which_is_unsatisfied().unwrap());
506 }
507 assert!(cs.is_satisfied());
508 }
509
510 #[allow(dead_code)]
511 pub(crate) fn frobenius_tests<
512 FE: Field,
513 ConstraintF: Field,
514 F: FieldGadget<FE, ConstraintF>,
515 >(
516 maxpower: usize,
517 ) {
518 let mut cs = TestConstraintSystem::<ConstraintF>::new();
519 let mut rng = XorShiftRng::seed_from_u64(1231275789u64);
520 for i in 0..=maxpower {
521 let mut a = FE::rand(&mut rng);
522 let mut a_gadget = F::alloc(cs.ns(|| format!("a_gadget_{:?}", i)), || Ok(a)).unwrap();
523 a_gadget = a_gadget
524 .frobenius_map(cs.ns(|| format!("frob_map_{}", i)), i)
525 .unwrap();
526 a.frobenius_map(i);
527
528 assert_eq!(a_gadget.get_value().unwrap(), a);
529 }
530
531 assert!(cs.is_satisfied());
532 }
533}