HyperPlonk, a zk-proof system for ZKEVMs

By: Binyi Chen and Benedikt Bünz

Paper: https://eprint.iacr.org/2022/1355

The core building block of both privacy and scalability for blockchains are zero-knowledge proof systems. These systems allow a prover to convince a verifier that some state transition was done correctly. This could, for example, be a CAPE transaction or a roll-up of many transactions. The two incredible features of zero-knowledge proofs (aka zk-SNARKs) are that (i) the proof reveals no information about the state transition, beyond that it is valid; and (ii) the proof is short and efficient to check, even if the state transition is complex and involves many transactions.

Over the past few years, Plonk has become the proof system of choice for most applications in the blockchain space. The reason is that Plonk provides great tradeoffs with short proofs, efficient verification, a high level of customization, and minimal trust assumptions. Unfortunately, Plonk still has limitations, especially when proving large statements or trying to use highly parallel hardware. These limitations are especially important when proving large and complex statements such as rollups and zkEVMs.

To overcome these bottlenecks, we built Hyperplonk. A new zk-proof system with a fully linear time prover and support for high-degree and lookup custom gates. Our prototype Hyperplonk implementation already beats our highly optimized Plonk implementation (Jellyfish), starting from circuits with about 16000 constraints, and the gap keeps growing as statement size increases or more parallelism is used. Hyperplonk also enables high-degree custom gates and lookup, something that is particularly useful for complicated circuits like the ZK-EVM one. These special gates can be used to enable complex EVM OPCODES and building a memory stack.

Plonk: background and limitations

Modern proof systems are built from two key building blocks. An information-theoretic polynomial interactive oracle proof (PIOP) that takes a computation and turns it into polynomial equations. And a polynomial commitment scheme that is used to prove that the equations are satisfied. Example PIOPs are Plonk, Marlin, and Spartan. Examples of polynomial commitment schemes are KZG, Bulletproofs, Virgo (FRI), and DARK¹ .

The benefit of this splitting is that you can take any PIOP and any polynomial commitment scheme and combine them for novel properties. For example, Halo2 combines the PLONK PIOP with the Bulletproofs polynomial commitment. Plonky2 combines PLONK with a FRI-based polynomial commitment. Xiphos, combines Quarks, an improvement on the spartan PIOP, with Dory, and so on.

The PLONK PIOP has received a lot of industry attention. One of the key reasons is that, unlike other proof systems, it enables custom gates. While traditional proof systems require you to formulate the computation as additions and multiplications, PLONK enables different gates, such as X³*Y+Y+X=Z. In our recent work on VERI-ZEXE we showed that these gates can significantly reduce the prover runtime. Additionally PLONK (and Plookup) enables something called lookup. This, enables, efficiently proving that a value is inside a table. For example, if the table contained the numbers [0,...,2³²-1] then you can efficiently show that a value is a 32-bit number. This, again, can significantly help with prover runtime and the types of computations you can efficiently express. For exactly this reason, all the efforts to build a ZKEVM have been using PLONK or PLONK-like systems². Until now there was a major downside to these systems.

As a first step PLONK requires you to encode the circuit values as a polynomial. As shown in the figure below, we write the circuit as a table and then build a polynomial such that on a set of points the polynomial equals these values. Finding this polynomial is done using the so-called Fast-Fourier-Transform (or FFT).

Writing a computation as a circuit and then the computation trace as a table

Encoding the trace as a polynomial. This requires an FFT and the goal of Hyperplonk is to remove this expensive step.

FFTs are beautiful algorithms [see here], but unfortunately, they still have a significant overhead. The runtime of an FFT is proportional to n log₂(n) for a circuit of size n. When n is small or medium-sized, this does not present a challenge but for ns larger than about a million (and log₂(n) about 20) FFTs become a significant factor. This is, especially an issue for systems like zk-rollups and zkEVMs when circuits can have almost a billion gates. An additional bottleneck of these FFTs is that they don’t parallelize very well and require complex memory accesses. All of this limits the deployment and usefulness of custom hardware (such as GPUs, FPGAs, and ASICs) for zero-knowledge proofs.

Removing the FFTs by going multi-variate

