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