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

Binyi Chen, Benedikt Bünz, Dan Boneh, Zhenfei Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 10 KB (an almost factor 1000 improvement) and show how to make the Virgo FRI-based opening proof simpler and shorter (This is an extended abstract. The full version is available on EPRINT[22]).

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology – EUROCRYPT 2023 - 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2023, Proceedings
EditorsCarmit Hazay, Martijn Stam
PublisherSpringer Science and Business Media Deutschland GmbH
Pages499-530
Number of pages32
ISBN (Print)9783031306167
DOIs
StatePublished - 2023
Event42nd Annual International Conference on Theory and Applications of Cryptographic Techniques, EUROCRYPT 2023 - Lyon, France
Duration: Apr 23 2023Apr 27 2023

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume14005 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference42nd Annual International Conference on Theory and Applications of Cryptographic Techniques, EUROCRYPT 2023
Country/TerritoryFrance
CityLyon
Period4/23/234/27/23

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'HyperPlonk: Plonk with Linear-Time Prover and High-Degree Custom Gates'. Together they form a unique fingerprint.

Cite this