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