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