Building a polynomial commitment scheme from the FRI-IOPP

$$
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 $\mathbb{F}$ denote a finite field, write $\mathrm{\Omega }\subset \mathbb{F}$ for a subgroup of the group of units ${\mathbb{F}}^{\times }$ with $|\mathrm{\Omega }|$ a power of two. Let ${\mathbb{F}}^{\mathrm{\Omega }}$ denote the vector space of functions $\mathrm{\Omega }\to \mathbb{F}$, considered as vectors with entries indexed by some fixed enumeration of $\mathrm{\Omega }$ (we’ll call elements of ${\mathbb{F}}^{\mathrm{\Omega }}$ “words”). Let $\mathrm{E}:\mathbb{F}[X]\to {\mathbb{F}}^{\mathrm{\Omega }}$ denote the evaluation map, i.e. $$(\mathrm{E}f{)}_{\omega }=f(\omega )\mathrm{\forall }f\in \mathbb{F}[X]\mathrm{\forall }\omega \in \mathrm{\Omega }.$$ Write $\mathrm{\Delta }$ for the relative Hamming distance on ${\mathbb{F}}^{\mathrm{\Omega }}$, and let ${\mathrm{RS}}_k=\mathrm{E}(\mathbb{F}[X{]}^{<k})\subset {\mathbb{F}}^{\mathrm{\Omega }}$ denote the Reed-Solomon code with degree bound $k$. Fix throughout some degree bound $1<d<|\mathrm{\Omega }|$. We will be concerned with two separate Reed-Solomon codes, namely ${\mathrm{RS}}_d$ and ${\mathrm{RS}}_{d-1}$ (note that both use the same evaluation points $\mathrm{\Omega }$). Write ${\delta }_0$ for the unique decoding radius of ${\mathrm{RS}}_d$, i.e. ${\delta }_0$ is maximal such that, for any $f\in \mathbb{F}[X{]}^{<d}$ and $u\in {\mathbb{F}}^{\mathrm{\Omega }}$, $$\mathrm{\Delta }(u,\mathrm{E}f)⩽{\delta }_0⟹(\mathrm{\forall }g\in \mathbb{F}[X{]}^{<d}\mathrm{\Delta }(u,\mathrm{E}g)⩽{\delta }_0⟹f=g).$$

The data of a commitment in the FRI-PCS with degree bound $d$ is a word $u\in {\mathbb{F}}^{\mathrm{\Omega }}$ (more precisely: an oracle to $u$). Assume for now that the prover is honest. In the simplest case, $u=\mathrm{E}f$ for some $f\in \mathbb{F}[X{]}^{<d}$. 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 $\mathrm{E}f$, i.e. $$\begin{array}{}\text{(UDR)}& \mathrm{\Delta }(u,\mathrm{E}f)⩽{\delta }_0\mathrm{\exists }f\in \mathbb{F}[X{]}^{<d}.\end{array}$$ Any such $u$ is considered to be a valid commitment to its corresponding $f\in \mathbb{F}[X{]}^{<d}$. Why is this subtlety necessary? Because if the stricter condition $u=\mathrm{E}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 nearby non-codewords (for an explicit demonstration, see here).

