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 crate::provider::pedersen::CommitmentKeyExtTrait;
791
792 use super::*;
793 type EE1<G1> = provider::ipa_pc::EvaluationEngine<G1>;
794 type EE2<G2> = provider::ipa_pc::EvaluationEngine<G2>;
795 type S1<G1> = spartan::RelaxedR1CSSNARK<G1, EE1<G1>>;
796 type S2<G2> = spartan::RelaxedR1CSSNARK<G2, EE2<G2>>;
797 type S1Prime<G1> = spartan::pp::RelaxedR1CSSNARK<G1, EE1<G1>>;
798 type S2Prime<G2> = spartan::pp::RelaxedR1CSSNARK<G2, EE2<G2>>;
799
800 use ::bellperson::{gadgets::num::AllocatedNum, ConstraintSystem, SynthesisError};
801 use core::marker::PhantomData;
802 use ff::PrimeField;
803 use traits::circuit::TrivialTestCircuit;
804
805 #[derive(Clone, Debug, Default)]
806 struct CubicCircuit<F: PrimeField> {
807 _p: PhantomData<F>,
808 }
809
810 impl<F> StepCircuit<F> for CubicCircuit<F>
811 where
812 F: PrimeField,
813 {
814 fn arity(&self) -> usize {
815 1
816 }
817
818 fn synthesize<CS: ConstraintSystem<F>>(
819 &self,
820 cs: &mut CS,
821 z: &[AllocatedNum<F>],
822 ) -> Result<Vec<AllocatedNum<F>>, SynthesisError> {
823 // Consider a cubic equation: `x^3 + x + 5 = y`, where `x` and `y` are respectively the input and output.
824 let x = &z[0];
825 let x_sq = x.square(cs.namespace(|| "x_sq"))?;
826 let x_cu = x_sq.mul(cs.namespace(|| "x_cu"), x)?;
827 let y = AllocatedNum::alloc(cs.namespace(|| "y"), || {
828 Ok(x_cu.get_value().unwrap() + x.get_value().unwrap() + F::from(5u64))
829 })?;
830
831 cs.enforce(
832 || "y = x^3 + x + 5",
833 |lc| {
834 lc + x_cu.get_variable()
835 + x.get_variable()
836 + CS::one()
837 + CS::one()
838 + CS::one()
839 + CS::one()
840 + CS::one()
841 },
842 |lc| lc + CS::one(),
843 |lc| lc + y.get_variable(),
844 );
845
846 Ok(vec![y])
847 }
848
849 fn output(&self, z: &[F]) -> Vec<F> {
850 vec![z[0] * z[0] * z[0] + z[0] + F::from(5u64)]
851 }
852 }
853
854 fn test_ivc_trivial_with<G1, G2>()
855 where
856 G1: Group<Base = <G2 as Group>::Scalar>,
857 G2: Group<Base = <G1 as Group>::Scalar>,
858 {
859 let test_circuit1 = TrivialTestCircuit::<<G1 as Group>::Scalar>::default();
860 let test_circuit2 = TrivialTestCircuit::<<G2 as Group>::Scalar>::default();
861
862 // produce public parameters
863 let pp = PublicParams::<
864 G1,
865 G2,
866 TrivialTestCircuit<<G1 as Group>::Scalar>,
867 TrivialTestCircuit<<G2 as Group>::Scalar>,
868 >::setup(test_circuit1.clone(), test_circuit2.clone());
869
870 let num_steps = 1;
871
872 // produce a recursive SNARK
873 let res = RecursiveSNARK::prove_step(
874 &pp,
875 None,
876 test_circuit1,
877 test_circuit2,
878 vec![<G1 as Group>::Scalar::ZERO],
879 vec![<G2 as Group>::Scalar::ZERO],
880 );
881 assert!(res.is_ok());
882 let recursive_snark = res.unwrap();
883
884 // verify the recursive SNARK
885 let res = recursive_snark.verify(
886 &pp,
887 num_steps,
888 vec![<G1 as Group>::Scalar::ZERO],
889 vec![<G2 as Group>::Scalar::ZERO],
890 );
891 assert!(res.is_ok());
892 }
893
894 #[test]
895 fn test_ivc_trivial() {
896 type G1 = pasta_curves::pallas::Point;
897 type G2 = pasta_curves::vesta::Point;
898 test_ivc_trivial_with::<G1, G2>();
899 }
900
901 fn test_ivc_nontrivial_with<G1, G2>()
902 where
903 G1: Group<Base = <G2 as Group>::Scalar>,
904 G2: Group<Base = <G1 as Group>::Scalar>,
905 {
906 let circuit_primary = TrivialTestCircuit::default();
907 let circuit_secondary = CubicCircuit::default();
908
909 // produce public parameters
910 let pp = PublicParams::<
911 G1,
912 G2,
913 TrivialTestCircuit<<G1 as Group>::Scalar>,
914 CubicCircuit<<G2 as Group>::Scalar>,
915 >::setup(circuit_primary.clone(), circuit_secondary.clone());
916
917 let num_steps = 3;
918
919 // produce a recursive SNARK
920 let mut recursive_snark: Option<
921 RecursiveSNARK<
922 G1,
923 G2,
924 TrivialTestCircuit<<G1 as Group>::Scalar>,
925 CubicCircuit<<G2 as Group>::Scalar>,
926 >,
927 > = None;
928
929 for i in 0..num_steps {
930 let res = RecursiveSNARK::prove_step(
931 &pp,
932 recursive_snark,
933 circuit_primary.clone(),
934 circuit_secondary.clone(),
935 vec![<G1 as Group>::Scalar::ONE],
936 vec![<G2 as Group>::Scalar::ZERO],
937 );
938 assert!(res.is_ok());
939 let recursive_snark_unwrapped = res.unwrap();
940
941 // verify the recursive snark at each step of recursion
942 let res = recursive_snark_unwrapped.verify(
943 &pp,
944 i + 1,
945 vec![<G1 as Group>::Scalar::ONE],
946 vec![<G2 as Group>::Scalar::ZERO],
947 );
948 assert!(res.is_ok());
949
950 // set the running variable for the next iteration
951 recursive_snark = Some(recursive_snark_unwrapped);
952 }
953
954 assert!(recursive_snark.is_some());
955 let recursive_snark = recursive_snark.unwrap();
956
957 // verify the recursive SNARK
958 let res = recursive_snark.verify(
959 &pp,
960 num_steps,
961 vec![<G1 as Group>::Scalar::ONE],
962 vec![<G2 as Group>::Scalar::ZERO],
963 );
964 assert!(res.is_ok());
965
966 let (zn_primary, zn_secondary) = res.unwrap();
967
968 // sanity: check the claimed output with a direct computation of the same
969 assert_eq!(zn_primary, vec![<G1 as Group>::Scalar::ONE]);
970 let mut zn_secondary_direct = vec![<G2 as Group>::Scalar::ZERO];
971 for _i in 0..num_steps {
972 zn_secondary_direct = circuit_secondary.clone().output(&zn_secondary_direct);
973 }
974 assert_eq!(zn_secondary, zn_secondary_direct);
975 assert_eq!(zn_secondary, vec![<G2 as Group>::Scalar::from(2460515u64)]);
976 }
977
978 #[test]
979 fn test_ivc_nontrivial() {
980 type G1 = pasta_curves::pallas::Point;
981 type G2 = pasta_curves::vesta::Point;
982
983 test_ivc_nontrivial_with::<G1, G2>();
984 }
985
986 fn test_ivc_nontrivial_with_compression_with<G1, G2>()
987 where
988 G1: Group<Base = <G2 as Group>::Scalar>,
989 G2: Group<Base = <G1 as Group>::Scalar>,
990 // this is due to the reliance on CommitmentKeyExtTrait as a bound in ipa_pc
991 <G1::CE as CommitmentEngineTrait<G1>>::CommitmentKey:
992 CommitmentKeyExtTrait<G1, CE = <G1 as Group>::CE>,
993 <G2::CE as CommitmentEngineTrait<G2>>::CommitmentKey:
994 CommitmentKeyExtTrait<G2, CE = <G2 as Group>::CE>,
995 {
996 let circuit_primary = TrivialTestCircuit::default();
997 let circuit_secondary = CubicCircuit::default();
998
999 // produce public parameters
1000 let pp = PublicParams::<
1001 G1,
1002 G2,
1003 TrivialTestCircuit<<G1 as Group>::Scalar>,
1004 CubicCircuit<<G2 as Group>::Scalar>,
1005 >::setup(circuit_primary.clone(), circuit_secondary.clone());
1006
1007 let num_steps = 3;
1008
1009 // produce a recursive SNARK
1010 let mut recursive_snark: Option<
1011 RecursiveSNARK<
1012 G1,
1013 G2,
1014 TrivialTestCircuit<<G1 as Group>::Scalar>,
1015 CubicCircuit<<G2 as Group>::Scalar>,
1016 >,
1017 > = None;
1018
1019 for _i in 0..num_steps {
1020 let res = RecursiveSNARK::prove_step(
1021 &pp,
1022 recursive_snark,
1023 circuit_primary.clone(),
1024 circuit_secondary.clone(),
1025 vec![<G1 as Group>::Scalar::ONE],
1026 vec![<G2 as Group>::Scalar::ZERO],
1027 );
1028 assert!(res.is_ok());
1029 recursive_snark = Some(res.unwrap());
1030 }
1031
1032 assert!(recursive_snark.is_some());
1033 let recursive_snark = recursive_snark.unwrap();
1034
1035 // verify the recursive SNARK
1036 let res = recursive_snark.verify(
1037 &pp,
1038 num_steps,
1039 vec![<G1 as Group>::Scalar::ONE],
1040 vec![<G2 as Group>::Scalar::ZERO],
1041 );
1042 assert!(res.is_ok());
1043
1044 let (zn_primary, zn_secondary) = res.unwrap();
1045
1046 // sanity: check the claimed output with a direct computation of the same
1047 assert_eq!(zn_primary, vec![<G1 as Group>::Scalar::ONE]);
1048 let mut zn_secondary_direct = vec![<G2 as Group>::Scalar::ZERO];
1049 for _i in 0..num_steps {
1050 zn_secondary_direct = circuit_secondary.clone().output(&zn_secondary_direct);
1051 }
1052 assert_eq!(zn_secondary, zn_secondary_direct);
1053 assert_eq!(zn_secondary, vec![<G2 as Group>::Scalar::from(2460515u64)]);
1054
1055 // produce the prover and verifier keys for compressed snark
1056 let (pk, vk) = CompressedSNARK::<_, _, _, _, S1<G1>, S2<G2>>::setup(&pp).unwrap();
1057
1058 // produce a compressed SNARK
1059 let res = CompressedSNARK::<_, _, _, _, S1<G1>, S2<G2>>::prove(&pp, &pk, &recursive_snark);
1060 assert!(res.is_ok());
1061 let compressed_snark = res.unwrap();
1062
1063 // verify the compressed SNARK
1064 let res = compressed_snark.verify(
1065 &vk,
1066 num_steps,
1067 vec![<G1 as Group>::Scalar::ONE],
1068 vec![<G2 as Group>::Scalar::ZERO],
1069 );
1070 assert!(res.is_ok());
1071 }
1072
1073 #[test]
1074 fn test_ivc_nontrivial_with_compression() {
1075 type G1 = pasta_curves::pallas::Point;
1076 type G2 = pasta_curves::vesta::Point;
1077
1078 test_ivc_nontrivial_with_compression_with::<G1, G2>();
1079 }
1080
1081 fn test_ivc_nontrivial_with_spark_compression_with<G1, G2>()
1082 where
1083 G1: Group<Base = <G2 as Group>::Scalar>,
1084 G2: Group<Base = <G1 as Group>::Scalar>,
1085 // this is due to the reliance on CommitmentKeyExtTrait as a bound in ipa_pc
1086 <G1::CE as CommitmentEngineTrait<G1>>::CommitmentKey:
1087 CommitmentKeyExtTrait<G1, CE = <G1 as Group>::CE>,
1088 <G2::CE as CommitmentEngineTrait<G2>>::CommitmentKey:
1089 CommitmentKeyExtTrait<G2, CE = <G2 as Group>::CE>,
1090 {
1091 let circuit_primary = TrivialTestCircuit::default();
1092 let circuit_secondary = CubicCircuit::default();
1093
1094 // produce public parameters
1095 let pp = PublicParams::<
1096 G1,
1097 G2,
1098 TrivialTestCircuit<<G1 as Group>::Scalar>,
1099 CubicCircuit<<G2 as Group>::Scalar>,
1100 >::setup(circuit_primary.clone(), circuit_secondary.clone());
1101
1102 let num_steps = 3;
1103
1104 // produce a recursive SNARK
1105 let mut recursive_snark: Option<
1106 RecursiveSNARK<
1107 G1,
1108 G2,
1109 TrivialTestCircuit<<G1 as Group>::Scalar>,
1110 CubicCircuit<<G2 as Group>::Scalar>,
1111 >,
1112 > = None;
1113
1114 for _i in 0..num_steps {
1115 let res = RecursiveSNARK::prove_step(
1116 &pp,
1117 recursive_snark,
1118 circuit_primary.clone(),
1119 circuit_secondary.clone(),
1120 vec![<G1 as Group>::Scalar::ONE],
1121 vec![<G2 as Group>::Scalar::ZERO],
1122 );
1123 assert!(res.is_ok());
1124 recursive_snark = Some(res.unwrap());
1125 }
1126
1127 assert!(recursive_snark.is_some());
1128 let recursive_snark = recursive_snark.unwrap();
1129
1130 // verify the recursive SNARK
1131 let res = recursive_snark.verify(
1132 &pp,
1133 num_steps,
1134 vec![<G1 as Group>::Scalar::ONE],
1135 vec![<G2 as Group>::Scalar::ZERO],
1136 );
1137 assert!(res.is_ok());
1138
1139 let (zn_primary, zn_secondary) = res.unwrap();
1140
1141 // sanity: check the claimed output with a direct computation of the same
1142 assert_eq!(zn_primary, vec![<G1 as Group>::Scalar::ONE]);
1143 let mut zn_secondary_direct = vec![<G2 as Group>::Scalar::ZERO];
1144 for _i in 0..num_steps {
1145 zn_secondary_direct = CubicCircuit::default().output(&zn_secondary_direct);
1146 }
1147 assert_eq!(zn_secondary, zn_secondary_direct);
1148 assert_eq!(zn_secondary, vec![<G2 as Group>::Scalar::from(2460515u64)]);
1149
1150 // run the compressed snark with Spark compiler
1151
1152 // produce the prover and verifier keys for compressed snark
1153 let (pk, vk) = CompressedSNARK::<_, _, _, _, S1Prime<G1>, S2Prime<G2>>::setup(&pp).unwrap();
1154
1155 // produce a compressed SNARK
1156 let res =
1157 CompressedSNARK::<_, _, _, _, S1Prime<G1>, S2Prime<G2>>::prove(&pp, &pk, &recursive_snark);
1158 assert!(res.is_ok());
1159 let compressed_snark = res.unwrap();
1160
1161 // verify the compressed SNARK
1162 let res = compressed_snark.verify(
1163 &vk,
1164 num_steps,
1165 vec![<G1 as Group>::Scalar::ONE],
1166 vec![<G2 as Group>::Scalar::ZERO],
1167 );
1168 assert!(res.is_ok());
1169 }
1170
1171 #[test]
1172 fn test_ivc_nontrivial_with_spark_compression() {
1173 type G1 = pasta_curves::pallas::Point;
1174 type G2 = pasta_curves::vesta::Point;
1175
1176 test_ivc_nontrivial_with_spark_compression_with::<G1, G2>();
1177 }
1178
1179 fn test_ivc_nondet_with_compression_with<G1, G2>()
1180 where
1181 G1: Group<Base = <G2 as Group>::Scalar>,
1182 G2: Group<Base = <G1 as Group>::Scalar>,
1183 // this is due to the reliance on CommitmentKeyExtTrait as a bound in ipa_pc
1184 <G1::CE as CommitmentEngineTrait<G1>>::CommitmentKey:
1185 CommitmentKeyExtTrait<G1, CE = <G1 as Group>::CE>,
1186 <G2::CE as CommitmentEngineTrait<G2>>::CommitmentKey:
1187 CommitmentKeyExtTrait<G2, CE = <G2 as Group>::CE>,
1188 {
1189 // y is a non-deterministic advice representing the fifth root of the input at a step.
1190 #[derive(Clone, Debug)]
1191 struct FifthRootCheckingCircuit<F: PrimeField> {
1192 y: F,
1193 }
1194
1195 impl<F> FifthRootCheckingCircuit<F>
1196 where
1197 F: PrimeField,
1198 {
1199 fn new(num_steps: usize) -> (Vec<F>, Vec<Self>) {
1200 let mut powers = Vec::new();
1201 let rng = &mut rand::rngs::OsRng;
1202 let mut seed = F::random(rng);
1203 for _i in 0..num_steps + 1 {
1204 let mut power = seed;
1205 power = power.square();
1206 power = power.square();
1207 power *= seed;
1208
1209 powers.push(Self { y: power });
1210
1211 seed = power;
1212 }
1213
1214 // reverse the powers to get roots
1215 let roots = powers.into_iter().rev().collect::<Vec<Self>>();
1216 (vec![roots[0].y], roots[1..].to_vec())
1217 }
1218 }
1219
1220 impl<F> StepCircuit<F> for FifthRootCheckingCircuit<F>
1221 where
1222 F: PrimeField,
1223 {
1224 fn arity(&self) -> usize {
1225 1
1226 }
1227
1228 fn synthesize<CS: ConstraintSystem<F>>(
1229 &self,
1230 cs: &mut CS,
1231 z: &[AllocatedNum<F>],
1232 ) -> Result<Vec<AllocatedNum<F>>, SynthesisError> {
1233 let x = &z[0];
1234
1235 // we allocate a variable and set it to the provided non-deterministic advice.
1236 let y = AllocatedNum::alloc(cs.namespace(|| "y"), || Ok(self.y))?;
1237
1238 // We now check if y = x^{1/5} by checking if y^5 = x
1239 let y_sq = y.square(cs.namespace(|| "y_sq"))?;
1240 let y_quad = y_sq.square(cs.namespace(|| "y_quad"))?;
1241 let y_pow_5 = y_quad.mul(cs.namespace(|| "y_fifth"), &y)?;
1242
1243 cs.enforce(
1244 || "y^5 = x",
1245 |lc| lc + y_pow_5.get_variable(),
1246 |lc| lc + CS::one(),
1247 |lc| lc + x.get_variable(),
1248 );
1249
1250 Ok(vec![y])
1251 }
1252
1253 fn output(&self, z: &[F]) -> Vec<F> {
1254 // sanity check
1255 let x = z[0];
1256 let y_pow_5 = {
1257 let y = self.y;
1258 let y_sq = y.square();
1259 let y_quad = y_sq.square();
1260 y_quad * self.y
1261 };
1262 assert_eq!(x, y_pow_5);
1263
1264 // return non-deterministic advice
1265 // as the output of the step
1266 vec![self.y]
1267 }
1268 }
1269
1270 let circuit_primary = FifthRootCheckingCircuit {
1271 y: <G1 as Group>::Scalar::ZERO,
1272 };
1273
1274 let circuit_secondary = TrivialTestCircuit::default();
1275
1276 // produce public parameters
1277 let pp = PublicParams::<
1278 G1,
1279 G2,
1280 FifthRootCheckingCircuit<<G1 as Group>::Scalar>,
1281 TrivialTestCircuit<<G2 as Group>::Scalar>,
1282 >::setup(circuit_primary, circuit_secondary.clone());
1283
1284 let num_steps = 3;
1285
1286 // produce non-deterministic advice
1287 let (z0_primary, roots) = FifthRootCheckingCircuit::new(num_steps);
1288 let z0_secondary = vec![<G2 as Group>::Scalar::ZERO];
1289
1290 // produce a recursive SNARK
1291 let mut recursive_snark: Option<
1292 RecursiveSNARK<
1293 G1,
1294 G2,
1295 FifthRootCheckingCircuit<<G1 as Group>::Scalar>,
1296 TrivialTestCircuit<<G2 as Group>::Scalar>,
1297 >,
1298 > = None;
1299
1300 for circuit_primary in roots.iter().take(num_steps) {
1301 let res = RecursiveSNARK::prove_step(
1302 &pp,
1303 recursive_snark,
1304 circuit_primary.clone(),
1305 circuit_secondary.clone(),
1306 z0_primary.clone(),
1307 z0_secondary.clone(),
1308 );
1309 assert!(res.is_ok());
1310 recursive_snark = Some(res.unwrap());
1311 }
1312
1313 assert!(recursive_snark.is_some());
1314 let recursive_snark = recursive_snark.unwrap();
1315
1316 // verify the recursive SNARK
1317 let res = recursive_snark.verify(&pp, num_steps, z0_primary.clone(), z0_secondary.clone());
1318 assert!(res.is_ok());
1319
1320 // produce the prover and verifier keys for compressed snark
1321 let (pk, vk) = CompressedSNARK::<_, _, _, _, S1<G1>, S2<G2>>::setup(&pp).unwrap();
1322
1323 // produce a compressed SNARK
1324 let res = CompressedSNARK::<_, _, _, _, S1<G1>, S2<G2>>::prove(&pp, &pk, &recursive_snark);
1325 assert!(res.is_ok());
1326 let compressed_snark = res.unwrap();
1327
1328 // verify the compressed SNARK
1329 let res = compressed_snark.verify(&vk, num_steps, z0_primary, z0_secondary);
1330 assert!(res.is_ok());
1331 }
1332
1333 #[test]
1334 fn test_ivc_nondet_with_compression() {
1335 type G1 = pasta_curves::pallas::Point;
1336 type G2 = pasta_curves::vesta::Point;
1337
1338 test_ivc_nondet_with_compression_with::<G1, G2>();
1339 }
1340
1341 fn test_ivc_base_with<G1, G2>()
1342 where
1343 G1: Group<Base = <G2 as Group>::Scalar>,
1344 G2: Group<Base = <G1 as Group>::Scalar>,
1345 {
1346 // produce public parameters
1347 let pp = PublicParams::<
1348 G1,
1349 G2,
1350 TrivialTestCircuit<<G1 as Group>::Scalar>,
1351 CubicCircuit<<G2 as Group>::Scalar>,
1352 >::setup(TrivialTestCircuit::default(), CubicCircuit::default());
1353
1354 let num_steps = 1;
1355
1356 // produce a recursive SNARK
1357 let res = RecursiveSNARK::prove_step(
1358 &pp,
1359 None,
1360 TrivialTestCircuit::default(),
1361 CubicCircuit::default(),
1362 vec![<G1 as Group>::Scalar::ONE],
1363 vec![<G2 as Group>::Scalar::ZERO],
1364 );
1365 assert!(res.is_ok());
1366 let recursive_snark = res.unwrap();
1367
1368 // verify the recursive SNARK
1369 let res = recursive_snark.verify(
1370 &pp,
1371 num_steps,
1372 vec![<G1 as Group>::Scalar::ONE],
1373 vec![<G2 as Group>::Scalar::ZERO],
1374 );
1375 assert!(res.is_ok());
1376
1377 let (zn_primary, zn_secondary) = res.unwrap();
1378
1379 assert_eq!(zn_primary, vec![<G1 as Group>::Scalar::ONE]);
1380 assert_eq!(zn_secondary, vec![<G2 as Group>::Scalar::from(5u64)]);
1381 }
1382
1383 #[test]
1384 fn test_ivc_base() {
1385 type G1 = pasta_curves::pallas::Point;
1386 type G2 = pasta_curves::vesta::Point;
1387
1388 test_ivc_base_with::<G1, G2>();
1389 }
1390}