HyperPlonk

Introduction

Plonk is a powerful tool that can be tweaked to support custom gates (TurboPlonk) and lookup tables (Plonkup). However, as circuits grow larger, FFT becomes a bottleneck. HyperPlonk modifies Plonk by using multivariate polynomials over a boolean hypercube. This achieves two main advantages:

1. Eliminating the need for FFT.

2. Enabling efficient computation of high-degree custom gates without significant overhead, resulting in faster proving times.

Background

Why is FFT a bottleneck?

The diagram above illustrates the FFT process for a polynomial of size 8. First, as shown on the left side of the diagram, a bit reversal operation is performed. Then, butterfly operations are executed at each stage. A bit reversal operation takes $O(N)$, and a butterfly operation also requires $O(N)$. Since the number of stages is $\log N$, the overall complexity is $O(N \cdot \log N)$. Furthermore, FFT is notoriously difficult to parallelize. This is because, as the stages progress, the memory locations required to compute the outputs for the next stage become increasingly scattered. If calculations must be performed on hardware like GPUs with limited memory, these constraints can be critical.

Modern SNARK

Polynomial IOP (Interactive Oracle Proof) refers to a verification method where the prover provides an oracle to the verifier. The verifier interacts by sampling random points, and in the final round, accesses the oracle to verify computations on these random points.

Here, the oracle can be thought of as a polynomial. However, since polynomials often have high degrees, they are not succinct. To address this, a PCS (Polynomial Commitment Scheme) is used. Instead of sending the full polynomial, the prover sends a commitment that represents the polynomial. During the final round of verification, the prover can reveal (or "open") the evaluations at the random points along with a proof, enabling succinct verification. This combination allows for succinct SNARKs.

Modern SNARKs are built by combining Polynomial IOP with PCS, structured as follows:

• Univariate IOP + Univariate PCS: Examples include Sonic, Marlin, and Plonk.

• Multilinear IOP + Multilinear PCS: Examples include Hyrax, Libra, Spartan, Quarks, and Gemini.

• Vector IOP + Vector PCS: Examples include STARK, Aurora, Virgo, Brakedown, and Orion.

When is FFT used in Plonk?

Let's walk through a simple circuit as an example. The circuit above represents a Fibonacci sequence starting with $(1, 1)$. Each column in the circuit is interpreted as a univariate polynomial. Since Plonk implements Univariate IOP + Univariate PCS, the protocol proceeds as follows:

For simplicity, the Wiring Check (Permutation Argument) is omitted in this example, as the focus is on why FFT is used.

1. The prover commits to the polynomials A, B, and C to assert that the following relationship holds. This step uses PCS.BatchCommit and corresponds to Oracle:

1. After Poly IOP for Wiring Identity, to assert that the gate identity is satisfied, the prover commits to $Q$. Since $t$ is a known polynomial (pre-shared between prover and verifier), it does not require a separate commitment. This step corresponds to Poly IOP for Gate Identity → Poly IOP for Quotient Check:

1. The verifier samples a random $x$ from the entire field space.

2. Since $x$ is sampled randomly from the field, the prover must interpolate the polynomials $A, B,$ and $C$ to their Lagrange basis using IFFT:

1. The prover sends the evaluations $A(x), B(x), C(x),$ and $Q(x)$ along with the opening proof:

1. The verifier checks that the gate identity holds at the random point $x$:

High-degree custom gates in Plonk

This section is based on the Halo2 book. Custom gates enable representation of complex operations that cannot easily be expressed with simple addition and multiplication. Let’s explore how they are implemented in Plonk.

Consider a polynomial of degree $d$ (or a table with $d + 1$ rows). In the earlier example, we dealt with a simple addition operation, where the degree of $A + B - C$ was $d$. This simplicity made computation straightforward.

When dealing with more complex circuits, custom gates can be represented as $f_i$, with selectors $s_i$. For a given domain $H$, each custom gate $f_i$ must satisfy:

Checking each gate $f_i$ individually is inefficient for the verifier. Instead, we use a common ZK technique: random linear combination. Starting from step 2 of the protocol:

