Nova/src/lib.rs
src/lib.rsRaw
1//! This library implements Nova, a high-speed recursive SNARK.
2#![allow(non_snake_case)]
3#![allow(clippy::type_complexity)]
4#![deny(missing_docs)]
5
6// private modules
7mod bellperson;
8mod circuit;
9mod commitments;
10mod constants;
11mod nifs;
12mod poseidon;
13mod r1cs;
14
15// public modules
16pub mod errors;
17pub mod gadgets;
18pub mod pasta;
19pub mod spartan_with_ipa_pc;
20pub mod traits;
21
22use crate::bellperson::{
23 r1cs::{NovaShape, NovaWitness},
24 shape_cs::ShapeCS,
25 solver::SatisfyingAssignment,
26};
27use ::bellperson::{Circuit, ConstraintSystem};
28use circuit::{NovaAugmentedCircuit, NovaAugmentedCircuitInputs, NovaAugmentedCircuitParams};
29use constants::NUM_HASH_BITS;
30use constants::{BN_LIMB_WIDTH, BN_N_LIMBS};
31use core::marker::PhantomData;
32use errors::NovaError;
33use ff::Field;
34use gadgets::utils::scalar_as_base;
35use nifs::NIFS;
36use r1cs::{
37 R1CSGens, R1CSInstance, R1CSShape, R1CSWitness, RelaxedR1CSInstance, RelaxedR1CSWitness,
38};
39use traits::{
40 circuit::StepCircuit, snark::RelaxedR1CSSNARKTrait, AbsorbInROTrait, Group, ROConstants,
41 ROConstantsCircuit, ROConstantsTrait, ROTrait,
42};
43
44/// A type that holds public parameters of Nova
45pub struct PublicParams<G1, G2, C1, C2>
46where
47 G1: Group<Base = <G2 as Group>::Scalar>,
48 G2: Group<Base = <G1 as Group>::Scalar>,
49 C1: StepCircuit<G1::Scalar>,
50 C2: StepCircuit<G2::Scalar>,
51{
52 ro_consts_primary: ROConstants<G1>,
53 ro_consts_circuit_primary: ROConstantsCircuit<G2>,
54 r1cs_gens_primary: R1CSGens<G1>,
55 r1cs_shape_primary: R1CSShape<G1>,
56 r1cs_shape_padded_primary: R1CSShape<G1>,
57 ro_consts_secondary: ROConstants<G2>,
58 ro_consts_circuit_secondary: ROConstantsCircuit<G1>,
59 r1cs_gens_secondary: R1CSGens<G2>,
60 r1cs_shape_secondary: R1CSShape<G2>,
61 r1cs_shape_padded_secondary: R1CSShape<G2>,
62 augmented_circuit_params_primary: NovaAugmentedCircuitParams,
63 augmented_circuit_params_secondary: NovaAugmentedCircuitParams,
64 _p_c1: PhantomData<C1>,
65 _p_c2: PhantomData<C2>,
66}
67
68impl<G1, G2, C1, C2> PublicParams<G1, G2, C1, C2>
69where
70 G1: Group<Base = <G2 as Group>::Scalar>,
71 G2: Group<Base = <G1 as Group>::Scalar>,
72 C1: StepCircuit<G1::Scalar>,
73 C2: StepCircuit<G2::Scalar>,
74{
75 /// Create a new `PublicParams`
76 pub fn setup(c_primary: C1, c_secondary: C2) -> Self {
77 let augmented_circuit_params_primary =
78 NovaAugmentedCircuitParams::new(BN_LIMB_WIDTH, BN_N_LIMBS, true);
79 let augmented_circuit_params_secondary =
80 NovaAugmentedCircuitParams::new(BN_LIMB_WIDTH, BN_N_LIMBS, false);
81
82 let ro_consts_primary: ROConstants<G1> = ROConstants::<G1>::new();
83 let ro_consts_secondary: ROConstants<G2> = ROConstants::<G2>::new();
84
85 // ro_consts_circuit_primart are parameterized by G2 because the type alias uses G2::Base = G1::Scalar
86 let ro_consts_circuit_primary: ROConstantsCircuit<G2> = ROConstantsCircuit::<G2>::new();
87 let ro_consts_circuit_secondary: ROConstantsCircuit<G1> = ROConstantsCircuit::<G1>::new();
88
89 // Initialize gens for the primary
90 let circuit_primary: NovaAugmentedCircuit<G2, C1> = NovaAugmentedCircuit::new(
91 augmented_circuit_params_primary.clone(),
92 None,
93 c_primary,
94 ro_consts_circuit_primary.clone(),
95 );
96 let mut cs: ShapeCS<G1> = ShapeCS::new();
97 let _ = circuit_primary.synthesize(&mut cs);
98 let (r1cs_shape_primary, r1cs_gens_primary) = (cs.r1cs_shape(), cs.r1cs_gens());
99 let r1cs_shape_padded_primary = r1cs_shape_primary.pad();
100
101 // Initialize gens for the secondary
102 let circuit_secondary: NovaAugmentedCircuit<G1, C2> = NovaAugmentedCircuit::new(
103 augmented_circuit_params_secondary.clone(),
104 None,
105 c_secondary,
106 ro_consts_circuit_secondary.clone(),
107 );
108 let mut cs: ShapeCS<G2> = ShapeCS::new();
109 let _ = circuit_secondary.synthesize(&mut cs);
110 let (r1cs_shape_secondary, r1cs_gens_secondary) = (cs.r1cs_shape(), cs.r1cs_gens());
111 let r1cs_shape_padded_secondary = r1cs_shape_secondary.pad();
112
113 Self {
114 ro_consts_primary,
115 ro_consts_circuit_primary,
116 r1cs_gens_primary,
117 r1cs_shape_primary,
118 r1cs_shape_padded_primary,
119 ro_consts_secondary,
120 ro_consts_circuit_secondary,
121 r1cs_gens_secondary,
122 r1cs_shape_secondary,
123 r1cs_shape_padded_secondary,
124 augmented_circuit_params_primary,
125 augmented_circuit_params_secondary,
126 _p_c1: Default::default(),
127 _p_c2: Default::default(),
128 }
129 }
130
131 /// Returns the number of constraints in the primary and secondary circuits
132 pub fn num_constraints(&self) -> (usize, usize) {
133 (
134 self.r1cs_shape_primary.num_cons,
135 self.r1cs_shape_secondary.num_cons,
136 )
137 }
138}
139
140/// A SNARK that proves the correct execution of an incremental computation
141#[derive(Clone, Debug)]
142pub struct RecursiveSNARK<G1, G2, C1, C2>
143where
144 G1: Group<Base = <G2 as Group>::Scalar>,
145 G2: Group<Base = <G1 as Group>::Scalar>,
146 C1: StepCircuit<G1::Scalar>,
147 C2: StepCircuit<G2::Scalar>,
148{
149 r_W_primary: RelaxedR1CSWitness<G1>,
150 r_U_primary: RelaxedR1CSInstance<G1>,
151 l_w_primary: R1CSWitness<G1>,
152 l_u_primary: R1CSInstance<G1>,
153 r_W_secondary: RelaxedR1CSWitness<G2>,
154 r_U_secondary: RelaxedR1CSInstance<G2>,
155 l_w_secondary: R1CSWitness<G2>,
156 l_u_secondary: R1CSInstance<G2>,
157 i: usize,
158 zi_primary: G1::Scalar,
159 zi_secondary: G2::Scalar,
160 _p_c1: PhantomData<C1>,
161 _p_c2: PhantomData<C2>,
162}
163
164impl<G1, G2, C1, C2> RecursiveSNARK<G1, G2, C1, C2>
165where
166 G1: Group<Base = <G2 as Group>::Scalar>,
167 G2: Group<Base = <G1 as Group>::Scalar>,
168 C1: StepCircuit<G1::Scalar>,
169 C2: StepCircuit<G2::Scalar>,
170{
171 /// Create a new `RecursiveSNARK` (or updates the provided `RecursiveSNARK`)
172 /// by executing a step of the incremental computation
173 pub fn prove_step(
174 pp: &PublicParams<G1, G2, C1, C2>,
175 recursive_snark: Option<Self>,
176 c_primary: C1,
177 c_secondary: C2,
178 z0_primary: G1::Scalar,
179 z0_secondary: G2::Scalar,
180 ) -> Result<Self, NovaError> {
181 match recursive_snark {
182 None => {
183 // base case for the primary
184 let mut cs_primary: SatisfyingAssignment<G1> = SatisfyingAssignment::new();
185 let inputs_primary: NovaAugmentedCircuitInputs<G2> = NovaAugmentedCircuitInputs::new(
186 pp.r1cs_shape_secondary.get_digest(),
187 G1::Scalar::zero(),
188 z0_primary,
189 None,
190 None,
191 None,
192 None,
193 );
194
195 let circuit_primary: NovaAugmentedCircuit<G2, C1> = NovaAugmentedCircuit::new(
196 pp.augmented_circuit_params_primary.clone(),
197 Some(inputs_primary),
198 c_primary.clone(),
199 pp.ro_consts_circuit_primary.clone(),
200 );
201 let _ = circuit_primary.synthesize(&mut cs_primary);
202 let (u_primary, w_primary) = cs_primary
203 .r1cs_instance_and_witness(&pp.r1cs_shape_primary, &pp.r1cs_gens_primary)
204 .map_err(|_e| NovaError::UnSat)?;
205
206 // base case for the secondary
207 let mut cs_secondary: SatisfyingAssignment<G2> = SatisfyingAssignment::new();
208 let inputs_secondary: NovaAugmentedCircuitInputs<G1> = NovaAugmentedCircuitInputs::new(
209 pp.r1cs_shape_primary.get_digest(),
210 G2::Scalar::zero(),
211 z0_secondary,
212 None,
213 None,
214 Some(u_primary.clone()),
215 None,
216 );
217 let circuit_secondary: NovaAugmentedCircuit<G1, C2> = NovaAugmentedCircuit::new(
218 pp.augmented_circuit_params_secondary.clone(),
219 Some(inputs_secondary),
220 c_secondary.clone(),
221 pp.ro_consts_circuit_secondary.clone(),
222 );
223 let _ = circuit_secondary.synthesize(&mut cs_secondary);
224 let (u_secondary, w_secondary) = cs_secondary
225 .r1cs_instance_and_witness(&pp.r1cs_shape_secondary, &pp.r1cs_gens_secondary)
226 .map_err(|_e| NovaError::UnSat)?;
227
228 // IVC proof for the primary circuit
229 let l_w_primary = w_primary;
230 let l_u_primary = u_primary;
231 let r_W_primary =
232 RelaxedR1CSWitness::from_r1cs_witness(&pp.r1cs_shape_primary, &l_w_primary);
233 let r_U_primary = RelaxedR1CSInstance::from_r1cs_instance(
234 &pp.r1cs_gens_primary,
235 &pp.r1cs_shape_primary,
236 &l_u_primary,
237 );
238
239 // IVC proof of the secondary circuit
240 let l_w_secondary = w_secondary;
241 let l_u_secondary = u_secondary;
242 let r_W_secondary = RelaxedR1CSWitness::<G2>::default(&pp.r1cs_shape_secondary);
243 let r_U_secondary =
244 RelaxedR1CSInstance::<G2>::default(&pp.r1cs_gens_secondary, &pp.r1cs_shape_secondary);
245
246 // Outputs of the two circuits thus far
247 let zi_primary = c_primary.output(&z0_primary);
248 let zi_secondary = c_secondary.output(&z0_secondary);
249
250 Ok(Self {
251 r_W_primary,
252 r_U_primary,
253 l_w_primary,
254 l_u_primary,
255 r_W_secondary,
256 r_U_secondary,
257 l_w_secondary,
258 l_u_secondary,
259 i: 1_usize,
260 zi_primary,
261 zi_secondary,
262 _p_c1: Default::default(),
263 _p_c2: Default::default(),
264 })
265 }
266 Some(r_snark) => {
267 // fold the secondary circuit's instance
268 let (nifs_secondary, (r_U_secondary, r_W_secondary)) = NIFS::prove(
269 &pp.r1cs_gens_secondary,
270 &pp.ro_consts_secondary,
271 &pp.r1cs_shape_secondary,
272 &r_snark.r_U_secondary,
273 &r_snark.r_W_secondary,
274 &r_snark.l_u_secondary,
275 &r_snark.l_w_secondary,
276 )?;
277
278 let mut cs_primary: SatisfyingAssignment<G1> = SatisfyingAssignment::new();
279 let inputs_primary: NovaAugmentedCircuitInputs<G2> = NovaAugmentedCircuitInputs::new(
280 pp.r1cs_shape_secondary.get_digest(),
281 G1::Scalar::from(r_snark.i as u64),
282 z0_primary,
283 Some(r_snark.zi_primary),
284 Some(r_snark.r_U_secondary.clone()),
285 Some(r_snark.l_u_secondary.clone()),
286 Some(nifs_secondary.comm_T.decompress()?),
287 );
288
289 let circuit_primary: NovaAugmentedCircuit<G2, C1> = NovaAugmentedCircuit::new(
290 pp.augmented_circuit_params_primary.clone(),
291 Some(inputs_primary),
292 c_primary.clone(),
293 pp.ro_consts_circuit_primary.clone(),
294 );
295 let _ = circuit_primary.synthesize(&mut cs_primary);
296
297 let (l_u_primary, l_w_primary) = cs_primary
298 .r1cs_instance_and_witness(&pp.r1cs_shape_primary, &pp.r1cs_gens_primary)
299 .map_err(|_e| NovaError::UnSat)?;
300
301 // fold the primary circuit's instance
302 let (nifs_primary, (r_U_primary, r_W_primary)) = NIFS::prove(
303 &pp.r1cs_gens_primary,
304 &pp.ro_consts_primary,
305 &pp.r1cs_shape_primary,
306 &r_snark.r_U_primary,
307 &r_snark.r_W_primary,
308 &l_u_primary,
309 &l_w_primary,
310 )?;
311
312 let mut cs_secondary: SatisfyingAssignment<G2> = SatisfyingAssignment::new();
313 let inputs_secondary: NovaAugmentedCircuitInputs<G1> = NovaAugmentedCircuitInputs::new(
314 pp.r1cs_shape_primary.get_digest(),
315 G2::Scalar::from(r_snark.i as u64),
316 z0_secondary,
317 Some(r_snark.zi_secondary),
318 Some(r_snark.r_U_primary.clone()),
319 Some(l_u_primary.clone()),
320 Some(nifs_primary.comm_T.decompress()?),
321 );
322
323 let circuit_secondary: NovaAugmentedCircuit<G1, C2> = NovaAugmentedCircuit::new(
324 pp.augmented_circuit_params_secondary.clone(),
325 Some(inputs_secondary),
326 c_secondary.clone(),
327 pp.ro_consts_circuit_secondary.clone(),
328 );
329 let _ = circuit_secondary.synthesize(&mut cs_secondary);
330
331 let (l_u_secondary, l_w_secondary) = cs_secondary
332 .r1cs_instance_and_witness(&pp.r1cs_shape_secondary, &pp.r1cs_gens_secondary)
333 .map_err(|_e| NovaError::UnSat)?;
334
335 // update the running instances and witnesses
336 let zi_primary = c_primary.output(&r_snark.zi_primary);
337 let zi_secondary = c_secondary.output(&r_snark.zi_secondary);
338
339 Ok(Self {
340 r_W_primary,
341 r_U_primary,
342 l_w_primary,
343 l_u_primary,
344 r_W_secondary,
345 r_U_secondary,
346 l_w_secondary,
347 l_u_secondary,
348 i: r_snark.i + 1,
349 zi_primary,
350 zi_secondary,
351 _p_c1: Default::default(),
352 _p_c2: Default::default(),
353 })
354 }
355 }
356 }
357
358 /// Verify the correctness of the `RecursiveSNARK`
359 pub fn verify(
360 &self,
361 pp: &PublicParams<G1, G2, C1, C2>,
362 num_steps: usize,
363 z0_primary: G1::Scalar,
364 z0_secondary: G2::Scalar,
365 ) -> Result<(G1::Scalar, G2::Scalar), NovaError> {
366 // number of steps cannot be zero
367 if num_steps == 0 {
368 return Err(NovaError::ProofVerifyError);
369 }
370
371 // check if the provided proof has executed num_steps
372 if self.i != num_steps {
373 return Err(NovaError::ProofVerifyError);
374 }
375
376 // check if the (relaxed) R1CS instances have two public outputs
377 if self.l_u_primary.X.len() != 2
378 || self.l_u_secondary.X.len() != 2
379 || self.r_U_primary.X.len() != 2
380 || self.r_U_secondary.X.len() != 2
381 {
382 return Err(NovaError::ProofVerifyError);
383 }
384
385 // check if the output hashes in R1CS instances point to the right running instances
386 let (hash_primary, hash_secondary) = {
387 let mut hasher = <G2 as Group>::RO::new(pp.ro_consts_secondary.clone());
388 hasher.absorb(scalar_as_base::<G2>(pp.r1cs_shape_secondary.get_digest()));
389 hasher.absorb(G1::Scalar::from(num_steps as u64));
390 hasher.absorb(z0_primary);
391 hasher.absorb(self.zi_primary);
392 self.r_U_secondary.absorb_in_ro(&mut hasher);
393
394 let mut hasher2 = <G1 as Group>::RO::new(pp.ro_consts_primary.clone());
395 hasher2.absorb(scalar_as_base::<G1>(pp.r1cs_shape_primary.get_digest()));
396 hasher2.absorb(G2::Scalar::from(num_steps as u64));
397 hasher2.absorb(z0_secondary);
398 hasher2.absorb(self.zi_secondary);
399 self.r_U_primary.absorb_in_ro(&mut hasher2);
400
401 (
402 hasher.squeeze(NUM_HASH_BITS),
403 hasher2.squeeze(NUM_HASH_BITS),
404 )
405 };
406
407 if hash_primary != scalar_as_base::<G1>(self.l_u_primary.X[1])
408 || hash_secondary != scalar_as_base::<G2>(self.l_u_secondary.X[1])
409 {
410 return Err(NovaError::ProofVerifyError);
411 }
412
413 // check the satisfiability of the provided instances
414 let ((res_r_primary, res_l_primary), (res_r_secondary, res_l_secondary)) = rayon::join(
415 || {
416 rayon::join(
417 || {
418 pp.r1cs_shape_primary.is_sat_relaxed(
419 &pp.r1cs_gens_primary,
420 &self.r_U_primary,
421 &self.r_W_primary,
422 )
423 },
424 || {
425 pp.r1cs_shape_primary.is_sat(
426 &pp.r1cs_gens_primary,
427 &self.l_u_primary,
428 &self.l_w_primary,
429 )
430 },
431 )
432 },
433 || {
434 rayon::join(
435 || {
436 pp.r1cs_shape_secondary.is_sat_relaxed(
437 &pp.r1cs_gens_secondary,
438 &self.r_U_secondary,
439 &self.r_W_secondary,
440 )
441 },
442 || {
443 pp.r1cs_shape_secondary.is_sat(
444 &pp.r1cs_gens_secondary,
445 &self.l_u_secondary,
446 &self.l_w_secondary,
447 )
448 },
449 )
450 },
451 );
452
453 // check the returned res objects
454 res_r_primary?;
455 res_l_primary?;
456 res_r_secondary?;
457 res_l_secondary?;
458
459 Ok((self.zi_primary, self.zi_secondary))
460 }
461}
462
463/// A SNARK that proves the knowledge of a valid `RecursiveSNARK`
464#[derive(Clone, Debug)]
465pub struct CompressedSNARK<G1, G2, C1, C2, S1, S2>
466where
467 G1: Group<Base = <G2 as Group>::Scalar>,
468 G2: Group<Base = <G1 as Group>::Scalar>,
469 C1: StepCircuit<G1::Scalar>,
470 C2: StepCircuit<G2::Scalar>,
471 S1: RelaxedR1CSSNARKTrait<G1>,
472 S2: RelaxedR1CSSNARKTrait<G2>,
473{
474 r_U_primary: RelaxedR1CSInstance<G1>,
475 l_u_primary: R1CSInstance<G1>,
476 nifs_primary: NIFS<G1>,
477 f_W_snark_primary: S1,
478
479 r_U_secondary: RelaxedR1CSInstance<G2>,
480 l_u_secondary: R1CSInstance<G2>,
481 nifs_secondary: NIFS<G2>,
482 f_W_snark_secondary: S2,
483
484 zn_primary: G1::Scalar,
485 zn_secondary: G2::Scalar,
486
487 _p_c1: PhantomData<C1>,
488 _p_c2: PhantomData<C2>,
489}
490
491impl<G1, G2, C1, C2, S1, S2> CompressedSNARK<G1, G2, C1, C2, S1, S2>
492where
493 G1: Group<Base = <G2 as Group>::Scalar>,
494 G2: Group<Base = <G1 as Group>::Scalar>,
495 C1: StepCircuit<G1::Scalar>,
496 C2: StepCircuit<G2::Scalar>,
497 S1: RelaxedR1CSSNARKTrait<G1>,
498 S2: RelaxedR1CSSNARKTrait<G2>,
499{
500 /// Create a new `CompressedSNARK`
501 pub fn prove(
502 pp: &PublicParams<G1, G2, C1, C2>,
503 recursive_snark: &RecursiveSNARK<G1, G2, C1, C2>,
504 ) -> Result<Self, NovaError> {
505 let (res_primary, res_secondary) = rayon::join(
506 // fold the primary circuit's instance
507 || {
508 NIFS::prove(
509 &pp.r1cs_gens_primary,
510 &pp.ro_consts_primary,
511 &pp.r1cs_shape_primary,
512 &recursive_snark.r_U_primary,
513 &recursive_snark.r_W_primary,
514 &recursive_snark.l_u_primary,
515 &recursive_snark.l_w_primary,
516 )
517 },
518 || {
519 // fold the secondary circuit's instance
520 NIFS::prove(
521 &pp.r1cs_gens_secondary,
522 &pp.ro_consts_secondary,
523 &pp.r1cs_shape_secondary,
524 &recursive_snark.r_U_secondary,
525 &recursive_snark.r_W_secondary,
526 &recursive_snark.l_u_secondary,
527 &recursive_snark.l_w_secondary,
528 )
529 },
530 );
531
532 let (nifs_primary, (f_U_primary, f_W_primary)) = res_primary?;
533 let (nifs_secondary, (f_U_secondary, f_W_secondary)) = res_secondary?;
534
535 // produce a prover key for the SNARK
536 let (pk_primary, pk_secondary) = rayon::join(
537 || S1::prover_key(&pp.r1cs_gens_primary, &pp.r1cs_shape_padded_primary),
538 || S2::prover_key(&pp.r1cs_gens_secondary, &pp.r1cs_shape_padded_secondary),
539 );
540
541 // create SNARKs proving the knowledge of f_W_primary and f_W_secondary
542 let (f_W_snark_primary, f_W_snark_secondary) = rayon::join(
543 || {
544 S1::prove(
545 &pk_primary,
546 &f_U_primary,
547 &f_W_primary.pad(&pp.r1cs_shape_padded_primary), // pad the witness since shape was padded
548 )
549 },
550 || {
551 S2::prove(
552 &pk_secondary,
553 &f_U_secondary,
554 &f_W_secondary.pad(&pp.r1cs_shape_padded_secondary), // pad the witness since the shape was padded
555 )
556 },
557 );
558
559 Ok(Self {
560 r_U_primary: recursive_snark.r_U_primary.clone(),
561 l_u_primary: recursive_snark.l_u_primary.clone(),
562 nifs_primary,
563 f_W_snark_primary: f_W_snark_primary?,
564
565 r_U_secondary: recursive_snark.r_U_secondary.clone(),
566 l_u_secondary: recursive_snark.l_u_secondary.clone(),
567 nifs_secondary,
568 f_W_snark_secondary: f_W_snark_secondary?,
569
570 zn_primary: recursive_snark.zi_primary,
571 zn_secondary: recursive_snark.zi_secondary,
572
573 _p_c1: Default::default(),
574 _p_c2: Default::default(),
575 })
576 }
577
578 /// Verify the correctness of the `CompressedSNARK`
579 pub fn verify(
580 &self,
581 pp: &PublicParams<G1, G2, C1, C2>,
582 num_steps: usize,
583 z0_primary: G1::Scalar,
584 z0_secondary: G2::Scalar,
585 ) -> Result<(G1::Scalar, G2::Scalar), NovaError> {
586 // number of steps cannot be zero
587 if num_steps == 0 {
588 return Err(NovaError::ProofVerifyError);
589 }
590
591 // check if the (relaxed) R1CS instances have two public outputs
592 if self.l_u_primary.X.len() != 2
593 || self.l_u_secondary.X.len() != 2
594 || self.r_U_primary.X.len() != 2
595 || self.r_U_secondary.X.len() != 2
596 {
597 return Err(NovaError::ProofVerifyError);
598 }
599
600 // check if the output hashes in R1CS instances point to the right running instances
601 let (hash_primary, hash_secondary) = {
602 let mut hasher = <G2 as Group>::RO::new(pp.ro_consts_secondary.clone());
603 hasher.absorb(scalar_as_base::<G2>(pp.r1cs_shape_secondary.get_digest()));
604 hasher.absorb(G1::Scalar::from(num_steps as u64));
605 hasher.absorb(z0_primary);
606 hasher.absorb(self.zn_primary);
607 self.r_U_secondary.absorb_in_ro(&mut hasher);
608
609 let mut hasher2 = <G1 as Group>::RO::new(pp.ro_consts_primary.clone());
610 hasher2.absorb(scalar_as_base::<G1>(pp.r1cs_shape_primary.get_digest()));
611 hasher2.absorb(G2::Scalar::from(num_steps as u64));
612 hasher2.absorb(z0_secondary);
613 hasher2.absorb(self.zn_secondary);
614 self.r_U_primary.absorb_in_ro(&mut hasher2);
615
616 (
617 hasher.squeeze(NUM_HASH_BITS),
618 hasher2.squeeze(NUM_HASH_BITS),
619 )
620 };
621
622 if hash_primary != scalar_as_base::<G1>(self.l_u_primary.X[1])
623 || hash_secondary != scalar_as_base::<G2>(self.l_u_secondary.X[1])
624 {
625 return Err(NovaError::ProofVerifyError);
626 }
627
628 // fold the running instance and last instance to get a folded instance
629 let f_U_primary = self.nifs_primary.verify(
630 &pp.ro_consts_primary,
631 &pp.r1cs_shape_primary,
632 &self.r_U_primary,
633 &self.l_u_primary,
634 )?;
635 let f_U_secondary = self.nifs_secondary.verify(
636 &pp.ro_consts_secondary,
637 &pp.r1cs_shape_secondary,
638 &self.r_U_secondary,
639 &self.l_u_secondary,
640 )?;
641
642 // produce a verifier key for the SNARK
643 let (vk_primary, vk_secondary) = rayon::join(
644 || S1::verifier_key(&pp.r1cs_gens_primary, &pp.r1cs_shape_padded_primary),
645 || S2::verifier_key(&pp.r1cs_gens_secondary, &pp.r1cs_shape_padded_secondary),
646 );
647
648 // check the satisfiability of the folded instances using SNARKs proving the knowledge of their satisfying witnesses
649 let (res_primary, res_secondary) = rayon::join(
650 || self.f_W_snark_primary.verify(&vk_primary, &f_U_primary),
651 || {
652 self
653 .f_W_snark_secondary
654 .verify(&vk_secondary, &f_U_secondary)
655 },
656 );
657
658 res_primary?;
659 res_secondary?;
660
661 Ok((self.zn_primary, self.zn_secondary))
662 }
663}
664
665#[cfg(test)]
666mod tests {
667 use super::*;
668 type G1 = pasta_curves::pallas::Point;
669 type G2 = pasta_curves::vesta::Point;
670 type S1 = spartan_with_ipa_pc::RelaxedR1CSSNARK<G1>;
671 type S2 = spartan_with_ipa_pc::RelaxedR1CSSNARK<G2>;
672 use ::bellperson::{gadgets::num::AllocatedNum, ConstraintSystem, SynthesisError};
673 use core::marker::PhantomData;
674 use ff::PrimeField;
675 use traits::circuit::TrivialTestCircuit;
676
677 #[derive(Clone, Debug, Default)]
678 struct CubicCircuit<F: PrimeField> {
679 _p: PhantomData<F>,
680 }
681
682 impl<F> StepCircuit<F> for CubicCircuit<F>
683 where
684 F: PrimeField,
685 {
686 fn synthesize<CS: ConstraintSystem<F>>(
687 &self,
688 cs: &mut CS,
689 z: AllocatedNum<F>,
690 ) -> Result<AllocatedNum<F>, SynthesisError> {
691 // Consider a cubic equation: `x^3 + x + 5 = y`, where `x` and `y` are respectively the input and output.
692 let x = z;
693 let x_sq = x.square(cs.namespace(|| "x_sq"))?;
694 let x_cu = x_sq.mul(cs.namespace(|| "x_cu"), &x)?;
695 let y = AllocatedNum::alloc(cs.namespace(|| "y"), || {
696 Ok(x_cu.get_value().unwrap() + x.get_value().unwrap() + F::from(5u64))
697 })?;
698
699 cs.enforce(
700 || "y = x^3 + x + 5",
701 |lc| {
702 lc + x_cu.get_variable()
703 + x.get_variable()
704 + CS::one()
705 + CS::one()
706 + CS::one()
707 + CS::one()
708 + CS::one()
709 },
710 |lc| lc + CS::one(),
711 |lc| lc + y.get_variable(),
712 );
713
714 Ok(y)
715 }
716
717 fn output(&self, z: &F) -> F {
718 *z * *z * *z + z + F::from(5u64)
719 }
720 }
721
722 #[test]
723 fn test_ivc_trivial() {
724 // produce public parameters
725 let pp = PublicParams::<
726 G1,
727 G2,
728 TrivialTestCircuit<<G1 as Group>::Scalar>,
729 TrivialTestCircuit<<G2 as Group>::Scalar>,
730 >::setup(TrivialTestCircuit::default(), TrivialTestCircuit::default());
731
732 let num_steps = 1;
733
734 // produce a recursive SNARK
735 let res = RecursiveSNARK::prove_step(
736 &pp,
737 None,
738 TrivialTestCircuit::default(),
739 TrivialTestCircuit::default(),
740 <G1 as Group>::Scalar::zero(),
741 <G2 as Group>::Scalar::zero(),
742 );
743 assert!(res.is_ok());
744 let recursive_snark = res.unwrap();
745
746 // verify the recursive SNARK
747 let res = recursive_snark.verify(
748 &pp,
749 num_steps,
750 <G1 as Group>::Scalar::zero(),
751 <G2 as Group>::Scalar::zero(),
752 );
753 assert!(res.is_ok());
754 }
755
756 #[test]
757 fn test_ivc_nontrivial() {
758 let circuit_primary = TrivialTestCircuit::default();
759 let circuit_secondary = CubicCircuit::default();
760
761 // produce public parameters
762 let pp = PublicParams::<
763 G1,
764 G2,
765 TrivialTestCircuit<<G1 as Group>::Scalar>,
766 CubicCircuit<<G2 as Group>::Scalar>,
767 >::setup(circuit_primary.clone(), circuit_secondary.clone());
768
769 let num_steps = 3;
770
771 // produce a recursive SNARK
772 let mut recursive_snark: Option<
773 RecursiveSNARK<
774 G1,
775 G2,
776 TrivialTestCircuit<<G1 as Group>::Scalar>,
777 CubicCircuit<<G2 as Group>::Scalar>,
778 >,
779 > = None;
780
781 for i in 0..num_steps {
782 let res = RecursiveSNARK::prove_step(
783 &pp,
784 recursive_snark,
785 circuit_primary.clone(),
786 circuit_secondary.clone(),
787 <G1 as Group>::Scalar::one(),
788 <G2 as Group>::Scalar::zero(),
789 );
790 assert!(res.is_ok());
791 let recursive_snark_unwrapped = res.unwrap();
792
793 // verify the recursive snark at each step of recursion
794 let res = recursive_snark_unwrapped.verify(
795 &pp,
796 i + 1,
797 <G1 as Group>::Scalar::one(),
798 <G2 as Group>::Scalar::zero(),
799 );
800 assert!(res.is_ok());
801
802 // set the running variable for the next iteration
803 recursive_snark = Some(recursive_snark_unwrapped);
804 }
805
806 assert!(recursive_snark.is_some());
807 let recursive_snark = recursive_snark.unwrap();
808
809 // verify the recursive SNARK
810 let res = recursive_snark.verify(
811 &pp,
812 num_steps,
813 <G1 as Group>::Scalar::one(),
814 <G2 as Group>::Scalar::zero(),
815 );
816 assert!(res.is_ok());
817
818 let (zn_primary, zn_secondary) = res.unwrap();
819
820 // sanity: check the claimed output with a direct computation of the same
821 assert_eq!(zn_primary, <G1 as Group>::Scalar::one());
822 let mut zn_secondary_direct = <G2 as Group>::Scalar::zero();
823 for _i in 0..num_steps {
824 zn_secondary_direct = CubicCircuit::default().output(&zn_secondary_direct);
825 }
826 assert_eq!(zn_secondary, zn_secondary_direct);
827 assert_eq!(zn_secondary, <G2 as Group>::Scalar::from(2460515u64));
828 }
829
830 #[test]
831 fn test_ivc_nontrivial_with_compression() {
832 let circuit_primary = TrivialTestCircuit::default();
833 let circuit_secondary = CubicCircuit::default();
834
835 // produce public parameters
836 let pp = PublicParams::<
837 G1,
838 G2,
839 TrivialTestCircuit<<G1 as Group>::Scalar>,
840 CubicCircuit<<G2 as Group>::Scalar>,
841 >::setup(circuit_primary.clone(), circuit_secondary.clone());
842
843 let num_steps = 3;
844
845 // produce a recursive SNARK
846 let mut recursive_snark: Option<
847 RecursiveSNARK<
848 G1,
849 G2,
850 TrivialTestCircuit<<G1 as Group>::Scalar>,
851 CubicCircuit<<G2 as Group>::Scalar>,
852 >,
853 > = None;
854
855 for _i in 0..num_steps {
856 let res = RecursiveSNARK::prove_step(
857 &pp,
858 recursive_snark,
859 circuit_primary.clone(),
860 circuit_secondary.clone(),
861 <G1 as Group>::Scalar::one(),
862 <G2 as Group>::Scalar::zero(),
863 );
864 assert!(res.is_ok());
865 recursive_snark = Some(res.unwrap());
866 }
867
868 assert!(recursive_snark.is_some());
869 let recursive_snark = recursive_snark.unwrap();
870
871 // verify the recursive SNARK
872 let res = recursive_snark.verify(
873 &pp,
874 num_steps,
875 <G1 as Group>::Scalar::one(),
876 <G2 as Group>::Scalar::zero(),
877 );
878 assert!(res.is_ok());
879
880 let (zn_primary, zn_secondary) = res.unwrap();
881
882 // sanity: check the claimed output with a direct computation of the same
883 assert_eq!(zn_primary, <G1 as Group>::Scalar::one());
884 let mut zn_secondary_direct = <G2 as Group>::Scalar::zero();
885 for _i in 0..num_steps {
886 zn_secondary_direct = CubicCircuit::default().output(&zn_secondary_direct);
887 }
888 assert_eq!(zn_secondary, zn_secondary_direct);
889 assert_eq!(zn_secondary, <G2 as Group>::Scalar::from(2460515u64));
890
891 // produce a compressed SNARK
892 let res = CompressedSNARK::<_, _, _, _, S1, S2>::prove(&pp, &recursive_snark);
893 assert!(res.is_ok());
894 let compressed_snark = res.unwrap();
895
896 // verify the compressed SNARK
897 let res = compressed_snark.verify(
898 &pp,
899 num_steps,
900 <G1 as Group>::Scalar::one(),
901 <G2 as Group>::Scalar::zero(),
902 );
903 assert!(res.is_ok());
904 }
905
906 #[test]
907 fn test_ivc_nondet_with_compression() {
908 // y is a non-deterministic advice representing the fifth root of the input at a step.
909 #[derive(Clone, Debug)]
910 struct FifthRootCheckingCircuit<F: PrimeField> {
911 y: F,
912 }
913
914 impl<F> FifthRootCheckingCircuit<F>
915 where
916 F: PrimeField,
917 {
918 fn new(num_steps: usize) -> (F, Vec<Self>) {
919 let mut powers = Vec::new();
920 let rng = &mut rand::rngs::OsRng;
921 let mut seed = F::random(rng);
922 for _i in 0..num_steps + 1 {
923 let mut power = seed;
924 power = power.square();
925 power = power.square();
926 power *= seed;
927
928 powers.push(Self { y: power });
929
930 seed = power;
931 }
932
933 // reverse the powers to get roots
934 let roots = powers.into_iter().rev().collect::<Vec<Self>>();
935 (roots[0].y, roots[1..].to_vec())
936 }
937 }
938
939 impl<F> StepCircuit<F> for FifthRootCheckingCircuit<F>
940 where
941 F: PrimeField,
942 {
943 fn synthesize<CS: ConstraintSystem<F>>(
944 &self,
945 cs: &mut CS,
946 z: AllocatedNum<F>,
947 ) -> Result<AllocatedNum<F>, SynthesisError> {
948 let x = z;
949
950 // we allocate a variable and set it to the provided non-derministic advice.
951 let y = AllocatedNum::alloc(cs.namespace(|| "y"), || Ok(self.y))?;
952
953 // We now check if y = x^{1/5} by checking if y^5 = x
954 let y_sq = y.square(cs.namespace(|| "y_sq"))?;
955 let y_quad = y_sq.square(cs.namespace(|| "y_quad"))?;
956 let y_pow_5 = y_quad.mul(cs.namespace(|| "y_fifth"), &y)?;
957
958 cs.enforce(
959 || "y^5 = x",
960 |lc| lc + y_pow_5.get_variable(),
961 |lc| lc + CS::one(),
962 |lc| lc + x.get_variable(),
963 );
964
965 Ok(y)
966 }
967
968 fn output(&self, z: &F) -> F {
969 // sanity check
970 let x = *z;
971 let y_pow_5 = {
972 let y = self.y;
973 let y_sq = y.square();
974 let y_quad = y_sq.square();
975 y_quad * self.y
976 };
977 assert_eq!(x, y_pow_5);
978
979 // return non-deterministic advice
980 // as the output of the step
981 self.y
982 }
983 }
984
985 let circuit_primary = FifthRootCheckingCircuit {
986 y: <G1 as Group>::Scalar::zero(),
987 };
988
989 let circuit_secondary = TrivialTestCircuit::default();
990
991 // produce public parameters
992 let pp = PublicParams::<
993 G1,
994 G2,
995 FifthRootCheckingCircuit<<G1 as Group>::Scalar>,
996 TrivialTestCircuit<<G2 as Group>::Scalar>,
997 >::setup(circuit_primary, circuit_secondary.clone());
998
999 let num_steps = 3;
1000
1001 // produce non-deterministic advice
1002 let (z0_primary, roots) = FifthRootCheckingCircuit::new(num_steps);
1003 let z0_secondary = <G2 as Group>::Scalar::zero();
1004
1005 // produce a recursive SNARK
1006 let mut recursive_snark: Option<
1007 RecursiveSNARK<
1008 G1,
1009 G2,
1010 FifthRootCheckingCircuit<<G1 as Group>::Scalar>,
1011 TrivialTestCircuit<<G2 as Group>::Scalar>,
1012 >,
1013 > = None;
1014
1015 for circuit_primary in roots.iter().take(num_steps) {
1016 let res = RecursiveSNARK::prove_step(
1017 &pp,
1018 recursive_snark,
1019 circuit_primary.clone(),
1020 circuit_secondary.clone(),
1021 z0_primary,
1022 z0_secondary,
1023 );
1024 assert!(res.is_ok());
1025 recursive_snark = Some(res.unwrap());
1026 }
1027
1028 assert!(recursive_snark.is_some());
1029 let recursive_snark = recursive_snark.unwrap();
1030
1031 // verify the recursive SNARK
1032 let res = recursive_snark.verify(&pp, num_steps, z0_primary, z0_secondary);
1033 assert!(res.is_ok());
1034
1035 // produce a compressed SNARK
1036 let res = CompressedSNARK::<_, _, _, _, S1, S2>::prove(&pp, &recursive_snark);
1037 assert!(res.is_ok());
1038 let compressed_snark = res.unwrap();
1039
1040 // verify the compressed SNARK
1041 let res = compressed_snark.verify(&pp, num_steps, z0_primary, z0_secondary);
1042 assert!(res.is_ok());
1043 }
1044
1045 #[test]
1046 fn test_ivc_base() {
1047 // produce public parameters
1048 let pp = PublicParams::<
1049 G1,
1050 G2,
1051 TrivialTestCircuit<<G1 as Group>::Scalar>,
1052 CubicCircuit<<G2 as Group>::Scalar>,
1053 >::setup(TrivialTestCircuit::default(), CubicCircuit::default());
1054
1055 let num_steps = 1;
1056
1057 // produce a recursive SNARK
1058 let res = RecursiveSNARK::prove_step(
1059 &pp,
1060 None,
1061 TrivialTestCircuit::default(),
1062 CubicCircuit::default(),
1063 <G1 as Group>::Scalar::one(),
1064 <G2 as Group>::Scalar::zero(),
1065 );
1066 assert!(res.is_ok());
1067 let recursive_snark = res.unwrap();
1068
1069 // verify the recursive SNARK
1070 let res = recursive_snark.verify(
1071 &pp,
1072 num_steps,
1073 <G1 as Group>::Scalar::one(),
1074 <G2 as Group>::Scalar::zero(),
1075 );
1076 assert!(res.is_ok());
1077
1078 let (zn_primary, zn_secondary) = res.unwrap();
1079
1080 assert_eq!(zn_primary, <G1 as Group>::Scalar::one());
1081 assert_eq!(zn_secondary, <G2 as Group>::Scalar::from(5u64));
1082 }
1083}