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