testudo/src/lib.rs
src/lib.rsRaw
1#![allow(non_snake_case)]
2#![doc = include_str!("../README.md")]
3#![deny(missing_docs)]
4#![feature(test)]
5#![allow(clippy::assertions_on_result_states)]
6
7extern crate ark_std;
8extern crate byteorder;
9extern crate core;
10extern crate digest;
11extern crate lazy_static;
12extern crate merlin;
13extern crate rand;
14extern crate sha3;
15extern crate test;
16
17#[macro_use]
18extern crate json;
19
20#[cfg(feature = "multicore")]
21extern crate rayon;
22
23mod commitments;
24mod dense_mlpoly;
25mod errors;
26mod group;
27mod math;
28mod nizk;
29mod product_tree;
30mod r1csinstance;
31mod r1csproof;
32mod random;
33mod scalar;
34mod sparse_mlpoly;
35mod sumcheck;
36mod timer;
37mod transcript;
38mod unipoly;
39
40/// TODO
41pub mod parameters;
42/// TODO
43pub mod poseidon_transcript;
44
45use ark_ff::{BigInteger, Field, PrimeField};
46use ark_serialize::*;
47use ark_std::{One, UniformRand, Zero};
48use core::cmp::max;
49use errors::{ProofVerifyError, R1CSError};
50use merlin::Transcript;
51use poseidon_transcript::{AppendToPoseidon, PoseidonTranscript};
52use r1csinstance::{
53 R1CSCommitment, R1CSCommitmentGens, R1CSDecommitment, R1CSEvalProof, R1CSInstance,
54};
55use r1csproof::{R1CSGens, R1CSProof};
56use random::RandomTape;
57use scalar::Scalar;
58use std::borrow::Borrow;
59use timer::Timer;
60use transcript::{AppendToTranscript, ProofTranscript};
61
62/// `ComputationCommitment` holds a public preprocessed NP statement (e.g., R1CS)
63pub struct ComputationCommitment {
64 comm: R1CSCommitment,
65}
66
67/// `ComputationDecommitment` holds information to decommit `ComputationCommitment`
68pub struct ComputationDecommitment {
69 decomm: R1CSDecommitment,
70}
71
72/// `Assignment` holds an assignment of values to either the inputs or variables in an `Instance`
73#[derive(Clone)]
74pub struct Assignment {
75 assignment: Vec<Scalar>,
76}
77
78impl Assignment {
79 /// Constructs a new `Assignment` from a vector
80 pub fn new(assignment: &Vec<Vec<u8>>) -> Result<Assignment, R1CSError> {
81 let bytes_to_scalar = |vec: &Vec<Vec<u8>>| -> Result<Vec<Scalar>, R1CSError> {
82 let mut vec_scalar: Vec<Scalar> = Vec::new();
83 for v in vec {
84 let val = Scalar::from_random_bytes(v.as_slice());
85 if val.is_some() == true {
86 vec_scalar.push(val.unwrap());
87 } else {
88 return Err(R1CSError::InvalidScalar);
89 }
90 }
91 Ok(vec_scalar)
92 };
93
94 let assignment_scalar = bytes_to_scalar(assignment);
95
96 // check for any parsing errors
97 if assignment_scalar.is_err() {
98 return Err(R1CSError::InvalidScalar);
99 }
100
101 Ok(Assignment {
102 assignment: assignment_scalar.unwrap(),
103 })
104 }
105
106 /// pads Assignment to the specified length
107 fn pad(&self, len: usize) -> VarsAssignment {
108 // check that the new length is higher than current length
109 assert!(len > self.assignment.len());
110
111 let padded_assignment = {
112 let mut padded_assignment = self.assignment.clone();
113 padded_assignment.extend(vec![Scalar::zero(); len - self.assignment.len()]);
114 padded_assignment
115 };
116
117 VarsAssignment {
118 assignment: padded_assignment,
119 }
120 }
121}
122
123/// `VarsAssignment` holds an assignment of values to variables in an `Instance`
124pub type VarsAssignment = Assignment;
125
126/// `InputsAssignment` holds an assignment of values to variables in an `Instance`
127pub type InputsAssignment = Assignment;
128
129/// `Instance` holds the description of R1CS matrices and a hash of the matrices
130#[derive(Debug)]
131pub struct Instance {
132 inst: R1CSInstance,
133 digest: Vec<u8>,
134}
135
136impl Instance {
137 /// Constructs a new `Instance` and an associated satisfying assignment
138 pub fn new(
139 num_cons: usize,
140 num_vars: usize,
141 num_inputs: usize,
142 A: &[(usize, usize, Vec<u8>)],
143 B: &[(usize, usize, Vec<u8>)],
144 C: &[(usize, usize, Vec<u8>)],
145 ) -> Result<Instance, R1CSError> {
146 let (num_vars_padded, num_cons_padded) = {
147 let num_vars_padded = {
148 let mut num_vars_padded = num_vars;
149
150 // ensure that num_inputs + 1 <= num_vars
151 num_vars_padded = max(num_vars_padded, num_inputs + 1);
152
153 // ensure that num_vars_padded a power of two
154 if num_vars_padded.next_power_of_two() != num_vars_padded {
155 num_vars_padded = num_vars_padded.next_power_of_two();
156 }
157 num_vars_padded
158 };
159
160 let num_cons_padded = {
161 let mut num_cons_padded = num_cons;
162
163 // ensure that num_cons_padded is at least 2
164 if num_cons_padded == 0 || num_cons_padded == 1 {
165 num_cons_padded = 2;
166 }
167
168 // ensure that num_cons_padded is power of 2
169 if num_cons.next_power_of_two() != num_cons {
170 num_cons_padded = num_cons.next_power_of_two();
171 }
172 num_cons_padded
173 };
174
175 (num_vars_padded, num_cons_padded)
176 };
177
178 let bytes_to_scalar =
179 |tups: &[(usize, usize, Vec<u8>)]| -> Result<Vec<(usize, usize, Scalar)>, R1CSError> {
180 let mut mat: Vec<(usize, usize, Scalar)> = Vec::new();
181 for (row, col, val_bytes) in tups {
182 // row must be smaller than num_cons
183 if *row >= num_cons {
184 return Err(R1CSError::InvalidIndex);
185 }
186
187 // col must be smaller than num_vars + 1 + num_inputs
188 if *col >= num_vars + 1 + num_inputs {
189 return Err(R1CSError::InvalidIndex);
190 }
191
192 let val = Scalar::from_random_bytes(&val_bytes.as_slice());
193 if val.is_some() == true {
194 // if col >= num_vars, it means that it is referencing a 1 or input in the satisfying
195 // assignment
196 if *col >= num_vars {
197 mat.push((*row, *col + num_vars_padded - num_vars, val.unwrap()));
198 } else {
199 mat.push((*row, *col, val.unwrap()));
200 }
201 } else {
202 return Err(R1CSError::InvalidScalar);
203 }
204 }
205
206 // pad with additional constraints up until num_cons_padded if the original constraints were 0 or 1
207 // we do not need to pad otherwise because the dummy constraints are implicit in the sum-check protocol
208 if num_cons == 0 || num_cons == 1 {
209 for i in tups.len()..num_cons_padded {
210 mat.push((i, num_vars, Scalar::zero()));
211 }
212 }
213
214 Ok(mat)
215 };
216
217 let A_scalar = bytes_to_scalar(A);
218 if A_scalar.is_err() {
219 return Err(A_scalar.err().unwrap());
220 }
221
222 let B_scalar = bytes_to_scalar(B);
223 if B_scalar.is_err() {
224 return Err(B_scalar.err().unwrap());
225 }
226
227 let C_scalar = bytes_to_scalar(C);
228 if C_scalar.is_err() {
229 return Err(C_scalar.err().unwrap());
230 }
231
232 let inst = R1CSInstance::new(
233 num_cons_padded,
234 num_vars_padded,
235 num_inputs,
236 &A_scalar.unwrap(),
237 &B_scalar.unwrap(),
238 &C_scalar.unwrap(),
239 );
240
241 let digest = inst.get_digest();
242
243 Ok(Instance { inst, digest })
244 }
245
246 /// Checks if a given R1CSInstance is satisfiable with a given variables and inputs assignments
247 pub fn is_sat(
248 &self,
249 vars: &VarsAssignment,
250 inputs: &InputsAssignment,
251 ) -> Result<bool, R1CSError> {
252 if vars.assignment.len() > self.inst.get_num_vars() {
253 return Err(R1CSError::InvalidNumberOfInputs);
254 }
255
256 if inputs.assignment.len() != self.inst.get_num_inputs() {
257 return Err(R1CSError::InvalidNumberOfInputs);
258 }
259
260 // we might need to pad variables
261 let padded_vars = {
262 let num_padded_vars = self.inst.get_num_vars();
263 let num_vars = vars.assignment.len();
264 if num_padded_vars > num_vars {
265 vars.pad(num_padded_vars)
266 } else {
267 vars.clone()
268 }
269 };
270
271 Ok(
272 self
273 .inst
274 .is_sat(&padded_vars.assignment, &inputs.assignment),
275 )
276 }
277
278 /// Constructs a new synthetic R1CS `Instance` and an associated satisfying assignment
279 pub fn produce_synthetic_r1cs(
280 num_cons: usize,
281 num_vars: usize,
282 num_inputs: usize,
283 ) -> (Instance, VarsAssignment, InputsAssignment) {
284 let (inst, vars, inputs) = R1CSInstance::produce_synthetic_r1cs(num_cons, num_vars, num_inputs);
285 let digest = inst.get_digest();
286 (
287 Instance { inst, digest },
288 VarsAssignment { assignment: vars },
289 InputsAssignment { assignment: inputs },
290 )
291 }
292}
293
294/// `SNARKGens` holds public parameters for producing and verifying proofs with the Spartan SNARK
295pub struct SNARKGens {
296 gens_r1cs_sat: R1CSGens,
297 gens_r1cs_eval: R1CSCommitmentGens,
298}
299
300impl SNARKGens {
301 /// Constructs a new `SNARKGens` given the size of the R1CS statement
302 /// `num_nz_entries` specifies the maximum number of non-zero entries in any of the three R1CS matrices
303 pub fn new(num_cons: usize, num_vars: usize, num_inputs: usize, num_nz_entries: usize) -> Self {
304 let num_vars_padded = {
305 let mut num_vars_padded = max(num_vars, num_inputs + 1);
306 if num_vars_padded != num_vars_padded.next_power_of_two() {
307 num_vars_padded = num_vars_padded.next_power_of_two();
308 }
309 num_vars_padded
310 };
311
312 let gens_r1cs_sat = R1CSGens::new(b"gens_r1cs_sat", num_cons, num_vars_padded);
313 let gens_r1cs_eval = R1CSCommitmentGens::new(
314 b"gens_r1cs_eval",
315 num_cons,
316 num_vars_padded,
317 num_inputs,
318 num_nz_entries,
319 );
320 SNARKGens {
321 gens_r1cs_sat,
322 gens_r1cs_eval,
323 }
324 }
325}
326
327/// `SNARK` holds a proof produced by Spartan SNARK
328#[derive(CanonicalSerialize, CanonicalDeserialize, Debug)]
329pub struct SNARK {
330 r1cs_sat_proof: R1CSProof,
331 inst_evals: (Scalar, Scalar, Scalar),
332 r1cs_eval_proof: R1CSEvalProof,
333}
334
335impl SNARK {
336 fn protocol_name() -> &'static [u8] {
337 b"Spartan SNARK proof"
338 }
339
340 /// A public computation to create a commitment to an R1CS instance
341 pub fn encode(
342 inst: &Instance,
343 gens: &SNARKGens,
344 ) -> (ComputationCommitment, ComputationDecommitment) {
345 let timer_encode = Timer::new("SNARK::encode");
346 let (comm, decomm) = inst.inst.commit(&gens.gens_r1cs_eval);
347 timer_encode.stop();
348 (
349 ComputationCommitment { comm },
350 ComputationDecommitment { decomm },
351 )
352 }
353
354 /// A method to produce a SNARK proof of the satisfiability of an R1CS instance
355 pub fn prove(
356 inst: &Instance,
357 comm: &ComputationCommitment,
358 decomm: &ComputationDecommitment,
359 vars: VarsAssignment,
360 inputs: &InputsAssignment,
361 gens: &SNARKGens,
362 transcript: &mut PoseidonTranscript,
363 ) -> Self {
364 let timer_prove = Timer::new("SNARK::prove");
365
366 // we create a Transcript object seeded with a random Scalar
367 // to aid the prover produce its randomness
368 let mut random_tape = RandomTape::new(b"proof");
369
370 // transcript.append_protocol_name(SNARK::protocol_name());
371 comm.comm.append_to_poseidon(transcript);
372
373 let (r1cs_sat_proof, rx, ry) = {
374 let (proof, rx, ry) = {
375 // we might need to pad variables
376 let padded_vars = {
377 let num_padded_vars = inst.inst.get_num_vars();
378 let num_vars = vars.assignment.len();
379 if num_padded_vars > num_vars {
380 vars.pad(num_padded_vars)
381 } else {
382 vars
383 }
384 };
385
386 R1CSProof::prove(
387 &inst.inst,
388 padded_vars.assignment,
389 &inputs.assignment,
390 &gens.gens_r1cs_sat,
391 transcript,
392 &mut random_tape,
393 )
394 };
395
396 let mut proof_encoded: Vec<u8> = Vec::new();
397 proof.serialize(&mut proof_encoded).unwrap();
398 Timer::print(&format!("len_r1cs_sat_proof {:?}", proof_encoded.len()));
399
400 (proof, rx, ry)
401 };
402
403 // We send evaluations of A, B, C at r = (rx, ry) as claims
404 // to enable the verifier complete the first sum-check
405 let timer_eval = Timer::new("eval_sparse_polys");
406 let inst_evals = {
407 let (Ar, Br, Cr) = inst.inst.evaluate(&rx, &ry);
408 transcript.append_scalar(&Ar);
409 transcript.append_scalar(&Br);
410 transcript.append_scalar(&Cr);
411 (Ar, Br, Cr)
412 };
413 timer_eval.stop();
414
415 let r1cs_eval_proof = {
416 let proof = R1CSEvalProof::prove(
417 &decomm.decomm,
418 &rx,
419 &ry,
420 &inst_evals,
421 &gens.gens_r1cs_eval,
422 transcript,
423 &mut random_tape,
424 );
425
426 let mut proof_encoded: Vec<u8> = Vec::new();
427 proof.serialize(&mut proof_encoded).unwrap();
428 Timer::print(&format!("len_r1cs_eval_proof {:?}", proof_encoded.len()));
429 proof
430 };
431
432 timer_prove.stop();
433 SNARK {
434 r1cs_sat_proof,
435 inst_evals,
436 r1cs_eval_proof,
437 }
438 }
439
440 /// A method to verify the SNARK proof of the satisfiability of an R1CS instance
441 pub fn verify(
442 &self,
443 comm: &ComputationCommitment,
444 input: &InputsAssignment,
445 transcript: &mut PoseidonTranscript,
446 gens: &SNARKGens,
447 ) -> Result<(), ProofVerifyError> {
448 let timer_verify = Timer::new("SNARK::verify");
449 // transcript.append_protocol_name(SNARK::protocol_name());
450
451 // append a commitment to the computation to the transcript
452 comm.comm.append_to_poseidon(transcript);
453
454 let timer_sat_proof = Timer::new("verify_sat_proof");
455 assert_eq!(input.assignment.len(), comm.comm.get_num_inputs());
456 let (rx, ry) = self.r1cs_sat_proof.verify(
457 comm.comm.get_num_vars(),
458 comm.comm.get_num_cons(),
459 &input.assignment,
460 &self.inst_evals,
461 transcript,
462 &gens.gens_r1cs_sat,
463 )?;
464 timer_sat_proof.stop();
465
466 let timer_eval_proof = Timer::new("verify_eval_proof");
467 let (Ar, Br, Cr) = &self.inst_evals;
468 // Ar.append_to_transcript(b"Ar_claim", transcript);
469 // Br.append_to_transcript(b"Br_claim", transcript);
470 // Cr.append_to_transcript(b"Cr_claim", transcript);
471 transcript.append_scalar(&Ar);
472 transcript.append_scalar(&Br);
473 transcript.append_scalar(&Cr);
474 self.r1cs_eval_proof.verify(
475 &comm.comm,
476 &rx,
477 &ry,
478 &self.inst_evals,
479 &gens.gens_r1cs_eval,
480 transcript,
481 )?;
482 timer_eval_proof.stop();
483 timer_verify.stop();
484 Ok(())
485 }
486}
487
488/// `NIZKGens` holds public parameters for producing and verifying proofs with the Spartan NIZK
489pub struct NIZKGens {
490 gens_r1cs_sat: R1CSGens,
491}
492
493impl NIZKGens {
494 /// Constructs a new `NIZKGens` given the size of the R1CS statement
495 pub fn new(num_cons: usize, num_vars: usize, num_inputs: usize) -> Self {
496 let num_vars_padded = {
497 let mut num_vars_padded = max(num_vars, num_inputs + 1);
498 if num_vars_padded != num_vars_padded.next_power_of_two() {
499 num_vars_padded = num_vars_padded.next_power_of_two();
500 }
501 num_vars_padded
502 };
503
504 let gens_r1cs_sat = R1CSGens::new(b"gens_r1cs_sat", num_cons, num_vars_padded);
505 NIZKGens { gens_r1cs_sat }
506 }
507}
508
509/// `NIZK` holds a proof produced by Spartan NIZK
510#[derive(CanonicalSerialize, CanonicalDeserialize, Debug)]
511pub struct NIZK {
512 r1cs_sat_proof: R1CSProof,
513 r: (Vec<Scalar>, Vec<Scalar>),
514}
515
516impl NIZK {
517 fn protocol_name() -> &'static [u8] {
518 b"Spartan NIZK proof"
519 }
520
521 /// A method to produce a NIZK proof of the satisfiability of an R1CS instance
522 pub fn prove(
523 inst: &Instance,
524 vars: VarsAssignment,
525 input: &InputsAssignment,
526 gens: &NIZKGens,
527 transcript: &mut PoseidonTranscript,
528 ) -> Self {
529 let timer_prove = Timer::new("NIZK::prove");
530 // we create a Transcript object seeded with a random Scalar
531 // to aid the prover produce its randomness
532 let mut random_tape = RandomTape::new(b"proof");
533
534<<<<<<< HEAD
535 transcript.append_protocol_name(NIZK::protocol_name());
536 transcript.append_message(b"R1CSInstanceDigest", &inst.digest);
537=======
538 // transcript.append_protocol_name(NIZK::protocol_name());
539 inst.inst.append_to_poseidon(transcript);
540>>>>>>> simplify transcript and change merlin backend to poseidon
541
542 let (r1cs_sat_proof, rx, ry) = {
543 // we might need to pad variables
544 let padded_vars = {
545 let num_padded_vars = inst.inst.get_num_vars();
546 let num_vars = vars.assignment.len();
547 if num_padded_vars > num_vars {
548 vars.pad(num_padded_vars)
549 } else {
550 vars
551 }
552 };
553
554 let (proof, rx, ry) = R1CSProof::prove(
555 &inst.inst,
556 padded_vars.assignment,
557 &input.assignment,
558 &gens.gens_r1cs_sat,
559 transcript,
560 &mut random_tape,
561 );
562 let mut proof_encoded = Vec::new();
563 proof.serialize(&mut proof_encoded).unwrap();
564 Timer::print(&format!("len_r1cs_sat_proof {:?}", proof_encoded.len()));
565 (proof, rx, ry)
566 };
567
568 timer_prove.stop();
569 NIZK {
570 r1cs_sat_proof,
571 r: (rx, ry),
572 }
573 }
574
575 /// A method to verify a NIZK proof of the satisfiability of an R1CS instance
576 pub fn verify(
577 &self,
578 inst: &Instance,
579 input: &InputsAssignment,
580 transcript: &mut PoseidonTranscript,
581 gens: &NIZKGens,
582 ) -> Result<(), ProofVerifyError> {
583 let timer_verify = Timer::new("NIZK::verify");
584
585<<<<<<< HEAD
586 transcript.append_protocol_name(NIZK::protocol_name());
587 transcript.append_message(b"R1CSInstanceDigest", &inst.digest);
588=======
589 // transcript.append_protocol_name(NIZK::protocol_name());
590 inst.inst.append_to_poseidon(transcript);
591>>>>>>> simplify transcript and change merlin backend to poseidon
592
593 // We send evaluations of A, B, C at r = (rx, ry) as claims
594 // to enable the verifier complete the first sum-check
595 let timer_eval = Timer::new("eval_sparse_polys");
596 let (claimed_rx, claimed_ry) = &self.r;
597 let inst_evals = inst.inst.evaluate(claimed_rx, claimed_ry);
598 timer_eval.stop();
599
600 let timer_sat_proof = Timer::new("verify_sat_proof");
601 assert_eq!(input.assignment.len(), inst.inst.get_num_inputs());
602 let (rx, ry) = self.r1cs_sat_proof.verify(
603 inst.inst.get_num_vars(),
604 inst.inst.get_num_cons(),
605 &input.assignment,
606 &inst_evals,
607 transcript,
608 &gens.gens_r1cs_sat,
609 )?;
610
611 // verify if claimed rx and ry are correct
612 assert_eq!(rx, *claimed_rx);
613 assert_eq!(ry, *claimed_ry);
614 timer_sat_proof.stop();
615 timer_verify.stop();
616
617 Ok(())
618 }
619}
620
621#[cfg(test)]
622mod tests {
623 use crate::parameters::poseidon_params;
624
625 use super::*;
626 use ark_ff::PrimeField;
627
628 #[test]
629 pub fn check_snark() {
630 let num_vars = 256;
631 let num_cons = num_vars;
632 let num_inputs = 10;
633
634 // produce public generators
635 let gens = SNARKGens::new(num_cons, num_vars, num_inputs, num_cons);
636
637 // produce a synthetic R1CSInstance
638 let (inst, vars, inputs) = Instance::produce_synthetic_r1cs(num_cons, num_vars, num_inputs);
639
640 // create a commitment to R1CSInstance
641 let (comm, decomm) = SNARK::encode(&inst, &gens);
642
643 let params = poseidon_params();
644
645 // produce a proof
646 let mut prover_transcript = PoseidonTranscript::new(¶ms);
647 let proof = SNARK::prove(
648 &inst,
649 &comm,
650 &decomm,
651 vars,
652 &inputs,
653 &gens,
654 &mut prover_transcript,
655 );
656
657 // verify the proof
658 let mut verifier_transcript = PoseidonTranscript::new(¶ms);
659 assert!(proof
660 .verify(&comm, &inputs, &mut verifier_transcript, &gens)
661 .is_ok());
662 }
663
664 #[test]
665 pub fn check_r1cs_invalid_index() {
666 let num_cons = 4;
667 let num_vars = 8;
668 let num_inputs = 1;
669
670 let zero: [u8; 32] = [
671 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,
672 0,
673 ];
674
675 let A = vec![(0, 0, zero.to_vec())];
676 let B = vec![(100, 1, zero.to_vec())];
677 let C = vec![(1, 1, zero.to_vec())];
678
679 let inst = Instance::new(num_cons, num_vars, num_inputs, &A, &B, &C);
680 assert!(inst.is_err());
681 assert_eq!(inst.err(), Some(R1CSError::InvalidIndex));
682 }
683
684 #[test]
685 pub fn check_r1cs_invalid_scalar() {
686 let num_cons = 4;
687 let num_vars = 8;
688 let num_inputs = 1;
689
690 let zero: [u8; 32] = [
691 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,
692 0,
693 ];
694
695 let larger_than_mod = [
696 3, 0, 0, 0, 255, 255, 255, 255, 254, 91, 254, 255, 2, 164, 189, 83, 5, 216, 161, 9, 8, 216,
697 57, 51, 72, 125, 157, 41, 83, 167, 237, 115,
698 ];
699
700 let A = vec![(0, 0, zero.to_vec())];
701 let B = vec![(1, 1, larger_than_mod.to_vec())];
702 let C = vec![(1, 1, zero.to_vec())];
703
704 let inst = Instance::new(num_cons, num_vars, num_inputs, &A, &B, &C);
705 assert!(inst.is_err());
706 assert_eq!(inst.err(), Some(R1CSError::InvalidScalar));
707 }
708
709 #[test]
710 fn test_padded_constraints() {
711 // parameters of the R1CS instance
712 let num_cons = 1;
713 let num_vars = 0;
714 let num_inputs = 3;
715 let num_non_zero_entries = 3;
716
717 // We will encode the above constraints into three matrices, where
718 // the coefficients in the matrix are in the little-endian byte order
719 let mut A: Vec<(usize, usize, Vec<u8>)> = Vec::new();
720 let mut B: Vec<(usize, usize, Vec<u8>)> = Vec::new();
721 let mut C: Vec<(usize, usize, Vec<u8>)> = Vec::new();
722
723 // Create a^2 + b + 13
724 A.push((0, num_vars + 2, (Scalar::one().into_repr().to_bytes_le()))); // 1*a
725 B.push((0, num_vars + 2, Scalar::one().into_repr().to_bytes_le())); // 1*a
726 C.push((0, num_vars + 1, Scalar::one().into_repr().to_bytes_le())); // 1*z
727 C.push((
728 0,
729 num_vars,
730 (-Scalar::from(13u64)).into_repr().to_bytes_le(),
731 )); // -13*1
732 C.push((0, num_vars + 3, (-Scalar::one()).into_repr().to_bytes_le())); // -1*b
733
734 // Var Assignments (Z_0 = 16 is the only output)
735 let vars = vec![Scalar::zero().into_repr().to_bytes_le(); num_vars];
736
737 // create an InputsAssignment (a = 1, b = 2)
738 let mut inputs = vec![Scalar::zero().into_repr().to_bytes_le(); num_inputs];
739 inputs[0] = Scalar::from(16u64).into_repr().to_bytes_le();
740 inputs[1] = Scalar::from(1u64).into_repr().to_bytes_le();
741 inputs[2] = Scalar::from(2u64).into_repr().to_bytes_le();
742
743 let assignment_inputs = InputsAssignment::new(&inputs).unwrap();
744 let assignment_vars = VarsAssignment::new(&vars).unwrap();
745
746 // Check if instance is satisfiable
747 let inst = Instance::new(num_cons, num_vars, num_inputs, &A, &B, &C).unwrap();
748 let res = inst.is_sat(&assignment_vars, &assignment_inputs);
749 assert!(res.unwrap(), "should be satisfied");
750
751 // SNARK public params
752 let gens = SNARKGens::new(num_cons, num_vars, num_inputs, num_non_zero_entries);
753
754 // create a commitment to the R1CS instance
755 let (comm, decomm) = SNARK::encode(&inst, &gens);
756
757 let params = poseidon_params();
758
759 // produce a SNARK
760 let mut prover_transcript = PoseidonTranscript::new(¶ms);
761 let proof = SNARK::prove(
762 &inst,
763 &comm,
764 &decomm,
765 assignment_vars.clone(),
766 &assignment_inputs,
767 &gens,
768 &mut prover_transcript,
769 );
770
771 // verify the SNARK
772 let mut verifier_transcript = PoseidonTranscript::new(¶ms);
773 assert!(proof
774 .verify(&comm, &assignment_inputs, &mut verifier_transcript, &gens)
775 .is_ok());
776
777 // NIZK public params
778 let gens = NIZKGens::new(num_cons, num_vars, num_inputs);
779
780 let params = poseidon_params();
781
782 // produce a NIZK
783 let mut prover_transcript = PoseidonTranscript::new(¶ms);
784 let proof = NIZK::prove(
785 &inst,
786 assignment_vars,
787 &assignment_inputs,
788 &gens,
789 &mut prover_transcript,
790 );
791
792 // verify the NIZK
793 let mut verifier_transcript = PoseidonTranscript::new(¶ms);
794 assert!(proof
795 .verify(&inst, &assignment_inputs, &mut verifier_transcript, &gens)
796 .is_ok());
797 }
798}