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