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