Yuval Domb
yuval@ingonyama.com
In BaseFold, the authors make a key observation about the connection between multilinear and univariate polynomials, and the FRI protocol, leading to the construction of a new multilinear Polynomial Commitment Scheme (PCS).
Consider a multilinear polynomial $f_M(\underline{x})$, where $\underline{x} \equiv (x_0, x_1, \dots, x_{n-1})$. Transforming it into a univariate polynomial $f_U(x)$ can be done by substituting $x_i \leftarrow x^{2^i}$ for all $i \in [n]$. The resulting univariate polynomial has degree $\deg(f_U) = 2^n - 1$, as expected. We refer to $f_M(\underline{x})$ and $f_U(x)$ as the multilinear-univariate twins, hereafter.
Notably, executing $n$ rounds of the FRI protocol on the univariate polynomial $f_U(x)$ with the randomness sequence $\underline{r} \equiv (r_0, r_1, \dots, r_{n-1})$ results in a constant polynomial $f(x) = c_r$ where $c_r = f_M(\underline{r})$, the evaluation of $f_U(x)$'s multilinear twin at $\underline{r}$. This suggests that FRI can act as an instantiation of the random oracle for a Sum-Check Interactive Oracle Proof (IOP). Concretely, this entails executing the two protocols concurrently, round-by-round, using the same randomness and equating their outputs.
To construct a PCS, BaseFold proposes the following approach. Suppose a Prover is given a multilinear polynomial $f_M(\underline{x})$ and aims to construct a transparent PCS for evaluating it at $\underline{z} \in \mathbb{F}^n$.The Prover begins by committing to $f_U(x)$, the univariate twin of $f_M(\underline{x})$. It then concurrently executes the FRI protocol on $f_U(x)$ and the Sum-Check protocol on the modified polynomial $\tilde{f}_M(\underline{x}) \equiv f_M(\underline{x}) \cdot eq(\underline{x}, \underline{z})$, where