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
 21// To run these benchmarks, first download `criterion` with `cargo install cargo install cargo-criterion`.
 22// Then `cargo criterion --bench recursive-snark`. The results are located in `target/criterion/data/<name-of-benchmark>`.
 23// For flamegraphs, run `cargo criterion --bench recursive-snark --features flamegraph -- --profile-time <secs>`.
 24// The results are located in `target/criterion/profile/<name-of-benchmark>`.
 25cfg_if::cfg_if! {
 26  if #[cfg(feature = "flamegraph")] {
 27    criterion_group! {
 28      name = recursive_snark;
 29      config = Criterion::default().warm_up_time(Duration::from_millis(3000)).with_profiler(pprof::criterion::PProfProfiler::new(100, pprof::criterion::Output::Flamegraph(None)));
 30      targets = bench_recursive_snark
 31    }
 32  } else {
 33    criterion_group! {
 34      name = recursive_snark;
 35      config = Criterion::default().warm_up_time(Duration::from_millis(3000));
 36      targets = bench_recursive_snark
 37    }
 38  }
 39}
 40
 41criterion_main!(recursive_snark);
 42
 43fn bench_recursive_snark(c: &mut Criterion) {
 44  let num_cons_verifier_circuit_primary = 9819;
 45  // we vary the number of constraints in the step circuit
 46  for &num_cons_in_augmented_circuit in
 47    [9819, 16384, 32768, 65536, 131072, 262144, 524288, 1048576].iter()
 48  {
 49    // number of constraints in the step circuit
 50    let num_cons = num_cons_in_augmented_circuit - num_cons_verifier_circuit_primary;
 51
 52    let mut group = c.benchmark_group(format!("RecursiveSNARK-StepCircuitSize-{num_cons}"));
 53    group.sample_size(10);
 54
 55    let c_primary = NonTrivialTestCircuit::new(num_cons);
 56    let c_secondary = TrivialTestCircuit::default();
 57
 58    // Produce public parameters
 59    let pp = PublicParams::<G1, G2, C1, C2>::setup(c_primary.clone(), c_secondary.clone());
 60
 61    // Bench time to produce a recursive SNARK;
 62    // we execute a certain number of warm-up steps since executing
 63    // the first step is cheaper than other steps owing to the presence of
 64    // a lot of zeros in the satisfying assignment
 65    let num_warmup_steps = 10;
 66    let mut recursive_snark: RecursiveSNARK<G1, G2, C1, C2> = RecursiveSNARK::new(
 67      &pp,
 68      &c_primary,
 69      &c_secondary,
 70      vec![<G1 as Group>::Scalar::from(2u64)],
 71      vec![<G2 as Group>::Scalar::from(2u64)],
 72    );
 73
 74    for i in 0..num_warmup_steps {
 75      let res = recursive_snark.prove_step(
 76        &pp,
 77        &c_primary,
 78        &c_secondary,
 79        vec![<G1 as Group>::Scalar::from(2u64)],
 80        vec![<G2 as Group>::Scalar::from(2u64)],
 81      );
 82      assert!(res.is_ok());
 83
 84      // verify the recursive snark at each step of recursion
 85      let res = recursive_snark.verify(
 86        &pp,
 87        i + 1,
 88        &[<G1 as Group>::Scalar::from(2u64)],
 89        &[<G2 as Group>::Scalar::from(2u64)],
 90      );
 91      assert!(res.is_ok());
 92    }
 93
 94    group.bench_function("Prove", |b| {
 95      b.iter(|| {
 96        // produce a recursive SNARK for a step of the recursion
 97        assert!(black_box(&mut recursive_snark.clone())
 98          .prove_step(
 99            black_box(&pp),
100            black_box(&c_primary),
101            black_box(&c_secondary),
102            black_box(vec![<G1 as Group>::Scalar::from(2u64)]),
103            black_box(vec![<G2 as Group>::Scalar::from(2u64)]),
104          )
105          .is_ok());
106      })
107    });
108
109    // Benchmark the verification time
110    group.bench_function("Verify", |b| {
111      b.iter(|| {
112        assert!(black_box(&recursive_snark)
113          .verify(
114            black_box(&pp),
115            black_box(num_warmup_steps),
116            black_box(&vec![<G1 as Group>::Scalar::from(2u64)][..]),
117            black_box(&vec![<G2 as Group>::Scalar::from(2u64)][..]),
118          )
119          .is_ok());
120      });
121    });
122    group.finish();
123  }
124}
125
126#[derive(Clone, Debug, Default)]
127struct NonTrivialTestCircuit<F: PrimeField> {
128  num_cons: usize,
129  _p: PhantomData<F>,
130}
131
132impl<F> NonTrivialTestCircuit<F>
133where
134  F: PrimeField,
135{
136  pub fn new(num_cons: usize) -> Self {
137    Self {
138      num_cons,
139      _p: Default::default(),
140    }
141  }
142}
143impl<F> StepCircuit<F> for NonTrivialTestCircuit<F>
144where
145  F: PrimeField,
146{
147  fn arity(&self) -> usize {
148    1
149  }
150
151  fn synthesize<CS: ConstraintSystem<F>>(
152    &self,
153    cs: &mut CS,
154    z: &[AllocatedNum<F>],
155  ) -> Result<Vec<AllocatedNum<F>>, SynthesisError> {
156    // Consider a an equation: `x^2 = y`, where `x` and `y` are respectively the input and output.
157    let mut x = z[0].clone();
158    let mut y = x.clone();
159    for i in 0..self.num_cons {
160      y = x.square(cs.namespace(|| format!("x_sq_{i}")))?;
161      x = y.clone();
162    }
163    Ok(vec![y])
164  }
165
166  fn output(&self, z: &[F]) -> Vec<F> {
167    let mut x = z[0];
168    let mut y = x;
169    for _i in 0..self.num_cons {
170      y = x * x;
171      x = y;
172    }
173    vec![y]
174  }
175}