FRI Protocol

FRI, short for Fast Reed-Solomon Interactive Oracle Proof of Proximity, is a protocol that proves a committed set of values is close to a low-degree polynomial, that is, a valid Reed-Solomon codeword. Introduced by Ben-Sasson and colleagues, it is the polynomial-commitment engine inside STARK proof systems and the leading transparent alternative to pairing-based commitments.

How folding works

FRI works by repeated folding. The prover commits to evaluations of a polynomial, then combines pairs of points with a verifier-supplied random challenge to produce a new polynomial of half the degree, committing to it as well. After a logarithmic number of folding rounds the polynomial shrinks to a constant, which the verifier can check directly. The verifier then spot-checks a handful of random positions for consistency across the rounds, gaining high confidence that the original commitment really was low-degree.

Why it matters

FRI needs no trusted setup; its randomness comes only from public hash functions, making it transparent. Because it relies on collision-resistant hashing rather than elliptic curves, it is also believed to be post-quantum secure. The tradeoff is proof size: FRI proofs are larger than pairing-based ones, though prover time is strictly linear and verifier time logarithmic.

FRI is the transparent counterpart to the KZG polynomial commitment within the wider family of the polynomial commitment scheme.