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 cpu_best_multiexp,
5 keccak::Keccak256Transcript,
6 pedersen::CommitmentEngine,
7 poseidon::{PoseidonRO, PoseidonROCircuit},
8 },
9 traits::{CompressedGroup, Group, PrimeFieldExt, TranscriptReprTrait},
10};
11use digest::{ExtendableOutput, Update};
12use ff::{FromUniformBytes, PrimeField};
13use num_bigint::BigInt;
14use num_traits::Num;
15use pasta_curves::{
16 self,
17 arithmetic::{CurveAffine, CurveExt},
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.update(label);
101 let mut reader = shake.finalize_xof();
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 ck_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 ck_proj.len() > num_threads {
119 let chunk = (ck_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 ck_proj.len()
127 } else {
128 core::cmp::min((i + 1) * chunk, ck_proj.len())
129 };
130 if end > start {
131 let mut ck = vec![$name_curve_affine::identity(); end - start];
132 <Self as Curve>::batch_normalize(&ck_proj[start..end], &mut ck);
133 ck
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 ck = vec![$name_curve_affine::identity(); n];
144 <Self as Curve>::batch_normalize(&ck_proj, &mut ck);
145 ck
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 = $name::Point::a();
160 let B = $name::Point::b();
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::identity()
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_uniform_bytes(&bytes_arr)
179 }
180 }
181
182 impl<G: Group> TranscriptReprTrait<G> for $name_compressed {
183 fn to_transcript_bytes(&self) -> Vec<u8> {
184 self.repr.to_vec()
185 }
186 }
187
188 impl CompressedGroup for $name_compressed {
189 type GroupElement = $name::Point;
190
191 fn decompress(&self) -> Option<$name::Point> {
192 Some($name_curve::from_bytes(&self.repr).unwrap())
193 }
194 }
195 };
196}
197
198impl<G: Group> TranscriptReprTrait<G> for pallas::Base {
199 fn to_transcript_bytes(&self) -> Vec<u8> {
200 self.to_repr().to_vec()
201 }
202}
203
204impl<G: Group> TranscriptReprTrait<G> for pallas::Scalar {
205 fn to_transcript_bytes(&self) -> Vec<u8> {
206 self.to_repr().to_vec()
207 }
208}
209
210impl_traits!(
211 pallas,
212 PallasCompressedElementWrapper,
213 Ep,
214 EpAffine,
215 "40000000000000000000000000000000224698fc0994a8dd8c46eb2100000001"
216);
217
218impl_traits!(
219 vesta,
220 VestaCompressedElementWrapper,
221 Eq,
222 EqAffine,
223 "40000000000000000000000000000000224698fc094cf91b992d30ed00000001"
224);
225
226#[cfg(test)]
227mod tests {
228 use super::*;
229 type G = pasta_curves::pallas::Point;
230
231 fn from_label_serial(label: &'static [u8], n: usize) -> Vec<EpAffine> {
232 let mut shake = Shake256::default();
233 shake.update(label);
234 let mut reader = shake.finalize_xof();
235 let mut ck = Vec::new();
236 for _ in 0..n {
237 let mut uniform_bytes = [0u8; 32];
238 reader.read_exact(&mut uniform_bytes).unwrap();
239 let hash = Ep::hash_to_curve("from_uniform_bytes");
240 ck.push(hash(&uniform_bytes).to_affine());
241 }
242 ck
243 }
244
245 #[test]
246 fn test_from_label() {
247 let label = b"test_from_label";
248 for n in [
249 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 1021,
250 ] {
251 let ck_par = <G as Group>::from_label(label, n);
252 let ck_ser = from_label_serial(label, n);
253 assert_eq!(ck_par.len(), n);
254 assert_eq!(ck_ser.len(), n);
255 assert_eq!(ck_par, ck_ser);
256 }
257 }
258}