FRI (Fast Reed-Solomon Interactive Oracle Proof of Proximity)

FRI is the low-degree testing engine at the heart of STARK proof systems. It lets a prover convince a verifier that a committed function is “close to” a low-degree polynomial — without the verifier ever reading more than a handful of points. No elliptic curves, no trusted setup, no pairings. Just hashes and field arithmetic.

The Problem FRI Solves

In a STARK proof pipeline, a prover encodes a computation as a polynomial and commits to its evaluations over a large domain. The verifier needs to check that the committed function is actually a low-degree polynomial, not arbitrary garbage that happens to match at a few points.

This is the low-degree testing problem: given oracle access to a function f: D → F, determine whether f is (close to) a polynomial of degree less than d.

Why does this matter? The entire soundness argument of STARKs rests on one fact: two distinct low-degree polynomials can only agree on a small fraction of points. If the prover commits to something that isn’t low-degree, it cannot satisfy the polynomial constraints of the computation — except with negligible probability. FRI is how we enforce this.

Analogy: the book compression test. Imagine you claim a 1000-page book can be perfectly compressed to 10 pages (it’s “low-complexity”). I can’t read all 1000 pages, but I can spot-check: I pick random pages and ask you to reconstruct them from your compressed version. If the book really is compressible, you’ll always succeed. If you lied, you’ll fail on most pages. FRI works the same way — “low degree” plays the role of “compressible,” and random queries are the spot checks.

Background: Reed-Solomon Codes

FRI is built on Reed-Solomon (RS) codes, one of the most studied objects in coding theory.

A Reed-Solomon codeword is the set of evaluations of a polynomial of degree < d over a domain D of size n (where n >> d). The key property:

If deg(P) < d and |D| = n, then P is uniquely determined by
any d of its n evaluations. Two distinct polynomials of degree < d
agree on at most d-1 points out of n.

The rate of the code is ρ = d/n. In STARK systems, typical rates are ρ = 1/4 to 1/16 (called the “blowup factor” in STARK terminology — a blowup of 4× means ρ = 1/4).

FRI tests whether a given function f is within the Reed-Solomon code — i.e., whether f agrees with some polynomial of degree < d on all (or almost all) of the domain.

FRI Step by Step

FRI proceeds in rounds, each halving the degree bound and domain size. The protocol has two phases: a commit phase (prover builds layers) and a query phase (verifier spot-checks).

Commit Phase

Round 0:  f₀ over D₀  (degree < d, domain size n)
Round 1:  f₁ over D₁  (degree < d/2, domain size n/2)
Round 2:  f₂ over D₂  (degree < d/4, domain size n/4)
  ...
Round k:  fₖ is constant  (degree < 1)

At each round i:

Step 1 — Split. The current polynomial fᵢ(x) is decomposed into even and odd components:

fᵢ(x) = gᵢ(x²) + x · hᵢ(x²)

where gᵢ and hᵢ each have degree < deg(fᵢ)/2.

Step 2 — Receive challenge. The verifier sends a random field element αᵢ (in practice, derived via Fiat-Shamir from the Merkle commitment).

Step 3 — Fold. The prover computes:

fᵢ₊₁(y) = gᵢ(y) + αᵢ · hᵢ(y)

This is a random linear combination of gᵢ and hᵢ. If both have degree < d/2, then fᵢ₊₁ also has degree < d/2. Crucially, the domain also halves: D₁ = {x² : x ∈ D₀}.

Step 4 — Commit. The prover evaluates fᵢ₊₁ over the new domain Dᵢ₊₁ and commits via a Merkle tree.

Step 5 — Repeat until the polynomial is constant (degree 0). The prover sends this constant value directly.

ASCII Diagram: FRI Folding

Layer 0:  [f₀(x) over D₀, degree < d]
            │
            │  α₀ (random challenge)
            ▼
Layer 1:  [f₁(y) over D₁, degree < d/2]
            │
            │  α₁
            ▼
Layer 2:  [f₂(z) over D₂, degree < d/4]
            │
            │  α₂
            ▼
          ...
            │
            ▼
Layer k:  [fₖ = constant]        k = log₂(d) rounds

Domain:   |D₀| = n → |D₁| = n/2 → ... → |Dₖ| = n/2ᵏ
Degree:   d → d/2 → d/4 → ... → 1

Query Phase

After the commit phase, the verifier performs q independent queries (typically 30-80). For each query:

Pick a random index s₀ in D₀.
Request f₀(s₀) and f₀(-s₀) from the Layer 0 Merkle tree. (These are “sibling” evaluations — they share the same x² value.)

