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