Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Cryptographic Layer: Polynomial Commitments

The Polynomial IOP (Poly-IOP) provides an abstract, information-theoretically secure blueprint for a proof. However, it’s not practical on its own. Its “oracles” are enormous polynomials, and sending them over a network would violate the core “succinctness” promise of a SNARK.

This is where a Polynomial Commitment Scheme (PCS) comes in. A PCS is a cryptographic tool that transforms the abstract Poly-IOP into a concrete, practical protocol. It allows a prover to “commit” to a high-degree polynomial with a tiny piece of data, and then later prove that the polynomial evaluates to a specific value at any chosen point, without necessarily having to transmit the entire polynomial.

A PCS provides three core functions:

  • Commit(P(x)) -> C: The prover takes a polynomial \(P(x)\) and computes a small, binding commitment \(C\).
  • Open(C, z) -> (y, proof): The prover claims that the polynomial committed to in \(C\) evaluates to \(y\) at point \(z\). He generates a small proof to attest to this claim.
  • Verify(C, z, y, proof) -> 0/1: The verifier uses the commitment, the claimed evaluation, and the proof to check if the prover’s claim is valid.

For a PCS to be secure and useful, it must be binding: once a prover commits to a polynomial, he is bound to both its values and its maximum degree. This means he cannot later convince a verifier of a false evaluation, nor can they pretend a high-degree polynomial is a low-degree one. This property is what grounds the soundness of the entire SNARK. The commitment and proof must also be succinct, meaning they are significantly smaller than the polynomial itself.

The FRI Protocol: Proving Polynomials with Hashing

Many modern zkVMs rely on a PCS called FRI (Fast Reed-Solomon Interactive Oracle Proof of Proximity). It’s a foundational technology for STARKs because it’s transparent (it requires no trusted setup) and is built from a simple, well-understood ingredient: cryptographic hashing.

The core challenge FRI solves is this: how can a prover, who has committed to a set of evaluations, convince a verifier that those evaluations truly correspond to a low-degree polynomial? Doing this efficiently is the key to succinctness. FRI’s solution is elegant: it uses recursion.

The process works in a few steps:

  1. Commit: The prover starts with their degree-\(N\) polynomial \(P(x)\). To add redundancy and security, they evaluate it over a much larger domain of points. The domain size is determined by a blowup factor \(\rho^{-1}\) (e.g., a blowup factor of 8 means a domain of size \(8N\)). This special domain structure is critical, as it ensures that for every point \(x\) in the domain, its negation \(-x\) is also present, and that the domain of squared points \(x^2\) is exactly half the size. The prover then places all these evaluations into a Merkle tree and shares the root with the verifier. This root is the polynomial commitment \(C\).

  2. Fold: The prover then “folds” the polynomial \(P(x)\) into a new polynomial, \(P’(x)\), of roughly half the degree. This trick relies on splitting \(P(x)\) into its even and odd degree components: $$P(x) = P_{even}(x^2) + x \cdot P_{odd}(x^2)$$ \(P_{even}\) and \(P_{odd}\) are new polynomials, each with at most half the degree of \(P\). The verifier provides a random challenge scalar \(\alpha\), and the prover combines the two halves to form the next polynomial: \(P’(y) = P_{even}(y) + \alpha \cdot P_{odd}(y)\). The prover then commits to this new, smaller polynomial.

  3. Repeat: This folding process is repeated many times. In each round, the dimension of the polynomial (its degree bound plus one) and the size of its evaluation domain are halved. After about \(\log(N)\) rounds, the original high-dimension polynomial has been reduced to a tiny one (often a constant), which the prover can send directly to the verifier.

  4. Verify via Colinearity Checks: To ensure the prover didn’t cheat during the folding process, the verifier performs several random spot-checks. Instead of checking every value, the verifier uses a powerful geometric intuition: the colinearity check. For each round of folding, the verifier picks a random point \(x_i\) from that round’s domain and asks the prover to reveal the values of three points: \(P(x_i)\), \(P(-x_i)\), and the corresponding folded value \(P’(x_i^2)\). The verifier checks if these three values lie on the same line. If the prover was honest, they always will. To prevent certain attacks, the random indices chosen by the verifier are reused (and folded) across all rounds. The number of queries performed is determined by the target security level \(\lambda\) and the blowup factor \(\rho^{-1}\), typically \(\lambda / \log_2(\rho^{-1})\). If all checks pass, the verifier is convinced that the original commitment \(C\) corresponds to a set of values that is very “close” to the evaluations of a valid low-degree polynomial.

Using FRI for Point-Value Proofs

The FRI protocol proves that a commitment corresponds to a set of evaluations that is close to a low-degree polynomial. But how can we use this “proof of proximity” to prove a precise evaluation, like \(P(z) = y\)? This is done with another algebraic trick.

If \(P(z) = y\) is true, then the polynomial \(P(x) - y\) must have a root at \(x=z\). This means it is divisible by \((x-z)\). Therefore, the expression for the quotient polynomial: $$Q(x) = \frac{P(x) - y}{x-z}$$ evaluates to a polynomial of degree \(N-1\). If the original claim was false, then \(Q(x)\) would be a rational function, not a polynomial.

To prove an opening, the prover runs the FRI protocol on the evaluations of \(Q(x)\). The protocol convinces the verifier that these evaluations are close to those of an actual low-degree polynomial. Because Reed-Solomon codes have excellent distance properties, this closeness is sufficient; if the prover’s claim were false, the resulting evaluations for \(Q(x)\) would be far from any low-degree polynomial, and the FRI protocol would fail with high probability. Thus, a successful proof on the quotient is a robust confirmation of the original claim that \(P(z)=y\).

This recursive, hash-based strategy is powerful. While other schemes exist, such as KZG, which uses elliptic curve pairings to achieve constant-sized proofs at the cost of a trusted setup, the transparency and minimal assumptions of FRI have made it a dominant approach for building scalable and secure zkVMs.

This foundation is rapidly being built upon. Protocols like STIR optimize FRI by recursively improving the underlying code’s rate, which reduces the number of queries needed and results in significantly smaller proofs. A more fundamental evolution is WHIR, which integrates a lightweight sumcheck protocol directly into its folding recursion. This architectural shift enables native support for multilinear polynomials, leading to asymptotically fewer queries and exceptionally fast verification times, making hash-based proofs even more practical for the future of Ethereum.

Further Reading/Listening