Skip to main content

About the FRI Protocol

The FRI (Fast, Reed-Solomon Interactive Oracle Proof of Proximity) protocol is the final component of RISC Zero's argument of computational integrity.

RISC Zero's STARK converts an assertion of computational integrity to an assertion about polynomial division. In the language of Reed-Solomon codes, this assertion about polynomial division can be re-framed as an assertion about block proximity. The FRI protocol finishes the argument by proving the assertion about block proximity.

Basic Function​

Given a Merkle root, the FRI protocol is a recursive technique for proving that the associated Merkle leaves are associated with a low-degree polynomial.

Background​

Inside the Algorithm​

The FRI protocol consists of a number of commit rounds followed by a number of query rounds.

  • In each commit round, the Prover commits a new (smaller) Merkle tree corresponding to evaluations of a lower-degree polynomial; the round-by-round commitments depend on a random mixing parameter that allows for an audit-trail in the upcoming query round.
    • In each commit round, the degree of the FRI polynomial and the size of the associated Merkle tree is reduced by a factor of 16, in the RISC Zero implementation.
    • RISC Zero runs commit rounds until the degree of the FRI polynomial is less than or equal to 255.
  • In each query round, the Prover reveals Merkle branches (and leaves) from each of the FRI commitments. The branches revealed in the query rounds are selected using the Fiat-Shamir Heuristic.
    • Varying the number of query rounds offers a tradeoff between security level and computational efficiency.
  • RISC Zero's implementation for FRI can be found here

About DEEP-FRI​

Shortly after the FRI protocol was released, an alternative protocol called DEEP-FRI was released. Although DEEP-FRI was initially thought to have improved soundness relative to FRI, the Proximity Gaps for Reed-Solomon Codes paper shows that the original FRI protocol offers the same soundness results as DEEP-FRI at less computational complexity. The RISC Zero ZKP system uses the original FRI protocol.

Suggested Reading​

Academic Papers​

Explanatory References​