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 pasta;
13mod poseidon;
14pub mod r1cs;
15pub mod traits;
16
17use commitments::CompressedCommitment;
18use errors::NovaError;
19use r1cs::{
20 R1CSGens, R1CSInstance, R1CSShape, R1CSWitness, RelaxedR1CSInstance, RelaxedR1CSWitness,
21};
22use std::marker::PhantomData;
23use traits::{AbsorbInROTrait, Group, HashFuncTrait};
24
25/// A SNARK that holds the proof of a step of an incremental computation
26pub struct StepSNARK<G: Group> {
27 comm_T: CompressedCommitment<G::CompressedGroupElement>,
28 _p: PhantomData<G>,
29}
30
31type ROConstants<G> =
32 <<G as Group>::HashFunc as HashFuncTrait<<G as Group>::Base, <G as Group>::Scalar>>::Constants;
33
34impl<G: Group> StepSNARK<G> {
35 /// Takes as input a Relaxed R1CS instance-witness tuple `(U1, W1)` and
36 /// an R1CS instance-witness tuple `(U2, W2)` with the same structure `shape`
37 /// and defined with respect to the same `gens`, and outputs
38 /// a folded Relaxed R1CS instance-witness tuple `(U, W)` of the same shape `shape`,
39 /// with the guarantee that the folded witness `W` satisfies the folded instance `U`
40 /// if and only if `W1` satisfies `U1` and `W2` satisfies `U2`.
41 pub fn prove(
42 gens: &R1CSGens<G>,
43 ro_consts: &ROConstants<G>,
44 S: &R1CSShape<G>,
45 U1: &RelaxedR1CSInstance<G>,
46 W1: &RelaxedR1CSWitness<G>,
47 U2: &R1CSInstance<G>,
48 W2: &R1CSWitness<G>,
49 ) -> Result<
50 (
51 StepSNARK<G>,
52 (RelaxedR1CSInstance<G>, RelaxedR1CSWitness<G>),
53 ),
54 NovaError,
55 > {
56 // initialize a new RO
57 let mut ro = G::HashFunc::new(ro_consts.clone());
58
59 // append S to the transcript
60 S.absorb_in_ro(&mut ro);
61
62 // append U1 and U2 to transcript
63 U1.absorb_in_ro(&mut ro);
64 U2.absorb_in_ro(&mut ro);
65
66 // compute a commitment to the cross-term
67 let (T, comm_T) = S.commit_T(gens, U1, W1, U2, W2)?;
68
69 // append `comm_T` to the transcript and obtain a challenge
70 comm_T.absorb_in_ro(&mut ro);
71
72 // compute a challenge from the RO
73 let r = ro.get_challenge();
74
75 // fold the instance using `r` and `comm_T`
76 let U = U1.fold(U2, &comm_T, &r)?;
77
78 // fold the witness using `r` and `T`
79 let W = W1.fold(W2, &T, &r)?;
80
81 // return the folded instance and witness
82 Ok((
83 StepSNARK {
84 comm_T: comm_T.compress(),
85 _p: Default::default(),
86 },
87 (U, W),
88 ))
89 }
90
91 /// Takes as input a relaxed R1CS instance `U1` and and R1CS instance `U2`
92 /// with the same shape and defined with respect to the same parameters,
93 /// and outputs a folded instance `U` with the same shape,
94 /// with the guarantee that the folded instance `U`
95 /// if and only if `U1` and `U2` are satisfiable.
96 pub fn verify(
97 &self,
98 ro_consts: &ROConstants<G>,
99 S: &R1CSShape<G>,
100 U1: &RelaxedR1CSInstance<G>,
101 U2: &R1CSInstance<G>,
102 ) -> Result<RelaxedR1CSInstance<G>, NovaError> {
103 // initialize a new RO
104 let mut ro = G::HashFunc::new(ro_consts.clone());
105
106 // append S to the transcript
107 S.absorb_in_ro(&mut ro);
108
109 // append U1 and U2 to transcript
110 U1.absorb_in_ro(&mut ro);
111 U2.absorb_in_ro(&mut ro);
112
113 // append `comm_T` to the transcript and obtain a challenge
114 let comm_T = self.comm_T.decompress()?;
115 comm_T.absorb_in_ro(&mut ro);
116
117 // compute a challenge from the RO
118 let r = ro.get_challenge();
119
120 // fold the instance using `r` and `comm_T`
121 let U = U1.fold(U2, &comm_T, &r)?;
122
123 // return the folded instance
124 Ok(U)
125 }
126}
127
128/// A SNARK that holds the proof of the final step of an incremental computation
129pub struct FinalSNARK<G: Group> {
130 W: RelaxedR1CSWitness<G>,
131}
132
133impl<G: Group> FinalSNARK<G> {
134 /// Produces a proof of a instance given its satisfying witness `W`.
135 pub fn prove(W: &RelaxedR1CSWitness<G>) -> Result<FinalSNARK<G>, NovaError> {
136 Ok(FinalSNARK { W: W.clone() })
137 }
138
139 /// Verifies the proof of a folded instance `U` given its shape `S` public parameters `gens`
140 pub fn verify(
141 &self,
142 gens: &R1CSGens<G>,
143 S: &R1CSShape<G>,
144 U: &RelaxedR1CSInstance<G>,
145 ) -> Result<(), NovaError> {
146 // check that the witness is a valid witness to the folded instance `U`
147 S.is_sat_relaxed(gens, U, &self.W)
148 }
149}
150
151#[cfg(test)]
152mod tests {
153 use super::*;
154 use crate::traits::HashFuncConstantsTrait;
155 use ::bellperson::{gadgets::num::AllocatedNum, ConstraintSystem, SynthesisError};
156 use ff::{Field, PrimeField};
157 use rand::rngs::OsRng;
158
159 type S = pasta_curves::pallas::Scalar;
160 type G = pasta_curves::pallas::Point;
161
162 fn synthesize_tiny_r1cs_bellperson<Scalar: PrimeField, CS: ConstraintSystem<Scalar>>(
163 cs: &mut CS,
164 x_val: Option<Scalar>,
165 ) -> Result<(), SynthesisError> {
166 // Consider a cubic equation: `x^3 + x + 5 = y`, where `x` and `y` are respectively the input and output.
167 let x = AllocatedNum::alloc(cs.namespace(|| "x"), || Ok(x_val.unwrap()))?;
168 let _ = x.inputize(cs.namespace(|| "x is input"));
169
170 let x_sq = x.square(cs.namespace(|| "x_sq"))?;
171 let x_cu = x_sq.mul(cs.namespace(|| "x_cu"), &x)?;
172 let y = AllocatedNum::alloc(cs.namespace(|| "y"), || {
173 Ok(x_cu.get_value().unwrap() + x.get_value().unwrap() + Scalar::from(5u64))
174 })?;
175 let _ = y.inputize(cs.namespace(|| "y is output"));
176
177 cs.enforce(
178 || "y = x^3 + x + 5",
179 |lc| {
180 lc + x_cu.get_variable()
181 + x.get_variable()
182 + CS::one()
183 + CS::one()
184 + CS::one()
185 + CS::one()
186 + CS::one()
187 },
188 |lc| lc + CS::one(),
189 |lc| lc + y.get_variable(),
190 );
191
192 Ok(())
193 }
194
195 #[test]
196 fn test_tiny_r1cs_bellperson() {
197 use super::bellperson::{
198 r1cs::{NovaShape, NovaWitness},
199 shape_cs::ShapeCS,
200 solver::SatisfyingAssignment,
201 };
202
203 // First create the shape
204 let mut cs: ShapeCS<G> = ShapeCS::new();
205 let _ = synthesize_tiny_r1cs_bellperson(&mut cs, None);
206 let shape = cs.r1cs_shape();
207 let gens = cs.r1cs_gens();
208 let ro_consts = <<G as Group>::HashFunc as HashFuncTrait<
209 <G as Group>::Base,
210 <G as Group>::Scalar,
211 >>::Constants::new();
212
213 // Now get the instance and assignment for one instance
214 let mut cs: SatisfyingAssignment<G> = SatisfyingAssignment::new();
215 let _ = synthesize_tiny_r1cs_bellperson(&mut cs, Some(S::from(5)));
216 let (U1, W1) = cs.r1cs_instance_and_witness(&shape, &gens).unwrap();
217
218 // Make sure that the first instance is satisfiable
219 assert!(shape.is_sat(&gens, &U1, &W1).is_ok());
220
221 // Now get the instance and assignment for second instance
222 let mut cs: SatisfyingAssignment<G> = SatisfyingAssignment::new();
223 let _ = synthesize_tiny_r1cs_bellperson(&mut cs, Some(S::from(135)));
224 let (U2, W2) = cs.r1cs_instance_and_witness(&shape, &gens).unwrap();
225
226 // Make sure that the second instance is satisfiable
227 assert!(shape.is_sat(&gens, &U2, &W2).is_ok());
228
229 // execute a sequence of folds
230 execute_sequence(&gens, &ro_consts, &shape, &U1, &W1, &U2, &W2);
231 }
232
233 fn execute_sequence(
234 gens: &R1CSGens<G>,
235 ro_consts: &<<G as traits::Group>::HashFunc as HashFuncTrait<
236 <G as traits::Group>::Base,
237 <G as traits::Group>::Scalar,
238 >>::Constants,
239 shape: &R1CSShape<G>,
240 U1: &R1CSInstance<G>,
241 W1: &R1CSWitness<G>,
242 U2: &R1CSInstance<G>,
243 W2: &R1CSWitness<G>,
244 ) {
245 // produce a default running instance
246 let mut r_W = RelaxedR1CSWitness::default(shape);
247 let mut r_U = RelaxedR1CSInstance::default(gens, shape);
248
249 // produce a step SNARK with (W1, U1) as the first incoming witness-instance pair
250 let res = StepSNARK::prove(gens, ro_consts, shape, &r_U, &r_W, U1, W1);
251 assert!(res.is_ok());
252 let (step_snark, (_U, W)) = res.unwrap();
253
254 // verify the step SNARK with U1 as the first incoming instance
255 let res = step_snark.verify(ro_consts, shape, &r_U, U1);
256 assert!(res.is_ok());
257 let U = res.unwrap();
258
259 assert_eq!(U, _U);
260
261 // update the running witness and instance
262 r_W = W;
263 r_U = U;
264
265 // produce a step SNARK with (W2, U2) as the second incoming witness-instance pair
266 let res = StepSNARK::prove(gens, ro_consts, shape, &r_U, &r_W, U2, W2);
267 assert!(res.is_ok());
268 let (step_snark, (_U, W)) = res.unwrap();
269
270 // verify the step SNARK with U1 as the first incoming instance
271 let res = step_snark.verify(ro_consts, shape, &r_U, U2);
272 assert!(res.is_ok());
273 let U = res.unwrap();
274
275 assert_eq!(U, _U);
276
277 // update the running witness and instance
278 r_W = W;
279 r_U = U;
280
281 // produce a final SNARK
282 let res = FinalSNARK::prove(&r_W);
283 assert!(res.is_ok());
284 let final_snark = res.unwrap();
285 // verify the final SNARK
286 let res = final_snark.verify(gens, shape, &r_U);
287 assert!(res.is_ok());
288 }
289
290 #[test]
291 fn test_tiny_r1cs() {
292 let one = S::one();
293 let (num_cons, num_vars, num_io, A, B, C) = {
294 let num_cons = 4;
295 let num_vars = 4;
296 let num_io = 2;
297
298 // Consider a cubic equation: `x^3 + x + 5 = y`, where `x` and `y` are respectively the input and output.
299 // The R1CS for this problem consists of the following constraints:
300 // `I0 * I0 - Z0 = 0`
301 // `Z0 * I0 - Z1 = 0`
302 // `(Z1 + I0) * 1 - Z2 = 0`
303 // `(Z2 + 5) * 1 - I1 = 0`
304
305 // Relaxed R1CS is a set of three sparse matrices (A B C), where there is a row for every
306 // constraint and a column for every entry in z = (vars, u, inputs)
307 // An R1CS instance is satisfiable iff:
308 // Az \circ Bz = u \cdot Cz + E, where z = (vars, 1, inputs)
309 let mut A: Vec<(usize, usize, S)> = Vec::new();
310 let mut B: Vec<(usize, usize, S)> = Vec::new();
311 let mut C: Vec<(usize, usize, S)> = Vec::new();
312
313 // constraint 0 entries in (A,B,C)
314 // `I0 * I0 - Z0 = 0`
315 A.push((0, num_vars + 1, one));
316 B.push((0, num_vars + 1, one));
317 C.push((0, 0, one));
318
319 // constraint 1 entries in (A,B,C)
320 // `Z0 * I0 - Z1 = 0`
321 A.push((1, 0, one));
322 B.push((1, num_vars + 1, one));
323 C.push((1, 1, one));
324
325 // constraint 2 entries in (A,B,C)
326 // `(Z1 + I0) * 1 - Z2 = 0`
327 A.push((2, 1, one));
328 A.push((2, num_vars + 1, one));
329 B.push((2, num_vars, one));
330 C.push((2, 2, one));
331
332 // constraint 3 entries in (A,B,C)
333 // `(Z2 + 5) * 1 - I1 = 0`
334 A.push((3, 2, one));
335 A.push((3, num_vars, one + one + one + one + one));
336 B.push((3, num_vars, one));
337 C.push((3, num_vars + 2, one));
338
339 (num_cons, num_vars, num_io, A, B, C)
340 };
341
342 // create a shape object
343 let S = {
344 let res = R1CSShape::new(num_cons, num_vars, num_io, &A, &B, &C);
345 assert!(res.is_ok());
346 res.unwrap()
347 };
348
349 // generate generators and ro constants
350 let gens = R1CSGens::new(num_cons, num_vars);
351 let ro_consts = <<G as Group>::HashFunc as HashFuncTrait<
352 <G as Group>::Base,
353 <G as Group>::Scalar,
354 >>::Constants::new();
355
356 let rand_inst_witness_generator =
357 |gens: &R1CSGens<G>, I: &S| -> (S, R1CSInstance<G>, R1CSWitness<G>) {
358 let i0 = *I;
359
360 // compute a satisfying (vars, X) tuple
361 let (O, vars, X) = {
362 let z0 = i0 * i0; // constraint 0
363 let z1 = i0 * z0; // constraint 1
364 let z2 = z1 + i0; // constraint 2
365 let i1 = z2 + one + one + one + one + one; // constraint 3
366
367 // store the witness and IO for the instance
368 let W = vec![z0, z1, z2, S::zero()];
369 let X = vec![i0, i1];
370 (i1, W, X)
371 };
372
373 let W = {
374 let res = R1CSWitness::new(&S, &vars);
375 assert!(res.is_ok());
376 res.unwrap()
377 };
378 let U = {
379 let comm_W = W.commit(gens);
380 let res = R1CSInstance::new(&S, &comm_W, &X);
381 assert!(res.is_ok());
382 res.unwrap()
383 };
384
385 // check that generated instance is satisfiable
386 assert!(S.is_sat(gens, &U, &W).is_ok());
387
388 (O, U, W)
389 };
390
391 let mut csprng: OsRng = OsRng;
392 let I = S::random(&mut csprng); // the first input is picked randomly for the first instance
393 let (O, U1, W1) = rand_inst_witness_generator(&gens, &I);
394 let (_O, U2, W2) = rand_inst_witness_generator(&gens, &O);
395
396 // execute a sequence of folds
397 execute_sequence(&gens, &ro_consts, &S, &U1, &W1, &U2, &W2);
398 }
399}