HYPERPLONK

Understanding how PLONK when expressed over a multilinear polynomial, see this as a study companion while reading the HyperPLONK paper.

Proof systems have long been a fascinating cornerstone of cryptography and theoretical computer science, offering ways to verify complex computations without redoing the heavy lifting. In recent years, a special breed of these systems—called SNARKs (Succinct Non-Interactive Arguments of Knowledge)—has captured the spotlight. SNARKs allow someone to prove they’ve correctly solved a problem, delivering a proof that’s both tiny and quick to check, all without spilling any secrets. This blend of efficiency and privacy has sparked a wave of real-world applications, from scaling blockchains to securing sensitive data.

Among the SNARK family, Plonk has risen as a fan favorite. Its proofs are impressively compact—think just a few hundred bytes—and can be verified in a flash, making it a go-to for industries like decentralized finance and beyond. Plonk’s flexibility shines through its support for custom gates, letting developers tailor it to specific needs. But there’s a hitch: when the circuits get massive—say, millions or billions of gates—the prover (the one generating the proof) starts to sweat. The culprit? Operations like fast Fourier transforms (FFTs), which Plonk relies on to handle its univariate polynomials. These FFTs scale quasi-linearly with circuit size (think O(s log s)), turning proof generation into a bottleneck for large-scale tasks.

The FFT algorithm is quite fascinating, but this introduces significant overhead in the PLONK PIOP when building the polynomials representing the circuit trace. The goal of HyperPLONK is to eliminate FFT from this flow.

In a recent paper, the xAI team introduces HyperPLONK, a clever evolution of the Plonk Interactive Oracle Proof (IOP) and its extensions. Unlike Plonk, HyperPLONK operates over the boolean hypercube—denoted as Bµ := {0,1}µ—a space of binary strings of length µ. This shift redefines it as a multilinear-IOP, opening the door to compilation with a suitable multilinear commitment scheme. The result? A SNARK (or even a zkSNARK) with a highly efficient prover.

HyperPLONK inherits Plonk’s flexibility, supporting circuits with custom gates just as seamlessly. But it brings some serious upgrades to the table. By leveraging the boolean hypercube, it ditches the need for fast Fourier transforms (FFTs) during proof generation—a major win. Instead, it taps into the classic SumCheck protocol [61], cutting the prover’s runtime from Oλ(s log s) to a streamlined Oλ(s). For those keeping score, that’s a leap from quasi-linear to linear complexity, making it a powerhouse for large-scale circuits.

Technical Overview

In other to express PLONK over the boolean hypercube we need to break down PLONK into it elementary sub-protocols, and then start making these sub-protocols possible on multilinear polynomials and then trust the compounding effect.

Recap on PLONK

if you don't know how PLONK works, you shouldn't be here!!

PLONK for **mmies | plonk

Plonk SNARK: A Simple Breakdown

Plonk is a cryptography tool that proves you’ve done a calculation correctly without revealing the steps. It’s a type of SNARK, delivering short, fast-to-check proofs. Here’s how it works, step by step.

1. What’s a Circuit?

• A circuit is a math flowchart with steps called gates.

• Each gate takes two inputs and does one operation: add, multiply, or something custom.

• It has n public inputs (starting numbers) and s gates (steps).

2. Turning the Circuit into a Table

• Plonk builds a table M with three columns: Left (L), Right (R), and Output (O).

• The table has n + s + 1 rows:

  • First n rows: Public inputs.

  • Next s rows: Gate inputs and outputs.

  • Last row: A check (set to zero) to confirm the final output.

3. Encoding the Table into a Polynomial

• Plonk uses a special number set called a cyclic subgroup Ω with 3(n + s + 1) elements.

• It creates a polynomial M(X) that encodes the table:

  • M(ω⁰) = L₀, M(ω¹) = R₀, M(ω²) = O₀, and so on for each row.

4. Committing to the Polynomial

• The prover “locks” M(X) in a commitment (like a sealed envelope).

• The verifier can ask questions about it without seeing the polynomial.

5. Proving It’s Correct

• The prover shows:

  • Each gate’s output fits its operation (e.g., O = L * R for multiplication).

  • Inputs and outputs connect properly between gates.

  • The final row confirms the output is correct (zero).

• This is done in a short proof through a back-and-forth process.

...