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