Paper 2022/1355

HyperPlonk: Plonk with Linear-Time Prover and High-Degree Custom Gates

Binyi Chen, Espresso Systems
Benedikt Bünz, Espresso Systems, Stanford University
Dan Boneh, Stanford University
Zhenfei Zhang, Espresso Systems
Abstract

Plonk is a widely used succinct non-interactive proof system that uses univariate polynomial commitments. Plonk is quite flexible: it supports circuits with low-degree ``custom'' gates as well as circuits with lookup gates (a lookup gate ensures that its input is contained in a predefined table). For large circuits, the bottleneck in generating a Plonk proof is the need for computing a large FFT. We present HyperPlonk, an adaptation of Plonk to the boolean hypercube, using multilinear polynomial commitments. HyperPlonk retains the flexibility of Plonk but provides several additional benefits. First, it avoids the need for an FFT during proof generation. Second, and more importantly, it supports custom gates of much higher degree than Plonk without harming the running time of the prover. Both of these can dramatically speed up the prover's running time. Since HyperPlonk relies on multilinear polynomial commitments, we revisit two elegant constructions: one from Orion and one from Virgo. We show how to reduce the Orion opening proof size to less than 10kb (an almost factor 1000 improvement) and show how to make the Virgo FRI-based opening proof simpler and shorter.

Note: 1. Added a new permutation PIOP for small fields (Sec 3.6). 2. Updated experiments and evaluations (Sec 6). 3. Revised the unrolled and optimized HyperPlonk (Appendix C).

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in EUROCRYPT 2023
Keywords
zero-knowledge proofssumcheckplonkpolynomial commitment scheme
Contact author(s)
binyi @ espressosys com
benedikt @ cs stanford edu
dabo @ cs stanford edu
zhangzhenfei @ gmail com
History
2023-12-21: last of 2 revisions
2022-10-10: received
See all versions
Short URL
https://ia.cr/2022/1355
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1355,
      author = {Binyi Chen and Benedikt Bünz and Dan Boneh and Zhenfei Zhang},
      title = {HyperPlonk: Plonk with Linear-Time Prover and High-Degree Custom Gates},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1355},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1355}},
      url = {https://eprint.iacr.org/2022/1355}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.