Review of FRI

As we've already mentioned, our commitment scheme uses Reed–Solomon codes, and particular binary ones. Here, we will begin to sketch why our use of codes pays off. The crucial underlying mathematical tool turns out to be FRI—short for fast Reed–Solomon interactive oracle proof of proximity—a key protocol developed by Ben-Sasson, Bentov, Horesh and Riabzev [BBHR18].

FRI is an extremely complicated topic, and we will simply not be able to cover all of its ins and outs here. In short, FRI is a proximity test—an interactive protocol, between a prover and a verifier—pertaining to a committed word. The verifier's goal is to determine whether the word is close to a codeword—that is, whether it differs from some (i.e., any) codeword at just a few positions, or whether it's instead far from them all. In the process, the verifier would like to query as few positions of the committed word as possible. FRI resides firmly in the IOP model. A key aspect of the protocol is interaction: during the protocol, the prover and verifier interact over the course of a logarithmic number of rounds (in the length of the initial committed word). In each round, the verifier samples and sends a random challenge, and the prover commits a further word to the string oracle. In the end, the verifier runs a testing procedure known as querying, during which it reads the prover's various committed words at various points.

We conduct our overview of FRI in the binary setting—the setting, in fact, in which most of that protocol's original treatment was carried out. On the other hand, we moreover specialize binary-field FRI itself in a key way, following [DP24, § 3.1]. Our specialization is designed to make FRI compatible with the additive NTT.

Some Mathematical Objects

During our description of the additive NTT, we worked with a binary field $\mathcal{T}_\tau$, a size parameters $\ell$, and a rate parameter $\mathcal{R}$. Our encoding algorithm, on input a list $(a_0, \ldots , a_{2^{\ell - 1}})$, gave us a further list $(b_0, \ldots , b_{2^{\ell + \mathcal{R}} - 1})$, which arose as the evaluations of a certain polynomial $P(X)$ of degree less than $2^\ell$ on $S$; here, $S \subset \mathcal{T}_\tau$ is a domain of dimension $\ell + \mathcal{R}$ over $\mathbb{F}_2$. In fact, we chose $S$ to be an $\mathbb{F}_2$-vector subspace of $\mathcal{T}_\tau$ (specifically, the span of the basis prefix $\left< \beta_0, \ldots , \beta_{\ell + \mathcal{R} - 1} \right>$). Our commitment procedure ultimately wrapped up by sending $(b_0, \ldots , b_{2^{\ell + \mathcal{R}}})$ to the string oracle.

In FRI, the domain $S^{(0)} \coloneqq S$ becomes just the first in a sequence of domains $S^{(0)}, S^{(1)}, \ldots , S^{(\ell)}$. Each of these shrinks by exactly one dimension; in particular, $S^{(1)}$ is $\ell + \mathcal{R} - 1$-dimensional, and $S^{(\ell)}$ is just $\mathcal{R}$-dimensional as an $\mathbb{F}_2$-vector subspace of $\mathcal{T}_\tau$. In fact, we link up these domains using a series of $\mathbb{F}_2$-linear maps:

Here, each map $q^{(i)} : S^{(i)} \to S^{(i + 1)}$ is linear, with a one-dimensional kernel. In particular, $q^{(i)}$ vanishes on a 1-dimensional subspace of $S^{(i)}$; moreover, the image of its restriction to $S^{(i)}$ is exactly $S^{(i + 1)}$, a subspace whose dimension is exactly one less than $S^{(i)}$'s.

Finally, the committed word $(b_0, \ldots , b_{2^{\ell + \mathcal{R}} - 1})$, which we view as a function $f^{(0)} : S^{(0)} \to \mathcal{T}_\tau$, becomes just the first in a series of smaller and smaller words $f^{(1)}, \ldots , f^{(\ell - 1)}$ committed to by the prover. Each committed word $f^{(i)}$ is a function on $S^{(i)}$. To describe these further words, we need to describe the structure of the FRI protocol.

Rough Idea of FRI

The FRI protocol proceeds over $\ell$ rounds. We start with the prover's initial committed word $f^{(0)} : S^{(0)} \to \mathcal{T}_\tau$. For each round index $i \in \{0, \ldots , \ell - 1\}$,

• The verifier samples a random scalar $r_i \gets \mathcal{T}_\tau$, and sends it to the prover.
• The prover, using its existing oracle $f^{(i)} : S^{(i)} \to \mathcal{T}_\tau$ and $r_i$, carries out a procedure called "FRI folding", which depends on both $f^{(i)}$ and $r_i$. Using this procedure, the prover comes up with a further word $f^{(i + 1)} : S^{(i + 1)} \to \mathcal{T}_\tau$. It commits this word to the oracle.

The exception is the very final round, the $\ell$th. In this round, instead of committing to $f^{(\ell)}$, the prover just sends a single constant to the verifier. Finally, the verifier kicks off its querying phase. At the end of this phase, the verifier either accepts or rejects.

