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