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