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 // return hash(x_i_plus_1, y_i_plus_1) since Nova circuits expect a single output
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 println!("Producing public parameters...");
173 let pp = PublicParams::<
174 G1,
175 G2,
176 MinRootCircuit<<G1 as Group>::Scalar>,
177 TrivialTestCircuit<<G2 as Group>::Scalar>,
178 >::setup(circuit_primary, circuit_secondary.clone());
179 println!(
180 "Number of constraints per step (primary circuit): {}",
181 pp.num_constraints().0
182 );
183 println!(
184 "Number of constraints per step (secondary circuit): {}",
185 pp.num_constraints().1
186 );
187
188 println!(
189 "Number of variables per step (primary circuit): {}",
190 pp.num_variables().0
191 );
192 println!(
193 "Number of variables per step (secondary circuit): {}",
194 pp.num_variables().1
195 );
196
197 // produce non-deterministic advice
198 let (z0_primary, minroot_iterations) = MinRootIteration::new(
199 num_iters_per_step * num_steps,
200 &<G1 as Group>::Scalar::zero(),
201 &<G1 as Group>::Scalar::one(),
202 );
203 let minroot_circuits = (0..num_steps)
204 .map(|i| MinRootCircuit {
205 seq: (0..num_iters_per_step)
206 .map(|j| MinRootIteration {
207 x_i: minroot_iterations[i * num_iters_per_step + j].x_i,
208 y_i: minroot_iterations[i * num_iters_per_step + j].y_i,
209 x_i_plus_1: minroot_iterations[i * num_iters_per_step + j].x_i_plus_1,
210 y_i_plus_1: minroot_iterations[i * num_iters_per_step + j].y_i_plus_1,
211 })
212 .collect::<Vec<_>>(),
213 })
214 .collect::<Vec<_>>();
215
216 let z0_secondary = vec![<G2 as Group>::Scalar::zero()];
217
218 type C1 = MinRootCircuit<<G1 as Group>::Scalar>;
219 type C2 = TrivialTestCircuit<<G2 as Group>::Scalar>;
220 // produce a recursive SNARK
221 println!("Generating a RecursiveSNARK...");
222 let mut recursive_snark: Option<RecursiveSNARK<G1, G2, C1, C2>> = None;
223
224 for (i, circuit_primary) in minroot_circuits.iter().take(num_steps).enumerate() {
225 let start = Instant::now();
226 let res = RecursiveSNARK::prove_step(
227 &pp,
228 recursive_snark,
229 circuit_primary.clone(),
230 circuit_secondary.clone(),
231 z0_primary.clone(),
232 z0_secondary.clone(),
233 );
234 assert!(res.is_ok());
235 println!(
236 "RecursiveSNARK::prove_step {}: {:?}, took {:?} ",
237 i,
238 res.is_ok(),
239 start.elapsed()
240 );
241 recursive_snark = Some(res.unwrap());
242 }
243
244 assert!(recursive_snark.is_some());
245 let recursive_snark = recursive_snark.unwrap();
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.clone(), z0_secondary.clone());
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 start = Instant::now();
261 type S1 = nova_snark::spartan_with_ipa_pc::RelaxedR1CSSNARK<G1>;
262 type S2 = nova_snark::spartan_with_ipa_pc::RelaxedR1CSSNARK<G2>;
263 let res = CompressedSNARK::<_, _, _, _, S1, S2>::prove(&pp, &recursive_snark);
264 println!(
265 "CompressedSNARK::prove: {:?}, took {:?}",
266 res.is_ok(),
267 start.elapsed()
268 );
269 assert!(res.is_ok());
270 let compressed_snark = res.unwrap();
271
272 // verify the compressed SNARK
273 println!("Verifying a CompressedSNARK...");
274 let start = Instant::now();
275 let res = compressed_snark.verify(&pp, num_steps, z0_primary, z0_secondary);
276 println!(
277 "CompressedSNARK::verify: {:?}, took {:?}",
278 res.is_ok(),
279 start.elapsed()
280 );
281 assert!(res.is_ok());
282 println!("=========================================================");
283 }
284}