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 // Returns (self / denominator), but requires fewer constraints than
204 // self * denominator.inverse()
205 // It is up to the caller to ensure that denominator is non-zero,
206 // since in that case the result is unconstrained.
207 fn mul_by_inverse<CS: ConstraintSystem<ConstraintF>>(
208 &self,
209 mut cs: CS,
210 denominator: &Self,
211 ) -> Result<Self, SynthesisError> {
212 let denominator_inv_native = denominator
213 .get_value()
214 .and_then(|val| val.inverse())
215 .get()?;
216 let result_native = self.get_value().get()? * &denominator_inv_native;
217
218 let result = Self::alloc(&mut cs.ns(|| "alloc mul_by_inverse result"), || {
219 Ok(result_native)
220 })?;
221 result.mul_equals(cs.ns(|| "check mul_by_inverse"), &denominator, &self)?;
222
223 Ok(result)
224 }
225
226 fn frobenius_map<CS: ConstraintSystem<ConstraintF>>(
227 &self,
228 _: CS,
229 power: usize,
230 ) -> Result<Self, SynthesisError>;
231
232 fn frobenius_map_in_place<CS: ConstraintSystem<ConstraintF>>(
233 &mut self,
234 cs: CS,
235 power: usize,
236 ) -> Result<&mut Self, SynthesisError> {
237 *self = self.frobenius_map(cs, power)?;
238 Ok(self)
239 }
240
241 /// Accepts as input a list of bits which, when interpreted in big-endian
242 /// form, are a scalar.
243 #[inline]
244 fn pow<CS: ConstraintSystem<ConstraintF>>(
245 &self,
246 mut cs: CS,
247 bits: &[Boolean],
248 ) -> Result<Self, SynthesisError> {
249 let mut res = Self::one(cs.ns(|| "Alloc result"))?;
250 for (i, bit) in bits.iter().enumerate() {
251 res = res.square(cs.ns(|| format!("Double {}", i)))?;
252 let tmp = res.mul(cs.ns(|| format!("Add {}-th base power", i)), self)?;
253 res = Self::conditionally_select(
254 cs.ns(|| format!("Conditional Select {}", i)),
255 bit,
256 &tmp,
257 &res,
258 )?;
259 }
260 Ok(res)
261 }
262
263 fn pow_by_constant<S: AsRef<[u64]>, CS: ConstraintSystem<ConstraintF>>(
264 &self,
265 mut cs: CS,
266 exp: S,
267 ) -> Result<Self, SynthesisError> {
268 let mut res = self.clone();
269 let mut found_one = false;
270
271 for (i, bit) in BitIterator::new(exp).enumerate() {
272 if found_one {
273 res = res.square(cs.ns(|| format!("square for bit {:?}", i)))?;
274 }
275
276 if bit {
277 if found_one {
278 res = res.mul(cs.ns(|| format!("mul for bit {:?}", i)), self)?;
279 }
280 found_one = true;
281 }
282 }
283
284 Ok(res)
285 }
286
287 fn cost_of_mul() -> usize;
288
289 fn cost_of_mul_equals() -> usize {
290 Self::cost_of_mul() + <Self as EqGadget<ConstraintF>>::cost()
291 }
292
293 fn cost_of_inv() -> usize {
294 Self::cost_of_mul_equals()
295 }
296}
297
298#[cfg(test)]
299pub(crate) mod tests {
300 use rand::{self, SeedableRng};
301 use rand_xorshift::XorShiftRng;
302
303 use crate::{prelude::*, test_constraint_system::TestConstraintSystem, Vec};
304 use algebra::{test_rng, BitIterator, Field, UniformRand};
305 use r1cs_core::ConstraintSystem;
306
307 #[allow(dead_code)]
308 pub(crate) fn field_test<FE: Field, ConstraintF: Field, F: FieldGadget<FE, ConstraintF>>() {
309 let mut cs = TestConstraintSystem::<ConstraintF>::new();
310
311 let mut rng = test_rng();
312 let a_native = FE::rand(&mut rng);
313 let b_native = FE::rand(&mut rng);
314 let a = F::alloc(&mut cs.ns(|| "generate_a"), || Ok(a_native)).unwrap();
315 let b = F::alloc(&mut cs.ns(|| "generate_b"), || Ok(b_native)).unwrap();
316 let b_const = F::alloc_constant(&mut cs.ns(|| "generate_b_as_constant"), b_native).unwrap();
317
318 let zero = F::zero(cs.ns(|| "zero")).unwrap();
319 let zero_native = zero.get_value().unwrap();
320 zero.enforce_equal(&mut cs.ns(|| "zero_equals?"), &zero)
321 .unwrap();
322 assert_eq!(zero, zero);
323
324 let one = F::one(cs.ns(|| "one")).unwrap();
325 let one_native = one.get_value().unwrap();
326 assert_eq!(one, one);
327 one.enforce_equal(&mut cs.ns(|| "one_equals?"), &one)
328 .unwrap();
329 assert_ne!(one, zero);
330
331 let one_dup = zero.add(cs.ns(|| "zero_plus_one"), &one).unwrap();
332 one_dup
333 .enforce_equal(&mut cs.ns(|| "one_plus_zero_equals"), &one)
334 .unwrap();
335 assert_eq!(one_dup, one);
336
337 let two = one.add(cs.ns(|| "one_plus_one"), &one).unwrap();
338 two.enforce_equal(&mut cs.ns(|| "two_equals?"), &two)
339 .unwrap();
340 assert_eq!(two, two);
341 assert_ne!(zero, two);
342 assert_ne!(one, two);
343
344 // a == a
345 assert_eq!(a, a);
346
347 // a + 0 = a
348 let a_plus_zero = a.add(cs.ns(|| "a_plus_zero"), &zero).unwrap();
349 assert_eq!(a_plus_zero, a);
350 assert_eq!(a_plus_zero.get_value().unwrap(), a_native);
351 a_plus_zero
352 .enforce_equal(&mut cs.ns(|| "a_plus_zero_equals?"), &a)
353 .unwrap();
354
355 // a - 0 = a
356 let a_minus_zero = a.sub(cs.ns(|| "a_minus_zero"), &zero).unwrap();
357 assert_eq!(a_minus_zero, a);
358 assert_eq!(a_minus_zero.get_value().unwrap(), a_native);
359 a_minus_zero
360 .enforce_equal(&mut cs.ns(|| "a_minus_zero_equals?"), &a)
361 .unwrap();
362
363 // a - a = 0
364 let a_minus_a = a.sub(cs.ns(|| "a_minus_a"), &a).unwrap();
365 assert_eq!(a_minus_a, zero);
366 assert_eq!(a_minus_a.get_value().unwrap(), zero_native);
367 a_minus_a
368 .enforce_equal(&mut cs.ns(|| "a_minus_a_equals?"), &zero)
369 .unwrap();
370
371 // a + b = b + a
372 let a_b = a.add(cs.ns(|| "a_plus_b"), &b).unwrap();
373 let b_a = b.add(cs.ns(|| "b_plus_a"), &a).unwrap();
374 assert_eq!(a_b, b_a);
375 assert_eq!(a_b.get_value().unwrap(), a_native + &b_native);
376 a_b.enforce_equal(&mut cs.ns(|| "a+b == b+a"), &b_a)
377 .unwrap();
378
379 // (a + b) + a = a + (b + a)
380 let ab_a = a_b.add(cs.ns(|| "a_b_plus_a"), &a).unwrap();
381 let a_ba = a.add(cs.ns(|| "a_plus_b_a"), &b_a).unwrap();
382 assert_eq!(ab_a, a_ba);
383 assert_eq!(ab_a.get_value().unwrap(), a_native + &b_native + &a_native);
384 ab_a.enforce_equal(&mut cs.ns(|| "a+b + a == a+ b+a"), &a_ba)
385 .unwrap();
386
387 let b_times_a_plus_b = a_b.mul(cs.ns(|| "b * (a + b)"), &b).unwrap();
388 let b_times_b_plus_a = b_a.mul(cs.ns(|| "b * (b + a)"), &b).unwrap();
389 assert_eq!(b_times_b_plus_a, b_times_a_plus_b);
390 assert_eq!(
391 b_times_a_plus_b.get_value().unwrap(),
392 b_native * &(b_native + &a_native)
393 );
394 assert_eq!(
395 b_times_a_plus_b.get_value().unwrap(),
396 (b_native + &a_native) * &b_native
397 );
398 assert_eq!(
399 b_times_a_plus_b.get_value().unwrap(),
400 (a_native + &b_native) * &b_native
401 );
402 b_times_b_plus_a
403 .enforce_equal(&mut cs.ns(|| "b*(a+b) == b * (b+a)"), &b_times_a_plus_b)
404 .unwrap();
405
406 // a * 0 = 0
407 assert_eq!(a.mul(cs.ns(|| "a_times_zero"), &zero).unwrap(), zero);
408
409 // a * 1 = a
410 assert_eq!(a.mul(cs.ns(|| "a_times_one"), &one).unwrap(), a);
411 assert_eq!(
412 a.mul(cs.ns(|| "a_times_one2"), &one)
413 .unwrap()
414 .get_value()
415 .unwrap(),
416 a_native * &one_native
417 );
418
419 // a * b = b * a
420 let ab = a.mul(cs.ns(|| "a_times_b"), &b).unwrap();
421 let ba = b.mul(cs.ns(|| "b_times_a"), &a).unwrap();
422 assert_eq!(ab, ba);
423 assert_eq!(ab.get_value().unwrap(), a_native * &b_native);
424
425 let ab_const = a.mul(cs.ns(|| "a_times_b_const"), &b_const).unwrap();
426 let b_const_a = b_const.mul(cs.ns(|| "b_const_times_a"), &a).unwrap();
427 assert_eq!(ab_const, b_const_a);
428 assert_eq!(ab_const, ab);
429 assert_eq!(ab_const.get_value().unwrap(), a_native * &b_native);
430
431 // (a * b) * a = a * (b * a)
432 let ab_a = ab.mul(cs.ns(|| "ab_times_a"), &a).unwrap();
433 let a_ba = a.mul(cs.ns(|| "a_times_ba"), &ba).unwrap();
434 assert_eq!(ab_a, a_ba);
435 assert_eq!(ab_a.get_value().unwrap(), a_native * &b_native * &a_native);
436
437 let aa = a.mul(cs.ns(|| "a * a"), &a).unwrap();
438 let a_squared = a.square(cs.ns(|| "a^2")).unwrap();
439 a_squared
440 .enforce_equal(&mut cs.ns(|| "a^2 == a*a"), &aa)
441 .unwrap();
442 assert_eq!(aa, a_squared);
443 assert_eq!(aa.get_value().unwrap(), a_native.square());
444
445 let aa = a
446 .mul_by_constant(cs.ns(|| "a * a via mul_by_const"), &a.get_value().unwrap())
447 .unwrap();
448 a_squared
449 .enforce_equal(&mut cs.ns(|| "a^2 == a*a via mul_by_const"), &aa)
450 .unwrap();
451 assert_eq!(aa, a_squared);
452 assert_eq!(aa.get_value().unwrap(), a_native.square());
453
454 let a_b2 = a
455 .add_constant(cs.ns(|| "a + b via add_const"), &b.get_value().unwrap())
456 .unwrap();
457 a_b.enforce_equal(&mut cs.ns(|| "a + b == a + b via add_const"), &a_b2)
458 .unwrap();
459 assert_eq!(a_b, a_b2);
460
461 let a_inv = a.inverse(cs.ns(|| "a_inv")).unwrap();
462 a_inv
463 .mul_equals(cs.ns(|| "check a_inv * a = 1"), &a, &one)
464 .unwrap();
465 assert_eq!(
466 a_inv.get_value().unwrap(),
467 a.get_value().unwrap().inverse().unwrap()
468 );
469 assert_eq!(a_inv.get_value().unwrap(), a_native.inverse().unwrap());
470
471 let a_b_inv = a.mul_by_inverse(cs.ns(|| "a_b_inv"), &b).unwrap();
472 a_b_inv
473 .mul_equals(cs.ns(|| "check a_b_inv * b = a"), &b, &a)
474 .unwrap();
475 assert_eq!(
476 a_b_inv.get_value().unwrap(),
477 a_native * b_native.inverse().unwrap()
478 );
479
480 // a * a * a = a^3
481 let bits = BitIterator::new([0x3])
482 .map(Boolean::constant)
483 .collect::<Vec<_>>();
484 assert_eq!(
485 a_native * &(a_native * &a_native),
486 a.pow(cs.ns(|| "test_pow"), &bits)
487 .unwrap()
488 .get_value()
489 .unwrap()
490 );
491
492 // a * a * a = a^3
493 assert_eq!(
494 a_native * &(a_native * &a_native),
495 a.pow_by_constant(cs.ns(|| "test_constant_pow"), &[3])
496 .unwrap()
497 .get_value()
498 .unwrap()
499 );
500
501 // a * a * a = a^3
502 let mut constants = [FE::zero(); 4];
503 for c in &mut constants {
504 *c = UniformRand::rand(&mut test_rng());
505 println!("Current c[i]: {:?}", c);
506 }
507 let bits = [Boolean::constant(false), Boolean::constant(true)];
508 let lookup_result =
509 F::two_bit_lookup(cs.ns(|| "Lookup"), &bits, constants.as_ref()).unwrap();
510 assert_eq!(lookup_result.get_value().unwrap(), constants[2]);
511
512 let negone: FE = UniformRand::rand(&mut test_rng());
513
514 let n = F::alloc(&mut cs.ns(|| "alloc new var"), || Ok(negone)).unwrap();
515 let _ = n.to_bytes(&mut cs.ns(|| "ToBytes")).unwrap();
516 let _ = n
517 .to_non_unique_bytes(&mut cs.ns(|| "ToBytes Strict"))
518 .unwrap();
519
520 let ab_false = a
521 .conditionally_add_constant(
522 cs.ns(|| "Add bool with coeff false"),
523 &Boolean::constant(false),
524 b_native,
525 )
526 .unwrap();
527 assert_eq!(ab_false.get_value().unwrap(), a_native);
528 let ab_true = a
529 .conditionally_add_constant(
530 cs.ns(|| "Add bool with coeff true"),
531 &Boolean::constant(true),
532 b_native,
533 )
534 .unwrap();
535 assert_eq!(ab_true.get_value().unwrap(), a_native + &b_native);
536
537 if !cs.is_satisfied() {
538 println!("{:?}", cs.which_is_unsatisfied().unwrap());
539 }
540 assert!(cs.is_satisfied());
541 }
542
543 #[allow(dead_code)]
544 pub(crate) fn frobenius_tests<
545 FE: Field,
546 ConstraintF: Field,
547 F: FieldGadget<FE, ConstraintF>,
548 >(
549 maxpower: usize,
550 ) {
551 let mut cs = TestConstraintSystem::<ConstraintF>::new();
552 let mut rng = XorShiftRng::seed_from_u64(1231275789u64);
553 for i in 0..=maxpower {
554 let mut a = FE::rand(&mut rng);
555 let mut a_gadget = F::alloc(cs.ns(|| format!("a_gadget_{:?}", i)), || Ok(a)).unwrap();
556 a_gadget = a_gadget
557 .frobenius_map(cs.ns(|| format!("frob_map_{}", i)), i)
558 .unwrap();
559 a.frobenius_map(i);
560
561 assert_eq!(a_gadget.get_value().unwrap(), a);
562 }
563
564 assert!(cs.is_satisfied());
565 }
566}