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