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