ark-r1cs-std/r1cs-std/src/fields/mod.rs
r1cs-std/src/fields/mod.rsRaw
1use algebra::{prelude::*, BitIteratorBE};
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 /// Comptues `self^bits`, where `bits` is a *little-endian* bit-wise decomposition
136 /// of the exponent.
137 fn pow_le(&self, bits: &[Boolean<ConstraintF>]) -> Result<Self, SynthesisError> {
138 let mut res = Self::one();
139 let mut power = self.clone();
140 for bit in bits {
141 let tmp = res.clone() * &power;
142 res = bit.select(&tmp, &res)?;
143 power.square_in_place()?;
144 }
145 Ok(res)
146 }
147
148 /// Computes `self^S`, where S is interpreted as an integer.
149 fn pow_by_constant<S: AsRef<[u64]>>(&self, exp: S) -> Result<Self, SynthesisError> {
150 let mut res = Self::one();
151 for i in BitIteratorBE::without_leading_zeros(exp) {
152 res.square_in_place()?;
153 if i {
154 res *= self;
155 }
156 }
157 Ok(res)
158 }
159}
160
161#[cfg(test)]
162pub(crate) mod tests {
163 use rand::{self, SeedableRng};
164 use rand_xorshift::XorShiftRng;
165
166 use crate::{fields::*, Vec};
167 use algebra::{test_rng, BitIteratorLE, Field, UniformRand};
168 use r1cs_core::{ConstraintSystem, SynthesisError};
169
170 #[allow(dead_code)]
171 pub(crate) fn field_test<F, ConstraintF, AF>() -> Result<(), SynthesisError>
172 where
173 F: Field,
174 ConstraintF: Field,
175 AF: FieldVar<F, ConstraintF>,
176 AF: TwoBitLookupGadget<ConstraintF, TableConstant = F>,
177 for<'a> &'a AF: FieldOpsBounds<'a, F, AF>,
178 {
179 let cs = ConstraintSystem::<ConstraintF>::new_ref();
180
181 let mut rng = test_rng();
182 let a_native = F::rand(&mut rng);
183 let b_native = F::rand(&mut rng);
184 let a = AF::new_witness(r1cs_core::ns!(cs, "generate_a"), || Ok(a_native))?;
185 let b = AF::new_witness(r1cs_core::ns!(cs, "generate_b"), || Ok(b_native))?;
186 let b_const = AF::new_constant(r1cs_core::ns!(cs, "b_as_constant"), b_native)?;
187
188 let zero = AF::zero();
189 let zero_native = zero.value()?;
190 zero.enforce_equal(&zero)?;
191
192 let one = AF::one();
193 let one_native = one.value()?;
194 one.enforce_equal(&one)?;
195
196 one.enforce_not_equal(&zero)?;
197
198 let one_dup = &zero + &one;
199 one_dup.enforce_equal(&one)?;
200
201 let two = &one + &one;
202 two.enforce_equal(&two)?;
203 two.enforce_equal(&one.double()?)?;
204 two.enforce_not_equal(&one)?;
205 two.enforce_not_equal(&zero)?;
206
207 // a + 0 = a
208 let a_plus_zero = &a + &zero;
209 assert_eq!(a_plus_zero.value()?, a_native);
210 a_plus_zero.enforce_equal(&a)?;
211 a_plus_zero.enforce_not_equal(&a.double()?)?;
212
213 // a - 0 = a
214 let a_minus_zero = &a - &zero;
215 assert_eq!(a_minus_zero.value()?, a_native);
216 a_minus_zero.enforce_equal(&a)?;
217
218 // a - a = 0
219 let a_minus_a = &a - &a;
220 assert_eq!(a_minus_a.value()?, zero_native);
221 a_minus_a.enforce_equal(&zero)?;
222
223 // a + b = b + a
224 let a_b = &a + &b;
225 let b_a = &b + &a;
226 assert_eq!(a_b.value()?, a_native + &b_native);
227 a_b.enforce_equal(&b_a)?;
228
229 // (a + b) + a = a + (b + a)
230 let ab_a = &a_b + &a;
231 let a_ba = &a + &b_a;
232 assert_eq!(ab_a.value()?, a_native + &b_native + &a_native);
233 ab_a.enforce_equal(&a_ba)?;
234
235 let b_times_a_plus_b = &a_b * &b;
236 let b_times_b_plus_a = &b_a * &b;
237 assert_eq!(
238 b_times_a_plus_b.value()?,
239 b_native * &(b_native + &a_native)
240 );
241 assert_eq!(
242 b_times_a_plus_b.value()?,
243 (b_native + &a_native) * &b_native
244 );
245 assert_eq!(
246 b_times_a_plus_b.value()?,
247 (a_native + &b_native) * &b_native
248 );
249 b_times_b_plus_a.enforce_equal(&b_times_a_plus_b)?;
250
251 // a * 1 = a
252 assert_eq!((&a * &one).value()?, a_native * &one_native);
253
254 // a * b = b * a
255 let ab = &a * &b;
256 let ba = &b * &a;
257 assert_eq!(ab.value()?, ba.value()?);
258 assert_eq!(ab.value()?, a_native * &b_native);
259
260 let ab_const = &a * &b_const;
261 let b_const_a = &b_const * &a;
262 assert_eq!(ab_const.value()?, b_const_a.value()?);
263 assert_eq!(ab_const.value()?, ab.value()?);
264 assert_eq!(ab_const.value()?, a_native * &b_native);
265
266 // (a * b) * a = a * (b * a)
267 let ab_a = &ab * &a;
268 let a_ba = &a * &ba;
269 assert_eq!(ab_a.value()?, a_ba.value()?);
270 assert_eq!(ab_a.value()?, a_native * &b_native * &a_native);
271
272 let aa = &a * &a;
273 let a_squared = a.square()?;
274 a_squared.enforce_equal(&aa)?;
275 assert_eq!(aa.value()?, a_squared.value()?);
276 assert_eq!(aa.value()?, a_native.square());
277
278 let aa = &a * a.value()?;
279 a_squared.enforce_equal(&aa)?;
280 assert_eq!(aa.value()?, a_squared.value()?);
281 assert_eq!(aa.value()?, a_native.square());
282
283 let a_b2 = &a + b_native;
284 a_b.enforce_equal(&a_b2)?;
285 assert_eq!(a_b.value()?, a_b2.value()?);
286
287 let a_inv = a.inverse()?;
288 a_inv.mul_equals(&a, &one)?;
289 assert_eq!(a_inv.value()?, a.value()?.inverse().unwrap());
290 assert_eq!(a_inv.value()?, a_native.inverse().unwrap());
291
292 let a_b_inv = a.mul_by_inverse(&b)?;
293 a_b_inv.mul_equals(&b, &a)?;
294 assert_eq!(a_b_inv.value()?, a_native * b_native.inverse().unwrap());
295
296 // a * a * a = a^3
297 let bits = BitIteratorLE::without_trailing_zeros([3u64])
298 .map(Boolean::constant)
299 .collect::<Vec<_>>();
300 assert_eq!(a_native.pow([0x3]), a.pow_le(&bits)?.value()?);
301
302 // a * a * a = a^3
303 assert_eq!(a_native.pow([0x3]), a.pow_by_constant(&[0x3])?.value()?);
304 assert!(cs.is_satisfied().unwrap());
305
306 // a * a * a = a^3
307 let mut constants = [F::zero(); 4];
308 for c in &mut constants {
309 *c = UniformRand::rand(&mut test_rng());
310 }
311 let bits = [
312 Boolean::<ConstraintF>::constant(false),
313 Boolean::constant(true),
314 ];
315 let lookup_result = AF::two_bit_lookup(&bits, constants.as_ref())?;
316 assert_eq!(lookup_result.value()?, constants[2]);
317 assert!(cs.is_satisfied().unwrap());
318
319 let f = F::from(1u128 << 64);
320 let f_bits = algebra::BitIteratorLE::new(&[0u64, 1u64]).collect::<Vec<_>>();
321 let fv = AF::new_witness(r1cs_core::ns!(cs, "alloc u128"), || Ok(f))?;
322 assert_eq!(fv.to_bits_le()?.value().unwrap()[..128], f_bits[..128]);
323 assert!(cs.is_satisfied().unwrap());
324
325 let r_native: F = UniformRand::rand(&mut test_rng());
326
327 let r = AF::new_witness(r1cs_core::ns!(cs, "r_native"), || Ok(r_native)).unwrap();
328 let _ = r.to_non_unique_bits_le()?;
329 assert!(cs.is_satisfied().unwrap());
330 let _ = r.to_bits_le()?;
331 assert!(cs.is_satisfied().unwrap());
332
333 let bytes = r.to_non_unique_bytes()?;
334 assert_eq!(
335 algebra::to_bytes!(r_native).unwrap(),
336 bytes.value().unwrap()
337 );
338 assert!(cs.is_satisfied().unwrap());
339 let bytes = r.to_bytes()?;
340 assert_eq!(
341 algebra::to_bytes!(r_native).unwrap(),
342 bytes.value().unwrap()
343 );
344 assert!(cs.is_satisfied().unwrap());
345
346 let ab_false = &a + (AF::from(Boolean::Constant(false)) * b_native);
347 assert_eq!(ab_false.value()?, a_native);
348 let ab_true = &a + (AF::from(Boolean::Constant(true)) * b_native);
349 assert_eq!(ab_true.value()?, a_native + &b_native);
350
351 if !cs.is_satisfied().unwrap() {
352 println!("{:?}", cs.which_is_unsatisfied().unwrap());
353 }
354 assert!(cs.is_satisfied().unwrap());
355 Ok(())
356 }
357
358 #[allow(dead_code)]
359 pub(crate) fn frobenius_tests<F: Field, ConstraintF, AF>(
360 maxpower: usize,
361 ) -> Result<(), SynthesisError>
362 where
363 F: Field,
364 ConstraintF: Field,
365 AF: FieldVar<F, ConstraintF>,
366 for<'a> &'a AF: FieldOpsBounds<'a, F, AF>,
367 {
368 let cs = ConstraintSystem::<ConstraintF>::new_ref();
369 let mut rng = XorShiftRng::seed_from_u64(1231275789u64);
370 for i in 0..=maxpower {
371 let mut a = F::rand(&mut rng);
372 let mut a_gadget = AF::new_witness(r1cs_core::ns!(cs, "a"), || Ok(a))?;
373 a_gadget.frobenius_map_in_place(i)?;
374 a.frobenius_map(i);
375
376 assert_eq!(a_gadget.value()?, a);
377 }
378
379 assert!(cs.is_satisfied().unwrap());
380 Ok(())
381 }
382}