FRI From Scratch

The problem FRI solves

In a STARK, the prover commits to large vectors of field elements that are supposed to be evaluations of low-degree polynomials. The verifier can't afford to download every value, interpolate the polynomial, and check its degree directly.

FRI — Fast Reed–Solomon Interactive Oracle Proof of Proximity — gives the verifier a cheaper way to test whether the committed evaluations are close to a polynomial below a required degree bound.

Why low degree matters

A STARK turns execution correctness into polynomial identities. Trace columns become polynomials, AIR constraints become algebraic relations, and the resulting polynomial claims come with degree bounds. If a prover could swap in arbitrary high-degree functions instead, the verifier's algebraic checks would no longer establish what they're supposed to.

Commit to the evaluation layer

Suppose f(X) has been evaluated over a multiplicative domain. The prover places those evaluations into a Merkle tree and sends only the root — fixing the entire layer before the verifier's next random challenge is even known.

The folding idea

Write the polynomial by splitting its even and odd powers:

The verifier samples a random field element β. The prover then defines the next polynomial by mixing the two halves:

If f has degree roughly d, its even and odd parts have degree roughly d/2. The new polynomial has a correspondingly smaller degree bound.

Folding directly from evaluations

For opposite domain points x and -x, the even and odd pieces can be recovered directly from their evaluations, without ever interpolating a polynomial:

So the next-layer evaluation becomes:

That's what makes folding practical to implement — the prover works directly with evaluation vectors, round after round, instead of reconstructing a new polynomial at every step.

Commit → challenge → fold

The order here is essential. The prover commits to the current layer first; only after that commitment is fixed does β get sampled. In a non-interactive STARK, Fiat–Shamir derives that challenge from the transcript instead of an actual verifier.

The process repeats, halving the layer in a binary FRI construction, until the remaining polynomial is small enough to check directly.

Why queries are still needed

Merkle roots only show that the prover fixed each layer — they don't show that one layer was honestly obtained by folding the previous one. Once every commitment is fixed, the verifier chooses random query positions to check that.

For each query, the prover opens the required values from one layer along with their Merkle authentication paths. The verifier checks those paths, recomputes the fold using the round's challenge, and compares the result against the opened value in the next layer.

Why random queries give confidence

If the original data is far from every low-degree polynomial, the prover generally can't make all the committed layers behave like honest folds at once. Random query paths exist to expose exactly that kind of inconsistency, and repeating the test across many independently sampled queries shrinks the chance that malformed data slips through undetected.

Why low-degree extension comes first

Before FRI runs, a STARK normally evaluates its polynomial over a domain larger than the original trace domain — the low-degree extension. Those extra evaluations introduce redundancy: a genuinely low-degree polynomial can't take arbitrary values across the enlarged domain, which is exactly the structure FRI needs to test against.

Where FRI fits in a STARK

By the time FRI runs, execution correctness has already been translated into algebraic constraints and polynomial claims. FRI supplies the low-degree-testing layer that makes those claims efficiently checkable.

FRI and KZG solve related problems differently