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