Nova/examples/minroot.rs
examples/minroot.rsRaw
1//! Demonstrates how to use Nova to produce a recursive proof of the correct execution of
2//! iterations of the MinRoot function, thereby realizing a Nova-based verifiable delay function (VDF).
3//! We execute a configurable number of iterations of the MinRoot function per step of Nova's recursion.
4type G1 = pasta_curves::pallas::Point;
5type G2 = pasta_curves::vesta::Point;
6use ::bellperson::{gadgets::num::AllocatedNum, ConstraintSystem, SynthesisError};
7use ff::PrimeField;
8use generic_array::typenum::U2;
9use neptune::{
10 circuit::poseidon_hash,
11 poseidon::{Poseidon, PoseidonConstants},
12 Strength,
13};
14use nova_snark::{
15 traits::{Group, StepCircuit},
16 CompressedSNARK, PublicParams, RecursiveSNARK,
17};
18use num_bigint::BigUint;
19use std::marker::PhantomData;
20use std::time::Instant;
21
22#[derive(Clone, Debug)]
23struct MinRootIteration<F: PrimeField> {
24 x_i: F,
25 y_i: F,
26 x_i_plus_1: F,
27 y_i_plus_1: F,
28}
29
30impl<F: PrimeField> MinRootIteration<F> {
31 // produces a sample non-deterministic advice, executing one invocation of MinRoot per step
32 fn new(num_iters: usize, x_0: &F, y_0: &F, pc: &PoseidonConstants<F, U2>) -> (F, Vec<Self>) {
33 // although this code is written generically, it is tailored to Pallas' scalar field
34 // (p - 3 / 5)
35 let exp = BigUint::parse_bytes(
36 b"23158417847463239084714197001737581570690445185553317903743794198714690358477",
37 10,
38 )
39 .unwrap();
40
41 let mut res = Vec::new();
42 let mut x_i = *x_0;
43 let mut y_i = *y_0;
44 for _i in 0..num_iters {
45 let x_i_plus_1 = (x_i + y_i).pow_vartime(exp.to_u64_digits()); // computes the fifth root of x_i + y_i
46
47 // sanity check
48 let sq = x_i_plus_1 * x_i_plus_1;
49 let quad = sq * sq;
50 let fifth = quad * x_i_plus_1;
51 debug_assert_eq!(fifth, x_i + y_i);
52
53 let y_i_plus_1 = x_i;
54
55 res.push(Self {
56 x_i,
57 y_i,
58 x_i_plus_1,
59 y_i_plus_1,
60 });
61
62 x_i = x_i_plus_1;
63 y_i = y_i_plus_1;
64 }
65
66 let z0 = Poseidon::<F, U2>::new_with_preimage(&[*x_0, *y_0], pc).hash();
67
68 (z0, res)
69 }
70}
71
72#[derive(Clone, Debug)]
73struct MinRootCircuit<F: PrimeField> {
74 seq: Vec<MinRootIteration<F>>,
75 pc: PoseidonConstants<F, U2>,
76}
77
78impl<F> StepCircuit<F> for MinRootCircuit<F>
79where
80 F: PrimeField,
81{
82 fn synthesize<CS: ConstraintSystem<F>>(
83 &self,
84 cs: &mut CS,
85 z: AllocatedNum<F>,
86 ) -> Result<AllocatedNum<F>, SynthesisError> {
87 let mut z_out: Result<AllocatedNum<F>, SynthesisError> = Err(SynthesisError::AssignmentMissing);
88 for i in 0..self.seq.len() {
89 // Allocate four variables for holding non-deterministic advice: x_i, y_i, x_i_plus_1, y_i_plus_1
90 let x_i = AllocatedNum::alloc(cs.namespace(|| format!("x_i_iter_{}", i)), || {
91 Ok(self.seq[i].x_i)
92 })?;
93 let y_i = AllocatedNum::alloc(cs.namespace(|| format!("y_i_iter_{}", i)), || {
94 Ok(self.seq[i].y_i)
95 })?;
96 let x_i_plus_1 =
97 AllocatedNum::alloc(cs.namespace(|| format!("x_i_plus_1_iter_{}", i)), || {
98 Ok(self.seq[i].x_i_plus_1)
99 })?;
100
101 // check that z = hash(x_i, y_i), where z is an output from the prior step
102 if i == 0 {
103 let z_hash = poseidon_hash(
104 cs.namespace(|| "input hash"),
105 vec![x_i.clone(), y_i.clone()],
106 &self.pc,
107 )?;
108 cs.enforce(
109 || "z =? z_hash",
110 |lc| lc + z_hash.get_variable(),
111 |lc| lc + CS::one(),
112 |lc| lc + z.get_variable(),
113 );
114 }
115
116 // check the following conditions hold:
117 // (i) x_i_plus_1 = (x_i + y_i)^{1/5}, which can be more easily checked with x_i_plus_1^5 = x_i + y_i
118 // (ii) y_i_plus_1 = x_i
119 // (1) constraints for condition (i) are below
120 // (2) constraints for condition (ii) is avoided because we just used x_i wherever y_i_plus_1 is used
121 let x_i_plus_1_sq =
122 x_i_plus_1.square(cs.namespace(|| format!("x_i_plus_1_sq_iter_{}", i)))?;
123 let x_i_plus_1_quad =
124 x_i_plus_1_sq.square(cs.namespace(|| format!("x_i_plus_1_quad_{}", i)))?;
125 let x_i_plus_1_pow_5 = x_i_plus_1_quad.mul(
126 cs.namespace(|| format!("x_i_plus_1_pow_5_{}", i)),
127 &x_i_plus_1,
128 )?;
129 cs.enforce(
130 || format!("x_i_plus_1_pow_5 = x_i + y_i_iter_{}", i),
131 |lc| lc + x_i_plus_1_pow_5.get_variable(),
132 |lc| lc + CS::one(),
133 |lc| lc + x_i.get_variable() + y_i.get_variable(),
134 );
135
136 // return hash(x_i_plus_1, y_i_plus_1) since Nova circuits expect a single output
137 if i == self.seq.len() - 1 {
138 z_out = poseidon_hash(
139 cs.namespace(|| "output hash"),
140 vec![x_i_plus_1, x_i.clone()],
141 &self.pc,
142 );
143 }
144 }
145
146 z_out
147 }
148
149 fn compute(&self, z: &F) -> F {
150 // sanity check
151 let z_hash =
152 Poseidon::<F, U2>::new_with_preimage(&[self.seq[0].x_i, self.seq[0].y_i], &self.pc).hash();
153 debug_assert_eq!(z, &z_hash);
154
155 // compute output hash using advice
156 let iters = self.seq.len();
157 Poseidon::<F, U2>::new_with_preimage(
158 &[
159 self.seq[iters - 1].x_i_plus_1,
160 self.seq[iters - 1].y_i_plus_1,
161 ],
162 &self.pc,
163 )
164 .hash()
165 }
166}
167
168fn main() {
169 let num_steps = 10;
170 let num_iters_per_step = 10; // number of iterations of MinRoot per Nova's recursive step
171
172 let pc = PoseidonConstants::<<G1 as Group>::Scalar, U2>::new_with_strength(Strength::Standard);
173 let circuit_primary = MinRootCircuit {
174 seq: vec![
175 MinRootIteration {
176 x_i: <G1 as Group>::Scalar::zero(),
177 y_i: <G1 as Group>::Scalar::zero(),
178 x_i_plus_1: <G1 as Group>::Scalar::zero(),
179 y_i_plus_1: <G1 as Group>::Scalar::zero(),
180 };
181 num_iters_per_step
182 ],
183 pc: pc.clone(),
184 };
185
186 let circuit_secondary = TrivialTestCircuit {
187 _p: Default::default(),
188 };
189
190 println!("Nova-based VDF with MinRoot delay function");
191 println!("==========================================");
192 println!(
193 "Proving {} iterations of MinRoot per step",
194 num_iters_per_step
195 );
196
197 // produce public parameters
198 println!("Producing public parameters...");
199 let pp = PublicParams::<
200 G1,
201 G2,
202 MinRootCircuit<<G1 as Group>::Scalar>,
203 TrivialTestCircuit<<G2 as Group>::Scalar>,
204 >::setup(circuit_primary, circuit_secondary.clone());
205 println!(
206 "Number of constraints per step (primary circuit): {}",
207 pp.num_constraints().0
208 );
209 println!(
210 "Number of constraints per step (secondary circuit): {}",
211 pp.num_constraints().1
212 );
213
214 // produce non-deterministic advice
215 let (z0_primary, minroot_iterations) = MinRootIteration::new(
216 num_iters_per_step * num_steps,
217 &<G1 as Group>::Scalar::zero(),
218 &<G1 as Group>::Scalar::one(),
219 &pc,
220 );
221 let minroot_circuits = (0..num_steps)
222 .map(|i| MinRootCircuit {
223 seq: (0..num_iters_per_step)
224 .map(|j| MinRootIteration {
225 x_i: minroot_iterations[i * num_iters_per_step + j].x_i,
226 y_i: minroot_iterations[i * num_iters_per_step + j].y_i,
227 x_i_plus_1: minroot_iterations[i * num_iters_per_step + j].x_i_plus_1,
228 y_i_plus_1: minroot_iterations[i * num_iters_per_step + j].y_i_plus_1,
229 })
230 .collect::<Vec<_>>(),
231 pc: pc.clone(),
232 })
233 .collect::<Vec<_>>();
234
235 let z0_secondary = <G2 as Group>::Scalar::zero();
236
237 type C1 = MinRootCircuit<<G1 as Group>::Scalar>;
238 type C2 = TrivialTestCircuit<<G2 as Group>::Scalar>;
239 // produce a recursive SNARK
240 println!("Generating a RecursiveSNARK...");
241 let mut recursive_snark: Option<RecursiveSNARK<G1, G2, C1, C2>> = None;
242
243 for (i, circuit_primary) in minroot_circuits.iter().take(num_steps).enumerate() {
244 let start = Instant::now();
245 let res = RecursiveSNARK::prove_step(
246 &pp,
247 recursive_snark,
248 circuit_primary.clone(),
249 circuit_secondary.clone(),
250 z0_primary,
251 z0_secondary,
252 );
253 assert!(res.is_ok());
254 println!(
255 "RecursiveSNARK::prove_step {}: {:?}, took {:?} ",
256 i,
257 res.is_ok(),
258 start.elapsed()
259 );
260 recursive_snark = Some(res.unwrap());
261 }
262
263 assert!(recursive_snark.is_some());
264 let recursive_snark = recursive_snark.unwrap();
265
266 // verify the recursive SNARK
267 println!("Verifying a RecursiveSNARK...");
268 let start = Instant::now();
269 let res = recursive_snark.verify(&pp, num_steps, z0_primary, z0_secondary);
270 println!(
271 "RecursiveSNARK::verify: {:?}, took {:?}",
272 res.is_ok(),
273 start.elapsed()
274 );
275 assert!(res.is_ok());
276
277 // produce a compressed SNARK
278 println!("Generating a CompressedSNARK using Spartan with IPA-PC...");
279 let start = Instant::now();
280 type S1 = nova_snark::spartan_with_ipa_pc::RelaxedR1CSSNARK<G1>;
281 type S2 = nova_snark::spartan_with_ipa_pc::RelaxedR1CSSNARK<G2>;
282 let res = CompressedSNARK::<_, _, _, _, S1, S2>::prove(&pp, &recursive_snark);
283 println!(
284 "CompressedSNARK::prove: {:?}, took {:?}",
285 res.is_ok(),
286 start.elapsed()
287 );
288 assert!(res.is_ok());
289 let compressed_snark = res.unwrap();
290
291 // verify the compressed SNARK
292 println!("Verifying a CompressedSNARK...");
293 let start = Instant::now();
294 let res = compressed_snark.verify(&pp, num_steps, z0_primary, z0_secondary);
295 println!(
296 "CompressedSNARK::verify: {:?}, took {:?}",
297 res.is_ok(),
298 start.elapsed()
299 );
300 assert!(res.is_ok());
301}
302
303// A trivial test circuit that we use on the secondary curve
304#[derive(Clone, Debug)]
305struct TrivialTestCircuit<F: PrimeField> {
306 _p: PhantomData<F>,
307}
308
309impl<F> StepCircuit<F> for TrivialTestCircuit<F>
310where
311 F: PrimeField,
312{
313 fn synthesize<CS: ConstraintSystem<F>>(
314 &self,
315 _cs: &mut CS,
316 z: AllocatedNum<F>,
317 ) -> Result<AllocatedNum<F>, SynthesisError> {
318 Ok(z)
319 }
320
321 fn compute(&self, z: &F) -> F {
322 *z
323 }
324}