1//! This module implements RelaxedR1CSSNARKTrait using Spartan that is generic
  2//! over the polynomial commitment and evaluation argument (i.e., a PCS)
  3//! We provide two implementations, one in snark.rs (which does not use any preprocessing)
  4//! and another in ppsnark.rs (which uses preprocessing to keep the verifier's state small if the PCS scheme provides a succinct verifier)
  5//! We also provide direct.rs that allows proving a step circuit directly with either of the two SNARKs.
  6pub mod direct;
  7mod math;
  8pub(crate) mod polynomial;
  9pub mod ppsnark;
 10pub mod snark;
 11mod sumcheck;
 12
 13use crate::{traits::Group, Commitment};
 14use ff::Field;
 15use polynomial::SparsePolynomial;
 16
 17fn powers<G: Group>(s: &G::Scalar, n: usize) -> Vec<G::Scalar> {
 18  assert!(n >= 1);
 19  let mut powers = Vec::new();
 20  powers.push(G::Scalar::ONE);
 21  for i in 1..n {
 22    powers.push(powers[i - 1] * s);
 23  }
 24  powers
 25}
 26
 27/// A type that holds a witness to a polynomial evaluation instance
 28pub struct PolyEvalWitness<G: Group> {
 29  p: Vec<G::Scalar>, // polynomial
 30}
 31
 32impl<G: Group> PolyEvalWitness<G> {
 33  fn pad(W: &[PolyEvalWitness<G>]) -> Vec<PolyEvalWitness<G>> {
 34    // determine the maximum size
 35    if let Some(n) = W.iter().map(|w| w.p.len()).max() {
 36      W.iter()
 37        .map(|w| {
 38          let mut p = w.p.clone();
 39          p.resize(n, G::Scalar::ZERO);
 40          PolyEvalWitness { p }
 41        })
 42        .collect()
 43    } else {
 44      Vec::new()
 45    }
 46  }
 47
 48  fn weighted_sum(W: &[PolyEvalWitness<G>], s: &[G::Scalar]) -> PolyEvalWitness<G> {
 49    assert_eq!(W.len(), s.len());
 50    let mut p = vec![G::Scalar::ZERO; W[0].p.len()];
 51    for i in 0..W.len() {
 52      for j in 0..W[i].p.len() {
 53        p[j] += W[i].p[j] * s[i]
 54      }
 55    }
 56    PolyEvalWitness { p }
 57  }
 58
 59  fn batch(p_vec: &[&Vec<G::Scalar>], s: &G::Scalar) -> PolyEvalWitness<G> {
 60    let powers_of_s = powers::<G>(s, p_vec.len());
 61    let mut p = vec![G::Scalar::ZERO; p_vec[0].len()];
 62    for i in 0..p_vec.len() {
 63      for (j, item) in p.iter_mut().enumerate().take(p_vec[i].len()) {
 64        *item += p_vec[i][j] * powers_of_s[i]
 65      }
 66    }
 67    PolyEvalWitness { p }
 68  }
 69}
 70
 71/// A type that holds a polynomial evaluation instance
 72pub struct PolyEvalInstance<G: Group> {
 73  c: Commitment<G>,  // commitment to the polynomial
 74  x: Vec<G::Scalar>, // evaluation point
 75  e: G::Scalar,      // claimed evaluation
 76}
 77
 78impl<G: Group> PolyEvalInstance<G> {
 79  fn pad(U: &[PolyEvalInstance<G>]) -> Vec<PolyEvalInstance<G>> {
 80    // determine the maximum size
 81    if let Some(ell) = U.iter().map(|u| u.x.len()).max() {
 82      U.iter()
 83        .map(|u| {
 84          let mut x = vec![G::Scalar::ZERO; ell - u.x.len()];
 85          x.extend(u.x.clone());
 86          PolyEvalInstance { c: u.c, x, e: u.e }
 87        })
 88        .collect()
 89    } else {
 90      Vec::new()
 91    }
 92  }
 93
 94  fn batch(
 95    c_vec: &[Commitment<G>],
 96    x: &[G::Scalar],
 97    e_vec: &[G::Scalar],
 98    s: &G::Scalar,
 99  ) -> PolyEvalInstance<G> {
100    let powers_of_s = powers::<G>(s, c_vec.len());
101    let e = e_vec
102      .iter()
103      .zip(powers_of_s.iter())
104      .map(|(e, p)| *e * p)
105      .sum();
106    let c = c_vec
107      .iter()
108      .zip(powers_of_s.iter())
109      .map(|(c, p)| *c * *p)
110      .fold(Commitment::<G>::default(), |acc, item| acc + item);
111
112    PolyEvalInstance {
113      c,
114      x: x.to_vec(),
115      e,
116    }
117  }
118}