testudo/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 byteorder;
8extern crate core;
9extern crate curve25519_dalek;
10extern crate digest;
11extern crate merlin;
12extern crate rand;
13extern crate rayon;
14extern crate sha3;
15extern crate test;
16
17mod commitments;
18mod dense_mlpoly;
19mod errors;
20mod group;
21mod math;
22mod nizk;
23mod product_tree;
24mod r1csinstance;
25mod r1csproof;
26mod random;
27mod scalar;
28mod sparse_mlpoly;
29mod sumcheck;
30mod timer;
31mod transcript;
32mod unipoly;
33
34use errors::ProofVerifyError;
35use merlin::Transcript;
36use r1csinstance::{
37 R1CSCommitment, R1CSCommitmentGens, R1CSDecommitment, R1CSEvalProof, R1CSInstance,
38};
39use r1csproof::{R1CSGens, R1CSProof};
40use random::RandomTape;
41use scalar::Scalar;
42use serde::{Deserialize, Serialize};
43use timer::Timer;
44use transcript::{AppendToTranscript, ProofTranscript};
45
46/// `ComputationCommitment` holds a public preprocessed NP statement (e.g., R1CS)
47pub struct ComputationCommitment {
48 comm: R1CSCommitment,
49}
50
51/// `ComputationDecommitment` holds information to decommit `ComputationCommitment`
52pub struct ComputationDecommitment {
53 decomm: R1CSDecommitment,
54}
55
56/// `Instance` holds the description of R1CS matrices
57pub struct Instance {
58 inst: R1CSInstance,
59}
60
61impl Instance {
62 /// Constructs a new `Instance` and an associated satisfying assignment
63 pub fn new(
64 num_cons: usize,
65 num_vars: usize,
66 num_inputs: usize,
67 ) -> (Self, Vec<Scalar>, Vec<Scalar>) {
68 let (inst, vars, inputs) = R1CSInstance::produce_synthetic_r1cs(num_cons, num_vars, num_inputs);
69 (Instance { inst }, vars, inputs)
70 }
71}
72
73/// `SNARKGens` holds public parameters for producing and verifying proofs with the Spartan SNARK
74pub struct SNARKGens {
75 gens_r1cs_sat: R1CSGens,
76 gens_r1cs_eval: R1CSCommitmentGens,
77}
78
79impl SNARKGens {
80 /// Constructs a new `SNARKGens` given the size of the R1CS statement
81 pub fn new(num_cons: usize, num_vars: usize, num_inputs: usize, num_nz_entries: usize) -> Self {
82 let gens_r1cs_sat = R1CSGens::new(b"gens_r1cs_sat", num_cons, num_vars);
83 let gens_r1cs_eval = R1CSCommitmentGens::new(
84 b"gens_r1cs_eval",
85 num_cons,
86 num_vars,
87 num_inputs,
88 num_nz_entries,
89 );
90 SNARKGens {
91 gens_r1cs_sat,
92 gens_r1cs_eval,
93 }
94 }
95}
96
97/// `SNARK` holds a proof produced by Spartan SNARK
98#[derive(Serialize, Deserialize, Debug)]
99pub struct SNARK {
100 r1cs_sat_proof: R1CSProof,
101 inst_evals: (Scalar, Scalar, Scalar),
102 r1cs_eval_proof: R1CSEvalProof,
103}
104
105impl SNARK {
106 fn protocol_name() -> &'static [u8] {
107 b"Spartan SNARK proof"
108 }
109
110 /// A public computation to create a commitment to an R1CS instance
111 pub fn encode(
112 inst: &Instance,
113 gens: &SNARKGens,
114 ) -> (ComputationCommitment, ComputationDecommitment) {
115 let timer_encode = Timer::new("SNARK::encode");
116 let (comm, decomm) = inst.inst.commit(&gens.gens_r1cs_eval);
117 timer_encode.stop();
118 (
119 ComputationCommitment { comm },
120 ComputationDecommitment { decomm },
121 )
122 }
123
124 /// A method to produce a SNARK proof of the satisfiability of an R1CS instance
125 pub fn prove(
126 inst: &Instance,
127 decomm: &ComputationDecommitment,
128 vars: Vec<Scalar>,
129 input: &[Scalar],
130 gens: &SNARKGens,
131 transcript: &mut Transcript,
132 ) -> Self {
133 let timer_prove = Timer::new("SNARK::prove");
134
135 // we create a Transcript object seeded with a random Scalar
136 // to aid the prover produce its randomness
137 let mut random_tape = RandomTape::new(b"proof");
138 transcript.append_protocol_name(SNARK::protocol_name());
139 let (r1cs_sat_proof, rx, ry) = {
140 let (proof, rx, ry) = R1CSProof::prove(
141 &inst.inst,
142 vars,
143 input,
144 &gens.gens_r1cs_sat,
145 transcript,
146 &mut random_tape,
147 );
148 let proof_encoded: Vec<u8> = bincode::serialize(&proof).unwrap();
149 Timer::print(&format!("len_r1cs_sat_proof {:?}", proof_encoded.len()));
150
151 (proof, rx, ry)
152 };
153
154 // We send evaluations of A, B, C at r = (rx, ry) as claims
155 // to enable the verifier complete the first sum-check
156 let timer_eval = Timer::new("eval_sparse_polys");
157 let inst_evals = {
158 let (Ar, Br, Cr) = inst.inst.evaluate(&rx, &ry);
159 Ar.append_to_transcript(b"Ar_claim", transcript);
160 Br.append_to_transcript(b"Br_claim", transcript);
161 Cr.append_to_transcript(b"Cr_claim", transcript);
162 (Ar, Br, Cr)
163 };
164 timer_eval.stop();
165
166 let r1cs_eval_proof = {
167 let proof = R1CSEvalProof::prove(
168 &decomm.decomm,
169 &rx,
170 &ry,
171 &inst_evals,
172 &gens.gens_r1cs_eval,
173 transcript,
174 &mut random_tape,
175 );
176
177 let proof_encoded: Vec<u8> = bincode::serialize(&proof).unwrap();
178 Timer::print(&format!("len_r1cs_eval_proof {:?}", proof_encoded.len()));
179 proof
180 };
181
182 timer_prove.stop();
183 SNARK {
184 r1cs_sat_proof,
185 inst_evals,
186 r1cs_eval_proof,
187 }
188 }
189
190 /// A method to verify the SNARK proof of the satisfiability of an R1CS instance
191 pub fn verify(
192 &self,
193 comm: &ComputationCommitment,
194 input: &[Scalar],
195 transcript: &mut Transcript,
196 gens: &SNARKGens,
197 ) -> Result<(), ProofVerifyError> {
198 let timer_verify = Timer::new("SNARK::verify");
199 transcript.append_protocol_name(SNARK::protocol_name());
200
201 let timer_sat_proof = Timer::new("verify_sat_proof");
202 assert_eq!(input.len(), comm.comm.get_num_inputs());
203 let (rx, ry) = self
204 .r1cs_sat_proof
205 .verify(
206 comm.comm.get_num_vars(),
207 comm.comm.get_num_cons(),
208 input,
209 &self.inst_evals,
210 transcript,
211 &gens.gens_r1cs_sat,
212 )
213 .unwrap();
214 timer_sat_proof.stop();
215
216 let timer_eval_proof = Timer::new("verify_eval_proof");
217 let (Ar, Br, Cr) = &self.inst_evals;
218 Ar.append_to_transcript(b"Ar_claim", transcript);
219 Br.append_to_transcript(b"Br_claim", transcript);
220 Cr.append_to_transcript(b"Cr_claim", transcript);
221 assert!(self
222 .r1cs_eval_proof
223 .verify(
224 &comm.comm,
225 &rx,
226 &ry,
227 &self.inst_evals,
228 &gens.gens_r1cs_eval,
229 transcript
230 )
231 .is_ok());
232 timer_eval_proof.stop();
233 timer_verify.stop();
234 Ok(())
235 }
236}
237
238/// `NIZKGens` holds public parameters for producing and verifying proofs with the Spartan NIZK
239pub struct NIZKGens {
240 gens_r1cs_sat: R1CSGens,
241}
242
243impl NIZKGens {
244 /// Constructs a new `NIZKGens` given the size of the R1CS statement
245 pub fn new(num_cons: usize, num_vars: usize) -> Self {
246 let gens_r1cs_sat = R1CSGens::new(b"gens_r1cs_sat", num_cons, num_vars);
247 NIZKGens { gens_r1cs_sat }
248 }
249}
250
251/// `NIZK` holds a proof produced by Spartan NIZK
252#[derive(Serialize, Deserialize, Debug)]
253pub struct NIZK {
254 r1cs_sat_proof: R1CSProof,
255 r: (Vec<Scalar>, Vec<Scalar>),
256}
257
258impl NIZK {
259 fn protocol_name() -> &'static [u8] {
260 b"Spartan NIZK proof"
261 }
262
263 /// A method to produce a NIZK proof of the satisfiability of an R1CS instance
264 pub fn prove(
265 inst: &Instance,
266 vars: Vec<Scalar>,
267 input: &[Scalar],
268 gens: &NIZKGens,
269 transcript: &mut Transcript,
270 ) -> Self {
271 let timer_prove = Timer::new("NIZK::prove");
272 // we create a Transcript object seeded with a random Scalar
273 // to aid the prover produce its randomness
274 let mut random_tape = RandomTape::new(b"proof");
275 transcript.append_protocol_name(NIZK::protocol_name());
276 let (r1cs_sat_proof, rx, ry) = {
277 let (proof, rx, ry) = R1CSProof::prove(
278 &inst.inst,
279 vars,
280 input,
281 &gens.gens_r1cs_sat,
282 transcript,
283 &mut random_tape,
284 );
285 let proof_encoded: Vec<u8> = bincode::serialize(&proof).unwrap();
286 Timer::print(&format!("len_r1cs_sat_proof {:?}", proof_encoded.len()));
287 (proof, rx, ry)
288 };
289
290 timer_prove.stop();
291 NIZK {
292 r1cs_sat_proof,
293 r: (rx, ry),
294 }
295 }
296
297 /// A method to verify a NIZK proof of the satisfiability of an R1CS instance
298 pub fn verify(
299 &self,
300 inst: &Instance,
301 input: &[Scalar],
302 transcript: &mut Transcript,
303 gens: &NIZKGens,
304 ) -> Result<(), ProofVerifyError> {
305 let timer_verify = Timer::new("NIZK::verify");
306
307 transcript.append_protocol_name(NIZK::protocol_name());
308
309 // We send evaluations of A, B, C at r = (rx, ry) as claims
310 // to enable the verifier complete the first sum-check
311 let timer_eval = Timer::new("eval_sparse_polys");
312 let (claimed_rx, claimed_ry) = &self.r;
313 let inst_evals = inst.inst.evaluate(claimed_rx, claimed_ry);
314 timer_eval.stop();
315
316 let timer_sat_proof = Timer::new("verify_sat_proof");
317 assert_eq!(input.len(), inst.inst.get_num_inputs());
318 let (rx, ry) = self
319 .r1cs_sat_proof
320 .verify(
321 inst.inst.get_num_vars(),
322 inst.inst.get_num_cons(),
323 input,
324 &inst_evals,
325 transcript,
326 &gens.gens_r1cs_sat,
327 )
328 .unwrap();
329
330 // verify if claimed rx and ry are correct
331 assert_eq!(rx, *claimed_rx);
332 assert_eq!(ry, *claimed_ry);
333 timer_sat_proof.stop();
334 timer_verify.stop();
335
336 Ok(())
337 }
338}
339
340#[cfg(test)]
341mod tests {
342 use super::*;
343
344 #[test]
345 pub fn check_snark() {
346 let num_vars = 256;
347 let num_cons = num_vars;
348 let num_inputs = 10;
349 let (inst, vars, inputs) = Instance::new(num_cons, num_vars, num_inputs);
350
351 // produce public generators
352 let gens = SNARKGens::new(num_cons, num_vars, num_inputs, num_cons);
353
354 // create a commitment to R1CSInstance
355 let (comm, decomm) = SNARK::encode(&inst, &gens);
356
357 // produce a proof
358 let mut prover_transcript = Transcript::new(b"example");
359 let proof = SNARK::prove(&inst, &decomm, vars, &inputs, &gens, &mut prover_transcript);
360
361 // verify the proof
362 let mut verifier_transcript = Transcript::new(b"example");
363 assert!(proof
364 .verify(&comm, &inputs, &mut verifier_transcript, &gens)
365 .is_ok());
366 }
367}