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