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 nova_snark::{
9 traits::{
10 circuit::{StepCircuit, TrivialTestCircuit},
11 Group,
12 },
13 CompressedSNARK, PublicParams, RecursiveSNARK,
14};
15use num_bigint::BigUint;
16use std::time::Instant;
17
18#[derive(Clone, Debug)]
19struct MinRootIteration<F: PrimeField> {
20 x_i: F,
21 y_i: F,
22 x_i_plus_1: F,
23 y_i_plus_1: F,
24}
25
26impl<F: PrimeField> MinRootIteration<F> {
27 // produces a sample non-deterministic advice, executing one invocation of MinRoot per step
28 fn new(num_iters: usize, x_0: &F, y_0: &F) -> (Vec<F>, Vec<Self>) {
29 // although this code is written generically, it is tailored to Pallas' scalar field
30 // (p - 3 / 5)
31 let exp = BigUint::parse_bytes(
32 b"23158417847463239084714197001737581570690445185553317903743794198714690358477",
33 10,
34 )
35 .unwrap();
36
37 let mut res = Vec::new();
38 let mut x_i = *x_0;
39 let mut y_i = *y_0;
40 for _i in 0..num_iters {
41 let x_i_plus_1 = (x_i + y_i).pow_vartime(exp.to_u64_digits()); // computes the fifth root of x_i + y_i
42
43 // sanity check
44 let sq = x_i_plus_1 * x_i_plus_1;
45 let quad = sq * sq;
46 let fifth = quad * x_i_plus_1;
47 debug_assert_eq!(fifth, x_i + y_i);
48
49 let y_i_plus_1 = x_i;
50
51 res.push(Self {
52 x_i,
53 y_i,
54 x_i_plus_1,
55 y_i_plus_1,
56 });
57
58 x_i = x_i_plus_1;
59 y_i = y_i_plus_1;
60 }
61
62 let z0 = vec![*x_0, *y_0];
63
64 (z0, res)
65 }
66}
67
68#[derive(Clone, Debug)]
69struct MinRootCircuit<F: PrimeField> {
70 seq: Vec<MinRootIteration<F>>,
71}
72
73impl<F> StepCircuit<F> for MinRootCircuit<F>
74where
75 F: PrimeField,
76{
77 fn arity(&self) -> usize {
78 2
79 }
80
81 fn synthesize<CS: ConstraintSystem<F>>(
82 &self,
83 cs: &mut CS,
84 z: &[AllocatedNum<F>],
85 ) -> Result<Vec<AllocatedNum<F>>, SynthesisError> {
86 let mut z_out: Result<Vec<AllocatedNum<F>>, SynthesisError> =
87 Err(SynthesisError::AssignmentMissing);
88
89 // use the provided inputs
90 let x_0 = z[0].clone();
91 let y_0 = z[1].clone();
92
93 // variables to hold running x_i and y_i
94 let mut x_i = x_0;
95 let mut y_i = y_0;
96 for i in 0..self.seq.len() {
97 // non deterministic advice
98 let x_i_plus_1 =
99 AllocatedNum::alloc(cs.namespace(|| format!("x_i_plus_1_iter_{}", i)), || {
100 Ok(self.seq[i].x_i_plus_1)
101 })?;
102
103 // check the following conditions hold:
104 // (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
105 // (ii) y_i_plus_1 = x_i
106 // (1) constraints for condition (i) are below
107 // (2) constraints for condition (ii) is avoided because we just used x_i wherever y_i_plus_1 is used
108 let x_i_plus_1_sq =
109 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!(
166 "Proving {} iterations of MinRoot per step",
167 num_iters_per_step
168 );
169
170 // produce public parameters
171 println!("Producing public parameters...");
172 let pp = PublicParams::<
173 G1,
174 G2,
175 MinRootCircuit<<G1 as Group>::Scalar>,
176 TrivialTestCircuit<<G2 as Group>::Scalar>,
177 >::setup(circuit_primary, circuit_secondary.clone());
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: Option<RecursiveSNARK<G1, G2, C1, C2>> = None;
222
223 for (i, circuit_primary) in minroot_circuits.iter().take(num_steps).enumerate() {
224 let start = Instant::now();
225 let res = RecursiveSNARK::prove_step(
226 &pp,
227 recursive_snark,
228 circuit_primary.clone(),
229 circuit_secondary.clone(),
230 z0_primary.clone(),
231 z0_secondary.clone(),
232 );
233 assert!(res.is_ok());
234 println!(
235 "RecursiveSNARK::prove_step {}: {:?}, took {:?} ",
236 i,
237 res.is_ok(),
238 start.elapsed()
239 );
240 recursive_snark = Some(res.unwrap());
241 }
242
243 assert!(recursive_snark.is_some());
244 let recursive_snark = recursive_snark.unwrap();
245
246 // verify the recursive SNARK
247 println!("Verifying a RecursiveSNARK...");
248 let start = Instant::now();
249 let res = recursive_snark.verify(&pp, num_steps, z0_primary.clone(), z0_secondary.clone());
250 println!(
251 "RecursiveSNARK::verify: {:?}, took {:?}",
252 res.is_ok(),
253 start.elapsed()
254 );
255 assert!(res.is_ok());
256
257 // produce a compressed SNARK
258 println!("Generating a CompressedSNARK using Spartan with IPA-PC...");
259 let start = Instant::now();
260 type S1 = nova_snark::spartan_with_ipa_pc::RelaxedR1CSSNARK<G1>;
261 type S2 = nova_snark::spartan_with_ipa_pc::RelaxedR1CSSNARK<G2>;
262 let res = CompressedSNARK::<_, _, _, _, S1, S2>::prove(&pp, &recursive_snark);
263 println!(
264 "CompressedSNARK::prove: {:?}, took {:?}",
265 res.is_ok(),
266 start.elapsed()
267 );
268 assert!(res.is_ok());
269 let compressed_snark = res.unwrap();
270
271 // verify the compressed SNARK
272 println!("Verifying a CompressedSNARK...");
273 let start = Instant::now();
274 let res = compressed_snark.verify(&pp, num_steps, z0_primary, z0_secondary);
275 println!(
276 "CompressedSNARK::verify: {:?}, took {:?}",
277 res.is_ok(),
278 start.elapsed()
279 );
280 assert!(res.is_ok());
281 println!("=========================================================");
282 }
283}