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