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