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