FRI Protocol

The core primitive of FRI is proving that a committed function corresponds to a polynomial of a specific low degree. The protocol uses a split-and-fold technique: in each round, the prover combines evaluations from pairs of points using a random challenge, reducing the polynomial's degree by half. After a logarithmic number of rounds, the polynomial is reduced to a constant, which the verifier checks directly. This interactive oracle proof is made non-interactive via the Fiat-Shamir heuristic, using a Merkle tree as the commitment scheme.

FRI achieves polylogarithmic proof size relative to the computation being verified. Key efficiency characteristics:

• Prover complexity: O(N log N) field operations, dominated by FFTs
• Verifier complexity: O(log² N) operations, making verification extremely fast
• Proof size: O(log² N) hash values, typically tens of kilobytes for real-world computations
• Round complexity: log₂(N) rounds of interaction, each halving the instance size This logarithmic scaling is what makes STARKs practical for proving large computations on resource-constrained verifiers.

FRI proves that a committed function is δ-close to a low-degree polynomial in Reed-Solomon code space. The proximity parameter δ determines the protocol's soundness error:

• A function that is δ-far from all low-degree polynomials will be rejected with high probability
• The soundness error is bounded by a function of δ, the number of queries, and the field size
• Increasing the number of query repetitions reduces soundness error exponentially
• Typical configurations use 30-80 queries to achieve 80-128 bits of security This relaxed notion of correctness (proximity rather than exact equality) is sufficient for all STARK applications.

Unlike pairing-based proof systems, FRI requires no trusted setup ceremony. The protocol relies solely on:

• Collision-resistant hash functions (typically SHA-256 or BLAKE3)
• Reed-Solomon codes over finite fields
• Merkle trees for polynomial commitments This transparency eliminates the toxic waste problem inherent in structured reference strings. Additionally, the reliance on symmetric cryptography rather than bilinear pairings or discrete log assumptions provides conjectured post-quantum security, making FRI-based STARKs resistant to attacks by large-scale quantum computers.

Standard FRI only queries points within the evaluation domain. DEEP-FRI (Domain Extension for Eliminating Pretenders) adds a crucial security enhancement:

• The verifier samples a random point outside the original evaluation domain
• The prover must open the polynomial at this out-of-domain point
• This prevents a class of algebraic attacks where a malicious prover constructs a function that passes in-domain tests but is not actually close to a low-degree polynomial
• Combined with quotienting (proving the polynomial satisfies specific constraints at the random point), DEEP-FRI achieves tighter soundness bounds Most production STARK implementations, including StarkWare's Stone prover, use DEEP-FRI.

FRI supports efficient batch verification of multiple polynomial proximity claims:

• Multiple polynomials can be combined into a single random linear combination
• A single FRI proof then attests to the low-degree property of all polynomials simultaneously
• This batching reduces amortized proof size and verification cost Furthermore, FRI proofs can be recursively composed: a STARK proof attesting to the validity of another STARK proof. This recursion enables:
• Proof compression: Multiple proofs collapsed into one constant-size proof
• Incremental verifiable computation: Long computations broken into steps, each proven incrementally
• L3 scaling solutions: Recursive proof aggregation for rollup ecosystems