ark-r1cs-std/r1cs-std/src/fields/mod.rs
r1cs-std/src/fields/mod.rsRaw
1use algebra::{prelude::*, BitIterator};
2use core::{
3 fmt::Debug,
4 ops::{Add, AddAssign, Mul, MulAssign, Sub, SubAssign},
5};
6use r1cs_core::SynthesisError;
7
8use crate::{prelude::*, Assignment};
9
10pub mod cubic_extension;
11pub mod quadratic_extension;
12
13pub mod fp;
14pub mod fp12;
15pub mod fp2;
16pub mod fp3;
17pub mod fp4;
18pub mod fp6_2over3;
19pub mod fp6_3over2;
20
21/// A hack used to work around the lack of implied bounds.
22pub trait FieldOpsBounds<'a, F, T: 'a>:
23 Sized
24 + Add<&'a T, Output = T>
25 + Sub<&'a T, Output = T>
26 + Mul<&'a T, Output = T>
27 + Add<T, Output = T>
28 + Sub<T, Output = T>
29 + Mul<T, Output = T>
30 + Add<F, Output = T>
31 + Sub<F, Output = T>
32 + Mul<F, Output = T>
33{
34}
35
36/// A variable representing a field. Corresponds to the native type `F`.
37pub trait FieldVar<F: Field, ConstraintF: Field>:
38 'static
39 + Clone
40 + From<Boolean<ConstraintF>>
41 + R1CSVar<ConstraintF, Value = F>
42 + EqGadget<ConstraintF>
43 + ToBitsGadget<ConstraintF>
44 + AllocVar<F, ConstraintF>
45 + ToBytesGadget<ConstraintF>
46 + CondSelectGadget<ConstraintF>
47 + for<'a> FieldOpsBounds<'a, F, Self>
48 + for<'a> AddAssign<&'a Self>
49 + for<'a> SubAssign<&'a Self>
50 + for<'a> MulAssign<&'a Self>
51 + AddAssign<Self>
52 + SubAssign<Self>
53 + MulAssign<Self>
54 + AddAssign<F>
55 + SubAssign<F>
56 + MulAssign<F>
57 + Debug
58{
59 fn zero() -> Self;
60
61 fn is_zero(&self) -> Result<Boolean<ConstraintF>, SynthesisError> {
62 self.is_eq(&Self::zero())
63 }
64
65 fn one() -> Self;
66
67 fn is_one(&self) -> Result<Boolean<ConstraintF>, SynthesisError> {
68 self.is_eq(&Self::one())
69 }
70
71 fn constant(v: F) -> Self;
72
73 fn double(&self) -> Result<Self, SynthesisError> {
74 Ok(self.clone() + self)
75 }
76
77 fn double_in_place(&mut self) -> Result<&mut Self, SynthesisError> {
78 *self += self.double()?;
79 Ok(self)
80 }
81
82 fn negate(&self) -> Result<Self, SynthesisError>;
83
84 #[inline]
85 fn negate_in_place(&mut self) -> Result<&mut Self, SynthesisError> {
86 *self = self.negate()?;
87 Ok(self)
88 }
89
90 fn square(&self) -> Result<Self, SynthesisError> {
91 Ok(self.clone() * self)
92 }
93
94 fn square_in_place(&mut self) -> Result<&mut Self, SynthesisError> {
95 *self = self.square()?;
96 Ok(self)
97 }
98
99 /// Enforce that `self * other == result`.
100 fn mul_equals(&self, other: &Self, result: &Self) -> Result<(), SynthesisError> {
101 let actual_result = self.clone() * other;
102 result.enforce_equal(&actual_result)
103 }
104
105 /// Enforce that `self * self == result`.
106 fn square_equals(&self, result: &Self) -> Result<(), SynthesisError> {
107 let actual_result = self.square()?;
108 result.enforce_equal(&actual_result)
109 }
110
111 fn inverse(&self) -> Result<Self, SynthesisError>;
112
113 /// Returns (self / denominator), but requires fewer constraints than
114 /// self * denominator.inverse()
115 /// It is up to the caller to ensure that denominator is non-zero,
116 /// since in that case the result is unconstrained.
117 fn mul_by_inverse(&self, denominator: &Self) -> Result<Self, SynthesisError> {
118 let result = Self::new_witness(self.cs().unwrap(), || {
119 let denominator_inv_native = denominator.value()?.inverse().get()?;
120 let result = self.value()? * &denominator_inv_native;
121 Ok(result)
122 })?;
123 result.mul_equals(&denominator, &self)?;
124
125 Ok(result)
126 }
127
128 fn frobenius_map(&self, power: usize) -> Result<Self, SynthesisError>;
129
130 fn frobenius_map_in_place(&mut self, power: usize) -> Result<&mut Self, SynthesisError> {
131 *self = self.frobenius_map(power)?;
132 Ok(self)
133 }
134
135 /// Accepts as input a list of bits which, when interpreted in little-endian
136 /// form, are a scalar.
137 //
138 // TODO: check that the input really should be in little-endian or not...
139 fn pow(&self, bits: &[Boolean<ConstraintF>]) -> Result<Self, SynthesisError> {
140 let mut res = Self::one();
141 for bit in bits.iter() {
142 res.square_in_place()?;
143 let tmp = res.clone() * self;
144 res = bit.select(&tmp, &res)?;
145 }
146 Ok(res)
147 }
148
149 fn pow_by_constant<S: AsRef<[u64]>>(&self, exp: S) -> Result<Self, SynthesisError> {
150 let mut res = self.clone();
151 let mut found_one = false;
152
153 for bit in BitIterator::new(exp) {
154 if found_one {
155 res = res.square()?;
156 }
157
158 if bit {
159 if found_one {
160 res *= self;
161 }
162 found_one = true;
163 }
164 }
165
166 Ok(res)
167 }
168}
169
170#[cfg(test)]
171pub(crate) mod tests {
172 use rand::{self, SeedableRng};
173 use rand_xorshift::XorShiftRng;
174
175 use crate::{fields::*, Vec};
176 use algebra::{test_rng, BitIterator, Field, UniformRand};
177 use r1cs_core::{ConstraintSystem, SynthesisError};
178
179 #[allow(dead_code)]
180 pub(crate) fn field_test<F, ConstraintF, AF>() -> Result<(), SynthesisError>
181 where
182 F: Field,
183 ConstraintF: Field,
184 AF: FieldVar<F, ConstraintF>,
185 AF: TwoBitLookupGadget<ConstraintF, TableConstant = F>,
186 for<'a> &'a AF: FieldOpsBounds<'a, F, AF>,
187 {
188 let cs = ConstraintSystem::<ConstraintF>::new_ref();
189
190 let mut rng = test_rng();
191 let a_native = F::rand(&mut rng);
192 let b_native = F::rand(&mut rng);
193 let a = AF::new_witness(cs.ns("generate_a"), || Ok(a_native))?;
194 let b = AF::new_witness(cs.ns("generate_b"), || Ok(b_native))?;
195 let b_const = AF::new_constant(cs.ns("b_as_constant"), b_native)?;
196
197 let zero = AF::zero();
198 let zero_native = zero.value()?;
199 zero.enforce_equal(&zero)?;
200
201 let one = AF::one();
202 let one_native = one.value()?;
203 one.enforce_equal(&one)?;
204
205 one.enforce_not_equal(&zero)?;
206
207 let one_dup = &zero + &one;
208 one_dup.enforce_equal(&one)?;
209
210 let two = &one + &one;
211 two.enforce_equal(&two)?;
212 two.enforce_equal(&one.double()?)?;
213 two.enforce_not_equal(&one)?;
214 two.enforce_not_equal(&zero)?;
215
216 // a + 0 = a
217 let a_plus_zero = &a + &zero;
218 assert_eq!(a_plus_zero.value()?, a_native);
219 a_plus_zero.enforce_equal(&a)?;
220 a_plus_zero.enforce_not_equal(&a.double()?)?;
221
222 // a - 0 = a
223 let a_minus_zero = &a - &zero;
224 assert_eq!(a_minus_zero.value()?, a_native);
225 a_minus_zero.enforce_equal(&a)?;
226
227 // a - a = 0
228 let a_minus_a = &a - &a;
229 assert_eq!(a_minus_a.value()?, zero_native);
230 a_minus_a.enforce_equal(&zero)?;
231
232 // a + b = b + a
233 let a_b = &a + &b;
234 let b_a = &b + &a;
235 assert_eq!(a_b.value()?, a_native + &b_native);
236 a_b.enforce_equal(&b_a)?;
237
238 // (a + b) + a = a + (b + a)
239 let ab_a = &a_b + &a;
240 let a_ba = &a + &b_a;
241 assert_eq!(ab_a.value()?, a_native + &b_native + &a_native);
242 ab_a.enforce_equal(&a_ba)?;
243
244 let b_times_a_plus_b = &a_b * &b;
245 let b_times_b_plus_a = &b_a * &b;
246 assert_eq!(
247 b_times_a_plus_b.value()?,
248 b_native * &(b_native + &a_native)
249 );
250 assert_eq!(
251 b_times_a_plus_b.value()?,
252 (b_native + &a_native) * &b_native
253 );
254 assert_eq!(
255 b_times_a_plus_b.value()?,
256 (a_native + &b_native) * &b_native
257 );
258 b_times_b_plus_a.enforce_equal(&b_times_a_plus_b)?;
259
260 // a * 1 = a
261 assert_eq!((&a * &one).value()?, a_native * &one_native);
262
263 // a * b = b * a
264 let ab = &a * &b;
265 let ba = &b * &a;
266 assert_eq!(ab.value()?, ba.value()?);
267 assert_eq!(ab.value()?, a_native * &b_native);
268
269 let ab_const = &a * &b_const;
270 let b_const_a = &b_const * &a;
271 assert_eq!(ab_const.value()?, b_const_a.value()?);
272 assert_eq!(ab_const.value()?, ab.value()?);
273 assert_eq!(ab_const.value()?, a_native * &b_native);
274
275 // (a * b) * a = a * (b * a)
276 let ab_a = &ab * &a;
277 let a_ba = &a * &ba;
278 assert_eq!(ab_a.value()?, a_ba.value()?);
279 assert_eq!(ab_a.value()?, a_native * &b_native * &a_native);
280
281 let aa = &a * &a;
282 let a_squared = a.square()?;
283 a_squared.enforce_equal(&aa)?;
284 assert_eq!(aa.value()?, a_squared.value()?);
285 assert_eq!(aa.value()?, a_native.square());
286
287 let aa = &a * a.value()?;
288 a_squared.enforce_equal(&aa)?;
289 assert_eq!(aa.value()?, a_squared.value()?);
290 assert_eq!(aa.value()?, a_native.square());
291
292 let a_b2 = &a + b_native;
293 a_b.enforce_equal(&a_b2)?;
294 assert_eq!(a_b.value()?, a_b2.value()?);
295
296 let a_inv = a.inverse()?;
297 a_inv.mul_equals(&a, &one)?;
298 assert_eq!(a_inv.value()?, a.value()?.inverse().unwrap());
299 assert_eq!(a_inv.value()?, a_native.inverse().unwrap());
300
301 let a_b_inv = a.mul_by_inverse(&b)?;
302 a_b_inv.mul_equals(&b, &a)?;
303 assert_eq!(a_b_inv.value()?, a_native * b_native.inverse().unwrap());
304
305 // a * a * a = a^3
306 let bits = BitIterator::new([0x3])
307 .map(Boolean::constant)
308 .collect::<Vec<_>>();
309 assert_eq!(a_native.pow([0x3]), a.pow(&bits)?.value()?);
310
311 // a * a * a = a^3
312 assert_eq!(a_native.pow([0x3]), a.pow_by_constant(&[3])?.value()?);
313
314 // a * a * a = a^3
315 let mut constants = [F::zero(); 4];
316 for c in &mut constants {
317 *c = UniformRand::rand(&mut test_rng());
318 }
319 let bits = [
320 Boolean::<ConstraintF>::constant(false),
321 Boolean::constant(true),
322 ];
323 let lookup_result = AF::two_bit_lookup(&bits, constants.as_ref())?;
324 assert_eq!(lookup_result.value()?, constants[2]);
325
326 let negone: F = UniformRand::rand(&mut test_rng());
327
328 let n = AF::new_witness(cs.ns("alloc new var"), || Ok(negone)).unwrap();
329 let _ = n.to_bytes()?;
330 let _ = n.to_non_unique_bytes()?;
331
332 let ab_false = &a + (AF::from(Boolean::Constant(false)) * b_native);
333 assert_eq!(ab_false.value()?, a_native);
334 let ab_true = &a + (AF::from(Boolean::Constant(true)) * b_native);
335 assert_eq!(ab_true.value()?, a_native + &b_native);
336
337 if !cs.is_satisfied().unwrap() {
338 println!("{:?}", cs.which_is_unsatisfied().unwrap());
339 }
340 assert!(cs.is_satisfied().unwrap());
341 Ok(())
342 }
343
344 #[allow(dead_code)]
345 pub(crate) fn frobenius_tests<F: Field, ConstraintF, AF>(
346 maxpower: usize,
347 ) -> Result<(), SynthesisError>
348 where
349 F: Field,
350 ConstraintF: Field,
351 AF: FieldVar<F, ConstraintF>,
352 for<'a> &'a AF: FieldOpsBounds<'a, F, AF>,
353 {
354 let cs = ConstraintSystem::<ConstraintF>::new_ref();
355 let mut rng = XorShiftRng::seed_from_u64(1231275789u64);
356 for i in 0..=maxpower {
357 let mut a = F::rand(&mut rng);
358 let mut a_gadget = AF::new_witness(cs.ns(format!("a_gadget_{:?}", i)), || Ok(a))?;
359 a_gadget.frobenius_map_in_place(i)?;
360 a.frobenius_map(i);
361
362 assert_eq!(a_gadget.value()?, a);
363 }
364
365 assert!(cs.is_satisfied().unwrap());
366 Ok(())
367 }
368}