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