snark_verifier/
loader.rs

Help
1//! Abstraction of field element and elliptic curve point for generic verifier
2//! implementation.
3
4use crate::util::{
5    arithmetic::{CurveAffine, FieldOps, PrimeField},
6    Itertools,
7};
8use std::{borrow::Cow, fmt::Debug, iter, ops::Deref};
9
10/// Native (cpu) loader
11pub mod native;
12
13#[cfg(feature = "loader_evm")]
14/// EVM loader
15pub mod evm;
16
17#[cfg(feature = "loader_halo2")]
18/// Halo2 loader
19pub mod halo2;
20
21/// Loaded elliptic curve point.
22pub trait LoadedEcPoint<C: CurveAffine>: Clone + Debug + PartialEq {
23    /// [`Loader`].
24    type Loader: Loader<C, LoadedEcPoint = Self>;
25
26    /// Returns [`Loader`].
27    fn loader(&self) -> &Self::Loader;
28}
29
30/// Loaded field element.
31pub trait LoadedScalar<F: PrimeField>: Clone + Debug + PartialEq + FieldOps {
32    /// [`Loader`].
33    type Loader: ScalarLoader<F, LoadedScalar = Self>;
34
35    /// Returns [`Loader`].
36    fn loader(&self) -> &Self::Loader;
37
38    /// Returns square.
39    fn square(&self) -> Self {
40        self.clone() * self
41    }
42
43    /// Returns inverse if any.
44    fn invert(&self) -> Option<Self> {
45        FieldOps::invert(self)
46    }
47
48    /// Returns power to exponent.
49    fn pow_const(&self, mut exp: u64) -> Self {
50        assert!(exp > 0);
51
52        let mut base = self.clone();
53
54        while exp & 1 == 0 {
55            base = base.square();
56            exp >>= 1;
57        }
58
59        let mut acc = base.clone();
60        while exp > 1 {
61            exp >>= 1;
62            base = base.square();
63            if exp & 1 == 1 {
64                acc *= &base;
65            }
66        }
67        acc
68    }
69
70    /// Returns power to exponent, where exponent is also [`LoadedScalar`].
71    /// If `Loader` is for Halo2, then `exp` must have at most `exp_max_bits` bits (otherwise constraints will fail).
72    ///
73    /// Currently **unimplemented** for EvmLoader
74    fn pow_var(&self, exp: &Self, exp_max_bits: usize) -> Self;
75
76    /// Returns powers up to exponent `n-1`.
77    fn powers(&self, n: usize) -> Vec<Self> {
78        iter::once(self.loader().load_one())
79            .chain(
80                iter::successors(Some(self.clone()), |power| Some(power.clone() * self))
81                    .take(n - 1),
82            )
83            .collect_vec()
84    }
85}
86
87/// Elliptic curve point loader.
88pub trait EcPointLoader<C: CurveAffine> {
89    /// [`LoadedEcPoint`].
90    type LoadedEcPoint: LoadedEcPoint<C, Loader = Self>;
91
92    /// Load a constant elliptic curve point.
93    fn ec_point_load_const(&self, value: &C) -> Self::LoadedEcPoint;
94
95    /// Load `identity` as constant.
96    fn ec_point_load_zero(&self) -> Self::LoadedEcPoint {
97        self.ec_point_load_const(&C::identity())
98    }
99
100    /// Load `generator` as constant.
101    fn ec_point_load_one(&self) -> Self::LoadedEcPoint {
102        self.ec_point_load_const(&C::generator())
103    }
104
105    /// Assert lhs and rhs elliptic curve points are equal.
106    fn ec_point_assert_eq(
107        &self,
108        annotation: &str,
109        lhs: &Self::LoadedEcPoint,
110        rhs: &Self::LoadedEcPoint,
111    );
112
113    /// Perform multi-scalar multiplication.
114    fn multi_scalar_multiplication(
115        pairs: &[(&Self::LoadedScalar, &Self::LoadedEcPoint)],
116    ) -> Self::LoadedEcPoint
117    where
118        Self: ScalarLoader<C::ScalarExt>;
119}
120
121/// Field element loader.
122pub trait ScalarLoader<F: PrimeField> {
123    /// [`LoadedScalar`].
124    type LoadedScalar: LoadedScalar<F, Loader = Self>;
125
126    /// Load a constant field element.
127    fn load_const(&self, value: &F) -> Self::LoadedScalar;
128
129    /// Load `zero` as constant.
130    fn load_zero(&self) -> Self::LoadedScalar {
131        self.load_const(&F::ZERO)
132    }
133
134    /// Load `one` as constant.
135    fn load_one(&self) -> Self::LoadedScalar {
136        self.load_const(&F::ONE)
137    }
138
139    /// Assert lhs and rhs field elements are equal.
140    fn assert_eq(&self, annotation: &str, lhs: &Self::LoadedScalar, rhs: &Self::LoadedScalar);
141
142    /// Sum field elements with coefficients and constant.
143    fn sum_with_coeff_and_const(
144        &self,
145        values: &[(F, &Self::LoadedScalar)],
146        constant: F,
147    ) -> Self::LoadedScalar {
148        if values.is_empty() {
149            return self.load_const(&constant);
150        }
151
152        let loader = values.first().unwrap().1.loader();
153        iter::empty()
154            .chain(if constant == F::ZERO {
155                None
156            } else {
157                Some(Cow::Owned(loader.load_const(&constant)))
158            })
159            .chain(values.iter().map(|&(coeff, value)| {
160                if coeff == F::ONE {
161                    Cow::Borrowed(value)
162                } else {
163                    Cow::Owned(loader.load_const(&coeff) * value)
164                }
165            }))
166            .reduce(|acc, term| Cow::Owned(acc.into_owned() + term.deref()))
167            .unwrap()
168            .into_owned()
169    }
170
171    /// Sum product of field elements with coefficients and constant.
172    fn sum_products_with_coeff_and_const(
173        &self,
174        values: &[(F, &Self::LoadedScalar, &Self::LoadedScalar)],
175        constant: F,
176    ) -> Self::LoadedScalar {
177        if values.is_empty() {
178            return self.load_const(&constant);
179        }
180
181        let loader = values.first().unwrap().1.loader();
182        iter::empty()
183            .chain(if constant == F::ZERO { None } else { Some(loader.load_const(&constant)) })
184            .chain(values.iter().map(|&(coeff, lhs, rhs)| {
185                if coeff == F::ONE {
186                    lhs.clone() * rhs
187                } else {
188                    loader.load_const(&coeff) * lhs * rhs
189                }
190            }))
191            .reduce(|acc, term| acc + term)
192            .unwrap()
193    }
194
195    /// Sum field elements with coefficients.
196    fn sum_with_coeff(&self, values: &[(F, &Self::LoadedScalar)]) -> Self::LoadedScalar {
197        self.sum_with_coeff_and_const(values, F::ZERO)
198    }
199
200    /// Sum field elements and constant.
201    fn sum_with_const(&self, values: &[&Self::LoadedScalar], constant: F) -> Self::LoadedScalar {
202        self.sum_with_coeff_and_const(
203            &values.iter().map(|&value| (F::ONE, value)).collect_vec(),
204            constant,
205        )
206    }
207
208    /// Sum field elements.
209    fn sum(&self, values: &[&Self::LoadedScalar]) -> Self::LoadedScalar {
210        self.sum_with_const(values, F::ZERO)
211    }
212
213    /// Sum product of field elements with coefficients.
214    fn sum_products_with_coeff(
215        &self,
216        values: &[(F, &Self::LoadedScalar, &Self::LoadedScalar)],
217    ) -> Self::LoadedScalar {
218        self.sum_products_with_coeff_and_const(values, F::ZERO)
219    }
220
221    /// Sum product of field elements and constant.
222    fn sum_products_with_const(
223        &self,
224        values: &[(&Self::LoadedScalar, &Self::LoadedScalar)],
225        constant: F,
226    ) -> Self::LoadedScalar {
227        self.sum_products_with_coeff_and_const(
228            &values.iter().map(|&(lhs, rhs)| (F::ONE, lhs, rhs)).collect_vec(),
229            constant,
230        )
231    }
232
233    /// Sum product of field elements.
234    fn sum_products(
235        &self,
236        values: &[(&Self::LoadedScalar, &Self::LoadedScalar)],
237    ) -> Self::LoadedScalar {
238        self.sum_products_with_const(values, F::ZERO)
239    }
240
241    /// Product of field elements.
242    fn product(&self, values: &[&Self::LoadedScalar]) -> Self::LoadedScalar {
243        values.iter().fold(self.load_one(), |acc, value| acc * *value)
244    }
245
246    /// Batch invert field elements.
247    fn batch_invert<'a>(values: impl IntoIterator<Item = &'a mut Self::LoadedScalar>)
248    where
249        Self::LoadedScalar: 'a,
250    {
251        values
252            .into_iter()
253            .for_each(|value| *value = LoadedScalar::invert(value).unwrap_or_else(|| value.clone()))
254    }
255}
256
257/// [`EcPointLoader`] and [`ScalarLoader`] with some helper methods.
258pub trait Loader<C: CurveAffine>:
259    EcPointLoader<C> + ScalarLoader<C::ScalarExt> + Clone + Debug
260{
261    /// Start cost metering with an `identifier`.
262    fn start_cost_metering(&self, _identifier: &str) {}
263
264    /// End latest started cost metering.
265    fn end_cost_metering(&self) {}
266}
snark_verifier/loader.rs

snark_verifier/
loader.rs
