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