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