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};
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 + for<'a> FieldOpsBounds<'a, F, Self>
80 + for<'a> AddAssign<&'a Self>
81 + for<'a> SubAssign<&'a Self>
82 + for<'a> MulAssign<&'a Self>
83 + AddAssign<Self>
84 + SubAssign<Self>
85 + MulAssign<Self>
86 + AddAssign<F>
87 + SubAssign<F>
88 + MulAssign<F>
89 + Debug
90{
91 /// Returns the constant `F::zero()`.
92 fn zero() -> Self;
93
94 /// Returns a `Boolean` representing whether `self == Self::zero()`.
95 fn is_zero(&self) -> Result<Boolean<ConstraintF>, SynthesisError> {
96 self.is_eq(&Self::zero())
97 }
98
99 /// Returns the constant `F::one()`.
100 fn one() -> Self;
101
102 /// Returns a `Boolean` representing whether `self == Self::one()`.
103 fn is_one(&self) -> Result<Boolean<ConstraintF>, SynthesisError> {
104 self.is_eq(&Self::one())
105 }
106
107 /// Returns a constant with value `v`.
108 ///
109 /// This *should not* allocate any variables.
110 fn constant(v: F) -> Self;
111
112 /// Computes `self + self`.
113 fn double(&self) -> Result<Self, SynthesisError> {
114 Ok(self.clone() + self)
115 }
116
117 /// Sets `self = self + self`.
118 fn double_in_place(&mut self) -> Result<&mut Self, SynthesisError> {
119 *self += self.double()?;
120 Ok(self)
121 }
122
123 /// Coputes `-self`.
124 fn negate(&self) -> Result<Self, SynthesisError>;
125
126 /// Sets `self = -self`.
127 #[inline]
128 fn negate_in_place(&mut self) -> Result<&mut Self, SynthesisError> {
129 *self = self.negate()?;
130 Ok(self)
131 }
132
133 /// Computes `self * self`.
134 ///
135 /// A default implementation is provided which just invokes the underlying
136 /// multiplication routine. However, this method should be specialized
137 /// for extension fields, where faster algorithms exist for squaring.
138 fn square(&self) -> Result<Self, SynthesisError> {
139 Ok(self.clone() * self)
140 }
141
142 /// Sets `self = self.square()`.
143 fn square_in_place(&mut self) -> Result<&mut Self, SynthesisError> {
144 *self = self.square()?;
145 Ok(self)
146 }
147
148 /// Enforces that `self * other == result`.
149 fn mul_equals(&self, other: &Self, result: &Self) -> Result<(), SynthesisError> {
150 let actual_result = self.clone() * other;
151 result.enforce_equal(&actual_result)
152 }
153
154 /// Enforces that `self * self == result`.
155 fn square_equals(&self, result: &Self) -> Result<(), SynthesisError> {
156 let actual_result = self.square()?;
157 result.enforce_equal(&actual_result)
158 }
159
160 /// Computes `result` such that `self * result == Self::one()`.
161 fn inverse(&self) -> Result<Self, SynthesisError>;
162
163 /// Returns `(self / d)`.
164 /// The constraint system will be unsatisfiable when `d = 0`.
165 fn mul_by_inverse(&self, d: &Self) -> Result<Self, SynthesisError> {
166 // Enforce that `d` is not zero.
167 d.enforce_not_equal(&Self::zero())?;
168 self.mul_by_inverse_unchecked(d)
169 }
170
171 /// Returns `(self / d)`.
172 ///
173 /// The precondition for this method is that `d != 0`. If `d == 0`, this
174 /// method offers no guarantees about the soundness of the resulting
175 /// constraint system. For example, if `self == d == 0`, the current
176 /// implementation allows the constraint system to be trivially satisfiable.
177 fn mul_by_inverse_unchecked(&self, d: &Self) -> Result<Self, SynthesisError> {
178 let cs = self.cs().or(d.cs());
179 match cs {
180 // If we're in the constant case, we just allocate a new constant having value equalling
181 // `self * d.inverse()`.
182 ConstraintSystemRef::None => Self::new_constant(
183 cs,
184 self.value()? * d.value()?.inverse().expect("division by zero"),
185 ),
186 // If not, we allocate `result` as a new witness having value `self * d.inverse()`,
187 // and check that `result * d = self`.
188 _ => {
189 let result = Self::new_witness(ark_relations::ns!(cs, "self * d_inv"), || {
190 Ok(self.value()? * &d.value()?.inverse().unwrap_or(F::zero()))
191 })?;
192 result.mul_equals(d, self)?;
193 Ok(result)
194 },
195 }
196 }
197
198 /// Computes the frobenius map over `self`.
199 fn frobenius_map(&self, power: usize) -> Result<Self, SynthesisError>;
200
201 /// Sets `self = self.frobenius_map()`.
202 fn frobenius_map_in_place(&mut self, power: usize) -> Result<&mut Self, SynthesisError> {
203 *self = self.frobenius_map(power)?;
204 Ok(self)
205 }
206
207 /// Comptues `self^bits`, where `bits` is a *little-endian* bit-wise
208 /// decomposition of the exponent.
209 fn pow_le(&self, bits: &[Boolean<ConstraintF>]) -> Result<Self, SynthesisError> {
210 let mut res = Self::one();
211 let mut power = self.clone();
212 for bit in bits {
213 let tmp = res.clone() * &power;
214 res = bit.select(&tmp, &res)?;
215 power.square_in_place()?;
216 }
217 Ok(res)
218 }
219
220 /// Computes `self^S`, where S is interpreted as an little-endian
221 /// u64-decomposition of an integer.
222 fn pow_by_constant<S: AsRef<[u64]>>(&self, exp: S) -> Result<Self, SynthesisError> {
223 let mut res = Self::one();
224 for i in BitIteratorBE::without_leading_zeros(exp) {
225 res.square_in_place()?;
226 if i {
227 res *= self;
228 }
229 }
230 Ok(res)
231 }
232}