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