The goal of Hyperplonk is to remove the requirements for FFTs from Plonk to make it more scalable and suitable for custom hardware. In order to do this, we rely on some old tricks that have been used in proof systems going back to the early 90s [Sumcheck, GKR,Hyrax,Spartan,Quarks,…]. Instead of encoding a polynomial P(X) with one variable, we use multiple variables (log₂(n) to be precise) and encode a polynomial P(X₁,X₂,...,Xμ). It turns out that with log₂(n) variables we can find a polynomial that encodes n values but is at most linear in every variable. That means the polynomial has no Xi² terms, for example. More precisely, we can easily in time n encode a so-called multi-linear polynomial that has a certain set of values at the values (0,0,…0) to (1,1,…,1). This is called the boolean hypercube, as each variable takes on the value either 0 or 1 and as you may have guessed, this hypercube inspired the name for HyperPlonk.

Unlike standard Plonk, HyperPlonk encodes the computation trace as a multi-linear polynomial with multiple variables.

Building a toolbox for multi-linear polynomials

Efficiently encoding the values as a multi-linear polynomial removes the requirement for FFTs, but this only serves as a starting point. Plonk can be described as a set of subprotocols that are called to build the big protocol. These protocols include a circuit for gate check that ensures that every gate in the circuit is satisfied. For example, if the inputs to a multiplication gate are 7 and 11 then the output must be 77. Another protocol is the so-called wiring or permutation check. This protocol ensures that the circuit is wired correctly and that the output of one gate is the correct input of a succeeding gate. For example, we want to ensure that the output of gate 1, equals the right input of gate 2. In Plonk these protocols are built using univariate polynomials (and a lot of them also require additional FFTs). We need to adapt and build protocols for these checks that work with multi-linear polynomials and do not rely on FFTs. Toward this, we built a toolbox of subprotocols for multi-linear polynomials. Some of these are new (like a batching protocol for evaluating many polynomials at many points), and some of these are very old, like the famous SumCheck protocol (for which we provide an improvement for high degree gates).

Hyperplonk consists of many sub-protocols and is based on the famous sumcheck protocol.

HyperPlonk, HyperPlonk+, and custom gates

With this toolbox in place, we can easily build HyperPlonk. One key goal for this research was to support all the nice Plonk features with Hyperplonk. It turns out that we can do even better than that. Plonk supports custom gates but there is a tradeoff where too large (or more specifically high-degree) custom gates will increase the size of the so-called quotient polynomial. This slows down the prover and reduce the benefit that one might get from having smaller circuits. Because of this, the largest gate degree used in practice is 5 (So for example X⁵-Y=Z). In Hyperplonk, there is no quotient polynomial and the tradeoff for higher-degree gates is much better than in Plonk. Our evaluation shows that Hyperplonk could potentially support degree 32 gates or even larger which for certain computations could significantly, improve the prover time. We also support lookups and call the resulting protocol that combines HyperPlonk with lookups HyperPlonk+. We believe that the better support for high-degree and lookup gates can make HyperPlonk a great fit for zkEVM applications.

Bonus: Orion+, a super-fast polynomial commitment scheme

As we wrote earlier, modern proof systems consist of both a PIOP and a polynomial commitment scheme (PCS). HyperPlonk is a PIOP, and there are many interesting polynomial commitment schemes that it could be used with (in our evaluation, we use a multi-linear variant of KZG). One, recent and particularly interesting PCS is called Orion. Orion has the out-and-out fastest prover, and it is fully compatible with HyperPlonk and HyperPlonk+. And Orion proof for a million gates, takes only 3s to generate. Unfortunately, it also has very large proofs of about ~5.5MB for circuits with ~30 million gates (KZG proofs would be about 1KB for the same size). We reconcile this by building Orion+, which drastically reduces the proof size of Orion down to ~7KB for the same circuit. Orion+, in its design, actually uses HyperPlonk and its commit and prove features. We are still evaluating the practicality of Orion+, but it is a very exciting direction that could deliver a blazing-fast prover with a reasonable proof size.

Implementation and Evaluation

We have a prototype implementation of HyperPlonk and compare it against Jellyfish, the state-of-the art Plonk implementation we built here at Espresso. Our preliminary results, already show the power of Hyperplonk. Hyperplonk beats Jellyfish starting from about circuits with 16000 constraints, and the bigger the circuit, the bigger the gap. Hyperplonk proofs are a bit larger than Plonk proofs (~6kb vs. 1kb) but for many applications this is ok and they are significantly smaller than any other proof system that works without FFTs.

We also see that Hyperplonk can efficiently support high-degree gates. A degree 32 gate is only 20% more expensive than a degree 2 gate.

We are still working on the implementation (and its potential optimizations) of HyperPlonk. We also plan to integrate it into our Jellyfish library in the near future.

Footnotes

1. Some systems like Bulletproofs are both a PIOP and a commitment scheme.
2. Starkware’s AIR has very similar characteristics to PLONK