FRI: Folding Polynomials and Catching Cheaters

Introduction

FRI (Fast Reed-Solomon Interactive Oracle Proof) is a polynomial commitment scheme. Let's break that down:

• Polynomial: If you don't know what this is, this article might not be for you… sorry 😕
• Commitment Scheme: You choose a value and commit to it (e.g., with a hash function). Once committed, you can't change it. Later, you reveal it to prove what you committed to. However, in FRI, you don’t fully reveal it, that’s the magic!
• Polynomial Commitment Scheme: You pick a polynomial and commit to it.

FRI enables a prover to commit to a polynomial and convince a verifier that the polynomial satisfies certain properties, mainly that it has a low degree.

Why Do We Need FRI?

There are several polynomial commitment schemes. What makes FRI special?

• No Trusted Setup ✅

  Unlike KZG commitments, which require a structured reference string (SRS), FRI only needs Merkle commitments.

• Post-Quantum Security 🔒

  Since it avoids elliptic curve pairings, FRI-based proofs are more resistant to quantum attacks.

Where Is FRI Used?

1. STARKs

FRI is used in STARKs (Scalable Transparent Arguments of Knowledge) to commit to the execution trace of a computation.

1. Data Availability & Danksharding

FRI is also used in data availability sampling. Instead of sending an entire data blob to a client, a validator commits to the data using FRI, and clients can verify data integrity without downloading everything.

Process:

• The original data (e.g., rollup transactions) is structured into a matrix.
• Each row and column undergoes Reed-Solomon encoding, forming a low-degree polynomial for redundancy.
• A commitment is made by evaluating the polynomial on a large domain and constructing a Merkle tree.