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
133 // row must be smaller than num_cons
134 if row >= num_cons {
135 return Err(R1CSError::InvalidIndex);
136 }
137
138 // col must be smaller than num_vars + 1 + num_inputs
139 if col >= num_vars + 1 + num_inputs {
140 return Err(R1CSError::InvalidIndex);
141 }
142
143 let val = Scalar::from_bytes(&val_bytes);
144 if val.is_some().unwrap_u8() == 1 {
145 mat.push((row, col, val.unwrap()));
146 } else {
147 return Err(R1CSError::InvalidScalar);
148 }
149 }
150 Ok(mat)
151 };
152
153 let A_scalar = bytes_to_scalar(A);
154 if A_scalar.is_err() {
155 return Err(A_scalar.err().unwrap());
156 }
157
158 let B_scalar = bytes_to_scalar(B);
159 if B_scalar.is_err() {
160 return Err(B_scalar.err().unwrap());
161 }
162
163 let C_scalar = bytes_to_scalar(C);
164 if C_scalar.is_err() {
165 return Err(C_scalar.err().unwrap());
166 }
167
168 let inst = R1CSInstance::new(
169 num_cons,
170 num_vars,
171 num_inputs,
172 &A_scalar.unwrap(),
173 &B_scalar.unwrap(),
174 &C_scalar.unwrap(),
175 );
176
177 Ok(Instance { inst })
178 }
179
180 /// Checks if a given R1CSInstance is satisfiable with a given variables and inputs assignments
181 pub fn is_sat(
182 &self,
183 vars: &VarsAssignment,
184 inputs: &InputsAssignment,
185 ) -> Result<bool, R1CSError> {
186 if vars.assignment.len() != self.inst.get_num_vars() {
187 return Err(R1CSError::InvalidNumberOfVars);
188 }
189
190 if inputs.assignment.len() != self.inst.get_num_inputs() {
191 return Err(R1CSError::InvalidNumberOfInputs);
192 }
193
194 Ok(self.inst.is_sat(&vars.assignment, &inputs.assignment))
195 }
196
197 /// Constructs a new synthetic R1CS `Instance` and an associated satisfying assignment
198 pub fn produce_synthetic_r1cs(
199 num_cons: usize,
200 num_vars: usize,
201 num_inputs: usize,
202 ) -> (Instance, VarsAssignment, InputsAssignment) {
203 let (inst, vars, inputs) = R1CSInstance::produce_synthetic_r1cs(num_cons, num_vars, num_inputs);
204 (
205 Instance { inst },
206 VarsAssignment { assignment: vars },
207 InputsAssignment { assignment: inputs },
208 )
209 }
210}
211
212/// `SNARKGens` holds public parameters for producing and verifying proofs with the Spartan SNARK
213pub struct SNARKGens {
214 gens_r1cs_sat: R1CSGens,
215 gens_r1cs_eval: R1CSCommitmentGens,
216}
217
218impl SNARKGens {
219 /// Constructs a new `SNARKGens` given the size of the R1CS statement
220 pub fn new(num_cons: usize, num_vars: usize, num_inputs: usize, num_nz_entries: usize) -> Self {
221 let gens_r1cs_sat = R1CSGens::new(b"gens_r1cs_sat", num_cons, num_vars);
222 let gens_r1cs_eval = R1CSCommitmentGens::new(
223 b"gens_r1cs_eval",
224 num_cons,
225 num_vars,
226 num_inputs,
227 num_nz_entries,
228 );
229 SNARKGens {
230 gens_r1cs_sat,
231 gens_r1cs_eval,
232 }
233 }
234}
235
236/// `SNARK` holds a proof produced by Spartan SNARK
237#[derive(Serialize, Deserialize, Debug)]
238pub struct SNARK {
239 r1cs_sat_proof: R1CSProof,
240 inst_evals: (Scalar, Scalar, Scalar),
241 r1cs_eval_proof: R1CSEvalProof,
242}
243
244impl SNARK {
245 fn protocol_name() -> &'static [u8] {
246 b"Spartan SNARK proof"
247 }
248
249 /// A public computation to create a commitment to an R1CS instance
250 pub fn encode(
251 inst: &Instance,
252 gens: &SNARKGens,
253 ) -> (ComputationCommitment, ComputationDecommitment) {
254 let timer_encode = Timer::new("SNARK::encode");
255 let (comm, decomm) = inst.inst.commit(&gens.gens_r1cs_eval);
256 timer_encode.stop();
257 (
258 ComputationCommitment { comm },
259 ComputationDecommitment { decomm },
260 )
261 }
262
263 /// A method to produce a SNARK proof of the satisfiability of an R1CS instance
264 pub fn prove(
265 inst: &Instance,
266 decomm: &ComputationDecommitment,
267 vars: VarsAssignment,
268 inputs: &InputsAssignment,
269 gens: &SNARKGens,
270 transcript: &mut Transcript,
271 ) -> Self {
272 let timer_prove = Timer::new("SNARK::prove");
273
274 // we create a Transcript object seeded with a random Scalar
275 // to aid the prover produce its randomness
276 let mut random_tape = RandomTape::new(b"proof");
277 transcript.append_protocol_name(SNARK::protocol_name());
278 let (r1cs_sat_proof, rx, ry) = {
279 let (proof, rx, ry) = R1CSProof::prove(
280 &inst.inst,
281 vars.assignment,
282 &inputs.assignment,
283 &gens.gens_r1cs_sat,
284 transcript,
285 &mut random_tape,
286 );
287 let proof_encoded: Vec<u8> = bincode::serialize(&proof).unwrap();
288 Timer::print(&format!("len_r1cs_sat_proof {:?}", proof_encoded.len()));
289
290 (proof, rx, ry)
291 };
292
293 // We send evaluations of A, B, C at r = (rx, ry) as claims
294 // to enable the verifier complete the first sum-check
295 let timer_eval = Timer::new("eval_sparse_polys");
296 let inst_evals = {
297 let (Ar, Br, Cr) = inst.inst.evaluate(&rx, &ry);
298 Ar.append_to_transcript(b"Ar_claim", transcript);
299 Br.append_to_transcript(b"Br_claim", transcript);
300 Cr.append_to_transcript(b"Cr_claim", transcript);
301 (Ar, Br, Cr)
302 };
303 timer_eval.stop();
304
305 let r1cs_eval_proof = {
306 let proof = R1CSEvalProof::prove(
307 &decomm.decomm,
308 &rx,
309 &ry,
310 &inst_evals,
311 &gens.gens_r1cs_eval,
312 transcript,
313 &mut random_tape,
314 );
315
316 let proof_encoded: Vec<u8> = bincode::serialize(&proof).unwrap();
317 Timer::print(&format!("len_r1cs_eval_proof {:?}", proof_encoded.len()));
318 proof
319 };
320
321 timer_prove.stop();
322 SNARK {
323 r1cs_sat_proof,
324 inst_evals,
325 r1cs_eval_proof,
326 }
327 }
328
329 /// A method to verify the SNARK proof of the satisfiability of an R1CS instance
330 pub fn verify(
331 &self,
332 comm: &ComputationCommitment,
333 input: &InputsAssignment,
334 transcript: &mut Transcript,
335 gens: &SNARKGens,
336 ) -> Result<(), ProofVerifyError> {
337 let timer_verify = Timer::new("SNARK::verify");
338 transcript.append_protocol_name(SNARK::protocol_name());
339
340 let timer_sat_proof = Timer::new("verify_sat_proof");
341 assert_eq!(input.assignment.len(), comm.comm.get_num_inputs());
342 let (rx, ry) = self
343 .r1cs_sat_proof
344 .verify(
345 comm.comm.get_num_vars(),
346 comm.comm.get_num_cons(),
347 &input.assignment,
348 &self.inst_evals,
349 transcript,
350 &gens.gens_r1cs_sat,
351 )
352 .unwrap();
353 timer_sat_proof.stop();
354
355 let timer_eval_proof = Timer::new("verify_eval_proof");
356 let (Ar, Br, Cr) = &self.inst_evals;
357 Ar.append_to_transcript(b"Ar_claim", transcript);
358 Br.append_to_transcript(b"Br_claim", transcript);
359 Cr.append_to_transcript(b"Cr_claim", transcript);
360 assert!(self
361 .r1cs_eval_proof
362 .verify(
363 &comm.comm,
364 &rx,
365 &ry,
366 &self.inst_evals,
367 &gens.gens_r1cs_eval,
368 transcript
369 )
370 .is_ok());
371 timer_eval_proof.stop();
372 timer_verify.stop();
373 Ok(())
374 }
375}
376
377/// `NIZKGens` holds public parameters for producing and verifying proofs with the Spartan NIZK
378pub struct NIZKGens {
379 gens_r1cs_sat: R1CSGens,
380}
381
382impl NIZKGens {
383 /// Constructs a new `NIZKGens` given the size of the R1CS statement
384 pub fn new(num_cons: usize, num_vars: usize) -> Self {
385 let gens_r1cs_sat = R1CSGens::new(b"gens_r1cs_sat", num_cons, num_vars);
386 NIZKGens { gens_r1cs_sat }
387 }
388}
389
390/// `NIZK` holds a proof produced by Spartan NIZK
391#[derive(Serialize, Deserialize, Debug)]
392pub struct NIZK {
393 r1cs_sat_proof: R1CSProof,
394 r: (Vec<Scalar>, Vec<Scalar>),
395}
396
397impl NIZK {
398 fn protocol_name() -> &'static [u8] {
399 b"Spartan NIZK proof"
400 }
401
402 /// A method to produce a NIZK proof of the satisfiability of an R1CS instance
403 pub fn prove(
404 inst: &Instance,
405 vars: VarsAssignment,
406 input: &InputsAssignment,
407 gens: &NIZKGens,
408 transcript: &mut Transcript,
409 ) -> Self {
410 let timer_prove = Timer::new("NIZK::prove");
411 // we create a Transcript object seeded with a random Scalar
412 // to aid the prover produce its randomness
413 let mut random_tape = RandomTape::new(b"proof");
414 transcript.append_protocol_name(NIZK::protocol_name());
415 let (r1cs_sat_proof, rx, ry) = {
416 let (proof, rx, ry) = R1CSProof::prove(
417 &inst.inst,
418 vars.assignment,
419 &input.assignment,
420 &gens.gens_r1cs_sat,
421 transcript,
422 &mut random_tape,
423 );
424 let proof_encoded: Vec<u8> = bincode::serialize(&proof).unwrap();
425 Timer::print(&format!("len_r1cs_sat_proof {:?}", proof_encoded.len()));
426 (proof, rx, ry)
427 };
428
429 timer_prove.stop();
430 NIZK {
431 r1cs_sat_proof,
432 r: (rx, ry),
433 }
434 }
435
436 /// A method to verify a NIZK proof of the satisfiability of an R1CS instance
437 pub fn verify(
438 &self,
439 inst: &Instance,
440 input: &InputsAssignment,
441 transcript: &mut Transcript,
442 gens: &NIZKGens,
443 ) -> Result<(), ProofVerifyError> {
444 let timer_verify = Timer::new("NIZK::verify");
445
446 transcript.append_protocol_name(NIZK::protocol_name());
447
448 // We send evaluations of A, B, C at r = (rx, ry) as claims
449 // to enable the verifier complete the first sum-check
450 let timer_eval = Timer::new("eval_sparse_polys");
451 let (claimed_rx, claimed_ry) = &self.r;
452 let inst_evals = inst.inst.evaluate(claimed_rx, claimed_ry);
453 timer_eval.stop();
454
455 let timer_sat_proof = Timer::new("verify_sat_proof");
456 assert_eq!(input.assignment.len(), inst.inst.get_num_inputs());
457 let (rx, ry) = self
458 .r1cs_sat_proof
459 .verify(
460 inst.inst.get_num_vars(),
461 inst.inst.get_num_cons(),
462 &input.assignment,
463 &inst_evals,
464 transcript,
465 &gens.gens_r1cs_sat,
466 )
467 .unwrap();
468
469 // verify if claimed rx and ry are correct
470 assert_eq!(rx, *claimed_rx);
471 assert_eq!(ry, *claimed_ry);
472 timer_sat_proof.stop();
473 timer_verify.stop();
474
475 Ok(())
476 }
477}
478
479#[cfg(test)]
480mod tests {
481 use super::*;
482
483 #[test]
484 pub fn check_snark() {
485 let num_vars = 256;
486 let num_cons = num_vars;
487 let num_inputs = 10;
488
489 // produce public generators
490 let gens = SNARKGens::new(num_cons, num_vars, num_inputs, num_cons);
491
492 // produce a synthetic R1CSInstance
493 let (inst, vars, inputs) = Instance::produce_synthetic_r1cs(num_cons, num_vars, num_inputs);
494
495 // create a commitment to R1CSInstance
496 let (comm, decomm) = SNARK::encode(&inst, &gens);
497
498 // produce a proof
499 let mut prover_transcript = Transcript::new(b"example");
500 let proof = SNARK::prove(&inst, &decomm, vars, &inputs, &gens, &mut prover_transcript);
501
502 // verify the proof
503 let mut verifier_transcript = Transcript::new(b"example");
504 assert!(proof
505 .verify(&comm, &inputs, &mut verifier_transcript, &gens)
506 .is_ok());
507 }
508
509 #[test]
510 pub fn check_r1cs_invalid_index() {
511 let num_cons = 4;
512 let num_vars = 8;
513 let num_inputs = 1;
514
515 let zero: [u8; 32] = [
516 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
517 0,
518 ];
519
520 let A = vec![(0, 0, zero)];
521 let B = vec![(100, 1, zero)];
522 let C = vec![(1, 1, zero)];
523
524 let inst = Instance::new(num_cons, num_vars, num_inputs, &A, &B, &C);
525 assert_eq!(inst.is_err(), true);
526 assert_eq!(inst.err(), Some(R1CSError::InvalidIndex));
527 }
528
529 #[test]
530 pub fn check_r1cs_invalid_scalar() {
531 let num_cons = 4;
532 let num_vars = 8;
533 let num_inputs = 1;
534
535 let zero: [u8; 32] = [
536 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
537 0,
538 ];
539
540 let larger_than_mod = [
541 3, 0, 0, 0, 255, 255, 255, 255, 254, 91, 254, 255, 2, 164, 189, 83, 5, 216, 161, 9, 8, 216,
542 57, 51, 72, 125, 157, 41, 83, 167, 237, 115,
543 ];
544
545 let A = vec![(0, 0, zero)];
546 let B = vec![(1, 1, larger_than_mod)];
547 let C = vec![(1, 1, zero)];
548
549 let inst = Instance::new(num_cons, num_vars, num_inputs, &A, &B, &C);
550 assert_eq!(inst.is_err(), true);
551 assert_eq!(inst.err(), Some(R1CSError::InvalidScalar));
552 }
553}