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