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 r_W_secondary: RelaxedR1CSWitness<G2>,
179 r_U_secondary: RelaxedR1CSInstance<G2>,
180 l_w_secondary: R1CSWitness<G2>,
181 l_u_secondary: R1CSInstance<G2>,
182 i: usize,
183 zi_primary: Vec<G1::Scalar>,
184 zi_secondary: Vec<G2::Scalar>,
185 _p_c1: PhantomData<C1>,
186 _p_c2: PhantomData<C2>,
187}
188
189impl<G1, G2, C1, C2> RecursiveSNARK<G1, G2, C1, C2>
190where
191 G1: Group<Base = <G2 as Group>::Scalar>,
192 G2: Group<Base = <G1 as Group>::Scalar>,
193 C1: StepCircuit<G1::Scalar>,
194 C2: StepCircuit<G2::Scalar>,
195{
196 /// Create a new `RecursiveSNARK` (or updates the provided `RecursiveSNARK`)
197 /// by executing a step of the incremental computation
198 pub fn prove_step(
199 pp: &PublicParams<G1, G2, C1, C2>,
200 recursive_snark: Option<Self>,
201 c_primary: C1,
202 c_secondary: C2,
203 z0_primary: Vec<G1::Scalar>,
204 z0_secondary: Vec<G2::Scalar>,
205 ) -> Result<Self, NovaError> {
206 if z0_primary.len() != pp.F_arity_primary || z0_secondary.len() != pp.F_arity_secondary {
207 return Err(NovaError::InvalidInitialInputLength);
208 }
209
210 match recursive_snark {
211 None => {
212 // base case for the primary
213 let mut cs_primary: SatisfyingAssignment<G1> = SatisfyingAssignment::new();
214 let inputs_primary: NovaAugmentedCircuitInputs<G2> = NovaAugmentedCircuitInputs::new(
215 scalar_as_base::<G1>(pp.digest),
216 G1::Scalar::ZERO,
217 z0_primary.clone(),
218 None,
219 None,
220 None,
221 None,
222 );
223
224 let circuit_primary: NovaAugmentedCircuit<G2, C1> = NovaAugmentedCircuit::new(
225 pp.augmented_circuit_params_primary.clone(),
226 Some(inputs_primary),
227 c_primary.clone(),
228 pp.ro_consts_circuit_primary.clone(),
229 );
230 let _ = circuit_primary.synthesize(&mut cs_primary);
231 let (u_primary, w_primary) = cs_primary
232 .r1cs_instance_and_witness(&pp.r1cs_shape_primary, &pp.ck_primary)
233 .map_err(|_e| NovaError::UnSat)?;
234
235 // base case for the secondary
236 let mut cs_secondary: SatisfyingAssignment<G2> = SatisfyingAssignment::new();
237 let inputs_secondary: NovaAugmentedCircuitInputs<G1> = NovaAugmentedCircuitInputs::new(
238 pp.digest,
239 G2::Scalar::ZERO,
240 z0_secondary.clone(),
241 None,
242 None,
243 Some(u_primary.clone()),
244 None,
245 );
246 let circuit_secondary: NovaAugmentedCircuit<G1, C2> = NovaAugmentedCircuit::new(
247 pp.augmented_circuit_params_secondary.clone(),
248 Some(inputs_secondary),
249 c_secondary.clone(),
250 pp.ro_consts_circuit_secondary.clone(),
251 );
252 let _ = circuit_secondary.synthesize(&mut cs_secondary);
253 let (u_secondary, w_secondary) = cs_secondary
254 .r1cs_instance_and_witness(&pp.r1cs_shape_secondary, &pp.ck_secondary)
255 .map_err(|_e| NovaError::UnSat)?;
256
257 // IVC proof for the primary circuit
258 let l_w_primary = w_primary;
259 let l_u_primary = u_primary;
260 let r_W_primary =
261 RelaxedR1CSWitness::from_r1cs_witness(&pp.r1cs_shape_primary, &l_w_primary);
262 let r_U_primary = RelaxedR1CSInstance::from_r1cs_instance(
263 &pp.ck_primary,
264 &pp.r1cs_shape_primary,
265 &l_u_primary,
266 );
267
268 // IVC proof of the secondary circuit
269 let l_w_secondary = w_secondary;
270 let l_u_secondary = u_secondary;
271 let r_W_secondary = RelaxedR1CSWitness::<G2>::default(&pp.r1cs_shape_secondary);
272 let r_U_secondary =
273 RelaxedR1CSInstance::<G2>::default(&pp.ck_secondary, &pp.r1cs_shape_secondary);
274
275 // Outputs of the two circuits thus far
276 let zi_primary = c_primary.output(&z0_primary);
277 let zi_secondary = c_secondary.output(&z0_secondary);
278
279 if zi_primary.len() != pp.F_arity_primary || zi_secondary.len() != pp.F_arity_secondary {
280 return Err(NovaError::InvalidStepOutputLength);
281 }
282
283 Ok(Self {
284 r_W_primary,
285 r_U_primary,
286 r_W_secondary,
287 r_U_secondary,
288 l_w_secondary,
289 l_u_secondary,
290 i: 1_usize,
291 zi_primary,
292 zi_secondary,
293 _p_c1: Default::default(),
294 _p_c2: Default::default(),
295 })
296 }
297 Some(r_snark) => {
298 // fold the secondary circuit's instance
299 let (nifs_secondary, (r_U_secondary, r_W_secondary)) = NIFS::prove(
300 &pp.ck_secondary,
301 &pp.ro_consts_secondary,
302 &scalar_as_base::<G1>(pp.digest),
303 &pp.r1cs_shape_secondary,
304 &r_snark.r_U_secondary,
305 &r_snark.r_W_secondary,
306 &r_snark.l_u_secondary,
307 &r_snark.l_w_secondary,
308 )?;
309
310 let mut cs_primary: SatisfyingAssignment<G1> = SatisfyingAssignment::new();
311 let inputs_primary: NovaAugmentedCircuitInputs<G2> = NovaAugmentedCircuitInputs::new(
312 scalar_as_base::<G1>(pp.digest),
313 G1::Scalar::from(r_snark.i as u64),
314 z0_primary,
315 Some(r_snark.zi_primary.clone()),
316 Some(r_snark.r_U_secondary.clone()),
317 Some(r_snark.l_u_secondary.clone()),
318 Some(Commitment::<G2>::decompress(&nifs_secondary.comm_T)?),
319 );
320
321 let circuit_primary: NovaAugmentedCircuit<G2, C1> = NovaAugmentedCircuit::new(
322 pp.augmented_circuit_params_primary.clone(),
323 Some(inputs_primary),
324 c_primary.clone(),
325 pp.ro_consts_circuit_primary.clone(),
326 );
327 let _ = circuit_primary.synthesize(&mut cs_primary);
328
329 let (l_u_primary, l_w_primary) = cs_primary
330 .r1cs_instance_and_witness(&pp.r1cs_shape_primary, &pp.ck_primary)
331 .map_err(|_e| NovaError::UnSat)?;
332
333 // fold the primary circuit's instance
334 let (nifs_primary, (r_U_primary, r_W_primary)) = NIFS::prove(
335 &pp.ck_primary,
336 &pp.ro_consts_primary,
337 &pp.digest,
338 &pp.r1cs_shape_primary,
339 &r_snark.r_U_primary,
340 &r_snark.r_W_primary,
341 &l_u_primary,
342 &l_w_primary,
343 )?;
344
345 let mut cs_secondary: SatisfyingAssignment<G2> = SatisfyingAssignment::new();
346 let inputs_secondary: NovaAugmentedCircuitInputs<G1> = NovaAugmentedCircuitInputs::new(
347 pp.digest,
348 G2::Scalar::from(r_snark.i as u64),
349 z0_secondary,
350 Some(r_snark.zi_secondary.clone()),
351 Some(r_snark.r_U_primary.clone()),
352 Some(l_u_primary),
353 Some(Commitment::<G1>::decompress(&nifs_primary.comm_T)?),
354 );
355
356 let circuit_secondary: NovaAugmentedCircuit<G1, C2> = NovaAugmentedCircuit::new(
357 pp.augmented_circuit_params_secondary.clone(),
358 Some(inputs_secondary),
359 c_secondary.clone(),
360 pp.ro_consts_circuit_secondary.clone(),
361 );
362 let _ = circuit_secondary.synthesize(&mut cs_secondary);
363
364 let (l_u_secondary, l_w_secondary) = cs_secondary
365 .r1cs_instance_and_witness(&pp.r1cs_shape_secondary, &pp.ck_secondary)
366 .map_err(|_e| NovaError::UnSat)?;
367
368 // update the running instances and witnesses
369 let zi_primary = c_primary.output(&r_snark.zi_primary);
370 let zi_secondary = c_secondary.output(&r_snark.zi_secondary);
371
372 Ok(Self {
373 r_W_primary,
374 r_U_primary,
375 r_W_secondary,
376 r_U_secondary,
377 l_w_secondary,
378 l_u_secondary,
379 i: r_snark.i + 1,
380 zi_primary,
381 zi_secondary,
382 _p_c1: Default::default(),
383 _p_c2: Default::default(),
384 })
385 }
386 }
387 }
388
389 /// Verify the correctness of the `RecursiveSNARK`
390 pub fn verify(
391 &self,
392 pp: &PublicParams<G1, G2, C1, C2>,
393 num_steps: usize,
394 z0_primary: Vec<G1::Scalar>,
395 z0_secondary: Vec<G2::Scalar>,
396 ) -> Result<(Vec<G1::Scalar>, Vec<G2::Scalar>), NovaError> {
397 // number of steps cannot be zero
398 if num_steps == 0 {
399 return Err(NovaError::ProofVerifyError);
400 }
401
402 // check if the provided proof has executed num_steps
403 if self.i != num_steps {
404 return Err(NovaError::ProofVerifyError);
405 }
406
407 // check if the (relaxed) R1CS instances have two public outputs
408 if self.l_u_secondary.X.len() != 2
409 || self.r_U_primary.X.len() != 2
410 || self.r_U_secondary.X.len() != 2
411 {
412 return Err(NovaError::ProofVerifyError);
413 }
414
415 // check if the output hashes in R1CS instances point to the right running instances
416 let (hash_primary, hash_secondary) = {
417 let mut hasher = <G2 as Group>::RO::new(
418 pp.ro_consts_secondary.clone(),
419 NUM_FE_WITHOUT_IO_FOR_CRHF + 2 * pp.F_arity_primary,
420 );
421 hasher.absorb(pp.digest);
422 hasher.absorb(G1::Scalar::from(num_steps as u64));
423 for e in &z0_primary {
424 hasher.absorb(*e);
425 }
426 for e in &self.zi_primary {
427 hasher.absorb(*e);
428 }
429 self.r_U_secondary.absorb_in_ro(&mut hasher);
430
431 let mut hasher2 = <G1 as Group>::RO::new(
432 pp.ro_consts_primary.clone(),
433 NUM_FE_WITHOUT_IO_FOR_CRHF + 2 * pp.F_arity_secondary,
434 );
435 hasher2.absorb(scalar_as_base::<G1>(pp.digest));
436 hasher2.absorb(G2::Scalar::from(num_steps as u64));
437 for e in &z0_secondary {
438 hasher2.absorb(*e);
439 }
440 for e in &self.zi_secondary {
441 hasher2.absorb(*e);
442 }
443 self.r_U_primary.absorb_in_ro(&mut hasher2);
444
445 (
446 hasher.squeeze(NUM_HASH_BITS),
447 hasher2.squeeze(NUM_HASH_BITS),
448 )
449 };
450
451 if hash_primary != self.l_u_secondary.X[0]
452 || hash_secondary != scalar_as_base::<G2>(self.l_u_secondary.X[1])
453 {
454 return Err(NovaError::ProofVerifyError);
455 }
456
457 // check the satisfiability of the provided instances
458 let (res_r_primary, (res_r_secondary, res_l_secondary)) = rayon::join(
459 || {
460 pp.r1cs_shape_primary
461 .is_sat_relaxed(&pp.ck_primary, &self.r_U_primary, &self.r_W_primary)
462 },
463 || {
464 rayon::join(
465 || {
466 pp.r1cs_shape_secondary.is_sat_relaxed(
467 &pp.ck_secondary,
468 &self.r_U_secondary,
469 &self.r_W_secondary,
470 )
471 },
472 || {
473 pp.r1cs_shape_secondary.is_sat(
474 &pp.ck_secondary,
475 &self.l_u_secondary,
476 &self.l_w_secondary,
477 )
478 },
479 )
480 },
481 );
482
483 // check the returned res objects
484 res_r_primary?;
485 res_r_secondary?;
486 res_l_secondary?;
487
488 Ok((self.zi_primary.clone(), self.zi_secondary.clone()))
489 }
490}
491
492/// A type that holds the prover key for `CompressedSNARK`
493#[derive(Clone, Debug, Serialize, Deserialize)]
494#[serde(bound = "")]
495pub struct ProverKey<G1, G2, C1, C2, S1, S2>
496where
497 G1: Group<Base = <G2 as Group>::Scalar>,
498 G2: Group<Base = <G1 as Group>::Scalar>,
499 C1: StepCircuit<G1::Scalar>,
500 C2: StepCircuit<G2::Scalar>,
501 S1: RelaxedR1CSSNARKTrait<G1>,
502 S2: RelaxedR1CSSNARKTrait<G2>,
503{
504 pk_primary: S1::ProverKey,
505 pk_secondary: S2::ProverKey,
506 _p_c1: PhantomData<C1>,
507 _p_c2: PhantomData<C2>,
508}
509
510/// A type that holds the verifier key for `CompressedSNARK`
511#[derive(Clone, Serialize, Deserialize)]
512#[serde(bound = "")]
513pub struct VerifierKey<G1, G2, C1, C2, S1, S2>
514where
515 G1: Group<Base = <G2 as Group>::Scalar>,
516 G2: Group<Base = <G1 as Group>::Scalar>,
517 C1: StepCircuit<G1::Scalar>,
518 C2: StepCircuit<G2::Scalar>,
519 S1: RelaxedR1CSSNARKTrait<G1>,
520 S2: RelaxedR1CSSNARKTrait<G2>,
521{
522 F_arity_primary: usize,
523 F_arity_secondary: usize,
524 ro_consts_primary: ROConstants<G1>,
525 ro_consts_secondary: ROConstants<G2>,
526 digest: G1::Scalar,
527 vk_primary: S1::VerifierKey,
528 vk_secondary: S2::VerifierKey,
529 _p_c1: PhantomData<C1>,
530 _p_c2: PhantomData<C2>,
531}
532
533/// A SNARK that proves the knowledge of a valid `RecursiveSNARK`
534#[derive(Clone, Serialize, Deserialize)]
535#[serde(bound = "")]
536pub struct CompressedSNARK<G1, G2, C1, C2, S1, S2>
537where
538 G1: Group<Base = <G2 as Group>::Scalar>,
539 G2: Group<Base = <G1 as Group>::Scalar>,
540 C1: StepCircuit<G1::Scalar>,
541 C2: StepCircuit<G2::Scalar>,
542 S1: RelaxedR1CSSNARKTrait<G1>,
543 S2: RelaxedR1CSSNARKTrait<G2>,
544{
545 r_U_primary: RelaxedR1CSInstance<G1>,
546 r_W_snark_primary: S1,
547
548 r_U_secondary: RelaxedR1CSInstance<G2>,
549 l_u_secondary: R1CSInstance<G2>,
550 nifs_secondary: NIFS<G2>,
551 f_W_snark_secondary: S2,
552
553 zn_primary: Vec<G1::Scalar>,
554 zn_secondary: Vec<G2::Scalar>,
555
556 _p_c1: PhantomData<C1>,
557 _p_c2: PhantomData<C2>,
558}
559
560impl<G1, G2, C1, C2, S1, S2> CompressedSNARK<G1, G2, C1, C2, S1, S2>
561where
562 G1: Group<Base = <G2 as Group>::Scalar>,
563 G2: Group<Base = <G1 as Group>::Scalar>,
564 C1: StepCircuit<G1::Scalar>,
565 C2: StepCircuit<G2::Scalar>,
566 S1: RelaxedR1CSSNARKTrait<G1>,
567 S2: RelaxedR1CSSNARKTrait<G2>,
568{
569 /// Creates prover and verifier keys for `CompressedSNARK`
570 pub fn setup(
571 pp: &PublicParams<G1, G2, C1, C2>,
572 ) -> Result<
573 (
574 ProverKey<G1, G2, C1, C2, S1, S2>,
575 VerifierKey<G1, G2, C1, C2, S1, S2>,
576 ),
577 NovaError,
578 > {
579 let (pk_primary, vk_primary) = S1::setup(&pp.ck_primary, &pp.r1cs_shape_primary)?;
580 let (pk_secondary, vk_secondary) = S2::setup(&pp.ck_secondary, &pp.r1cs_shape_secondary)?;
581
582 let pk = ProverKey {
583 pk_primary,
584 pk_secondary,
585 _p_c1: Default::default(),
586 _p_c2: Default::default(),
587 };
588
589 let vk = VerifierKey {
590 F_arity_primary: pp.F_arity_primary,
591 F_arity_secondary: pp.F_arity_secondary,
592 ro_consts_primary: pp.ro_consts_primary.clone(),
593 ro_consts_secondary: pp.ro_consts_secondary.clone(),
594 digest: pp.digest,
595 vk_primary,
596 vk_secondary,
597 _p_c1: Default::default(),
598 _p_c2: Default::default(),
599 };
600
601 Ok((pk, vk))
602 }
603
604 /// Create a new `CompressedSNARK`
605 pub fn prove(
606 pp: &PublicParams<G1, G2, C1, C2>,
607 pk: &ProverKey<G1, G2, C1, C2, S1, S2>,
608 recursive_snark: &RecursiveSNARK<G1, G2, C1, C2>,
609 ) -> Result<Self, NovaError> {
610 // fold the secondary circuit's instance
611 let res_secondary = NIFS::prove(
612 &pp.ck_secondary,
613 &pp.ro_consts_secondary,
614 &scalar_as_base::<G1>(pp.digest),
615 &pp.r1cs_shape_secondary,
616 &recursive_snark.r_U_secondary,
617 &recursive_snark.r_W_secondary,
618 &recursive_snark.l_u_secondary,
619 &recursive_snark.l_w_secondary,
620 );
621
622 let (nifs_secondary, (f_U_secondary, f_W_secondary)) = res_secondary?;
623
624 // create SNARKs proving the knowledge of f_W_primary and f_W_secondary
625 let (r_W_snark_primary, f_W_snark_secondary) = rayon::join(
626 || {
627 S1::prove(
628 &pp.ck_primary,
629 &pk.pk_primary,
630 &recursive_snark.r_U_primary,
631 &recursive_snark.r_W_primary,
632 )
633 },
634 || {
635 S2::prove(
636 &pp.ck_secondary,
637 &pk.pk_secondary,
638 &f_U_secondary,
639 &f_W_secondary,
640 )
641 },
642 );
643
644 Ok(Self {
645 r_U_primary: recursive_snark.r_U_primary.clone(),
646 r_W_snark_primary: r_W_snark_primary?,
647
648 r_U_secondary: recursive_snark.r_U_secondary.clone(),
649 l_u_secondary: recursive_snark.l_u_secondary.clone(),
650 nifs_secondary,
651 f_W_snark_secondary: f_W_snark_secondary?,
652
653 zn_primary: recursive_snark.zi_primary.clone(),
654 zn_secondary: recursive_snark.zi_secondary.clone(),
655
656 _p_c1: Default::default(),
657 _p_c2: Default::default(),
658 })
659 }
660
661 /// Verify the correctness of the `CompressedSNARK`
662 pub fn verify(
663 &self,
664 vk: &VerifierKey<G1, G2, C1, C2, S1, S2>,
665 num_steps: usize,
666 z0_primary: Vec<G1::Scalar>,
667 z0_secondary: Vec<G2::Scalar>,
668 ) -> Result<(Vec<G1::Scalar>, Vec<G2::Scalar>), NovaError> {
669 // number of steps cannot be zero
670 if num_steps == 0 {
671 return Err(NovaError::ProofVerifyError);
672 }
673
674 // check if the (relaxed) R1CS instances have two public outputs
675 if self.l_u_secondary.X.len() != 2
676 || self.r_U_primary.X.len() != 2
677 || self.r_U_secondary.X.len() != 2
678 {
679 return Err(NovaError::ProofVerifyError);
680 }
681
682 // check if the output hashes in R1CS instances point to the right running instances
683 let (hash_primary, hash_secondary) = {
684 let mut hasher = <G2 as Group>::RO::new(
685 vk.ro_consts_secondary.clone(),
686 NUM_FE_WITHOUT_IO_FOR_CRHF + 2 * vk.F_arity_primary,
687 );
688 hasher.absorb(vk.digest);
689 hasher.absorb(G1::Scalar::from(num_steps as u64));
690 for e in z0_primary {
691 hasher.absorb(e);
692 }
693 for e in &self.zn_primary {
694 hasher.absorb(*e);
695 }
696 self.r_U_secondary.absorb_in_ro(&mut hasher);
697
698 let mut hasher2 = <G1 as Group>::RO::new(
699 vk.ro_consts_primary.clone(),
700 NUM_FE_WITHOUT_IO_FOR_CRHF + 2 * vk.F_arity_secondary,
701 );
702 hasher2.absorb(scalar_as_base::<G1>(vk.digest));
703 hasher2.absorb(G2::Scalar::from(num_steps as u64));
704 for e in z0_secondary {
705 hasher2.absorb(e);
706 }
707 for e in &self.zn_secondary {
708 hasher2.absorb(*e);
709 }
710 self.r_U_primary.absorb_in_ro(&mut hasher2);
711
712 (
713 hasher.squeeze(NUM_HASH_BITS),
714 hasher2.squeeze(NUM_HASH_BITS),
715 )
716 };
717
718 if hash_primary != self.l_u_secondary.X[0]
719 || hash_secondary != scalar_as_base::<G2>(self.l_u_secondary.X[1])
720 {
721 return Err(NovaError::ProofVerifyError);
722 }
723
724 // fold the running instance and last instance to get a folded instance
725 let f_U_secondary = self.nifs_secondary.verify(
726 &vk.ro_consts_secondary,
727 &scalar_as_base::<G1>(vk.digest),
728 &self.r_U_secondary,
729 &self.l_u_secondary,
730 )?;
731
732 // check the satisfiability of the folded instances using SNARKs proving the knowledge of their satisfying witnesses
733 let (res_primary, res_secondary) = rayon::join(
734 || {
735 self
736 .r_W_snark_primary
737 .verify(&vk.vk_primary, &self.r_U_primary)
738 },
739 || {
740 self
741 .f_W_snark_secondary
742 .verify(&vk.vk_secondary, &f_U_secondary)
743 },
744 );
745
746 res_primary?;
747 res_secondary?;
748
749 Ok((self.zn_primary.clone(), self.zn_secondary.clone()))
750 }
751}
752
753type CommitmentKey<G> = <<G as traits::Group>::CE as CommitmentEngineTrait<G>>::CommitmentKey;
754type Commitment<G> = <<G as Group>::CE as CommitmentEngineTrait<G>>::Commitment;
755type CompressedCommitment<G> = <<<G as Group>::CE as CommitmentEngineTrait<G>>::Commitment as CommitmentTrait<G>>::CompressedCommitment;
756type CE<G> = <G as Group>::CE;
757
758fn compute_digest<G: Group, T: Serialize>(o: &T) -> G::Scalar {
759 // obtain a vector of bytes representing public parameters
760 let mut encoder = ZlibEncoder::new(Vec::new(), Compression::default());
761 bincode::serialize_into(&mut encoder, o).unwrap();
762 let pp_bytes = encoder.finish().unwrap();
763
764 // convert pp_bytes into a short digest
765 let mut hasher = Sha3_256::new();
766 hasher.input(&pp_bytes);
767 let digest = hasher.result();
768
769 // truncate the digest to NUM_HASH_BITS bits
770 let bv = (0..NUM_HASH_BITS).map(|i| {
771 let (byte_pos, bit_pos) = (i / 8, i % 8);
772 let bit = (digest[byte_pos] >> bit_pos) & 1;
773 bit == 1
774 });
775
776 // turn the bit vector into a scalar
777 let mut digest = G::Scalar::ZERO;
778 let mut coeff = G::Scalar::ONE;
779 for bit in bv {
780 if bit {
781 digest += coeff;
782 }
783 coeff += coeff;
784 }
785 digest
786}
787
788#[cfg(test)]
789mod tests {
790 use super::*;
791 type G1 = pasta_curves::pallas::Point;
792 type G2 = pasta_curves::vesta::Point;
793 type EE1 = provider::ipa_pc::EvaluationEngine<G1>;
794 type EE2 = provider::ipa_pc::EvaluationEngine<G2>;
795 type S1 = spartan::RelaxedR1CSSNARK<G1, EE1>;
796 type S2 = spartan::RelaxedR1CSSNARK<G2, EE2>;
797 use ::bellperson::{gadgets::num::AllocatedNum, ConstraintSystem, SynthesisError};
798 use core::marker::PhantomData;
799 use ff::PrimeField;
800 use traits::circuit::TrivialTestCircuit;
801
802 #[derive(Clone, Debug, Default)]
803 struct CubicCircuit<F: PrimeField> {
804 _p: PhantomData<F>,
805 }
806
807 impl<F> StepCircuit<F> for CubicCircuit<F>
808 where
809 F: PrimeField,
810 {
811 fn arity(&self) -> usize {
812 1
813 }
814
815 fn synthesize<CS: ConstraintSystem<F>>(
816 &self,
817 cs: &mut CS,
818 z: &[AllocatedNum<F>],
819 ) -> Result<Vec<AllocatedNum<F>>, SynthesisError> {
820 // Consider a cubic equation: `x^3 + x + 5 = y`, where `x` and `y` are respectively the input and output.
821 let x = &z[0];
822 let x_sq = x.square(cs.namespace(|| "x_sq"))?;
823 let x_cu = x_sq.mul(cs.namespace(|| "x_cu"), x)?;
824 let y = AllocatedNum::alloc(cs.namespace(|| "y"), || {
825 Ok(x_cu.get_value().unwrap() + x.get_value().unwrap() + F::from(5u64))
826 })?;
827
828 cs.enforce(
829 || "y = x^3 + x + 5",
830 |lc| {
831 lc + x_cu.get_variable()
832 + x.get_variable()
833 + CS::one()
834 + CS::one()
835 + CS::one()
836 + CS::one()
837 + CS::one()
838 },
839 |lc| lc + CS::one(),
840 |lc| lc + y.get_variable(),
841 );
842
843 Ok(vec![y])
844 }
845
846 fn output(&self, z: &[F]) -> Vec<F> {
847 vec![z[0] * z[0] * z[0] + z[0] + F::from(5u64)]
848 }
849 }
850
851 #[test]
852 fn test_ivc_trivial() {
853 // produce public parameters
854 let pp = PublicParams::<
855 G1,
856 G2,
857 TrivialTestCircuit<<G1 as Group>::Scalar>,
858 TrivialTestCircuit<<G2 as Group>::Scalar>,
859 >::setup(TrivialTestCircuit::default(), TrivialTestCircuit::default());
860
861 let num_steps = 1;
862
863 // produce a recursive SNARK
864 let res = RecursiveSNARK::prove_step(
865 &pp,
866 None,
867 TrivialTestCircuit::default(),
868 TrivialTestCircuit::default(),
869 vec![<G1 as Group>::Scalar::ZERO],
870 vec![<G2 as Group>::Scalar::ZERO],
871 );
872 assert!(res.is_ok());
873 let recursive_snark = res.unwrap();
874
875 // verify the recursive SNARK
876 let res = recursive_snark.verify(
877 &pp,
878 num_steps,
879 vec![<G1 as Group>::Scalar::ZERO],
880 vec![<G2 as Group>::Scalar::ZERO],
881 );
882 assert!(res.is_ok());
883 }
884
885 #[test]
886 fn test_ivc_nontrivial() {
887 let circuit_primary = TrivialTestCircuit::default();
888 let circuit_secondary = CubicCircuit::default();
889
890 // produce public parameters
891 let pp = PublicParams::<
892 G1,
893 G2,
894 TrivialTestCircuit<<G1 as Group>::Scalar>,
895 CubicCircuit<<G2 as Group>::Scalar>,
896 >::setup(circuit_primary.clone(), circuit_secondary.clone());
897
898 let num_steps = 3;
899
900 // produce a recursive SNARK
901 let mut recursive_snark: Option<
902 RecursiveSNARK<
903 G1,
904 G2,
905 TrivialTestCircuit<<G1 as Group>::Scalar>,
906 CubicCircuit<<G2 as Group>::Scalar>,
907 >,
908 > = None;
909
910 for i in 0..num_steps {
911 let res = RecursiveSNARK::prove_step(
912 &pp,
913 recursive_snark,
914 circuit_primary.clone(),
915 circuit_secondary.clone(),
916 vec![<G1 as Group>::Scalar::ONE],
917 vec![<G2 as Group>::Scalar::ZERO],
918 );
919 assert!(res.is_ok());
920 let recursive_snark_unwrapped = res.unwrap();
921
922 // verify the recursive snark at each step of recursion
923 let res = recursive_snark_unwrapped.verify(
924 &pp,
925 i + 1,
926 vec![<G1 as Group>::Scalar::ONE],
927 vec![<G2 as Group>::Scalar::ZERO],
928 );
929 assert!(res.is_ok());
930
931 // set the running variable for the next iteration
932 recursive_snark = Some(recursive_snark_unwrapped);
933 }
934
935 assert!(recursive_snark.is_some());
936 let recursive_snark = recursive_snark.unwrap();
937
938 // verify the recursive SNARK
939 let res = recursive_snark.verify(
940 &pp,
941 num_steps,
942 vec![<G1 as Group>::Scalar::ONE],
943 vec![<G2 as Group>::Scalar::ZERO],
944 );
945 assert!(res.is_ok());
946
947 let (zn_primary, zn_secondary) = res.unwrap();
948
949 // sanity: check the claimed output with a direct computation of the same
950 assert_eq!(zn_primary, vec![<G1 as Group>::Scalar::ONE]);
951 let mut zn_secondary_direct = vec![<G2 as Group>::Scalar::ZERO];
952 for _i in 0..num_steps {
953 zn_secondary_direct = CubicCircuit::default().output(&zn_secondary_direct);
954 }
955 assert_eq!(zn_secondary, zn_secondary_direct);
956 assert_eq!(zn_secondary, vec![<G2 as Group>::Scalar::from(2460515u64)]);
957 }
958
959 #[test]
960 fn test_ivc_nontrivial_with_compression() {
961 let circuit_primary = TrivialTestCircuit::default();
962 let circuit_secondary = CubicCircuit::default();
963
964 // produce public parameters
965 let pp = PublicParams::<
966 G1,
967 G2,
968 TrivialTestCircuit<<G1 as Group>::Scalar>,
969 CubicCircuit<<G2 as Group>::Scalar>,
970 >::setup(circuit_primary.clone(), circuit_secondary.clone());
971
972 let num_steps = 3;
973
974 // produce a recursive SNARK
975 let mut recursive_snark: Option<
976 RecursiveSNARK<
977 G1,
978 G2,
979 TrivialTestCircuit<<G1 as Group>::Scalar>,
980 CubicCircuit<<G2 as Group>::Scalar>,
981 >,
982 > = None;
983
984 for _i in 0..num_steps {
985 let res = RecursiveSNARK::prove_step(
986 &pp,
987 recursive_snark,
988 circuit_primary.clone(),
989 circuit_secondary.clone(),
990 vec![<G1 as Group>::Scalar::ONE],
991 vec![<G2 as Group>::Scalar::ZERO],
992 );
993 assert!(res.is_ok());
994 recursive_snark = Some(res.unwrap());
995 }
996
997 assert!(recursive_snark.is_some());
998 let recursive_snark = recursive_snark.unwrap();
999
1000 // verify the recursive SNARK
1001 let res = recursive_snark.verify(
1002 &pp,
1003 num_steps,
1004 vec![<G1 as Group>::Scalar::ONE],
1005 vec![<G2 as Group>::Scalar::ZERO],
1006 );
1007 assert!(res.is_ok());
1008
1009 let (zn_primary, zn_secondary) = res.unwrap();
1010
1011 // sanity: check the claimed output with a direct computation of the same
1012 assert_eq!(zn_primary, vec![<G1 as Group>::Scalar::ONE]);
1013 let mut zn_secondary_direct = vec![<G2 as Group>::Scalar::ZERO];
1014 for _i in 0..num_steps {
1015 zn_secondary_direct = CubicCircuit::default().output(&zn_secondary_direct);
1016 }
1017 assert_eq!(zn_secondary, zn_secondary_direct);
1018 assert_eq!(zn_secondary, vec![<G2 as Group>::Scalar::from(2460515u64)]);
1019
1020 // produce the prover and verifier keys for compressed snark
1021 let (pk, vk) = CompressedSNARK::<_, _, _, _, S1, S2>::setup(&pp).unwrap();
1022
1023 // produce a compressed SNARK
1024 let res = CompressedSNARK::<_, _, _, _, S1, S2>::prove(&pp, &pk, &recursive_snark);
1025 assert!(res.is_ok());
1026 let compressed_snark = res.unwrap();
1027
1028 // verify the compressed SNARK
1029 let res = compressed_snark.verify(
1030 &vk,
1031 num_steps,
1032 vec![<G1 as Group>::Scalar::ONE],
1033 vec![<G2 as Group>::Scalar::ZERO],
1034 );
1035 assert!(res.is_ok());
1036 }
1037
1038 #[test]
1039 fn test_ivc_nontrivial_with_spark_compression() {
1040 let circuit_primary = TrivialTestCircuit::default();
1041 let circuit_secondary = CubicCircuit::default();
1042
1043 // produce public parameters
1044 let pp = PublicParams::<
1045 G1,
1046 G2,
1047 TrivialTestCircuit<<G1 as Group>::Scalar>,
1048 CubicCircuit<<G2 as Group>::Scalar>,
1049 >::setup(circuit_primary.clone(), circuit_secondary.clone());
1050
1051 let num_steps = 3;
1052
1053 // produce a recursive SNARK
1054 let mut recursive_snark: Option<
1055 RecursiveSNARK<
1056 G1,
1057 G2,
1058 TrivialTestCircuit<<G1 as Group>::Scalar>,
1059 CubicCircuit<<G2 as Group>::Scalar>,
1060 >,
1061 > = None;
1062
1063 for _i in 0..num_steps {
1064 let res = RecursiveSNARK::prove_step(
1065 &pp,
1066 recursive_snark,
1067 circuit_primary.clone(),
1068 circuit_secondary.clone(),
1069 vec![<G1 as Group>::Scalar::ONE],
1070 vec![<G2 as Group>::Scalar::ZERO],
1071 );
1072 assert!(res.is_ok());
1073 recursive_snark = Some(res.unwrap());
1074 }
1075
1076 assert!(recursive_snark.is_some());
1077 let recursive_snark = recursive_snark.unwrap();
1078
1079 // verify the recursive SNARK
1080 let res = recursive_snark.verify(
1081 &pp,
1082 num_steps,
1083 vec![<G1 as Group>::Scalar::ONE],
1084 vec![<G2 as Group>::Scalar::ZERO],
1085 );
1086 assert!(res.is_ok());
1087
1088 let (zn_primary, zn_secondary) = res.unwrap();
1089
1090 // sanity: check the claimed output with a direct computation of the same
1091 assert_eq!(zn_primary, vec![<G1 as Group>::Scalar::ONE]);
1092 let mut zn_secondary_direct = vec![<G2 as Group>::Scalar::ZERO];
1093 for _i in 0..num_steps {
1094 zn_secondary_direct = CubicCircuit::default().output(&zn_secondary_direct);
1095 }
1096 assert_eq!(zn_secondary, zn_secondary_direct);
1097 assert_eq!(zn_secondary, vec![<G2 as Group>::Scalar::from(2460515u64)]);
1098
1099 // run the compressed snark with Spark compiler
1100 type S1Prime = spartan::pp::RelaxedR1CSSNARK<G1, EE1>;
1101 type S2Prime = spartan::pp::RelaxedR1CSSNARK<G2, EE2>;
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}