Compute the expected value of f₁(s₀²) using the folding formula:

f₁(s₀²) = (f₀(s₀) + f₀(-s₀))/2 + α₀ · (f₀(s₀) - f₀(-s₀))/(2·s₀)

Check this matches the committed value in Layer 1’s Merkle tree.
Continue: use s₁ = s₀² as the index into Layer 1, request f₁(s₁) and f₁(-s₁), compute expected f₂(s₁²), and so on.
At the final layer, check consistency with the claimed constant.

If the original function is not close to a low-degree polynomial, some layer will be inconsistent, and the spot-check will catch it with high probability.

Why FRI is Transparent (No Trusted Setup)

FRI’s only cryptographic ingredient is a collision-resistant hash function (for Merkle tree commitments). Compare this with SNARKs:

	SNARKs (Groth16, etc.)	FRI / STARKs
Setup	Trusted ceremony generating toxic waste	None — fully transparent
Crypto assumptions	Pairing-friendly elliptic curves, knowledge-of-exponent	Collision-resistant hashing
Quantum resistance	Broken by Shor’s algorithm	Hash functions remain secure

The random challenges in FRI come from the Fiat-Shamir heuristic: hash the prover’s commitment to derive the next challenge. No secret trapdoor is ever created. Anyone can verify a FRI proof with nothing but the hash function.

This transparency is a core philosophical advantage: there’s no “toxic waste” that, if leaked, would let someone forge proofs.

Complexity Analysis

Prover Complexity

The prover’s main work is evaluating polynomials and building Merkle trees at each layer.

Layer 0: n evaluations, O(n) Merkle leaves
Layer 1: n/2 evaluations
Layer 2: n/4 evaluations
...
Total: n + n/2 + n/4 + ... = O(n)

With FFT-based evaluation (the domain is chosen to support NTT — Number Theoretic Transform), each layer costs O(n/2ⁱ · log(n/2ⁱ)). Total prover time:

Prover time: O(n · log(n))     (dominated by Layer 0)
Prover space: O(n)

Verifier Complexity

The verifier reads 2 Merkle leaves per layer per query, and verifies O(log n) Merkle paths per leaf.

Per query: O(log²(n))     — log(n) layers × log(n) Merkle path per layer
Total:     O(q · log²(n))

With typical parameters (n = 2²⁰, q = 50), the verifier touches roughly 50 × 20 × 20 = 20,000 hash operations — trivial even on-chain.

Proof Size

Each query requires 2 Merkle authentication paths per layer:

Proof size ≈ q · log(d) · log(n) · hash_size
           ≈ 50 · 20 · 20 · 32 bytes
           ≈ 640 KB (naive)

In practice, batching and Merkle path sharing reduce this to ~50-200 KB. This is the main drawback vs SNARKs (~200 bytes), though recursion and STARK-to-SNARK wrapping can compress it further.

The Role of the Blowup Factor

The blowup factor (also called expansion factor) is ρ⁻¹ = n/d. It controls the security-efficiency tradeoff:

Higher blowup (e.g., 16×):
  ✓ Fewer queries needed for same security
  ✓ Better soundness per query
  ✗ Larger initial commitment (more evaluations)
  ✗ More prover work

Lower blowup (e.g., 4×):
  ✓ Smaller commitments
  ✓ Less prover work
  ✗ More queries needed
  ✗ Larger proof size

The soundness error per query is roughly (1 - (1-ρ)) = ρ. With blowup 4× (ρ = 1/4), each query catches a cheater with probability ~3/4, so ~80 queries give 2⁻¹²⁸ security.

Real-World Parameters: Starknet’s Choices

Starknet (via StarkWare’s Stone prover and the newer Stwo prover) uses these typical parameters:

Parameter	Value	Notes
Field	Mersenne-31 (M31 = 2³¹ - 1)	Stwo uses M31; Stone uses a 252-bit field
Blowup factor	4× or 8×	Stwo typically uses 4×
Number of FRI queries	~50-80	Targeting ~100-bit security
Hash function	Poseidon / Blake2s / Keccak	Poseidon for recursive proofs; Blake2s/Keccak for L1 verification
FRI layers	~20	For trace lengths of ~2²⁰
Final polynomial degree	0 or small constant	Sent directly

Stwo (STARKWare Two) is the latest-generation prover. It works over the Circle group on M31 (a “circle STARK” variant), which allows efficient NTT-like operations on the small 31-bit field. This dramatically improves prover performance compared to Stone’s larger field.

Variants: DEEP-FRI