Assuming that the prover has sent a commitment $u\in {\mathbb{F}}^{\mathrm{\Omega }}$ to the verifier, an evaluation proof proceeds as follows. The verifier chooses an evaluation point $r\in \mathbb{F}\setminus \mathrm{\Omega }$ and sends this to the prover, and the prover responds with the purported evaluation $c$ of the polynomial committed to (in the case of an honest prover, $c=f(r)$ where $f$ is determined by $\text{(UDR)}$). The prover wants to establish $$\begin{array}{}\text{(TwoPart)}& \mathrm{\exists }f\in \mathbb{F}[X{]}^{<d}\mathrm{s}.\mathrm{t}.\mathrm{\Delta }(u,\mathrm{E}f)⩽{\delta }_0\text{and}f(r)=c.\end{array}$$
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{array}{}\text{(Unified)}& \mathrm{\exists }q\in \mathbb{F}[X{]}^{<d-1}\mathrm{s}.\mathrm{t}.\mathrm{\Delta }(u,\mathrm{E}((X-r)q+c))⩽{\delta }_0.\end{array}$$ Thus we are interested in the proximity of the commitment $u$ to a specific subset of ${\mathrm{RS}}_d$, namely the subset consisting of codewords of the form $\mathrm{E}((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 ${\mathbb{F}}^{\mathrm{\Omega }}$). The good news is that, with a small amount of work, it can be seen that the claim $\text{(Unified)}$ is equivalent to a claim that can be established using the FRI-IOPP (with degree bound $d-1$). This claim involves a vector ${\mathrm{D}}_{r,c}u\in {\mathbb{F}}^{\mathrm{\Omega }}$ 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 {\mathbb{F}}^{\mathrm{\Omega }}$ that commits to $f\in \mathbb{F}[X{]}^{<d}$. 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 \mathrm{\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:\mathbb{F}\to \mathbb{F}$ for each $\omega \in \mathrm{\Omega }$, a bijection $\theta :{\mathbb{F}}^{\mathrm{\Omega }}\to {\mathbb{F}}^{\mathrm{\Omega }}$ of the space of all words can be defined by $$(\theta v{)}_{\omega }={\theta }_{\omega }(v_{\omega })\mathrm{\forall }v\in {\mathbb{F}}^{\mathrm{\Omega }},\mathrm{\forall }\omega \in \mathrm{\Omega }.$$ Call such a map $\theta$ a “component-wise bijection”; it is immediate for any such map that $$\begin{array}{}\text{(HDInv)}& \mathrm{\Delta }(\theta u,v)=\mathrm{\Delta }(u,{\theta }^{-1}v)\mathrm{\forall }u,v\in {\mathbb{F}}^{\mathrm{\Omega }}.\end{array}$$ For any $r\in \mathbb{F}\setminus \mathrm{\Omega }$ and $c\in \mathbb{F}$, define a component-wise bijection ${\mathrm{D}}_{r,c}:{\mathbb{F}}^{\mathrm{\Omega }}\to {\mathbb{F}}^{\mathrm{\Omega }}$ by $$({\mathrm{D}}_{r,c}u{)}_{\omega }=\frac{u_{\omega }–c}{\omega –r}\mathrm{\forall }u\in {\mathbb{F}}^{\mathrm{\Omega }},\mathrm{\forall }\omega \in \mathrm{\Omega }.$$ Its inverse is given by $$({\mathrm{D}}_{r,c}{}^{-1}(v){)}_{\omega }=(\omega –r)v_{\omega }+c\mathrm{\forall }v\in {\mathbb{F}}^{\mathrm{\Omega }},\mathrm{\forall }\omega \in \mathrm{\Omega },$$ from which it follows immediately that $$\begin{array}{}\text{(DrcInverse)}& ({\mathrm{D}}_{r,c}{}^{-1}\circ \mathrm{E})(q)=\mathrm{E}((X-r)q+c)\mathrm{\forall }q\in \mathbb{F}[X].\end{array}$$ Combining $\text{(HDInv)}$ and $\text{(DrcInverse)}$, we obtain $$\begin{array}{}\text{(StepDown)}& \mathrm{\Delta }({\mathrm{D}}_{r,c}u,\mathrm{E}(q))=\mathrm{\Delta }(u,\mathrm{E}((X-r)q+c))\mathrm{\forall }v\in {\mathbb{F}}^{\mathrm{\Omega }}\mathrm{\forall }q\in \mathbb{F}[X],\end{array}$$ and substituting this into the claim $\text{(Unified)}$, we obtain the equivalent claim $$\begin{array}{}\text{(FRIable)}& \mathrm{\exists }q\in \mathbb{F}[X{]}^{<d-1}\mathrm{s}.\mathrm{t}.\mathrm{\Delta }({\mathrm{D}}_{r,c}u,\mathrm{E}q)⩽{\delta }_0,\end{array}$$ which the prover and verifier can establish using the FRI-IOPP! $\text{(FRIable)}$ is nothing more than the statement that ${\mathrm{D}}_{r,c}u$ is ${\delta }_0$-close to ${\mathrm{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 $\text{(TwoPart)}$ doesn’t hold, i.e. for all $f\in \mathbb{F}[X{]}^{<d}$, $u$ is not within the unique decoding radius of some $\mathrm{E}f$. Put differently, this is just saying that $\mathrm{\Delta }(u,{\mathrm{RS}}_d)>{\delta }_0$, i.e. “$u$ is ${\delta }_0$-far from the code ${\mathrm{RS}}_d$”. Thus, by $\text{(StepDown)}$, for any $q\in \mathbb{F}[X{]}^{<d-1}$, $$\mathrm{\Delta }({\mathrm{D}}_{r,c}u,\mathrm{E}q)=\mathrm{\Delta }(u,\mathrm{E}((X-r)q+c))⩾\mathrm{\Delta }(u,{\mathrm{RS}}_d)>{\delta }_0,$$ and so claim $\text{(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 $\mathrm{E}f$ for some $f\in \mathbb{F}[X{]}^{<d}$, but the claimed evaluation is false, i.e. $f(r)\ne c$. Then for any $q\in \mathbb{F}[X{]}^{<d-1}$, we have $f\ne (X-r)q+c$ (since otherwise the evaluations at $c$ would match), and so $\mathrm{E}f$ and $\mathrm{E}((X-r)q+c)$ are distinct codewords. Thus, by $\text{(StepDown)}$, $$\mathrm{\Delta }({\mathrm{D}}_{r,c}u,\mathrm{E}q)=\mathrm{\Delta }(u,\mathrm{E}((X-r)q+c))>{\delta }_0,$$ since $u$ can be within ${\delta }_0$ (the unique decoding radius) of at most one codeword (which is $\mathrm{E}f$).