hyperplonk/hyperplonk/src/lib.rs
hyperplonk/src/lib.rsRaw
1//! Main module for the HyperPlonk PolyIOP.
2
3use crate::utils::eval_f;
4use arithmetic::VPAuxInfo;
5use ark_ec::PairingEngine;
6use ark_poly::{DenseMultilinearExtension, MultilinearExtension};
7use ark_std::{end_timer, log2, start_timer, One, Zero};
8use errors::HyperPlonkErrors;
9use pcs::prelude::{compute_qx_degree, merge_polynomials, PCSErrors, PolynomialCommitmentScheme};
10use poly_iop::{
11 prelude::{identity_permutation_mle, PermutationCheck, ZeroCheck},
12 PolyIOP,
13};
14use selectors::SelectorColumn;
15use std::{marker::PhantomData, rc::Rc};
16use structs::{HyperPlonkParams, HyperPlonkProof, HyperPlonkProvingKey, HyperPlonkVerifyingKey};
17use transcript::IOPTranscript;
18use utils::build_f;
19use witness::WitnessColumn;
20
21mod errors;
22mod selectors;
23mod structs;
24mod utils;
25mod witness;
26
27/// A trait for HyperPlonk SNARKs.
28/// A HyperPlonk is derived from SumChecks, ZeroChecks and PermutationChecks.
29pub trait HyperPlonkSNARK<E, PCS>: PermutationCheck<E, PCS>
30where
31 E: PairingEngine,
32 PCS: PolynomialCommitmentScheme<E>,
33{
34 type Parameters;
35 type ProvingKey;
36 type VerifyingKey;
37 type Proof;
38
39 /// Generate the preprocessed polynomials output by the indexer.
40 ///
41 /// Inputs:
42 /// - `params`: HyperPlonk instance parameters
43 /// - `permutation`: the permutation for the copy constraints
44 /// - `selectors`: the list of selector vectors for custom gates
45 /// Outputs:
46 /// - The HyperPlonk proving key, which includes the preprocessed
47 /// polynomials.
48 fn preprocess(
49 params: &Self::Parameters,
50 pcs_srs: &PCS::SRS,
51 permutation: &[E::Fr],
52 selectors: &[SelectorColumn<E::Fr>],
53 ) -> Result<(Self::ProvingKey, Self::VerifyingKey), HyperPlonkErrors>;
54
55 /// Generate HyperPlonk SNARK proof.
56 ///
57 /// Inputs:
58 /// - `pk`: circuit proving key
59 /// - `pub_input`: online public input
60 /// - `witness`: witness assignment
61 /// Outputs:
62 /// - The HyperPlonk SNARK proof.
63 fn prove(
64 pk: &Self::ProvingKey,
65 pub_input: &[E::Fr],
66 witnesses: &[WitnessColumn<E::Fr>],
67 ) -> Result<Self::Proof, HyperPlonkErrors>;
68
69 /// Verify the HyperPlonk proof.
70 ///
71 /// Inputs:
72 /// - `params`: instance parameter
73 /// - `pub_input`: online public input
74 /// - `proof`: HyperPlonk SNARK proof challenges
75 /// Outputs:
76 /// - Return a boolean on whether the verification is successful
77 fn verify(
78 params: &Self::VerifyingKey,
79 pub_input: &[E::Fr],
80 proof: &Self::Proof,
81 ) -> Result<bool, HyperPlonkErrors>;
82}
83
84impl<E, PCS> HyperPlonkSNARK<E, PCS> for PolyIOP<E::Fr>
85where
86 E: PairingEngine,
87 // Ideally we want to access polynomial as PCS::Polynomial, instead of instantiating it here.
88 // But since PCS::Polynomial can be both univariate or multivariate in our implementation
89 // we cannot bound PCS::Polynomial with a property trait bound.
90 PCS: PolynomialCommitmentScheme<
91 E,
92 Polynomial = Rc<DenseMultilinearExtension<E::Fr>>,
93 Point = Vec<E::Fr>,
94 Evaluation = E::Fr,
95 >,
96{
97 type Parameters = HyperPlonkParams;
98 type ProvingKey = HyperPlonkProvingKey<E, PCS>;
99 type VerifyingKey = HyperPlonkVerifyingKey<E, PCS>;
100 type Proof = HyperPlonkProof<E, Self, PCS>;
101
102 /// Generate the preprocessed polynomials output by the indexer.
103 ///
104 /// Inputs:
105 /// - `params`: HyperPlonk instance parameters
106 /// - `permutation`: the permutation for the copy constraints
107 /// - `selectors`: the list of selector vectors for custom gates
108 /// Outputs:
109 /// - The HyperPlonk proving key, which includes the preprocessed
110 /// polynomials.
111 fn preprocess(
112 params: &Self::Parameters,
113 pcs_srs: &PCS::SRS,
114 permutation: &[E::Fr],
115 selectors: &[SelectorColumn<E::Fr>],
116 ) -> Result<(Self::ProvingKey, Self::VerifyingKey), HyperPlonkErrors> {
117 let num_vars = params.nv;
118 let log_num_witness_polys = params.log_n_wires;
119
120 // number of variables in merged polynomial for Multilinear-KZG
121 let merged_nv = num_vars + log_num_witness_polys;
122 // degree of q(x) for Univariate-KZG
123 let supported_uni_degree = compute_qx_degree(num_vars, 1 << log_num_witness_polys);
124
125 // extract PCS prover and verifier keys from SRS
126 let (pcs_prover_param, pcs_verifier_param) = PCS::trim(
127 pcs_srs,
128 log2(supported_uni_degree) as usize,
129 Some(merged_nv + 1),
130 )?;
131
132 // build permutation oracles
133 let permutation_oracles = Rc::new(DenseMultilinearExtension::from_evaluations_slice(
134 merged_nv,
135 permutation,
136 ));
137 let perm_com = PCS::commit(&pcs_prover_param, &permutation_oracles)?;
138
139 // build selector oracles and commit to it
140 let selector_oracles: Vec<Rc<DenseMultilinearExtension<E::Fr>>> = selectors
141 .iter()
142 .map(|s| Rc::new(DenseMultilinearExtension::from(s)))
143 .collect();
144
145 let selector_com = selector_oracles
146 .iter()
147 .map(|poly| PCS::commit(&pcs_prover_param, poly))
148 .collect::<Result<Vec<PCS::Commitment>, PCSErrors>>()?;
149
150 Ok((
151 Self::ProvingKey {
152 params: params.clone(),
153 permutation_oracles,
154 selector_oracles,
155 pcs_param: pcs_prover_param,
156 },
157 Self::VerifyingKey {
158 params: params.clone(),
159 pcs_param: pcs_verifier_param,
160 selector_com,
161 perm_com,
162 },
163 ))
164 }
165
166 /// Generate HyperPlonk SNARK proof.
167 ///
168 /// Inputs:
169 /// - `pk`: circuit proving key
170 /// - `pub_input`: online public input of length 2^\ell
171 /// - `witness`: witness assignment of length 2^n
172 /// Outputs:
173 /// - The HyperPlonk SNARK proof.
174 ///
175 /// Steps:
176 ///
177 /// 1. Commit Witness polynomials `w_i(x)` and append commitment to
178 /// transcript
179 ///
180 /// 2. Run ZeroCheck on
181 ///
182 /// `f(q_0(x),...q_l(x), w_0(x),...w_d(x))`
183 ///
184 /// where `f` is the constraint polynomial i.e.,
185 /// ```ignore
186 /// f(q_l, q_r, q_m, q_o, w_a, w_b, w_c)
187 /// = q_l w_a(x) + q_r w_b(x) + q_m w_a(x)w_b(x) - q_o w_c(x)
188 /// ```
189 /// in vanilla plonk, and obtain a ZeroCheckSubClaim
190 ///
191 /// 3. Run permutation check on `\{w_i(x)\}` and `permutation_oracles`, and
192 /// obtain a PermCheckSubClaim.
193 ///
194 /// 4. Generate evaluations and corresponding proofs
195 /// - permutation check evaluations and proofs
196 /// - zero check evaluations and proofs
197 /// - public input consistency checks
198 ///
199 /// TODO: this function is gigantic -- refactor it to smaller ones
200 fn prove(
201 pk: &Self::ProvingKey,
202 pub_input: &[E::Fr],
203 witnesses: &[WitnessColumn<E::Fr>],
204 ) -> Result<Self::Proof, HyperPlonkErrors> {
205 let start = start_timer!(|| "hyperplonk proving");
206 let mut transcript = IOPTranscript::<E::Fr>::new(b"hyperplonk");
207
208 // witness assignment of length 2^n
209 let num_vars = pk.params.nv;
210 let log_num_witness_polys = pk.params.log_n_wires;
211 // number of variables in merged polynomial for Multilinear-KZG
212 let merged_nv = num_vars + log_num_witness_polys;
213 // degree of q(x) for Univariate-KZG
214 let _supported_uni_degree = compute_qx_degree(num_vars, 1 << log_num_witness_polys);
215 // online public input of length 2^\ell
216 let ell = pk.params.log_pub_input_len;
217
218 let witness_polys: Vec<Rc<DenseMultilinearExtension<E::Fr>>> = witnesses
219 .iter()
220 .map(|w| Rc::new(DenseMultilinearExtension::from(w)))
221 .collect();
222 let pi_poly = Rc::new(DenseMultilinearExtension::from_evaluations_slice(
223 ell as usize,
224 pub_input,
225 ));
226
227 // =======================================================================
228 // 0. sanity checks
229 // =======================================================================
230 // public input length
231 if pub_input.len() != 1 << ell {
232 return Err(HyperPlonkErrors::InvalidProver(format!(
233 "Public input length is not correct: got {}, expect {}",
234 pub_input.len(),
235 1 << ell
236 )));
237 }
238 // witnesses length
239 for (i, w) in witnesses.iter().enumerate() {
240 if w.0.len() != 1 << num_vars {
241 return Err(HyperPlonkErrors::InvalidProver(format!(
242 "{}-th witness length is not correct: got {}, expect {}",
243 i,
244 pub_input.len(),
245 1 << ell
246 )));
247 }
248 }
249 // check public input matches witness[0]'s first 2^ell elements
250 let pi_in_w0 =
251 Rc::new(witness_polys[0].fix_variables(vec![E::Fr::zero(); num_vars - ell].as_ref()));
252
253 if pi_in_w0 != pi_poly {
254 return Err(HyperPlonkErrors::InvalidProver(format!(
255 "Public input {:?} does not match witness[0] {:?}",
256 pi_poly, pi_in_w0,
257 )));
258 }
259 // =======================================================================
260 // 1. Commit Witness polynomials `w_i(x)` and append commitment to
261 // transcript
262 // =======================================================================
263 let step = start_timer!(|| "commit witnesses");
264 let mut witness_commits = vec![];
265 // TODO: batch commit
266 for wi_poly in witness_polys.iter() {
267 let wi_com = PCS::commit(&pk.pcs_param, wi_poly)?;
268 witness_commits.push(wi_com);
269 }
270
271 let w_merged = merge_polynomials(&witness_polys)?;
272 if w_merged.num_vars != merged_nv {
273 return Err(HyperPlonkErrors::InvalidParameters(format!(
274 "merged witness poly has a different num_var ({}) from expected ({})",
275 w_merged.num_vars, merged_nv
276 )));
277 }
278 let w_merged_com = PCS::commit(&pk.pcs_param, &w_merged)?;
279
280 transcript.append_serializable_element(b"w", &w_merged_com)?;
281 end_timer!(step);
282
283 // =======================================================================
284 // 2 Run ZeroCheck on
285 //
286 // `f(q_0(x),...q_l(x), w_0(x),...w_d(x))`
287 //
288 // where `f` is the constraint polynomial i.e.,
289 //
290 // f(q_l, q_r, q_m, q_o, w_a, w_b, w_c)
291 // = q_l w_a(x) + q_r w_b(x) + q_m w_a(x)w_b(x) - q_o w_c(x)
292 //
293 // in vanilla plonk, and obtain a ZeroCheckSubClaim
294 // =======================================================================
295 let step = start_timer!(|| "ZeroCheck on f");
296
297 let fx = build_f(
298 &pk.params.gate_func,
299 pk.params.nv,
300 &pk.selector_oracles,
301 &witness_polys,
302 )?;
303
304 let zero_check_proof = <Self as ZeroCheck<E::Fr>>::prove(&fx, &mut transcript)?;
305 end_timer!(step);
306
307 // =======================================================================
308 // 3. Run permutation check on `\{w_i(x)\}` and `permutation_oracles`, and
309 // obtain a PermCheckSubClaim.
310 // =======================================================================
311 let step = start_timer!(|| "Permutation check on w_i(x)");
312
313 let (perm_check_proof, prod_x) = <Self as PermutationCheck<E, PCS>>::prove(
314 &pk.pcs_param,
315 &w_merged,
316 &w_merged,
317 &pk.permutation_oracles,
318 &mut transcript,
319 )?;
320
321 // open prod(0,x), prod(1, x), prod(x, 0), prod(x, 1) at zero_check.point
322 // prod(0, x)
323 let tmp_point = [
324 perm_check_proof.zero_check_proof.point.as_slice(),
325 &[E::Fr::zero()],
326 ]
327 .concat();
328 let (prod_0_x_opening, prod_0_x_eval) = PCS::open(&pk.pcs_param, &prod_x, &tmp_point)?;
329 #[cfg(feature = "extensive_sanity_checks")]
330 {
331 // sanity check
332 let eval = prod_x.evaluate(&tmp_point).ok_or_else(|| {
333 HyperPlonkErrors::InvalidParameters(
334 "evaluation dimension does not match".to_string(),
335 )
336 })?;
337 if eval != prod_0_x_eval {
338 return Err(HyperPlonkErrors::InvalidProver(
339 "Evaluation is different from PCS opening".to_string(),
340 ));
341 }
342 }
343 // prod(1, x)
344 let tmp_point = [
345 perm_check_proof.zero_check_proof.point.as_slice(),
346 &[E::Fr::one()],
347 ]
348 .concat();
349 let (prod_1_x_opening, prod_1_x_eval) = PCS::open(&pk.pcs_param, &prod_x, &tmp_point)?;
350 #[cfg(feature = "extensive_sanity_checks")]
351 {
352 // sanity check
353 let eval = prod_x.evaluate(&tmp_point).ok_or_else(|| {
354 HyperPlonkErrors::InvalidParameters(
355 "evaluation dimension does not match".to_string(),
356 )
357 })?;
358 if eval != prod_1_x_eval {
359 return Err(HyperPlonkErrors::InvalidProver(
360 "Evaluation is different from PCS opening".to_string(),
361 ));
362 }
363 }
364 // prod(x, 0)
365 let tmp_point = [
366 &[E::Fr::zero()],
367 perm_check_proof.zero_check_proof.point.as_slice(),
368 ]
369 .concat();
370 let (prod_x_0_opening, prod_x_0_eval) = PCS::open(&pk.pcs_param, &prod_x, &tmp_point)?;
371 #[cfg(feature = "extensive_sanity_checks")]
372 {
373 // sanity check
374 let eval = prod_x.evaluate(&tmp_point).ok_or_else(|| {
375 HyperPlonkErrors::InvalidParameters(
376 "evaluation dimension does not match".to_string(),
377 )
378 })?;
379
380 if eval != prod_x_0_eval {
381 return Err(HyperPlonkErrors::InvalidProver(
382 "Evaluation is different from PCS opening".to_string(),
383 ));
384 }
385 }
386 // prod(x, 1)
387 let tmp_point = [
388 &[E::Fr::one()],
389 perm_check_proof.zero_check_proof.point.as_slice(),
390 ]
391 .concat();
392 let (prod_x_1_opening, prod_x_1_eval) = PCS::open(&pk.pcs_param, &prod_x, &tmp_point)?;
393 #[cfg(feature = "extensive_sanity_checks")]
394 {
395 // sanity check
396 let eval = prod_x.evaluate(&tmp_point).ok_or_else(|| {
397 HyperPlonkErrors::InvalidParameters(
398 "evaluation dimension does not match".to_string(),
399 )
400 })?;
401 if eval != prod_x_1_eval {
402 return Err(HyperPlonkErrors::InvalidProver(
403 "Evaluation is different from PCS opening".to_string(),
404 ));
405 }
406 }
407 end_timer!(step);
408
409 // =======================================================================
410 // 4. Generate evaluations and corresponding proofs
411 // - permutation check evaluations and proofs
412 // - wi_poly(r_perm_check) where r_perm_check is from perm_check_proof
413 // - selector_poly(r_perm_check)
414 //
415 // - zero check evaluations and proofs
416 // - wi_poly(r_zero_check) where r_zero_check is from zero_check_proof
417 // - selector_poly(r_zero_check)
418 //
419 // - public input consistency checks
420 // - pi_poly(r_pi) where r_pi is sampled from transcript
421 // =======================================================================
422 let step = start_timer!(|| "opening and evaluations");
423
424 // 4.1 permutation check
425 let mut witness_zero_check_evals = vec![];
426 let mut witness_zero_check_openings = vec![];
427 // TODO: parallelization
428 // TODO: Batch opening
429
430 // open permutation check proof
431 let (witness_perm_check_opening, witness_perm_check_eval) = PCS::open(
432 &pk.pcs_param,
433 &w_merged,
434 &perm_check_proof.zero_check_proof.point,
435 )?;
436
437 #[cfg(feature = "extensive_sanity_checks")]
438 {
439 // sanity checks
440 let eval = w_merged
441 .evaluate(&perm_check_proof.zero_check_proof.point)
442 .ok_or_else(|| {
443 HyperPlonkErrors::InvalidParameters(
444 "evaluation dimension does not match".to_string(),
445 )
446 })?;
447 if eval != witness_perm_check_eval {
448 return Err(HyperPlonkErrors::InvalidProver(
449 "Evaluation is different from PCS opening".to_string(),
450 ));
451 }
452 }
453
454 // 4.2 open zero check proof
455 // TODO: batch opening
456 for wire_poly in witness_polys {
457 // Open zero check proof
458 let (zero_proof, zero_eval) =
459 PCS::open(&pk.pcs_param, &wire_poly, &zero_check_proof.point)?;
460 {
461 let eval = wire_poly.evaluate(&zero_check_proof.point).ok_or_else(|| {
462 HyperPlonkErrors::InvalidParameters(
463 "evaluation dimension does not match".to_string(),
464 )
465 })?;
466 if eval != zero_eval {
467 return Err(HyperPlonkErrors::InvalidProver(
468 "Evaluation is different from PCS opening".to_string(),
469 ));
470 }
471 }
472 witness_zero_check_evals.push(zero_eval);
473 witness_zero_check_openings.push(zero_proof);
474 }
475
476 // Open permutation polynomial at perm_check_point
477 let (s_perm_opening, s_perm_eval) = PCS::open(
478 &pk.pcs_param,
479 &pk.permutation_oracles,
480 &perm_check_proof.zero_check_proof.point,
481 )?;
482
483 #[cfg(feature = "extensive_sanity_checks")]
484 {
485 // sanity check
486 let eval = pk
487 .permutation_oracles
488 .evaluate(&perm_check_proof.zero_check_proof.point)
489 .ok_or_else(|| {
490 HyperPlonkErrors::InvalidParameters(
491 "evaluation dimension does not match".to_string(),
492 )
493 })?;
494 if eval != s_perm_eval {
495 return Err(HyperPlonkErrors::InvalidProver(
496 "Evaluation is different from PCS opening".to_string(),
497 ));
498 }
499 }
500
501 // Open selector polynomial at zero_check_point
502 let mut selector_oracle_openings = vec![];
503 let mut selector_oracle_evals = vec![];
504
505 // TODO: parallelization
506 for selector_poly in pk.selector_oracles.iter() {
507 // Open zero check proof
508 // during verification, use this eval against subclaim
509 let (zero_proof, zero_eval) =
510 PCS::open(&pk.pcs_param, selector_poly, &zero_check_proof.point)?;
511
512 #[cfg(feature = "extensive_sanity_checks")]
513 {
514 let eval = selector_poly
515 .evaluate(&zero_check_proof.point)
516 .ok_or_else(|| {
517 HyperPlonkErrors::InvalidParameters(
518 "evaluation dimension does not match".to_string(),
519 )
520 })?;
521 if eval != zero_eval {
522 return Err(HyperPlonkErrors::InvalidProver(
523 "Evaluation is different from PCS opening".to_string(),
524 ));
525 }
526 }
527 selector_oracle_openings.push(zero_proof);
528 selector_oracle_evals.push(zero_eval);
529 }
530
531 // 4.3 public input consistency checks
532 let r_pi = transcript.get_and_append_challenge_vectors(b"r_pi", ell)?;
533
534 let (pi_opening, pi_eval) = PCS::open(&pk.pcs_param, &pi_in_w0, &r_pi)?;
535
536 #[cfg(feature = "extensive_sanity_checks")]
537 {
538 // sanity check
539 let eval = pi_poly.evaluate(&r_pi).ok_or_else(|| {
540 HyperPlonkErrors::InvalidParameters(
541 "evaluation dimension does not match".to_string(),
542 )
543 })?;
544 if eval != pi_eval {
545 return Err(HyperPlonkErrors::InvalidProver(
546 "Evaluation is different from PCS opening".to_string(),
547 ));
548 }
549 }
550
551 end_timer!(step);
552 end_timer!(start);
553
554 Ok(HyperPlonkProof {
555 // =======================================================================
556 // PCS components: common
557 // =======================================================================
558 witness_commits,
559 w_merged_com,
560 // =======================================================================
561 // PCS components: permutation check
562 // =======================================================================
563 // We do not validate prod(x), this is checked by subclaim
564 prod_evals: vec![prod_0_x_eval, prod_1_x_eval, prod_x_0_eval, prod_x_1_eval],
565 prod_openings: vec![
566 prod_0_x_opening,
567 prod_1_x_opening,
568 prod_x_0_opening,
569 prod_x_1_opening,
570 ],
571 witness_perm_check_opening,
572 witness_perm_check_eval,
573 perm_oracle_opening: s_perm_opening,
574 perm_oracle_eval: s_perm_eval,
575 // =======================================================================
576 // PCS components: zero check
577 // =======================================================================
578 witness_zero_check_openings,
579 witness_zero_check_evals,
580 selector_oracle_openings,
581 selector_oracle_evals,
582 // =======================================================================
583 // PCS components: public inputs
584 // =======================================================================
585 pi_eval,
586 pi_opening,
587 // =======================================================================
588 // IOP components
589 // =======================================================================
590 zero_check_proof,
591 perm_check_proof,
592 })
593 }
594
595 /// Verify the HyperPlonk proof.
596 ///
597 /// Inputs:
598 /// - `vk`: verification key
599 /// - `pub_input`: online public input
600 /// - `proof`: HyperPlonk SNARK proof
601 /// Outputs:
602 /// - Return a boolean on whether the verification is successful
603 ///
604 /// 1. Verify zero_check_proof on
605 ///
606 /// `f(q_0(x),...q_l(x), w_0(x),...w_d(x))`
607 ///
608 /// where `f` is the constraint polynomial i.e.,
609 /// ```ignore
610 /// f(q_l, q_r, q_m, q_o, w_a, w_b, w_c)
611 /// = q_l w_a(x) + q_r w_b(x) + q_m w_a(x)w_b(x) - q_o w_c(x)
612 /// ```
613 /// in vanilla plonk, and obtain a ZeroCheckSubClaim
614 ///
615 /// 2. Verify perm_check_proof on `\{w_i(x)\}` and `permutation_oracles`
616 ///
617 /// 3. Verify the opening against the commitment:
618 /// - check permutation check evaluations
619 /// - check zero check evaluations
620 /// - public input consistency checks
621 /// 4. check subclaim validity // todo
622 fn verify(
623 vk: &Self::VerifyingKey,
624 pub_input: &[E::Fr],
625 proof: &Self::Proof,
626 ) -> Result<bool, HyperPlonkErrors> {
627 let start = start_timer!(|| "hyperplonk verification");
628
629 let mut transcript = IOPTranscript::<E::Fr>::new(b"hyperplonk");
630 // witness assignment of length 2^n
631 let num_var = vk.params.nv;
632 let log_num_witness_polys = vk.params.log_n_wires;
633 // number of variables in merged polynomial for Multilinear-KZG
634 let merged_nv = num_var + log_num_witness_polys;
635
636 // online public input of length 2^\ell
637 let ell = vk.params.log_pub_input_len;
638
639 let pi_poly = DenseMultilinearExtension::from_evaluations_slice(ell as usize, pub_input);
640
641 // =======================================================================
642 // 0. sanity checks
643 // =======================================================================
644 // public input length
645 if pub_input.len() != 1 << ell {
646 return Err(HyperPlonkErrors::InvalidProver(format!(
647 "Public input length is not correct: got {}, expect {}",
648 pub_input.len(),
649 1 << ell
650 )));
651 }
652
653 // =======================================================================
654 // 1. Verify zero_check_proof on
655 // `f(q_0(x),...q_l(x), w_0(x),...w_d(x))`
656 //
657 // where `f` is the constraint polynomial i.e.,
658 //
659 // f(q_l, q_r, q_m, q_o, w_a, w_b, w_c)
660 // = q_l w_a(x) + q_r w_b(x) + q_m w_a(x)w_b(x) - q_o w_c(x)
661 //
662 // =======================================================================
663 let step = start_timer!(|| "verify zero check");
664 // Zero check and sum check have different AuxInfo because `w_merged` and
665 // `Prod(x)` have degree and num_vars
666 let zero_check_aux_info = VPAuxInfo::<E::Fr> {
667 // TODO: get the real max degree from gate_func
668 // Here we use 6 is because the test has q[0] * w[0]^5 which is degree 6
669 max_degree: 6,
670 num_variables: num_var,
671 phantom: PhantomData::default(),
672 };
673
674 // push witness to transcript
675 transcript.append_serializable_element(b"w", &proof.w_merged_com)?;
676
677 let zero_check_sub_claim = <Self as ZeroCheck<E::Fr>>::verify(
678 &proof.zero_check_proof,
679 &zero_check_aux_info,
680 &mut transcript,
681 )?;
682
683 let zero_check_point = &zero_check_sub_claim.point;
684
685 // check zero check subclaim
686 let f_eval = eval_f(
687 &vk.params.gate_func,
688 &proof.selector_oracle_evals,
689 &proof.witness_zero_check_evals,
690 )?;
691 if f_eval != zero_check_sub_claim.expected_evaluation {
692 return Err(HyperPlonkErrors::InvalidProof(
693 "zero check evaluation failed".to_string(),
694 ));
695 }
696
697 end_timer!(step);
698 // =======================================================================
699 // 2. Verify perm_check_proof on `\{w_i(x)\}` and `permutation_oracles`
700 // =======================================================================
701 let step = start_timer!(|| "verify permutation check");
702
703 // Zero check and sum check have different AuxInfo because `w_merged` and
704 // `Prod(x)` have degree and num_vars
705 let perm_check_aux_info = VPAuxInfo::<E::Fr> {
706 // Prod(x) has a max degree of 2
707 max_degree: 2,
708 // degree of merged poly
709 num_variables: merged_nv,
710 phantom: PhantomData::default(),
711 };
712 let perm_check_sub_claim = <Self as PermutationCheck<E, PCS>>::verify(
713 &proof.perm_check_proof,
714 &perm_check_aux_info,
715 &mut transcript,
716 )?;
717
718 let perm_check_point = &perm_check_sub_claim
719 .product_check_sub_claim
720 .zero_check_sub_claim
721 .point;
722
723 let alpha = perm_check_sub_claim.product_check_sub_claim.alpha;
724 let (beta, gamma) = perm_check_sub_claim.challenges;
725
726 // check perm check subclaim:
727 // proof.witness_perm_check_eval ?= perm_check_sub_claim.expected_eval
728 //
729 // Q(x) := prod(1,x) - prod(x, 0) * prod(x, 1)
730 // + alpha * (
731 // (g(x) + beta * s_perm(x) + gamma) * prod(0, x)
732 // - (f(x) + beta * s_id(x) + gamma))
733 // where
734 // - Q(x) is perm_check_sub_claim.zero_check.exp_eval
735 // - prod(1, x) ... from prod(x) evaluated over (1, zero_point)
736 // - g(x), f(x) are both w_merged over (zero_point)
737 // - s_perm(x) and s_id(x) from vk_param.perm_oracle
738 // - alpha, beta, gamma from challenge
739
740 let s_id = identity_permutation_mle::<E::Fr>(perm_check_point.len());
741 let s_id_eval = s_id.evaluate(perm_check_point).ok_or_else(|| {
742 HyperPlonkErrors::InvalidVerifier("unable to evaluate s_id(x)".to_string())
743 })?;
744
745 let q_x_rec = proof.prod_evals[1] - proof.prod_evals[2] * proof.prod_evals[3]
746 + alpha
747 * ((proof.witness_perm_check_eval + beta * proof.perm_oracle_eval + gamma)
748 * proof.prod_evals[0]
749 - (proof.witness_perm_check_eval + beta * s_id_eval + gamma));
750
751 if q_x_rec
752 != perm_check_sub_claim
753 .product_check_sub_claim
754 .zero_check_sub_claim
755 .expected_evaluation
756 {
757 return Err(HyperPlonkErrors::InvalidVerifier(
758 "evaluation failed".to_string(),
759 ));
760 }
761
762 end_timer!(step);
763 // =======================================================================
764 // 3. Verify the opening against the commitment
765 // =======================================================================
766 let step = start_timer!(|| "verify commitments");
767
768 // =======================================================================
769 // 3.1 check permutation check evaluations
770 // =======================================================================
771 // witness for permutation check
772 if !PCS::verify(
773 &vk.pcs_param,
774 &proof.w_merged_com,
775 perm_check_point,
776 &proof.witness_perm_check_eval,
777 &proof.witness_perm_check_opening,
778 )? {
779 return Err(HyperPlonkErrors::InvalidProof(
780 "pcs verification failed".to_string(),
781 ));
782 }
783
784 if !PCS::verify(
785 &vk.pcs_param,
786 &vk.perm_com,
787 perm_check_point,
788 &proof.perm_oracle_eval,
789 &proof.perm_oracle_opening,
790 )? {
791 return Err(HyperPlonkErrors::InvalidProof(
792 "pcs verification failed".to_string(),
793 ));
794 }
795
796 // prod(x) for permutation check
797 // TODO: batch verification
798
799 // prod(0, x)
800 if !PCS::verify(
801 &vk.pcs_param,
802 &proof.perm_check_proof.prod_x_comm,
803 &[perm_check_point.as_slice(), &[E::Fr::zero()]].concat(),
804 &proof.prod_evals[0],
805 &proof.prod_openings[0],
806 )? {
807 return Err(HyperPlonkErrors::InvalidProof(
808 "pcs verification failed".to_string(),
809 ));
810 }
811 // prod(1, x)
812 if !PCS::verify(
813 &vk.pcs_param,
814 &proof.perm_check_proof.prod_x_comm,
815 &[perm_check_point.as_slice(), &[E::Fr::one()]].concat(),
816 &proof.prod_evals[1],
817 &proof.prod_openings[1],
818 )? {
819 return Err(HyperPlonkErrors::InvalidProof(
820 "pcs verification failed".to_string(),
821 ));
822 }
823 // prod(x, 0)
824 if !PCS::verify(
825 &vk.pcs_param,
826 &proof.perm_check_proof.prod_x_comm,
827 &[&[E::Fr::zero()], perm_check_point.as_slice()].concat(),
828 &proof.prod_evals[2],
829 &proof.prod_openings[2],
830 )? {
831 return Err(HyperPlonkErrors::InvalidProof(
832 "pcs verification failed".to_string(),
833 ));
834 }
835 // prod(x, 1)
836 if !PCS::verify(
837 &vk.pcs_param,
838 &proof.perm_check_proof.prod_x_comm,
839 &[&[E::Fr::one()], perm_check_point.as_slice()].concat(),
840 &proof.prod_evals[3],
841 &proof.prod_openings[3],
842 )? {
843 return Err(HyperPlonkErrors::InvalidProof(
844 "pcs verification failed".to_string(),
845 ));
846 }
847
848 // =======================================================================
849 // 3.2 check zero check evaluations
850 // =======================================================================
851 // witness for zero check
852 // TODO: batch verification
853 for (commitment, (opening, eval)) in proof.witness_commits.iter().zip(
854 proof
855 .witness_zero_check_openings
856 .iter()
857 .zip(proof.witness_zero_check_evals.iter()),
858 ) {
859 if !PCS::verify(&vk.pcs_param, commitment, zero_check_point, eval, opening)? {
860 return Err(HyperPlonkErrors::InvalidProof(
861 "pcs verification failed".to_string(),
862 ));
863 }
864 }
865
866 // selector for zero check
867 // TODO: for now we only support a single selector polynomial
868 for (opening, eval) in proof
869 .selector_oracle_openings
870 .iter()
871 .zip(proof.selector_oracle_evals.iter())
872 {
873 if !PCS::verify(
874 &vk.pcs_param,
875 &vk.selector_com[0],
876 perm_check_point,
877 eval,
878 opening,
879 )? {
880 return Err(HyperPlonkErrors::InvalidProof(
881 "pcs verification failed".to_string(),
882 ));
883 }
884 }
885
886 // =======================================================================
887 // 3.3 public input consistency checks
888 // =======================================================================
889 let mut r_pi = transcript.get_and_append_challenge_vectors(b"r_pi", ell)?;
890 let pi_eval = pi_poly.evaluate(&r_pi).ok_or_else(|| {
891 HyperPlonkErrors::InvalidParameters("evaluation dimension does not match".to_string())
892 })?;
893 r_pi = [vec![E::Fr::zero(); num_var - ell], r_pi].concat();
894 if !PCS::verify(
895 &vk.pcs_param,
896 &proof.witness_commits[0],
897 &r_pi,
898 &pi_eval,
899 &proof.pi_opening,
900 )? {
901 return Err(HyperPlonkErrors::InvalidProof(
902 "pcs verification failed".to_string(),
903 ));
904 }
905
906 end_timer!(step);
907 end_timer!(start);
908 Ok(true)
909 }
910}
911
912#[cfg(test)]
913mod tests {
914 use super::*;
915 use crate::{selectors::SelectorColumn, structs::CustomizedGates, witness::WitnessColumn};
916 use ark_bls12_381::Bls12_381;
917 use ark_std::test_rng;
918 use pcs::prelude::KZGMultilinearPCS;
919 use poly_iop::prelude::random_permutation_mle;
920
921 #[test]
922 fn test_hyperplonk_e2e() -> Result<(), HyperPlonkErrors> {
923 // Example:
924 // q_L(X) * W_1(X)^5 - W_2(X) = 0
925 // is represented as
926 // vec![
927 // ( 1, Some(id_qL), vec![id_W1, id_W1, id_W1, id_W1, id_W1]),
928 // (-1, None, vec![id_W2])
929 // ]
930 //
931 // 4 public input
932 // 1 selector,
933 // 2 witnesses,
934 // 2 variables for MLE,
935 // 4 wires,
936 let gates = CustomizedGates {
937 gates: vec![(1, Some(0), vec![0, 0, 0, 0, 0]), (-1, None, vec![1])],
938 };
939 test_hyperplonk_helper::<Bls12_381>(2, 2, 0, 1, gates)
940 }
941
942 fn test_hyperplonk_helper<E: PairingEngine>(
943 nv: usize,
944 log_pub_input_len: usize,
945 log_n_selectors: usize,
946 log_n_wires: usize,
947 gate_func: CustomizedGates,
948 ) -> Result<(), HyperPlonkErrors> {
949 let mut rng = test_rng();
950 // system parameters
951 let params = HyperPlonkParams {
952 nv,
953 log_pub_input_len,
954 log_n_selectors,
955 log_n_wires,
956 gate_func,
957 };
958 let pcs_srs = KZGMultilinearPCS::<E>::gen_srs_for_testing(&mut rng, 15)?;
959 let merged_nv = nv + log_n_wires;
960
961 let s_perm = random_permutation_mle(merged_nv, &mut rng);
962
963 let q1 = SelectorColumn(vec![E::Fr::one(), E::Fr::one(), E::Fr::one(), E::Fr::one()]);
964 // w1 := [0, 1, 2, 3]
965 let w1 = WitnessColumn(vec![
966 E::Fr::zero(),
967 E::Fr::one(),
968 E::Fr::from(2u64),
969 E::Fr::from(3u64),
970 ]);
971 // w2 := [0^5, 1^5, 2^5, 3^5]
972 let w2 = WitnessColumn(vec![
973 E::Fr::zero(),
974 E::Fr::one(),
975 E::Fr::from(32u64),
976 E::Fr::from(243u64),
977 ]);
978 // public input = w1
979 let pi = w1.clone();
980
981 // generate pk and vks
982 let (pk, vk) = <PolyIOP<E::Fr> as HyperPlonkSNARK<E, KZGMultilinearPCS<E>>>::preprocess(
983 ¶ms,
984 &pcs_srs,
985 &s_perm.evaluations,
986 &[q1],
987 )?;
988
989 // generate a proof and verify
990 let proof = <PolyIOP<E::Fr> as HyperPlonkSNARK<E, KZGMultilinearPCS<E>>>::prove(
991 &pk,
992 &pi.0,
993 &[w1, w2],
994 )?;
995
996 let _sub_claim = <PolyIOP<E::Fr> as HyperPlonkSNARK<E, KZGMultilinearPCS<E>>>::verify(
997 &vk, &pi.0, &proof,
998 )?;
999
1000 Ok(())
1001 }
1002}