FRI protocol is low-degree testing.
Let’s say the following function as codeword.
$$ f: D \rightarrow \mathbb{F} $$
We want to show the codeword is close to Reed-Solomon code defined as following:
$$ RS_k[F, D] = \{p(x)|_{x \in D}:p(X) \in F[X], \;deg\; p(X) \le k-1\} $$
We say $\rho = k/|D|$ as rate, or $1/\rho$ as a blowup factor.
FRI protocol has 2 phases. Commit phase, and Query phase.
Let’s say the initial domain of FRI as $L_0$, and want to show codeword $f: L_0 \rightarrow \mathbb{F}$ is close to some polynomial $p(X)$ of degree at most $k-1.$
$|L_0| = 2^n, k = 2^d$
Also, denote Merkle tree commitment of $f: L \rightarrow \mathbb{F}$ as $[f]$ .
Honest prover will proceed to prove that the interpolation of codeword $f$, which we call $f(X)$ has degree at most $k-1$ .
In commit phase, prover splits the domain size and the polynomial into half in each layer, and sends commitments of the polynomials in each layer.