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.r1cs_sat_proof.verify(
343 comm.comm.get_num_vars(),
344 comm.comm.get_num_cons(),
345 &input.assignment,
346 &self.inst_evals,
347 transcript,
348 &gens.gens_r1cs_sat,
349 )?;
350 timer_sat_proof.stop();
351
352 let timer_eval_proof = Timer::new("verify_eval_proof");
353 let (Ar, Br, Cr) = &self.inst_evals;
354 Ar.append_to_transcript(b"Ar_claim", transcript);
355 Br.append_to_transcript(b"Br_claim", transcript);
356 Cr.append_to_transcript(b"Cr_claim", transcript);
357 assert!(self
358 .r1cs_eval_proof
359 .verify(
360 &comm.comm,
361 &rx,
362 &ry,
363 &self.inst_evals,
364 &gens.gens_r1cs_eval,
365 transcript
366 )
367 .is_ok());
368 timer_eval_proof.stop();
369 timer_verify.stop();
370 Ok(())
371 }
372}
373
374/// `NIZKGens` holds public parameters for producing and verifying proofs with the Spartan NIZK
375pub struct NIZKGens {
376 gens_r1cs_sat: R1CSGens,
377}
378
379impl NIZKGens {
380 /// Constructs a new `NIZKGens` given the size of the R1CS statement
381 pub fn new(num_cons: usize, num_vars: usize) -> Self {
382 let gens_r1cs_sat = R1CSGens::new(b"gens_r1cs_sat", num_cons, num_vars);
383 NIZKGens { gens_r1cs_sat }
384 }
385}
386
387/// `NIZK` holds a proof produced by Spartan NIZK
388#[derive(Serialize, Deserialize, Debug)]
389pub struct NIZK {
390 r1cs_sat_proof: R1CSProof,
391 r: (Vec<Scalar>, Vec<Scalar>),
392}
393
394impl NIZK {
395 fn protocol_name() -> &'static [u8] {
396 b"Spartan NIZK proof"
397 }
398
399 /// A method to produce a NIZK proof of the satisfiability of an R1CS instance
400 pub fn prove(
401 inst: &Instance,
402 vars: VarsAssignment,
403 input: &InputsAssignment,
404 gens: &NIZKGens,
405 transcript: &mut Transcript,
406 ) -> Self {
407 let timer_prove = Timer::new("NIZK::prove");
408 // we create a Transcript object seeded with a random Scalar
409 // to aid the prover produce its randomness
410 let mut random_tape = RandomTape::new(b"proof");
411 transcript.append_protocol_name(NIZK::protocol_name());
412 let (r1cs_sat_proof, rx, ry) = {
413 let (proof, rx, ry) = R1CSProof::prove(
414 &inst.inst,
415 vars.assignment,
416 &input.assignment,
417 &gens.gens_r1cs_sat,
418 transcript,
419 &mut random_tape,
420 );
421 let proof_encoded: Vec<u8> = bincode::serialize(&proof).unwrap();
422 Timer::print(&format!("len_r1cs_sat_proof {:?}", proof_encoded.len()));
423 (proof, rx, ry)
424 };
425
426 timer_prove.stop();
427 NIZK {
428 r1cs_sat_proof,
429 r: (rx, ry),
430 }
431 }
432
433 /// A method to verify a NIZK proof of the satisfiability of an R1CS instance
434 pub fn verify(
435 &self,
436 inst: &Instance,
437 input: &InputsAssignment,
438 transcript: &mut Transcript,
439 gens: &NIZKGens,
440 ) -> Result<(), ProofVerifyError> {
441 let timer_verify = Timer::new("NIZK::verify");
442
443 transcript.append_protocol_name(NIZK::protocol_name());
444
445 // We send evaluations of A, B, C at r = (rx, ry) as claims
446 // to enable the verifier complete the first sum-check
447 let timer_eval = Timer::new("eval_sparse_polys");
448 let (claimed_rx, claimed_ry) = &self.r;
449 let inst_evals = inst.inst.evaluate(claimed_rx, claimed_ry);
450 timer_eval.stop();
451
452 let timer_sat_proof = Timer::new("verify_sat_proof");
453 assert_eq!(input.assignment.len(), inst.inst.get_num_inputs());
454 let (rx, ry) = self.r1cs_sat_proof.verify(
455 inst.inst.get_num_vars(),
456 inst.inst.get_num_cons(),
457 &input.assignment,
458 &inst_evals,
459 transcript,
460 &gens.gens_r1cs_sat,
461 )?;
462
463 // verify if claimed rx and ry are correct
464 assert_eq!(rx, *claimed_rx);
465 assert_eq!(ry, *claimed_ry);
466 timer_sat_proof.stop();
467 timer_verify.stop();
468
469 Ok(())
470 }
471}
472
473#[cfg(test)]
474mod tests {
475 use super::*;
476
477 #[test]
478 pub fn check_snark() {
479 let num_vars = 256;
480 let num_cons = num_vars;
481 let num_inputs = 10;
482
483 // produce public generators
484 let gens = SNARKGens::new(num_cons, num_vars, num_inputs, num_cons);
485
486 // produce a synthetic R1CSInstance
487 let (inst, vars, inputs) = Instance::produce_synthetic_r1cs(num_cons, num_vars, num_inputs);
488
489 // create a commitment to R1CSInstance
490 let (comm, decomm) = SNARK::encode(&inst, &gens);
491
492 // produce a proof
493 let mut prover_transcript = Transcript::new(b"example");
494 let proof = SNARK::prove(&inst, &decomm, vars, &inputs, &gens, &mut prover_transcript);
495
496 // verify the proof
497 let mut verifier_transcript = Transcript::new(b"example");
498 assert!(proof
499 .verify(&comm, &inputs, &mut verifier_transcript, &gens)
500 .is_ok());
501 }
502
503 #[test]
504 pub fn check_r1cs_invalid_index() {
505 let num_cons = 4;
506 let num_vars = 8;
507 let num_inputs = 1;
508
509 let zero: [u8; 32] = [
510 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,
511 0,
512 ];
513
514 let A = vec![(0, 0, zero)];
515 let B = vec![(100, 1, zero)];
516 let C = vec![(1, 1, zero)];
517
518 let inst = Instance::new(num_cons, num_vars, num_inputs, &A, &B, &C);
519 assert_eq!(inst.is_err(), true);
520 assert_eq!(inst.err(), Some(R1CSError::InvalidIndex));
521 }
522
523 #[test]
524 pub fn check_r1cs_invalid_scalar() {
525 let num_cons = 4;
526 let num_vars = 8;
527 let num_inputs = 1;
528
529 let zero: [u8; 32] = [
530 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,
531 0,
532 ];
533
534 let larger_than_mod = [
535 3, 0, 0, 0, 255, 255, 255, 255, 254, 91, 254, 255, 2, 164, 189, 83, 5, 216, 161, 9, 8, 216,
536 57, 51, 72, 125, 157, 41, 83, 167, 237, 115,
537 ];
538
539 let A = vec![(0, 0, zero)];
540 let B = vec![(1, 1, larger_than_mod)];
541 let C = vec![(1, 1, zero)];
542
543 let inst = Instance::new(num_cons, num_vars, num_inputs, &A, &B, &C);
544 assert_eq!(inst.is_err(), true);
545 assert_eq!(inst.err(), Some(R1CSError::InvalidScalar));
546 }
547}