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