1//! This module implements Nova's traits using the following configuration:
  2//! `CommitmentEngine` with Pedersen's commitments
  3//! `Group` with pasta curves and BN256/Grumpkin
  4//! `RO` traits with Poseidon
  5//! `EvaluationEngine` with an IPA-based polynomial evaluation argument
  6
  7pub mod bn256_grumpkin;
  8pub mod ipa_pc;
  9pub mod keccak;
 10pub mod pasta;
 11pub mod pedersen;
 12pub mod poseidon;
 13pub mod poseidon_transcript;
 14
 15use ff::PrimeField;
 16use pasta_curves::{self, arithmetic::CurveAffine, group::Group as AnotherGroup};
 17
 18/// Native implementation of fast multiexp
 19/// Adapted from zcash/halo2
 20fn cpu_multiexp_serial<C: CurveAffine>(coeffs: &[C::Scalar], bases: &[C], acc: &mut C::Curve) {
 21  let coeffs: Vec<_> = coeffs.iter().map(|a| a.to_repr()).collect();
 22
 23  let c = if bases.len() < 4 {
 24    1
 25  } else if bases.len() < 32 {
 26    3
 27  } else {
 28    (f64::from(bases.len() as u32)).ln().ceil() as usize
 29  };
 30
 31  fn get_at<F: PrimeField>(segment: usize, c: usize, bytes: &F::Repr) -> usize {
 32    let skip_bits = segment * c;
 33    let skip_bytes = skip_bits / 8;
 34
 35    if skip_bytes >= 32 {
 36      return 0;
 37    }
 38
 39    let mut v = [0; 8];
 40    for (v, o) in v.iter_mut().zip(bytes.as_ref()[skip_bytes..].iter()) {
 41      *v = *o;
 42    }
 43
 44    let mut tmp = u64::from_le_bytes(v);
 45    tmp >>= skip_bits - (skip_bytes * 8);
 46    tmp %= 1 << c;
 47
 48    tmp as usize
 49  }
 50
 51  let segments = (256 / c) + 1;
 52
 53  for current_segment in (0..segments).rev() {
 54    for _ in 0..c {
 55      *acc = acc.double();
 56    }
 57
 58    #[derive(Clone, Copy)]
 59    enum Bucket<C: CurveAffine> {
 60      None,
 61      Affine(C),
 62      Projective(C::Curve),
 63    }
 64
 65    impl<C: CurveAffine> Bucket<C> {
 66      fn add_assign(&mut self, other: &C) {
 67        *self = match *self {
 68          Bucket::None => Bucket::Affine(*other),
 69          Bucket::Affine(a) => Bucket::Projective(a + *other),
 70          Bucket::Projective(mut a) => {
 71            a += *other;
 72            Bucket::Projective(a)
 73          }
 74        }
 75      }
 76
 77      fn add(self, mut other: C::Curve) -> C::Curve {
 78        match self {
 79          Bucket::None => other,
 80          Bucket::Affine(a) => {
 81            other += a;
 82            other
 83          }
 84          Bucket::Projective(a) => other + a,
 85        }
 86      }
 87    }
 88
 89    let mut buckets: Vec<Bucket<C>> = vec![Bucket::None; (1 << c) - 1];
 90
 91    for (coeff, base) in coeffs.iter().zip(bases.iter()) {
 92      let coeff = get_at::<C::Scalar>(current_segment, c, coeff);
 93      if coeff != 0 {
 94        buckets[coeff - 1].add_assign(base);
 95      }
 96    }
 97
 98    // Summation by parts
 99    // e.g. 3a + 2b + 1c = a +
100    //                    (a) + b +
101    //                    ((a) + b) + c
102    let mut running_sum = C::Curve::identity();
103    for exp in buckets.into_iter().rev() {
104      running_sum = exp.add(running_sum);
105      *acc += &running_sum;
106    }
107  }
108}
109
110/// Performs a multi-exponentiation operation without GPU acceleration.
111///
112/// This function will panic if coeffs and bases have a different length.
113///
114/// This will use multithreading if beneficial.
115/// Adapted from zcash/halo2
116pub(crate) fn cpu_best_multiexp<C: CurveAffine>(coeffs: &[C::Scalar], bases: &[C]) -> C::Curve {
117  assert_eq!(coeffs.len(), bases.len());
118
119  let num_threads = rayon::current_num_threads();
120  if coeffs.len() > num_threads {
121    let chunk = coeffs.len() / num_threads;
122    let num_chunks = coeffs.chunks(chunk).len();
123    let mut results = vec![C::Curve::identity(); num_chunks];
124    rayon::scope(|scope| {
125      for ((coeffs, bases), acc) in coeffs
126        .chunks(chunk)
127        .zip(bases.chunks(chunk))
128        .zip(results.iter_mut())
129      {
130        scope.spawn(move |_| {
131          cpu_multiexp_serial(coeffs, bases, acc);
132        });
133      }
134    });
135    results.iter().fold(C::Curve::identity(), |a, b| a + b)
136  } else {
137    let mut acc = C::Curve::identity();
138    cpu_multiexp_serial(coeffs, bases, &mut acc);
139    acc
140  }
141}