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