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}
332
333impl SNARK {
334 fn protocol_name() -> &'static [u8] {
335 b"Spartan SNARK proof"
336 }
337
338 /// A public computation to create a commitment to an R1CS instance
339 pub fn encode(
340 inst: &Instance,
341 gens: &SNARKGens,
342 ) -> (ComputationCommitment, ComputationDecommitment) {
343 let timer_encode = Timer::new("SNARK::encode");
344 let (comm, decomm) = inst.inst.commit(&gens.gens_r1cs_eval);
345 timer_encode.stop();
346 (
347 ComputationCommitment { comm },
348 ComputationDecommitment { decomm },
349 )
350 }
351
352 /// A method to produce a SNARK proof of the satisfiability of an R1CS instance
353 pub fn prove(
354 inst: &Instance,
355 comm: &ComputationCommitment,
356 decomm: &ComputationDecommitment,
357 vars: VarsAssignment,
358 inputs: &InputsAssignment,
359 gens: &SNARKGens,
360 transcript: &mut PoseidonTranscript,
361 ) -> Self {
362 let timer_prove = Timer::new("SNARK::prove");
363
364 // we create a Transcript object seeded with a random Scalar
365 // to aid the prover produce its randomness
366 let mut random_tape = RandomTape::new(b"proof");
367
368 // transcript.append_protocol_name(SNARK::protocol_name());
369 comm.comm.append_to_poseidon(transcript);
370
371 let (r1cs_sat_proof, rx, ry) = {
372 let (proof, rx, ry) = {
373 // we might need to pad variables
374 let padded_vars = {
375 let num_padded_vars = inst.inst.get_num_vars();
376 let num_vars = vars.assignment.len();
377 if num_padded_vars > num_vars {
378 vars.pad(num_padded_vars)
379 } else {
380 vars
381 }
382 };
383
384 R1CSProof::prove(
385 &inst.inst,
386 padded_vars.assignment,
387 &inputs.assignment,
388 // &gens.gens_r1cs_sat,
389 transcript,
390 // &mut random_tape,
391 )
392 };
393
394 let mut proof_encoded: Vec<u8> = Vec::new();
395 proof.serialize(&mut proof_encoded).unwrap();
396 Timer::print(&format!("len_r1cs_sat_proof {:?}", proof_encoded.len()));
397
398 (proof, rx, ry)
399 };
400
401 // We send evaluations of A, B, C at r = (rx, ry) as claims
402 // to enable the verifier complete the first sum-check
403 let timer_eval = Timer::new("eval_sparse_polys");
404 let inst_evals = {
405 let (Ar, Br, Cr) = inst.inst.evaluate(&rx, &ry);
406 transcript.append_scalar(&Ar);
407 transcript.append_scalar(&Br);
408 transcript.append_scalar(&Cr);
409 (Ar, Br, Cr)
410 };
411 timer_eval.stop();
412
413 let r1cs_eval_proof = {
414 let proof = R1CSEvalProof::prove(
415 &decomm.decomm,
416 &rx,
417 &ry,
418 &inst_evals,
419 &gens.gens_r1cs_eval,
420 transcript,
421 &mut random_tape,
422 );
423
424 let mut proof_encoded: Vec<u8> = Vec::new();
425 proof.serialize(&mut proof_encoded).unwrap();
426 Timer::print(&format!("len_r1cs_eval_proof {:?}", proof_encoded.len()));
427 proof
428 };
429
430 timer_prove.stop();
431 SNARK {
432 r1cs_sat_proof,
433 inst_evals,
434 r1cs_eval_proof,
435 }
436 }
437
438 /// A method to verify the SNARK proof of the satisfiability of an R1CS instance
439 pub fn verify(
440 &self,
441 comm: &ComputationCommitment,
442 input: &InputsAssignment,
443 transcript: &mut PoseidonTranscript,
444 _gens: &SNARKGens,
445 ) -> Result<(), ProofVerifyError> {
446 let _timer_verify = Timer::new("SNARK::verify");
447 // transcript.append_protocol_name(SNARK::protocol_name());
448
449 // append a commitment to the computation to the transcript
450 comm.comm.append_to_poseidon(transcript);
451
452 let timer_sat_proof = Timer::new("verify_sat_proof");
453 assert_eq!(input.assignment.len(), comm.comm.get_num_inputs());
454 // let (rx, ry) =
455 self.r1cs_sat_proof.circuit_size(
456 comm.comm.get_num_vars(),
457 comm.comm.get_num_cons(),
458 &input.assignment,
459 &self.inst_evals,
460 transcript,
461 // &gens.gens_r1cs_sat,
462 )?;
463 timer_sat_proof.stop();
464
465 // let timer_eval_proof = Timer::new("verify_eval_proof");
466 // let (Ar, Br, Cr) = &self.inst_evals;
467 // // Ar.append_to_transcript(b"Ar_claim", transcript);
468 // // Br.append_to_transcript(b"Br_claim", transcript);
469 // // Cr.append_to_transcript(b"Cr_claim", transcript);
470 // transcript.append_scalar(&Ar);
471 // transcript.append_scalar(&Br);
472 // transcript.append_scalar(&Cr);
473 // self.r1cs_eval_proof.verify(
474 // &comm.comm,
475 // &rx,
476 // &ry,
477 // &self.inst_evals,
478 // &gens.gens_r1cs_eval,
479 // transcript,
480 // )?;
481 // timer_eval_proof.stop();
482 // timer_verify.stop();
483 Ok(())
484 }
485}
486
487#[derive(Clone)]
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 _random_tape = RandomTape::new(b"proof");
533
534 // transcript.append_protocol_name(NIZK::protocol_name());
535 transcript.append_bytes(&inst.digest);
536
537 let (r1cs_sat_proof, rx, ry) = {
538 // we might need to pad variables
539 let padded_vars = {
540 let num_padded_vars = inst.inst.get_num_vars();
541 let num_vars = vars.assignment.len();
542 if num_padded_vars > num_vars {
543 vars.pad(num_padded_vars)
544 } else {
545 vars
546 }
547 };
548
549 let (proof, rx, ry) = R1CSProof::prove(
550 &inst.inst,
551 padded_vars.assignment,
552 &input.assignment,
553 // &gens.gens_r1cs_sat,
554 transcript,
555 // &mut random_tape,
556 );
557 let mut proof_encoded = Vec::new();
558 proof.serialize(&mut proof_encoded).unwrap();
559 Timer::print(&format!("len_r1cs_sat_proof {:?}", proof_encoded.len()));
560 (proof, rx, ry)
561 };
562
563 timer_prove.stop();
564 NIZK {
565 r1cs_sat_proof,
566 r: (rx, ry),
567 }
568 }
569
570 /// A method to verify a NIZK proof of the satisfiability of an R1CS instance
571 pub fn verify(
572 &self,
573 inst: &Instance,
574 input: &InputsAssignment,
575 transcript: &mut PoseidonTranscript,
576 // gens: &NIZKGens,
577 ) -> Result<usize, ProofVerifyError> {
578 let timer_verify = Timer::new("NIZK::verify");
579
580 transcript.append_bytes(&inst.digest);
581
582 // We send evaluations of A, B, C at r = (rx, ry) as claims
583 // to enable the verifier complete the first sum-check
584 let timer_eval = Timer::new("eval_sparse_polys");
585 let (claimed_rx, claimed_ry) = &self.r;
586 let inst_evals = inst.inst.evaluate(claimed_rx, claimed_ry);
587 timer_eval.stop();
588
589 let timer_sat_proof = Timer::new("verify_sat_proof");
590 assert_eq!(input.assignment.len(), inst.inst.get_num_inputs());
591 // let (rx, ry) =
592 let nc = self.r1cs_sat_proof.circuit_size(
593 inst.inst.get_num_vars(),
594 inst.inst.get_num_cons(),
595 &input.assignment,
596 &inst_evals,
597 transcript,
598 // &gens.gens_r1cs_sat,
599 )?;
600
601 // verify if claimed rx and ry are correct
602 // assert_eq!(rx, *claimed_rx);
603 // assert_eq!(ry, *claimed_ry);
604 timer_sat_proof.stop();
605 timer_verify.stop();
606
607 Ok(nc)
608 }
609
610 /// A method to verify a NIZK proof of the satisfiability of an R1CS instance with Groth16
611 pub fn verify_groth16(
612 &self,
613 inst: &Instance,
614 input: &InputsAssignment,
615 transcript: &mut PoseidonTranscript,
616 ) -> Result<(u128, u128, u128), ProofVerifyError> {
617 let timer_verify = Timer::new("NIZK::verify");
618
619 // transcript.append_protocol_name(NIZK::protocol_name());
620 transcript.append_bytes(&inst.digest);
621
622 // We send evaluations of A, B, C at r = (rx, ry) as claims
623 // to enable the verifier complete the first sum-check
624 let timer_eval = Timer::new("eval_sparse_polys");
625 let (claimed_rx, claimed_ry) = &self.r;
626 let inst_evals = inst.inst.evaluate(claimed_rx, claimed_ry);
627 timer_eval.stop();
628
629 let timer_sat_proof = Timer::new("verify_sat_proof");
630 assert_eq!(input.assignment.len(), inst.inst.get_num_inputs());
631 // let (rx, ry) =
632 let (ds, dp, dv) = self.r1cs_sat_proof.verify_groth16(
633 inst.inst.get_num_vars(),
634 inst.inst.get_num_cons(),
635 &input.assignment,
636 &inst_evals,
637 transcript,
638 // &gens.gens_r1cs_sat,
639 )?;
640
641 // verify if claimed rx and ry are correct
642 // assert_eq!(rx, *claimed_rx);
643 // assert_eq!(ry, *claimed_ry);
644 timer_sat_proof.stop();
645 timer_verify.stop();
646
647 Ok((ds, dp, dv))
648 }
649}
650
651#[cfg(test)]
652mod tests {
653 use crate::parameters::poseidon_params;
654
655 use super::*;
656 use ark_ff::{BigInteger, One, PrimeField};
657
658 #[test]
659 pub fn check_snark() {
660 let num_vars = 256;
661 let num_cons = num_vars;
662 let num_inputs = 10;
663
664 // produce public generators
665 let gens = SNARKGens::new(num_cons, num_vars, num_inputs, num_cons);
666
667 // produce a synthetic R1CSInstance
668 let (inst, vars, inputs) = Instance::produce_synthetic_r1cs(num_cons, num_vars, num_inputs);
669
670 // create a commitment to R1CSInstance
671 let (comm, decomm) = SNARK::encode(&inst, &gens);
672
673 let params = poseidon_params();
674
675 // produce a proof
676 let mut prover_transcript = PoseidonTranscript::new(¶ms);
677 let proof = SNARK::prove(
678 &inst,
679 &comm,
680 &decomm,
681 vars,
682 &inputs,
683 &gens,
684 &mut prover_transcript,
685 );
686
687 // verify the proof
688 let mut verifier_transcript = PoseidonTranscript::new(¶ms);
689 assert!(proof
690 .verify(&comm, &inputs, &mut verifier_transcript, &gens)
691 .is_ok());
692 }
693
694 #[test]
695 pub fn check_r1cs_invalid_index() {
696 let num_cons = 4;
697 let num_vars = 8;
698 let num_inputs = 1;
699
700 let zero: [u8; 32] = [
701 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,
702 0,
703 ];
704
705 let A = vec![(0, 0, zero.to_vec())];
706 let B = vec![(100, 1, zero.to_vec())];
707 let C = vec![(1, 1, zero.to_vec())];
708
709 let inst = Instance::new(num_cons, num_vars, num_inputs, &A, &B, &C);
710 assert!(inst.is_err());
711 assert_eq!(inst.err(), Some(R1CSError::InvalidIndex));
712 }
713
714 #[test]
715 pub fn check_r1cs_invalid_scalar() {
716 let num_cons = 4;
717 let num_vars = 8;
718 let num_inputs = 1;
719
720 let zero: [u8; 32] = [
721 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,
722 0,
723 ];
724
725 let larger_than_mod = [
726 3, 0, 0, 0, 255, 255, 255, 255, 254, 91, 254, 255, 2, 164, 189, 83, 5, 216, 161, 9, 8, 216,
727 57, 51, 72, 125, 157, 41, 83, 167, 237, 115,
728 ];
729
730 let A = vec![(0, 0, zero.to_vec())];
731 let B = vec![(1, 1, larger_than_mod.to_vec())];
732 let C = vec![(1, 1, zero.to_vec())];
733
734 let inst = Instance::new(num_cons, num_vars, num_inputs, &A, &B, &C);
735 assert!(inst.is_err());
736 assert_eq!(inst.err(), Some(R1CSError::InvalidScalar));
737 }
738
739 #[test]
740 fn test_padded_constraints() {
741 // parameters of the R1CS instance
742 let num_cons = 1;
743 let num_vars = 0;
744 let num_inputs = 3;
745 let num_non_zero_entries = 3;
746
747 // We will encode the above constraints into three matrices, where
748 // the coefficients in the matrix are in the little-endian byte order
749 let mut A: Vec<(usize, usize, Vec<u8>)> = Vec::new();
750 let mut B: Vec<(usize, usize, Vec<u8>)> = Vec::new();
751 let mut C: Vec<(usize, usize, Vec<u8>)> = Vec::new();
752
753 // Create a^2 + b + 13
754 A.push((0, num_vars + 2, (Scalar::one().into_repr().to_bytes_le()))); // 1*a
755 B.push((0, num_vars + 2, Scalar::one().into_repr().to_bytes_le())); // 1*a
756 C.push((0, num_vars + 1, Scalar::one().into_repr().to_bytes_le())); // 1*z
757 C.push((
758 0,
759 num_vars,
760 (-Scalar::from(13u64)).into_repr().to_bytes_le(),
761 )); // -13*1
762 C.push((0, num_vars + 3, (-Scalar::one()).into_repr().to_bytes_le())); // -1*b
763
764 // Var Assignments (Z_0 = 16 is the only output)
765 let vars = vec![Scalar::zero().into_repr().to_bytes_le(); num_vars];
766
767 // create an InputsAssignment (a = 1, b = 2)
768 let mut inputs = vec![Scalar::zero().into_repr().to_bytes_le(); num_inputs];
769 inputs[0] = Scalar::from(16u64).into_repr().to_bytes_le();
770 inputs[1] = Scalar::from(1u64).into_repr().to_bytes_le();
771 inputs[2] = Scalar::from(2u64).into_repr().to_bytes_le();
772
773 let assignment_inputs = InputsAssignment::new(&inputs).unwrap();
774 let assignment_vars = VarsAssignment::new(&vars).unwrap();
775
776 // Check if instance is satisfiable
777 let inst = Instance::new(num_cons, num_vars, num_inputs, &A, &B, &C).unwrap();
778 let res = inst.is_sat(&assignment_vars, &assignment_inputs);
779 assert!(res.unwrap(), "should be satisfied");
780
781 // SNARK public params
782 let gens = SNARKGens::new(num_cons, num_vars, num_inputs, num_non_zero_entries);
783
784 // create a commitment to the R1CS instance
785 let (comm, decomm) = SNARK::encode(&inst, &gens);
786
787 let params = poseidon_params();
788
789 // produce a SNARK
790 let mut prover_transcript = PoseidonTranscript::new(¶ms);
791 let proof = SNARK::prove(
792 &inst,
793 &comm,
794 &decomm,
795 assignment_vars.clone(),
796 &assignment_inputs,
797 &gens,
798 &mut prover_transcript,
799 );
800
801 // verify the SNARK
802 let mut verifier_transcript = PoseidonTranscript::new(¶ms);
803 assert!(proof
804 .verify(&comm, &assignment_inputs, &mut verifier_transcript, &gens)
805 .is_ok());
806
807 // NIZK public params
808 let _gens = NIZKGens::new(num_cons, num_vars, num_inputs);
809
810 let params = poseidon_params();
811
812 // produce a NIZK
813 let mut prover_transcript = PoseidonTranscript::new(¶ms);
814 let proof = NIZK::prove(
815 &inst,
816 assignment_vars,
817 &assignment_inputs,
818 // &gens,
819 &mut prover_transcript,
820 );
821
822 // verify the NIZK
823 let mut verifier_transcript = PoseidonTranscript::new(¶ms);
824 assert!(proof
825 .verify(&inst, &assignment_inputs, &mut verifier_transcript)
826 .is_ok());
827 }
828}