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<G2::Base> + Clone,
45 C2: StepCircuit<G1::Base> + 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<G2::Base> + Clone,
66 C2: StepCircuit<G1::Base> + 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<G2::Base> + Clone,
126 C2: StepCircuit<G1::Base> + 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<G2::Base> + Clone,
145 C2: StepCircuit<G1::Base> + 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 <G2 as Group>::Base::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 <G1 as Group>::Base::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 // TODO: execute the provided step circuit(s) to feed real z_i into the verifier circuit
219 for i in 1..num_steps {
220 // fold the secondary circuit's instance into r_W_primary
221 let (nifs_secondary, (r_U_next_secondary, r_W_next_secondary)) = NIFS::prove(
222 &pp.r1cs_gens_secondary,
223 &pp._ro_consts_secondary,
224 &pp.r1cs_shape_secondary,
225 &r_U_secondary,
226 &r_W_secondary,
227 &l_u_secondary,
228 &l_w_secondary,
229 )?;
230
231 z_next_primary = pp.c_primary.compute(&z_next_primary);
232 z_next_secondary = pp.c_secondary.compute(&z_next_secondary);
233
234 let mut cs_primary: SatisfyingAssignment<G1> = SatisfyingAssignment::new();
235 let inputs_primary: NIFSVerifierCircuitInputs<G2> = NIFSVerifierCircuitInputs::new(
236 pp.r1cs_shape_secondary.get_digest(),
237 <G2 as Group>::Base::from(i as u64),
238 z0_primary,
239 Some(z_next_primary),
240 Some(r_U_secondary),
241 Some(l_u_secondary),
242 Some(nifs_secondary.comm_T.decompress()?),
243 );
244
245 let circuit_primary: NIFSVerifierCircuit<G2, C1> = NIFSVerifierCircuit::new(
246 pp.params_primary.clone(),
247 Some(inputs_primary),
248 pp.c_primary.clone(),
249 pp.ro_consts_circuit_primary.clone(),
250 );
251 let _ = circuit_primary.synthesize(&mut cs_primary);
252
253 (l_u_primary, l_w_primary) = cs_primary
254 .r1cs_instance_and_witness(&pp.r1cs_shape_primary, &pp.r1cs_gens_primary)
255 .map_err(|_e| NovaError::UnSat)?;
256
257 // fold the secondary circuit's instance into r_W_primary
258 let (nifs_primary, (r_U_next_primary, r_W_next_primary)) = NIFS::prove(
259 &pp.r1cs_gens_primary,
260 &pp._ro_consts_primary,
261 &pp.r1cs_shape_primary,
262 &r_U_primary.clone(),
263 &r_W_primary.clone(),
264 &l_u_primary.clone(),
265 &l_w_primary.clone(),
266 )?;
267
268 let mut cs_secondary: SatisfyingAssignment<G2> = SatisfyingAssignment::new();
269 let inputs_secondary: NIFSVerifierCircuitInputs<G1> = NIFSVerifierCircuitInputs::new(
270 pp.r1cs_shape_primary.get_digest(),
271 <G1 as Group>::Base::from(i as u64),
272 z0_secondary,
273 Some(z_next_secondary),
274 Some(r_U_primary.clone()),
275 Some(l_u_primary.clone()),
276 Some(nifs_primary.comm_T.decompress()?),
277 );
278
279 let circuit_secondary: NIFSVerifierCircuit<G1, C2> = NIFSVerifierCircuit::new(
280 pp.params_secondary.clone(),
281 Some(inputs_secondary),
282 pp.c_secondary.clone(),
283 pp.ro_consts_circuit_secondary.clone(),
284 );
285 let _ = circuit_secondary.synthesize(&mut cs_secondary);
286
287 (l_u_secondary, l_w_secondary) = cs_secondary
288 .r1cs_instance_and_witness(&pp.r1cs_shape_secondary, &pp.r1cs_gens_secondary)
289 .map_err(|_e| NovaError::UnSat)?;
290
291 // update the running instances and witnesses
292 r_U_secondary = r_U_next_secondary;
293 r_W_secondary = r_W_next_secondary;
294 r_U_primary = r_U_next_primary;
295 r_W_primary = r_W_next_primary;
296 }
297
298 Ok(Self {
299 r_W_primary,
300 r_U_primary,
301 l_w_primary,
302 l_u_primary,
303 r_W_secondary,
304 r_U_secondary,
305 l_w_secondary,
306 l_u_secondary,
307 _p_c1: Default::default(),
308 _p_c2: Default::default(),
309 })
310 }
311
312 /// Verify the correctness of the `RecursiveSNARK`
313 pub fn verify(&self, pp: &PublicParams<G1, G2, C1, C2>) -> Result<(), NovaError> {
314 // TODO: perform additional checks on whether (shape_digest, z_0, z_i, i) are correct
315
316 pp.r1cs_shape_primary.is_sat_relaxed(
317 &pp.r1cs_gens_primary,
318 &self.r_U_primary,
319 &self.r_W_primary,
320 )?;
321
322 pp.r1cs_shape_primary
323 .is_sat(&pp.r1cs_gens_primary, &self.l_u_primary, &self.l_w_primary)?;
324
325 pp.r1cs_shape_secondary.is_sat_relaxed(
326 &pp.r1cs_gens_secondary,
327 &self.r_U_secondary,
328 &self.r_W_secondary,
329 )?;
330
331 pp.r1cs_shape_secondary.is_sat(
332 &pp.r1cs_gens_secondary,
333 &self.l_u_secondary,
334 &self.l_w_secondary,
335 )?;
336
337 Ok(())
338 }
339}
340
341#[cfg(test)]
342mod tests {
343 use super::*;
344 type G1 = pasta_curves::pallas::Point;
345 type G2 = pasta_curves::vesta::Point;
346 use ::bellperson::{gadgets::num::AllocatedNum, ConstraintSystem, SynthesisError};
347 use ff::PrimeField;
348 use std::marker::PhantomData;
349
350 #[derive(Clone, Debug)]
351 struct TrivialTestCircuit<F: PrimeField> {
352 _p: PhantomData<F>,
353 }
354
355 impl<F> StepCircuit<F> for TrivialTestCircuit<F>
356 where
357 F: PrimeField,
358 {
359 fn synthesize<CS: ConstraintSystem<F>>(
360 &self,
361 _cs: &mut CS,
362 z: AllocatedNum<F>,
363 ) -> Result<AllocatedNum<F>, SynthesisError> {
364 Ok(z)
365 }
366
367 fn compute(&self, z: &F) -> F {
368 *z
369 }
370 }
371
372 #[derive(Clone, Debug)]
373 struct CubicCircuit<F: PrimeField> {
374 _p: PhantomData<F>,
375 }
376
377 impl<F> StepCircuit<F> for CubicCircuit<F>
378 where
379 F: PrimeField,
380 {
381 fn synthesize<CS: ConstraintSystem<F>>(
382 &self,
383 cs: &mut CS,
384 z: AllocatedNum<F>,
385 ) -> Result<AllocatedNum<F>, SynthesisError> {
386 // Consider a cubic equation: `x^3 + x + 5 = y`, where `x` and `y` are respectively the input and output.
387 let x = z;
388 let x_sq = x.square(cs.namespace(|| "x_sq"))?;
389 let x_cu = x_sq.mul(cs.namespace(|| "x_cu"), &x)?;
390 let y = AllocatedNum::alloc(cs.namespace(|| "y"), || {
391 Ok(x_cu.get_value().unwrap() + x.get_value().unwrap() + F::from(5u64))
392 })?;
393
394 cs.enforce(
395 || "y = x^3 + x + 5",
396 |lc| {
397 lc + x_cu.get_variable()
398 + x.get_variable()
399 + CS::one()
400 + CS::one()
401 + CS::one()
402 + CS::one()
403 + CS::one()
404 },
405 |lc| lc + CS::one(),
406 |lc| lc + y.get_variable(),
407 );
408
409 Ok(y)
410 }
411
412 fn compute(&self, z: &F) -> F {
413 *z * *z * *z + z + F::from(5u64)
414 }
415 }
416
417 #[test]
418 fn test_ivc_trivial() {
419 // produce public parameters
420 let pp = PublicParams::<
421 G1,
422 G2,
423 TrivialTestCircuit<<G2 as Group>::Base>,
424 TrivialTestCircuit<<G1 as Group>::Base>,
425 >::setup(
426 TrivialTestCircuit {
427 _p: Default::default(),
428 },
429 TrivialTestCircuit {
430 _p: Default::default(),
431 },
432 );
433
434 // produce a recursive SNARK
435 let res = RecursiveSNARK::prove(
436 &pp,
437 <G2 as Group>::Base::zero(),
438 <G1 as Group>::Base::zero(),
439 3,
440 );
441 assert!(res.is_ok());
442 let recursive_snark = res.unwrap();
443
444 // verify the recursive SNARK
445 let res = recursive_snark.verify(&pp);
446 assert!(res.is_ok());
447 }
448
449 #[test]
450 fn test_ivc() {
451 // produce public parameters
452 let pp = PublicParams::<
453 G1,
454 G2,
455 TrivialTestCircuit<<G2 as Group>::Base>,
456 CubicCircuit<<G1 as Group>::Base>,
457 >::setup(
458 TrivialTestCircuit {
459 _p: Default::default(),
460 },
461 CubicCircuit {
462 _p: Default::default(),
463 },
464 );
465
466 // produce a recursive SNARK
467 let res = RecursiveSNARK::prove(
468 &pp,
469 <G2 as Group>::Base::zero(),
470 <G1 as Group>::Base::zero(),
471 3,
472 );
473 assert!(res.is_ok());
474 let recursive_snark = res.unwrap();
475
476 // verify the recursive SNARK
477 let res = recursive_snark.verify(&pp);
478 assert!(res.is_ok());
479 }
480}