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