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