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, TranscriptReprTrait},
9};
10use digest::{ExtendableOutput, Input};
11use ff::{FromUniformBytes, PrimeField};
12use num_bigint::BigInt;
13use num_traits::Num;
14use pasta_curves::{
15 self,
16 arithmetic::{CurveAffine, CurveExt},
17 group::{cofactor::CofactorCurveAffine, Curve, Group as AnotherGroup, GroupEncoding},
18 pallas, vesta, Ep, EpAffine, Eq, EqAffine,
19};
20use rayon::prelude::*;
21use serde::{Deserialize, Serialize};
22use sha3::Shake256;
23use std::io::Read;
24
25/// A wrapper for compressed group elements of pallas
26#[derive(Clone, Copy, Debug, Eq, PartialEq, Serialize, Deserialize)]
27pub struct PallasCompressedElementWrapper {
28 repr: [u8; 32],
29}
30
31impl PallasCompressedElementWrapper {
32 /// Wraps repr into the wrapper
33 pub fn new(repr: [u8; 32]) -> Self {
34 Self { repr }
35 }
36}
37
38/// A wrapper for compressed group elements of vesta
39#[derive(Clone, Copy, Debug, Eq, PartialEq, Serialize, Deserialize)]
40pub struct VestaCompressedElementWrapper {
41 repr: [u8; 32],
42}
43
44impl VestaCompressedElementWrapper {
45 /// Wraps repr into the wrapper
46 pub fn new(repr: [u8; 32]) -> Self {
47 Self { repr }
48 }
49}
50
51macro_rules! impl_traits {
52 (
53 $name:ident,
54 $name_compressed:ident,
55 $name_curve:ident,
56 $name_curve_affine:ident,
57 $order_str:literal
58 ) => {
59 impl Group for $name::Point {
60 type Base = $name::Base;
61 type Scalar = $name::Scalar;
62 type CompressedGroupElement = $name_compressed;
63 type PreprocessedGroupElement = $name::Affine;
64 type RO = PoseidonRO<Self::Base, Self::Scalar>;
65 type ROCircuit = PoseidonROCircuit<Self::Base>;
66 type TE = Keccak256Transcript<Self>;
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 ck_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 ck_proj.len() > num_threads {
118 let chunk = (ck_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 ck_proj.len()
126 } else {
127 core::cmp::min((i + 1) * chunk, ck_proj.len())
128 };
129 if end > start {
130 let mut ck = vec![$name_curve_affine::identity(); end - start];
131 <Self as Curve>::batch_normalize(&ck_proj[start..end], &mut ck);
132 ck
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 ck = vec![$name_curve_affine::identity(); n];
143 <Self as Curve>::batch_normalize(&ck_proj, &mut ck);
144 ck
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 = $name::Point::a();
159 let B = $name::Point::b();
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::identity()
167 }
168
169 fn get_generator() -> Self {
170 $name::Point::generator()
171 }
172 }
173
174 impl PrimeFieldExt for $name::Scalar {
175 fn from_uniform(bytes: &[u8]) -> Self {
176 let bytes_arr: [u8; 64] = bytes.try_into().unwrap();
177 $name::Scalar::from_uniform_bytes(&bytes_arr)
178 }
179 }
180
181 impl<G: Group> TranscriptReprTrait<G> for $name_compressed {
182 fn to_transcript_bytes(&self) -> Vec<u8> {
183 self.repr.to_vec()
184 }
185 }
186
187 impl CompressedGroup for $name_compressed {
188 type GroupElement = $name::Point;
189
190 fn decompress(&self) -> Option<$name::Point> {
191 Some($name_curve::from_bytes(&self.repr).unwrap())
192 }
193 }
194 };
195}
196
197impl<G: Group> TranscriptReprTrait<G> for pallas::Base {
198 fn to_transcript_bytes(&self) -> Vec<u8> {
199 self.to_repr().to_vec()
200 }
201}
202
203impl<G: Group> TranscriptReprTrait<G> for pallas::Scalar {
204 fn to_transcript_bytes(&self) -> Vec<u8> {
205 self.to_repr().to_vec()
206 }
207}
208
209impl_traits!(
210 pallas,
211 PallasCompressedElementWrapper,
212 Ep,
213 EpAffine,
214 "40000000000000000000000000000000224698fc0994a8dd8c46eb2100000001"
215);
216
217impl_traits!(
218 vesta,
219 VestaCompressedElementWrapper,
220 Eq,
221 EqAffine,
222 "40000000000000000000000000000000224698fc094cf91b992d30ed00000001"
223);
224
225/// Native implementation of fast multiexp for platforms that do not support pasta_msm/semolina
226/// Adapted from zcash/halo2
227fn cpu_multiexp_serial<C: CurveAffine>(coeffs: &[C::Scalar], bases: &[C], acc: &mut C::Curve) {
228 let coeffs: Vec<_> = coeffs.iter().map(|a| a.to_repr()).collect();
229
230 let c = if bases.len() < 4 {
231 1
232 } else if bases.len() < 32 {
233 3
234 } else {
235 (f64::from(bases.len() as u32)).ln().ceil() as usize
236 };
237
238 fn get_at<F: PrimeField>(segment: usize, c: usize, bytes: &F::Repr) -> usize {
239 let skip_bits = segment * c;
240 let skip_bytes = skip_bits / 8;
241
242 if skip_bytes >= 32 {
243 return 0;
244 }
245
246 let mut v = [0; 8];
247 for (v, o) in v.iter_mut().zip(bytes.as_ref()[skip_bytes..].iter()) {
248 *v = *o;
249 }
250
251 let mut tmp = u64::from_le_bytes(v);
252 tmp >>= skip_bits - (skip_bytes * 8);
253 tmp %= 1 << c;
254
255 tmp as usize
256 }
257
258 let segments = (256 / c) + 1;
259
260 for current_segment in (0..segments).rev() {
261 for _ in 0..c {
262 *acc = acc.double();
263 }
264
265 #[derive(Clone, Copy)]
266 enum Bucket<C: CurveAffine> {
267 None,
268 Affine(C),
269 Projective(C::Curve),
270 }
271
272 impl<C: CurveAffine> Bucket<C> {
273 fn add_assign(&mut self, other: &C) {
274 *self = match *self {
275 Bucket::None => Bucket::Affine(*other),
276 Bucket::Affine(a) => Bucket::Projective(a + *other),
277 Bucket::Projective(mut a) => {
278 a += *other;
279 Bucket::Projective(a)
280 }
281 }
282 }
283
284 fn add(self, mut other: C::Curve) -> C::Curve {
285 match self {
286 Bucket::None => other,
287 Bucket::Affine(a) => {
288 other += a;
289 other
290 }
291 Bucket::Projective(a) => other + a,
292 }
293 }
294 }
295
296 let mut buckets: Vec<Bucket<C>> = vec![Bucket::None; (1 << c) - 1];
297
298 for (coeff, base) in coeffs.iter().zip(bases.iter()) {
299 let coeff = get_at::<C::Scalar>(current_segment, c, coeff);
300 if coeff != 0 {
301 buckets[coeff - 1].add_assign(base);
302 }
303 }
304
305 // Summation by parts
306 // e.g. 3a + 2b + 1c = a +
307 // (a) + b +
308 // ((a) + b) + c
309 let mut running_sum = C::Curve::identity();
310 for exp in buckets.into_iter().rev() {
311 running_sum = exp.add(running_sum);
312 *acc += &running_sum;
313 }
314 }
315}
316
317/// Performs a multi-exponentiation operation without GPU acceleration.
318///
319/// This function will panic if coeffs and bases have a different length.
320///
321/// This will use multithreading if beneficial.
322/// Adapted from zcash/halo2
323pub(crate) fn cpu_best_multiexp<C: CurveAffine>(coeffs: &[C::Scalar], bases: &[C]) -> C::Curve {
324 assert_eq!(coeffs.len(), bases.len());
325
326 let num_threads = rayon::current_num_threads();
327 if coeffs.len() > num_threads {
328 let chunk = coeffs.len() / num_threads;
329 let num_chunks = coeffs.chunks(chunk).len();
330 let mut results = vec![C::Curve::identity(); num_chunks];
331 rayon::scope(|scope| {
332 for ((coeffs, bases), acc) in coeffs
333 .chunks(chunk)
334 .zip(bases.chunks(chunk))
335 .zip(results.iter_mut())
336 {
337 scope.spawn(move |_| {
338 cpu_multiexp_serial(coeffs, bases, acc);
339 });
340 }
341 });
342 results.iter().fold(C::Curve::identity(), |a, b| a + b)
343 } else {
344 let mut acc = C::Curve::identity();
345 cpu_multiexp_serial(coeffs, bases, &mut acc);
346 acc
347 }
348}
349
350#[cfg(test)]
351mod tests {
352 use super::*;
353 type G = pasta_curves::pallas::Point;
354
355 fn from_label_serial(label: &'static [u8], n: usize) -> Vec<EpAffine> {
356 let mut shake = Shake256::default();
357 shake.input(label);
358 let mut reader = shake.xof_result();
359 let mut ck = Vec::new();
360 for _ in 0..n {
361 let mut uniform_bytes = [0u8; 32];
362 reader.read_exact(&mut uniform_bytes).unwrap();
363 let hash = Ep::hash_to_curve("from_uniform_bytes");
364 ck.push(hash(&uniform_bytes).to_affine());
365 }
366 ck
367 }
368
369 #[test]
370 fn test_from_label() {
371 let label = b"test_from_label";
372 for n in [
373 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 1021,
374 ] {
375 let ck_par = <G as Group>::from_label(label, n);
376 let ck_ser = from_label_serial(label, n);
377 assert_eq!(ck_par.len(), n);
378 assert_eq!(ck_ser.len(), n);
379 assert_eq!(ck_par, ck_ser);
380 }
381 }
382}