1#![allow(non_snake_case)]
  2
  3use bellperson::{gadgets::num::AllocatedNum, ConstraintSystem, SynthesisError};
  4use core::marker::PhantomData;
  5use criterion::*;
  6use ff::PrimeField;
  7use nova_snark::{
  8  traits::{
  9    circuit::{StepCircuit, TrivialTestCircuit},
 10    Group,
 11  },
 12  PublicParams, RecursiveSNARK,
 13};
 14use std::time::Duration;
 15
 16type G1 = pasta_curves::pallas::Point;
 17type G2 = pasta_curves::vesta::Point;
 18type C1 = NonTrivialTestCircuit<<G1 as Group>::Scalar>;
 19type C2 = TrivialTestCircuit<<G2 as Group>::Scalar>;
 20
 21criterion_group! {
 22name = recursive_snark;
 23config = Criterion::default().warm_up_time(Duration::from_millis(3000));
 24targets = bench_recursive_snark
 25}
 26
 27criterion_main!(recursive_snark);
 28
 29fn bench_recursive_snark(c: &mut Criterion) {
 30  let num_cons_verifier_circuit_primary = 9819;
 31  // we vary the number of constraints in the step circuit
 32  for &num_cons_in_augmented_circuit in
 33    [9819, 16384, 32768, 65536, 131072, 262144, 524288, 1048576].iter()
 34  {
 35    // number of constraints in the step circuit
 36    let num_cons = num_cons_in_augmented_circuit - num_cons_verifier_circuit_primary;
 37
 38    let mut group = c.benchmark_group(format!("RecursiveSNARK-StepCircuitSize-{}", num_cons));
 39    group.sample_size(10);
 40
 41    // Produce public parameters
 42    let pp = PublicParams::<G1, G2, C1, C2>::setup(
 43      NonTrivialTestCircuit::new(num_cons),
 44      TrivialTestCircuit::default(),
 45    );
 46
 47    // Bench time to produce a recursive SNARK;
 48    // we execute a certain number of warm-up steps since executing
 49    // the first step is cheaper than other steps owing to the presence of
 50    // a lot of zeros in the satisfying assignment
 51    let num_warmup_steps = 10;
 52    let mut recursive_snark: Option<RecursiveSNARK<G1, G2, C1, C2>> = None;
 53
 54    for i in 0..num_warmup_steps {
 55      let res = RecursiveSNARK::prove_step(
 56        &pp,
 57        recursive_snark,
 58        NonTrivialTestCircuit::new(num_cons),
 59        TrivialTestCircuit::default(),
 60        vec![<G1 as Group>::Scalar::from(2u64)],
 61        vec![<G2 as Group>::Scalar::from(2u64)],
 62      );
 63      assert!(res.is_ok());
 64      let recursive_snark_unwrapped = res.unwrap();
 65
 66      // verify the recursive snark at each step of recursion
 67      let res = recursive_snark_unwrapped.verify(
 68        &pp,
 69        i + 1,
 70        vec![<G1 as Group>::Scalar::from(2u64)],
 71        vec![<G2 as Group>::Scalar::from(2u64)],
 72      );
 73      assert!(res.is_ok());
 74
 75      // set the running variable for the next iteration
 76      recursive_snark = Some(recursive_snark_unwrapped);
 77    }
 78
 79    group.bench_function("Prove", |b| {
 80      b.iter(|| {
 81        // produce a recursive SNARK for a step of the recursion
 82        assert!(RecursiveSNARK::prove_step(
 83          black_box(&pp),
 84          black_box(recursive_snark.clone()),
 85          black_box(NonTrivialTestCircuit::new(num_cons)),
 86          black_box(TrivialTestCircuit::default()),
 87          black_box(vec![<G1 as Group>::Scalar::from(2u64)]),
 88          black_box(vec![<G2 as Group>::Scalar::from(2u64)]),
 89        )
 90        .is_ok());
 91      })
 92    });
 93
 94    let recursive_snark = recursive_snark.unwrap();
 95
 96    // Benchmark the verification time
 97    group.bench_function("Verify", |b| {
 98      b.iter(|| {
 99        assert!(black_box(&recursive_snark)
100          .verify(
101            black_box(&pp),
102            black_box(num_warmup_steps),
103            black_box(vec![<G1 as Group>::Scalar::from(2u64)]),
104            black_box(vec![<G2 as Group>::Scalar::from(2u64)]),
105          )
106          .is_ok());
107      });
108    });
109    group.finish();
110  }
111}
112
113#[derive(Clone, Debug, Default)]
114struct NonTrivialTestCircuit<F: PrimeField> {
115  num_cons: usize,
116  _p: PhantomData<F>,
117}
118
119impl<F> NonTrivialTestCircuit<F>
120where
121  F: PrimeField,
122{
123  pub fn new(num_cons: usize) -> Self {
124    Self {
125      num_cons,
126      _p: Default::default(),
127    }
128  }
129}
130impl<F> StepCircuit<F> for NonTrivialTestCircuit<F>
131where
132  F: PrimeField,
133{
134  fn arity(&self) -> usize {
135    1
136  }
137
138  fn synthesize<CS: ConstraintSystem<F>>(
139    &self,
140    cs: &mut CS,
141    z: &[AllocatedNum<F>],
142  ) -> Result<Vec<AllocatedNum<F>>, SynthesisError> {
143    // Consider a an equation: `x^2 = y`, where `x` and `y` are respectively the input and output.
144    let mut x = z[0].clone();
145    let mut y = x.clone();
146    for i in 0..self.num_cons {
147      y = x.square(cs.namespace(|| format!("x_sq_{}", i)))?;
148      x = y.clone();
149    }
150    Ok(vec![y])
151  }
152
153  fn output(&self, z: &[F]) -> Vec<F> {
154    let mut x = z[0];
155    let mut y = x;
156    for _i in 0..self.num_cons {
157      y = x * x;
158      x = y;
159    }
160    vec![y]
161  }
162}