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#[cfg(test)]
251mod tests {
252 use super::*;
253 type G1 = pasta_curves::pallas::Point;
254 type G2 = pasta_curves::vesta::Point;
255 use ::bellperson::{gadgets::num::AllocatedNum, ConstraintSystem, SynthesisError};
256 use ff::PrimeField;
257 use std::marker::PhantomData;
258
259 #[derive(Clone, Debug)]
260 struct TestCircuit<F: PrimeField> {
261 _p: PhantomData<F>,
262 }
263
264 impl<F> StepCircuit<F> for TestCircuit<F>
265 where
266 F: PrimeField,
267 {
268 fn synthesize<CS: ConstraintSystem<F>>(
269 &self,
270 _cs: &mut CS,
271 z: AllocatedNum<F>,
272 ) -> Result<AllocatedNum<F>, SynthesisError> {
273 Ok(z)
274 }
275 }
276
277 #[test]
278 fn test_base_case() {
279 // produce public parameters
280 let pp = PublicParams::<
281 G1,
282 G2,
283 TestCircuit<<G2 as Group>::Base>,
284 TestCircuit<<G1 as Group>::Base>,
285 >::setup(
286 TestCircuit {
287 _p: Default::default(),
288 },
289 TestCircuit {
290 _p: Default::default(),
291 },
292 );
293
294 // produce a recursive SNARK
295 let res = RecursiveSNARK::prove(
296 &pp,
297 <G2 as Group>::Base::zero(),
298 <G1 as Group>::Base::zero(),
299 );
300 assert!(res.is_ok());
301 let recursive_snark = res.unwrap();
302
303 // verify the recursive SNARK
304 let res = recursive_snark.verify(&pp);
305 assert!(res.is_ok());
306 }
307}