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