Nova/src/provider/bn256_grumpkin.rs
src/provider/bn256_grumpkin.rsRaw
1//! This module implements the Nova traits for bn256::Point, bn256::Scalar, grumpkin::Point, grumpkin::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};
19use rayon::prelude::*;
20use sha3::Shake256;
21use std::io::Read;
22
23use halo2curves::bn256::{
24 G1Affine as Bn256Affine, G1Compressed as Bn256Compressed, G1 as Bn256Point,
25};
26use halo2curves::grumpkin::{
27 G1Affine as GrumpkinAffine, G1Compressed as GrumpkinCompressed, G1 as GrumpkinPoint,
28};
29
30/// Re-exports that give access to the standard aliases used in the code base, for bn256
31pub mod bn256 {
32 pub use halo2curves::bn256::{
33 Fq as Base, Fr as Scalar, G1Affine as Affine, G1Compressed as Compressed, G1 as Point,
34 };
35}
36
37/// Re-exports that give access to the standard aliases used in the code base, for grumpkin
38pub mod grumpkin {
39 pub use halo2curves::grumpkin::{
40 Fq as Base, Fr as Scalar, G1Affine as Affine, G1Compressed as Compressed, G1 as Point,
41 };
42}
43
44// This implementation behaves in ways specific to the bn256/grumpkin curves in:
45// - to_coordinates,
46// - vartime_multiscalar_mul, where it does not call into accelerated implementations.
47macro_rules! impl_traits {
48 (
49 $name:ident,
50 $name_compressed:ident,
51 $name_curve:ident,
52 $name_curve_affine:ident,
53 $order_str:literal
54 ) => {
55 impl Group for $name::Point {
56 type Base = $name::Base;
57 type Scalar = $name::Scalar;
58 type CompressedGroupElement = $name_compressed;
59 type PreprocessedGroupElement = $name::Affine;
60 type RO = PoseidonRO<Self::Base, Self::Scalar>;
61 type ROCircuit = PoseidonROCircuit<Self::Base>;
62 type TE = Keccak256Transcript<Self>;
63 type CE = CommitmentEngine<Self>;
64
65 fn vartime_multiscalar_mul(
66 scalars: &[Self::Scalar],
67 bases: &[Self::PreprocessedGroupElement],
68 ) -> Self {
69 cpu_best_multiexp(scalars, bases)
70 }
71
72 fn preprocessed(&self) -> Self::PreprocessedGroupElement {
73 self.to_affine()
74 }
75
76 fn compress(&self) -> Self::CompressedGroupElement {
77 self.to_bytes()
78 }
79
80 fn from_label(label: &'static [u8], n: usize) -> Vec<Self::PreprocessedGroupElement> {
81 let mut shake = Shake256::default();
82 shake.input(label);
83 let mut reader = shake.xof_result();
84 let mut uniform_bytes_vec = Vec::new();
85 for _ in 0..n {
86 let mut uniform_bytes = [0u8; 32];
87 reader.read_exact(&mut uniform_bytes).unwrap();
88 uniform_bytes_vec.push(uniform_bytes);
89 }
90 let gens_proj: Vec<$name_curve> = (0..n)
91 .collect::<Vec<usize>>()
92 .into_par_iter()
93 .map(|i| {
94 let hash = $name_curve::hash_to_curve("from_uniform_bytes");
95 hash(&uniform_bytes_vec[i])
96 })
97 .collect();
98
99 let num_threads = rayon::current_num_threads();
100 if gens_proj.len() > num_threads {
101 let chunk = (gens_proj.len() as f64 / num_threads as f64).ceil() as usize;
102 (0..num_threads)
103 .collect::<Vec<usize>>()
104 .into_par_iter()
105 .map(|i| {
106 let start = i * chunk;
107 let end = if i == num_threads - 1 {
108 gens_proj.len()
109 } else {
110 core::cmp::min((i + 1) * chunk, gens_proj.len())
111 };
112 if end > start {
113 let mut gens = vec![$name_curve_affine::identity(); end - start];
114 <Self as Curve>::batch_normalize(&gens_proj[start..end], &mut gens);
115 gens
116 } else {
117 vec![]
118 }
119 })
120 .collect::<Vec<Vec<$name_curve_affine>>>()
121 .into_par_iter()
122 .flatten()
123 .collect()
124 } else {
125 let mut gens = vec![$name_curve_affine::identity(); n];
126 <Self as Curve>::batch_normalize(&gens_proj, &mut gens);
127 gens
128 }
129 }
130
131 fn to_coordinates(&self) -> (Self::Base, Self::Base, bool) {
132 let coordinates = self.to_affine().coordinates();
133 if coordinates.is_some().unwrap_u8() == 1
134 // The bn256/grumpkin convention is to define and return the identity point's affine encoding (not None)
135 && (Self::PreprocessedGroupElement::identity() != self.to_affine())
136 {
137 (*coordinates.unwrap().x(), *coordinates.unwrap().y(), false)
138 } else {
139 (Self::Base::zero(), Self::Base::zero(), true)
140 }
141 }
142
143 fn get_curve_params() -> (Self::Base, Self::Base, BigInt) {
144 let A = $name::Point::a();
145 let B = $name::Point::b();
146 let order = BigInt::from_str_radix($order_str, 16).unwrap();
147
148 (A, B, order)
149 }
150
151 fn zero() -> Self {
152 $name::Point::identity()
153 }
154
155 fn get_generator() -> Self {
156 $name::Point::generator()
157 }
158 }
159
160 impl PrimeFieldExt for $name::Scalar {
161 fn from_uniform(bytes: &[u8]) -> Self {
162 let bytes_arr: [u8; 64] = bytes.try_into().unwrap();
163 $name::Scalar::from_uniform_bytes(&bytes_arr)
164 }
165 }
166
167 impl<G: Group> TranscriptReprTrait<G> for $name_compressed {
168 fn to_transcript_bytes(&self) -> Vec<u8> {
169 self.as_ref().to_vec()
170 }
171 }
172
173 impl CompressedGroup for $name_compressed {
174 type GroupElement = $name::Point;
175
176 fn decompress(&self) -> Option<$name::Point> {
177 Some($name_curve::from_bytes(&self).unwrap())
178 }
179 }
180 };
181}
182
183impl<G: Group> TranscriptReprTrait<G> for grumpkin::Base {
184 fn to_transcript_bytes(&self) -> Vec<u8> {
185 self.to_repr().to_vec()
186 }
187}
188
189impl<G: Group> TranscriptReprTrait<G> for grumpkin::Scalar {
190 fn to_transcript_bytes(&self) -> Vec<u8> {
191 self.to_repr().to_vec()
192 }
193}
194
195impl_traits!(
196 bn256,
197 Bn256Compressed,
198 Bn256Point,
199 Bn256Affine,
200 "30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f0000001"
201);
202
203impl_traits!(
204 grumpkin,
205 GrumpkinCompressed,
206 GrumpkinPoint,
207 GrumpkinAffine,
208 "30644e72e131a029b85045b68181585d97816a916871ca8d3c208c16d87cfd47"
209);
210
211/// Performs a multi-exponentiation operation without GPU acceleration.
212///
213/// This function will panic if coeffs and bases have a different length.
214///
215/// This will use multithreading if beneficial.
216/// Adapted from zcash/halo2
217// TODO: update once https://github.com/privacy-scaling-explorations/halo2curves/pull/29
218// (or a successor thereof) is merged
219fn cpu_best_multiexp<C: CurveAffine>(coeffs: &[C::Scalar], bases: &[C]) -> C::Curve {
220 crate::provider::pasta::cpu_best_multiexp(coeffs, bases)
221}
222
223#[cfg(test)]
224mod tests {
225 use super::*;
226 type G = bn256::Point;
227
228 fn from_label_serial(label: &'static [u8], n: usize) -> Vec<Bn256Affine> {
229 let mut shake = Shake256::default();
230 shake.input(label);
231 let mut reader = shake.xof_result();
232 let mut ck = Vec::new();
233 for _ in 0..n {
234 let mut uniform_bytes = [0u8; 32];
235 reader.read_exact(&mut uniform_bytes).unwrap();
236 let hash = bn256::Point::hash_to_curve("from_uniform_bytes");
237 ck.push(hash(&uniform_bytes).to_affine());
238 }
239 ck
240 }
241
242 #[test]
243 fn test_from_label() {
244 let label = b"test_from_label";
245 for n in [
246 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 1021,
247 ] {
248 let ck_par = <G as Group>::from_label(label, n);
249 let ck_ser = from_label_serial(label, n);
250 assert_eq!(ck_par.len(), n);
251 assert_eq!(ck_ser.len(), n);
252 assert_eq!(ck_par, ck_ser);
253 }
254 }
255}