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, identity_permutation_mles, VPAuxInfo};
9use ark_ec::PairingEngine;
10use ark_poly::DenseMultilinearExtension;
11use ark_std::{end_timer, log2, start_timer, One, Zero};
12use std::{marker::PhantomData, rc::Rc};
13use subroutines::{
14 pcs::prelude::{Commitment, PolynomialCommitmentScheme},
15 poly_iop::{
16 prelude::{PermutationCheck, ZeroCheck},
17 PolyIOP,
18 },
19 BatchProof,
20};
21use transcript::IOPTranscript;
22
23impl<E, PCS> HyperPlonkSNARK<E, PCS> for PolyIOP<E::Fr>
24where
25 E: PairingEngine,
26 // Ideally we want to access polynomial as PCS::Polynomial, instead of instantiating it here.
27 // But since PCS::Polynomial can be both univariate or multivariate in our implementation
28 // we cannot bound PCS::Polynomial with a property trait bound.
29 PCS: PolynomialCommitmentScheme<
30 E,
31 Polynomial = Rc<DenseMultilinearExtension<E::Fr>>,
32 Point = Vec<E::Fr>,
33 Evaluation = E::Fr,
34 Commitment = Commitment<E>,
35 BatchProof = BatchProof<E, PCS>,
36 >,
37{
38 type Index = HyperPlonkIndex<E::Fr>;
39 type ProvingKey = HyperPlonkProvingKey<E, PCS>;
40 type VerifyingKey = HyperPlonkVerifyingKey<E, PCS>;
41 type Proof = HyperPlonkProof<E, Self, PCS>;
42
43 fn preprocess(
44 index: &Self::Index,
45 pcs_srs: &PCS::SRS,
46 ) -> Result<(Self::ProvingKey, Self::VerifyingKey), HyperPlonkErrors> {
47 let num_vars = index.num_variables();
48 let supported_ml_degree = num_vars;
49
50 // extract PCS prover and verifier keys from SRS
51 let (pcs_prover_param, pcs_verifier_param) =
52 PCS::trim(pcs_srs, None, Some(supported_ml_degree))?;
53
54 // build identity oracles
55 let id_oracles = identity_permutation_mles(num_vars, index.num_witness_columns());
56 let mut id_comms = vec![];
57 for id_oracle in id_oracles.iter() {
58 id_comms.push(PCS::commit(&pcs_prover_param, id_oracle)?);
59 }
60
61 // build permutation oracles
62 let mut permutation_oracles = vec![];
63 let mut perm_comms = vec![];
64 let chunk_size = 1 << num_vars;
65 for i in 0..index.num_witness_columns() {
66 let perm_oracle = Rc::new(DenseMultilinearExtension::from_evaluations_slice(
67 num_vars,
68 &index.permutation[i * chunk_size..(i + 1) * chunk_size],
69 ));
70 let perm_comm = PCS::commit(&pcs_prover_param, &perm_oracle)?;
71 permutation_oracles.push(perm_oracle);
72 perm_comms.push(perm_comm);
73 }
74
75 // build selector oracles and commit to it
76 let selector_oracles: Vec<Rc<DenseMultilinearExtension<E::Fr>>> = index
77 .selectors
78 .iter()
79 .map(|s| Rc::new(DenseMultilinearExtension::from(s)))
80 .collect();
81
82 let selector_commitments = selector_oracles
83 .iter()
84 .map(|poly| PCS::commit(&pcs_prover_param, poly))
85 .collect::<Result<Vec<_>, _>>()?;
86
87 Ok((
88 Self::ProvingKey {
89 params: index.params.clone(),
90 id_oracles,
91 permutation_oracles,
92 selector_oracles,
93 selector_commitments: selector_commitments.clone(),
94 permutation_commitments: perm_comms.clone(),
95 id_commitments: id_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 id_commitments: id_comms,
104 },
105 ))
106 }
107
108 /// Generate HyperPlonk SNARK proof.
109 ///
110 /// Inputs:
111 /// - `pk`: circuit proving key
112 /// - `pub_input`: online public input of length 2^\ell
113 /// - `witness`: witness assignment of length 2^n
114 /// Outputs:
115 /// - The HyperPlonk SNARK proof.
116 ///
117 /// Steps:
118 ///
119 /// 1. Commit Witness polynomials `w_i(x)` and append commitment to
120 /// transcript
121 ///
122 /// 2. Run ZeroCheck on
123 ///
124 /// `f(q_0(x),...q_l(x), w_0(x),...w_d(x))`
125 ///
126 /// where `f` is the constraint polynomial i.e.,
127 /// ```ignore
128 /// f(q_l, q_r, q_m, q_o, w_a, w_b, w_c)
129 /// = q_l w_a(x) + q_r w_b(x) + q_m w_a(x)w_b(x) - q_o w_c(x)
130 /// ```
131 /// in vanilla plonk, and obtain a ZeroCheckSubClaim
132 ///
133 /// 3. Run permutation check on `\{w_i(x)\}` and `permutation_oracle`, and
134 /// obtain a PermCheckSubClaim.
135 ///
136 /// 4. Generate evaluations and corresponding proofs
137 /// - 4.1. (deferred) batch opening prod(x) at
138 /// - [0, perm_check_point]
139 /// - [1, perm_check_point]
140 /// - [perm_check_point, 0]
141 /// - [perm_check_point, 1]
142 /// - [1,...1, 0]
143 ///
144 /// - 4.2. permutation check evaluations and proofs
145 /// - 4.2.1. (deferred) wi_poly(perm_check_point)
146 ///
147 /// - 4.3. zero check evaluations and proofs
148 /// - 4.3.1. (deferred) wi_poly(zero_check_point)
149 /// - 4.3.2. (deferred) selector_poly(zero_check_point)
150 ///
151 /// - 4.4. public input consistency checks
152 /// - pi_poly(r_pi) where r_pi is sampled from transcript
153 ///
154 /// - 5. deferred batch opening
155 fn prove(
156 pk: &Self::ProvingKey,
157 pub_input: &[E::Fr],
158 witnesses: &[WitnessColumn<E::Fr>],
159 ) -> Result<Self::Proof, HyperPlonkErrors> {
160 let start = start_timer!(|| "hyperplonk proving");
161 let mut transcript = IOPTranscript::<E::Fr>::new(b"hyperplonk");
162
163 prover_sanity_check(&pk.params, pub_input, witnesses)?;
164
165 // witness assignment of length 2^n
166 let num_vars = pk.params.num_variables();
167
168 // online public input of length 2^\ell
169 let ell = log2(pk.params.num_pub_input) as usize;
170
171 // We use accumulators to store the polynomials and their eval points.
172 // They are batch opened at a later stage.
173 let mut pcs_acc = PcsAccumulator::<E, PCS>::new(num_vars);
174
175 // =======================================================================
176 // 1. Commit Witness polynomials `w_i(x)` and append commitment to
177 // transcript
178 // =======================================================================
179 let step = start_timer!(|| "commit witnesses");
180
181 let witness_polys: Vec<Rc<DenseMultilinearExtension<E::Fr>>> = witnesses
182 .iter()
183 .map(|w| Rc::new(DenseMultilinearExtension::from(w)))
184 .collect();
185
186 let witness_commits = witness_polys
187 .iter()
188 .map(|x| PCS::commit(&pk.pcs_param, x).unwrap())
189 .collect::<Vec<_>>();
190 for w_com in witness_commits.iter() {
191 transcript.append_serializable_element(b"w", w_com)?;
192 }
193
194 end_timer!(step);
195 // =======================================================================
196 // 2 Run ZeroCheck on
197 //
198 // `f(q_0(x),...q_l(x), w_0(x),...w_d(x))`
199 //
200 // where `f` is the constraint polynomial i.e.,
201 //
202 // f(q_l, q_r, q_m, q_o, w_a, w_b, w_c)
203 // = q_l w_a(x) + q_r w_b(x) + q_m w_a(x)w_b(x) - q_o w_c(x)
204 //
205 // in vanilla plonk, and obtain a ZeroCheckSubClaim
206 // =======================================================================
207 let step = start_timer!(|| "ZeroCheck on f");
208
209 let fx = build_f(
210 &pk.params.gate_func,
211 pk.params.num_variables(),
212 &pk.selector_oracles,
213 &witness_polys,
214 )?;
215
216 let zero_check_proof = <Self as ZeroCheck<E::Fr>>::prove(&fx, &mut transcript)?;
217 end_timer!(step);
218 // =======================================================================
219 // 3. Run permutation check on `\{w_i(x)\}` and `permutation_oracle`, and
220 // obtain a PermCheckSubClaim.
221 // =======================================================================
222 let step = start_timer!(|| "Permutation check on w_i(x)");
223
224 let (perm_check_proof, prod_x, frac_poly) = <Self as PermutationCheck<E, PCS>>::prove(
225 &pk.pcs_param,
226 &witness_polys,
227 &witness_polys,
228 &pk.permutation_oracles,
229 &mut transcript,
230 )?;
231 let perm_check_point = &perm_check_proof.zero_check_proof.point;
232
233 end_timer!(step);
234 // =======================================================================
235 // 4. Generate evaluations and corresponding proofs
236 // - permcheck
237 // 1. (deferred) batch opening prod(x) at
238 // - [perm_check_point]
239 // - [perm_check_point[2..n], 0]
240 // - [perm_check_point[2..n], 1]
241 // - [1,...1, 0]
242 // 2. (deferred) batch opening frac(x) at
243 // - [perm_check_point]
244 // - [perm_check_point[2..n], 0]
245 // - [perm_check_point[2..n], 1]
246 // 3. (deferred) batch opening s_id(x) at
247 // - [perm_check_point]
248 // 4. (deferred) batch opening perms(x) at
249 // - [perm_check_point]
250 // 5. (deferred) batch opening witness_i(x) at
251 // - [perm_check_point]
252 //
253 // - zero check evaluations and proofs
254 // - 4.3.1. (deferred) wi_poly(zero_check_point)
255 // - 4.3.2. (deferred) selector_poly(zero_check_point)
256 //
257 // - 4.4. (deferred) public input consistency checks
258 // - pi_poly(r_pi) where r_pi is sampled from transcript
259 // =======================================================================
260 let step = start_timer!(|| "opening and evaluations");
261
262 // (perm_check_point[2..n], 0)
263 let perm_check_point_0 = [&[E::Fr::zero()], &perm_check_point[0..num_vars - 1]].concat();
264 // (perm_check_point[2..n], 1)
265 let perm_check_point_1 = [&[E::Fr::one()], &perm_check_point[0..num_vars - 1]].concat();
266 // (1, ..., 1, 0)
267 let prod_final_query_point =
268 [vec![E::Fr::zero()], vec![E::Fr::one(); num_vars - 1]].concat();
269
270 // prod(x)'s points
271 pcs_acc.insert_poly_and_points(&prod_x, &perm_check_proof.prod_x_comm, perm_check_point);
272 pcs_acc.insert_poly_and_points(&prod_x, &perm_check_proof.prod_x_comm, &perm_check_point_0);
273 pcs_acc.insert_poly_and_points(&prod_x, &perm_check_proof.prod_x_comm, &perm_check_point_1);
274 pcs_acc.insert_poly_and_points(
275 &prod_x,
276 &perm_check_proof.prod_x_comm,
277 &prod_final_query_point,
278 );
279
280 // frac(x)'s points
281 pcs_acc.insert_poly_and_points(&frac_poly, &perm_check_proof.frac_comm, perm_check_point);
282 pcs_acc.insert_poly_and_points(
283 &frac_poly,
284 &perm_check_proof.frac_comm,
285 &perm_check_point_0,
286 );
287 pcs_acc.insert_poly_and_points(
288 &frac_poly,
289 &perm_check_proof.frac_comm,
290 &perm_check_point_1,
291 );
292
293 // s_id(x)'s points
294 for (s_id, s_com) in pk.id_oracles.iter().zip(pk.id_commitments.iter()) {
295 pcs_acc.insert_poly_and_points(s_id, s_com, perm_check_point);
296 }
297
298 // perms(x)'s points
299 for (perm, pcom) in pk
300 .permutation_oracles
301 .iter()
302 .zip(pk.permutation_commitments.iter())
303 {
304 pcs_acc.insert_poly_and_points(perm, pcom, perm_check_point);
305 }
306
307 // witnesses' points
308 // TODO: refactor so it remains correct even if the order changed
309 for (wpoly, wcom) in witness_polys.iter().zip(witness_commits.iter()) {
310 pcs_acc.insert_poly_and_points(wpoly, wcom, perm_check_point);
311 }
312 for (wpoly, wcom) in witness_polys.iter().zip(witness_commits.iter()) {
313 pcs_acc.insert_poly_and_points(wpoly, wcom, &zero_check_proof.point);
314 }
315
316 // - 4.3.2. (deferred) selector_poly(zero_check_point)
317 pk.selector_oracles
318 .iter()
319 .zip(pk.selector_commitments.iter())
320 .for_each(|(poly, com)| {
321 pcs_acc.insert_poly_and_points(poly, com, &zero_check_proof.point)
322 });
323
324 // - 4.4. public input consistency checks
325 // - pi_poly(r_pi) where r_pi is sampled from transcript
326 let r_pi = transcript.get_and_append_challenge_vectors(b"r_pi", ell)?;
327 let tmp_point = [vec![E::Fr::zero(); num_vars - ell], r_pi].concat();
328 pcs_acc.insert_poly_and_points(&witness_polys[0], &witness_commits[0], &tmp_point);
329 end_timer!(step);
330
331 // =======================================================================
332 // 5. deferred batch opening
333 // =======================================================================
334 let step = start_timer!(|| "deferred batch openings prod(x)");
335 let batch_openings = pcs_acc.multi_open(&pk.pcs_param, &mut transcript)?;
336 end_timer!(step);
337
338 end_timer!(start);
339
340 Ok(HyperPlonkProof {
341 // PCS commit for witnesses
342 witness_commits,
343 // batch_openings,
344 batch_openings,
345 // =======================================================================
346 // IOP proofs
347 // =======================================================================
348 // the custom gate zerocheck proof
349 zero_check_proof,
350 // the permutation check proof for copy constraints
351 perm_check_proof,
352 })
353 }
354
355 /// Verify the HyperPlonk proof.
356 ///
357 /// Inputs:
358 /// - `vk`: verification key
359 /// - `pub_input`: online public input
360 /// - `proof`: HyperPlonk SNARK proof
361 /// Outputs:
362 /// - Return a boolean on whether the verification is successful
363 ///
364 /// 1. Verify zero_check_proof on
365 ///
366 /// `f(q_0(x),...q_l(x), w_0(x),...w_d(x))`
367 ///
368 /// where `f` is the constraint polynomial i.e.,
369 /// ```ignore
370 /// f(q_l, q_r, q_m, q_o, w_a, w_b, w_c)
371 /// = q_l w_a(x) + q_r w_b(x) + q_m w_a(x)w_b(x) - q_o w_c(x)
372 /// ```
373 /// in vanilla plonk, and obtain a ZeroCheckSubClaim
374 ///
375 /// 2. Verify perm_check_proof on `\{w_i(x)\}` and `permutation_oracles`
376 ///
377 /// 3. check subclaim validity
378 ///
379 /// 4. Verify the opening against the commitment:
380 /// - check permutation check evaluations
381 /// - check zero check evaluations
382 /// - public input consistency checks
383 fn verify(
384 vk: &Self::VerifyingKey,
385 pub_input: &[E::Fr],
386 proof: &Self::Proof,
387 ) -> Result<bool, HyperPlonkErrors> {
388 let start = start_timer!(|| "hyperplonk verification");
389
390 let mut transcript = IOPTranscript::<E::Fr>::new(b"hyperplonk");
391
392 let num_selectors = vk.params.num_selector_columns();
393 let num_witnesses = vk.params.num_witness_columns();
394 let num_vars = vk.params.num_variables();
395
396 // online public input of length 2^\ell
397 let ell = log2(vk.params.num_pub_input) as usize;
398
399 // =======================================================================
400 // 0. sanity checks
401 // =======================================================================
402 // public input length
403 if pub_input.len() != vk.params.num_pub_input {
404 return Err(HyperPlonkErrors::InvalidProver(format!(
405 "Public input length is not correct: got {}, expect {}",
406 pub_input.len(),
407 1 << ell
408 )));
409 }
410
411 // Extract evaluations from openings
412 let prod_evals = &proof.batch_openings.f_i_eval_at_point_i[0..4];
413 let frac_evals = &proof.batch_openings.f_i_eval_at_point_i[4..7];
414 let id_evals = &proof.batch_openings.f_i_eval_at_point_i[7..7 + num_witnesses];
415 let perm_evals =
416 &proof.batch_openings.f_i_eval_at_point_i[7 + num_witnesses..7 + 2 * num_witnesses];
417 let witness_perm_evals =
418 &proof.batch_openings.f_i_eval_at_point_i[7 + 2 * num_witnesses..7 + 3 * num_witnesses];
419 let witness_gate_evals =
420 &proof.batch_openings.f_i_eval_at_point_i[7 + 3 * num_witnesses..7 + 4 * num_witnesses];
421 let selector_evals = &proof.batch_openings.f_i_eval_at_point_i
422 [7 + 4 * num_witnesses..7 + 4 * num_witnesses + num_selectors];
423 let pi_eval = proof.batch_openings.f_i_eval_at_point_i.last().unwrap();
424
425 // =======================================================================
426 // 1. Verify zero_check_proof on
427 // `f(q_0(x),...q_l(x), w_0(x),...w_d(x))`
428 //
429 // where `f` is the constraint polynomial i.e.,
430 //
431 // f(q_l, q_r, q_m, q_o, w_a, w_b, w_c)
432 // = q_l w_a(x) + q_r w_b(x) + q_m w_a(x)w_b(x) - q_o w_c(x)
433 //
434 // =======================================================================
435 let step = start_timer!(|| "verify zero check");
436 // Zero check and perm check have different AuxInfo
437 let zero_check_aux_info = VPAuxInfo::<E::Fr> {
438 max_degree: vk.params.gate_func.degree(),
439 num_variables: num_vars,
440 phantom: PhantomData::default(),
441 };
442 // push witness to transcript
443 for w_com in proof.witness_commits.iter() {
444 transcript.append_serializable_element(b"w", w_com)?;
445 }
446
447 let zero_check_sub_claim = <Self as ZeroCheck<E::Fr>>::verify(
448 &proof.zero_check_proof,
449 &zero_check_aux_info,
450 &mut transcript,
451 )?;
452
453 let zero_check_point = zero_check_sub_claim.point.clone();
454
455 // check zero check subclaim
456 let f_eval = eval_f(&vk.params.gate_func, selector_evals, witness_gate_evals)?;
457 if f_eval != zero_check_sub_claim.expected_evaluation {
458 return Err(HyperPlonkErrors::InvalidProof(
459 "zero check evaluation failed".to_string(),
460 ));
461 }
462
463 end_timer!(step);
464 // =======================================================================
465 // 2. Verify perm_check_proof on `\{w_i(x)\}` and `permutation_oracle`
466 // =======================================================================
467 let step = start_timer!(|| "verify permutation check");
468
469 // Zero check and perm check have different AuxInfo
470 let perm_check_aux_info = VPAuxInfo::<E::Fr> {
471 // Prod(x) has a max degree of witnesses.len() + 1
472 max_degree: proof.witness_commits.len() + 1,
473 num_variables: num_vars,
474 phantom: PhantomData::default(),
475 };
476 let perm_check_sub_claim = <Self as PermutationCheck<E, PCS>>::verify(
477 &proof.perm_check_proof,
478 &perm_check_aux_info,
479 &mut transcript,
480 )?;
481
482 let perm_check_point = perm_check_sub_claim
483 .product_check_sub_claim
484 .zero_check_sub_claim
485 .point
486 .clone();
487
488 let alpha = perm_check_sub_claim.product_check_sub_claim.alpha;
489 let (beta, gamma) = perm_check_sub_claim.challenges;
490
491 // check evaluation subclaim
492 let perm_gate_eval = eval_perm_gate(
493 prod_evals,
494 frac_evals,
495 witness_perm_evals,
496 id_evals,
497 perm_evals,
498 alpha,
499 beta,
500 gamma,
501 *perm_check_point.last().unwrap(),
502 )?;
503 if perm_gate_eval
504 != perm_check_sub_claim
505 .product_check_sub_claim
506 .zero_check_sub_claim
507 .expected_evaluation
508 {
509 return Err(HyperPlonkErrors::InvalidVerifier(
510 "evaluation failed".to_string(),
511 ));
512 }
513
514 end_timer!(step);
515 // =======================================================================
516 // 3. Verify the opening against the commitment
517 // =======================================================================
518 let step = start_timer!(|| "verify commitments");
519
520 // generate evaluation points and commitments
521 let mut comms = vec![];
522 let mut points = vec![];
523
524 let perm_check_point_0 = [&[E::Fr::zero()], &perm_check_point[0..num_vars - 1]].concat();
525 let perm_check_point_1 = [&[E::Fr::one()], &perm_check_point[0..num_vars - 1]].concat();
526 let prod_final_query_point =
527 [vec![E::Fr::zero()], vec![E::Fr::one(); num_vars - 1]].concat();
528
529 // prod(x)'s points
530 comms.push(proof.perm_check_proof.prod_x_comm);
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 points.push(perm_check_point.clone());
535 points.push(perm_check_point_0.clone());
536 points.push(perm_check_point_1.clone());
537 points.push(prod_final_query_point);
538
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 // s_id's points
548 for &id_com in vk.id_commitments.iter() {
549 comms.push(id_com);
550 points.push(perm_check_point.clone());
551 }
552
553 // perms' points
554 for &pcom in vk.perm_commitments.iter() {
555 comms.push(pcom);
556 points.push(perm_check_point.clone());
557 }
558
559 // witnesses' points
560 for &wcom in proof.witness_commits.iter() {
561 comms.push(wcom);
562 points.push(perm_check_point.clone());
563 }
564 for &wcom in proof.witness_commits.iter() {
565 comms.push(wcom);
566 points.push(zero_check_point.clone());
567 }
568
569 // selector_poly(zero_check_point)
570 for &com in vk.selector_commitments.iter() {
571 comms.push(com);
572 points.push(zero_check_point.clone());
573 }
574
575 // - 4.4. public input consistency checks
576 // - pi_poly(r_pi) where r_pi is sampled from transcript
577 let r_pi = transcript.get_and_append_challenge_vectors(b"r_pi", ell)?;
578 let tmp_point = [vec![E::Fr::zero(); num_vars - ell], r_pi].concat();
579 // check public evaluation
580 let pi_poly = DenseMultilinearExtension::from_evaluations_slice(ell as usize, pub_input);
581 let expect_pi_eval = evaluate_opt(&pi_poly, &tmp_point[..]);
582 if expect_pi_eval != *pi_eval {
583 return Err(HyperPlonkErrors::InvalidProver(format!(
584 "Public input eval mismatch: got {}, expect {}",
585 pi_eval, expect_pi_eval,
586 )));
587 }
588 comms.push(proof.witness_commits[0]);
589 points.push(tmp_point);
590
591 assert_eq!(comms.len(), proof.batch_openings.f_i_eval_at_point_i.len());
592
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(2u64),
676 E::Fr::from(3u64),
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(32u64),
683 E::Fr::from(243u64),
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}