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