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