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#[cfg(test)]
395mod tests {
396 use super::*;
397 type G1 = pasta_curves::pallas::Point;
398 type G2 = pasta_curves::vesta::Point;
399 use ::bellperson::{gadgets::num::AllocatedNum, ConstraintSystem, SynthesisError};
400 use ff::PrimeField;
401 use std::marker::PhantomData;
402
403 #[derive(Clone, Debug)]
404 struct TrivialTestCircuit<F: PrimeField> {
405 _p: PhantomData<F>,
406 }
407
408 impl<F> StepCircuit<F> for TrivialTestCircuit<F>
409 where
410 F: PrimeField,
411 {
412 fn synthesize<CS: ConstraintSystem<F>>(
413 &self,
414 _cs: &mut CS,
415 z: AllocatedNum<F>,
416 ) -> Result<AllocatedNum<F>, SynthesisError> {
417 Ok(z)
418 }
419
420 fn compute(&self, z: &F) -> F {
421 *z
422 }
423 }
424
425 #[derive(Clone, Debug)]
426 struct CubicCircuit<F: PrimeField> {
427 _p: PhantomData<F>,
428 }
429
430 impl<F> StepCircuit<F> for CubicCircuit<F>
431 where
432 F: PrimeField,
433 {
434 fn synthesize<CS: ConstraintSystem<F>>(
435 &self,
436 cs: &mut CS,
437 z: AllocatedNum<F>,
438 ) -> Result<AllocatedNum<F>, SynthesisError> {
439 // Consider a cubic equation: `x^3 + x + 5 = y`, where `x` and `y` are respectively the input and output.
440 let x = z;
441 let x_sq = x.square(cs.namespace(|| "x_sq"))?;
442 let x_cu = x_sq.mul(cs.namespace(|| "x_cu"), &x)?;
443 let y = AllocatedNum::alloc(cs.namespace(|| "y"), || {
444 Ok(x_cu.get_value().unwrap() + x.get_value().unwrap() + F::from(5u64))
445 })?;
446
447 cs.enforce(
448 || "y = x^3 + x + 5",
449 |lc| {
450 lc + x_cu.get_variable()
451 + x.get_variable()
452 + CS::one()
453 + CS::one()
454 + CS::one()
455 + CS::one()
456 + CS::one()
457 },
458 |lc| lc + CS::one(),
459 |lc| lc + y.get_variable(),
460 );
461
462 Ok(y)
463 }
464
465 fn compute(&self, z: &F) -> F {
466 *z * *z * *z + z + F::from(5u64)
467 }
468 }
469
470 #[test]
471 fn test_ivc_trivial() {
472 // produce public parameters
473 let pp = PublicParams::<
474 G1,
475 G2,
476 TrivialTestCircuit<<G1 as Group>::Scalar>,
477 TrivialTestCircuit<<G2 as Group>::Scalar>,
478 >::setup(
479 TrivialTestCircuit {
480 _p: Default::default(),
481 },
482 TrivialTestCircuit {
483 _p: Default::default(),
484 },
485 );
486
487 // produce a recursive SNARK
488 let res = RecursiveSNARK::prove(
489 &pp,
490 3,
491 <G1 as Group>::Scalar::zero(),
492 <G2 as Group>::Scalar::zero(),
493 );
494 assert!(res.is_ok());
495 let recursive_snark = res.unwrap();
496
497 // verify the recursive SNARK
498 let res = recursive_snark.verify(
499 &pp,
500 3,
501 <G1 as Group>::Scalar::zero(),
502 <G2 as Group>::Scalar::zero(),
503 );
504 assert!(res.is_ok());
505 }
506
507 #[test]
508 fn test_ivc_nontrivial() {
509 // produce public parameters
510 let pp = PublicParams::<
511 G1,
512 G2,
513 TrivialTestCircuit<<G1 as Group>::Scalar>,
514 CubicCircuit<<G2 as Group>::Scalar>,
515 >::setup(
516 TrivialTestCircuit {
517 _p: Default::default(),
518 },
519 CubicCircuit {
520 _p: Default::default(),
521 },
522 );
523
524 let num_steps = 3;
525
526 // produce a recursive SNARK
527 let res = RecursiveSNARK::prove(
528 &pp,
529 num_steps,
530 <G1 as Group>::Scalar::one(),
531 <G2 as Group>::Scalar::zero(),
532 );
533 assert!(res.is_ok());
534 let recursive_snark = res.unwrap();
535
536 // verify the recursive SNARK
537 let res = recursive_snark.verify(
538 &pp,
539 num_steps,
540 <G1 as Group>::Scalar::one(),
541 <G2 as Group>::Scalar::zero(),
542 );
543 assert!(res.is_ok());
544
545 let (zn_primary, zn_secondary) = res.unwrap();
546
547 // sanity: check the claimed output with a direct computation of the same
548 assert_eq!(zn_primary, <G1 as Group>::Scalar::one());
549 let mut zn_secondary_direct = <G2 as Group>::Scalar::zero();
550 for _i in 0..num_steps {
551 zn_secondary_direct = CubicCircuit {
552 _p: Default::default(),
553 }
554 .compute(&zn_secondary_direct);
555 }
556 assert_eq!(zn_secondary, zn_secondary_direct);
557 assert_eq!(zn_secondary, <G2 as Group>::Scalar::from(2460515u64));
558 }
559
560 #[test]
561 fn test_ivc_base() {
562 // produce public parameters
563 let pp = PublicParams::<
564 G1,
565 G2,
566 TrivialTestCircuit<<G1 as Group>::Scalar>,
567 CubicCircuit<<G2 as Group>::Scalar>,
568 >::setup(
569 TrivialTestCircuit {
570 _p: Default::default(),
571 },
572 CubicCircuit {
573 _p: Default::default(),
574 },
575 );
576
577 let num_steps = 1;
578
579 // produce a recursive SNARK
580 let res = RecursiveSNARK::prove(
581 &pp,
582 num_steps,
583 <G1 as Group>::Scalar::one(),
584 <G2 as Group>::Scalar::zero(),
585 );
586 assert!(res.is_ok());
587 let recursive_snark = res.unwrap();
588
589 // verify the recursive SNARK
590 let res = recursive_snark.verify(
591 &pp,
592 num_steps,
593 <G1 as Group>::Scalar::one(),
594 <G2 as Group>::Scalar::zero(),
595 );
596 assert!(res.is_ok());
597
598 let (zn_primary, zn_secondary) = res.unwrap();
599
600 assert_eq!(zn_primary, <G1 as Group>::Scalar::one());
601 assert_eq!(zn_secondary, <G2 as Group>::Scalar::from(5u64));
602 }
603}