The key idea necessary to understand FRI is closeness to the Reed–Solomon code. If the prover is honest, then, for each $i \in \{0, \ldots , \ell - 1\}$, the committed word $f^{(i)}$ will be a codeword in the Reed–Solomon code $\mathsf{RS}_{S^{(i)}, \mathcal{T}_\tau}[2^{\ell - i}, 2^{\ell + \mathcal{R} - i}]$. That is, it will arise as the evaluations of some polynomial of degree less than $2^{\ell - i}$ on the size-$2^{\ell + \mathcal{R} - i}$ domain $S^{(\ell - i)}$.

On the other hand, if the prover is dishonest, then its oracles might not be codewords; they might even be far from the code, in the sense that they don't even reside near any codeword, forget about equalling one. Here, the notion "far from the code" is fairly tricky. Roughly, we can say that $f^{(0)}$ is far from $C$ if $d(f^{(0)}, C) \geq \frac{d}{2}$, in the sense that, for each codeword $\overline{f}{}^{(0)} \in C$, $d(f^{(0)}, \overline{f}{}^{(0)}) \geq \frac{d}{2}$ holds. Here, $d = n - k + 1 = 2^{\ell + \mathcal{R}} - 2^\ell + 1$ is the distance of the Reed–Solomon code $\mathsf{RS}_{S, \mathcal{T}_\tau}[2^\ell, 2^{\ell + \mathcal{R}}]$. The right-hand side $\frac{d}{2}$ represents $C$'s unique decoding radius. If $f^{(0)}$'s distance from $C$ is less than $\frac{d}{2}$, then there exists a codeword $\overline{f}{}^{(0)} \in C$ such that $d(f^{(0)}, \overline{f}{}^{(0)}) < \frac{d}{2}$ holds, and moreover $\overline{f}{}^{(0)}$ is unique. Otherwise, the codeword $\overline{f}{}^{(0)}$ won't exist.

FRI's security guarantee entails that if the prover's initial word $f^{(0)} : S^{(0)} \to \mathcal{T}_\tau$ is far from the initial code $C := \mathsf{RS}_{S, \mathcal{T}_\tau}[2^\ell, 2^{\ell + \mathcal{R}}]$, then the verifier will reject during its querying phase with overwhelming probability. This is true regardless of how the prover constructs its positive-indexed oracles $f^{(1)}, \ldots , f^{(\ell - 1)}$.

Thus, stepping back, we see why FRI is called a proximity test: its overall purpose is to detect whether some committed word $f^{(0)} : S^{(0)} \to \mathcal{T}_\tau$ is close or not. If the thing is not close, then the verifier will reject.

The NTT-Friendly Specialization

As we've mentioned, we use the additive NTT to encode our initial Reed–Solomon codeword $f^{(0)} : S^{(0)} \to \mathcal{T}_\tau$. As it happens, we are going to moreover want to choose the FRI folding maps $q^{(0)} : S^{(0)} \to \mathcal{T}_\tau$ in a particular way, in order to make those maps work "compatibly" with the additive NTT.

The particular sort of "compatibility" we're after here is pretty complicated, and we are going to essentially punt to [DP24, § 3.1] for the full treatment. Here, we give an extremely rough sketch.

We've already mentioned that, if the prover is honest, then each word $f^{(i)} : S^{(i)} \to \mathcal{T}_\tau$ will be a codeword in $\mathsf{RS}_{S, \mathcal{T}_\tau}[2^\ell, 2^{\ell + \mathcal{R}}]$—that is, an evaluation of some polynomial $P^{(i)}(X)$ of degree less than $2^{\ell - i}$ on $S^{(i)}$. But which polynomial? In the case of $i = 0$, we already know, by definition of our commitment scheme: that is, it will be nothing other than

where $(a_0, \ldots , a_{2^\ell - 1})$ are the (flattened) coefficients of our initial multilinear. This is simply the definition of our commitment scheme. What about for positive $i > 0$?

In the work BaseFold [ZCF23], it is noted that in the prime-field setting, FRI folding acts in a "predictable" way upon the coefficients of the polynomial $P^{(i)}(X)$ underlying $f^{(i)}(X)$. That is, if $P^{(i)}(X)$'s coefficients are

let's say, then $f^{(i + 1)} = \mathsf{fold}(f^{(i)}, r_i)$ will be the evaluation on $S^{(i + 1)}$ of the polynomial $P^{(i + 1)}(X)$ with coefficients

That is, in the coefficient domain, FRI folding amounts to an even–odd folding of adjacent pairs of elements, using the random challenge $r_i$.

In [DP24, § 3.1], we describe a particular construction of the maps $q^{(i)} : S^{(i)} \to S^{(i + 1)}$ which causes this behavior to re-emerge in the binary setting. We emphasize that for maps $q^{(i)} : S^{(i)} \to S^{(i + 1)}$ chosen arbitrarily—and [BBHR18] does not suggest a particular choice—the required even–odd folding behavior will not be preserved.