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 merlin::Transcript;
20use r1cs::{
21 R1CSGens, R1CSInstance, R1CSShape, R1CSWitness, RelaxedR1CSInstance, RelaxedR1CSWitness,
22};
23use std::marker::PhantomData;
24use traits::{AppendToTranscriptTrait, ChallengeTrait, Group};
25
26/// A SNARK that holds the proof of a step of an incremental computation
27pub struct StepSNARK<G: Group> {
28 comm_T: CompressedCommitment<G::CompressedGroupElement>,
29 _p: PhantomData<G>,
30}
31
32impl<G: Group> StepSNARK<G> {
33 fn protocol_name() -> &'static [u8] {
34 b"NovaStepSNARK"
35 }
36
37 /// Takes as input a Relaxed R1CS instance-witness tuple `(U1, W1)` and
38 /// an R1CS instance-witness tuple `(U2, W2)` with the same structure `shape`
39 /// and defined with respect to the same `gens`, and outputs
40 /// a folded Relaxed R1CS instance-witness tuple `(U, W)` of the same shape `shape`,
41 /// with the guarantee that the folded witness `W` satisfies the folded instance `U`
42 /// if and only if `W1` satisfies `U1` and `W2` satisfies `U2`.
43 pub fn prove(
44 gens: &R1CSGens<G>,
45 S: &R1CSShape<G>,
46 U1: &RelaxedR1CSInstance<G>,
47 W1: &RelaxedR1CSWitness<G>,
48 U2: &R1CSInstance<G>,
49 W2: &R1CSWitness<G>,
50 transcript: &mut Transcript,
51 ) -> Result<
52 (
53 StepSNARK<G>,
54 (RelaxedR1CSInstance<G>, RelaxedR1CSWitness<G>),
55 ),
56 NovaError,
57 > {
58 // append the protocol name to the transcript
59 transcript.append_message(b"protocol-name", StepSNARK::<G>::protocol_name());
60
61 // append S to the transcript
62 S.append_to_transcript(b"S", transcript);
63
64 // append U1 and U2 to transcript
65 U1.append_to_transcript(b"U1", transcript);
66 U2.append_to_transcript(b"U2", transcript);
67
68 // compute a commitment to the cross-term
69 let (T, comm_T) = S.commit_T(gens, U1, W1, U2, W2)?;
70
71 // append `comm_T` to the transcript and obtain a challenge
72 comm_T.append_to_transcript(b"comm_T", transcript);
73
74 // compute a challenge from the transcript
75 let r = G::Scalar::challenge(b"r", transcript);
76
77 // fold the instance using `r` and `comm_T`
78 let U = U1.fold(U2, &comm_T, &r)?;
79
80 // fold the witness using `r` and `T`
81 let W = W1.fold(W2, &T, &r)?;
82
83 // return the folded instance and witness
84 Ok((
85 StepSNARK {
86 comm_T,
87 _p: Default::default(),
88 },
89 (U, W),
90 ))
91 }
92
93 /// Takes as input a relaxed R1CS instance `U1` and and R1CS instance `U2`
94 /// with the same shape and defined with respect to the same parameters,
95 /// and outputs a folded instance `U` with the same shape,
96 /// with the guarantee that the folded instance `U`
97 /// if and only if `U1` and `U2` are satisfiable.
98 pub fn verify(
99 &self,
100 S: &R1CSShape<G>,
101 U1: &RelaxedR1CSInstance<G>,
102 U2: &R1CSInstance<G>,
103 transcript: &mut Transcript,
104 ) -> Result<RelaxedR1CSInstance<G>, NovaError> {
105 // append the protocol name to the transcript
106 transcript.append_message(b"protocol-name", StepSNARK::<G>::protocol_name());
107
108 // append S to the transcript
109 S.append_to_transcript(b"S", transcript);
110
111 // append U1 and U2 to transcript
112 U1.append_to_transcript(b"U1", transcript);
113 U2.append_to_transcript(b"U2", transcript);
114
115 // append `comm_T` to the transcript and obtain a challenge
116 self.comm_T.append_to_transcript(b"comm_T", transcript);
117
118 // compute a challenge from the transcript
119 let r = G::Scalar::challenge(b"r", transcript);
120
121 // fold the instance using `r` and `comm_T`
122 let U = U1.fold(U2, &self.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 mut prover_transcript = Transcript::new(b"StepSNARKExample");
243 let res = StepSNARK::prove(gens, shape, &r_U, &r_W, U1, W1, &mut prover_transcript);
244 assert!(res.is_ok());
245 let (step_snark, (_U, W)) = res.unwrap();
246
247 // verify the step SNARK with U1 as the first incoming instance
248 let mut verifier_transcript = Transcript::new(b"StepSNARKExample");
249 let res = step_snark.verify(shape, &r_U, U1, &mut verifier_transcript);
250 assert!(res.is_ok());
251 let U = res.unwrap();
252
253 assert_eq!(U, _U);
254
255 // update the running witness and instance
256 r_W = W;
257 r_U = U;
258
259 // produce a step SNARK with (W2, U2) as the second incoming witness-instance pair
260 let res = StepSNARK::prove(gens, shape, &r_U, &r_W, U2, W2, &mut prover_transcript);
261 assert!(res.is_ok());
262 let (step_snark, (_U, W)) = res.unwrap();
263
264 // verify the step SNARK with U1 as the first incoming instance
265 let res = step_snark.verify(shape, &r_U, U2, &mut verifier_transcript);
266 assert!(res.is_ok());
267 let U = res.unwrap();
268
269 assert_eq!(U, _U);
270
271 // update the running witness and instance
272 r_W = W;
273 r_U = U;
274
275 // produce a final SNARK
276 let res = FinalSNARK::prove(&r_W);
277 assert!(res.is_ok());
278 let final_snark = res.unwrap();
279 // verify the final SNARK
280 let res = final_snark.verify(gens, shape, &r_U);
281 assert!(res.is_ok());
282 }
283
284 #[test]
285 fn test_tiny_r1cs() {
286 let one = S::one();
287 let (num_cons, num_vars, num_io, A, B, C) = {
288 let num_cons = 4;
289 let num_vars = 4;
290 let num_io = 2;
291
292 // Consider a cubic equation: `x^3 + x + 5 = y`, where `x` and `y` are respectively the input and output.
293 // The R1CS for this problem consists of the following constraints:
294 // `I0 * I0 - Z0 = 0`
295 // `Z0 * I0 - Z1 = 0`
296 // `(Z1 + I0) * 1 - Z2 = 0`
297 // `(Z2 + 5) * 1 - I1 = 0`
298
299 // Relaxed R1CS is a set of three sparse matrices (A B C), where there is a row for every
300 // constraint and a column for every entry in z = (vars, u, inputs)
301 // An R1CS instance is satisfiable iff:
302 // Az \circ Bz = u \cdot Cz + E, where z = (vars, 1, inputs)
303 let mut A: Vec<(usize, usize, S)> = Vec::new();
304 let mut B: Vec<(usize, usize, S)> = Vec::new();
305 let mut C: Vec<(usize, usize, S)> = Vec::new();
306
307 // constraint 0 entries in (A,B,C)
308 // `I0 * I0 - Z0 = 0`
309 A.push((0, num_vars + 1, one));
310 B.push((0, num_vars + 1, one));
311 C.push((0, 0, one));
312
313 // constraint 1 entries in (A,B,C)
314 // `Z0 * I0 - Z1 = 0`
315 A.push((1, 0, one));
316 B.push((1, num_vars + 1, one));
317 C.push((1, 1, one));
318
319 // constraint 2 entries in (A,B,C)
320 // `(Z1 + I0) * 1 - Z2 = 0`
321 A.push((2, 1, one));
322 A.push((2, num_vars + 1, one));
323 B.push((2, num_vars, one));
324 C.push((2, 2, one));
325
326 // constraint 3 entries in (A,B,C)
327 // `(Z2 + 5) * 1 - I1 = 0`
328 A.push((3, 2, one));
329 A.push((3, num_vars, one + one + one + one + one));
330 B.push((3, num_vars, one));
331 C.push((3, num_vars + 2, one));
332
333 (num_cons, num_vars, num_io, A, B, C)
334 };
335
336 // create a shape object
337 let S = {
338 let res = R1CSShape::new(num_cons, num_vars, num_io, &A, &B, &C);
339 assert!(res.is_ok());
340 res.unwrap()
341 };
342
343 // generate generators
344 let gens = R1CSGens::new(num_cons, num_vars);
345
346 let rand_inst_witness_generator =
347 |gens: &R1CSGens<G>, I: &S| -> (S, R1CSInstance<G>, R1CSWitness<G>) {
348 let i0 = *I;
349
350 // compute a satisfying (vars, X) tuple
351 let (O, vars, X) = {
352 let z0 = i0 * i0; // constraint 0
353 let z1 = i0 * z0; // constraint 1
354 let z2 = z1 + i0; // constraint 2
355 let i1 = z2 + one + one + one + one + one; // constraint 3
356
357 // store the witness and IO for the instance
358 let W = vec![z0, z1, z2, S::zero()];
359 let X = vec![i0, i1];
360 (i1, W, X)
361 };
362
363 let W = {
364 let res = R1CSWitness::new(&S, &vars);
365 assert!(res.is_ok());
366 res.unwrap()
367 };
368 let U = {
369 let comm_W = W.commit(gens);
370 let res = R1CSInstance::new(&S, &comm_W, &X);
371 assert!(res.is_ok());
372 res.unwrap()
373 };
374
375 // check that generated instance is satisfiable
376 assert!(S.is_sat(gens, &U, &W).is_ok());
377
378 (O, U, W)
379 };
380
381 let mut csprng: OsRng = OsRng;
382 let I = S::random(&mut csprng); // the first input is picked randomly for the first instance
383 let (O, U1, W1) = rand_inst_witness_generator(&gens, &I);
384 let (_O, U2, W2) = rand_inst_witness_generator(&gens, &O);
385
386 // execute a sequence of folds
387 execute_sequence(&gens, &S, &U1, &W1, &U2, &W2);
388 }
389}