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::PairingEngine;
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::Fr>
33where
34 E: PairingEngine,
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::Fr>>,
41 Point = Vec<E::Fr>,
42 Evaluation = E::Fr,
43 Commitment = Commitment<E>,
44 BatchProof = BatchProof<E, PCS>,
45 >,
46{
47 type Index = HyperPlonkIndex<E::Fr>;
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::Fr>>> = 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::Fr],
157 witnesses: &[WitnessColumn<E::Fr>],
158 ) -> Result<Self::Proof, HyperPlonkErrors> {
159 let start = start_timer!(|| "hyperplonk proving");
160 let mut transcript = IOPTranscript::<E::Fr>::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::Fr>>> = 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::Fr>>::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 = [&[E::Fr::zero()], &perm_check_point[0..num_vars - 1]].concat();
263 // (perm_check_point[2..n], 1)
264 let perm_check_point_1 = [&[E::Fr::one()], &perm_check_point[0..num_vars - 1]].concat();
265 // (1, ..., 1, 0)
266 let prod_final_query_point =
267 [vec![E::Fr::zero()], vec![E::Fr::one(); num_vars - 1]].concat();
268
269 // prod(x)'s points
270 pcs_acc.insert_poly_and_points(&prod_x, &perm_check_proof.prod_x_comm, perm_check_point);
271 pcs_acc.insert_poly_and_points(&prod_x, &perm_check_proof.prod_x_comm, &perm_check_point_0);
272 pcs_acc.insert_poly_and_points(&prod_x, &perm_check_proof.prod_x_comm, &perm_check_point_1);
273 pcs_acc.insert_poly_and_points(
274 &prod_x,
275 &perm_check_proof.prod_x_comm,
276 &prod_final_query_point,
277 );
278
279 // frac(x)'s points
280 pcs_acc.insert_poly_and_points(&frac_poly, &perm_check_proof.frac_comm, perm_check_point);
281 pcs_acc.insert_poly_and_points(
282 &frac_poly,
283 &perm_check_proof.frac_comm,
284 &perm_check_point_0,
285 );
286 pcs_acc.insert_poly_and_points(
287 &frac_poly,
288 &perm_check_proof.frac_comm,
289 &perm_check_point_1,
290 );
291
292 // perms(x)'s points
293 for (perm, pcom) in pk
294 .permutation_oracles
295 .iter()
296 .zip(pk.permutation_commitments.iter())
297 {
298 pcs_acc.insert_poly_and_points(perm, pcom, perm_check_point);
299 }
300
301 // witnesses' points
302 // TODO: refactor so it remains correct even if the order changed
303 for (wpoly, wcom) in witness_polys.iter().zip(witness_commits.iter()) {
304 pcs_acc.insert_poly_and_points(wpoly, wcom, perm_check_point);
305 }
306 for (wpoly, wcom) in witness_polys.iter().zip(witness_commits.iter()) {
307 pcs_acc.insert_poly_and_points(wpoly, wcom, &zero_check_proof.point);
308 }
309
310 // - 4.3.2. (deferred) selector_poly(zero_check_point)
311 pk.selector_oracles
312 .iter()
313 .zip(pk.selector_commitments.iter())
314 .for_each(|(poly, com)| {
315 pcs_acc.insert_poly_and_points(poly, com, &zero_check_proof.point)
316 });
317
318 // - 4.4. public input consistency checks
319 // - pi_poly(r_pi) where r_pi is sampled from transcript
320 let r_pi = transcript.get_and_append_challenge_vectors(b"r_pi", ell)?;
321 // padded with zeros
322 let r_pi_padded = [r_pi, vec![E::Fr::zero(); num_vars - ell]].concat();
323 // Evaluate witness_poly[0] at r_pi||0s which is equal to public_input evaluated
324 // at r_pi. Assumes that public_input is a power of 2
325 pcs_acc.insert_poly_and_points(&witness_polys[0], &witness_commits[0], &r_pi_padded);
326 end_timer!(step);
327
328 // =======================================================================
329 // 5. deferred batch opening
330 // =======================================================================
331 let step = start_timer!(|| "deferred batch openings prod(x)");
332 let batch_openings = pcs_acc.multi_open(&pk.pcs_param, &mut transcript)?;
333 end_timer!(step);
334
335 end_timer!(start);
336
337 Ok(HyperPlonkProof {
338 // PCS commit for witnesses
339 witness_commits,
340 // batch_openings,
341 batch_openings,
342 // =======================================================================
343 // IOP proofs
344 // =======================================================================
345 // the custom gate zerocheck proof
346 zero_check_proof,
347 // the permutation check proof for copy constraints
348 perm_check_proof,
349 })
350 }
351
352 /// Verify the HyperPlonk proof.
353 ///
354 /// Inputs:
355 /// - `vk`: verification key
356 /// - `pub_input`: online public input
357 /// - `proof`: HyperPlonk SNARK proof
358 /// Outputs:
359 /// - Return a boolean on whether the verification is successful
360 ///
361 /// 1. Verify zero_check_proof on
362 ///
363 /// `f(q_0(x),...q_l(x), w_0(x),...w_d(x))`
364 ///
365 /// where `f` is the constraint polynomial i.e.,
366 /// ```ignore
367 /// f(q_l, q_r, q_m, q_o, w_a, w_b, w_c)
368 /// = q_l w_a(x) + q_r w_b(x) + q_m w_a(x)w_b(x) - q_o w_c(x)
369 /// ```
370 /// in vanilla plonk, and obtain a ZeroCheckSubClaim
371 ///
372 /// 2. Verify perm_check_proof on `\{w_i(x)\}` and `permutation_oracles`
373 ///
374 /// 3. check subclaim validity
375 ///
376 /// 4. Verify the opening against the commitment:
377 /// - check permutation check evaluations
378 /// - check zero check evaluations
379 /// - public input consistency checks
380 fn verify(
381 vk: &Self::VerifyingKey,
382 pub_input: &[E::Fr],
383 proof: &Self::Proof,
384 ) -> Result<bool, HyperPlonkErrors> {
385 let start = start_timer!(|| "hyperplonk verification");
386
387 let mut transcript = IOPTranscript::<E::Fr>::new(b"hyperplonk");
388
389 let num_selectors = vk.params.num_selector_columns();
390 let num_witnesses = vk.params.num_witness_columns();
391 let num_vars = vk.params.num_variables();
392
393 // online public input of length 2^\ell
394 let ell = log2(vk.params.num_pub_input) as usize;
395
396 // =======================================================================
397 // 0. sanity checks
398 // =======================================================================
399 // public input length
400 if pub_input.len() != vk.params.num_pub_input {
401 return Err(HyperPlonkErrors::InvalidProver(format!(
402 "Public input length is not correct: got {}, expect {}",
403 pub_input.len(),
404 1 << ell
405 )));
406 }
407
408 // Extract evaluations from openings
409 let prod_evals = &proof.batch_openings.f_i_eval_at_point_i[0..4];
410 let frac_evals = &proof.batch_openings.f_i_eval_at_point_i[4..7];
411 let perm_evals = &proof.batch_openings.f_i_eval_at_point_i[7..7 + num_witnesses];
412 let witness_perm_evals =
413 &proof.batch_openings.f_i_eval_at_point_i[7 + num_witnesses..7 + 2 * num_witnesses];
414 let witness_gate_evals =
415 &proof.batch_openings.f_i_eval_at_point_i[7 + 2 * num_witnesses..7 + 3 * num_witnesses];
416 let selector_evals = &proof.batch_openings.f_i_eval_at_point_i
417 [7 + 3 * num_witnesses..7 + 3 * num_witnesses + num_selectors];
418 let pi_eval = proof.batch_openings.f_i_eval_at_point_i.last().unwrap();
419
420 // =======================================================================
421 // 1. Verify zero_check_proof on
422 // `f(q_0(x),...q_l(x), w_0(x),...w_d(x))`
423 //
424 // where `f` is the constraint polynomial i.e.,
425 //
426 // f(q_l, q_r, q_m, q_o, w_a, w_b, w_c)
427 // = q_l w_a(x) + q_r w_b(x) + q_m w_a(x)w_b(x) - q_o w_c(x)
428 //
429 // =======================================================================
430 let step = start_timer!(|| "verify zero check");
431 // Zero check and perm check have different AuxInfo
432 let zero_check_aux_info = VPAuxInfo::<E::Fr> {
433 max_degree: vk.params.gate_func.degree(),
434 num_variables: num_vars,
435 phantom: PhantomData::default(),
436 };
437 // push witness to transcript
438 for w_com in proof.witness_commits.iter() {
439 transcript.append_serializable_element(b"w", w_com)?;
440 }
441
442 let zero_check_sub_claim = <Self as ZeroCheck<E::Fr>>::verify(
443 &proof.zero_check_proof,
444 &zero_check_aux_info,
445 &mut transcript,
446 )?;
447
448 let zero_check_point = zero_check_sub_claim.point.clone();
449
450 // check zero check subclaim
451 let f_eval = eval_f(&vk.params.gate_func, selector_evals, witness_gate_evals)?;
452 if f_eval != zero_check_sub_claim.expected_evaluation {
453 return Err(HyperPlonkErrors::InvalidProof(
454 "zero check evaluation failed".to_string(),
455 ));
456 }
457
458 end_timer!(step);
459 // =======================================================================
460 // 2. Verify perm_check_proof on `\{w_i(x)\}` and `permutation_oracle`
461 // =======================================================================
462 let step = start_timer!(|| "verify permutation check");
463
464 // Zero check and perm check have different AuxInfo
465 let perm_check_aux_info = VPAuxInfo::<E::Fr> {
466 // Prod(x) has a max degree of witnesses.len() + 1
467 max_degree: proof.witness_commits.len() + 1,
468 num_variables: num_vars,
469 phantom: PhantomData::default(),
470 };
471 let perm_check_sub_claim = <Self as PermutationCheck<E, PCS>>::verify(
472 &proof.perm_check_proof,
473 &perm_check_aux_info,
474 &mut transcript,
475 )?;
476
477 let perm_check_point = perm_check_sub_claim
478 .product_check_sub_claim
479 .zero_check_sub_claim
480 .point
481 .clone();
482
483 let alpha = perm_check_sub_claim.product_check_sub_claim.alpha;
484 let (beta, gamma) = perm_check_sub_claim.challenges;
485
486 let mut id_evals = vec![];
487 for i in 0..num_witnesses {
488 let ith_point = gen_eval_point(i, log2(num_witnesses) as usize, &perm_check_point[..]);
489 id_evals.push(vk.params.eval_id_oracle(&ith_point[..])?);
490 }
491
492 // check evaluation subclaim
493 let perm_gate_eval = eval_perm_gate(
494 prod_evals,
495 frac_evals,
496 witness_perm_evals,
497 &id_evals[..],
498 perm_evals,
499 alpha,
500 beta,
501 gamma,
502 *perm_check_point.last().unwrap(),
503 )?;
504 if perm_gate_eval
505 != perm_check_sub_claim
506 .product_check_sub_claim
507 .zero_check_sub_claim
508 .expected_evaluation
509 {
510 return Err(HyperPlonkErrors::InvalidVerifier(
511 "evaluation failed".to_string(),
512 ));
513 }
514
515 end_timer!(step);
516 // =======================================================================
517 // 3. Verify the opening against the commitment
518 // =======================================================================
519 let step = start_timer!(|| "assemble commitments");
520
521 // generate evaluation points and commitments
522 let mut comms = vec![];
523 let mut points = vec![];
524
525 let perm_check_point_0 = [&[E::Fr::zero()], &perm_check_point[0..num_vars - 1]].concat();
526 let perm_check_point_1 = [&[E::Fr::one()], &perm_check_point[0..num_vars - 1]].concat();
527 let prod_final_query_point =
528 [vec![E::Fr::zero()], vec![E::Fr::one(); num_vars - 1]].concat();
529
530 // prod(x)'s points
531 comms.push(proof.perm_check_proof.prod_x_comm);
532 comms.push(proof.perm_check_proof.prod_x_comm);
533 comms.push(proof.perm_check_proof.prod_x_comm);
534 comms.push(proof.perm_check_proof.prod_x_comm);
535 points.push(perm_check_point.clone());
536 points.push(perm_check_point_0.clone());
537 points.push(perm_check_point_1.clone());
538 points.push(prod_final_query_point);
539 // frac(x)'s points
540 comms.push(proof.perm_check_proof.frac_comm);
541 comms.push(proof.perm_check_proof.frac_comm);
542 comms.push(proof.perm_check_proof.frac_comm);
543 points.push(perm_check_point.clone());
544 points.push(perm_check_point_0);
545 points.push(perm_check_point_1);
546
547 // perms' points
548 for &pcom in vk.perm_commitments.iter() {
549 comms.push(pcom);
550 points.push(perm_check_point.clone());
551 }
552
553 // witnesses' points
554 // TODO: merge points
555 for &wcom in proof.witness_commits.iter() {
556 comms.push(wcom);
557 points.push(perm_check_point.clone());
558 }
559 for &wcom in proof.witness_commits.iter() {
560 comms.push(wcom);
561 points.push(zero_check_point.clone());
562 }
563
564 // selector_poly(zero_check_point)
565 for &com in vk.selector_commitments.iter() {
566 comms.push(com);
567 points.push(zero_check_point.clone());
568 }
569
570 // - 4.4. public input consistency checks
571 // - pi_poly(r_pi) where r_pi is sampled from transcript
572 let r_pi = transcript.get_and_append_challenge_vectors(b"r_pi", ell)?;
573
574 // check public evaluation
575 let pi_step = start_timer!(|| "check public evaluation");
576 let pi_poly = DenseMultilinearExtension::from_evaluations_slice(ell, pub_input);
577 let expect_pi_eval = evaluate_opt(&pi_poly, &r_pi[..]);
578 if expect_pi_eval != *pi_eval {
579 return Err(HyperPlonkErrors::InvalidProver(format!(
580 "Public input eval mismatch: got {}, expect {}",
581 pi_eval, expect_pi_eval,
582 )));
583 }
584 let r_pi_padded = [r_pi, vec![E::Fr::zero(); num_vars - ell]].concat();
585
586 comms.push(proof.witness_commits[0]);
587 points.push(r_pi_padded);
588 assert_eq!(comms.len(), proof.batch_openings.f_i_eval_at_point_i.len());
589 end_timer!(pi_step);
590
591 end_timer!(step);
592 let step = start_timer!(|| "PCS batch verify");
593 // check proof
594 let res = PCS::batch_verify(
595 &vk.pcs_param,
596 &comms,
597 &points,
598 &proof.batch_openings,
599 &mut transcript,
600 )?;
601
602 end_timer!(step);
603 end_timer!(start);
604 Ok(res)
605 }
606}
607
608#[cfg(test)]
609mod tests {
610 use super::*;
611 use crate::{
612 custom_gate::CustomizedGates, selectors::SelectorColumn, structs::HyperPlonkParams,
613 witness::WitnessColumn,
614 };
615 use arithmetic::{identity_permutation, random_permutation};
616 use ark_bls12_381::Bls12_381;
617 use ark_std::test_rng;
618 use subroutines::pcs::prelude::MultilinearKzgPCS;
619
620 #[test]
621 fn test_hyperplonk_e2e() -> Result<(), HyperPlonkErrors> {
622 // Example:
623 // q_L(X) * W_1(X)^5 - W_2(X) = 0
624 // is represented as
625 // vec![
626 // ( 1, Some(id_qL), vec![id_W1, id_W1, id_W1, id_W1, id_W1]),
627 // (-1, None, vec![id_W2])
628 // ]
629 //
630 // 4 public input
631 // 1 selector,
632 // 2 witnesses,
633 // 2 variables for MLE,
634 // 4 wires,
635 let gates = CustomizedGates {
636 gates: vec![(1, Some(0), vec![0, 0, 0, 0, 0]), (-1, None, vec![1])],
637 };
638 test_hyperplonk_helper::<Bls12_381>(gates)
639 }
640
641 fn test_hyperplonk_helper<E: PairingEngine>(
642 gate_func: CustomizedGates,
643 ) -> Result<(), HyperPlonkErrors> {
644 let mut rng = test_rng();
645 let pcs_srs = MultilinearKzgPCS::<E>::gen_srs_for_testing(&mut rng, 16)?;
646
647 let num_constraints = 4;
648 let num_pub_input = 4;
649 let nv = log2(num_constraints) as usize;
650 let num_witnesses = 2;
651
652 // generate index
653 let params = HyperPlonkParams {
654 num_constraints,
655 num_pub_input,
656 gate_func,
657 };
658 let permutation = identity_permutation(nv, num_witnesses);
659 let q1 = SelectorColumn(vec![E::Fr::one(), E::Fr::one(), E::Fr::one(), E::Fr::one()]);
660 let index = HyperPlonkIndex {
661 params,
662 permutation,
663 selectors: vec![q1],
664 };
665
666 // generate pk and vks
667 let (pk, vk) = <PolyIOP<E::Fr> as HyperPlonkSNARK<E, MultilinearKzgPCS<E>>>::preprocess(
668 &index, &pcs_srs,
669 )?;
670
671 // w1 := [0, 1, 2, 3]
672 let w1 = WitnessColumn(vec![
673 E::Fr::zero(),
674 E::Fr::one(),
675 E::Fr::from(2u128),
676 E::Fr::from(3u128),
677 ]);
678 // w2 := [0^5, 1^5, 2^5, 3^5]
679 let w2 = WitnessColumn(vec![
680 E::Fr::zero(),
681 E::Fr::one(),
682 E::Fr::from(32u128),
683 E::Fr::from(243u128),
684 ]);
685 // public input = w1
686 let pi = w1.clone();
687
688 // generate a proof and verify
689 let proof = <PolyIOP<E::Fr> as HyperPlonkSNARK<E, MultilinearKzgPCS<E>>>::prove(
690 &pk,
691 &pi.0,
692 &[w1.clone(), w2.clone()],
693 )?;
694
695 let _verify = <PolyIOP<E::Fr> as HyperPlonkSNARK<E, MultilinearKzgPCS<E>>>::verify(
696 &vk, &pi.0, &proof,
697 )?;
698
699 // bad path 1: wrong permutation
700 let rand_perm: Vec<E::Fr> = random_permutation(nv, num_witnesses, &mut rng);
701 let mut bad_index = index.clone();
702 bad_index.permutation = rand_perm;
703 // generate pk and vks
704 let (_, bad_vk) = <PolyIOP<E::Fr> as HyperPlonkSNARK<E, MultilinearKzgPCS<E>>>::preprocess(
705 &bad_index, &pcs_srs,
706 )?;
707 assert_eq!(
708 <PolyIOP<E::Fr> as HyperPlonkSNARK<E, MultilinearKzgPCS<E>>>::verify(
709 &bad_vk, &pi.0, &proof,
710 )?,
711 false
712 );
713
714 // bad path 2: wrong witness
715 let mut w1_bad = w1.clone();
716 w1_bad.0[0] = E::Fr::one();
717 assert!(
718 <PolyIOP<E::Fr> as HyperPlonkSNARK<E, MultilinearKzgPCS<E>>>::prove(
719 &pk,
720 &pi.0,
721 &[w1_bad, w2],
722 )
723 .is_err()
724 );
725
726 Ok(())
727 }
728}