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