1. The verifier samples a random y.

2. Using $y$, the prover combines all custom gates into a single equation:

Here, $m$ is the number of gates. The degree of $Q$ is calculated as:

For example, if $m = 3$, the custom gates $f_i$ are the following:

Then the degree of $Q$ is $n \cdot d - 1$, where $n$ is the max degree of the custom gates. (i.e., the maximum number of polynomial multiplications). Here, $n$ is 3. Since the degree of $Q$ can be much higher than $d$, it needs to be decomposed into $n$ smaller polynomials $q_i$ to fit within the commitment scheme:

Before committing to $q_i$, the prover must compute $f_i$. For high-degree gates, this involves the following:

The degree becomes $n \cdot d$ for the sections highlighted in green, which significantly slows down computation. If the $n$ of the custom gate is set too small, flexibility to create a diverse range of computations decreases. On the other hand, if $n$ is set too large, it introduces significant overhead in High-Degree FFT, Gate Evaluation, and High-Degree Inverse FFT. Therefore, $n$ must be set to an appropriate value. For example, $f(x) = x * e^{2 pi i \xi x}$n is 9 in Polygon Miden. On the other hand, there is no such limitation in Halo2.

In summary, in a simple protocol as discussed earlier, $Q$ could be committed before conducting the Inverse FFT. However, when custom gates are introduced, committing $Q$ requires going through the following steps:

Inverse FFT → High Degree FFT → Gate Evaluation → High Degree Inverse FFT.

1. The prover commits to $q_0, q_1, q_2$.

1. The verifier samples a random point $x$.

2. The prover sends $A(x), B(x), C(x)$ and $q(x)$ along with the opening proof $\pi$ to the verifier:

1. The verifier checks whether the following equation holds at the random point $x$. Here, $s_i$ is assumed to be a polynomial already known to both the prover and the verifier:

1. To validate the proof, the verifier performs the following test. If the test is passed, the verifier accepts the proof:

From the above, the approximate total execution time for the Plonk prover can be calculated as follows:

Furthermore, according to the Halo2 benchmarks from the Tachyon repository, it can be observed that the majority of the time is spent on the build $h$ poly step, which is directly related to $Q$.

Protocol Explanation

This image is taken from the paper, and describes HyperPlonk and HyperPlonk+.

ZeroCheck → SumCheck

In HyperPlonk, the way constraints are imposed is not fundamentally different from Plonk. For example, to represent an addition gate, the following expression can be used:

Plonk uses a ZeroCheck followed by a QuotientCheck, as shown below:

where $H := \{ \omega^i | i = 0, 1, \dots, d-1 \}$ and $\omega$ is $d$-th root of unity.

HyperPlonk instead uses a ZeroCheck followed by a SumCheck:

where $B_\mu := \{0, 1\}^\mu$ is the boolean hypercube.

High-degree custom gates in HyperPlonk

Why does using SumCheck eliminate the overhead for high-degree custom gates? Using the same example as above, the prover's claim can be expressed as follows:

In the SumCheck protocol, the univariate polynomial sent by the prover to the verifier in each round has a degree that is less than or equal to the degree of the multivariate polynomial. Thus, the prover only needs to send univariate polynomials with a maximum degree equal to the degree of the custom gate + 1.

Consider how a univariate polynomial can be constructed from a 1st-degree multivariate polynomial. For a 1st-degree polynomial in 2 variables, it can be expressed as:

Now let’s create an degree 1 univariate polynomial $P_0$ based on the multilinear polynomial above.

The complexity for this computation in round $i$ (starting from 0) is $O(2^{μ - i - 1})$.

For higher-degree multivariate polynomials, the same method is applied to each component, and the results are multiplied. For example, with $f_0$:

Let’s analyze complexity for each round $i$ (starting from 0):

• Univariate Polynomial Construction: $O(n\cdot 2^{μ − i −1})$, where $n$ is the number of components.

• Polynomial Multiplication: $O(n^2)$

Since the number of total rounds is $\mu$, the total complexity is computed to $O(n \cdot 2μ + μ \cdot n^2)$ as follows:

