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 crate::poseidon::ROConstantsCircuit; // TODO: make this a trait so we can use it without the concrete implementation
24use ::bellperson::{Circuit, ConstraintSystem};
25use circuit::{NIFSVerifierCircuit, NIFSVerifierCircuitInputs, NIFSVerifierCircuitParams};
26use constants::{BN_LIMB_WIDTH, BN_N_LIMBS};
27use core::marker::PhantomData;
28use errors::NovaError;
29use ff::Field;
30use r1cs::{
31 R1CSGens, R1CSInstance, R1CSShape, R1CSWitness, RelaxedR1CSInstance, RelaxedR1CSWitness,
32};
33use traits::{Group, HashFuncConstantsTrait, HashFuncTrait, StepCircuit};
34
35type ROConstants<G> =
36 <<G as Group>::HashFunc as HashFuncTrait<<G as Group>::Base, <G as Group>::Scalar>>::Constants;
37
38/// A type that holds public parameters of Nova
39pub struct PublicParams<G1, G2, C1, C2>
40where
41 G1: Group<Base = <G2 as Group>::Scalar>,
42 G2: Group<Base = <G1 as Group>::Scalar>,
43 C1: StepCircuit<G2::Base> + Clone,
44 C2: StepCircuit<G1::Base> + Clone,
45{
46 _ro_consts_primary: ROConstants<G1>,
47 ro_consts_circuit_primary: ROConstantsCircuit<<G2 as Group>::Base>,
48 r1cs_gens_primary: R1CSGens<G1>,
49 r1cs_shape_primary: R1CSShape<G1>,
50 _ro_consts_secondary: ROConstants<G2>,
51 ro_consts_circuit_secondary: ROConstantsCircuit<<G1 as Group>::Base>,
52 r1cs_gens_secondary: R1CSGens<G2>,
53 r1cs_shape_secondary: R1CSShape<G2>,
54 c_primary: C1,
55 c_secondary: C2,
56 params_primary: NIFSVerifierCircuitParams,
57 params_secondary: NIFSVerifierCircuitParams,
58}
59
60impl<G1, G2, C1, C2> PublicParams<G1, G2, C1, C2>
61where
62 G1: Group<Base = <G2 as Group>::Scalar>,
63 G2: Group<Base = <G1 as Group>::Scalar>,
64 C1: StepCircuit<G2::Base> + Clone,
65 C2: StepCircuit<G1::Base> + Clone,
66{
67 /// Create a new `PublicParams`
68 pub fn setup(c_primary: C1, c_secondary: C2) -> Self {
69 let params_primary = NIFSVerifierCircuitParams::new(BN_LIMB_WIDTH, BN_N_LIMBS, true);
70 let params_secondary = NIFSVerifierCircuitParams::new(BN_LIMB_WIDTH, BN_N_LIMBS, false);
71
72 let _ro_consts_primary: ROConstants<G1> = ROConstants::<G1>::new();
73 let _ro_consts_secondary: ROConstants<G2> = ROConstants::<G2>::new();
74
75 let ro_consts_circuit_primary: ROConstantsCircuit<<G2 as Group>::Base> =
76 ROConstantsCircuit::new();
77 let ro_consts_circuit_secondary: ROConstantsCircuit<<G1 as Group>::Base> =
78 ROConstantsCircuit::new();
79
80 // Initialize gens for the primary
81 let circuit_primary: NIFSVerifierCircuit<G2, C1> = NIFSVerifierCircuit::new(
82 params_primary.clone(),
83 None,
84 c_primary.clone(),
85 ro_consts_circuit_primary.clone(),
86 );
87 let mut cs: ShapeCS<G1> = ShapeCS::new();
88 let _ = circuit_primary.synthesize(&mut cs);
89 let (r1cs_shape_primary, r1cs_gens_primary) = (cs.r1cs_shape(), cs.r1cs_gens());
90
91 // Initialize gens for the secondary
92 let circuit_secondary: NIFSVerifierCircuit<G1, C2> = NIFSVerifierCircuit::new(
93 params_secondary.clone(),
94 None,
95 c_secondary.clone(),
96 ro_consts_circuit_secondary.clone(),
97 );
98 let mut cs: ShapeCS<G2> = ShapeCS::new();
99 let _ = circuit_secondary.synthesize(&mut cs);
100 let (r1cs_shape_secondary, r1cs_gens_secondary) = (cs.r1cs_shape(), cs.r1cs_gens());
101
102 Self {
103 _ro_consts_primary,
104 ro_consts_circuit_primary,
105 r1cs_gens_primary,
106 r1cs_shape_primary,
107 _ro_consts_secondary,
108 ro_consts_circuit_secondary,
109 r1cs_gens_secondary,
110 r1cs_shape_secondary,
111 c_primary,
112 c_secondary,
113 params_primary,
114 params_secondary,
115 }
116 }
117}
118
119/// A SNARK that proves the correct execution of an incremental computation
120pub struct RecursiveSNARK<G1, G2, C1, C2>
121where
122 G1: Group<Base = <G2 as Group>::Scalar>,
123 G2: Group<Base = <G1 as Group>::Scalar>,
124 C1: StepCircuit<G2::Base> + Clone,
125 C2: StepCircuit<G1::Base> + Clone,
126{
127 r_W_primary: RelaxedR1CSWitness<G1>,
128 r_U_primary: RelaxedR1CSInstance<G1>,
129 l_w_primary: R1CSWitness<G1>,
130 l_u_primary: R1CSInstance<G1>,
131 r_W_secondary: RelaxedR1CSWitness<G2>,
132 r_U_secondary: RelaxedR1CSInstance<G2>,
133 l_w_secondary: R1CSWitness<G2>,
134 l_u_secondary: R1CSInstance<G2>,
135 _p_c1: PhantomData<C1>,
136 _p_c2: PhantomData<C2>,
137}
138
139impl<G1, G2, C1, C2> RecursiveSNARK<G1, G2, C1, C2>
140where
141 G1: Group<Base = <G2 as Group>::Scalar>,
142 G2: Group<Base = <G1 as Group>::Scalar>,
143 C1: StepCircuit<G2::Base> + Clone,
144 C2: StepCircuit<G1::Base> + Clone,
145{
146 /// Create a new `RecursiveSNARK`
147 pub fn prove(
148 pp: &PublicParams<G1, G2, C1, C2>,
149 z0_primary: G1::Scalar,
150 z0_secondary: G2::Scalar,
151 ) -> Result<Self, NovaError> {
152 // Execute the base case for the primary
153 let mut cs_primary: SatisfyingAssignment<G1> = SatisfyingAssignment::new();
154 let inputs_primary: NIFSVerifierCircuitInputs<G2> = NIFSVerifierCircuitInputs::new(
155 pp.r1cs_shape_secondary.get_digest(),
156 <G2 as Group>::Base::zero(),
157 z0_primary,
158 None,
159 None,
160 None,
161 None,
162 );
163 let circuit_primary: NIFSVerifierCircuit<G2, C1> = NIFSVerifierCircuit::new(
164 pp.params_primary.clone(),
165 Some(inputs_primary),
166 pp.c_primary.clone(),
167 pp.ro_consts_circuit_primary.clone(),
168 );
169 let _ = circuit_primary.synthesize(&mut cs_primary);
170 let (u_primary, w_primary) = cs_primary
171 .r1cs_instance_and_witness(&pp.r1cs_shape_primary, &pp.r1cs_gens_primary)
172 .map_err(|_e| NovaError::UnSat)?;
173
174 // check if the base case is satisfied
175 pp.r1cs_shape_primary
176 .is_sat(&pp.r1cs_gens_primary, &u_primary, &w_primary)
177 .map_err(|_e| NovaError::UnSat)?;
178
179 // Execute the base case for the secondary
180 let mut cs_secondary: SatisfyingAssignment<G2> = SatisfyingAssignment::new();
181 let inputs_secondary: NIFSVerifierCircuitInputs<G1> = NIFSVerifierCircuitInputs::new(
182 pp.r1cs_shape_primary.get_digest(),
183 <G1 as Group>::Base::zero(),
184 z0_secondary,
185 None,
186 None,
187 Some(u_primary.clone()),
188 None,
189 );
190 let circuit_secondary: NIFSVerifierCircuit<G1, C2> = NIFSVerifierCircuit::new(
191 pp.params_secondary.clone(),
192 Some(inputs_secondary),
193 pp.c_secondary.clone(),
194 pp.ro_consts_circuit_secondary.clone(),
195 );
196 let _ = circuit_secondary.synthesize(&mut cs_secondary);
197 let (u_secondary, w_secondary) = cs_secondary
198 .r1cs_instance_and_witness(&pp.r1cs_shape_secondary, &pp.r1cs_gens_secondary)
199 .map_err(|_e| NovaError::UnSat)?;
200
201 // check if the base case is satisfied
202 pp.r1cs_shape_secondary
203 .is_sat(&pp.r1cs_gens_secondary, &u_secondary, &w_secondary)
204 .map_err(|_e| NovaError::UnSat)?;
205
206 Ok(Self {
207 r_W_primary: RelaxedR1CSWitness::<G1>::default(&pp.r1cs_shape_primary),
208 r_U_primary: RelaxedR1CSInstance::<G1>::default(
209 &pp.r1cs_gens_primary,
210 &pp.r1cs_shape_primary,
211 ),
212 l_w_primary: w_primary,
213 l_u_primary: u_primary,
214 r_W_secondary: RelaxedR1CSWitness::<G2>::default(&pp.r1cs_shape_secondary),
215 r_U_secondary: RelaxedR1CSInstance::<G2>::default(
216 &pp.r1cs_gens_secondary,
217 &pp.r1cs_shape_secondary,
218 ),
219 l_w_secondary: w_secondary,
220 l_u_secondary: u_secondary,
221 _p_c1: Default::default(),
222 _p_c2: Default::default(),
223 })
224 }
225
226 /// Verify the correctness of the `RecursiveSNARK`
227 pub fn verify(&self, pp: &PublicParams<G1, G2, C1, C2>) -> Result<(), NovaError> {
228 pp.r1cs_shape_primary.is_sat_relaxed(
229 &pp.r1cs_gens_primary,
230 &self.r_U_primary,
231 &self.r_W_primary,
232 )?;
233 pp.r1cs_shape_primary
234 .is_sat(&pp.r1cs_gens_primary, &self.l_u_primary, &self.l_w_primary)?;
235 pp.r1cs_shape_secondary.is_sat_relaxed(
236 &pp.r1cs_gens_secondary,
237 &self.r_U_secondary,
238 &self.r_W_secondary,
239 )?;
240 pp.r1cs_shape_secondary.is_sat(
241 &pp.r1cs_gens_secondary,
242 &self.l_u_secondary,
243 &self.l_w_secondary,
244 )?;
245
246 Ok(())
247 }
248}
249
250/// A SNARK that proves the knowledge of a valid `RecursiveSNARK`
251pub struct CompressedSNARKTrivial<G: Group> {
252 W: RelaxedR1CSWitness<G>,
253}
254
255impl<G: Group> CompressedSNARKTrivial<G> {
256 /// Produces a proof of a instance given its satisfying witness `W`.
257 pub fn prove(W: &RelaxedR1CSWitness<G>) -> Result<CompressedSNARKTrivial<G>, NovaError> {
258 Ok(Self { W: W.clone() })
259 }
260
261 /// Verifies the proof of a folded instance `U` given its shape `S` public parameters `gens`
262 pub fn verify(
263 &self,
264 gens: &R1CSGens<G>,
265 S: &R1CSShape<G>,
266 U: &RelaxedR1CSInstance<G>,
267 ) -> Result<(), NovaError> {
268 // check that the witness is a valid witness to the folded instance `U`
269 S.is_sat_relaxed(gens, U, &self.W)
270 }
271}
272
273#[cfg(test)]
274mod tests {
275 use super::*;
276 type G1 = pasta_curves::pallas::Point;
277 type G2 = pasta_curves::vesta::Point;
278 use ::bellperson::{gadgets::num::AllocatedNum, ConstraintSystem, SynthesisError};
279 use ff::PrimeField;
280 use std::marker::PhantomData;
281
282 #[derive(Clone, Debug)]
283 struct TestCircuit<F: PrimeField> {
284 _p: PhantomData<F>,
285 }
286
287 impl<F> StepCircuit<F> for TestCircuit<F>
288 where
289 F: PrimeField,
290 {
291 fn synthesize<CS: ConstraintSystem<F>>(
292 &self,
293 _cs: &mut CS,
294 z: AllocatedNum<F>,
295 ) -> Result<AllocatedNum<F>, SynthesisError> {
296 Ok(z)
297 }
298 }
299
300 #[test]
301 fn test_base_case() {
302 // produce public parameters
303 let pp = PublicParams::<
304 G1,
305 G2,
306 TestCircuit<<G2 as Group>::Base>,
307 TestCircuit<<G1 as Group>::Base>,
308 >::setup(
309 TestCircuit {
310 _p: Default::default(),
311 },
312 TestCircuit {
313 _p: Default::default(),
314 },
315 );
316
317 // produce a recursive SNARK
318 let res = RecursiveSNARK::prove(
319 &pp,
320 <G2 as Group>::Base::zero(),
321 <G1 as Group>::Base::zero(),
322 );
323 assert!(res.is_ok());
324 let recursive_snark = res.unwrap();
325
326 // verify the recursive SNARK
327 let res = recursive_snark.verify(&pp);
328 assert!(res.is_ok());
329 }
330}