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;
11mod gadgets;
12pub mod pasta;
13mod poseidon;
14pub mod r1cs;
15pub mod traits;
16
17use std::marker::PhantomData;
18
19use commitments::{AppendToTranscriptTrait, CompressedCommitment};
20use errors::NovaError;
21use merlin::Transcript;
22use r1cs::{
23 R1CSGens, R1CSInstance, R1CSShape, R1CSWitness, RelaxedR1CSInstance, RelaxedR1CSWitness,
24};
25use traits::{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_protocol_name(StepSNARK::protocol_name());
61 transcript.append_message(b"protocol-name", StepSNARK::<G>::protocol_name());
62
63 // compute a commitment to the cross-term
64 let (T, comm_T) = S.commit_T(gens, U1, W1, U2, W2)?;
65
66 // append `comm_T` to the transcript and obtain a challenge
67 comm_T.append_to_transcript(b"comm_T", transcript);
68
69 // compute a challenge from the transcript
70 let r = G::Scalar::challenge(b"r", transcript);
71
72 // fold the instance using `r` and `comm_T`
73 let U = U1.fold(U2, &comm_T, &r)?;
74
75 // fold the witness using `r` and `T`
76 let W = W1.fold(W2, &T, &r)?;
77
78 // return the folded instance and witness
79 Ok((
80 StepSNARK {
81 comm_T,
82 _p: Default::default(),
83 },
84 (U, W),
85 ))
86 }
87
88 /// Takes as input a relaxed R1CS instance `U1` and and R1CS instance `U2`
89 /// with the same shape and defined with respect to the same parameters,
90 /// and outputs a folded instance `U` with the same shape,
91 /// with the guarantee that the folded instance `U`
92 /// if and only if `U1` and `U2` are satisfiable.
93 pub fn verify(
94 &self,
95 U1: &RelaxedR1CSInstance<G>,
96 U2: &R1CSInstance<G>,
97 transcript: &mut Transcript,
98 ) -> Result<RelaxedR1CSInstance<G>, NovaError> {
99 // append the protocol name to the transcript
100 transcript.append_message(b"protocol-name", StepSNARK::<G>::protocol_name());
101
102 // append `comm_T` to the transcript and obtain a challenge
103 self.comm_T.append_to_transcript(b"comm_T", transcript);
104
105 // compute a challenge from the transcript
106 let r = G::Scalar::challenge(b"r", transcript);
107
108 // fold the instance using `r` and `comm_T`
109 let U = U1.fold(U2, &self.comm_T, &r)?;
110
111 // return the folded instance
112 Ok(U)
113 }
114}
115
116/// A SNARK that holds the proof of the final step of an incremental computation
117pub struct FinalSNARK<G: Group> {
118 W: RelaxedR1CSWitness<G>,
119}
120
121impl<G: Group> FinalSNARK<G> {
122 /// Produces a proof of a instance given its satisfying witness `W`.
123 pub fn prove(W: &RelaxedR1CSWitness<G>) -> Result<FinalSNARK<G>, NovaError> {
124 Ok(FinalSNARK { W: W.clone() })
125 }
126
127 /// Verifies the proof of a folded instance `U` given its shape `S` public parameters `gens`
128 pub fn verify(
129 &self,
130 gens: &R1CSGens<G>,
131 S: &R1CSShape<G>,
132 U: &RelaxedR1CSInstance<G>,
133 ) -> Result<(), NovaError> {
134 // check that the witness is a valid witness to the folded instance `U`
135 S.is_sat_relaxed(gens, U, &self.W)
136 }
137}
138
139#[cfg(test)]
140mod tests {
141 use super::*;
142 use ff::Field;
143 use rand::rngs::OsRng;
144
145 type S = pasta_curves::pallas::Scalar;
146 type G = pasta_curves::pallas::Point;
147
148 #[test]
149 fn test_tiny_r1cs() {
150 let one = S::one();
151 let (num_cons, num_vars, num_io, A, B, C) = {
152 let num_cons = 4;
153 let num_vars = 4;
154 let num_io = 2;
155
156 // Consider a cubic equation: `x^3 + x + 5 = y`, where `x` and `y` are respectively the input and output.
157 // The R1CS for this problem consists of the following constraints:
158 // `I0 * I0 - Z0 = 0`
159 // `Z0 * I0 - Z1 = 0`
160 // `(Z1 + I0) * 1 - Z2 = 0`
161 // `(Z2 + 5) * 1 - I1 = 0`
162
163 // Relaxed R1CS is a set of three sparse matrices (A B C), where there is a row for every
164 // constraint and a column for every entry in z = (vars, u, inputs)
165 // An R1CS instance is satisfiable iff:
166 // Az \circ Bz = u \cdot Cz + E, where z = (vars, 1, inputs)
167 let mut A: Vec<(usize, usize, S)> = Vec::new();
168 let mut B: Vec<(usize, usize, S)> = Vec::new();
169 let mut C: Vec<(usize, usize, S)> = Vec::new();
170
171 // constraint 0 entries in (A,B,C)
172 // `I0 * I0 - Z0 = 0`
173 A.push((0, num_vars + 1, one));
174 B.push((0, num_vars + 1, one));
175 C.push((0, 0, one));
176
177 // constraint 1 entries in (A,B,C)
178 // `Z0 * I0 - Z1 = 0`
179 A.push((1, 0, one));
180 B.push((1, num_vars + 1, one));
181 C.push((1, 1, one));
182
183 // constraint 2 entries in (A,B,C)
184 // `(Z1 + I0) * 1 - Z2 = 0`
185 A.push((2, 1, one));
186 A.push((2, num_vars + 1, one));
187 B.push((2, num_vars, one));
188 C.push((2, 2, one));
189
190 // constraint 3 entries in (A,B,C)
191 // `(Z2 + 5) * 1 - I1 = 0`
192 A.push((3, 2, one));
193 A.push((3, num_vars, one + one + one + one + one));
194 B.push((3, num_vars, one));
195 C.push((3, num_vars + 2, one));
196
197 (num_cons, num_vars, num_io, A, B, C)
198 };
199
200 // create a shape object
201 let S = {
202 let res = R1CSShape::new(num_cons, num_vars, num_io, &A, &B, &C);
203 assert!(res.is_ok());
204 res.unwrap()
205 };
206
207 // generate generators
208 let gens = R1CSGens::new(num_cons, num_vars);
209
210 let rand_inst_witness_generator =
211 |gens: &R1CSGens<G>, I: &S| -> (S, R1CSInstance<G>, R1CSWitness<G>) {
212 let i0 = *I;
213
214 // compute a satisfying (vars, X) tuple
215 let (O, vars, X) = {
216 let z0 = i0 * i0; // constraint 0
217 let z1 = i0 * z0; // constraint 1
218 let z2 = z1 + i0; // constraint 2
219 let i1 = z2 + one + one + one + one + one; // constraint 3
220
221 // store the witness and IO for the instance
222 let W = vec![z0, z1, z2, S::zero()];
223 let X = vec![i0, i1];
224 (i1, W, X)
225 };
226
227 let W = {
228 let res = R1CSWitness::new(&S, &vars);
229 assert!(res.is_ok());
230 res.unwrap()
231 };
232 let U = {
233 let comm_W = W.commit(gens);
234 let res = R1CSInstance::new(&S, &comm_W, &X);
235 assert!(res.is_ok());
236 res.unwrap()
237 };
238
239 // check that generated instance is satisfiable
240 assert!(S.is_sat(gens, &U, &W).is_ok());
241
242 (O, U, W)
243 };
244
245 let mut csprng: OsRng = OsRng;
246 let I = S::random(&mut csprng); // the first input is picked randomly for the first instance
247 let (O, U1, W1) = rand_inst_witness_generator(&gens, &I);
248 let (_O, U2, W2) = rand_inst_witness_generator(&gens, &O);
249
250 // produce a default running instance
251 let mut r_W = RelaxedR1CSWitness::default(&S);
252 let mut r_U = RelaxedR1CSInstance::default(&gens, &S);
253
254 // produce a step SNARK with (W1, U1) as the first incoming witness-instance pair
255 let mut prover_transcript = Transcript::new(b"StepSNARKExample");
256 let res = StepSNARK::prove(&gens, &S, &r_U, &r_W, &U1, &W1, &mut prover_transcript);
257 assert!(res.is_ok());
258 let (step_snark, (_U, W)) = res.unwrap();
259
260 // verify the step SNARK with U1 as the first incoming instance
261 let mut verifier_transcript = Transcript::new(b"StepSNARKExample");
262 let res = step_snark.verify(&r_U, &U1, &mut verifier_transcript);
263 assert!(res.is_ok());
264 let U = res.unwrap();
265
266 assert_eq!(U, _U);
267
268 // update the running witness and instance
269 r_W = W;
270 r_U = U;
271
272 // produce a step SNARK with (W2, U2) as the second incoming witness-instance pair
273 let res = StepSNARK::prove(&gens, &S, &r_U, &r_W, &U2, &W2, &mut prover_transcript);
274 assert!(res.is_ok());
275 let (step_snark, (_U, W)) = res.unwrap();
276
277 // verify the step SNARK with U1 as the first incoming instance
278 let res = step_snark.verify(&r_U, &U2, &mut verifier_transcript);
279 assert!(res.is_ok());
280 let U = res.unwrap();
281
282 assert_eq!(U, _U);
283
284 // update the running witness and instance
285 r_W = W;
286 r_U = U;
287
288 // produce a final SNARK
289 let res = FinalSNARK::prove(&r_W);
290 assert!(res.is_ok());
291 let final_snark = res.unwrap();
292 // verify the final SNARK
293 let res = final_snark.verify(&gens, &S, &r_U);
294 assert!(res.is_ok());
295 }
296}