hyperplonk/hyperplonk/src/snark.rs
hyperplonk/src/snark.rsRaw
1use crate::{
2 errors::HyperPlonkErrors,
3 structs::{HyperPlonkIndex, HyperPlonkProof, HyperPlonkProvingKey, HyperPlonkVerifyingKey},
4 utils::{build_f, eval_f, prover_sanity_check, PcsAccumulator},
5 witness::WitnessColumn,
6 HyperPlonkSNARK,
7};
8use arithmetic::{evaluate_opt, identity_permutation_mle, merge_polynomials, VPAuxInfo};
9use ark_ec::PairingEngine;
10use ark_poly::DenseMultilinearExtension;
11use ark_std::{end_timer, log2, start_timer, One, Zero};
12use std::{marker::PhantomData, rc::Rc};
13use subroutines::{
14 pcs::prelude::{Commitment, PolynomialCommitmentScheme},
15 poly_iop::{
16 prelude::{PermutationCheck, ZeroCheck},
17 PolyIOP,
18 },
19 BatchProof,
20};
21use transcript::IOPTranscript;
22
23impl<E, PCS> HyperPlonkSNARK<E, PCS> for PolyIOP<E::Fr>
24where
25 E: PairingEngine,
26 // Ideally we want to access polynomial as PCS::Polynomial, instead of instantiating it here.
27 // But since PCS::Polynomial can be both univariate or multivariate in our implementation
28 // we cannot bound PCS::Polynomial with a property trait bound.
29 PCS: PolynomialCommitmentScheme<
30 E,
31 Polynomial = Rc<DenseMultilinearExtension<E::Fr>>,
32 Point = Vec<E::Fr>,
33 Evaluation = E::Fr,
34 Commitment = Commitment<E>,
35 BatchProof = BatchProof<E, PCS>,
36 >,
37{
38 type Index = HyperPlonkIndex<E::Fr>;
39 type ProvingKey = HyperPlonkProvingKey<E, PCS>;
40 type VerifyingKey = HyperPlonkVerifyingKey<E, PCS>;
41 type Proof = HyperPlonkProof<E, Self, PCS>;
42
43 fn preprocess(
44 index: &Self::Index,
45 pcs_srs: &PCS::SRS,
46 ) -> Result<(Self::ProvingKey, Self::VerifyingKey), HyperPlonkErrors> {
47 let num_vars = index.num_variables();
48
49 let log_num_witness_polys = log2(index.num_witness_columns()) as usize;
50 let witness_merged_nv = num_vars + log_num_witness_polys;
51
52 let log_chunk_size = log_num_witness_polys + 1;
53 let prod_x_nv = num_vars + log_chunk_size;
54
55 let supported_ml_degree = prod_x_nv;
56
57 // extract PCS prover and verifier keys from SRS
58 let (pcs_prover_param, pcs_verifier_param) =
59 PCS::trim(pcs_srs, None, Some(supported_ml_degree))?;
60
61 // build permutation oracles
62 let permutation_oracle = Rc::new(DenseMultilinearExtension::from_evaluations_slice(
63 witness_merged_nv,
64 &index.permutation,
65 ));
66 let perm_com = PCS::commit(&pcs_prover_param, &permutation_oracle)?;
67
68 // build selector oracles and commit to it
69 let selector_oracles: Vec<Rc<DenseMultilinearExtension<E::Fr>>> = index
70 .selectors
71 .iter()
72 .map(|s| Rc::new(DenseMultilinearExtension::from(s)))
73 .collect();
74
75 let selector_commitments = selector_oracles
76 .iter()
77 .map(|poly| PCS::commit(&pcs_prover_param, poly))
78 .collect::<Result<Vec<_>, _>>()?;
79
80 // let selector_merged = merge_polynomials(&selector_oracles)?;
81 // let selector_com = PCS::commit(&pcs_prover_param, &selector_merged)?;
82
83 Ok((
84 Self::ProvingKey {
85 params: index.params.clone(),
86 permutation_oracle: permutation_oracle.clone(),
87 selector_oracles,
88 selector_commitments: selector_commitments.clone(),
89 pcs_param: pcs_prover_param,
90 },
91 Self::VerifyingKey {
92 params: index.params.clone(),
93 permutation_oracle,
94 pcs_param: pcs_verifier_param,
95 selector_commitments,
96 perm_com,
97 },
98 ))
99 }
100
101 /// Generate HyperPlonk SNARK proof.
102 ///
103 /// Inputs:
104 /// - `pk`: circuit proving key
105 /// - `pub_input`: online public input of length 2^\ell
106 /// - `witness`: witness assignment of length 2^n
107 /// Outputs:
108 /// - The HyperPlonk SNARK proof.
109 ///
110 /// Steps:
111 ///
112 /// 1. Commit Witness polynomials `w_i(x)` and append commitment to
113 /// transcript
114 ///
115 /// 2. Run ZeroCheck on
116 ///
117 /// `f(q_0(x),...q_l(x), w_0(x),...w_d(x))`
118 ///
119 /// where `f` is the constraint polynomial i.e.,
120 /// ```ignore
121 /// f(q_l, q_r, q_m, q_o, w_a, w_b, w_c)
122 /// = q_l w_a(x) + q_r w_b(x) + q_m w_a(x)w_b(x) - q_o w_c(x)
123 /// ```
124 /// in vanilla plonk, and obtain a ZeroCheckSubClaim
125 ///
126 /// 3. Run permutation check on `\{w_i(x)\}` and `permutation_oracle`, and
127 /// obtain a PermCheckSubClaim.
128 ///
129 /// 4. Generate evaluations and corresponding proofs
130 /// - 4.1. (deferred) batch opening prod(x) at
131 /// - [0, perm_check_point]
132 /// - [1, perm_check_point]
133 /// - [perm_check_point, 0]
134 /// - [perm_check_point, 1]
135 /// - [1,...1, 0]
136 ///
137 /// - 4.2. permutation check evaluations and proofs
138 /// - 4.2.1. (deferred) wi_poly(perm_check_point)
139 ///
140 /// - 4.3. zero check evaluations and proofs
141 /// - 4.3.1. (deferred) wi_poly(zero_check_point)
142 /// - 4.3.2. (deferred) selector_poly(zero_check_point)
143 ///
144 /// - 4.4. public input consistency checks
145 /// - pi_poly(r_pi) where r_pi is sampled from transcript
146 ///
147 /// - 5. deferred batch opening
148 fn prove(
149 pk: &Self::ProvingKey,
150 pub_input: &[E::Fr],
151 witnesses: &[WitnessColumn<E::Fr>],
152 ) -> Result<Self::Proof, HyperPlonkErrors> {
153 let start = start_timer!(|| "hyperplonk proving");
154 let mut transcript = IOPTranscript::<E::Fr>::new(b"hyperplonk");
155
156 prover_sanity_check(&pk.params, pub_input, witnesses)?;
157
158 // witness assignment of length 2^n
159 let num_vars = pk.params.num_variables();
160 let log_num_witness_polys = log2(pk.params.num_witness_columns()) as usize;
161 let merged_nv = num_vars + log_num_witness_polys;
162
163 // number of nv in prod(x) which is supposed to be the cap
164 // so each chunk we we store maximum 1 << (prod_x_nv - num_var) selectors
165 let log_chunk_size = log_num_witness_polys + 1;
166 let prod_x_nv = num_vars + log_chunk_size;
167
168 // online public input of length 2^\ell
169 let ell = log2(pk.params.num_pub_input) as usize;
170
171 // We use accumulators to store the polynomials and their eval points.
172 // They are batch opened at a later stage.
173 // This includes
174 // - witnesses
175 // - prod(x)
176 // - selectors
177 //
178 // Accumulator's nv is bounded by prod(x) that means
179 // we need to split the selectors into multiple chunks if
180 // #selectors > chunk_size
181 // let mut pcs_acc = PcsAccumulator::<E, PCS>::new(prod_x_nv);
182 let mut prod_x_pcs_acc = PcsAccumulator::<E, PCS>::new(prod_x_nv);
183 let mut witness_and_selector_x_pcs_acc = PcsAccumulator::<E, PCS>::new(num_vars);
184
185 // =======================================================================
186 // 1. Commit Witness polynomials `w_i(x)` and append commitment to
187 // transcript
188 // =======================================================================
189 let step = start_timer!(|| "commit witnesses");
190
191 let witness_polys: Vec<Rc<DenseMultilinearExtension<E::Fr>>> = witnesses
192 .iter()
193 .map(|w| Rc::new(DenseMultilinearExtension::from(w)))
194 .collect();
195
196 let witness_commits = witness_polys
197 .iter()
198 .map(|x| PCS::commit(&pk.pcs_param, x).unwrap())
199 .collect::<Vec<_>>();
200
201 // merge all witness into a single MLE - we will run perm check on it
202 // to obtain prod(x)
203 let w_merged = merge_polynomials(&witness_polys)?;
204 if w_merged.num_vars != merged_nv {
205 return Err(HyperPlonkErrors::InvalidParameters(format!(
206 "merged witness poly has a different num_vars ({}) from expected ({})",
207 w_merged.num_vars, merged_nv
208 )));
209 }
210
211 // TODO: we'll remove one of witness_merged_commit and witness_commits later.
212 let witness_merged_commit = PCS::commit(&pk.pcs_param, &w_merged)?;
213 transcript.append_serializable_element(b"w", &witness_merged_commit)?;
214
215 end_timer!(step);
216 // =======================================================================
217 // 2 Run ZeroCheck on
218 //
219 // `f(q_0(x),...q_l(x), w_0(x),...w_d(x))`
220 //
221 // where `f` is the constraint polynomial i.e.,
222 //
223 // f(q_l, q_r, q_m, q_o, w_a, w_b, w_c)
224 // = q_l w_a(x) + q_r w_b(x) + q_m w_a(x)w_b(x) - q_o w_c(x)
225 //
226 // in vanilla plonk, and obtain a ZeroCheckSubClaim
227 // =======================================================================
228 let step = start_timer!(|| "ZeroCheck on f");
229
230 let fx = build_f(
231 &pk.params.gate_func,
232 pk.params.num_variables(),
233 &pk.selector_oracles,
234 &witness_polys,
235 )?;
236
237 let zero_check_proof = <Self as ZeroCheck<E::Fr>>::prove(&fx, &mut transcript)?;
238 end_timer!(step);
239 // =======================================================================
240 // 3. Run permutation check on `\{w_i(x)\}` and `permutation_oracle`, and
241 // obtain a PermCheckSubClaim.
242 // =======================================================================
243 let step = start_timer!(|| "Permutation check on w_i(x)");
244
245 let (perm_check_proof, prod_x) = <Self as PermutationCheck<E, PCS>>::prove(
246 &pk.pcs_param,
247 &[w_merged.clone()],
248 &[w_merged.clone()],
249 &[pk.permutation_oracle.clone()],
250 &mut transcript,
251 )?;
252 let perm_check_point = &perm_check_proof.zero_check_proof.point;
253
254 end_timer!(step);
255 // =======================================================================
256 // 4. Generate evaluations and corresponding proofs
257 // - 4.1. (deferred) batch opening prod(x) at
258 // - [0, perm_check_point]
259 // - [1, perm_check_point]
260 // - [perm_check_point, 0]
261 // - [perm_check_point, 1]
262 // - [1,...1, 0]
263 //
264 // - 4.2. permutation check evaluations and proofs
265 // - 4.2.1. (deferred) wi_poly(perm_check_point)
266 //
267 // - 4.3. zero check evaluations and proofs
268 // - 4.3.1. (deferred) wi_poly(zero_check_point)
269 // - 4.3.2. (deferred) selector_poly(zero_check_point)
270 //
271 // - 4.4. (deferred) public input consistency checks
272 // - pi_poly(r_pi) where r_pi is sampled from transcript
273 // =======================================================================
274 let step = start_timer!(|| "opening and evaluations");
275
276 // 4.1 (deferred) open prod(0,x), prod(1, x), prod(x, 0), prod(x, 1)
277 // perm_check_point
278 // prod(0, x)
279 let tmp_point1 = [perm_check_point.as_slice(), &[E::Fr::zero()]].concat();
280 // prod(1, x)
281 let tmp_point2 = [perm_check_point.as_slice(), &[E::Fr::one()]].concat();
282 // prod(x, 0)
283 let tmp_point3 = [&[E::Fr::zero()], perm_check_point.as_slice()].concat();
284 // prod(x, 1)
285 let tmp_point4 = [&[E::Fr::one()], perm_check_point.as_slice()].concat();
286 // // prod(1, ..., 1, 0)
287 // let tmp_point5 = [vec![E::Fr::zero()], vec![E::Fr::one();
288 // merged_nv]].concat();
289
290 prod_x_pcs_acc.insert_poly_and_points(&prod_x, &perm_check_proof.prod_x_comm, &tmp_point1);
291 prod_x_pcs_acc.insert_poly_and_points(&prod_x, &perm_check_proof.prod_x_comm, &tmp_point2);
292 prod_x_pcs_acc.insert_poly_and_points(&prod_x, &perm_check_proof.prod_x_comm, &tmp_point3);
293 prod_x_pcs_acc.insert_poly_and_points(&prod_x, &perm_check_proof.prod_x_comm, &tmp_point4);
294
295 // 4.2 permutation check
296 // - 4.2.1. wi_poly(perm_check_point)
297 let (perm_check_opening, perm_check_eval) =
298 PCS::open(&pk.pcs_param, &w_merged, perm_check_point)?;
299
300 // - 4.3. zero check evaluations and proofs
301 // - 4.3.1 (deferred) wi_poly(zero_check_point)
302 for i in 0..witness_polys.len() {
303 witness_and_selector_x_pcs_acc.insert_poly_and_points(
304 &witness_polys[i],
305 &witness_commits[i],
306 &zero_check_proof.point,
307 );
308 }
309
310 // - 4.3.2. (deferred) selector_poly(zero_check_point)
311 pk.selector_oracles
312 .iter()
313 .zip(pk.selector_commitments.iter())
314 .for_each(|(poly, com)| {
315 witness_and_selector_x_pcs_acc.insert_poly_and_points(
316 poly,
317 com,
318 &zero_check_proof.point,
319 )
320 });
321
322 // - 4.4. public input consistency checks
323 // - pi_poly(r_pi) where r_pi is sampled from transcript
324 let r_pi = transcript.get_and_append_challenge_vectors(b"r_pi", ell)?;
325 let tmp_point = [vec![E::Fr::zero(); num_vars - ell], r_pi].concat();
326 witness_and_selector_x_pcs_acc.insert_poly_and_points(
327 &witness_polys[0],
328 &witness_commits[0],
329 &tmp_point,
330 );
331 end_timer!(step);
332
333 // =======================================================================
334 // 5. deferred batch opening
335 // =======================================================================
336 let step = start_timer!(|| "deferred batch openings prod(x)");
337 let batch_prod_x_openings = prod_x_pcs_acc.multi_open(&pk.pcs_param, &mut transcript)?;
338 end_timer!(step);
339
340 let step = start_timer!(|| "deferred batch openings witness and selectors");
341 let batch_witness_and_selector_openings =
342 witness_and_selector_x_pcs_acc.multi_open(&pk.pcs_param, &mut transcript)?;
343 end_timer!(step);
344
345 end_timer!(start);
346
347 Ok(HyperPlonkProof {
348 // PCS commit for witnesses
349 witness_merged_commit,
350 witness_commits,
351 // batch_openings,
352 batch_prod_x_openings,
353 batch_witness_and_selector_openings,
354 // perm check openings
355 perm_check_opening,
356 perm_check_eval,
357 // =======================================================================
358 // IOP proofs
359 // =======================================================================
360 // the custom gate zerocheck proof
361 zero_check_proof,
362 // the permutation check proof for copy constraints
363 perm_check_proof,
364 })
365 }
366
367 /// Verify the HyperPlonk proof.
368 ///
369 /// Inputs:
370 /// - `vk`: verification key
371 /// - `pub_input`: online public input
372 /// - `proof`: HyperPlonk SNARK proof
373 /// Outputs:
374 /// - Return a boolean on whether the verification is successful
375 ///
376 /// 1. Verify zero_check_proof on
377 ///
378 /// `f(q_0(x),...q_l(x), w_0(x),...w_d(x))`
379 ///
380 /// where `f` is the constraint polynomial i.e.,
381 /// ```ignore
382 /// f(q_l, q_r, q_m, q_o, w_a, w_b, w_c)
383 /// = q_l w_a(x) + q_r w_b(x) + q_m w_a(x)w_b(x) - q_o w_c(x)
384 /// ```
385 /// in vanilla plonk, and obtain a ZeroCheckSubClaim
386 ///
387 /// 2. Verify perm_check_proof on `\{w_i(x)\}` and `permutation_oracle`
388 ///
389 /// 3. check subclaim validity
390 ///
391 /// 4. Verify the opening against the commitment:
392 /// - check permutation check evaluations
393 /// - check zero check evaluations
394 /// - public input consistency checks
395 fn verify(
396 vk: &Self::VerifyingKey,
397 pub_input: &[E::Fr],
398 proof: &Self::Proof,
399 ) -> Result<bool, HyperPlonkErrors> {
400 let start = start_timer!(|| "hyperplonk verification");
401
402 let mut transcript = IOPTranscript::<E::Fr>::new(b"hyperplonk");
403
404 let num_selectors = vk.params.num_selector_columns();
405 let num_witnesses = vk.params.num_witness_columns();
406
407 // witness assignment of length 2^n
408 let log_num_witness_polys = log2(num_witnesses) as usize;
409 let num_vars = vk.params.num_variables();
410 // number of variables in merged polynomial for Multilinear-KZG
411 let merged_nv = num_vars + log_num_witness_polys;
412
413 // online public input of length 2^\ell
414 let ell = log2(vk.params.num_pub_input) as usize;
415
416 // sequence:
417 // - prod(x) at 5 points
418 // - w_merged at perm check point
419 // - w_merged at zero check points (#witness points)
420 // - selector_merged at zero check points (#selector points)
421 // - w[0] at r_pi
422 let selector_evals = &proof
423 .batch_witness_and_selector_openings
424 .f_i_eval_at_point_i[num_witnesses..num_witnesses + num_selectors];
425 let witness_evals = &proof
426 .batch_witness_and_selector_openings
427 .f_i_eval_at_point_i[..num_witnesses];
428 let prod_evals = &proof.batch_prod_x_openings.f_i_eval_at_point_i[0..4];
429 let pi_eval = proof
430 .batch_witness_and_selector_openings
431 .f_i_eval_at_point_i
432 .last()
433 .unwrap();
434
435 let pi_poly = DenseMultilinearExtension::from_evaluations_slice(ell as usize, pub_input);
436
437 // =======================================================================
438 // 0. sanity checks
439 // =======================================================================
440 // public input length
441 if pub_input.len() != vk.params.num_pub_input {
442 return Err(HyperPlonkErrors::InvalidProver(format!(
443 "Public input length is not correct: got {}, expect {}",
444 pub_input.len(),
445 1 << ell
446 )));
447 }
448
449 // =======================================================================
450 // 1. Verify zero_check_proof on
451 // `f(q_0(x),...q_l(x), w_0(x),...w_d(x))`
452 //
453 // where `f` is the constraint polynomial i.e.,
454 //
455 // f(q_l, q_r, q_m, q_o, w_a, w_b, w_c)
456 // = q_l w_a(x) + q_r w_b(x) + q_m w_a(x)w_b(x) - q_o w_c(x)
457 //
458 // =======================================================================
459 let step = start_timer!(|| "verify zero check");
460 // Zero check and perm check have different AuxInfo
461 let zero_check_aux_info = VPAuxInfo::<E::Fr> {
462 max_degree: vk.params.gate_func.degree(),
463 num_variables: num_vars,
464 phantom: PhantomData::default(),
465 };
466 // push witness to transcript
467 transcript.append_serializable_element(b"w", &proof.witness_merged_commit)?;
468
469 let zero_check_sub_claim = <Self as ZeroCheck<E::Fr>>::verify(
470 &proof.zero_check_proof,
471 &zero_check_aux_info,
472 &mut transcript,
473 )?;
474
475 let zero_check_point = &zero_check_sub_claim.point;
476
477 // check zero check subclaim
478 let f_eval = eval_f(&vk.params.gate_func, selector_evals, witness_evals)?;
479 if f_eval != zero_check_sub_claim.expected_evaluation {
480 return Err(HyperPlonkErrors::InvalidProof(
481 "zero check evaluation failed".to_string(),
482 ));
483 }
484
485 end_timer!(step);
486 // =======================================================================
487 // 2. Verify perm_check_proof on `\{w_i(x)\}` and `permutation_oracle`
488 // =======================================================================
489 let step = start_timer!(|| "verify permutation check");
490
491 // Zero check and perm check have different AuxInfo
492 let perm_check_aux_info = VPAuxInfo::<E::Fr> {
493 // Prod(x) has a max degree of 2
494 max_degree: 2,
495 // degree of merged poly
496 num_variables: merged_nv,
497 phantom: PhantomData::default(),
498 };
499 let perm_check_sub_claim = <Self as PermutationCheck<E, PCS>>::verify(
500 &proof.perm_check_proof,
501 &perm_check_aux_info,
502 &mut transcript,
503 )?;
504
505 let perm_check_point = &perm_check_sub_claim
506 .product_check_sub_claim
507 .zero_check_sub_claim
508 .point;
509
510 let alpha = perm_check_sub_claim.product_check_sub_claim.alpha;
511 let (beta, gamma) = perm_check_sub_claim.challenges;
512
513 // check perm check subclaim:
514 // proof.witness_perm_check_eval ?= perm_check_sub_claim.expected_eval
515 //
516 // Q(x) := prod(1,x) - prod(x, 0) * prod(x, 1)
517 // + alpha * (
518 // (g(x) + beta * s_perm(x) + gamma) * prod(0, x)
519 // - (f(x) + beta * s_id(x) + gamma))
520 // where
521 // - Q(x) is perm_check_sub_claim.zero_check.exp_eval
522 // - prod(1, x) ... from prod(x) evaluated over (1, zero_point)
523 // - g(x), f(x) are both w_merged over (zero_point)
524 // - s_perm(x) and s_id(x) from vk_param.perm_oracle
525 // - alpha, beta, gamma from challenge
526
527 // we evaluate MLE directly instead of using s_id/s_perm PCS verify
528 // Verification takes n pairings while evaluate takes 2^n field ops.
529 let s_id = identity_permutation_mle::<E::Fr>(perm_check_point.len());
530 let s_id_eval = evaluate_opt(&s_id, perm_check_point);
531 let s_perm_eval = evaluate_opt(&vk.permutation_oracle, perm_check_point);
532
533 let q_x_rec = prod_evals[1] - prod_evals[2] * prod_evals[3]
534 + alpha
535 * ((prod_evals[0] + beta * s_perm_eval + gamma) * prod_evals[0]
536 - (prod_evals[0] + beta * s_id_eval + gamma));
537
538 if q_x_rec
539 != perm_check_sub_claim
540 .product_check_sub_claim
541 .zero_check_sub_claim
542 .expected_evaluation
543 {
544 return Err(HyperPlonkErrors::InvalidVerifier(
545 "evaluation failed".to_string(),
546 ));
547 }
548
549 end_timer!(step);
550 // =======================================================================
551 // 3. Verify the opening against the commitment
552 // =======================================================================
553 let step = start_timer!(|| "verify commitments");
554
555 // =======================================================================
556 // 3.1 open prod(x)' evaluations
557 // =======================================================================
558 // TODO: Check prod(x) at (1,...,1,0)
559 let _prod_final_query = perm_check_sub_claim.product_check_sub_claim.final_query;
560 let prod_points = [
561 [perm_check_point.as_slice(), &[E::Fr::zero()]].concat(),
562 [perm_check_point.as_slice(), &[E::Fr::one()]].concat(),
563 [&[E::Fr::zero()], perm_check_point.as_slice()].concat(),
564 [&[E::Fr::one()], perm_check_point.as_slice()].concat(),
565 // prod_final_query.0,
566 ];
567
568 let mut r_pi = transcript.get_and_append_challenge_vectors(b"r_pi", ell)?;
569
570 let res = PCS::batch_verify(
571 &vk.pcs_param,
572 [proof.perm_check_proof.prod_x_comm; 4].as_ref(),
573 prod_points.as_ref(),
574 &proof.batch_prod_x_openings,
575 &mut transcript,
576 )?;
577 assert!(res);
578
579 // =======================================================================
580 // 3.3 open witnesses' and selectors evaluations
581 // =======================================================================
582
583 let res = PCS::verify(
584 &vk.pcs_param,
585 &proof.witness_merged_commit,
586 perm_check_point,
587 &proof.perm_check_eval,
588 &proof.perm_check_opening,
589 )?;
590 assert!(res);
591
592 let pi_eval_rec = evaluate_opt(&pi_poly, &r_pi);
593 assert_eq!(&pi_eval_rec, pi_eval);
594
595 r_pi = [vec![E::Fr::zero(); num_vars - ell], r_pi].concat();
596 let commitments = [
597 proof.witness_commits.as_slice(),
598 vk.selector_commitments.as_slice(),
599 &[proof.witness_commits[0]],
600 ]
601 .concat();
602
603 let points = [
604 vec![zero_check_point.clone(); num_witnesses + num_selectors].as_slice(),
605 &[r_pi],
606 ]
607 .concat();
608
609 let res = PCS::batch_verify(
610 &vk.pcs_param,
611 commitments.as_ref(),
612 points.as_ref(),
613 &proof.batch_witness_and_selector_openings,
614 &mut transcript,
615 )?;
616
617 assert!(res);
618
619 end_timer!(step);
620 end_timer!(start);
621 Ok(true)
622 }
623}
624
625#[cfg(test)]
626mod tests {
627 use super::*;
628 use crate::{
629 custom_gate::CustomizedGates, selectors::SelectorColumn, structs::HyperPlonkParams,
630 witness::WitnessColumn,
631 };
632 use arithmetic::random_permutation_mle;
633 use ark_bls12_381::Bls12_381;
634 use ark_std::test_rng;
635 use subroutines::pcs::prelude::MultilinearKzgPCS;
636
637 #[test]
638 fn test_hyperplonk_e2e() -> Result<(), HyperPlonkErrors> {
639 // Example:
640 // q_L(X) * W_1(X)^5 - W_2(X) = 0
641 // is represented as
642 // vec![
643 // ( 1, Some(id_qL), vec![id_W1, id_W1, id_W1, id_W1, id_W1]),
644 // (-1, None, vec![id_W2])
645 // ]
646 //
647 // 4 public input
648 // 1 selector,
649 // 2 witnesses,
650 // 2 variables for MLE,
651 // 4 wires,
652 let gates = CustomizedGates {
653 gates: vec![(1, Some(0), vec![0, 0, 0, 0, 0]), (-1, None, vec![1])],
654 };
655 test_hyperplonk_helper::<Bls12_381>(gates)
656 }
657
658 fn test_hyperplonk_helper<E: PairingEngine>(
659 gate_func: CustomizedGates,
660 ) -> Result<(), HyperPlonkErrors> {
661 let mut rng = test_rng();
662 let pcs_srs = MultilinearKzgPCS::<E>::gen_srs_for_testing(&mut rng, 16)?;
663
664 let num_constraints = 4;
665 let num_pub_input = 4;
666 let nv = log2(num_constraints) as usize;
667 let merged_nv = nv + log2(gate_func.num_witness_columns()) as usize;
668
669 // generate index
670 let params = HyperPlonkParams {
671 num_constraints,
672 num_pub_input,
673 gate_func,
674 };
675 let permutation = identity_permutation_mle(merged_nv).evaluations.clone();
676 let q1 = SelectorColumn(vec![E::Fr::one(), E::Fr::one(), E::Fr::one(), E::Fr::one()]);
677 let index = HyperPlonkIndex {
678 params,
679 permutation,
680 selectors: vec![q1],
681 };
682
683 // generate pk and vks
684 let (pk, vk) = <PolyIOP<E::Fr> as HyperPlonkSNARK<E, MultilinearKzgPCS<E>>>::preprocess(
685 &index, &pcs_srs,
686 )?;
687
688 // w1 := [0, 1, 2, 3]
689 let w1 = WitnessColumn(vec![
690 E::Fr::zero(),
691 E::Fr::one(),
692 E::Fr::from(2u64),
693 E::Fr::from(3u64),
694 ]);
695 // w2 := [0^5, 1^5, 2^5, 3^5]
696 let w2 = WitnessColumn(vec![
697 E::Fr::zero(),
698 E::Fr::one(),
699 E::Fr::from(32u64),
700 E::Fr::from(243u64),
701 ]);
702 // public input = w1
703 let pi = w1.clone();
704
705 // generate a proof and verify
706 let proof = <PolyIOP<E::Fr> as HyperPlonkSNARK<E, MultilinearKzgPCS<E>>>::prove(
707 &pk,
708 &pi.0,
709 &[w1.clone(), w2.clone()],
710 )?;
711
712 let _verify = <PolyIOP<E::Fr> as HyperPlonkSNARK<E, MultilinearKzgPCS<E>>>::verify(
713 &vk, &pi.0, &proof,
714 )?;
715
716 // bad path 1: wrong permutation
717 let rand_perm: Vec<E::Fr> = random_permutation_mle(merged_nv, &mut rng)
718 .evaluations
719 .clone();
720 let mut bad_index = index.clone();
721 bad_index.permutation = rand_perm;
722 // generate pk and vks
723 let (_, bad_vk) = <PolyIOP<E::Fr> as HyperPlonkSNARK<E, MultilinearKzgPCS<E>>>::preprocess(
724 &bad_index, &pcs_srs,
725 )?;
726 assert!(
727 <PolyIOP<E::Fr> as HyperPlonkSNARK<E, MultilinearKzgPCS<E>>>::verify(
728 &bad_vk, &pi.0, &proof,
729 )
730 .is_err()
731 );
732
733 // bad path 2: wrong witness
734 let mut w1_bad = w1.clone();
735 w1_bad.0[0] = E::Fr::one();
736 assert!(
737 <PolyIOP<E::Fr> as HyperPlonkSNARK<E, MultilinearKzgPCS<E>>>::prove(
738 &pk,
739 &pi.0,
740 &[w1_bad, w2],
741 )
742 .is_err()
743 );
744
745 Ok(())
746 }
747}