testudo/src/r1csproof.rs
src/r1csproof.rsRaw
1#![allow(clippy::too_many_arguments)]
2use crate::constraints::{VerifierCircuit, VerifierConfig};
3use crate::group::{Fq, Fr};
4use crate::math::Math;
5use crate::parameters::poseidon_params;
6use crate::poseidon_transcript::PoseidonTranscript;
7use crate::sumcheck::SumcheckInstanceProof;
8
9use ark_bw6_761::BW6_761 as P;
10
11use super::commitments::MultiCommitGens;
12use super::dense_mlpoly::{DensePolynomial, EqPolynomial, PolyCommitmentGens};
13use super::errors::ProofVerifyError;
14
15use super::r1csinstance::R1CSInstance;
16
17use super::scalar::Scalar;
18use super::sparse_mlpoly::{SparsePolyEntry, SparsePolynomial};
19use super::timer::Timer;
20use ark_crypto_primitives::{CircuitSpecificSetupSNARK, SNARK};
21
22use ark_groth16::Groth16;
23use ark_relations::r1cs::{ConstraintSynthesizer, ConstraintSystem};
24use ark_serialize::*;
25use ark_std::{One, Zero};
26
27use std::time::Instant;
28
29#[derive(CanonicalSerialize, CanonicalDeserialize, Debug)]
30pub struct R1CSProof {
31 sc_proof_phase1: SumcheckInstanceProof,
32 claims_phase2: (Scalar, Scalar, Scalar, Scalar),
33 // pok_claims_phase2: (KnowledgeProof, ProductProof),
34 // proof_eq_sc_phase1: EqualityProof,
35 sc_proof_phase2: SumcheckInstanceProof,
36 eval_vars_at_ry: Scalar,
37 // proof_eval_vars_at_ry: PolyEvalProof,
38 // proof_eq_sc_phase2: EqualityProof,
39}
40#[derive(Clone)]
41pub struct R1CSSumcheckGens {
42 gens_1: MultiCommitGens,
43 gens_3: MultiCommitGens,
44 gens_4: MultiCommitGens,
45}
46
47// TODO: fix passing gens_1_ref
48impl R1CSSumcheckGens {
49 pub fn new(label: &'static [u8], gens_1_ref: &MultiCommitGens) -> Self {
50 let gens_1 = gens_1_ref.clone();
51 let gens_3 = MultiCommitGens::new(3, label);
52 let gens_4 = MultiCommitGens::new(4, label);
53
54 R1CSSumcheckGens {
55 gens_1,
56 gens_3,
57 gens_4,
58 }
59 }
60}
61
62#[derive(Clone)]
63pub struct R1CSGens {
64 gens_sc: R1CSSumcheckGens,
65 gens_pc: PolyCommitmentGens,
66}
67
68impl R1CSGens {
69 pub fn new(label: &'static [u8], _num_cons: usize, num_vars: usize) -> Self {
70 let num_poly_vars = num_vars.log_2();
71 let gens_pc = PolyCommitmentGens::new(num_poly_vars, label);
72 let gens_sc = R1CSSumcheckGens::new(label, &gens_pc.gens.gens_1);
73 R1CSGens { gens_sc, gens_pc }
74 }
75}
76
77impl R1CSProof {
78 fn prove_phase_one(
79 num_rounds: usize,
80 evals_tau: &mut DensePolynomial,
81 evals_Az: &mut DensePolynomial,
82 evals_Bz: &mut DensePolynomial,
83 evals_Cz: &mut DensePolynomial,
84 transcript: &mut PoseidonTranscript,
85 ) -> (SumcheckInstanceProof, Vec<Scalar>, Vec<Scalar>) {
86 let comb_func =
87 |poly_tau_comp: &Scalar,
88 poly_A_comp: &Scalar,
89 poly_B_comp: &Scalar,
90 poly_C_comp: &Scalar|
91 -> Scalar { (*poly_tau_comp) * ((*poly_A_comp) * poly_B_comp - poly_C_comp) };
92
93 let (sc_proof_phase_one, r, claims) = SumcheckInstanceProof::prove_cubic_with_additive_term(
94 &Scalar::zero(), // claim is zero
95 num_rounds,
96 evals_tau,
97 evals_Az,
98 evals_Bz,
99 evals_Cz,
100 comb_func,
101 transcript,
102 );
103
104 (sc_proof_phase_one, r, claims)
105 }
106
107 fn prove_phase_two(
108 num_rounds: usize,
109 claim: &Scalar,
110 evals_z: &mut DensePolynomial,
111 evals_ABC: &mut DensePolynomial,
112 transcript: &mut PoseidonTranscript,
113 ) -> (SumcheckInstanceProof, Vec<Scalar>, Vec<Scalar>) {
114 let comb_func =
115 |poly_A_comp: &Scalar, poly_B_comp: &Scalar| -> Scalar { (*poly_A_comp) * poly_B_comp };
116 let (sc_proof_phase_two, r, claims) = SumcheckInstanceProof::prove_quad(
117 claim, num_rounds, evals_z, evals_ABC, comb_func, transcript,
118 );
119
120 (sc_proof_phase_two, r, claims)
121 }
122
123 fn protocol_name() -> &'static [u8] {
124 b"R1CS proof"
125 }
126
127 pub fn prove(
128 inst: &R1CSInstance,
129 vars: Vec<Scalar>,
130 input: &[Scalar],
131 transcript: &mut PoseidonTranscript,
132 ) -> (R1CSProof, Vec<Scalar>, Vec<Scalar>) {
133 let timer_prove = Timer::new("R1CSProof::prove");
134 // we currently require the number of |inputs| + 1 to be at most number of vars
135 assert!(input.len() < vars.len());
136
137 let c = transcript.challenge_scalar();
138 transcript.new_from_state(&c);
139
140 transcript.append_scalar_vector(input);
141
142 let poly_vars = DensePolynomial::new(vars.clone());
143
144 let timer_sc_proof_phase1 = Timer::new("prove_sc_phase_one");
145
146 // append input to variables to create a single vector z
147 let z = {
148 let num_inputs = input.len();
149 let num_vars = vars.len();
150 let mut z = vars;
151 z.extend(&vec![Scalar::one()]); // add constant term in z
152 z.extend(input);
153 z.extend(&vec![Scalar::zero(); num_vars - num_inputs - 1]); // we will pad with zeros
154 z
155 };
156
157 // derive the verifier's challenge tau
158 let (num_rounds_x, num_rounds_y) = (inst.get_num_cons().log_2(), z.len().log_2());
159 let tau = transcript.challenge_vector(num_rounds_x);
160 // compute the initial evaluation table for R(\tau, x)
161 let mut poly_tau = DensePolynomial::new(EqPolynomial::new(tau).evals());
162 let (mut poly_Az, mut poly_Bz, mut poly_Cz) =
163 inst.multiply_vec(inst.get_num_cons(), z.len(), &z);
164
165 let (sc_proof_phase1, rx, _claims_phase1) = R1CSProof::prove_phase_one(
166 num_rounds_x,
167 &mut poly_tau,
168 &mut poly_Az,
169 &mut poly_Bz,
170 &mut poly_Cz,
171 transcript,
172 );
173 assert_eq!(poly_tau.len(), 1);
174 assert_eq!(poly_Az.len(), 1);
175 assert_eq!(poly_Bz.len(), 1);
176 assert_eq!(poly_Cz.len(), 1);
177 timer_sc_proof_phase1.stop();
178
179 let (tau_claim, Az_claim, Bz_claim, Cz_claim) =
180 (&poly_tau[0], &poly_Az[0], &poly_Bz[0], &poly_Cz[0]);
181 let prod_Az_Bz_claims = (*Az_claim) * Bz_claim;
182
183 // prove the final step of sum-check #1
184 let taus_bound_rx = tau_claim;
185 let _claim_post_phase1 = ((*Az_claim) * Bz_claim - Cz_claim) * taus_bound_rx;
186
187 let timer_sc_proof_phase2 = Timer::new("prove_sc_phase_two");
188 // combine the three claims into a single claim
189 let r_A = transcript.challenge_scalar();
190 let r_B = transcript.challenge_scalar();
191 let r_C = transcript.challenge_scalar();
192 let claim_phase2 = r_A * Az_claim + r_B * Bz_claim + r_C * Cz_claim;
193
194 let evals_ABC = {
195 // compute the initial evaluation table for R(\tau, x)
196 let evals_rx = EqPolynomial::new(rx.clone()).evals();
197 let (evals_A, evals_B, evals_C) =
198 inst.compute_eval_table_sparse(inst.get_num_cons(), z.len(), &evals_rx);
199
200 assert_eq!(evals_A.len(), evals_B.len());
201 assert_eq!(evals_A.len(), evals_C.len());
202 (0..evals_A.len())
203 .map(|i| r_A * evals_A[i] + r_B * evals_B[i] + r_C * evals_C[i])
204 .collect::<Vec<Scalar>>()
205 };
206
207 // another instance of the sum-check protocol
208 let (sc_proof_phase2, ry, _claims_phase2) = R1CSProof::prove_phase_two(
209 num_rounds_y,
210 &claim_phase2,
211 &mut DensePolynomial::new(z),
212 &mut DensePolynomial::new(evals_ABC),
213 transcript,
214 );
215 timer_sc_proof_phase2.stop();
216
217 let timer_polyeval = Timer::new("polyeval");
218 let eval_vars_at_ry = poly_vars.evaluate(&ry[1..]);
219 timer_polyeval.stop();
220
221 timer_prove.stop();
222
223 (
224 R1CSProof {
225 sc_proof_phase1,
226 claims_phase2: (*Az_claim, *Bz_claim, *Cz_claim, prod_Az_Bz_claims),
227 sc_proof_phase2,
228 eval_vars_at_ry,
229 },
230 rx,
231 ry,
232 )
233 }
234
235 pub fn verify_groth16(
236 &self,
237 num_vars: usize,
238 num_cons: usize,
239 input: &[Scalar],
240 evals: &(Scalar, Scalar, Scalar),
241 transcript: &mut PoseidonTranscript,
242 ) -> Result<(u128, u128, u128), ProofVerifyError> {
243 let c = transcript.challenge_scalar();
244
245 let mut input_as_sparse_poly_entries = vec![SparsePolyEntry::new(0, Scalar::one())];
246 //remaining inputs
247 input_as_sparse_poly_entries.extend(
248 (0..input.len())
249 .map(|i| SparsePolyEntry::new(i + 1, input[i]))
250 .collect::<Vec<SparsePolyEntry>>(),
251 );
252
253 let n = num_vars;
254 let input_as_sparse_poly =
255 SparsePolynomial::new(n.log_2() as usize, input_as_sparse_poly_entries);
256
257 let config = VerifierConfig {
258 num_vars,
259 num_cons,
260 input: input.to_vec(),
261 evals: *evals,
262 params: poseidon_params(),
263 prev_challenge: c,
264 claims_phase2: self.claims_phase2,
265 polys_sc1: self.sc_proof_phase1.polys.clone(),
266 polys_sc2: self.sc_proof_phase2.polys.clone(),
267 eval_vars_at_ry: self.eval_vars_at_ry,
268 input_as_sparse_poly,
269 };
270
271 let mut rng = ark_std::test_rng();
272
273 let start = Instant::now();
274 let circuit = VerifierCircuit::new(&config, &mut rng).unwrap();
275 let dp1 = start.elapsed().as_millis();
276
277 let start = Instant::now();
278 let (pk, vk) = Groth16::<P>::setup(circuit.clone(), &mut rng).unwrap();
279 let ds = start.elapsed().as_millis();
280
281 let start = Instant::now();
282 let proof = Groth16::<P>::prove(&pk, circuit, &mut rng).unwrap();
283 let dp2 = start.elapsed().as_millis();
284
285 let start = Instant::now();
286 let is_verified = Groth16::<P>::verify(&vk, &[], &proof).unwrap();
287 let dv = start.elapsed().as_millis();
288 assert!(is_verified);
289
290 Ok((ds, dp1 + dp2, dv))
291 }
292
293 pub fn circuit_size(
294 &self,
295 num_vars: usize,
296 num_cons: usize,
297 input: &[Scalar],
298 evals: &(Scalar, Scalar, Scalar),
299 transcript: &mut PoseidonTranscript,
300 ) -> Result<usize, ProofVerifyError> {
301 let c = transcript.challenge_scalar();
302
303 let mut input_as_sparse_poly_entries = vec![SparsePolyEntry::new(0, Scalar::one())];
304 //remaining inputs
305 input_as_sparse_poly_entries.extend(
306 (0..input.len())
307 .map(|i| SparsePolyEntry::new(i + 1, input[i]))
308 .collect::<Vec<SparsePolyEntry>>(),
309 );
310
311 let n = num_vars;
312 let input_as_sparse_poly =
313 SparsePolynomial::new(n.log_2() as usize, input_as_sparse_poly_entries);
314
315 let config = VerifierConfig {
316 num_vars,
317 num_cons,
318 input: input.to_vec(),
319 evals: *evals,
320 params: poseidon_params(),
321 prev_challenge: c,
322 claims_phase2: self.claims_phase2,
323 polys_sc1: self.sc_proof_phase1.polys.clone(),
324 polys_sc2: self.sc_proof_phase2.polys.clone(),
325 eval_vars_at_ry: self.eval_vars_at_ry,
326 input_as_sparse_poly,
327 };
328
329 let mut rng = ark_std::test_rng();
330 let circuit = VerifierCircuit::new(&config, &mut rng).unwrap();
331
332 let nc_inner = verify_constraints_inner(circuit.clone(), &num_cons);
333
334 let nc_outer = verify_constraints_outer(circuit, &num_cons);
335 Ok(nc_inner + nc_outer)
336 }
337}
338
339fn verify_constraints_outer(circuit: VerifierCircuit, _num_cons: &usize) -> usize {
340 let cs = ConstraintSystem::<Fq>::new_ref();
341 circuit.generate_constraints(cs.clone()).unwrap();
342 assert!(cs.is_satisfied().unwrap());
343 cs.num_constraints()
344}
345
346fn verify_constraints_inner(circuit: VerifierCircuit, _num_cons: &usize) -> usize {
347 let cs = ConstraintSystem::<Fr>::new_ref();
348 circuit
349 .inner_circuit
350 .generate_constraints(cs.clone())
351 .unwrap();
352 assert!(cs.is_satisfied().unwrap());
353 cs.num_constraints()
354}
355
356#[cfg(test)]
357mod tests {
358 use crate::parameters::poseidon_params;
359
360 use super::*;
361
362 use ark_std::UniformRand;
363
364 fn produce_tiny_r1cs() -> (R1CSInstance, Vec<Scalar>, Vec<Scalar>) {
365 // three constraints over five variables Z1, Z2, Z3, Z4, and Z5
366 // rounded to the nearest power of two
367 let num_cons = 128;
368 let num_vars = 256;
369 let num_inputs = 2;
370
371 // encode the above constraints into three matrices
372 let mut A: Vec<(usize, usize, Scalar)> = Vec::new();
373 let mut B: Vec<(usize, usize, Scalar)> = Vec::new();
374 let mut C: Vec<(usize, usize, Scalar)> = Vec::new();
375
376 let one = Scalar::one();
377 // constraint 0 entries
378 // (Z1 + Z2) * I0 - Z3 = 0;
379 A.push((0, 0, one));
380 A.push((0, 1, one));
381 B.push((0, num_vars + 1, one));
382 C.push((0, 2, one));
383
384 // constraint 1 entries
385 // (Z1 + I1) * (Z3) - Z4 = 0
386 A.push((1, 0, one));
387 A.push((1, num_vars + 2, one));
388 B.push((1, 2, one));
389 C.push((1, 3, one));
390 // constraint 3 entries
391 // Z5 * 1 - 0 = 0
392 A.push((2, 4, one));
393 B.push((2, num_vars, one));
394
395 let inst = R1CSInstance::new(num_cons, num_vars, num_inputs, &A, &B, &C);
396
397 // compute a satisfying assignment
398 let mut rng = ark_std::rand::thread_rng();
399 let i0 = Scalar::rand(&mut rng);
400 let i1 = Scalar::rand(&mut rng);
401 let z1 = Scalar::rand(&mut rng);
402 let z2 = Scalar::rand(&mut rng);
403 let z3 = (z1 + z2) * i0; // constraint 1: (Z1 + Z2) * I0 - Z3 = 0;
404 let z4 = (z1 + i1) * z3; // constraint 2: (Z1 + I1) * (Z3) - Z4 = 0
405 let z5 = Scalar::zero(); //constraint 3
406
407 let mut vars = vec![Scalar::zero(); num_vars];
408 vars[0] = z1;
409 vars[1] = z2;
410 vars[2] = z3;
411 vars[3] = z4;
412 vars[4] = z5;
413
414 let mut input = vec![Scalar::zero(); num_inputs];
415 input[0] = i0;
416 input[1] = i1;
417
418 (inst, vars, input)
419 }
420
421 #[test]
422 fn test_tiny_r1cs() {
423 let (inst, vars, input) = tests::produce_tiny_r1cs();
424 let is_sat = inst.is_sat(&vars, &input);
425 assert!(is_sat);
426 }
427
428 #[test]
429 fn test_synthetic_r1cs() {
430 let (inst, vars, input) = R1CSInstance::produce_synthetic_r1cs(1024, 1024, 10);
431 let is_sat = inst.is_sat(&vars, &input);
432 assert!(is_sat);
433 }
434
435 #[test]
436 pub fn check_r1cs_proof() {
437 let num_vars = 1024;
438 let num_cons = num_vars;
439 let num_inputs = 10;
440 let (inst, vars, input) = R1CSInstance::produce_synthetic_r1cs(num_cons, num_vars, num_inputs);
441
442 // let gens = R1CSGens::new(b"test-m", num_cons, num_vars);
443
444 let params = poseidon_params();
445 // let mut random_tape = RandomTape::new(b"proof");
446
447 let mut prover_transcript = PoseidonTranscript::new(¶ms);
448 let (proof, rx, ry) = R1CSProof::prove(&inst, vars, &input, &mut prover_transcript);
449
450 let inst_evals = inst.evaluate(&rx, &ry);
451
452 let mut verifier_transcript = PoseidonTranscript::new(¶ms);
453
454 // if you want to check the test fails
455 // input[0] = Scalar::zero();
456
457 assert!(proof
458 .verify_groth16(
459 inst.get_num_vars(),
460 inst.get_num_cons(),
461 &input,
462 &inst_evals,
463 &mut verifier_transcript,
464 )
465 .is_ok());
466 }
467}