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 nifs::NIFS;
30use poseidon::ROConstantsCircuit; // TODO: make this a trait so we can use it without the concrete implementation
31use r1cs::{
32 R1CSGens, R1CSInstance, R1CSShape, R1CSWitness, RelaxedR1CSInstance, RelaxedR1CSWitness,
33};
34use traits::{Group, HashFuncConstantsTrait, HashFuncTrait, StepCircuit};
35
36type ROConstants<G> =
37 <<G as Group>::HashFunc as HashFuncTrait<<G as Group>::Base, <G as Group>::Scalar>>::Constants;
38
39/// A type that holds public parameters of Nova
40pub struct PublicParams<G1, G2, C1, C2>
41where
42 G1: Group<Base = <G2 as Group>::Scalar>,
43 G2: Group<Base = <G1 as Group>::Scalar>,
44 C1: StepCircuit<G1::Scalar> + Clone,
45 C2: StepCircuit<G2::Scalar> + Clone,
46{
47 ro_consts_primary: ROConstants<G1>,
48 ro_consts_circuit_primary: ROConstantsCircuit<<G2 as Group>::Base>,
49 r1cs_gens_primary: R1CSGens<G1>,
50 r1cs_shape_primary: R1CSShape<G1>,
51 ro_consts_secondary: ROConstants<G2>,
52 ro_consts_circuit_secondary: ROConstantsCircuit<<G1 as Group>::Base>,
53 r1cs_gens_secondary: R1CSGens<G2>,
54 r1cs_shape_secondary: R1CSShape<G2>,
55 c_primary: C1,
56 c_secondary: C2,
57 params_primary: NIFSVerifierCircuitParams,
58 params_secondary: NIFSVerifierCircuitParams,
59}
60
61impl<G1, G2, C1, C2> PublicParams<G1, G2, C1, C2>
62where
63 G1: Group<Base = <G2 as Group>::Scalar>,
64 G2: Group<Base = <G1 as Group>::Scalar>,
65 C1: StepCircuit<G1::Scalar> + Clone,
66 C2: StepCircuit<G2::Scalar> + Clone,
67{
68 /// Create a new `PublicParams`
69 pub fn setup(c_primary: C1, c_secondary: C2) -> Self {
70 let params_primary = NIFSVerifierCircuitParams::new(BN_LIMB_WIDTH, BN_N_LIMBS, true);
71 let params_secondary = NIFSVerifierCircuitParams::new(BN_LIMB_WIDTH, BN_N_LIMBS, false);
72
73 let ro_consts_primary: ROConstants<G1> = ROConstants::<G1>::new();
74 let ro_consts_secondary: ROConstants<G2> = ROConstants::<G2>::new();
75
76 let ro_consts_circuit_primary: ROConstantsCircuit<<G2 as Group>::Base> =
77 ROConstantsCircuit::new();
78 let ro_consts_circuit_secondary: ROConstantsCircuit<<G1 as Group>::Base> =
79 ROConstantsCircuit::new();
80
81 // Initialize gens for the primary
82 let circuit_primary: NIFSVerifierCircuit<G2, C1> = NIFSVerifierCircuit::new(
83 params_primary.clone(),
84 None,
85 c_primary.clone(),
86 ro_consts_circuit_primary.clone(),
87 );
88 let mut cs: ShapeCS<G1> = ShapeCS::new();
89 let _ = circuit_primary.synthesize(&mut cs);
90 let (r1cs_shape_primary, r1cs_gens_primary) = (cs.r1cs_shape(), cs.r1cs_gens());
91
92 // Initialize gens for the secondary
93 let circuit_secondary: NIFSVerifierCircuit<G1, C2> = NIFSVerifierCircuit::new(
94 params_secondary.clone(),
95 None,
96 c_secondary.clone(),
97 ro_consts_circuit_secondary.clone(),
98 );
99 let mut cs: ShapeCS<G2> = ShapeCS::new();
100 let _ = circuit_secondary.synthesize(&mut cs);
101 let (r1cs_shape_secondary, r1cs_gens_secondary) = (cs.r1cs_shape(), cs.r1cs_gens());
102
103 Self {
104 ro_consts_primary,
105 ro_consts_circuit_primary,
106 r1cs_gens_primary,
107 r1cs_shape_primary,
108 ro_consts_secondary,
109 ro_consts_circuit_secondary,
110 r1cs_gens_secondary,
111 r1cs_shape_secondary,
112 c_primary,
113 c_secondary,
114 params_primary,
115 params_secondary,
116 }
117 }
118}
119
120/// A SNARK that proves the correct execution of an incremental computation
121pub struct RecursiveSNARK<G1, G2, C1, C2>
122where
123 G1: Group<Base = <G2 as Group>::Scalar>,
124 G2: Group<Base = <G1 as Group>::Scalar>,
125 C1: StepCircuit<G1::Scalar> + Clone,
126 C2: StepCircuit<G2::Scalar> + Clone,
127{
128 r_W_primary: RelaxedR1CSWitness<G1>,
129 r_U_primary: RelaxedR1CSInstance<G1>,
130 l_w_primary: R1CSWitness<G1>,
131 l_u_primary: R1CSInstance<G1>,
132 r_W_secondary: RelaxedR1CSWitness<G2>,
133 r_U_secondary: RelaxedR1CSInstance<G2>,
134 l_w_secondary: R1CSWitness<G2>,
135 l_u_secondary: R1CSInstance<G2>,
136 _p_c1: PhantomData<C1>,
137 _p_c2: PhantomData<C2>,
138}
139
140impl<G1, G2, C1, C2> RecursiveSNARK<G1, G2, C1, C2>
141where
142 G1: Group<Base = <G2 as Group>::Scalar>,
143 G2: Group<Base = <G1 as Group>::Scalar>,
144 C1: StepCircuit<G1::Scalar> + Clone,
145 C2: StepCircuit<G2::Scalar> + Clone,
146{
147 /// Create a new `RecursiveSNARK`
148 pub fn prove(
149 pp: &PublicParams<G1, G2, C1, C2>,
150 z0_primary: G1::Scalar,
151 z0_secondary: G2::Scalar,
152 num_steps: usize,
153 ) -> Result<Self, NovaError> {
154 // Execute the base case for the primary
155 let mut cs_primary: SatisfyingAssignment<G1> = SatisfyingAssignment::new();
156 let inputs_primary: NIFSVerifierCircuitInputs<G2> = NIFSVerifierCircuitInputs::new(
157 pp.r1cs_shape_secondary.get_digest(),
158 <G1 as Group>::Scalar::zero(),
159 z0_primary,
160 None,
161 None,
162 None,
163 None,
164 );
165 let circuit_primary: NIFSVerifierCircuit<G2, C1> = NIFSVerifierCircuit::new(
166 pp.params_primary.clone(),
167 Some(inputs_primary),
168 pp.c_primary.clone(),
169 pp.ro_consts_circuit_primary.clone(),
170 );
171 let _ = circuit_primary.synthesize(&mut cs_primary);
172 let (u_primary, w_primary) = cs_primary
173 .r1cs_instance_and_witness(&pp.r1cs_shape_primary, &pp.r1cs_gens_primary)
174 .map_err(|_e| NovaError::UnSat)?;
175
176 // Execute the base case for the secondary
177 let mut cs_secondary: SatisfyingAssignment<G2> = SatisfyingAssignment::new();
178 let inputs_secondary: NIFSVerifierCircuitInputs<G1> = NIFSVerifierCircuitInputs::new(
179 pp.r1cs_shape_primary.get_digest(),
180 <G2 as Group>::Scalar::zero(),
181 z0_secondary,
182 None,
183 None,
184 Some(u_primary.clone()),
185 None,
186 );
187 let circuit_secondary: NIFSVerifierCircuit<G1, C2> = NIFSVerifierCircuit::new(
188 pp.params_secondary.clone(),
189 Some(inputs_secondary),
190 pp.c_secondary.clone(),
191 pp.ro_consts_circuit_secondary.clone(),
192 );
193 let _ = circuit_secondary.synthesize(&mut cs_secondary);
194 let (u_secondary, w_secondary) = cs_secondary
195 .r1cs_instance_and_witness(&pp.r1cs_shape_secondary, &pp.r1cs_gens_secondary)
196 .map_err(|_e| NovaError::UnSat)?;
197
198 // execute the remaining steps, alternating between G1 and G2
199 let mut l_w_primary = w_primary;
200 let mut l_u_primary = u_primary;
201 let mut r_W_primary =
202 RelaxedR1CSWitness::from_r1cs_witness(&pp.r1cs_shape_primary, &l_w_primary);
203 let mut r_U_primary = RelaxedR1CSInstance::from_r1cs_instance(
204 &pp.r1cs_gens_primary,
205 &pp.r1cs_shape_primary,
206 &l_u_primary,
207 );
208
209 let mut r_W_secondary = RelaxedR1CSWitness::<G2>::default(&pp.r1cs_shape_secondary);
210 let mut r_U_secondary =
211 RelaxedR1CSInstance::<G2>::default(&pp.r1cs_gens_secondary, &pp.r1cs_shape_secondary);
212 let mut l_w_secondary = w_secondary;
213 let mut l_u_secondary = u_secondary;
214
215 let mut z_next_primary = z0_primary;
216 let mut z_next_secondary = z0_secondary;
217
218 for i in 1..num_steps {
219 // fold the secondary circuit's instance
220 let (nifs_secondary, (r_U_next_secondary, r_W_next_secondary)) = NIFS::prove(
221 &pp.r1cs_gens_secondary,
222 &pp.ro_consts_secondary,
223 &pp.r1cs_shape_secondary,
224 &r_U_secondary,
225 &r_W_secondary,
226 &l_u_secondary,
227 &l_w_secondary,
228 )?;
229
230 z_next_primary = pp.c_primary.compute(&z_next_primary);
231 z_next_secondary = pp.c_secondary.compute(&z_next_secondary);
232
233 let mut cs_primary: SatisfyingAssignment<G1> = SatisfyingAssignment::new();
234 let inputs_primary: NIFSVerifierCircuitInputs<G2> = NIFSVerifierCircuitInputs::new(
235 pp.r1cs_shape_secondary.get_digest(),
236 <G1 as Group>::Scalar::from(i as u64),
237 z0_primary,
238 Some(z_next_primary),
239 Some(r_U_secondary),
240 Some(l_u_secondary),
241 Some(nifs_secondary.comm_T.decompress()?),
242 );
243
244 let circuit_primary: NIFSVerifierCircuit<G2, C1> = NIFSVerifierCircuit::new(
245 pp.params_primary.clone(),
246 Some(inputs_primary),
247 pp.c_primary.clone(),
248 pp.ro_consts_circuit_primary.clone(),
249 );
250 let _ = circuit_primary.synthesize(&mut cs_primary);
251
252 (l_u_primary, l_w_primary) = cs_primary
253 .r1cs_instance_and_witness(&pp.r1cs_shape_primary, &pp.r1cs_gens_primary)
254 .map_err(|_e| NovaError::UnSat)?;
255
256 // fold the primary circuit's instance
257 let (nifs_primary, (r_U_next_primary, r_W_next_primary)) = NIFS::prove(
258 &pp.r1cs_gens_primary,
259 &pp.ro_consts_primary,
260 &pp.r1cs_shape_primary,
261 &r_U_primary.clone(),
262 &r_W_primary.clone(),
263 &l_u_primary.clone(),
264 &l_w_primary.clone(),
265 )?;
266
267 let mut cs_secondary: SatisfyingAssignment<G2> = SatisfyingAssignment::new();
268 let inputs_secondary: NIFSVerifierCircuitInputs<G1> = NIFSVerifierCircuitInputs::new(
269 pp.r1cs_shape_primary.get_digest(),
270 <G2 as Group>::Scalar::from(i as u64),
271 z0_secondary,
272 Some(z_next_secondary),
273 Some(r_U_primary.clone()),
274 Some(l_u_primary.clone()),
275 Some(nifs_primary.comm_T.decompress()?),
276 );
277
278 let circuit_secondary: NIFSVerifierCircuit<G1, C2> = NIFSVerifierCircuit::new(
279 pp.params_secondary.clone(),
280 Some(inputs_secondary),
281 pp.c_secondary.clone(),
282 pp.ro_consts_circuit_secondary.clone(),
283 );
284 let _ = circuit_secondary.synthesize(&mut cs_secondary);
285
286 (l_u_secondary, l_w_secondary) = cs_secondary
287 .r1cs_instance_and_witness(&pp.r1cs_shape_secondary, &pp.r1cs_gens_secondary)
288 .map_err(|_e| NovaError::UnSat)?;
289
290 // update the running instances and witnesses
291 r_U_secondary = r_U_next_secondary;
292 r_W_secondary = r_W_next_secondary;
293 r_U_primary = r_U_next_primary;
294 r_W_primary = r_W_next_primary;
295 }
296
297 Ok(Self {
298 r_W_primary,
299 r_U_primary,
300 l_w_primary,
301 l_u_primary,
302 r_W_secondary,
303 r_U_secondary,
304 l_w_secondary,
305 l_u_secondary,
306 _p_c1: Default::default(),
307 _p_c2: Default::default(),
308 })
309 }
310
311 /// Verify the correctness of the `RecursiveSNARK`
312 pub fn verify(&self, pp: &PublicParams<G1, G2, C1, C2>) -> Result<(), NovaError> {
313 // TODO: perform additional checks on whether (shape_digest, z_0, z_i, i) are correct
314
315 pp.r1cs_shape_primary.is_sat_relaxed(
316 &pp.r1cs_gens_primary,
317 &self.r_U_primary,
318 &self.r_W_primary,
319 )?;
320
321 pp.r1cs_shape_primary
322 .is_sat(&pp.r1cs_gens_primary, &self.l_u_primary, &self.l_w_primary)?;
323
324 pp.r1cs_shape_secondary.is_sat_relaxed(
325 &pp.r1cs_gens_secondary,
326 &self.r_U_secondary,
327 &self.r_W_secondary,
328 )?;
329
330 pp.r1cs_shape_secondary.is_sat(
331 &pp.r1cs_gens_secondary,
332 &self.l_u_secondary,
333 &self.l_w_secondary,
334 )?;
335
336 Ok(())
337 }
338}
339
340#[cfg(test)]
341mod tests {
342 use super::*;
343 type G1 = pasta_curves::pallas::Point;
344 type G2 = pasta_curves::vesta::Point;
345 use ::bellperson::{gadgets::num::AllocatedNum, ConstraintSystem, SynthesisError};
346 use ff::PrimeField;
347 use std::marker::PhantomData;
348
349 #[derive(Clone, Debug)]
350 struct TrivialTestCircuit<F: PrimeField> {
351 _p: PhantomData<F>,
352 }
353
354 impl<F> StepCircuit<F> for TrivialTestCircuit<F>
355 where
356 F: PrimeField,
357 {
358 fn synthesize<CS: ConstraintSystem<F>>(
359 &self,
360 _cs: &mut CS,
361 z: AllocatedNum<F>,
362 ) -> Result<AllocatedNum<F>, SynthesisError> {
363 Ok(z)
364 }
365
366 fn compute(&self, z: &F) -> F {
367 *z
368 }
369 }
370
371 #[derive(Clone, Debug)]
372 struct CubicCircuit<F: PrimeField> {
373 _p: PhantomData<F>,
374 }
375
376 impl<F> StepCircuit<F> for CubicCircuit<F>
377 where
378 F: PrimeField,
379 {
380 fn synthesize<CS: ConstraintSystem<F>>(
381 &self,
382 cs: &mut CS,
383 z: AllocatedNum<F>,
384 ) -> Result<AllocatedNum<F>, SynthesisError> {
385 // Consider a cubic equation: `x^3 + x + 5 = y`, where `x` and `y` are respectively the input and output.
386 let x = z;
387 let x_sq = x.square(cs.namespace(|| "x_sq"))?;
388 let x_cu = x_sq.mul(cs.namespace(|| "x_cu"), &x)?;
389 let y = AllocatedNum::alloc(cs.namespace(|| "y"), || {
390 Ok(x_cu.get_value().unwrap() + x.get_value().unwrap() + F::from(5u64))
391 })?;
392
393 cs.enforce(
394 || "y = x^3 + x + 5",
395 |lc| {
396 lc + x_cu.get_variable()
397 + x.get_variable()
398 + CS::one()
399 + CS::one()
400 + CS::one()
401 + CS::one()
402 + CS::one()
403 },
404 |lc| lc + CS::one(),
405 |lc| lc + y.get_variable(),
406 );
407
408 Ok(y)
409 }
410
411 fn compute(&self, z: &F) -> F {
412 *z * *z * *z + z + F::from(5u64)
413 }
414 }
415
416 #[test]
417 fn test_ivc_trivial() {
418 // produce public parameters
419 let pp = PublicParams::<
420 G1,
421 G2,
422 TrivialTestCircuit<<G1 as Group>::Scalar>,
423 TrivialTestCircuit<<G2 as Group>::Scalar>,
424 >::setup(
425 TrivialTestCircuit {
426 _p: Default::default(),
427 },
428 TrivialTestCircuit {
429 _p: Default::default(),
430 },
431 );
432
433 // produce a recursive SNARK
434 let res = RecursiveSNARK::prove(
435 &pp,
436 <G1 as Group>::Scalar::zero(),
437 <G2 as Group>::Scalar::zero(),
438 3,
439 );
440 assert!(res.is_ok());
441 let recursive_snark = res.unwrap();
442
443 // verify the recursive SNARK
444 let res = recursive_snark.verify(&pp);
445 assert!(res.is_ok());
446 }
447
448 #[test]
449 fn test_ivc() {
450 // produce public parameters
451 let pp = PublicParams::<
452 G1,
453 G2,
454 TrivialTestCircuit<<G1 as Group>::Scalar>,
455 CubicCircuit<<G2 as Group>::Scalar>,
456 >::setup(
457 TrivialTestCircuit {
458 _p: Default::default(),
459 },
460 CubicCircuit {
461 _p: Default::default(),
462 },
463 );
464
465 // produce a recursive SNARK
466 let res = RecursiveSNARK::prove(
467 &pp,
468 <G1 as Group>::Scalar::zero(),
469 <G2 as Group>::Scalar::zero(),
470 3,
471 );
472 assert!(res.is_ok());
473 let recursive_snark = res.unwrap();
474
475 // verify the recursive SNARK
476 let res = recursive_snark.verify(&pp);
477 assert!(res.is_ok());
478 }
479}