hyperplonk/hyperplonk/src/snark.rs
hyperplonk/src/snark.rsRaw
1// Copyright (c) 2023 Espresso Systems (espressosys.com)
2// This file is part of the HyperPlonk library.
3
4// You should have received a copy of the MIT License
5// along with the HyperPlonk library. If not, see <https://mit-license.org/>.
6
7use crate::{
8 errors::HyperPlonkErrors,
9 structs::{HyperPlonkIndex, HyperPlonkProof, HyperPlonkProvingKey, HyperPlonkVerifyingKey},
10 utils::{build_f, eval_f, eval_perm_gate, prover_sanity_check, PcsAccumulator},
11 witness::WitnessColumn,
12 HyperPlonkSNARK,
13};
14use arithmetic::{evaluate_opt, gen_eval_point, VPAuxInfo};
15use ark_ec::pairing::Pairing;
16use ark_poly::DenseMultilinearExtension;
17use ark_std::{end_timer, log2, start_timer, One, Zero};
18use rayon::iter::IntoParallelRefIterator;
19#[cfg(feature = "parallel")]
20use rayon::iter::ParallelIterator;
21use std::{marker::PhantomData, sync::Arc};
22use subroutines::{
23 pcs::prelude::{Commitment, PolynomialCommitmentScheme},
24 poly_iop::{
25 prelude::{PermutationCheck, ZeroCheck},
26 PolyIOP,
27 },
28 BatchProof,
29};
30use transcript::IOPTranscript;
31
32impl<E, PCS> HyperPlonkSNARK<E, PCS> for PolyIOP<E::ScalarField>
33where
34 E: Pairing,
35 // Ideally we want to access polynomial as PCS::Polynomial, instead of instantiating it here.
36 // But since PCS::Polynomial can be both univariate or multivariate in our implementation
37 // we cannot bound PCS::Polynomial with a property trait bound.
38 PCS: PolynomialCommitmentScheme<
39 E,
40 Polynomial = Arc<DenseMultilinearExtension<E::ScalarField>>,
41 Point = Vec<E::ScalarField>,
42 Evaluation = E::ScalarField,
43 Commitment = Commitment<E>,
44 BatchProof = BatchProof<E, PCS>,
45 >,
46{
47 type Index = HyperPlonkIndex<E::ScalarField>;
48 type ProvingKey = HyperPlonkProvingKey<E, PCS>;
49 type VerifyingKey = HyperPlonkVerifyingKey<E, PCS>;
50 type Proof = HyperPlonkProof<E, Self, PCS>;
51
52 fn preprocess(
53 index: &Self::Index,
54 pcs_srs: &PCS::SRS,
55 ) -> Result<(Self::ProvingKey, Self::VerifyingKey), HyperPlonkErrors> {
56 let num_vars = index.num_variables();
57 let supported_ml_degree = num_vars;
58
59 // extract PCS prover and verifier keys from SRS
60 let (pcs_prover_param, pcs_verifier_param) =
61 PCS::trim(pcs_srs, None, Some(supported_ml_degree))?;
62
63 // build permutation oracles
64 let mut permutation_oracles = vec![];
65 let mut perm_comms = vec![];
66 let chunk_size = 1 << num_vars;
67 for i in 0..index.num_witness_columns() {
68 let perm_oracle = Arc::new(DenseMultilinearExtension::from_evaluations_slice(
69 num_vars,
70 &index.permutation[i * chunk_size..(i + 1) * chunk_size],
71 ));
72 let perm_comm = PCS::commit(&pcs_prover_param, &perm_oracle)?;
73 permutation_oracles.push(perm_oracle);
74 perm_comms.push(perm_comm);
75 }
76
77 // build selector oracles and commit to it
78 let selector_oracles: Vec<Arc<DenseMultilinearExtension<E::ScalarField>>> = index
79 .selectors
80 .iter()
81 .map(|s| Arc::new(DenseMultilinearExtension::from(s)))
82 .collect();
83
84 let selector_commitments = selector_oracles
85 .par_iter()
86 .map(|poly| PCS::commit(&pcs_prover_param, poly))
87 .collect::<Result<Vec<_>, _>>()?;
88
89 Ok((
90 Self::ProvingKey {
91 params: index.params.clone(),
92 permutation_oracles,
93 selector_oracles,
94 selector_commitments: selector_commitments.clone(),
95 permutation_commitments: perm_comms.clone(),
96 pcs_param: pcs_prover_param,
97 },
98 Self::VerifyingKey {
99 params: index.params.clone(),
100 pcs_param: pcs_verifier_param,
101 selector_commitments,
102 perm_commitments: perm_comms,
103 },
104 ))
105 }
106
107 /// Generate HyperPlonk SNARK proof.
108 ///
109 /// Inputs:
110 /// - `pk`: circuit proving key
111 /// - `pub_input`: online public input of length 2^\ell
112 /// - `witness`: witness assignment of length 2^n
113 /// Outputs:
114 /// - The HyperPlonk SNARK proof.
115 ///
116 /// Steps:
117 ///
118 /// 1. Commit Witness polynomials `w_i(x)` and append commitment to
119 /// transcript
120 ///
121 /// 2. Run ZeroCheck on
122 ///
123 /// `f(q_0(x),...q_l(x), w_0(x),...w_d(x))`
124 ///
125 /// where `f` is the constraint polynomial i.e.,
126 /// ```ignore
127 /// f(q_l, q_r, q_m, q_o, w_a, w_b, w_c)
128 /// = q_l w_a(x) + q_r w_b(x) + q_m w_a(x)w_b(x) - q_o w_c(x)
129 /// ```
130 /// in vanilla plonk, and obtain a ZeroCheckSubClaim
131 ///
132 /// 3. Run permutation check on `\{w_i(x)\}` and `permutation_oracle`, and
133 /// obtain a PermCheckSubClaim.
134 ///
135 /// 4. Generate evaluations and corresponding proofs
136 /// - 4.1. (deferred) batch opening prod(x) at
137 /// - [0, perm_check_point]
138 /// - [1, perm_check_point]
139 /// - [perm_check_point, 0]
140 /// - [perm_check_point, 1]
141 /// - [1,...1, 0]
142 ///
143 /// - 4.2. permutation check evaluations and proofs
144 /// - 4.2.1. (deferred) wi_poly(perm_check_point)
145 ///
146 /// - 4.3. zero check evaluations and proofs
147 /// - 4.3.1. (deferred) wi_poly(zero_check_point)
148 /// - 4.3.2. (deferred) selector_poly(zero_check_point)
149 ///
150 /// - 4.4. public input consistency checks
151 /// - pi_poly(r_pi) where r_pi is sampled from transcript
152 ///
153 /// - 5. deferred batch opening
154 fn prove(
155 pk: &Self::ProvingKey,
156 pub_input: &[E::ScalarField],
157 witnesses: &[WitnessColumn<E::ScalarField>],
158 ) -> Result<Self::Proof, HyperPlonkErrors> {
159 let start = start_timer!(|| "hyperplonk proving");
160 let mut transcript = IOPTranscript::<E::ScalarField>::new(b"hyperplonk");
161
162 prover_sanity_check(&pk.params, pub_input, witnesses)?;
163
164 // witness assignment of length 2^n
165 let num_vars = pk.params.num_variables();
166
167 // online public input of length 2^\ell
168 let ell = log2(pk.params.num_pub_input) as usize;
169
170 // We use accumulators to store the polynomials and their eval points.
171 // They are batch opened at a later stage.
172 let mut pcs_acc = PcsAccumulator::<E, PCS>::new(num_vars);
173
174 // =======================================================================
175 // 1. Commit Witness polynomials `w_i(x)` and append commitment to
176 // transcript
177 // =======================================================================
178 let step = start_timer!(|| "commit witnesses");
179
180 let witness_polys: Vec<Arc<DenseMultilinearExtension<E::ScalarField>>> = witnesses
181 .iter()
182 .map(|w| Arc::new(DenseMultilinearExtension::from(w)))
183 .collect();
184
185 let witness_commits = witness_polys
186 .par_iter()
187 .map(|x| PCS::commit(&pk.pcs_param, x).unwrap())
188 .collect::<Vec<_>>();
189 for w_com in witness_commits.iter() {
190 transcript.append_serializable_element(b"w", w_com)?;
191 }
192
193 end_timer!(step);
194 // =======================================================================
195 // 2 Run ZeroCheck on
196 //
197 // `f(q_0(x),...q_l(x), w_0(x),...w_d(x))`
198 //
199 // where `f` is the constraint polynomial i.e.,
200 //
201 // f(q_l, q_r, q_m, q_o, w_a, w_b, w_c)
202 // = q_l w_a(x) + q_r w_b(x) + q_m w_a(x)w_b(x) - q_o w_c(x)
203 //
204 // in vanilla plonk, and obtain a ZeroCheckSubClaim
205 // =======================================================================
206 let step = start_timer!(|| "ZeroCheck on f");
207
208 let fx = build_f(
209 &pk.params.gate_func,
210 pk.params.num_variables(),
211 &pk.selector_oracles,
212 &witness_polys,
213 )?;
214
215 let zero_check_proof = <Self as ZeroCheck<E::ScalarField>>::prove(&fx, &mut transcript)?;
216 end_timer!(step);
217 // =======================================================================
218 // 3. Run permutation check on `\{w_i(x)\}` and `permutation_oracle`, and
219 // obtain a PermCheckSubClaim.
220 // =======================================================================
221 let step = start_timer!(|| "Permutation check on w_i(x)");
222
223 let (perm_check_proof, prod_x, frac_poly) = <Self as PermutationCheck<E, PCS>>::prove(
224 &pk.pcs_param,
225 &witness_polys,
226 &witness_polys,
227 &pk.permutation_oracles,
228 &mut transcript,
229 )?;
230 let perm_check_point = &perm_check_proof.zero_check_proof.point;
231
232 end_timer!(step);
233 // =======================================================================
234 // 4. Generate evaluations and corresponding proofs
235 // - permcheck
236 // 1. (deferred) batch opening prod(x) at
237 // - [perm_check_point]
238 // - [perm_check_point[2..n], 0]
239 // - [perm_check_point[2..n], 1]
240 // - [1,...1, 0]
241 // 2. (deferred) batch opening frac(x) at
242 // - [perm_check_point]
243 // - [perm_check_point[2..n], 0]
244 // - [perm_check_point[2..n], 1]
245 // 3. (deferred) batch opening s_id(x) at
246 // - [perm_check_point]
247 // 4. (deferred) batch opening perms(x) at
248 // - [perm_check_point]
249 // 5. (deferred) batch opening witness_i(x) at
250 // - [perm_check_point]
251 //
252 // - zero check evaluations and proofs
253 // - 4.3.1. (deferred) wi_poly(zero_check_point)
254 // - 4.3.2. (deferred) selector_poly(zero_check_point)
255 //
256 // - 4.4. (deferred) public input consistency checks
257 // - pi_poly(r_pi) where r_pi is sampled from transcript
258 // =======================================================================
259 let step = start_timer!(|| "opening and evaluations");
260
261 // (perm_check_point[2..n], 0)
262 let perm_check_point_0 = [
263 &[E::ScalarField::zero()],
264 &perm_check_point[0..num_vars - 1],
265 ]
266 .concat();
267 // (perm_check_point[2..n], 1)
268 let perm_check_point_1 =
269 [&[E::ScalarField::one()], &perm_check_point[0..num_vars - 1]].concat();
270 // (1, ..., 1, 0)
271 let prod_final_query_point = [
272 vec![E::ScalarField::zero()],
273 vec![E::ScalarField::one(); num_vars - 1],
274 ]
275 .concat();
276
277 // prod(x)'s points
278 pcs_acc.insert_poly_and_points(&prod_x, &perm_check_proof.prod_x_comm, perm_check_point);
279 pcs_acc.insert_poly_and_points(&prod_x, &perm_check_proof.prod_x_comm, &perm_check_point_0);
280 pcs_acc.insert_poly_and_points(&prod_x, &perm_check_proof.prod_x_comm, &perm_check_point_1);
281 pcs_acc.insert_poly_and_points(
282 &prod_x,
283 &perm_check_proof.prod_x_comm,
284 &prod_final_query_point,
285 );
286
287 // frac(x)'s points
288 pcs_acc.insert_poly_and_points(&frac_poly, &perm_check_proof.frac_comm, perm_check_point);
289 pcs_acc.insert_poly_and_points(
290 &frac_poly,
291 &perm_check_proof.frac_comm,
292 &perm_check_point_0,
293 );
294 pcs_acc.insert_poly_and_points(
295 &frac_poly,
296 &perm_check_proof.frac_comm,
297 &perm_check_point_1,
298 );
299
300 // perms(x)'s points
301 for (perm, pcom) in pk
302 .permutation_oracles
303 .iter()
304 .zip(pk.permutation_commitments.iter())
305 {
306 pcs_acc.insert_poly_and_points(perm, pcom, perm_check_point);
307 }
308
309 // witnesses' points
310 // TODO: refactor so it remains correct even if the order changed
311 for (wpoly, wcom) in witness_polys.iter().zip(witness_commits.iter()) {
312 pcs_acc.insert_poly_and_points(wpoly, wcom, perm_check_point);
313 }
314 for (wpoly, wcom) in witness_polys.iter().zip(witness_commits.iter()) {
315 pcs_acc.insert_poly_and_points(wpoly, wcom, &zero_check_proof.point);
316 }
317
318 // - 4.3.2. (deferred) selector_poly(zero_check_point)
319 pk.selector_oracles
320 .iter()
321 .zip(pk.selector_commitments.iter())
322 .for_each(|(poly, com)| {
323 pcs_acc.insert_poly_and_points(poly, com, &zero_check_proof.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 // padded with zeros
330 let r_pi_padded = [r_pi, vec![E::ScalarField::zero(); num_vars - ell]].concat();
331 // Evaluate witness_poly[0] at r_pi||0s which is equal to public_input evaluated
332 // at r_pi. Assumes that public_input is a power of 2
333 pcs_acc.insert_poly_and_points(&witness_polys[0], &witness_commits[0], &r_pi_padded);
334 end_timer!(step);
335
336 // =======================================================================
337 // 5. deferred batch opening
338 // =======================================================================
339 let step = start_timer!(|| "deferred batch openings prod(x)");
340 let batch_openings = pcs_acc.multi_open(&pk.pcs_param, &mut transcript)?;
341 end_timer!(step);
342
343 end_timer!(start);
344
345 Ok(HyperPlonkProof {
346 // PCS commit for witnesses
347 witness_commits,
348 // batch_openings,
349 batch_openings,
350 // =======================================================================
351 // IOP proofs
352 // =======================================================================
353 // the custom gate zerocheck proof
354 zero_check_proof,
355 // the permutation check proof for copy constraints
356 perm_check_proof,
357 })
358 }
359
360 /// Verify the HyperPlonk proof.
361 ///
362 /// Inputs:
363 /// - `vk`: verification key
364 /// - `pub_input`: online public input
365 /// - `proof`: HyperPlonk SNARK proof
366 /// Outputs:
367 /// - Return a boolean on whether the verification is successful
368 ///
369 /// 1. Verify zero_check_proof on
370 ///
371 /// `f(q_0(x),...q_l(x), w_0(x),...w_d(x))`
372 ///
373 /// where `f` is the constraint polynomial i.e.,
374 /// ```ignore
375 /// f(q_l, q_r, q_m, q_o, w_a, w_b, w_c)
376 /// = q_l w_a(x) + q_r w_b(x) + q_m w_a(x)w_b(x) - q_o w_c(x)
377 /// ```
378 /// in vanilla plonk, and obtain a ZeroCheckSubClaim
379 ///
380 /// 2. Verify perm_check_proof on `\{w_i(x)\}` and `permutation_oracles`
381 ///
382 /// 3. check subclaim validity
383 ///
384 /// 4. Verify the opening against the commitment:
385 /// - check permutation check evaluations
386 /// - check zero check evaluations
387 /// - public input consistency checks
388 fn verify(
389 vk: &Self::VerifyingKey,
390 pub_input: &[E::ScalarField],
391 proof: &Self::Proof,
392 ) -> Result<bool, HyperPlonkErrors> {
393 let start = start_timer!(|| "hyperplonk verification");
394
395 let mut transcript = IOPTranscript::<E::ScalarField>::new(b"hyperplonk");
396
397 let num_selectors = vk.params.num_selector_columns();
398 let num_witnesses = vk.params.num_witness_columns();
399 let num_vars = vk.params.num_variables();
400
401 // online public input of length 2^\ell
402 let ell = log2(vk.params.num_pub_input) as usize;
403
404 // =======================================================================
405 // 0. sanity checks
406 // =======================================================================
407 // public input length
408 if pub_input.len() != vk.params.num_pub_input {
409 return Err(HyperPlonkErrors::InvalidProver(format!(
410 "Public input length is not correct: got {}, expect {}",
411 pub_input.len(),
412 1 << ell
413 )));
414 }
415
416 // Extract evaluations from openings
417 let prod_evals = &proof.batch_openings.f_i_eval_at_point_i[0..4];
418 let frac_evals = &proof.batch_openings.f_i_eval_at_point_i[4..7];
419 let perm_evals = &proof.batch_openings.f_i_eval_at_point_i[7..7 + num_witnesses];
420 let witness_perm_evals =
421 &proof.batch_openings.f_i_eval_at_point_i[7 + num_witnesses..7 + 2 * num_witnesses];
422 let witness_gate_evals =
423 &proof.batch_openings.f_i_eval_at_point_i[7 + 2 * num_witnesses..7 + 3 * num_witnesses];
424 let selector_evals = &proof.batch_openings.f_i_eval_at_point_i
425 [7 + 3 * num_witnesses..7 + 3 * num_witnesses + num_selectors];
426 let pi_eval = proof.batch_openings.f_i_eval_at_point_i.last().unwrap();
427
428 // =======================================================================
429 // 1. Verify zero_check_proof on
430 // `f(q_0(x),...q_l(x), w_0(x),...w_d(x))`
431 //
432 // where `f` is the constraint polynomial i.e.,
433 //
434 // f(q_l, q_r, q_m, q_o, w_a, w_b, w_c)
435 // = q_l w_a(x) + q_r w_b(x) + q_m w_a(x)w_b(x) - q_o w_c(x)
436 //
437 // =======================================================================
438 let step = start_timer!(|| "verify zero check");
439 // Zero check and perm check have different AuxInfo
440 let zero_check_aux_info = VPAuxInfo::<E::ScalarField> {
441 max_degree: vk.params.gate_func.degree(),
442 num_variables: num_vars,
443 phantom: PhantomData::default(),
444 };
445 // push witness to transcript
446 for w_com in proof.witness_commits.iter() {
447 transcript.append_serializable_element(b"w", w_com)?;
448 }
449
450 let zero_check_sub_claim = <Self as ZeroCheck<E::ScalarField>>::verify(
451 &proof.zero_check_proof,
452 &zero_check_aux_info,
453 &mut transcript,
454 )?;
455
456 let zero_check_point = zero_check_sub_claim.point.clone();
457
458 // check zero check subclaim
459 let f_eval = eval_f(&vk.params.gate_func, selector_evals, witness_gate_evals)?;
460 if f_eval != zero_check_sub_claim.expected_evaluation {
461 return Err(HyperPlonkErrors::InvalidProof(
462 "zero check evaluation failed".to_string(),
463 ));
464 }
465
466 end_timer!(step);
467 // =======================================================================
468 // 2. Verify perm_check_proof on `\{w_i(x)\}` and `permutation_oracle`
469 // =======================================================================
470 let step = start_timer!(|| "verify permutation check");
471
472 // Zero check and perm check have different AuxInfo
473 let perm_check_aux_info = VPAuxInfo::<E::ScalarField> {
474 // Prod(x) has a max degree of witnesses.len() + 1
475 max_degree: proof.witness_commits.len() + 1,
476 num_variables: num_vars,
477 phantom: PhantomData::default(),
478 };
479 let perm_check_sub_claim = <Self as PermutationCheck<E, PCS>>::verify(
480 &proof.perm_check_proof,
481 &perm_check_aux_info,
482 &mut transcript,
483 )?;
484
485 let perm_check_point = perm_check_sub_claim
486 .product_check_sub_claim
487 .zero_check_sub_claim
488 .point
489 .clone();
490
491 let alpha = perm_check_sub_claim.product_check_sub_claim.alpha;
492 let (beta, gamma) = perm_check_sub_claim.challenges;
493
494 let mut id_evals = vec![];
495 for i in 0..num_witnesses {
496 let ith_point = gen_eval_point(i, log2(num_witnesses) as usize, &perm_check_point[..]);
497 id_evals.push(vk.params.eval_id_oracle(&ith_point[..])?);
498 }
499
500 // check evaluation subclaim
501 let perm_gate_eval = eval_perm_gate(
502 prod_evals,
503 frac_evals,
504 witness_perm_evals,
505 &id_evals[..],
506 perm_evals,
507 alpha,
508 beta,
509 gamma,
510 *perm_check_point.last().unwrap(),
511 )?;
512 if perm_gate_eval
513 != perm_check_sub_claim
514 .product_check_sub_claim
515 .zero_check_sub_claim
516 .expected_evaluation
517 {
518 return Err(HyperPlonkErrors::InvalidVerifier(
519 "evaluation failed".to_string(),
520 ));
521 }
522
523 end_timer!(step);
524 // =======================================================================
525 // 3. Verify the opening against the commitment
526 // =======================================================================
527 let step = start_timer!(|| "assemble commitments");
528
529 // generate evaluation points and commitments
530 let mut comms = vec![];
531 let mut points = vec![];
532
533 let perm_check_point_0 = [
534 &[E::ScalarField::zero()],
535 &perm_check_point[0..num_vars - 1],
536 ]
537 .concat();
538 let perm_check_point_1 =
539 [&[E::ScalarField::one()], &perm_check_point[0..num_vars - 1]].concat();
540 let prod_final_query_point = [
541 vec![E::ScalarField::zero()],
542 vec![E::ScalarField::one(); num_vars - 1],
543 ]
544 .concat();
545
546 // prod(x)'s points
547 comms.push(proof.perm_check_proof.prod_x_comm);
548 comms.push(proof.perm_check_proof.prod_x_comm);
549 comms.push(proof.perm_check_proof.prod_x_comm);
550 comms.push(proof.perm_check_proof.prod_x_comm);
551 points.push(perm_check_point.clone());
552 points.push(perm_check_point_0.clone());
553 points.push(perm_check_point_1.clone());
554 points.push(prod_final_query_point);
555 // frac(x)'s points
556 comms.push(proof.perm_check_proof.frac_comm);
557 comms.push(proof.perm_check_proof.frac_comm);
558 comms.push(proof.perm_check_proof.frac_comm);
559 points.push(perm_check_point.clone());
560 points.push(perm_check_point_0);
561 points.push(perm_check_point_1);
562
563 // perms' points
564 for &pcom in vk.perm_commitments.iter() {
565 comms.push(pcom);
566 points.push(perm_check_point.clone());
567 }
568
569 // witnesses' points
570 // TODO: merge points
571 for &wcom in proof.witness_commits.iter() {
572 comms.push(wcom);
573 points.push(perm_check_point.clone());
574 }
575 for &wcom in proof.witness_commits.iter() {
576 comms.push(wcom);
577 points.push(zero_check_point.clone());
578 }
579
580 // selector_poly(zero_check_point)
581 for &com in vk.selector_commitments.iter() {
582 comms.push(com);
583 points.push(zero_check_point.clone());
584 }
585
586 // - 4.4. public input consistency checks
587 // - pi_poly(r_pi) where r_pi is sampled from transcript
588 let r_pi = transcript.get_and_append_challenge_vectors(b"r_pi", ell)?;
589
590 // check public evaluation
591 let pi_step = start_timer!(|| "check public evaluation");
592 let pi_poly = DenseMultilinearExtension::from_evaluations_slice(ell, pub_input);
593 let expect_pi_eval = evaluate_opt(&pi_poly, &r_pi[..]);
594 if expect_pi_eval != *pi_eval {
595 return Err(HyperPlonkErrors::InvalidProver(format!(
596 "Public input eval mismatch: got {}, expect {}",
597 pi_eval, expect_pi_eval,
598 )));
599 }
600 let r_pi_padded = [r_pi, vec![E::ScalarField::zero(); num_vars - ell]].concat();
601
602 comms.push(proof.witness_commits[0]);
603 points.push(r_pi_padded);
604 assert_eq!(comms.len(), proof.batch_openings.f_i_eval_at_point_i.len());
605 end_timer!(pi_step);
606
607 end_timer!(step);
608 let step = start_timer!(|| "PCS batch verify");
609 // check proof
610 let res = PCS::batch_verify(
611 &vk.pcs_param,
612 &comms,
613 &points,
614 &proof.batch_openings,
615 &mut transcript,
616 )?;
617
618 end_timer!(step);
619 end_timer!(start);
620 Ok(res)
621 }
622}
623
624#[cfg(test)]
625mod tests {
626 use super::*;
627 use crate::{
628 custom_gate::CustomizedGates, selectors::SelectorColumn, structs::HyperPlonkParams,
629 witness::WitnessColumn,
630 };
631 use arithmetic::{identity_permutation, random_permutation};
632 use ark_bls12_381::Bls12_381;
633 use ark_std::test_rng;
634 use subroutines::pcs::prelude::MultilinearKzgPCS;
635
636 #[test]
637 fn test_hyperplonk_e2e() -> Result<(), HyperPlonkErrors> {
638 // Example:
639 // q_L(X) * W_1(X)^5 - W_2(X) = 0
640 // is represented as
641 // vec![
642 // ( 1, Some(id_qL), vec![id_W1, id_W1, id_W1, id_W1, id_W1]),
643 // (-1, None, vec![id_W2])
644 // ]
645 //
646 // 4 public input
647 // 1 selector,
648 // 2 witnesses,
649 // 2 variables for MLE,
650 // 4 wires,
651 let gates = CustomizedGates {
652 gates: vec![(1, Some(0), vec![0, 0, 0, 0, 0]), (-1, None, vec![1])],
653 };
654 test_hyperplonk_helper::<Bls12_381>(gates)
655 }
656
657 fn test_hyperplonk_helper<E: Pairing>(
658 gate_func: CustomizedGates,
659 ) -> Result<(), HyperPlonkErrors> {
660 let mut rng = test_rng();
661 let pcs_srs = MultilinearKzgPCS::<E>::gen_srs_for_testing(&mut rng, 16)?;
662
663 let num_constraints = 4;
664 let num_pub_input = 4;
665 let nv = log2(num_constraints) as usize;
666 let num_witnesses = 2;
667
668 // generate index
669 let params = HyperPlonkParams {
670 num_constraints,
671 num_pub_input,
672 gate_func,
673 };
674 let permutation = identity_permutation(nv, num_witnesses);
675 let q1 = SelectorColumn(vec![
676 E::ScalarField::one(),
677 E::ScalarField::one(),
678 E::ScalarField::one(),
679 E::ScalarField::one(),
680 ]);
681 let index = HyperPlonkIndex {
682 params,
683 permutation,
684 selectors: vec![q1],
685 };
686
687 // generate pk and vks
688 let (pk, vk) =
689 <PolyIOP<E::ScalarField> as HyperPlonkSNARK<E, MultilinearKzgPCS<E>>>::preprocess(
690 &index, &pcs_srs,
691 )?;
692
693 // w1 := [0, 1, 2, 3]
694 let w1 = WitnessColumn(vec![
695 E::ScalarField::zero(),
696 E::ScalarField::one(),
697 E::ScalarField::from(2u128),
698 E::ScalarField::from(3u128),
699 ]);
700 // w2 := [0^5, 1^5, 2^5, 3^5]
701 let w2 = WitnessColumn(vec![
702 E::ScalarField::zero(),
703 E::ScalarField::one(),
704 E::ScalarField::from(32u128),
705 E::ScalarField::from(243u128),
706 ]);
707 // public input = w1
708 let pi = w1.clone();
709
710 // generate a proof and verify
711 let proof = <PolyIOP<E::ScalarField> as HyperPlonkSNARK<E, MultilinearKzgPCS<E>>>::prove(
712 &pk,
713 &pi.0,
714 &[w1.clone(), w2.clone()],
715 )?;
716
717 let _verify =
718 <PolyIOP<E::ScalarField> as HyperPlonkSNARK<E, MultilinearKzgPCS<E>>>::verify(
719 &vk, &pi.0, &proof,
720 )?;
721
722 // bad path 1: wrong permutation
723 let rand_perm: Vec<E::ScalarField> = random_permutation(nv, num_witnesses, &mut rng);
724 let mut bad_index = index;
725 bad_index.permutation = rand_perm;
726 // generate pk and vks
727 let (_, bad_vk) =
728 <PolyIOP<E::ScalarField> as HyperPlonkSNARK<E, MultilinearKzgPCS<E>>>::preprocess(
729 &bad_index, &pcs_srs,
730 )?;
731 assert!(!<PolyIOP<E::ScalarField> as HyperPlonkSNARK<
732 E,
733 MultilinearKzgPCS<E>,
734 >>::verify(&bad_vk, &pi.0, &proof,)?);
735
736 // bad path 2: wrong witness
737 let mut w1_bad = w1;
738 w1_bad.0[0] = E::ScalarField::one();
739 assert!(
740 <PolyIOP<E::ScalarField> as HyperPlonkSNARK<E, MultilinearKzgPCS<E>>>::prove(
741 &pk,
742 &pi.0,
743 &[w1_bad, w2],
744 )
745 .is_err()
746 );
747
748 Ok(())
749 }
750}