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, R1CSError};
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/// `Assignment` holds an assignment of values to either the inputs or variables in an `Instance`
57#[derive(Clone)]
58pub struct Assignment {
59 assignment: Vec<Scalar>,
60}
61
62impl Assignment {
63 /// Constructs a new `Assignment` from a vector
64 pub fn new(assignment: &Vec<[u8; 32]>) -> Result<Assignment, R1CSError> {
65 let bytes_to_scalar = |vec: &Vec<[u8; 32]>| -> Result<Vec<Scalar>, R1CSError> {
66 let mut vec_scalar: Vec<Scalar> = Vec::new();
67 for i in 0..vec.len() {
68 let val = Scalar::from_bytes(&vec[i]);
69 if val.is_some().unwrap_u8() == 1 {
70 vec_scalar.push(val.unwrap());
71 } else {
72 return Err(R1CSError::InvalidScalar);
73 }
74 }
75 Ok(vec_scalar)
76 };
77
78 let assignment_scalar = bytes_to_scalar(assignment);
79
80 // check for any parsing errors
81 if assignment_scalar.is_err() {
82 return Err(R1CSError::InvalidScalar);
83 }
84
85 Ok(Assignment {
86 assignment: assignment_scalar.unwrap(),
87 })
88 }
89}
90
91/// `VarsAssignment` holds an assignment of values to variables in an `Instance`
92pub type VarsAssignment = Assignment;
93
94/// `VarsAssignment` holds an assignment of values to variables in an `Instance`
95pub type InputsAssignment = Assignment;
96
97/// `Instance` holds the description of R1CS matrices
98pub struct Instance {
99 inst: R1CSInstance,
100}
101
102impl Instance {
103 /// Constructs a new `Instance` and an associated satisfying assignment
104 pub fn new(
105 num_cons: usize,
106 num_vars: usize,
107 num_inputs: usize,
108 A: &Vec<(usize, usize, [u8; 32])>,
109 B: &Vec<(usize, usize, [u8; 32])>,
110 C: &Vec<(usize, usize, [u8; 32])>,
111 ) -> Result<Instance, R1CSError> {
112 // check that num_cons is power of 2
113 if num_cons.next_power_of_two() != num_cons {
114 return Err(R1CSError::NonPowerOfTwoCons);
115 }
116
117 // check that the number of variables is a power of 2
118 if num_vars.next_power_of_two() != num_vars {
119 return Err(R1CSError::NonPowerOfTwoVars);
120 }
121
122 // check that num_inputs + 1 <= num_vars
123 if num_inputs >= num_vars {
124 return Err(R1CSError::InvalidNumberOfInputs);
125 }
126
127 let bytes_to_scalar =
128 |tups: &Vec<(usize, usize, [u8; 32])>| -> Result<Vec<(usize, usize, Scalar)>, R1CSError> {
129 let mut mat: Vec<(usize, usize, Scalar)> = Vec::new();
130 for i in 0..tups.len() {
131 let (row, col, val_bytes) = tups[i];
132 let val = Scalar::from_bytes(&val_bytes);
133 if val.is_some().unwrap_u8() == 1 {
134 mat.push((row, col, val.unwrap()));
135 } else {
136 return Err(R1CSError::InvalidScalar);
137 }
138 }
139 Ok(mat)
140 };
141
142 let A_scalar = bytes_to_scalar(A);
143 let B_scalar = bytes_to_scalar(B);
144 let C_scalar = bytes_to_scalar(C);
145
146 // check for any parsing errors
147 if A_scalar.is_err() || B_scalar.is_err() || C_scalar.is_err() {
148 return Err(R1CSError::InvalidScalar);
149 }
150
151 let inst = R1CSInstance::new(
152 num_cons,
153 num_vars,
154 num_inputs,
155 &A_scalar.unwrap(),
156 &B_scalar.unwrap(),
157 &C_scalar.unwrap(),
158 );
159
160 Ok(Instance { inst })
161 }
162
163 /// Checks if a given R1CSInstance is satisfiable with a given variables and inputs assignments
164 pub fn is_sat(&self, vars: &VarsAssignment, inputs: &InputsAssignment) -> Result<bool, R1CSError> {
165
166 if vars.assignment.len() != self.inst.get_num_vars() {
167 return Err(R1CSError::InvalidNumberOfVars)
168 }
169
170 if inputs.assignment.len() != self.inst.get_num_inputs() {
171 return Err(R1CSError::InvalidNumberOfInputs)
172 }
173
174 Ok(self.inst.is_sat(&vars.assignment, &inputs.assignment))
175 }
176
177 /// Constructs a new synthetic R1CS `Instance` and an associated satisfying assignment
178 pub fn produce_synthetic_r1cs(
179 num_cons: usize,
180 num_vars: usize,
181 num_inputs: usize,
182 ) -> (Instance, VarsAssignment, InputsAssignment) {
183 let (inst, vars, inputs) = R1CSInstance::produce_synthetic_r1cs(num_cons, num_vars, num_inputs);
184 (
185 Instance { inst },
186 VarsAssignment { assignment: vars },
187 InputsAssignment { assignment: inputs },
188 )
189 }
190}
191
192/// `SNARKGens` holds public parameters for producing and verifying proofs with the Spartan SNARK
193pub struct SNARKGens {
194 gens_r1cs_sat: R1CSGens,
195 gens_r1cs_eval: R1CSCommitmentGens,
196}
197
198impl SNARKGens {
199 /// Constructs a new `SNARKGens` given the size of the R1CS statement
200 pub fn new(num_cons: usize, num_vars: usize, num_inputs: usize, num_nz_entries: usize) -> Self {
201 let gens_r1cs_sat = R1CSGens::new(b"gens_r1cs_sat", num_cons, num_vars);
202 let gens_r1cs_eval = R1CSCommitmentGens::new(
203 b"gens_r1cs_eval",
204 num_cons,
205 num_vars,
206 num_inputs,
207 num_nz_entries,
208 );
209 SNARKGens {
210 gens_r1cs_sat,
211 gens_r1cs_eval,
212 }
213 }
214}
215
216/// `SNARK` holds a proof produced by Spartan SNARK
217#[derive(Serialize, Deserialize, Debug)]
218pub struct SNARK {
219 r1cs_sat_proof: R1CSProof,
220 inst_evals: (Scalar, Scalar, Scalar),
221 r1cs_eval_proof: R1CSEvalProof,
222}
223
224impl SNARK {
225 fn protocol_name() -> &'static [u8] {
226 b"Spartan SNARK proof"
227 }
228
229 /// A public computation to create a commitment to an R1CS instance
230 pub fn encode(
231 inst: &Instance,
232 gens: &SNARKGens,
233 ) -> (ComputationCommitment, ComputationDecommitment) {
234 let timer_encode = Timer::new("SNARK::encode");
235 let (comm, decomm) = inst.inst.commit(&gens.gens_r1cs_eval);
236 timer_encode.stop();
237 (
238 ComputationCommitment { comm },
239 ComputationDecommitment { decomm },
240 )
241 }
242
243 /// A method to produce a SNARK proof of the satisfiability of an R1CS instance
244 pub fn prove(
245 inst: &Instance,
246 decomm: &ComputationDecommitment,
247 vars: VarsAssignment,
248 inputs: &InputsAssignment,
249 gens: &SNARKGens,
250 transcript: &mut Transcript,
251 ) -> Self {
252 let timer_prove = Timer::new("SNARK::prove");
253
254 // we create a Transcript object seeded with a random Scalar
255 // to aid the prover produce its randomness
256 let mut random_tape = RandomTape::new(b"proof");
257 transcript.append_protocol_name(SNARK::protocol_name());
258 let (r1cs_sat_proof, rx, ry) = {
259 let (proof, rx, ry) = R1CSProof::prove(
260 &inst.inst,
261 vars.assignment,
262 &inputs.assignment,
263 &gens.gens_r1cs_sat,
264 transcript,
265 &mut random_tape,
266 );
267 let proof_encoded: Vec<u8> = bincode::serialize(&proof).unwrap();
268 Timer::print(&format!("len_r1cs_sat_proof {:?}", proof_encoded.len()));
269
270 (proof, rx, ry)
271 };
272
273 // We send evaluations of A, B, C at r = (rx, ry) as claims
274 // to enable the verifier complete the first sum-check
275 let timer_eval = Timer::new("eval_sparse_polys");
276 let inst_evals = {
277 let (Ar, Br, Cr) = inst.inst.evaluate(&rx, &ry);
278 Ar.append_to_transcript(b"Ar_claim", transcript);
279 Br.append_to_transcript(b"Br_claim", transcript);
280 Cr.append_to_transcript(b"Cr_claim", transcript);
281 (Ar, Br, Cr)
282 };
283 timer_eval.stop();
284
285 let r1cs_eval_proof = {
286 let proof = R1CSEvalProof::prove(
287 &decomm.decomm,
288 &rx,
289 &ry,
290 &inst_evals,
291 &gens.gens_r1cs_eval,
292 transcript,
293 &mut random_tape,
294 );
295
296 let proof_encoded: Vec<u8> = bincode::serialize(&proof).unwrap();
297 Timer::print(&format!("len_r1cs_eval_proof {:?}", proof_encoded.len()));
298 proof
299 };
300
301 timer_prove.stop();
302 SNARK {
303 r1cs_sat_proof,
304 inst_evals,
305 r1cs_eval_proof,
306 }
307 }
308
309 /// A method to verify the SNARK proof of the satisfiability of an R1CS instance
310 pub fn verify(
311 &self,
312 comm: &ComputationCommitment,
313 input: &InputsAssignment,
314 transcript: &mut Transcript,
315 gens: &SNARKGens,
316 ) -> Result<(), ProofVerifyError> {
317 let timer_verify = Timer::new("SNARK::verify");
318 transcript.append_protocol_name(SNARK::protocol_name());
319
320 let timer_sat_proof = Timer::new("verify_sat_proof");
321 assert_eq!(input.assignment.len(), comm.comm.get_num_inputs());
322 let (rx, ry) = self
323 .r1cs_sat_proof
324 .verify(
325 comm.comm.get_num_vars(),
326 comm.comm.get_num_cons(),
327 &input.assignment,
328 &self.inst_evals,
329 transcript,
330 &gens.gens_r1cs_sat,
331 )
332 .unwrap();
333 timer_sat_proof.stop();
334
335 let timer_eval_proof = Timer::new("verify_eval_proof");
336 let (Ar, Br, Cr) = &self.inst_evals;
337 Ar.append_to_transcript(b"Ar_claim", transcript);
338 Br.append_to_transcript(b"Br_claim", transcript);
339 Cr.append_to_transcript(b"Cr_claim", transcript);
340 assert!(self
341 .r1cs_eval_proof
342 .verify(
343 &comm.comm,
344 &rx,
345 &ry,
346 &self.inst_evals,
347 &gens.gens_r1cs_eval,
348 transcript
349 )
350 .is_ok());
351 timer_eval_proof.stop();
352 timer_verify.stop();
353 Ok(())
354 }
355}
356
357/// `NIZKGens` holds public parameters for producing and verifying proofs with the Spartan NIZK
358pub struct NIZKGens {
359 gens_r1cs_sat: R1CSGens,
360}
361
362impl NIZKGens {
363 /// Constructs a new `NIZKGens` given the size of the R1CS statement
364 pub fn new(num_cons: usize, num_vars: usize) -> Self {
365 let gens_r1cs_sat = R1CSGens::new(b"gens_r1cs_sat", num_cons, num_vars);
366 NIZKGens { gens_r1cs_sat }
367 }
368}
369
370/// `NIZK` holds a proof produced by Spartan NIZK
371#[derive(Serialize, Deserialize, Debug)]
372pub struct NIZK {
373 r1cs_sat_proof: R1CSProof,
374 r: (Vec<Scalar>, Vec<Scalar>),
375}
376
377impl NIZK {
378 fn protocol_name() -> &'static [u8] {
379 b"Spartan NIZK proof"
380 }
381
382 /// A method to produce a NIZK proof of the satisfiability of an R1CS instance
383 pub fn prove(
384 inst: &Instance,
385 vars: VarsAssignment,
386 input: &InputsAssignment,
387 gens: &NIZKGens,
388 transcript: &mut Transcript,
389 ) -> Self {
390 let timer_prove = Timer::new("NIZK::prove");
391 // we create a Transcript object seeded with a random Scalar
392 // to aid the prover produce its randomness
393 let mut random_tape = RandomTape::new(b"proof");
394 transcript.append_protocol_name(NIZK::protocol_name());
395 let (r1cs_sat_proof, rx, ry) = {
396 let (proof, rx, ry) = R1CSProof::prove(
397 &inst.inst,
398 vars.assignment,
399 &input.assignment,
400 &gens.gens_r1cs_sat,
401 transcript,
402 &mut random_tape,
403 );
404 let proof_encoded: Vec<u8> = bincode::serialize(&proof).unwrap();
405 Timer::print(&format!("len_r1cs_sat_proof {:?}", proof_encoded.len()));
406 (proof, rx, ry)
407 };
408
409 timer_prove.stop();
410 NIZK {
411 r1cs_sat_proof,
412 r: (rx, ry),
413 }
414 }
415
416 /// A method to verify a NIZK proof of the satisfiability of an R1CS instance
417 pub fn verify(
418 &self,
419 inst: &Instance,
420 input: &InputsAssignment,
421 transcript: &mut Transcript,
422 gens: &NIZKGens,
423 ) -> Result<(), ProofVerifyError> {
424 let timer_verify = Timer::new("NIZK::verify");
425
426 transcript.append_protocol_name(NIZK::protocol_name());
427
428 // We send evaluations of A, B, C at r = (rx, ry) as claims
429 // to enable the verifier complete the first sum-check
430 let timer_eval = Timer::new("eval_sparse_polys");
431 let (claimed_rx, claimed_ry) = &self.r;
432 let inst_evals = inst.inst.evaluate(claimed_rx, claimed_ry);
433 timer_eval.stop();
434
435 let timer_sat_proof = Timer::new("verify_sat_proof");
436 assert_eq!(input.assignment.len(), inst.inst.get_num_inputs());
437 let (rx, ry) = self
438 .r1cs_sat_proof
439 .verify(
440 inst.inst.get_num_vars(),
441 inst.inst.get_num_cons(),
442 &input.assignment,
443 &inst_evals,
444 transcript,
445 &gens.gens_r1cs_sat,
446 )
447 .unwrap();
448
449 // verify if claimed rx and ry are correct
450 assert_eq!(rx, *claimed_rx);
451 assert_eq!(ry, *claimed_ry);
452 timer_sat_proof.stop();
453 timer_verify.stop();
454
455 Ok(())
456 }
457}
458
459#[cfg(test)]
460mod tests {
461 use super::*;
462
463 #[test]
464 pub fn check_snark() {
465 let num_vars = 256;
466 let num_cons = num_vars;
467 let num_inputs = 10;
468
469 // produce public generators
470 let gens = SNARKGens::new(num_cons, num_vars, num_inputs, num_cons);
471
472 // produce a synthetic R1CSInstance
473 let (inst, vars, inputs) = Instance::produce_synthetic_r1cs(num_cons, num_vars, num_inputs);
474
475 // create a commitment to R1CSInstance
476 let (comm, decomm) = SNARK::encode(&inst, &gens);
477
478 // produce a proof
479 let mut prover_transcript = Transcript::new(b"example");
480 let proof = SNARK::prove(&inst, &decomm, vars, &inputs, &gens, &mut prover_transcript);
481
482 // verify the proof
483 let mut verifier_transcript = Transcript::new(b"example");
484 assert!(proof
485 .verify(&comm, &inputs, &mut verifier_transcript, &gens)
486 .is_ok());
487 }
488}