Nova/src/provider/pasta.rs
src/provider/pasta.rsRaw
1//! This module implements the Nova traits for pallas::Point, pallas::Scalar, vesta::Point, vesta::Scalar.
2use crate::{
3 provider::{
4 keccak::Keccak256Transcript,
5 pedersen::CommitmentEngine,
6 poseidon::{PoseidonRO, PoseidonROCircuit},
7 },
8 traits::{CompressedGroup, Group, PrimeFieldExt},
9};
10use digest::{ExtendableOutput, Input};
11use num_bigint::BigInt;
12use num_traits::Num;
13use pasta_curves::{
14 self,
15 arithmetic::{CurveAffine, CurveExt, FieldExt, Group as OtherGroup},
16 group::{cofactor::CofactorCurveAffine, Curve, Group as AnotherGroup, GroupEncoding},
17 pallas, vesta, Ep, EpAffine, Eq, EqAffine,
18};
19use rayon::prelude::*;
20use serde::{Deserialize, Serialize};
21use sha3::Shake256;
22use std::io::Read;
23
24/// A wrapper for compressed group elements of pallas
25#[derive(Clone, Copy, Debug, Eq, PartialEq, Serialize, Deserialize)]
26pub struct PallasCompressedElementWrapper {
27 repr: [u8; 32],
28}
29
30impl PallasCompressedElementWrapper {
31 /// Wraps repr into the wrapper
32 pub fn new(repr: [u8; 32]) -> Self {
33 Self { repr }
34 }
35}
36
37/// A wrapper for compressed group elements of vesta
38#[derive(Clone, Copy, Debug, Eq, PartialEq, Serialize, Deserialize)]
39pub struct VestaCompressedElementWrapper {
40 repr: [u8; 32],
41}
42
43impl VestaCompressedElementWrapper {
44 /// Wraps repr into the wrapper
45 pub fn new(repr: [u8; 32]) -> Self {
46 Self { repr }
47 }
48}
49
50macro_rules! impl_traits {
51 (
52 $name:ident,
53 $name_compressed:ident,
54 $name_curve:ident,
55 $name_curve_affine:ident,
56 $order_str:literal
57 ) => {
58 impl Group for $name::Point {
59 type Base = $name::Base;
60 type Scalar = $name::Scalar;
61 type CompressedGroupElement = $name_compressed;
62 type PreprocessedGroupElement = $name::Affine;
63 type RO = PoseidonRO<Self::Base, Self::Scalar>;
64 type ROCircuit = PoseidonROCircuit<Self::Base>;
65 type TE = Keccak256Transcript<Self>;
66 type CE = CommitmentEngine<Self>;
67
68 #[cfg(any(target_arch = "x86_64", target_arch = "aarch64"))]
69 fn vartime_multiscalar_mul(
70 scalars: &[Self::Scalar],
71 bases: &[Self::PreprocessedGroupElement],
72 ) -> Self {
73 if scalars.len() >= 128 {
74 pasta_msm::$name(bases, scalars)
75 } else {
76 cpu_best_multiexp(scalars, bases)
77 }
78 }
79
80 #[cfg(not(any(target_arch = "x86_64", target_arch = "aarch64")))]
81 fn vartime_multiscalar_mul(
82 scalars: &[Self::Scalar],
83 bases: &[Self::PreprocessedGroupElement],
84 ) -> Self {
85 cpu_best_multiexp(scalars, bases)
86 }
87
88 fn preprocessed(&self) -> Self::PreprocessedGroupElement {
89 self.to_affine()
90 }
91
92 fn compress(&self) -> Self::CompressedGroupElement {
93 $name_compressed::new(self.to_bytes())
94 }
95
96 fn from_label(label: &'static [u8], n: usize) -> Vec<Self::PreprocessedGroupElement> {
97 let mut shake = Shake256::default();
98 shake.input(label);
99 let mut reader = shake.xof_result();
100 let mut uniform_bytes_vec = Vec::new();
101 for _ in 0..n {
102 let mut uniform_bytes = [0u8; 32];
103 reader.read_exact(&mut uniform_bytes).unwrap();
104 uniform_bytes_vec.push(uniform_bytes);
105 }
106 let gens_proj: Vec<$name_curve> = (0..n)
107 .collect::<Vec<usize>>()
108 .into_par_iter()
109 .map(|i| {
110 let hash = $name_curve::hash_to_curve("from_uniform_bytes");
111 hash(&uniform_bytes_vec[i])
112 })
113 .collect();
114
115 let num_threads = rayon::current_num_threads();
116 if gens_proj.len() > num_threads {
117 let chunk = (gens_proj.len() as f64 / num_threads as f64).ceil() as usize;
118 (0..num_threads)
119 .collect::<Vec<usize>>()
120 .into_par_iter()
121 .map(|i| {
122 let start = i * chunk;
123 let end = if i == num_threads - 1 {
124 gens_proj.len()
125 } else {
126 core::cmp::min((i + 1) * chunk, gens_proj.len())
127 };
128 if end > start {
129 let mut gens = vec![$name_curve_affine::identity(); end - start];
130 <Self as Curve>::batch_normalize(&gens_proj[start..end], &mut gens);
131 gens
132 } else {
133 vec![]
134 }
135 })
136 .collect::<Vec<Vec<$name_curve_affine>>>()
137 .into_par_iter()
138 .flatten()
139 .collect()
140 } else {
141 let mut gens = vec![$name_curve_affine::identity(); n];
142 <Self as Curve>::batch_normalize(&gens_proj, &mut gens);
143 gens
144 }
145 }
146
147 fn to_coordinates(&self) -> (Self::Base, Self::Base, bool) {
148 let coordinates = self.to_affine().coordinates();
149 if coordinates.is_some().unwrap_u8() == 1 {
150 (*coordinates.unwrap().x(), *coordinates.unwrap().y(), false)
151 } else {
152 (Self::Base::zero(), Self::Base::zero(), true)
153 }
154 }
155
156 fn get_curve_params() -> (Self::Base, Self::Base, BigInt) {
157 let A = Self::Base::zero();
158 let B = Self::Base::from(5);
159 let order = BigInt::from_str_radix($order_str, 16).unwrap();
160
161 (A, B, order)
162 }
163
164 fn zero() -> Self {
165 $name::Point::group_zero()
166 }
167
168 fn get_generator() -> Self {
169 $name::Point::generator()
170 }
171 }
172
173 impl PrimeFieldExt for $name::Scalar {
174 fn from_uniform(bytes: &[u8]) -> Self {
175 let bytes_arr: [u8; 64] = bytes.try_into().unwrap();
176 $name::Scalar::from_bytes_wide(&bytes_arr)
177 }
178 }
179
180 impl CompressedGroup for $name_compressed {
181 type GroupElement = $name::Point;
182
183 fn decompress(&self) -> Option<$name::Point> {
184 Some($name_curve::from_bytes(&self.repr).unwrap())
185 }
186
187 fn as_bytes(&self) -> &[u8] {
188 &self.repr
189 }
190 }
191 };
192}
193
194impl_traits!(
195 pallas,
196 PallasCompressedElementWrapper,
197 Ep,
198 EpAffine,
199 "40000000000000000000000000000000224698fc0994a8dd8c46eb2100000001"
200);
201
202impl_traits!(
203 vesta,
204 VestaCompressedElementWrapper,
205 Eq,
206 EqAffine,
207 "40000000000000000000000000000000224698fc094cf91b992d30ed00000001"
208);
209
210/// Native implementation of fast multiexp for platforms that do not support pasta_msm/semolina
211/// Adapted from zcash/halo2
212fn cpu_multiexp_serial<C: CurveAffine>(coeffs: &[C::Scalar], bases: &[C], acc: &mut C::Curve) {
213 use ff::PrimeField;
214 let coeffs: Vec<_> = coeffs.iter().map(|a| a.to_repr()).collect();
215
216 let c = if bases.len() < 4 {
217 1
218 } else if bases.len() < 32 {
219 3
220 } else {
221 (f64::from(bases.len() as u32)).ln().ceil() as usize
222 };
223
224 fn get_at<F: PrimeField>(segment: usize, c: usize, bytes: &F::Repr) -> usize {
225 let skip_bits = segment * c;
226 let skip_bytes = skip_bits / 8;
227
228 if skip_bytes >= 32 {
229 return 0;
230 }
231
232 let mut v = [0; 8];
233 for (v, o) in v.iter_mut().zip(bytes.as_ref()[skip_bytes..].iter()) {
234 *v = *o;
235 }
236
237 let mut tmp = u64::from_le_bytes(v);
238 tmp >>= skip_bits - (skip_bytes * 8);
239 tmp %= 1 << c;
240
241 tmp as usize
242 }
243
244 let segments = (256 / c) + 1;
245
246 for current_segment in (0..segments).rev() {
247 for _ in 0..c {
248 *acc = acc.double();
249 }
250
251 #[derive(Clone, Copy)]
252 enum Bucket<C: CurveAffine> {
253 None,
254 Affine(C),
255 Projective(C::Curve),
256 }
257
258 impl<C: CurveAffine> Bucket<C> {
259 fn add_assign(&mut self, other: &C) {
260 *self = match *self {
261 Bucket::None => Bucket::Affine(*other),
262 Bucket::Affine(a) => Bucket::Projective(a + *other),
263 Bucket::Projective(mut a) => {
264 a += *other;
265 Bucket::Projective(a)
266 }
267 }
268 }
269
270 fn add(self, mut other: C::Curve) -> C::Curve {
271 match self {
272 Bucket::None => other,
273 Bucket::Affine(a) => {
274 other += a;
275 other
276 }
277 Bucket::Projective(a) => other + a,
278 }
279 }
280 }
281
282 let mut buckets: Vec<Bucket<C>> = vec![Bucket::None; (1 << c) - 1];
283
284 for (coeff, base) in coeffs.iter().zip(bases.iter()) {
285 let coeff = get_at::<C::Scalar>(current_segment, c, coeff);
286 if coeff != 0 {
287 buckets[coeff - 1].add_assign(base);
288 }
289 }
290
291 // Summation by parts
292 // e.g. 3a + 2b + 1c = a +
293 // (a) + b +
294 // ((a) + b) + c
295 let mut running_sum = C::Curve::identity();
296 for exp in buckets.into_iter().rev() {
297 running_sum = exp.add(running_sum);
298 *acc += &running_sum;
299 }
300 }
301}
302
303/// Performs a multi-exponentiation operation without GPU acceleration.
304///
305/// This function will panic if coeffs and bases have a different length.
306///
307/// This will use multithreading if beneficial.
308/// Adapted from zcash/halo2
309fn cpu_best_multiexp<C: CurveAffine>(coeffs: &[C::Scalar], bases: &[C]) -> C::Curve {
310 assert_eq!(coeffs.len(), bases.len());
311
312 let num_threads = rayon::current_num_threads();
313 if coeffs.len() > num_threads {
314 let chunk = coeffs.len() / num_threads;
315 let num_chunks = coeffs.chunks(chunk).len();
316 let mut results = vec![C::Curve::identity(); num_chunks];
317 rayon::scope(|scope| {
318 for ((coeffs, bases), acc) in coeffs
319 .chunks(chunk)
320 .zip(bases.chunks(chunk))
321 .zip(results.iter_mut())
322 {
323 scope.spawn(move |_| {
324 cpu_multiexp_serial(coeffs, bases, acc);
325 });
326 }
327 });
328 results.iter().fold(C::Curve::identity(), |a, b| a + b)
329 } else {
330 let mut acc = C::Curve::identity();
331 cpu_multiexp_serial(coeffs, bases, &mut acc);
332 acc
333 }
334}
335
336#[cfg(test)]
337mod tests {
338 use super::*;
339 type G = pasta_curves::pallas::Point;
340
341 fn from_label_serial(label: &'static [u8], n: usize) -> Vec<EpAffine> {
342 let mut shake = Shake256::default();
343 shake.input(label);
344 let mut reader = shake.xof_result();
345 let mut gens = Vec::new();
346 for _ in 0..n {
347 let mut uniform_bytes = [0u8; 32];
348 reader.read_exact(&mut uniform_bytes).unwrap();
349 let hash = Ep::hash_to_curve("from_uniform_bytes");
350 gens.push(hash(&uniform_bytes).to_affine());
351 }
352 gens
353 }
354
355 #[test]
356 fn test_from_label() {
357 let label = b"test_from_label";
358 for n in [
359 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 1021,
360 ] {
361 let gens_par = <G as Group>::from_label(label, n);
362 let gens_ser = from_label_serial(label, n);
363 assert_eq!(gens_par.len(), n);
364 assert_eq!(gens_ser.len(), n);
365 assert_eq!(gens_par, gens_ser);
366 }
367 }
368}