Nova/src/lib.rs
src/lib.rsRaw
1//! This library implements core components of Nova.
2#![allow(non_snake_case)]
3#![allow(clippy::type_complexity)]
4#![deny(missing_docs)]
5
6pub mod bellperson;
7mod circuit;
8mod commitments;
9mod constants;
10pub mod errors;
11pub mod gadgets;
12pub mod nifs;
13pub mod pasta;
14mod poseidon;
15pub mod r1cs;
16pub mod traits;
17
18use crate::bellperson::{
19 r1cs::{NovaShape, NovaWitness},
20 shape_cs::ShapeCS,
21 solver::SatisfyingAssignment,
22};
23use ::bellperson::{Circuit, ConstraintSystem};
24use circuit::{NIFSVerifierCircuit, NIFSVerifierCircuitInputs, NIFSVerifierCircuitParams};
25use constants::{BN_LIMB_WIDTH, BN_N_LIMBS};
26use core::marker::PhantomData;
27use errors::NovaError;
28use ff::Field;
29use gadgets::utils::scalar_as_base;
30use nifs::NIFS;
31use poseidon::ROConstantsCircuit; // TODO: make this a trait so we can use it without the concrete implementation
32use r1cs::{
33 R1CSGens, R1CSInstance, R1CSShape, R1CSWitness, RelaxedR1CSInstance, RelaxedR1CSWitness,
34};
35use traits::{AbsorbInROTrait, Group, HashFuncConstantsTrait, HashFuncTrait, StepCircuit};
36
37type ROConstants<G> =
38 <<G as Group>::HashFunc as HashFuncTrait<<G as Group>::Base, <G as Group>::Scalar>>::Constants;
39
40/// A type that holds public parameters of Nova
41pub struct PublicParams<G1, G2, C1, C2>
42where
43 G1: Group<Base = <G2 as Group>::Scalar>,
44 G2: Group<Base = <G1 as Group>::Scalar>,
45 C1: StepCircuit<G1::Scalar> + Clone,
46 C2: StepCircuit<G2::Scalar> + Clone,
47{
48 ro_consts_primary: ROConstants<G1>,
49 ro_consts_circuit_primary: ROConstantsCircuit<<G2 as Group>::Base>,
50 r1cs_gens_primary: R1CSGens<G1>,
51 r1cs_shape_primary: R1CSShape<G1>,
52 ro_consts_secondary: ROConstants<G2>,
53 ro_consts_circuit_secondary: ROConstantsCircuit<<G1 as Group>::Base>,
54 r1cs_gens_secondary: R1CSGens<G2>,
55 r1cs_shape_secondary: R1CSShape<G2>,
56 c_primary: C1,
57 c_secondary: C2,
58 params_primary: NIFSVerifierCircuitParams,
59 params_secondary: NIFSVerifierCircuitParams,
60}
61
62impl<G1, G2, C1, C2> PublicParams<G1, G2, C1, C2>
63where
64 G1: Group<Base = <G2 as Group>::Scalar>,
65 G2: Group<Base = <G1 as Group>::Scalar>,
66 C1: StepCircuit<G1::Scalar> + Clone,
67 C2: StepCircuit<G2::Scalar> + Clone,
68{
69 /// Create a new `PublicParams`
70 pub fn setup(c_primary: C1, c_secondary: C2) -> Self {
71 let params_primary = NIFSVerifierCircuitParams::new(BN_LIMB_WIDTH, BN_N_LIMBS, true);
72 let params_secondary = NIFSVerifierCircuitParams::new(BN_LIMB_WIDTH, BN_N_LIMBS, false);
73
74 let ro_consts_primary: ROConstants<G1> = ROConstants::<G1>::new();
75 let ro_consts_secondary: ROConstants<G2> = ROConstants::<G2>::new();
76
77 let ro_consts_circuit_primary: ROConstantsCircuit<<G2 as Group>::Base> =
78 ROConstantsCircuit::new();
79 let ro_consts_circuit_secondary: ROConstantsCircuit<<G1 as Group>::Base> =
80 ROConstantsCircuit::new();
81
82 // Initialize gens for the primary
83 let circuit_primary: NIFSVerifierCircuit<G2, C1> = NIFSVerifierCircuit::new(
84 params_primary.clone(),
85 None,
86 c_primary.clone(),
87 ro_consts_circuit_primary.clone(),
88 );
89 let mut cs: ShapeCS<G1> = ShapeCS::new();
90 let _ = circuit_primary.synthesize(&mut cs);
91 let (r1cs_shape_primary, r1cs_gens_primary) = (cs.r1cs_shape(), cs.r1cs_gens());
92
93 // Initialize gens for the secondary
94 let circuit_secondary: NIFSVerifierCircuit<G1, C2> = NIFSVerifierCircuit::new(
95 params_secondary.clone(),
96 None,
97 c_secondary.clone(),
98 ro_consts_circuit_secondary.clone(),
99 );
100 let mut cs: ShapeCS<G2> = ShapeCS::new();
101 let _ = circuit_secondary.synthesize(&mut cs);
102 let (r1cs_shape_secondary, r1cs_gens_secondary) = (cs.r1cs_shape(), cs.r1cs_gens());
103
104 Self {
105 ro_consts_primary,
106 ro_consts_circuit_primary,
107 r1cs_gens_primary,
108 r1cs_shape_primary,
109 ro_consts_secondary,
110 ro_consts_circuit_secondary,
111 r1cs_gens_secondary,
112 r1cs_shape_secondary,
113 c_primary,
114 c_secondary,
115 params_primary,
116 params_secondary,
117 }
118 }
119}
120
121/// A SNARK that proves the correct execution of an incremental computation
122pub struct RecursiveSNARK<G1, G2, C1, C2>
123where
124 G1: Group<Base = <G2 as Group>::Scalar>,
125 G2: Group<Base = <G1 as Group>::Scalar>,
126 C1: StepCircuit<G1::Scalar> + Clone,
127 C2: StepCircuit<G2::Scalar> + Clone,
128{
129 r_W_primary: RelaxedR1CSWitness<G1>,
130 r_U_primary: RelaxedR1CSInstance<G1>,
131 l_w_primary: R1CSWitness<G1>,
132 l_u_primary: R1CSInstance<G1>,
133 r_W_secondary: RelaxedR1CSWitness<G2>,
134 r_U_secondary: RelaxedR1CSInstance<G2>,
135 l_w_secondary: R1CSWitness<G2>,
136 l_u_secondary: R1CSInstance<G2>,
137 zn_primary: G1::Scalar,
138 zn_secondary: G2::Scalar,
139 _p_c1: PhantomData<C1>,
140 _p_c2: PhantomData<C2>,
141}
142
143impl<G1, G2, C1, C2> RecursiveSNARK<G1, G2, C1, C2>
144where
145 G1: Group<Base = <G2 as Group>::Scalar>,
146 G2: Group<Base = <G1 as Group>::Scalar>,
147 C1: StepCircuit<G1::Scalar> + Clone,
148 C2: StepCircuit<G2::Scalar> + Clone,
149{
150 /// Create a new `RecursiveSNARK`
151 pub fn prove(
152 pp: &PublicParams<G1, G2, C1, C2>,
153 num_steps: usize,
154 z0_primary: G1::Scalar,
155 z0_secondary: G2::Scalar,
156 ) -> Result<Self, NovaError> {
157 if num_steps == 0 {
158 return Err(NovaError::InvalidNumSteps);
159 }
160
161 // Execute the base case for the primary
162 let mut cs_primary: SatisfyingAssignment<G1> = SatisfyingAssignment::new();
163 let inputs_primary: NIFSVerifierCircuitInputs<G2> = NIFSVerifierCircuitInputs::new(
164 pp.r1cs_shape_secondary.get_digest(),
165 G1::Scalar::zero(),
166 z0_primary,
167 None,
168 None,
169 None,
170 None,
171 );
172 let circuit_primary: NIFSVerifierCircuit<G2, C1> = NIFSVerifierCircuit::new(
173 pp.params_primary.clone(),
174 Some(inputs_primary),
175 pp.c_primary.clone(),
176 pp.ro_consts_circuit_primary.clone(),
177 );
178 let _ = circuit_primary.synthesize(&mut cs_primary);
179 let (u_primary, w_primary) = cs_primary
180 .r1cs_instance_and_witness(&pp.r1cs_shape_primary, &pp.r1cs_gens_primary)
181 .map_err(|_e| NovaError::UnSat)?;
182
183 // Execute the base case for the secondary
184 let mut cs_secondary: SatisfyingAssignment<G2> = SatisfyingAssignment::new();
185 let inputs_secondary: NIFSVerifierCircuitInputs<G1> = NIFSVerifierCircuitInputs::new(
186 pp.r1cs_shape_primary.get_digest(),
187 G2::Scalar::zero(),
188 z0_secondary,
189 None,
190 None,
191 Some(u_primary.clone()),
192 None,
193 );
194 let circuit_secondary: NIFSVerifierCircuit<G1, C2> = NIFSVerifierCircuit::new(
195 pp.params_secondary.clone(),
196 Some(inputs_secondary),
197 pp.c_secondary.clone(),
198 pp.ro_consts_circuit_secondary.clone(),
199 );
200 let _ = circuit_secondary.synthesize(&mut cs_secondary);
201 let (u_secondary, w_secondary) = cs_secondary
202 .r1cs_instance_and_witness(&pp.r1cs_shape_secondary, &pp.r1cs_gens_secondary)
203 .map_err(|_e| NovaError::UnSat)?;
204
205 // execute the remaining steps, alternating between G1 and G2
206 let mut l_w_primary = w_primary;
207 let mut l_u_primary = u_primary;
208 let mut r_W_primary =
209 RelaxedR1CSWitness::from_r1cs_witness(&pp.r1cs_shape_primary, &l_w_primary);
210 let mut r_U_primary = RelaxedR1CSInstance::from_r1cs_instance(
211 &pp.r1cs_gens_primary,
212 &pp.r1cs_shape_primary,
213 &l_u_primary,
214 );
215
216 let mut r_W_secondary = RelaxedR1CSWitness::<G2>::default(&pp.r1cs_shape_secondary);
217 let mut r_U_secondary =
218 RelaxedR1CSInstance::<G2>::default(&pp.r1cs_gens_secondary, &pp.r1cs_shape_secondary);
219 let mut l_w_secondary = w_secondary;
220 let mut l_u_secondary = u_secondary;
221
222 let mut z_next_primary = z0_primary;
223 let mut z_next_secondary = z0_secondary;
224 z_next_primary = pp.c_primary.compute(&z_next_primary);
225 z_next_secondary = pp.c_secondary.compute(&z_next_secondary);
226
227 for i in 1..num_steps {
228 // fold the secondary circuit's instance
229 let (nifs_secondary, (r_U_next_secondary, r_W_next_secondary)) = NIFS::prove(
230 &pp.r1cs_gens_secondary,
231 &pp.ro_consts_secondary,
232 &pp.r1cs_shape_secondary,
233 &r_U_secondary,
234 &r_W_secondary,
235 &l_u_secondary,
236 &l_w_secondary,
237 )?;
238
239 let mut cs_primary: SatisfyingAssignment<G1> = SatisfyingAssignment::new();
240 let inputs_primary: NIFSVerifierCircuitInputs<G2> = NIFSVerifierCircuitInputs::new(
241 pp.r1cs_shape_secondary.get_digest(),
242 G1::Scalar::from(i as u64),
243 z0_primary,
244 Some(z_next_primary),
245 Some(r_U_secondary),
246 Some(l_u_secondary),
247 Some(nifs_secondary.comm_T.decompress()?),
248 );
249
250 let circuit_primary: NIFSVerifierCircuit<G2, C1> = NIFSVerifierCircuit::new(
251 pp.params_primary.clone(),
252 Some(inputs_primary),
253 pp.c_primary.clone(),
254 pp.ro_consts_circuit_primary.clone(),
255 );
256 let _ = circuit_primary.synthesize(&mut cs_primary);
257
258 (l_u_primary, l_w_primary) = cs_primary
259 .r1cs_instance_and_witness(&pp.r1cs_shape_primary, &pp.r1cs_gens_primary)
260 .map_err(|_e| NovaError::UnSat)?;
261
262 // fold the primary circuit's instance
263 let (nifs_primary, (r_U_next_primary, r_W_next_primary)) = NIFS::prove(
264 &pp.r1cs_gens_primary,
265 &pp.ro_consts_primary,
266 &pp.r1cs_shape_primary,
267 &r_U_primary.clone(),
268 &r_W_primary.clone(),
269 &l_u_primary.clone(),
270 &l_w_primary.clone(),
271 )?;
272
273 let mut cs_secondary: SatisfyingAssignment<G2> = SatisfyingAssignment::new();
274 let inputs_secondary: NIFSVerifierCircuitInputs<G1> = NIFSVerifierCircuitInputs::new(
275 pp.r1cs_shape_primary.get_digest(),
276 G2::Scalar::from(i as u64),
277 z0_secondary,
278 Some(z_next_secondary),
279 Some(r_U_primary.clone()),
280 Some(l_u_primary.clone()),
281 Some(nifs_primary.comm_T.decompress()?),
282 );
283
284 let circuit_secondary: NIFSVerifierCircuit<G1, C2> = NIFSVerifierCircuit::new(
285 pp.params_secondary.clone(),
286 Some(inputs_secondary),
287 pp.c_secondary.clone(),
288 pp.ro_consts_circuit_secondary.clone(),
289 );
290 let _ = circuit_secondary.synthesize(&mut cs_secondary);
291
292 (l_u_secondary, l_w_secondary) = cs_secondary
293 .r1cs_instance_and_witness(&pp.r1cs_shape_secondary, &pp.r1cs_gens_secondary)
294 .map_err(|_e| NovaError::UnSat)?;
295
296 // update the running instances and witnesses
297 r_U_secondary = r_U_next_secondary;
298 r_W_secondary = r_W_next_secondary;
299 r_U_primary = r_U_next_primary;
300 r_W_primary = r_W_next_primary;
301 z_next_primary = pp.c_primary.compute(&z_next_primary);
302 z_next_secondary = pp.c_secondary.compute(&z_next_secondary);
303 }
304
305 Ok(Self {
306 r_W_primary,
307 r_U_primary,
308 l_w_primary,
309 l_u_primary,
310 r_W_secondary,
311 r_U_secondary,
312 l_w_secondary,
313 l_u_secondary,
314 zn_primary: z_next_primary,
315 zn_secondary: z_next_secondary,
316 _p_c1: Default::default(),
317 _p_c2: Default::default(),
318 })
319 }
320
321 /// Verify the correctness of the `RecursiveSNARK`
322 pub fn verify(
323 &self,
324 pp: &PublicParams<G1, G2, C1, C2>,
325 num_steps: usize,
326 z0_primary: G1::Scalar,
327 z0_secondary: G2::Scalar,
328 ) -> Result<(G1::Scalar, G2::Scalar), NovaError> {
329 // number of steps cannot be zero
330 if num_steps == 0 {
331 return Err(NovaError::ProofVerifyError);
332 }
333
334 // check if the (relaxed) R1CS instances have two public outputs
335 if self.l_u_primary.X.len() != 2
336 || self.l_u_secondary.X.len() != 2
337 || self.r_U_primary.X.len() != 2
338 || self.r_U_secondary.X.len() != 2
339 {
340 return Err(NovaError::ProofVerifyError);
341 }
342
343 // check if the output hashes in R1CS instances point to the right running instances
344 let (hash_primary, hash_secondary) = {
345 let mut hasher = <G2 as Group>::HashFunc::new(pp.ro_consts_secondary.clone());
346 hasher.absorb(scalar_as_base::<G2>(pp.r1cs_shape_secondary.get_digest()));
347 hasher.absorb(G1::Scalar::from(num_steps as u64));
348 hasher.absorb(z0_primary);
349 hasher.absorb(self.zn_primary);
350 self.r_U_secondary.absorb_in_ro(&mut hasher);
351
352 let mut hasher2 = <G1 as Group>::HashFunc::new(pp.ro_consts_primary.clone());
353 hasher2.absorb(scalar_as_base::<G1>(pp.r1cs_shape_primary.get_digest()));
354 hasher2.absorb(G2::Scalar::from(num_steps as u64));
355 hasher2.absorb(z0_secondary);
356 hasher2.absorb(self.zn_secondary);
357 self.r_U_primary.absorb_in_ro(&mut hasher2);
358
359 (hasher.get_hash(), hasher2.get_hash())
360 };
361
362 if hash_primary != scalar_as_base::<G1>(self.l_u_primary.X[1])
363 || hash_secondary != scalar_as_base::<G2>(self.l_u_secondary.X[1])
364 {
365 return Err(NovaError::ProofVerifyError);
366 }
367
368 // check the satisfiability of the provided instances
369 pp.r1cs_shape_primary.is_sat_relaxed(
370 &pp.r1cs_gens_primary,
371 &self.r_U_primary,
372 &self.r_W_primary,
373 )?;
374
375 pp.r1cs_shape_primary
376 .is_sat(&pp.r1cs_gens_primary, &self.l_u_primary, &self.l_w_primary)?;
377
378 pp.r1cs_shape_secondary.is_sat_relaxed(
379 &pp.r1cs_gens_secondary,
380 &self.r_U_secondary,
381 &self.r_W_secondary,
382 )?;
383
384 pp.r1cs_shape_secondary.is_sat(
385 &pp.r1cs_gens_secondary,
386 &self.l_u_secondary,
387 &self.l_w_secondary,
388 )?;
389
390 Ok((self.zn_primary, self.zn_secondary))
391 }
392}
393
394/// A SNARK that proves the knowledge of a valid `RecursiveSNARK`
395/// For now, it implements a constant factor compression.
396/// In the future, we will implement an exponential reduction in proof sizes
397pub struct CompressedSNARK<G1, G2, C1, C2>
398where
399 G1: Group<Base = <G2 as Group>::Scalar>,
400 G2: Group<Base = <G1 as Group>::Scalar>,
401 C1: StepCircuit<G1::Scalar> + Clone,
402 C2: StepCircuit<G2::Scalar> + Clone,
403{
404 r_U_primary: RelaxedR1CSInstance<G1>,
405 l_u_primary: R1CSInstance<G1>,
406 nifs_primary: NIFS<G1>,
407 f_W_primary: RelaxedR1CSWitness<G1>,
408
409 r_U_secondary: RelaxedR1CSInstance<G2>,
410 l_u_secondary: R1CSInstance<G2>,
411 nifs_secondary: NIFS<G2>,
412 f_W_secondary: RelaxedR1CSWitness<G2>,
413
414 zn_primary: G1::Scalar,
415 zn_secondary: G2::Scalar,
416
417 _p_c1: PhantomData<C1>,
418 _p_c2: PhantomData<C2>,
419}
420
421impl<G1, G2, C1, C2> CompressedSNARK<G1, G2, C1, C2>
422where
423 G1: Group<Base = <G2 as Group>::Scalar>,
424 G2: Group<Base = <G1 as Group>::Scalar>,
425 C1: StepCircuit<G1::Scalar> + Clone,
426 C2: StepCircuit<G2::Scalar> + Clone,
427{
428 /// Create a new `CompressedSNARK`
429 pub fn prove(
430 pp: &PublicParams<G1, G2, C1, C2>,
431 recursive_snark: &RecursiveSNARK<G1, G2, C1, C2>,
432 ) -> Result<Self, NovaError> {
433 // fold the primary circuit's instance
434 let (nifs_primary, (_f_U_primary, f_W_primary)) = NIFS::prove(
435 &pp.r1cs_gens_primary,
436 &pp.ro_consts_primary,
437 &pp.r1cs_shape_primary,
438 &recursive_snark.r_U_primary,
439 &recursive_snark.r_W_primary,
440 &recursive_snark.l_u_primary,
441 &recursive_snark.l_w_primary,
442 )?;
443
444 // fold the secondary circuit's instance
445 let (nifs_secondary, (_f_U_secondary, f_W_secondary)) = NIFS::prove(
446 &pp.r1cs_gens_secondary,
447 &pp.ro_consts_secondary,
448 &pp.r1cs_shape_secondary,
449 &recursive_snark.r_U_secondary,
450 &recursive_snark.r_W_secondary,
451 &recursive_snark.l_u_secondary,
452 &recursive_snark.l_w_secondary,
453 )?;
454
455 Ok(Self {
456 r_U_primary: recursive_snark.r_U_primary.clone(),
457 l_u_primary: recursive_snark.l_u_primary.clone(),
458 nifs_primary,
459 f_W_primary,
460
461 r_U_secondary: recursive_snark.r_U_secondary.clone(),
462 l_u_secondary: recursive_snark.l_u_secondary.clone(),
463 nifs_secondary,
464 f_W_secondary,
465
466 zn_primary: recursive_snark.zn_primary,
467 zn_secondary: recursive_snark.zn_secondary,
468
469 _p_c1: Default::default(),
470 _p_c2: Default::default(),
471 })
472 }
473
474 /// Verify the correctness of the `CompressedSNARK`
475 pub fn verify(
476 &self,
477 pp: &PublicParams<G1, G2, C1, C2>,
478 num_steps: usize,
479 z0_primary: G1::Scalar,
480 z0_secondary: G2::Scalar,
481 ) -> Result<(G1::Scalar, G2::Scalar), NovaError> {
482 // number of steps cannot be zero
483 if num_steps == 0 {
484 return Err(NovaError::ProofVerifyError);
485 }
486
487 // check if the (relaxed) R1CS instances have two public outputs
488 if self.l_u_primary.X.len() != 2
489 || self.l_u_secondary.X.len() != 2
490 || self.r_U_primary.X.len() != 2
491 || self.r_U_secondary.X.len() != 2
492 {
493 return Err(NovaError::ProofVerifyError);
494 }
495
496 // check if the output hashes in R1CS instances point to the right running instances
497 let (hash_primary, hash_secondary) = {
498 let mut hasher = <G2 as Group>::HashFunc::new(pp.ro_consts_secondary.clone());
499 hasher.absorb(scalar_as_base::<G2>(pp.r1cs_shape_secondary.get_digest()));
500 hasher.absorb(G1::Scalar::from(num_steps as u64));
501 hasher.absorb(z0_primary);
502 hasher.absorb(self.zn_primary);
503 self.r_U_secondary.absorb_in_ro(&mut hasher);
504
505 let mut hasher2 = <G1 as Group>::HashFunc::new(pp.ro_consts_primary.clone());
506 hasher2.absorb(scalar_as_base::<G1>(pp.r1cs_shape_primary.get_digest()));
507 hasher2.absorb(G2::Scalar::from(num_steps as u64));
508 hasher2.absorb(z0_secondary);
509 hasher2.absorb(self.zn_secondary);
510 self.r_U_primary.absorb_in_ro(&mut hasher2);
511
512 (hasher.get_hash(), hasher2.get_hash())
513 };
514
515 if hash_primary != scalar_as_base::<G1>(self.l_u_primary.X[1])
516 || hash_secondary != scalar_as_base::<G2>(self.l_u_secondary.X[1])
517 {
518 return Err(NovaError::ProofVerifyError);
519 }
520
521 // fold the running instance and last instance to get a folded instance
522 let f_U_primary = self.nifs_primary.verify(
523 &pp.ro_consts_primary,
524 &pp.r1cs_shape_primary,
525 &self.r_U_primary,
526 &self.l_u_primary,
527 )?;
528 let f_U_secondary = self.nifs_secondary.verify(
529 &pp.ro_consts_secondary,
530 &pp.r1cs_shape_secondary,
531 &self.r_U_secondary,
532 &self.l_u_secondary,
533 )?;
534
535 // check the satisfiability of the folded instances using the purported folded witnesses
536 pp.r1cs_shape_primary
537 .is_sat_relaxed(&pp.r1cs_gens_primary, &f_U_primary, &self.f_W_primary)?;
538
539 pp.r1cs_shape_secondary.is_sat_relaxed(
540 &pp.r1cs_gens_secondary,
541 &f_U_secondary,
542 &self.f_W_secondary,
543 )?;
544
545 Ok((self.zn_primary, self.zn_secondary))
546 }
547}
548
549#[cfg(test)]
550mod tests {
551 use super::*;
552 type G1 = pasta_curves::pallas::Point;
553 type G2 = pasta_curves::vesta::Point;
554 use ::bellperson::{gadgets::num::AllocatedNum, ConstraintSystem, SynthesisError};
555 use ff::PrimeField;
556 use std::marker::PhantomData;
557
558 #[derive(Clone, Debug)]
559 struct TrivialTestCircuit<F: PrimeField> {
560 _p: PhantomData<F>,
561 }
562
563 impl<F> StepCircuit<F> for TrivialTestCircuit<F>
564 where
565 F: PrimeField,
566 {
567 fn synthesize<CS: ConstraintSystem<F>>(
568 &self,
569 _cs: &mut CS,
570 z: AllocatedNum<F>,
571 ) -> Result<AllocatedNum<F>, SynthesisError> {
572 Ok(z)
573 }
574
575 fn compute(&self, z: &F) -> F {
576 *z
577 }
578 }
579
580 #[derive(Clone, Debug)]
581 struct CubicCircuit<F: PrimeField> {
582 _p: PhantomData<F>,
583 }
584
585 impl<F> StepCircuit<F> for CubicCircuit<F>
586 where
587 F: PrimeField,
588 {
589 fn synthesize<CS: ConstraintSystem<F>>(
590 &self,
591 cs: &mut CS,
592 z: AllocatedNum<F>,
593 ) -> Result<AllocatedNum<F>, SynthesisError> {
594 // Consider a cubic equation: `x^3 + x + 5 = y`, where `x` and `y` are respectively the input and output.
595 let x = z;
596 let x_sq = x.square(cs.namespace(|| "x_sq"))?;
597 let x_cu = x_sq.mul(cs.namespace(|| "x_cu"), &x)?;
598 let y = AllocatedNum::alloc(cs.namespace(|| "y"), || {
599 Ok(x_cu.get_value().unwrap() + x.get_value().unwrap() + F::from(5u64))
600 })?;
601
602 cs.enforce(
603 || "y = x^3 + x + 5",
604 |lc| {
605 lc + x_cu.get_variable()
606 + x.get_variable()
607 + CS::one()
608 + CS::one()
609 + CS::one()
610 + CS::one()
611 + CS::one()
612 },
613 |lc| lc + CS::one(),
614 |lc| lc + y.get_variable(),
615 );
616
617 Ok(y)
618 }
619
620 fn compute(&self, z: &F) -> F {
621 *z * *z * *z + z + F::from(5u64)
622 }
623 }
624
625 #[test]
626 fn test_ivc_trivial() {
627 // produce public parameters
628 let pp = PublicParams::<
629 G1,
630 G2,
631 TrivialTestCircuit<<G1 as Group>::Scalar>,
632 TrivialTestCircuit<<G2 as Group>::Scalar>,
633 >::setup(
634 TrivialTestCircuit {
635 _p: Default::default(),
636 },
637 TrivialTestCircuit {
638 _p: Default::default(),
639 },
640 );
641
642 // produce a recursive SNARK
643 let res = RecursiveSNARK::prove(
644 &pp,
645 3,
646 <G1 as Group>::Scalar::zero(),
647 <G2 as Group>::Scalar::zero(),
648 );
649 assert!(res.is_ok());
650 let recursive_snark = res.unwrap();
651
652 // verify the recursive SNARK
653 let res = recursive_snark.verify(
654 &pp,
655 3,
656 <G1 as Group>::Scalar::zero(),
657 <G2 as Group>::Scalar::zero(),
658 );
659 assert!(res.is_ok());
660 }
661
662 #[test]
663 fn test_ivc_nontrivial() {
664 // produce public parameters
665 let pp = PublicParams::<
666 G1,
667 G2,
668 TrivialTestCircuit<<G1 as Group>::Scalar>,
669 CubicCircuit<<G2 as Group>::Scalar>,
670 >::setup(
671 TrivialTestCircuit {
672 _p: Default::default(),
673 },
674 CubicCircuit {
675 _p: Default::default(),
676 },
677 );
678
679 let num_steps = 3;
680
681 // produce a recursive SNARK
682 let res = RecursiveSNARK::prove(
683 &pp,
684 num_steps,
685 <G1 as Group>::Scalar::one(),
686 <G2 as Group>::Scalar::zero(),
687 );
688 assert!(res.is_ok());
689 let recursive_snark = res.unwrap();
690
691 // verify the recursive SNARK
692 let res = recursive_snark.verify(
693 &pp,
694 num_steps,
695 <G1 as Group>::Scalar::one(),
696 <G2 as Group>::Scalar::zero(),
697 );
698 assert!(res.is_ok());
699
700 let (zn_primary, zn_secondary) = res.unwrap();
701
702 // sanity: check the claimed output with a direct computation of the same
703 assert_eq!(zn_primary, <G1 as Group>::Scalar::one());
704 let mut zn_secondary_direct = <G2 as Group>::Scalar::zero();
705 for _i in 0..num_steps {
706 zn_secondary_direct = CubicCircuit {
707 _p: Default::default(),
708 }
709 .compute(&zn_secondary_direct);
710 }
711 assert_eq!(zn_secondary, zn_secondary_direct);
712 assert_eq!(zn_secondary, <G2 as Group>::Scalar::from(2460515u64));
713
714 // produce a compressed SNARK
715 let res = CompressedSNARK::prove(&pp, &recursive_snark);
716 assert!(res.is_ok());
717 let compressed_snark = res.unwrap();
718
719 // verify the compressed SNARK
720 let res = compressed_snark.verify(
721 &pp,
722 num_steps,
723 <G1 as Group>::Scalar::one(),
724 <G2 as Group>::Scalar::zero(),
725 );
726 assert!(res.is_ok());
727 }
728
729 #[test]
730 fn test_ivc_base() {
731 // produce public parameters
732 let pp = PublicParams::<
733 G1,
734 G2,
735 TrivialTestCircuit<<G1 as Group>::Scalar>,
736 CubicCircuit<<G2 as Group>::Scalar>,
737 >::setup(
738 TrivialTestCircuit {
739 _p: Default::default(),
740 },
741 CubicCircuit {
742 _p: Default::default(),
743 },
744 );
745
746 let num_steps = 1;
747
748 // produce a recursive SNARK
749 let res = RecursiveSNARK::prove(
750 &pp,
751 num_steps,
752 <G1 as Group>::Scalar::one(),
753 <G2 as Group>::Scalar::zero(),
754 );
755 assert!(res.is_ok());
756 let recursive_snark = res.unwrap();
757
758 // verify the recursive SNARK
759 let res = recursive_snark.verify(
760 &pp,
761 num_steps,
762 <G1 as Group>::Scalar::one(),
763 <G2 as Group>::Scalar::zero(),
764 );
765 assert!(res.is_ok());
766
767 let (zn_primary, zn_secondary) = res.unwrap();
768
769 assert_eq!(zn_primary, <G1 as Group>::Scalar::one());
770 assert_eq!(zn_secondary, <G2 as Group>::Scalar::from(5u64));
771 }
772}