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