# BaseFold+-: A Simple Improvement to BaseFold's Multilinear Polynomial Commitment Scheme using Point-Check

*Yuval Domb*
[e-mail]
###

In [BaseFold](https://eprint.iacr.org/2023/1705), the authors make a key observation about the connection between multilinear and univariate polynomials, and the [FRI](https://drops.dagstuhl.de/storage/00lipics/lipics-vol107-icalp2018/LIPIcs.ICALP.2018.14/LIPIcs.ICALP.2018.14.pdf) 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](https://dl.acm.org/doi/pdf/10.1145/146585.146605) 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

$$
eq(\underline{x}, \underline{z}) = \prod_{i=0}^{n-1} x_i z_i + (1 - x_i)(1 - z_i)
$$

The Sum-Check sum naturally evaluates to

$$
\sum_{\underline{x} \in \{0,1\}^n} \tilde{f}_M(\underline{x}) = f_M(\underline{z})
$$

which, by definition of a Multi-Linear Extension (MLE), provides the desired sample at $\underline{z}$.
At the end of the protocol, the Verifier checks that

$$
c_r \cdot eq(\underline{r}, \underline{z}) = \tilde{f}_M(\underline{r})
$$

where $c_r$ and $\tilde{f}_M(\underline{r})$ are the outputs of FRI and Sum-Check, respectively.

Intuitively, BaseFold's elegant heuristic is to use Sum-Check as an IOP for deterministically sampling $f_M(\underline{z})$ and FRI as its random oracle instance, binding Sum-Check to the random sample $f_M(\underline{r})$.
We identify two shortcomings of this method that are not addressed in this blog:
1. The randomness sequence $\underline{r}$ consists strictly of in-domain evaluations to facilitate the FRI query phase. This concretely lowers Sum-Check's security, as it relies on a smaller sampling subset for its randomness. A way to decouple this limitation is by sampling the randomness from an extension field, as mentioned in Remark 2 of the [BaseFold paper](https://eprint.iacr.org/2023/1705). This allows increasing the domain size for Sum-Check while still working on the original FRI domain. Interestingly, we think that this method is similar to running the PCS multiple times for the same $\underline{z}$ but different randomness sequences $\underline{r}$.
2. Since the PCS evaluation must be unique, FRI must operate within the Unique-Decoding-Radius regime. Potential approaches to mitigate this are discussed in [Basefold in the List Decoding Regime](https://eprint.iacr.org/2024/1571.pdf), [DeepFold](https://eprint.iacr.org/2024/1595.pdf), and [Khatam](https://eprint.iacr.org/2024/1843.pdf).

## Our Contribution
A simple improvement to BaseFold's PCS involves replacing the Sum-Check protocol with a *Point-Check* protocol. Instead of using a Sum-Check of degree two, we propose a simpler approach equivalent to an MLE Sum-Check (i.e., a Sum-Check of degree one). This marks a concrete improvement from a product Sum-Check to an MLE-equivalent Sum-Check.

Point-Check is an interactive protocol between a Prover and a Verifier, where the Prover attempts to convince the Verifier of the correctness of $f_M(\underline{z})$, an evaluation of an MLE polynomial.
The protocol proceeds as follows:
- Note that we use $\hat{f}_M$ in place of $f_M$ to highlight that it is a Prover's claim rather than the ground-truth. For an honest Prover, they are the same.
1. The Prover sends the claimed evaluation $\hat{f}_M(z_0, z_1, \dots, z_{n-1})$ to the Verifier, along with the linear polynomial $\hat{f}_M(x, z_1, \dots, z_{n-1})$.
2. The Verifier checks that the polynomial satisfies $\hat{f}_M(x, z_1, \dots, z_{n-1}) \big|_{x = z_0} = \hat{f}_M(z_0, z_1, \dots, z_{n-1})$ and then provides the Prover with a random sample $r_0$.
3. The Prover responds with the linear polynomial $\hat{f}_M(r_0, x, z_2, \dots, z_{n-1})$, which the Verifier checks using

$$
\hat{f}_M(r_0, x, z_2, \dots, z_{n-1}) \big|_{x = z_1} = \hat{f}_M(x, z_1, z_2, \dots, z_{n-1}) \big|_{x = r_0}
$$

4. In the $i$-th round, the Prover sends the polynomial $\hat{f}_M(r_0, \dots, r_{i-1}, x, z_{i+1}, \dots, z_{n-1})$.
5. In the final round, the Verifier receives $\hat{f}_M(r_0, r_1, \dots, r_{n-2}, x)$, evaluates it at the last random sample $x = r_{n-1}$, and verifies it against the random oracle output $f_M(r_0, r_1, \dots, r_{n-1})$.

A tabular representation of the Prover-Verifier interaction is presented below.

| # | Prover || Verifier |
| - | - | - | - |
|| $\hat{f}_M(z_0, z_1, \dots, z_{n-1})$ | $\rightarrow$ ||
| 0 | $\hat{f}_M(x, z_1, \dots, z_{n-1})$ | $\rightarrow$ ||
|||| $\begin{align}\text{assert:}\\\hat{f}_M&(x, z_1, \dots, z_{n-1})\|_{x = z_0} \\&== \hat{f}_M(z_0, z_1, \dots, z_{n-1})\end{align}$ |
||| $\leftarrow$ | $r_0$ |
| 1 | $\hat{f}_M(r_0, x, z_2, \dots, z_{n-1})$ | $\rightarrow$ |
|||| $\begin{align}\text{assert:}\\\hat{f}_M&(r_0, x, z_2, \dots, z_{n-1})\|_{x = z_1} \\&== \hat{f}_M(x, z_1, z_2, \dots, z_{n-1})\|_{x = r_0}\end{align}$ |
||| $\leftarrow$ | $r_1$ |
| $\vdots$ |
| $i$ | $\hat{f}_M(\dots, r_{i-1}, x, z_{i+1}, \dots)$ | $\rightarrow$ |
|||| $\begin{align}\text{assert:}\\\hat{f}_M&(\dots, r_{i-1}, x, z_{i+1}, \dots)\|_{x = z_i} \\&== \hat{f}_M(\dots, r_{i-2}, x, z_i, \dots)\|_{x = r_{i-1}}\end{align}$ |
||| $\leftarrow$ | $r_i$ |
| $\vdots$ |
| $n-1$ | $\hat{f}_M(r_0, r_1, \dots, r_{n-2}, x)$ | $\rightarrow$ ||
|||| $\begin{align}\text{assert:}\\\hat{f}_M&(r_0, r_1, \dots, r_{n-2}, x)\|_{x = r_{n-1}} \\&== f_M(r_0, r_1, \dots, r_{n-1})\end{align}$ |

This approach concretely reduces the Sum-Check degree from two to one, simplifying the protocol. Additionally, it allows direct verification of the Point-Check output against the FRI random oracle instance, obsoleting the multiplication by $eq(\underline{r}, \underline{z})$.

## A Concluding Remark
Interestingly, in BaseFold’s PCS, Point-Check (or Sum-Check) serves two key purposes:

1. Mapping the security guarantees from the random sample $f_M(\underline{r})$ to the target sample $f_M(\underline{z})$ with high probability.
2. Extending the PCS's sampling set from in-domain to out-of-domain.

This gives rise to the following schematic interpretation of BaseFold’s PCS:

- **Point-Check**, a degenerate Sum-Check IOP, is used solely to bind $f_M(\underline{z})$ to $f_M(\underline{r})$.
- **FRI**, an IOP of Proximity (IOPP), functions as a constrained, in-domain PCS, providing the evaluation $f_M(\underline{r})$.
- The binding between them is enforced through their round-by-round interleaving.

Finally, we ask: can this heuristic be formulated more compactly, or is it optimal?

## Acknowledgments
I’d like to extend my gratitude to Hadas Zeilberger from Yale University for reviewing the blog and pointing out a few things that I missed. A special thanks to Suyash Bagad, Karthik Inbasekar, Tomer Solberg, and Omer Shlomovits from Ingonyama for invaluable discussions.