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