ark-r1cs-std/src/fields/mod.rs
src/fields/mod.rsRaw
1use ark_ff::{prelude::*, BitIteratorBE};
2use ark_relations::r1cs::{ConstraintSystemRef, SynthesisError};
3use core::{
4 fmt::Debug,
5 ops::{Add, AddAssign, Mul, MulAssign, Sub, SubAssign},
6};
7
8use crate::convert::{ToBitsGadget, ToBytesGadget, ToConstraintFieldGadget};
9use crate::prelude::*;
10
11/// This module contains a generic implementation of cubic extension field
12/// variables. That is, it implements the R1CS equivalent of
13/// `ark_ff::CubicExtField`.
14pub mod cubic_extension;
15/// This module contains a generic implementation of quadratic extension field
16/// variables. That is, it implements the R1CS equivalent of
17/// `ark_ff::QuadExtField`.
18pub mod quadratic_extension;
19
20/// This module contains a generic implementation of prime field variables.
21/// That is, it implements the R1CS equivalent of `ark_ff::Fp*`.
22pub mod fp;
23
24/// This module contains a generic implementation of "emulated" prime field
25/// variables. It emulates `Fp` arithmetic using `Fq` operations, where `p != q`.
26pub mod emulated_fp;
27
28/// This module contains a generic implementation of the degree-12 tower
29/// extension field. That is, it implements the R1CS equivalent of
30/// `ark_ff::Fp12`
31pub mod fp12;
32/// This module contains a generic implementation of the degree-2 tower
33/// extension field. That is, it implements the R1CS equivalent of
34/// `ark_ff::Fp2`
35pub mod fp2;
36/// This module contains a generic implementation of the degree-3 tower
37/// extension field. That is, it implements the R1CS equivalent of
38/// `ark_ff::Fp3`
39pub mod fp3;
40/// This module contains a generic implementation of the degree-4 tower
41/// extension field. That is, it implements the R1CS equivalent of
42/// `ark_ff::Fp4`
43pub mod fp4;
44/// This module contains a generic implementation of the degree-6 tower
45/// extension field. That is, it implements the R1CS equivalent of
46/// `ark_ff::fp6_2over3::Fp6`
47pub mod fp6_2over3;
48/// This module contains a generic implementation of the degree-6 tower
49/// extension field. That is, it implements the R1CS equivalent of
50/// `ark_ff::fp6_3over2::Fp6`
51pub mod fp6_3over2;
52
53/// This trait is a hack used to work around the lack of implied bounds.
54pub trait FieldOpsBounds<'a, F, T: 'a>:
55 Sized
56 + Add<&'a T, Output = T>
57 + Sub<&'a T, Output = T>
58 + Mul<&'a T, Output = T>
59 + Add<T, Output = T>
60 + Sub<T, Output = T>
61 + Mul<T, Output = T>
62 + Add<F, Output = T>
63 + Sub<F, Output = T>
64 + Mul<F, Output = T>
65{
66}
67
68/// A variable representing a field. Corresponds to the native type `F`.
69pub trait FieldVar<F: Field, ConstraintF: PrimeField>:
70 'static
71 + Clone
72 + From<Boolean<ConstraintF>>
73 + R1CSVar<ConstraintF, Value = F>
74 + EqGadget<ConstraintF>
75 + ToBitsGadget<ConstraintF>
76 + AllocVar<F, ConstraintF>
77 + ToBytesGadget<ConstraintF>
78 + CondSelectGadget<ConstraintF>
79 + ToConstraintFieldGadget<ConstraintF>
80 + for<'a> FieldOpsBounds<'a, F, Self>
81 + for<'a> AddAssign<&'a Self>
82 + for<'a> SubAssign<&'a Self>
83 + for<'a> MulAssign<&'a Self>
84 + AddAssign<Self>
85 + SubAssign<Self>
86 + MulAssign<Self>
87 + AddAssign<F>
88 + SubAssign<F>
89 + MulAssign<F>
90 + Debug
91{
92 /// Returns the constant `F::zero()`.
93 fn zero() -> Self;
94
95 /// Returns a `Boolean` representing whether `self == Self::zero()`.
96 fn is_zero(&self) -> Result<Boolean<ConstraintF>, SynthesisError> {
97 self.is_eq(&Self::zero())
98 }
99
100 /// Returns the constant `F::one()`.
101 fn one() -> Self;
102
103 /// Returns a `Boolean` representing whether `self == Self::one()`.
104 fn is_one(&self) -> Result<Boolean<ConstraintF>, SynthesisError> {
105 self.is_eq(&Self::one())
106 }
107
108 /// Returns a constant with value `v`.
109 ///
110 /// This *should not* allocate any variables.
111 fn constant(v: F) -> Self;
112
113 /// Computes `self + self`.
114 fn double(&self) -> Result<Self, SynthesisError> {
115 Ok(self.clone() + self)
116 }
117
118 /// Sets `self = self + self`.
119 fn double_in_place(&mut self) -> Result<&mut Self, SynthesisError> {
120 *self += self.double()?;
121 Ok(self)
122 }
123
124 /// Coputes `-self`.
125 fn negate(&self) -> Result<Self, SynthesisError>;
126
127 /// Sets `self = -self`.
128 #[inline]
129 fn negate_in_place(&mut self) -> Result<&mut Self, SynthesisError> {
130 *self = self.negate()?;
131 Ok(self)
132 }
133
134 /// Computes `self * self`.
135 ///
136 /// A default implementation is provided which just invokes the underlying
137 /// multiplication routine. However, this method should be specialized
138 /// for extension fields, where faster algorithms exist for squaring.
139 fn square(&self) -> Result<Self, SynthesisError> {
140 Ok(self.clone() * self)
141 }
142
143 /// Sets `self = self.square()`.
144 fn square_in_place(&mut self) -> Result<&mut Self, SynthesisError> {
145 *self = self.square()?;
146 Ok(self)
147 }
148
149 /// Enforces that `self * other == result`.
150 fn mul_equals(&self, other: &Self, result: &Self) -> Result<(), SynthesisError> {
151 let actual_result = self.clone() * other;
152 result.enforce_equal(&actual_result)
153 }
154
155 /// Enforces that `self * self == result`.
156 fn square_equals(&self, result: &Self) -> Result<(), SynthesisError> {
157 let actual_result = self.square()?;
158 result.enforce_equal(&actual_result)
159 }
160
161 /// Computes `result` such that `self * result == Self::one()`.
162 fn inverse(&self) -> Result<Self, SynthesisError>;
163
164 /// Returns `(self / d)`.
165 /// The constraint system will be unsatisfiable when `d = 0`.
166 fn mul_by_inverse(&self, d: &Self) -> Result<Self, SynthesisError> {
167 // Enforce that `d` is not zero.
168 d.enforce_not_equal(&Self::zero())?;
169 self.mul_by_inverse_unchecked(d)
170 }
171
172 /// Returns `(self / d)`.
173 ///
174 /// The precondition for this method is that `d != 0`. If `d == 0`, this
175 /// method offers no guarantees about the soundness of the resulting
176 /// constraint system. For example, if `self == d == 0`, the current
177 /// implementation allows the constraint system to be trivially satisfiable.
178 fn mul_by_inverse_unchecked(&self, d: &Self) -> Result<Self, SynthesisError> {
179 let cs = self.cs().or(d.cs());
180 match cs {
181 // If we're in the constant case, we just allocate a new constant having value equalling
182 // `self * d.inverse()`.
183 ConstraintSystemRef::None => Self::new_constant(
184 cs,
185 self.value()? * d.value()?.inverse().expect("division by zero"),
186 ),
187 // If not, we allocate `result` as a new witness having value `self * d.inverse()`,
188 // and check that `result * d = self`.
189 _ => {
190 let result = Self::new_witness(ark_relations::ns!(cs, "self * d_inv"), || {
191 Ok(self.value()? * &d.value()?.inverse().unwrap_or(F::zero()))
192 })?;
193 result.mul_equals(d, self)?;
194 Ok(result)
195 },
196 }
197 }
198
199 /// Computes the frobenius map over `self`.
200 fn frobenius_map(&self, power: usize) -> Result<Self, SynthesisError>;
201
202 /// Sets `self = self.frobenius_map()`.
203 fn frobenius_map_in_place(&mut self, power: usize) -> Result<&mut Self, SynthesisError> {
204 *self = self.frobenius_map(power)?;
205 Ok(self)
206 }
207
208 /// Comptues `self^bits`, where `bits` is a *little-endian* bit-wise
209 /// decomposition of the exponent.
210 fn pow_le(&self, bits: &[Boolean<ConstraintF>]) -> Result<Self, SynthesisError> {
211 let mut res = Self::one();
212 let mut power = self.clone();
213 for bit in bits {
214 let tmp = res.clone() * &power;
215 res = bit.select(&tmp, &res)?;
216 power.square_in_place()?;
217 }
218 Ok(res)
219 }
220
221 /// Computes `self^S`, where S is interpreted as an little-endian
222 /// u64-decomposition of an integer.
223 fn pow_by_constant<S: AsRef<[u64]>>(&self, exp: S) -> Result<Self, SynthesisError> {
224 let mut res = Self::one();
225 for i in BitIteratorBE::without_leading_zeros(exp) {
226 res.square_in_place()?;
227 if i {
228 res *= self;
229 }
230 }
231 Ok(res)
232 }
233}