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