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 =
110 x_i_plus_1.square(cs.namespace(|| format!("x_i_plus_1_sq_iter_{}", i)))?;
111 let x_i_plus_1_quad =
112 x_i_plus_1_sq.square(cs.namespace(|| format!("x_i_plus_1_quad_{}", i)))?;
113 cs.enforce(
114 || format!("x_i_plus_1_quad * x_i_plus_1 = x_i + y_i_iter_{}", i),
115 |lc| lc + x_i_plus_1_quad.get_variable(),
116 |lc| lc + x_i_plus_1.get_variable(),
117 |lc| lc + x_i.get_variable() + y_i.get_variable(),
118 );
119
120 if i == self.seq.len() - 1 {
121 z_out = Ok(vec![x_i_plus_1.clone(), x_i.clone()]);
122 }
123
124 // update x_i and y_i for the next iteration
125 y_i = x_i;
126 x_i = x_i_plus_1;
127 }
128
129 z_out
130 }
131
132 fn output(&self, z: &[F]) -> Vec<F> {
133 // sanity check
134 debug_assert_eq!(z[0], self.seq[0].x_i);
135 debug_assert_eq!(z[1], self.seq[0].y_i);
136
137 // compute output using advice
138 vec![
139 self.seq[self.seq.len() - 1].x_i_plus_1,
140 self.seq[self.seq.len() - 1].y_i_plus_1,
141 ]
142 }
143}
144
145fn main() {
146 println!("Nova-based VDF with MinRoot delay function");
147 println!("=========================================================");
148
149 let num_steps = 10;
150 for num_iters_per_step in [1024, 2048, 4096, 8192, 16384, 32768, 65535] {
151 // number of iterations of MinRoot per Nova's recursive step
152 let circuit_primary = MinRootCircuit {
153 seq: vec![
154 MinRootIteration {
155 x_i: <G1 as Group>::Scalar::zero(),
156 y_i: <G1 as Group>::Scalar::zero(),
157 x_i_plus_1: <G1 as Group>::Scalar::zero(),
158 y_i_plus_1: <G1 as Group>::Scalar::zero(),
159 };
160 num_iters_per_step
161 ],
162 };
163
164 let circuit_secondary = TrivialTestCircuit::default();
165
166 println!(
167 "Proving {} iterations of MinRoot per step",
168 num_iters_per_step
169 );
170
171 // produce public parameters
172 let start = Instant::now();
173 println!("Producing public parameters...");
174 let pp = PublicParams::<
175 G1,
176 G2,
177 MinRootCircuit<<G1 as Group>::Scalar>,
178 TrivialTestCircuit<<G2 as Group>::Scalar>,
179 >::setup(circuit_primary, circuit_secondary.clone());
180 println!("PublicParams::setup, took {:?} ", start.elapsed());
181
182 println!(
183 "Number of constraints per step (primary circuit): {}",
184 pp.num_constraints().0
185 );
186 println!(
187 "Number of constraints per step (secondary circuit): {}",
188 pp.num_constraints().1
189 );
190
191 println!(
192 "Number of variables per step (primary circuit): {}",
193 pp.num_variables().0
194 );
195 println!(
196 "Number of variables per step (secondary circuit): {}",
197 pp.num_variables().1
198 );
199
200 // produce non-deterministic advice
201 let (z0_primary, minroot_iterations) = MinRootIteration::new(
202 num_iters_per_step * num_steps,
203 &<G1 as Group>::Scalar::zero(),
204 &<G1 as Group>::Scalar::one(),
205 );
206 let minroot_circuits = (0..num_steps)
207 .map(|i| MinRootCircuit {
208 seq: (0..num_iters_per_step)
209 .map(|j| MinRootIteration {
210 x_i: minroot_iterations[i * num_iters_per_step + j].x_i,
211 y_i: minroot_iterations[i * num_iters_per_step + j].y_i,
212 x_i_plus_1: minroot_iterations[i * num_iters_per_step + j].x_i_plus_1,
213 y_i_plus_1: minroot_iterations[i * num_iters_per_step + j].y_i_plus_1,
214 })
215 .collect::<Vec<_>>(),
216 })
217 .collect::<Vec<_>>();
218
219 let z0_secondary = vec![<G2 as Group>::Scalar::zero()];
220
221 type C1 = MinRootCircuit<<G1 as Group>::Scalar>;
222 type C2 = TrivialTestCircuit<<G2 as Group>::Scalar>;
223 // produce a recursive SNARK
224 println!("Generating a RecursiveSNARK...");
225 let mut recursive_snark: Option<RecursiveSNARK<G1, G2, C1, C2>> = None;
226
227 for (i, circuit_primary) in minroot_circuits.iter().take(num_steps).enumerate() {
228 let start = Instant::now();
229 let res = RecursiveSNARK::prove_step(
230 &pp,
231 recursive_snark,
232 circuit_primary.clone(),
233 circuit_secondary.clone(),
234 z0_primary.clone(),
235 z0_secondary.clone(),
236 );
237 assert!(res.is_ok());
238 println!(
239 "RecursiveSNARK::prove_step {}: {:?}, took {:?} ",
240 i,
241 res.is_ok(),
242 start.elapsed()
243 );
244 recursive_snark = Some(res.unwrap());
245 }
246
247 assert!(recursive_snark.is_some());
248 let recursive_snark = recursive_snark.unwrap();
249
250 // verify the recursive SNARK
251 println!("Verifying a RecursiveSNARK...");
252 let start = Instant::now();
253 let res = recursive_snark.verify(&pp, num_steps, z0_primary.clone(), z0_secondary.clone());
254 println!(
255 "RecursiveSNARK::verify: {:?}, took {:?}",
256 res.is_ok(),
257 start.elapsed()
258 );
259 assert!(res.is_ok());
260
261 // produce a compressed SNARK
262 println!("Generating a CompressedSNARK using Spartan with IPA-PC...");
263 let start = Instant::now();
264 type S1 = nova_snark::spartan_with_ipa_pc::RelaxedR1CSSNARK<G1>;
265 type S2 = nova_snark::spartan_with_ipa_pc::RelaxedR1CSSNARK<G2>;
266 let res = CompressedSNARK::<_, _, _, _, S1, S2>::prove(&pp, &recursive_snark);
267 println!(
268 "CompressedSNARK::prove: {:?}, took {:?}",
269 res.is_ok(),
270 start.elapsed()
271 );
272 assert!(res.is_ok());
273 let compressed_snark = res.unwrap();
274
275 let mut encoder = ZlibEncoder::new(Vec::new(), Compression::default());
276 bincode::serialize_into(&mut encoder, &compressed_snark).unwrap();
277 let compressed_snark_encoded = encoder.finish().unwrap();
278 println!(
279 "CompressedSNARK::len {:?} bytes",
280 compressed_snark_encoded.len()
281 );
282
283 // verify the compressed SNARK
284 println!("Verifying a CompressedSNARK...");
285 let start = Instant::now();
286 let res = compressed_snark.verify(&pp, num_steps, z0_primary, z0_secondary);
287 println!(
288 "CompressedSNARK::verify: {:?}, took {:?}",
289 res.is_ok(),
290 start.elapsed()
291 );
292 assert!(res.is_ok());
293 println!("=========================================================");
294 }
295}