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.sum_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 .sum_check_sub_claim
722 .point;
723
724 let alpha = perm_check_sub_claim.product_check_sub_claim.challenge;
725 let (beta, gamma) = perm_check_sub_claim.challenges;
726
727 // check perm check subclaim:
728 // proof.witness_perm_check_eval ?= perm_check_sub_claim.expected_eval
729 //
730 // Q(x) := prod(1,x) - prod(x, 0) * prod(x, 1)
731 // + alpha * (
732 // (g(x) + beta * s_perm(x) + gamma) * prod(0, x)
733 // - (f(x) + beta * s_id(x) + gamma))
734 // where
735 // - Q(x) is perm_check_sub_claim.zero_check.exp_eval
736 // - prod(1, x) ... from prod(x) evaluated over (1, zero_point)
737 // - g(x), f(x) are both w_merged over (zero_point)
738 // - s_perm(x) and s_id(x) from vk_param.perm_oracle
739 // - alpha, beta, gamma from challenge
740
741 let s_id = identity_permutation_mle::<E::Fr>(perm_check_point.len());
742 let s_id_eval = s_id.evaluate(perm_check_point).ok_or_else(|| {
743 HyperPlonkErrors::InvalidVerifier("unable to evaluate s_id(x)".to_string())
744 })?;
745
746 let q_x_rec = proof.prod_evals[1] - proof.prod_evals[2] * proof.prod_evals[3]
747 + alpha
748 * ((proof.witness_perm_check_eval + beta * proof.perm_oracle_eval + gamma)
749 * proof.prod_evals[0]
750 - (proof.witness_perm_check_eval + beta * s_id_eval + gamma));
751
752 if q_x_rec
753 != perm_check_sub_claim
754 .product_check_sub_claim
755 .zero_check_sub_claim
756 .expected_evaluation
757 {
758 return Err(HyperPlonkErrors::InvalidVerifier(
759 "evaluation failed".to_string(),
760 ));
761 }
762
763 end_timer!(step);
764 // =======================================================================
765 // 3. Verify the opening against the commitment
766 // =======================================================================
767 let step = start_timer!(|| "verify commitments");
768
769 // =======================================================================
770 // 3.1 check permutation check evaluations
771 // =======================================================================
772 // witness for permutation check
773 if !PCS::verify(
774 &vk.pcs_param,
775 &proof.w_merged_com,
776 perm_check_point,
777 &proof.witness_perm_check_eval,
778 &proof.witness_perm_check_opening,
779 )? {
780 return Err(HyperPlonkErrors::InvalidProof(
781 "pcs verification failed".to_string(),
782 ));
783 }
784
785 if !PCS::verify(
786 &vk.pcs_param,
787 &vk.perm_com,
788 perm_check_point,
789 &proof.perm_oracle_eval,
790 &proof.perm_oracle_opening,
791 )? {
792 return Err(HyperPlonkErrors::InvalidProof(
793 "pcs verification failed".to_string(),
794 ));
795 }
796
797 // prod(x) for permutation check
798 // TODO: batch verification
799
800 // prod(0, x)
801 if !PCS::verify(
802 &vk.pcs_param,
803 &proof.perm_check_proof.prod_x_comm,
804 &[perm_check_point.as_slice(), &[E::Fr::zero()]].concat(),
805 &proof.prod_evals[0],
806 &proof.prod_openings[0],
807 )? {
808 return Err(HyperPlonkErrors::InvalidProof(
809 "pcs verification failed".to_string(),
810 ));
811 }
812 // prod(1, x)
813 if !PCS::verify(
814 &vk.pcs_param,
815 &proof.perm_check_proof.prod_x_comm,
816 &[perm_check_point.as_slice(), &[E::Fr::one()]].concat(),
817 &proof.prod_evals[1],
818 &proof.prod_openings[1],
819 )? {
820 return Err(HyperPlonkErrors::InvalidProof(
821 "pcs verification failed".to_string(),
822 ));
823 }
824 // prod(x, 0)
825 if !PCS::verify(
826 &vk.pcs_param,
827 &proof.perm_check_proof.prod_x_comm,
828 &[&[E::Fr::zero()], perm_check_point.as_slice()].concat(),
829 &proof.prod_evals[2],
830 &proof.prod_openings[2],
831 )? {
832 return Err(HyperPlonkErrors::InvalidProof(
833 "pcs verification failed".to_string(),
834 ));
835 }
836 // prod(x, 1)
837 if !PCS::verify(
838 &vk.pcs_param,
839 &proof.perm_check_proof.prod_x_comm,
840 &[&[E::Fr::one()], perm_check_point.as_slice()].concat(),
841 &proof.prod_evals[3],
842 &proof.prod_openings[3],
843 )? {
844 return Err(HyperPlonkErrors::InvalidProof(
845 "pcs verification failed".to_string(),
846 ));
847 }
848
849 // =======================================================================
850 // 3.2 check zero check evaluations
851 // =======================================================================
852 // witness for zero check
853 // TODO: batch verification
854 for (commitment, (opening, eval)) in proof.witness_commits.iter().zip(
855 proof
856 .witness_zero_check_openings
857 .iter()
858 .zip(proof.witness_zero_check_evals.iter()),
859 ) {
860 if !PCS::verify(&vk.pcs_param, commitment, zero_check_point, eval, opening)? {
861 return Err(HyperPlonkErrors::InvalidProof(
862 "pcs verification failed".to_string(),
863 ));
864 }
865 }
866
867 // selector for zero check
868 // TODO: for now we only support a single selector polynomial
869 for (opening, eval) in proof
870 .selector_oracle_openings
871 .iter()
872 .zip(proof.selector_oracle_evals.iter())
873 {
874 if !PCS::verify(
875 &vk.pcs_param,
876 &vk.selector_com[0],
877 perm_check_point,
878 eval,
879 opening,
880 )? {
881 return Err(HyperPlonkErrors::InvalidProof(
882 "pcs verification failed".to_string(),
883 ));
884 }
885 }
886
887 // =======================================================================
888 // 3.3 public input consistency checks
889 // =======================================================================
890 let mut r_pi = transcript.get_and_append_challenge_vectors(b"r_pi", ell)?;
891 let pi_eval = pi_poly.evaluate(&r_pi).ok_or_else(|| {
892 HyperPlonkErrors::InvalidParameters("evaluation dimension does not match".to_string())
893 })?;
894 r_pi = [vec![E::Fr::zero(); num_var - ell], r_pi].concat();
895 if !PCS::verify(
896 &vk.pcs_param,
897 &proof.witness_commits[0],
898 &r_pi,
899 &pi_eval,
900 &proof.pi_opening,
901 )? {
902 return Err(HyperPlonkErrors::InvalidProof(
903 "pcs verification failed".to_string(),
904 ));
905 }
906
907 end_timer!(step);
908 end_timer!(start);
909 Ok(true)
910 }
911}
912
913#[cfg(test)]
914mod tests {
915 use super::*;
916 use crate::{selectors::SelectorColumn, structs::CustomizedGates, witness::WitnessColumn};
917 use ark_bls12_381::Bls12_381;
918 use ark_std::test_rng;
919 use pcs::prelude::KZGMultilinearPCS;
920 use poly_iop::prelude::random_permutation_mle;
921
922 #[test]
923 fn test_hyperplonk_e2e() -> Result<(), HyperPlonkErrors> {
924 // Example:
925 // q_L(X) * W_1(X)^5 - W_2(X) = 0
926 // is represented as
927 // vec![
928 // ( 1, Some(id_qL), vec![id_W1, id_W1, id_W1, id_W1, id_W1]),
929 // (-1, None, vec![id_W2])
930 // ]
931 //
932 // 4 public input
933 // 1 selector,
934 // 2 witnesses,
935 // 2 variables for MLE,
936 // 4 wires,
937 let gates = CustomizedGates {
938 gates: vec![(1, Some(0), vec![0, 0, 0, 0, 0]), (-1, None, vec![1])],
939 };
940 test_hyperplonk_helper::<Bls12_381>(2, 2, 0, 1, gates)
941 }
942
943 fn test_hyperplonk_helper<E: PairingEngine>(
944 nv: usize,
945 log_pub_input_len: usize,
946 log_n_selectors: usize,
947 log_n_wires: usize,
948 gate_func: CustomizedGates,
949 ) -> Result<(), HyperPlonkErrors> {
950 let mut rng = test_rng();
951 // system parameters
952 let params = HyperPlonkParams {
953 nv,
954 log_pub_input_len,
955 log_n_selectors,
956 log_n_wires,
957 gate_func,
958 };
959 let pcs_srs = KZGMultilinearPCS::<E>::gen_srs_for_testing(&mut rng, 15)?;
960 let merged_nv = nv + log_n_wires;
961
962 let s_perm = random_permutation_mle(merged_nv, &mut rng);
963
964 let q1 = SelectorColumn(vec![E::Fr::one(), E::Fr::one(), E::Fr::one(), E::Fr::one()]);
965 // w1 := [0, 1, 2, 3]
966 let w1 = WitnessColumn(vec![
967 E::Fr::zero(),
968 E::Fr::one(),
969 E::Fr::from(2u64),
970 E::Fr::from(3u64),
971 ]);
972 // w2 := [0^5, 1^5, 2^5, 3^5]
973 let w2 = WitnessColumn(vec![
974 E::Fr::zero(),
975 E::Fr::one(),
976 E::Fr::from(32u64),
977 E::Fr::from(243u64),
978 ]);
979 // public input = w1
980 let pi = w1.clone();
981
982 // generate pk and vks
983 let (pk, vk) = <PolyIOP<E::Fr> as HyperPlonkSNARK<E, KZGMultilinearPCS<E>>>::preprocess(
984 ¶ms,
985 &pcs_srs,
986 &s_perm.evaluations,
987 &[q1],
988 )?;
989
990 // generate a proof and verify
991 let proof = <PolyIOP<E::Fr> as HyperPlonkSNARK<E, KZGMultilinearPCS<E>>>::prove(
992 &pk,
993 &pi.0,
994 &[w1, w2],
995 )?;
996
997 let _sub_claim = <PolyIOP<E::Fr> as HyperPlonkSNARK<E, KZGMultilinearPCS<E>>>::verify(
998 &vk, &pi.0, &proof,
999 )?;
1000
1001 Ok(())
1002 }
1003}