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