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