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