Standard FRI proves low-degree proximity but doesn’t directly link the polynomial to a specific computation. DEEP-FRI (Domain Extension for Eliminating Pretenders) addresses this.

The idea: the verifier picks a random “out-of-domain” point z (outside the evaluation domain D) and asks the prover for f(z). The prover must provide a consistent answer. Then the FRI protocol runs on the quotient:

g(x) = (f(x) - f(z)) / (x - z)

If f truly has degree < d, then g has degree < d-1. If the prover lied about f(z), the quotient won’t be a polynomial at all, and FRI will reject.

DEEP-FRI is critical in practice because it binds the FRI proof to specific claimed evaluations, which is how the verifier checks that constraint polynomials vanish where they should.

Standard FRI:  "f is close to a polynomial of degree < d"
DEEP-FRI:      "f is close to a polynomial of degree < d,
                AND that polynomial evaluates to v at point z"

FRI in the Full STARK Pipeline

FRI doesn’t exist in isolation. Here’s where it fits:

┌─────────────────────────────────────────────────┐
│ 1. COMPUTATION                                   │
│    Program → Execution Trace (table of values)   │
├─────────────────────────────────────────────────┤
│ 2. AIR (Algebraic Intermediate Representation)   │
│    Trace → Polynomial constraints                │
├─────────────────────────────────────────────────┤
│ 3. COMPOSITION                                   │
│    Combine constraints into composition poly     │
│    C(x) = Σ αᵢ · Cᵢ(x) / Zᵢ(x)                │
├─────────────────────────────────────────────────┤
│ 4. LOW-DEGREE TESTING (FRI)              ← here │
│    Prove C(x) has the expected degree            │
├─────────────────────────────────────────────────┤
│ 5. PROOF                                         │
│    Merkle commitments + FRI layers + queries     │
└─────────────────────────────────────────────────┘

The prover:

Executes the program and records the execution trace.
Encodes constraints as an AIR (see Execution Trace & AIR).
Combines all constraints into a single composition polynomial using random linear combination.
Runs FRI on the composition polynomial to prove it has low degree.
Packages everything into the final proof.

The verifier:

Replays the Fiat-Shamir challenges.
Spot-checks the composition polynomial via DEEP-FRI queries.
Verifies FRI layer consistency.
Accepts if all checks pass.

Intuition: Why Does Folding Work?

The folding step is the heart of FRI, and it deserves one more angle of intuition.

Any polynomial P(x) of degree < d can be uniquely written as:

P(x) = E(x²) + x · O(x²)

where E has the even-degree coefficients and O has the odd-degree coefficients of P. Both E and O have degree < d/2.

When we fold with random α:

P'(y) = E(y) + α · O(y)

This is a random linear combination. If P truly had degree < d, then P’ has degree < d/2. But if P had degree ≥ d, then E or O would have degree ≥ d/2, and P’ would also (with overwhelming probability over the random choice of α).

So each round acts as a “degree filter”: honest polynomials pass cleanly, while cheating polynomials get caught. After log₂(d) rounds, an honest polynomial reduces to a constant, while a cheating one would have been detected at some layer.

Open Questions and Active Research

Circle FRI: Stwo’s approach using the circle group over M31, avoiding the need for large multiplicative subgroups. This is an active area with ongoing optimization.
FRI for small fields: Traditional FRI needs a large enough field for soundness. Techniques like field extension and the Binius approach (binary fields) are pushing boundaries.
Proof compression: STARK proofs (driven by FRI) are still ~100× larger than SNARKs. Recursive proving (a STARK that verifies a STARK) and STARK-to-SNARK wrapping (verify a STARK inside a SNARK for on-chain compression) are practical solutions deployed today.
Batch FRI: Proving multiple polynomials are low-degree simultaneously with a single FRI invocation, reducing proof size.

References

Ben-Sasson, E., Bentov, I., Horesh, Y., & Riabzev, M. (2018). “Fast Reed-Solomon Interactive Oracle Proofs of Proximity.” ICALP 2018. ECCC TR17-134
Ben-Sasson, E., et al. (2018). “Scalable, transparent, and post-quantum secure computational integrity.” CRYPTO 2019. (The STARK paper.)
Buterin, V. (2017). “STARKs, Part II: Thank Goodness It’s FRI-day.” Blog post
Haböck, U. (2022). “A summary on the FRI low degree test.” IACR ePrint 2022/1216
StarkWare. “ethSTARK Documentation.” GitHub
Polygon Labs. “Plonky2 and FRI.” Technical docs

See also: STARKs vs SNARKs, Execution Trace & AIR, Commitment Schemes, Merkle Trees

FRI Protocol