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