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;
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
490 let alpha = perm_check_sub_claim.product_check_sub_claim.alpha;
491 let (beta, gamma) = perm_check_sub_claim.challenges;
492
493 let mut id_evals = vec![];
494 for i in 0..num_witnesses {
495 let ith_point = gen_eval_point(i, log2(num_witnesses) as usize, &perm_check_point[..]);
496 id_evals.push(vk.params.eval_id_oracle(&ith_point[..])?);
497 }
498
499 // check evaluation subclaim
500 let perm_gate_eval = eval_perm_gate(
501 prod_evals,
502 frac_evals,
503 witness_perm_evals,
504 &id_evals[..],
505 perm_evals,
506 alpha,
507 beta,
508 gamma,
509 *perm_check_point.last().unwrap(),
510 )?;
511 if perm_gate_eval
512 != perm_check_sub_claim
513 .product_check_sub_claim
514 .zero_check_sub_claim
515 .expected_evaluation
516 {
517 return Err(HyperPlonkErrors::InvalidVerifier(
518 "evaluation failed".to_string(),
519 ));
520 }
521
522 end_timer!(step);
523 // =======================================================================
524 // 3. Verify the opening against the commitment
525 // =======================================================================
526 let step = start_timer!(|| "assemble commitments");
527
528 // generate evaluation points and commitments
529 let mut comms = vec![];
530 let mut points = vec![];
531
532 let perm_check_point_0 = [
533 &[E::ScalarField::zero()],
534 &perm_check_point[0..num_vars - 1],
535 ]
536 .concat();
537 let perm_check_point_1 =
538 [&[E::ScalarField::one()], &perm_check_point[0..num_vars - 1]].concat();
539 let prod_final_query_point = [
540 vec![E::ScalarField::zero()],
541 vec![E::ScalarField::one(); num_vars - 1],
542 ]
543 .concat();
544
545 // prod(x)'s points
546 comms.push(proof.perm_check_proof.prod_x_comm);
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 points.push(perm_check_point.clone());
551 points.push(perm_check_point_0.clone());
552 points.push(perm_check_point_1.clone());
553 points.push(prod_final_query_point);
554 // frac(x)'s points
555 comms.push(proof.perm_check_proof.frac_comm);
556 comms.push(proof.perm_check_proof.frac_comm);
557 comms.push(proof.perm_check_proof.frac_comm);
558 points.push(perm_check_point.clone());
559 points.push(perm_check_point_0);
560 points.push(perm_check_point_1);
561
562 // perms' points
563 for &pcom in vk.perm_commitments.iter() {
564 comms.push(pcom);
565 points.push(perm_check_point.clone());
566 }
567
568 // witnesses' points
569 // TODO: merge points
570 for &wcom in proof.witness_commits.iter() {
571 comms.push(wcom);
572 points.push(perm_check_point.clone());
573 }
574 for &wcom in proof.witness_commits.iter() {
575 comms.push(wcom);
576 points.push(zero_check_point.clone());
577 }
578
579 // selector_poly(zero_check_point)
580 for &com in vk.selector_commitments.iter() {
581 comms.push(com);
582 points.push(zero_check_point.clone());
583 }
584
585 // - 4.4. public input consistency checks
586 // - pi_poly(r_pi) where r_pi is sampled from transcript
587 let r_pi = transcript.get_and_append_challenge_vectors(b"r_pi", ell)?;
588
589 // check public evaluation
590 let pi_step = start_timer!(|| "check public evaluation");
591 let pi_poly = DenseMultilinearExtension::from_evaluations_slice(ell, pub_input);
592 let expect_pi_eval = evaluate_opt(&pi_poly, &r_pi[..]);
593 if expect_pi_eval != *pi_eval {
594 return Err(HyperPlonkErrors::InvalidProver(format!(
595 "Public input eval mismatch: got {}, expect {}",
596 pi_eval, expect_pi_eval,
597 )));
598 }
599 let r_pi_padded = [r_pi, vec![E::ScalarField::zero(); num_vars - ell]].concat();
600
601 comms.push(proof.witness_commits[0]);
602 points.push(r_pi_padded);
603 assert_eq!(comms.len(), proof.batch_openings.f_i_eval_at_point_i.len());
604 end_timer!(pi_step);
605
606 end_timer!(step);
607 let step = start_timer!(|| "PCS batch verify");
608 // check proof
609 let res = PCS::batch_verify(
610 &vk.pcs_param,
611 &comms,
612 &points,
613 &proof.batch_openings,
614 &mut transcript,
615 )?;
616
617 end_timer!(step);
618 end_timer!(start);
619 Ok(res)
620 }
621}
622
623#[cfg(test)]
624mod tests {
625 use super::*;
626 use crate::{
627 custom_gate::CustomizedGates, selectors::SelectorColumn, structs::HyperPlonkParams,
628 witness::WitnessColumn,
629 };
630 use arithmetic::{identity_permutation, random_permutation};
631 use ark_bls12_381::Bls12_381;
632 use ark_std::test_rng;
633 use subroutines::pcs::prelude::MultilinearKzgPCS;
634
635 #[test]
636 fn test_hyperplonk_e2e() -> Result<(), HyperPlonkErrors> {
637 // Example:
638 // q_L(X) * W_1(X)^5 - W_2(X) = 0
639 // is represented as
640 // vec![
641 // ( 1, Some(id_qL), vec![id_W1, id_W1, id_W1, id_W1, id_W1]),
642 // (-1, None, vec![id_W2])
643 // ]
644 //
645 // 4 public input
646 // 1 selector,
647 // 2 witnesses,
648 // 2 variables for MLE,
649 // 4 wires,
650 let gates = CustomizedGates {
651 gates: vec![(1, Some(0), vec![0, 0, 0, 0, 0]), (-1, None, vec![1])],
652 };
653 test_hyperplonk_helper::<Bls12_381>(gates)
654 }
655
656 fn test_hyperplonk_helper<E: Pairing>(
657 gate_func: CustomizedGates,
658 ) -> Result<(), HyperPlonkErrors> {
659 let mut rng = test_rng();
660 let pcs_srs = MultilinearKzgPCS::<E>::gen_srs_for_testing(&mut rng, 16)?;
661
662 let num_constraints = 4;
663 let num_pub_input = 4;
664 let nv = log2(num_constraints) as usize;
665 let num_witnesses = 2;
666
667 // generate index
668 let params = HyperPlonkParams {
669 num_constraints,
670 num_pub_input,
671 gate_func,
672 };
673 let permutation = identity_permutation(nv, num_witnesses);
674 let q1 = SelectorColumn(vec![
675 E::ScalarField::one(),
676 E::ScalarField::one(),
677 E::ScalarField::one(),
678 E::ScalarField::one(),
679 ]);
680 let index = HyperPlonkIndex {
681 params,
682 permutation,
683 selectors: vec![q1],
684 };
685
686 // generate pk and vks
687 let (pk, vk) =
688 <PolyIOP<E::ScalarField> as HyperPlonkSNARK<E, MultilinearKzgPCS<E>>>::preprocess(
689 &index, &pcs_srs,
690 )?;
691
692 // w1 := [0, 1, 2, 3]
693 let w1 = WitnessColumn(vec![
694 E::ScalarField::zero(),
695 E::ScalarField::one(),
696 E::ScalarField::from(2u128),
697 E::ScalarField::from(3u128),
698 ]);
699 // w2 := [0^5, 1^5, 2^5, 3^5]
700 let w2 = WitnessColumn(vec![
701 E::ScalarField::zero(),
702 E::ScalarField::one(),
703 E::ScalarField::from(32u128),
704 E::ScalarField::from(243u128),
705 ]);
706 // public input = w1
707 let pi = w1.clone();
708
709 // generate a proof and verify
710 let proof = <PolyIOP<E::ScalarField> as HyperPlonkSNARK<E, MultilinearKzgPCS<E>>>::prove(
711 &pk,
712 &pi.0,
713 &[w1.clone(), w2.clone()],
714 )?;
715
716 let _verify =
717 <PolyIOP<E::ScalarField> as HyperPlonkSNARK<E, MultilinearKzgPCS<E>>>::verify(
718 &vk, &pi.0, &proof,
719 )?;
720
721 // bad path 1: wrong permutation
722 let rand_perm: Vec<E::ScalarField> = random_permutation(nv, num_witnesses, &mut rng);
723 let mut bad_index = index;
724 bad_index.permutation = rand_perm;
725 // generate pk and vks
726 let (_, bad_vk) =
727 <PolyIOP<E::ScalarField> as HyperPlonkSNARK<E, MultilinearKzgPCS<E>>>::preprocess(
728 &bad_index, &pcs_srs,
729 )?;
730 assert!(!<PolyIOP<E::ScalarField> as HyperPlonkSNARK<
731 E,
732 MultilinearKzgPCS<E>,
733 >>::verify(&bad_vk, &pi.0, &proof,)?);
734
735 // bad path 2: wrong witness
736 let mut w1_bad = w1;
737 w1_bad.0[0] = E::ScalarField::one();
738 assert!(
739 <PolyIOP<E::ScalarField> as HyperPlonkSNARK<E, MultilinearKzgPCS<E>>>::prove(
740 &pk,
741 &pi.0,
742 &[w1_bad, w2],
743 )
744 .is_err()
745 );
746
747 Ok(())
748 }
749}