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