If $n$ is treated as a constant, the SumCheck protocol allows ZeroCheck to be performed in linear time. For reference, the complexity calculation here differs from the one provided in the paper. For more details, refer to Section 3.1 (Computing SumCheck for high-degree polynomials) and Section 3.8 of the original paper, which introduce further optimizations for the SumCheck protocol.

ProductCheck

ProductCheck is a method to verify whether the product of a polynomial over a boolean hypercube equals a constant $c$:

For univariate polynomials, this is typically computed using a running product column, as explained in From Halo2, LogUp to LogUp-GKR. For multivariate polynomials, the process involves the following steps:

1. Define $v$ to satisfy the following conditions:

This allows $v$ to be computed as shown in the diagram below:

1. Define a new function $\hat{h}$ as follows:

1. Using $\hat{h}$, perform ZeroCheck → SumCheck as described earlier. Since $\hat{h}$ evaluates to zero for all points in $\{0,1\}^3$, this check ensures the validity of $v$.

2. Finally, the verifier queries $v$ at $(1, \dots, 1, 0)$ to ensure the products of $h$ are equal to $c$.

Wiring Identity → MultiSetEquality

In univariate polynomials, verifying Wiring Identity involves constructing $s_i^\sigma$ as shown in the figure below. The green arrows denote how the label is moved.

This is then transformed into a MultiSetEquality using a random value $\alpha$:

In multivariate polynomials, $s_i^\sigma$ is similarly constructed as shown in the figure below.

Using the same random value $\alpha$, this is transformed into a MultiSetEquality as follows:

MultiSetEquality can now be replaced by the ProductCheck protocol described earlier. This enables efficient verification using the established steps for product consistency.

For handling Permutation PIOP on small fields, Section 3.6 of the paper provides a detailed explanation. Interested readers are encouraged to explore that section for additional insights.

Shift Function for Lookup Argument

Incorporating Plookup into HyperPlonk creates HyperPlonk+.

where $s$ is $(f, t)$ sorted by $t$.

The equation above, taken from the Plookup paper, shows how values $f_i, s_i, t_{i+1}, s_{i+1}$ ​ are queried at both the $i$-th and $i+1$-th indices. For univariate polynomials in Plonk, this can be easily expressed as:

This "shift through the domain" is achieved using a shift function, which for univariate polynomials is defined as:

For multivariate polynomials, the shift function can be represented using a mechanism similar to the one illustrated below (also from the paper):

Consider $g_4(b_1, b_2, b_3, b_4)$ in the context of a 4-dimensional boolean hypercube. The function $g_4$ operates as follows:

This cyclically shifts all non-zero points in the boolean hypercube.

The XOR operation can be algebraically expressed as:

However, this representation is quadratic, leading to an explosion in degree when using nested functions like $f(g(X))$.

Luckily, $g_4$ can be simplified based on specific rules:

This reduces the complexity, allowing $g_4$ to be expressed as a linear function rather than a quadratic one. This is depicted in the formula below:

Using this linearized shift function, MultiSetEquality Check can be efficiently performed. By leveraging the defined Polynomial IOP, this shift function enables the protocol to verify lookup arguments in HyperPlonk+ without significant overhead.

This also implies that the domain in the circuit must be represented differently. Specifically, the point $(0, 0)$ cannot be included because it is not cyclic. Instead, the cyclic domain should exclude $(0, 0)$ and follow this order in the case of 4 or 8 rows:

Conclusion

We have explored how HyperPlonk operates through examples. Unlike Plonk, HyperPlonk introduces a method to leverage the boolean hypercube for proofs. This approach eliminates the computational overhead caused by FFTs as the maximum degree of custom gates increases, resulting in faster proof generation.

The figure above is a capture from the presentation by Benedikt Bünz at ZK Summit 8 (YouTube link):

Graph b above and the video screenshot both support this observation. While not covered, HyperPlonk has also contributed to the optimization of multivariate polynomial commitments, as seen in systems like Orion+. Despite these significant contributions, the Conclusions and Open Problems section of the paper highlights several areas for future work, introducing ideas for continued improvements and research.

Written by ryan Kim from A41