$\newcommand{\fxd}[0]{\mathbb{F}[X]^{< d}} \newcommand{\fxdone}[0]{\mathbb{F}[X]^{< d-1}} \newcommand{\RS}[0]{\mathrm{RS}} \newcommand{\drc}[0]{\mathrm{D}_{r, c}\,} \newcommand{\fo}[0]{\ff^\Omega} \newcommand{\eval}[0]{\mathrm{E}}$
Here we cover how to build a polynomial commitment scheme (PCS) from the FRI interactive oracle proof of proximity (FRI-IOPP). Specifically, we explain how to reduce an evaluation proof to a proof of proximity. It is assumed that the reader already understands the FRI-IOPP. Everything here was derived from reading Transparent PCS with polylogarithmic communication complexity (Vlasov & Panarin, 2019).
We assume the usual setup for FRI. Let $\ff$ denote a finite field, write $\Omega \subset \ff$ for a subgroup of the group of units $\ff^\times$ with $|\Omega|$ a power of two. Let $\fo$ denote the vector space of functions $\Omega \to \ff$, considered as vectors with entries indexed by some fixed enumeration of $\Omega$ (we’ll call elements of $\fo$ “words”). Let $\eval: \fx \to \fo$ denote the evaluation map, i.e. $$ (\eval f)_\omega = f(\omega) \quad \forall f \in \fx \quad \forall \omega \in \Omega.$$ Write $\Delta$ for the relative Hamming distance on $\fo$, and let $\RS_k = \eval (\fx^{< k}) \subset \fo$ denote the Reed-Solomon code with degree bound $k$. Fix throughout some degree bound $1 < d < |\Omega|$. We will be concerned with two separate Reed-Solomon codes, namely $\RS_d$ and $\RS_{d-1}$ (note that both use the same evaluation points $\Omega$). Write $\delta_0$ for the unique decoding radius of $\RS_d$, i.e. $\delta_0$ is maximal such that, for any $f \in \fxd$ and $u \in \fo$, $$ \Delta(u, \eval f) \leqslant \delta_0 \implies \left( \ \forall g \in \fxd \quad \Delta(u, \eval g) \leqslant \delta_0 \implies f = g \ \right).$$
The data of a commitment in the degree bound $d$ FRI-PCS is a word $u \in \fo$ (more precisely: an oracle to $u$). Assume for now the prover is honest. In the simplest case, $u = \eval f$ for some $f \in \fxd$. Crucially, however, we require something weaker than this of a commitment $u$: it is sufficient that $u$ be within the unique decoding radius of some codeword $\eval f$, i.e. $$\begin{equation}\label{UDR}\tag{UDR} \Delta (u, \eval f) \leqslant \delta_0 \quad \exists f \in \fxd.\end{equation}$$ Any such $u$ is considered to be a valid commitment to its corresponding $f \in \fxd$. Why is this subtlety necessary? Because if the stricter condition $u = \eval f$ were required, then the (soon to be explained) reduction of an evaluation proof to an invocation of the FRI-IOPP wouldn’t be possible. The FRI-IOPP isn’t sufficiently sensitive to reliably distinguish between a codeword and very nearby non-codewords (for an explicit demonstration, see here).
The prover having sent a commitment $u \in \fo$ to the verifier, an evaluation proof proceeds as follows. The verifier chooses an evaluation point $r \in \ff \setminus \Omega$ and sends this to the prover, and the prover responds with the purported evaluation $c$ of the committed to polynomial (in case of an honest prover, $c = f(r)$ where $f$ is determined by \eqref{UDR}). The prover wants to establish $$\begin{equation}\label{TwoPart}\tag{TwoPart} \exists f \in \fxd \quad \st \quad \Delta(u, \eval f) \leqslant \delta_0 \ \ \text{and} \ \ f(r) = c.\end{equation}$$
Since $f(r) = c$ if and only if $f-c$ is divisible by $X-r$, and degree is additive under polynomial multiplication, this two part claim is equivalent to the following unified claim:
$$\begin{equation}\label{Unified}\tag{Unified} \exists q \in \fxdone \quad \st \quad \Delta(u, \eval ((X-r)q + c)) \leqslant \delta_0.\end{equation}$$ Thus we are interested in the proximity of the commitment $u$ to a specific subset of $\RS_d$, namely the subset consisting of codewords of the form $\eval ((X-r)q + c)$. Note, however, that we can not immediately apply FRI-IOPP to establish this claim, since this subset is not itself a Reed-Solomon code (it isn’t even a linear subspace of $\fo$). The good news is that, with a small amount of work, it can be seen that the claim \eqref{Unified} is equivalent to a claim that can be established using the FRI-IOPP (with degree bound $d-1$). This claim involves a vector $\drc u \in \fo$ derived from $u$, which we’ll define below. And thus the FRI-PCS evaluation proof will be established using by a proximity proof!
Firstly, a note on oracles. Importantly, the verifier does not need to receive or read all of the $u \in \fo$ that commits to $f \in \fxd$. Since an evaluation proof reduces to an invocation of the FRI-IOPP, it is sufficient for the verifier to be supplied with a mechanism to query entries $u_\omega$ of $u$ at arbitrary indices $\omega \in \Omega$. In an information theoretic presentation, this mechanism is abstracted as an oracle. In implementation, the oracle is typically instantiated with a Merkle commitment to the tree whose leaves are the $u_\omega$ (enumerated in some agreed upon manner). The prover binds itself to $u$ by sending the Merkle root to the verifier, and the verifier queries an entry $u_\omega$ by asking the prover for the Merkle path from the root to the corresponding leaf.
Let’s now derive the reduction of the evaluation proof to an instance of the FRI-IOPP. Given bijections $\theta_w : \ff \to \ff$ for each $\omega \in \Omega$, a bijection $\theta : \fo \to \fo$ of the space of all words can be defined by $$(\theta v)_\omega = \theta_\omega (v_\omega) \quad \forall v \in \fo,\quad \forall \omega \in \Omega.$$ Call such a map $\theta$ a “component-wise bijection”; it is immediate for any such map that $$\begin{equation}\label{HDInv}\tag{HDInv} \Delta(\theta u,\ v) = \Delta(u,\ \theta^{-1} v) \quad \forall u, v \in \fo.\end{equation}$$ For any $r \in \ff \setminus \Omega$ and $c \in \ff$, define a component-wise bijection $\drc: \fo \to \fo$ by $$ (\drc u)_\omega = \frac{u_\omega – c}{\omega – r} \quad \forall u \in \fo, \quad \forall \omega \in \Omega.$$ Its inverse is given by $$ (\drc^{-1} (v))_\omega = (\omega – r) v_\omega + c \quad \forall v \in \fo, \quad \forall \omega \in \Omega,$$ from which it follows immediately that $$\begin{equation}\label{DrcInverse}\tag{DrcInverse} (\drc^{-1} \circ \eval) (q) = \eval ( (X-r) q + c) \quad \forall q \in \fx.\end{equation}$$ Combining \eqref{HDInv} and \eqref{DrcInverse}, we obtain $$\begin{equation}\label{StepDown}\tag{StepDown} \Delta(\drc u,\ \eval (q)) = \Delta(u,\ \eval((X-r)q + c)) \quad \forall v \in \fo \quad \forall q \in \fx,\end{equation}$$ and substituting this into the claim \eqref{Unified}, we obtain the equivalent claim $$\begin{equation}\label{FRIable}\tag{FRIable} \exists q \in \fxdone \quad \st \quad \Delta(\drc u, \eval q) \leqslant \delta_0,\end{equation}$$ which the prover and verifier can establish using the FRI-IOPP! \eqref{FRIable} is nothing more than the statement that $\drc u$ is $\delta_0$-close to $\RS_{d-1}$.
It is instructive to now consider the two possible cheating strategies for the prover in this reduction to the FRI-IOPP. The first is where the first claim of \eqref{TwoPart} doesn’t hold, i.e. for all $f \in \fxd$, $u$ is not within the unique decoding radius of some $\eval f$. Put differently, this is just saying that $\Delta(u,\ \RS_d) > \delta_0$, i.e. “$u$ is $\delta_0$-far from the code $\RS_d$”. Thus, by \eqref{StepDown}, for any $q \in \fxdone$, $$ \Delta(\drc u,\ \eval q) = \Delta(u,\ \eval ((X-r)q + c)) \geqslant \Delta(u,\ \RS_d) > \delta_0,$$ and so claim \eqref{FRIable} is false, and will be caught with the soundness bound of the FRI-IOPP. The only other cheating strategy for the prover is that where the $u$ is in the unique decoding radius of $\eval f$ for some $f \in \fxd$, but the claimed evaluation is false, i.e. $f(r) \ne c$. Then for any $q \in \fxdone$, we have $f \ne (X-r)q + c$ (since otherwise the evaluations at $c$ would match), and so $\eval f$ and $\eval ((X-r)q + c)$ are distinct codewords. Thus, by \eqref{StepDown}, $$\Delta(\drc u,\ \eval q) = \Delta(u,\ \eval ((X-r) q + c)) > \delta_0,$$ since $u$ can be within $\delta_0$ (the unique decoding radius) of at most one codeword (which is $\eval f$).