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 core;
8extern crate digest;
9extern crate lazy_static;
10extern crate merlin;
11extern crate rand;
12extern crate sha3;
13extern crate test;
14
15#[macro_use]
16extern crate json;
17
18#[cfg(feature = "multicore")]
19extern crate rayon;
20
21mod commitments;
22mod dense_mlpoly;
23mod errors;
24mod group;
25mod math;
26mod nizk;
27mod product_tree;
28mod r1csinstance;
29mod r1csproof;
30mod random;
31mod scalar;
32mod sparse_mlpoly;
33mod sumcheck;
34mod timer;
35mod transcript;
36mod unipoly;
37
38pub mod parameters;
39
40mod constraints;
41pub mod poseidon_transcript;
42
43use ark_ff::Field;
44
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(self
270 .inst
271 .is_sat(&padded_vars.assignment, &inputs.assignment))
272 }
273
274 /// Constructs a new synthetic R1CS `Instance` and an associated satisfying assignment
275 pub fn produce_synthetic_r1cs(
276 num_cons: usize,
277 num_vars: usize,
278 num_inputs: usize,
279 ) -> (Instance, VarsAssignment, InputsAssignment) {
280 let (inst, vars, inputs) =
281 R1CSInstance::produce_synthetic_r1cs(num_cons, num_vars, num_inputs);
282 let digest = inst.get_digest();
283 (
284 Instance { inst, digest },
285 VarsAssignment { assignment: vars },
286 InputsAssignment { assignment: inputs },
287 )
288 }
289}
290
291/// `SNARKGens` holds public parameters for producing and verifying proofs with the Spartan SNARK
292pub struct SNARKGens {
293 gens_r1cs_sat: R1CSGens,
294 gens_r1cs_eval: R1CSCommitmentGens,
295}
296
297impl SNARKGens {
298 /// Constructs a new `SNARKGens` given the size of the R1CS statement
299 /// `num_nz_entries` specifies the maximum number of non-zero entries in any of the three R1CS matrices
300 pub fn new(num_cons: usize, num_vars: usize, num_inputs: usize, num_nz_entries: usize) -> Self {
301 let num_vars_padded = {
302 let mut num_vars_padded = max(num_vars, num_inputs + 1);
303 if num_vars_padded != num_vars_padded.next_power_of_two() {
304 num_vars_padded = num_vars_padded.next_power_of_two();
305 }
306 num_vars_padded
307 };
308
309 let gens_r1cs_sat = R1CSGens::new(b"gens_r1cs_sat", num_cons, num_vars_padded);
310 let gens_r1cs_eval = R1CSCommitmentGens::new(
311 b"gens_r1cs_eval",
312 num_cons,
313 num_vars_padded,
314 num_inputs,
315 num_nz_entries,
316 );
317 SNARKGens {
318 gens_r1cs_sat,
319 gens_r1cs_eval,
320 }
321 }
322}
323
324/// `SNARK` holds a proof produced by Spartan SNARK
325#[derive(CanonicalSerialize, CanonicalDeserialize, Debug)]
326pub struct SNARK {
327 r1cs_sat_proof: R1CSProof,
328 inst_evals: (Scalar, Scalar, Scalar),
329 r1cs_eval_proof: R1CSEvalProof,
330 rx: Vec<Scalar>,
331 ry: Vec<Scalar>,
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 need to reset the transcript state before starting the evaluation
403 // proof and share this state with the verifier because, on the verifier's
404 // side all the previous updates are done on the transcript
405 // circuit variable and the transcript outside the circuit will be
406 // inconsistent wrt to the prover's.
407 transcript.new_from_state(&r1cs_sat_proof.transcript_sat_state);
408
409 // We send evaluations of A, B, C at r = (rx, ry) as claims
410 // to enable the verifier complete the first sum-check
411 let timer_eval = Timer::new("eval_sparse_polys");
412 let inst_evals = {
413 let (Ar, Br, Cr) = inst.inst.evaluate(&rx, &ry);
414 transcript.append_scalar(&Ar);
415 transcript.append_scalar(&Br);
416 transcript.append_scalar(&Cr);
417 (Ar, Br, Cr)
418 };
419 timer_eval.stop();
420
421 let r1cs_eval_proof = {
422 let proof = R1CSEvalProof::prove(
423 &decomm.decomm,
424 &rx,
425 &ry,
426 &inst_evals,
427 &gens.gens_r1cs_eval,
428 transcript,
429 &mut random_tape,
430 );
431
432 let mut proof_encoded: Vec<u8> = Vec::new();
433 proof.serialize(&mut proof_encoded).unwrap();
434 Timer::print(&format!("len_r1cs_eval_proof {:?}", proof_encoded.len()));
435 proof
436 };
437
438 timer_prove.stop();
439 SNARK {
440 r1cs_sat_proof,
441 inst_evals,
442 r1cs_eval_proof,
443 rx,
444 ry,
445 }
446 }
447
448 /// A method to verify the SNARK proof of the satisfiability of an R1CS instance
449 pub fn verify(
450 &self,
451 comm: &ComputationCommitment,
452 input: &InputsAssignment,
453 transcript: &mut PoseidonTranscript,
454 gens: &SNARKGens,
455 ) -> Result<(u128, u128, u128), ProofVerifyError> {
456 let timer_verify = Timer::new("SNARK::verify");
457 // transcript.append_protocol_name(SNARK::protocol_name());
458
459 // append a commitment to the computation to the transcript
460 comm.comm.append_to_poseidon(transcript);
461
462 let timer_sat_proof = Timer::new("verify_sat_proof");
463 assert_eq!(input.assignment.len(), comm.comm.get_num_inputs());
464 // let (rx, ry) =
465 let res = self.r1cs_sat_proof.verify_groth16(
466 comm.comm.get_num_vars(),
467 comm.comm.get_num_cons(),
468 &input.assignment,
469 &self.inst_evals,
470 transcript,
471 &gens.gens_r1cs_sat,
472 )?;
473 timer_sat_proof.stop();
474
475 let timer_eval_proof = Timer::new("verify_eval_proof");
476 // Reset the transcript using the state sent by the prover.
477 // TODO: find a way to retrieve this state from the circuit. Currently
478 // the API for generating constraints doesn't support returning values
479 // computed inside the circuit.
480 transcript.new_from_state(&self.r1cs_sat_proof.transcript_sat_state);
481
482 let (Ar, Br, Cr) = &self.inst_evals;
483 transcript.append_scalar(&Ar);
484 transcript.append_scalar(&Br);
485 transcript.append_scalar(&Cr);
486
487 self.r1cs_eval_proof.verify(
488 &comm.comm,
489 &self.rx,
490 &self.ry,
491 &self.inst_evals,
492 &gens.gens_r1cs_eval,
493 transcript,
494 )?;
495 timer_eval_proof.stop();
496 timer_verify.stop();
497 Ok(res)
498 }
499}
500
501#[derive(Clone)]
502/// `NIZKGens` holds public parameters for producing and verifying proofs with the Spartan NIZK
503pub struct NIZKGens {
504 gens_r1cs_sat: R1CSGens,
505}
506
507impl NIZKGens {
508 /// Constructs a new `NIZKGens` given the size of the R1CS statement
509 pub fn new(num_cons: usize, num_vars: usize, num_inputs: usize) -> Self {
510 let num_vars_padded = {
511 let mut num_vars_padded = max(num_vars, num_inputs + 1);
512 if num_vars_padded != num_vars_padded.next_power_of_two() {
513 num_vars_padded = num_vars_padded.next_power_of_two();
514 }
515 num_vars_padded
516 };
517
518 let gens_r1cs_sat = R1CSGens::new(b"gens_r1cs_sat", num_cons, num_vars_padded);
519 NIZKGens { gens_r1cs_sat }
520 }
521}
522
523/// `NIZK` holds a proof produced by Spartan NIZK
524#[derive(CanonicalSerialize, CanonicalDeserialize, Debug)]
525pub struct NIZK {
526 r1cs_sat_proof: R1CSProof,
527 r: (Vec<Scalar>, Vec<Scalar>),
528}
529
530impl NIZK {
531 fn protocol_name() -> &'static [u8] {
532 b"Spartan NIZK proof"
533 }
534
535 /// A method to produce a NIZK proof of the satisfiability of an R1CS instance
536 pub fn prove(
537 inst: &Instance,
538 vars: VarsAssignment,
539 input: &InputsAssignment,
540 gens: &NIZKGens,
541 transcript: &mut PoseidonTranscript,
542 ) -> Self {
543 let timer_prove = Timer::new("NIZK::prove");
544 // we create a Transcript object seeded with a random Scalar
545 // to aid the prover produce its randomness
546 let _random_tape = RandomTape::new(b"proof");
547
548 // transcript.append_protocol_name(NIZK::protocol_name());
549 transcript.append_bytes(&inst.digest);
550
551 let (r1cs_sat_proof, rx, ry) = {
552 // we might need to pad variables
553 let padded_vars = {
554 let num_padded_vars = inst.inst.get_num_vars();
555 let num_vars = vars.assignment.len();
556 if num_padded_vars > num_vars {
557 vars.pad(num_padded_vars)
558 } else {
559 vars
560 }
561 };
562
563 let (proof, rx, ry) = R1CSProof::prove(
564 &inst.inst,
565 padded_vars.assignment,
566 &input.assignment,
567 &gens.gens_r1cs_sat,
568 transcript,
569 // &mut random_tape,
570 );
571 let mut proof_encoded = Vec::new();
572 proof.serialize(&mut proof_encoded).unwrap();
573 Timer::print(&format!("len_r1cs_sat_proof {:?}", proof_encoded.len()));
574 (proof, rx, ry)
575 };
576
577 timer_prove.stop();
578 NIZK {
579 r1cs_sat_proof,
580 r: (rx, ry),
581 }
582 }
583
584 /// A method to verify a NIZK proof of the satisfiability of an R1CS instance
585 pub fn verify(
586 &self,
587 inst: &Instance,
588 input: &InputsAssignment,
589 transcript: &mut PoseidonTranscript,
590 gens: &NIZKGens,
591 ) -> Result<usize, ProofVerifyError> {
592 let timer_verify = Timer::new("NIZK::verify");
593
594 transcript.append_bytes(&inst.digest);
595
596 // We send evaluations of A, B, C at r = (rx, ry) as claims
597 // to enable the verifier complete the first sum-check
598 let timer_eval = Timer::new("eval_sparse_polys");
599 let (claimed_rx, claimed_ry) = &self.r;
600 let inst_evals = inst.inst.evaluate(claimed_rx, claimed_ry);
601 timer_eval.stop();
602
603 let timer_sat_proof = Timer::new("verify_sat_proof");
604 assert_eq!(input.assignment.len(), inst.inst.get_num_inputs());
605 // let (rx, ry) =
606 let nc = self.r1cs_sat_proof.circuit_size(
607 inst.inst.get_num_vars(),
608 inst.inst.get_num_cons(),
609 &input.assignment,
610 &inst_evals,
611 transcript,
612 &gens.gens_r1cs_sat,
613 )?;
614
615 // verify if claimed rx and ry are correct
616 // assert_eq!(rx, *claimed_rx);
617 // assert_eq!(ry, *claimed_ry);
618 timer_sat_proof.stop();
619 timer_verify.stop();
620
621 Ok(nc)
622 }
623
624 /// A method to verify a NIZK proof of the satisfiability of an R1CS instance with Groth16
625 pub fn verify_groth16(
626 &self,
627 inst: &Instance,
628 input: &InputsAssignment,
629 transcript: &mut PoseidonTranscript,
630 gens: &NIZKGens,
631 ) -> Result<(u128, u128, u128), ProofVerifyError> {
632 let timer_verify = Timer::new("NIZK::verify");
633
634 // transcript.append_protocol_name(NIZK::protocol_name());
635 transcript.append_bytes(&inst.digest);
636
637 // We send evaluations of A, B, C at r = (rx, ry) as claims
638 // to enable the verifier complete the first sum-check
639 let timer_eval = Timer::new("eval_sparse_polys");
640 let (claimed_rx, claimed_ry) = &self.r;
641 let inst_evals = inst.inst.evaluate(claimed_rx, claimed_ry);
642 timer_eval.stop();
643
644 let timer_sat_proof = Timer::new("verify_sat_proof");
645 assert_eq!(input.assignment.len(), inst.inst.get_num_inputs());
646 // let (rx, ry) =
647 let (ds, dp, dv) = self.r1cs_sat_proof.verify_groth16(
648 inst.inst.get_num_vars(),
649 inst.inst.get_num_cons(),
650 &input.assignment,
651 &inst_evals,
652 transcript,
653 &gens.gens_r1cs_sat,
654 )?;
655
656 // verify if claimed rx and ry are correct
657 // assert_eq!(rx, *claimed_rx);
658 // assert_eq!(ry, *claimed_ry);
659 timer_sat_proof.stop();
660 timer_verify.stop();
661
662 Ok((ds, dp, dv))
663 }
664}
665
666#[cfg(test)]
667mod tests {
668 use crate::parameters::poseidon_params;
669
670 use super::*;
671 use ark_ff::{BigInteger, One, PrimeField};
672
673 #[test]
674 pub fn check_snark() {
675 let num_vars = 256;
676 let num_cons = num_vars;
677 let num_inputs = 10;
678
679 // produce public generators
680 let gens = SNARKGens::new(num_cons, num_vars, num_inputs, num_cons);
681
682 // produce a synthetic R1CSInstance
683 let (inst, vars, inputs) = Instance::produce_synthetic_r1cs(num_cons, num_vars, num_inputs);
684
685 // create a commitment to R1CSInstance
686 let (comm, decomm) = SNARK::encode(&inst, &gens);
687
688 let params = poseidon_params();
689
690 // produce a proof
691 let mut prover_transcript = PoseidonTranscript::new(¶ms);
692 let proof = SNARK::prove(
693 &inst,
694 &comm,
695 &decomm,
696 vars,
697 &inputs,
698 &gens,
699 &mut prover_transcript,
700 );
701
702 // verify the proof
703 let mut verifier_transcript = PoseidonTranscript::new(¶ms);
704 assert!(proof
705 .verify(&comm, &inputs, &mut verifier_transcript, &gens)
706 .is_ok());
707 }
708
709 #[test]
710 pub fn check_r1cs_invalid_index() {
711 let num_cons = 4;
712 let num_vars = 8;
713 let num_inputs = 1;
714
715 let zero: [u8; 32] = [
716 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,
717 0, 0, 0,
718 ];
719
720 let A = vec![(0, 0, zero.to_vec())];
721 let B = vec![(100, 1, zero.to_vec())];
722 let C = vec![(1, 1, zero.to_vec())];
723
724 let inst = Instance::new(num_cons, num_vars, num_inputs, &A, &B, &C);
725 assert!(inst.is_err());
726 assert_eq!(inst.err(), Some(R1CSError::InvalidIndex));
727 }
728
729 #[test]
730 pub fn check_r1cs_invalid_scalar() {
731 let num_cons = 4;
732 let num_vars = 8;
733 let num_inputs = 1;
734
735 let zero: [u8; 32] = [
736 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,
737 0, 0, 0,
738 ];
739
740 let larger_than_mod = [
741 3, 0, 0, 0, 255, 255, 255, 255, 254, 91, 254, 255, 2, 164, 189, 83, 5, 216, 161, 9, 8,
742 216, 57, 51, 72, 125, 157, 41, 83, 167, 237, 115,
743 ];
744
745 let A = vec![(0, 0, zero.to_vec())];
746 let B = vec![(1, 1, larger_than_mod.to_vec())];
747 let C = vec![(1, 1, zero.to_vec())];
748
749 let inst = Instance::new(num_cons, num_vars, num_inputs, &A, &B, &C);
750 assert!(inst.is_err());
751 assert_eq!(inst.err(), Some(R1CSError::InvalidScalar));
752 }
753
754 #[test]
755 fn test_padded_constraints() {
756 // parameters of the R1CS instance
757 let num_cons = 1;
758 let num_vars = 0;
759 let num_inputs = 3;
760 let num_non_zero_entries = 3;
761
762 // We will encode the above constraints into three matrices, where
763 // the coefficients in the matrix are in the little-endian byte order
764 let mut A: Vec<(usize, usize, Vec<u8>)> = Vec::new();
765 let mut B: Vec<(usize, usize, Vec<u8>)> = Vec::new();
766 let mut C: Vec<(usize, usize, Vec<u8>)> = Vec::new();
767
768 // Create a^2 + b + 13
769 A.push((0, num_vars + 2, (Scalar::one().into_repr().to_bytes_le()))); // 1*a
770 B.push((0, num_vars + 2, Scalar::one().into_repr().to_bytes_le())); // 1*a
771 C.push((0, num_vars + 1, Scalar::one().into_repr().to_bytes_le())); // 1*z
772 C.push((
773 0,
774 num_vars,
775 (-Scalar::from(13u64)).into_repr().to_bytes_le(),
776 )); // -13*1
777 C.push((0, num_vars + 3, (-Scalar::one()).into_repr().to_bytes_le())); // -1*b
778
779 // Var Assignments (Z_0 = 16 is the only output)
780 let vars = vec![Scalar::zero().into_repr().to_bytes_le(); num_vars];
781
782 // create an InputsAssignment (a = 1, b = 2)
783 let mut inputs = vec![Scalar::zero().into_repr().to_bytes_le(); num_inputs];
784 inputs[0] = Scalar::from(16u64).into_repr().to_bytes_le();
785 inputs[1] = Scalar::from(1u64).into_repr().to_bytes_le();
786 inputs[2] = Scalar::from(2u64).into_repr().to_bytes_le();
787
788 let assignment_inputs = InputsAssignment::new(&inputs).unwrap();
789 let assignment_vars = VarsAssignment::new(&vars).unwrap();
790
791 // Check if instance is satisfiable
792 let inst = Instance::new(num_cons, num_vars, num_inputs, &A, &B, &C).unwrap();
793 let res = inst.is_sat(&assignment_vars, &assignment_inputs);
794 assert!(res.unwrap(), "should be satisfied");
795
796 // SNARK public params
797 let gens = SNARKGens::new(num_cons, num_vars, num_inputs, num_non_zero_entries);
798
799 // create a commitment to the R1CS instance
800 let (comm, decomm) = SNARK::encode(&inst, &gens);
801
802 let params = poseidon_params();
803
804 // produce a SNARK
805 let mut prover_transcript = PoseidonTranscript::new(¶ms);
806 let proof = SNARK::prove(
807 &inst,
808 &comm,
809 &decomm,
810 assignment_vars.clone(),
811 &assignment_inputs,
812 &gens,
813 &mut prover_transcript,
814 );
815
816 // verify the SNARK
817 let mut verifier_transcript = PoseidonTranscript::new(¶ms);
818 assert!(proof
819 .verify(&comm, &assignment_inputs, &mut verifier_transcript, &gens)
820 .is_ok());
821
822 // NIZK public params
823 let gens = NIZKGens::new(num_cons, num_vars, num_inputs);
824
825 let params = poseidon_params();
826
827 // produce a NIZK
828 let mut prover_transcript = PoseidonTranscript::new(¶ms);
829 let proof = NIZK::prove(
830 &inst,
831 assignment_vars,
832 &assignment_inputs,
833 &gens,
834 &mut prover_transcript,
835 );
836
837 // verify the NIZK
838 let mut verifier_transcript = PoseidonTranscript::new(¶ms);
839 assert!(proof
840 .verify_groth16(&inst, &assignment_inputs, &mut verifier_transcript, &gens)
841 .is_ok());
842 }
843}