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
10/// This module contains a generic implementation of cubic extension field variables.
11/// That is, it implements the R1CS equivalent of `algebra_core::CubicExtField`.
12pub mod cubic_extension;
13/// This module contains a generic implementation of quadratic extension field variables.
14/// That is, it implements the R1CS equivalent of `algebra_core::QuadExtField`.
15pub mod quadratic_extension;
16
17/// This module contains a generic implementation of prime field variables.
18/// That is, it implements the R1CS equivalent of `algebra_core::Fp*`.
19pub mod fp;
20
21/// This module contains a generic implementation of the degree-12 tower extension field.
22/// That is, it implements the R1CS equivalent of `algebra_core::Fp12`
23pub mod fp12;
24/// This module contains a generic implementation of the degree-2 tower extension field.
25/// That is, it implements the R1CS equivalent of `algebra_core::Fp2`
26pub mod fp2;
27/// This module contains a generic implementation of the degree-3 tower extension field.
28/// That is, it implements the R1CS equivalent of `algebra_core::Fp3`
29pub mod fp3;
30/// This module contains a generic implementation of the degree-4 tower extension field.
31/// That is, it implements the R1CS equivalent of `algebra_core::Fp4`
32pub mod fp4;
33/// This module contains a generic implementation of the degree-6 tower extension field.
34/// That is, it implements the R1CS equivalent of `algebra_core::fp6_2over3::Fp6`
35pub mod fp6_2over3;
36/// This module contains a generic implementation of the degree-6 tower extension field.
37/// That is, it implements the R1CS equivalent of `algebra_core::fp6_3over2::Fp6`
38pub mod fp6_3over2;
39
40/// This trait is a hack used to work around the lack of implied bounds.
41pub trait FieldOpsBounds<'a, F, T: 'a>:
42 Sized
43 + Add<&'a T, Output = T>
44 + Sub<&'a T, Output = T>
45 + Mul<&'a T, Output = T>
46 + Add<T, Output = T>
47 + Sub<T, Output = T>
48 + Mul<T, Output = T>
49 + Add<F, Output = T>
50 + Sub<F, Output = T>
51 + Mul<F, Output = T>
52{
53}
54
55/// A variable representing a field. Corresponds to the native type `F`.
56pub trait FieldVar<F: Field, ConstraintF: Field>:
57 'static
58 + Clone
59 + From<Boolean<ConstraintF>>
60 + R1CSVar<ConstraintF, Value = F>
61 + EqGadget<ConstraintF>
62 + ToBitsGadget<ConstraintF>
63 + AllocVar<F, ConstraintF>
64 + ToBytesGadget<ConstraintF>
65 + CondSelectGadget<ConstraintF>
66 + for<'a> FieldOpsBounds<'a, F, Self>
67 + for<'a> AddAssign<&'a Self>
68 + for<'a> SubAssign<&'a Self>
69 + for<'a> MulAssign<&'a Self>
70 + AddAssign<Self>
71 + SubAssign<Self>
72 + MulAssign<Self>
73 + AddAssign<F>
74 + SubAssign<F>
75 + MulAssign<F>
76 + Debug
77{
78 /// Returns the constant `F::zero()`.
79 fn zero() -> Self;
80
81 /// Returns a `Boolean` representing whether `self == Self::zero()`.
82 fn is_zero(&self) -> Result<Boolean<ConstraintF>, SynthesisError> {
83 self.is_eq(&Self::zero())
84 }
85
86 /// Returns the constant `F::one()`.
87 fn one() -> Self;
88
89 /// Returns a `Boolean` representing whether `self == Self::one()`.
90 fn is_one(&self) -> Result<Boolean<ConstraintF>, SynthesisError> {
91 self.is_eq(&Self::one())
92 }
93
94 /// Returns a constant with value `v`.
95 ///
96 /// This *should not* allocate any variables.
97 fn constant(v: F) -> Self;
98
99 /// Computes `self + self`.
100 fn double(&self) -> Result<Self, SynthesisError> {
101 Ok(self.clone() + self)
102 }
103
104 /// Sets `self = self + self`.
105 fn double_in_place(&mut self) -> Result<&mut Self, SynthesisError> {
106 *self += self.double()?;
107 Ok(self)
108 }
109
110 /// Coputes `-self`.
111 fn negate(&self) -> Result<Self, SynthesisError>;
112
113 /// Sets `self = -self`.
114 #[inline]
115 fn negate_in_place(&mut self) -> Result<&mut Self, SynthesisError> {
116 *self = self.negate()?;
117 Ok(self)
118 }
119
120 /// Computes `self * self`.
121 ///
122 /// A default implementation is provided which just invokes the underlying
123 /// multiplication routine. However, this method should be specialized
124 /// for extension fields, where faster algorithms exist for squaring.
125 fn square(&self) -> Result<Self, SynthesisError> {
126 Ok(self.clone() * self)
127 }
128
129 /// Sets `self = self.square()`.
130 fn square_in_place(&mut self) -> Result<&mut Self, SynthesisError> {
131 *self = self.square()?;
132 Ok(self)
133 }
134
135 /// Enforces that `self * other == result`.
136 fn mul_equals(&self, other: &Self, result: &Self) -> Result<(), SynthesisError> {
137 let actual_result = self.clone() * other;
138 result.enforce_equal(&actual_result)
139 }
140
141 /// Enforces that `self * self == result`.
142 fn square_equals(&self, result: &Self) -> Result<(), SynthesisError> {
143 let actual_result = self.square()?;
144 result.enforce_equal(&actual_result)
145 }
146
147 /// Computes `result` such that `self * result == Self::one()`.
148 fn inverse(&self) -> Result<Self, SynthesisError>;
149
150 /// Returns `(self / denominator)`. but requires fewer constraints than
151 /// `self * denominator.inverse()`.
152 /// It is up to the caller to ensure that denominator is non-zero,
153 /// since in that case the result is unconstrained.
154 fn mul_by_inverse(&self, denominator: &Self) -> Result<Self, SynthesisError> {
155 let result = Self::new_witness(self.cs(), || {
156 let denominator_inv_native = denominator.value()?.inverse().get()?;
157 let result = self.value()? * &denominator_inv_native;
158 Ok(result)
159 })?;
160 result.mul_equals(&denominator, &self)?;
161
162 Ok(result)
163 }
164
165 /// Computes the frobenius map over `self`.
166 fn frobenius_map(&self, power: usize) -> Result<Self, SynthesisError>;
167
168 /// Sets `self = self.frobenius_map()`.
169 fn frobenius_map_in_place(&mut self, power: usize) -> Result<&mut Self, SynthesisError> {
170 *self = self.frobenius_map(power)?;
171 Ok(self)
172 }
173
174 /// Comptues `self^bits`, where `bits` is a *little-endian* bit-wise decomposition
175 /// of the exponent.
176 fn pow_le(&self, bits: &[Boolean<ConstraintF>]) -> Result<Self, SynthesisError> {
177 let mut res = Self::one();
178 let mut power = self.clone();
179 for bit in bits {
180 let tmp = res.clone() * &power;
181 res = bit.select(&tmp, &res)?;
182 power.square_in_place()?;
183 }
184 Ok(res)
185 }
186
187 /// Computes `self^S`, where S is interpreted as an little-endian u64-decomposition of
188 /// an integer.
189 fn pow_by_constant<S: AsRef<[u64]>>(&self, exp: S) -> Result<Self, SynthesisError> {
190 let mut res = Self::one();
191 for i in BitIteratorBE::without_leading_zeros(exp) {
192 res.square_in_place()?;
193 if i {
194 res *= self;
195 }
196 }
197 Ok(res)
198 }
199}
200
201#[cfg(test)]
202pub(crate) mod tests {
203 use rand::{self, SeedableRng};
204 use rand_xorshift::XorShiftRng;
205
206 use crate::{fields::*, Vec};
207 use algebra::{test_rng, BitIteratorLE, Field, UniformRand};
208 use r1cs_core::{ConstraintSystem, SynthesisError};
209
210 #[allow(dead_code)]
211 pub(crate) fn field_test<F, ConstraintF, AF>() -> Result<(), SynthesisError>
212 where
213 F: Field,
214 ConstraintF: Field,
215 AF: FieldVar<F, ConstraintF>,
216 AF: TwoBitLookupGadget<ConstraintF, TableConstant = F>,
217 for<'a> &'a AF: FieldOpsBounds<'a, F, AF>,
218 {
219 let cs = ConstraintSystem::<ConstraintF>::new_ref();
220
221 let mut rng = test_rng();
222 let a_native = F::rand(&mut rng);
223 let b_native = F::rand(&mut rng);
224 let a = AF::new_witness(r1cs_core::ns!(cs, "generate_a"), || Ok(a_native))?;
225 let b = AF::new_witness(r1cs_core::ns!(cs, "generate_b"), || Ok(b_native))?;
226 let b_const = AF::new_constant(r1cs_core::ns!(cs, "b_as_constant"), b_native)?;
227
228 let zero = AF::zero();
229 let zero_native = zero.value()?;
230 zero.enforce_equal(&zero)?;
231
232 let one = AF::one();
233 let one_native = one.value()?;
234 one.enforce_equal(&one)?;
235
236 one.enforce_not_equal(&zero)?;
237
238 let one_dup = &zero + &one;
239 one_dup.enforce_equal(&one)?;
240
241 let two = &one + &one;
242 two.enforce_equal(&two)?;
243 two.enforce_equal(&one.double()?)?;
244 two.enforce_not_equal(&one)?;
245 two.enforce_not_equal(&zero)?;
246
247 // a + 0 = a
248 let a_plus_zero = &a + &zero;
249 assert_eq!(a_plus_zero.value()?, a_native);
250 a_plus_zero.enforce_equal(&a)?;
251 a_plus_zero.enforce_not_equal(&a.double()?)?;
252
253 // a - 0 = a
254 let a_minus_zero = &a - &zero;
255 assert_eq!(a_minus_zero.value()?, a_native);
256 a_minus_zero.enforce_equal(&a)?;
257
258 // a - a = 0
259 let a_minus_a = &a - &a;
260 assert_eq!(a_minus_a.value()?, zero_native);
261 a_minus_a.enforce_equal(&zero)?;
262
263 // a + b = b + a
264 let a_b = &a + &b;
265 let b_a = &b + &a;
266 assert_eq!(a_b.value()?, a_native + &b_native);
267 a_b.enforce_equal(&b_a)?;
268
269 // (a + b) + a = a + (b + a)
270 let ab_a = &a_b + &a;
271 let a_ba = &a + &b_a;
272 assert_eq!(ab_a.value()?, a_native + &b_native + &a_native);
273 ab_a.enforce_equal(&a_ba)?;
274
275 let b_times_a_plus_b = &a_b * &b;
276 let b_times_b_plus_a = &b_a * &b;
277 assert_eq!(
278 b_times_a_plus_b.value()?,
279 b_native * &(b_native + &a_native)
280 );
281 assert_eq!(
282 b_times_a_plus_b.value()?,
283 (b_native + &a_native) * &b_native
284 );
285 assert_eq!(
286 b_times_a_plus_b.value()?,
287 (a_native + &b_native) * &b_native
288 );
289 b_times_b_plus_a.enforce_equal(&b_times_a_plus_b)?;
290
291 // a * 1 = a
292 assert_eq!((&a * &one).value()?, a_native * &one_native);
293
294 // a * b = b * a
295 let ab = &a * &b;
296 let ba = &b * &a;
297 assert_eq!(ab.value()?, ba.value()?);
298 assert_eq!(ab.value()?, a_native * &b_native);
299
300 let ab_const = &a * &b_const;
301 let b_const_a = &b_const * &a;
302 assert_eq!(ab_const.value()?, b_const_a.value()?);
303 assert_eq!(ab_const.value()?, ab.value()?);
304 assert_eq!(ab_const.value()?, a_native * &b_native);
305
306 // (a * b) * a = a * (b * a)
307 let ab_a = &ab * &a;
308 let a_ba = &a * &ba;
309 assert_eq!(ab_a.value()?, a_ba.value()?);
310 assert_eq!(ab_a.value()?, a_native * &b_native * &a_native);
311
312 let aa = &a * &a;
313 let a_squared = a.square()?;
314 a_squared.enforce_equal(&aa)?;
315 assert_eq!(aa.value()?, a_squared.value()?);
316 assert_eq!(aa.value()?, a_native.square());
317
318 let aa = &a * a.value()?;
319 a_squared.enforce_equal(&aa)?;
320 assert_eq!(aa.value()?, a_squared.value()?);
321 assert_eq!(aa.value()?, a_native.square());
322
323 let a_b2 = &a + b_native;
324 a_b.enforce_equal(&a_b2)?;
325 assert_eq!(a_b.value()?, a_b2.value()?);
326
327 let a_inv = a.inverse()?;
328 a_inv.mul_equals(&a, &one)?;
329 assert_eq!(a_inv.value()?, a.value()?.inverse().unwrap());
330 assert_eq!(a_inv.value()?, a_native.inverse().unwrap());
331
332 let a_b_inv = a.mul_by_inverse(&b)?;
333 a_b_inv.mul_equals(&b, &a)?;
334 assert_eq!(a_b_inv.value()?, a_native * b_native.inverse().unwrap());
335
336 // a * a * a = a^3
337 let bits = BitIteratorLE::without_trailing_zeros([3u64])
338 .map(Boolean::constant)
339 .collect::<Vec<_>>();
340 assert_eq!(a_native.pow([0x3]), a.pow_le(&bits)?.value()?);
341
342 // a * a * a = a^3
343 assert_eq!(a_native.pow([0x3]), a.pow_by_constant(&[0x3])?.value()?);
344 assert!(cs.is_satisfied().unwrap());
345
346 // a * a * a = a^3
347 let mut constants = [F::zero(); 4];
348 for c in &mut constants {
349 *c = UniformRand::rand(&mut test_rng());
350 }
351 let bits = [
352 Boolean::<ConstraintF>::constant(false),
353 Boolean::constant(true),
354 ];
355 let lookup_result = AF::two_bit_lookup(&bits, constants.as_ref())?;
356 assert_eq!(lookup_result.value()?, constants[2]);
357 assert!(cs.is_satisfied().unwrap());
358
359 let f = F::from(1u128 << 64);
360 let f_bits = algebra::BitIteratorLE::new(&[0u64, 1u64]).collect::<Vec<_>>();
361 let fv = AF::new_witness(r1cs_core::ns!(cs, "alloc u128"), || Ok(f))?;
362 assert_eq!(fv.to_bits_le()?.value().unwrap()[..128], f_bits[..128]);
363 assert!(cs.is_satisfied().unwrap());
364
365 let r_native: F = UniformRand::rand(&mut test_rng());
366
367 let r = AF::new_witness(r1cs_core::ns!(cs, "r_native"), || Ok(r_native)).unwrap();
368 let _ = r.to_non_unique_bits_le()?;
369 assert!(cs.is_satisfied().unwrap());
370 let _ = r.to_bits_le()?;
371 assert!(cs.is_satisfied().unwrap());
372
373 let bytes = r.to_non_unique_bytes()?;
374 assert_eq!(
375 algebra::to_bytes!(r_native).unwrap(),
376 bytes.value().unwrap()
377 );
378 assert!(cs.is_satisfied().unwrap());
379 let bytes = r.to_bytes()?;
380 assert_eq!(
381 algebra::to_bytes!(r_native).unwrap(),
382 bytes.value().unwrap()
383 );
384 assert!(cs.is_satisfied().unwrap());
385
386 let ab_false = &a + (AF::from(Boolean::Constant(false)) * b_native);
387 assert_eq!(ab_false.value()?, a_native);
388 let ab_true = &a + (AF::from(Boolean::Constant(true)) * b_native);
389 assert_eq!(ab_true.value()?, a_native + &b_native);
390
391 if !cs.is_satisfied().unwrap() {
392 println!("{:?}", cs.which_is_unsatisfied().unwrap());
393 }
394 assert!(cs.is_satisfied().unwrap());
395 Ok(())
396 }
397
398 #[allow(dead_code)]
399 pub(crate) fn frobenius_tests<F: Field, ConstraintF, AF>(
400 maxpower: usize,
401 ) -> Result<(), SynthesisError>
402 where
403 F: Field,
404 ConstraintF: Field,
405 AF: FieldVar<F, ConstraintF>,
406 for<'a> &'a AF: FieldOpsBounds<'a, F, AF>,
407 {
408 let cs = ConstraintSystem::<ConstraintF>::new_ref();
409 let mut rng = XorShiftRng::seed_from_u64(1231275789u64);
410 for i in 0..=maxpower {
411 let mut a = F::rand(&mut rng);
412 let mut a_gadget = AF::new_witness(r1cs_core::ns!(cs, "a"), || Ok(a))?;
413 a_gadget.frobenius_map_in_place(i)?;
414 a.frobenius_map(i);
415
416 assert_eq!(a_gadget.value()?, a);
417 }
418
419 assert!(cs.is_satisfied().unwrap());
420 Ok(())
421 }
422}