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