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