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