Start with the actual problem
FRI is easier to understand if we first ask what a STARK prover needs to prove.
Suppose a prover claims that some huge computation is valid. After converting the computation into algebraic constraints, the prover eventually needs to convince the verifier about properties of one or more polynomials.
The verifier cannot simply download every evaluation and reconstruct the polynomial. There may be millions of values.
FRI provides a scalable way to test this claim through:
The prover commits to large evaluation vectors using Merkle trees.
The verifier checks only a small number of positions.
The prover repeatedly transforms a polynomial into a lower-degree polynomial.
At the end, the verifier has evidence that the original function was close to the claimed low-degree structure.
What does FRI stand for?
The full name is Fast Reed–Solomon Interactive Oracle of Proximity.
Each word tells us something important.
The protocol is designed to handle very large evaluation domains efficiently.
The underlying object is a polynomial evaluation code: values generated by evaluating a low-degree polynomial over a domain.
The verifier accesses selected locations of a committed function rather than receiving the entire function.
The goal is not merely to ask whether a function is exactly a codeword, but whether it is sufficiently close to one.
First principle: what is a polynomial?
A polynomial over a field can be written as:
The largest exponent with a non-zero coefficient is the degree.
For example:
FRI is fundamentally interested in whether a function behaves like a polynomial whose degree is below a specified bound.
The polynomial lives over a finite field
STARK systems do not normally evaluate polynomials over the real numbers.
They work over a finite field.
For example, over the field modulo 17:
Therefore a polynomial such as:
can be evaluated at field elements using finite-field arithmetic.
From coefficients to evaluations
A polynomial can be represented by its coefficients:
Or we can evaluate it at a collection of points:
FRI works primarily with this evaluation representation.
This is important because the prover can commit to a large vector of evaluations without revealing the entire polynomial's coefficients.
What is an evaluation domain?
An evaluation domain is a chosen set of field elements where the polynomial will be evaluated.
In STARK systems, the domain is often chosen with strong algebraic structure, commonly using a multiplicative subgroup or a related structured domain.
A structured domain makes polynomial operations and FFT-style transformations efficient.
Example
Suppose:
where ω is an element with the required multiplicative order.
Reed–Solomon code: the key connection
A Reed–Solomon code can be understood as taking a low-degree polynomial and encoding it by evaluating it at many points.
So a low-degree polynomial corresponds to a highly structured evaluation vector.
FRI exploits this structure.
What is an oracle?
An oracle is an abstraction for a function that the verifier can query at selected positions.
Imagine the prover has a huge vector:
The verifier does not receive the whole vector.
Instead, it asks:
FRI is an oracle proof because the verifier reasons about a huge function through a relatively small number of queries.
What does “proximity” mean?
This is one of the most important words in FRI.
Suppose the verifier expects a function that comes from a polynomial of degree at most d.
A function may not be exactly such a polynomial, but it might differ at only a small fraction of its positions.
FRI is designed to distinguish between:
The oracle differs from some valid low-degree polynomial only on a small fraction of the domain.
The oracle is not close to any polynomial within the claimed degree bound.
Why does the prover need to commit first?
If the prover could wait until seeing the verifier's queries before choosing values, it could answer each query dishonestly in a coordinated way.
Therefore the prover first commits to the evaluation vector.
The Merkle root acts as a compact commitment to the complete vector.
Merkle commitments in FRI
Suppose the prover has evaluations:
Hash the leaves:
Then repeatedly hash pairs:
Later, the prover gives a queried value together with its authentication path.
The verifier can reconstruct the root and check that the value was part of the committed vector.
The central idea: folding
FRI repeatedly reduces the size and degree of the polynomial problem.
The easiest intuition is to split evaluations into two halves:
and combine them using a random verifier challenge.
A common conceptual form is:
where α is a random challenge derived from the transcript.
The exact implementation can be expressed in several equivalent forms depending on the domain and indexing convention.
Why does pairing x and −x help?
Write a polynomial as its even and odd parts:
Then:
This decomposition is the algebraic reason folding can reduce the degree problem.
FRI uses a random linear combination of these pieces so that a cheating function is unlikely to continue looking low-degree after repeated folds.
What is the random challenge α?
At each folding round, the verifier contributes a random field element.
These challenges prevent the prover from preparing a malicious function specifically for a known folding rule.
In a non-interactive STARK, the challenges are typically derived using Fiat–Shamir:
FRI rounds
A simplified FRI protocol repeatedly performs:
After each fold, the domain becomes smaller and the degree bound decreases.
Conceptually:
The precise degree relationship depends on the protocol variant and how the folding is defined.
A tiny conceptual example
Suppose the prover claims a polynomial has degree at most 3:
Evaluate it over a domain of eight points:
FRI can fold the eight evaluations into four:
Then:
The point is not that “one value proves the polynomial.” The point is that repeated algebraic reductions make the low-degree claim progressively easier to test, while random challenges preserve soundness.
What happens at the end?
Eventually the polynomial is reduced to a very small object.
The verifier can directly check the final representation against the expected low-degree structure.
The prover cannot simply choose arbitrary final values because every folding step is tied to previous committed evaluations and transcript challenges.
Why are random queries necessary?
The verifier cannot inspect every position in every FRI layer.
Instead, it samples a small number of random positions.
For each query, the verifier checks the values needed to reconstruct the corresponding fold relation.
If the prover's function is far from low degree, random sampling gives the verifier a significant chance of detecting inconsistency.
What does a query look like?
Suppose the verifier chooses an index i.
The prover must provide enough information to verify the fold relationship involving the corresponding pair of locations.
Repeated queries make it increasingly unlikely that a significantly corrupted oracle passes all checks.
FRI and Fiat–Shamir
The original FRI description is interactive: the verifier sends random challenges.
A STARK prover generally needs a non-interactive proof.
Fiat–Shamir derives each challenge from the transcript:
This creates a deterministic transcript that both prover and verifier can reproduce.
Careful transcript design and domain separation are essential for security.
Why the order matters
The protocol must preserve the causal order:
not:
If the prover can adapt its committed function after learning the challenge, the soundness argument can fail.
How FRI gets soundness
Suppose the prover's oracle is far from every polynomial of the claimed degree.
The prover commits to this oracle before seeing the random challenges.
FRI's folding transformation and random challenges make it difficult for a far-from-low-degree function to remain consistent through every round.
The formal soundness analysis is more involved and depends on the field, degree bound, rate, number of rounds, and number of queries.
Soundness error intuition
If a cheating oracle has only a small chance of passing one random test, repeating independent or appropriately structured tests reduces the overall cheating probability.
The exact bound is protocol-specific, so this should be treated as intuition rather than a universal FRI formula.
What is the code rate?
The evaluation domain is usually larger than the polynomial's degree bound.
The ratio between the amount of information represented and the size of the encoded domain is related to the code rate.
In simple intuition:
FRI relies on this redundancy to test whether the oracle is consistent with a low-degree polynomial.
FRI and low-degree extension
In STARKs, a polynomial is often first evaluated over a larger domain than the original execution trace domain.
This is called a low-degree extension (LDE).
The enlarged domain provides redundancy that is useful for proximity testing and soundness.
Where does the composition polynomial fit?
In a STARK, the prover does not usually ask FRI to prove every individual AIR constraint independently.
Constraint violations can be combined into a composition polynomial or related algebraic object.
FRI then helps prove that the relevant composition object has the required low-degree structure.
FRI is not automatically zero knowledge
This distinction is important.
FRI is fundamentally a low-degree testing / proximity protocol. Zero knowledge is a separate security property.
A complete zero-knowledge STARK adds appropriate masking, randomization, and protocol techniques so that the proof does not reveal the private execution data that should remain hidden.
FRI inside a STARK
A simplified STARK pipeline is:
FRI is therefore not the entire STARK. It is one of the central components used to establish low-degree proximity.
Rust: the core folding idea
Educational FRI-style folding
// Educational illustration only.
// Real FRI implementations must use field elements,
// a carefully chosen domain, transcript challenges,
// commitments, and exact protocol indexing.
fn fold(
f_x: FieldElement,
f_minus_x: FieldElement,
alpha: FieldElement,
) -> FieldElement {
// Conceptual form:
// g(x²) = (f(x) + alpha * f(-x)) / 2
let two_inv = FieldElement::from(2).inverse();
(f_x + alpha * f_minus_x) * two_inv
}
// A real prover would:
// 1. evaluate a polynomial over a domain
// 2. commit to the evaluations
// 3. derive alpha from the transcript
// 4. fold the evaluations
// 5. commit to the next layer
// 6. repeat until the final layerThe important part is not the syntax. The important part is the repeated transformation:
What a real FRI implementation must handle
Every value must be a valid element of the selected finite field.
Paired points must be mapped consistently across every folding round.
Challenges must be derived in the exact order expected by prover and verifier.
Every FRI layer must be committed before its challenge is known.
The verifier must request all sibling values needed to validate folding relationships.
The final reduced object must be checked against the claimed degree bound.
FRI vs FFT
These are easy to confuse because both appear together in STARK implementations.
Efficiently moves between polynomial coefficients and evaluations over a structured domain.
Provides a protocol for testing that an evaluation oracle is close to a low-degree polynomial.
A STARK prover may use FFTs to construct polynomial evaluations and FRI to prove the resulting low-degree claims.
FRI vs Merkle trees
A Merkle tree by itself does not prove that a vector comes from a low-degree polynomial.
They work together:
FRI vs KZG
Both can be used as polynomial-proof machinery, but their cryptographic approaches are very different.
| Property | FRI | KZG |
|---|---|---|
| Core idea | Low-degree testing through recursive folding | Algebraic polynomial commitment with evaluation proofs |
| Commitment style | Hash / Merkle commitments | Elliptic-curve group commitment |
| Pairings | Not required by core FRI | Used for common KZG verification |
| Trusted setup | Transparent | Traditional KZG requires an SRS generated from secret setup randomness |
| Proof size | Generally larger | Very compact evaluation proofs |
| Typical STARK role | Core low-degree testing component | Not the usual commitment scheme |
Why does folding actually help?
Suppose the initial domain contains N evaluations.
After one fold:
After another:
After r rounds:
This logarithmic number of rounds is what makes recursive reduction practical for very large domains.
The simplest mental model
The prover cannot freely change old layers because every layer was committed before the corresponding challenge was derived.
Interview-level questions
Fast Reed–Solomon Interactive Oracle of Proximity.
It provides a scalable protocol for testing whether an oracle is close to the evaluation of a low-degree polynomial.
The verifier tests whether the function is close to a valid low-degree Reed–Solomon codeword, rather than requiring direct reconstruction of the whole polynomial.
Folding combines evaluations at related domain points using a random challenge to produce a new function on a smaller domain with a lower effective degree bound.
They commit to large evaluation vectors while allowing the verifier to authenticate only the values needed for random queries.
Otherwise the prover could adapt the evaluation vector after learning which folding or query choices will be tested.
It derives verifier challenges from the transcript, allowing an interactive-style FRI protocol to be represented as a non-interactive proof.
No. FRI is a central low-degree testing component used by common STARK constructions, but a STARK includes the complete proving system around it.
FRI itself is primarily a low-degree proximity protocol. A zero-knowledge STARK needs additional mechanisms to hide witness-dependent information.
A zkVM produces huge algebraic traces and polynomial representations. FRI lets the verifier test the required low-degree claims without downloading every evaluation.
The whole idea in one map
If you remember only one sentence, remember this: FRI lets a verifier test, using commitments, random queries, and recursive folding, whether a huge evaluation oracle is consistent with a low-degree polynomial without downloading the entire polynomial.