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

Yuval Domb
[e-mail]

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(\underset{―}{x})$, where

$\underset{―}{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

$\mathrm{deg}(f_U)=2^n-1$, as expected. We refer to

$f_M(\underset{―}{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

$\underset{―}{r}\equiv (r_0,r_1,\dots ,r_{n-1})$ results in a constant polynomial

$f(x)=c_r$ where

$c_r=f_M(\underset{―}{r})$, the evaluation of

$f_U(x)$'s multilinear twin at

$\underset{―}{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(\underset{―}{x})$ and aims to construct a transparent PCS for evaluating it at

$\underset{―}{z}\in {\mathbb{F}}^n$.
The Prover begins by committing to

$f_U(x)$, the univariate twin of

$f_M(\underset{―}{x})$. It then concurrently executes the FRI protocol on

$f_U(x)$ and the Sum-Check protocol on the modified polynomial

${\tilde{f}}_M(\underset{―}{x})\equiv f_M(\underset{―}{x})\cdot eq(\underset{―}{x},\underset{―}{z})$, where

$$eq(\underset{―}{x},\underset{―}{z})=\prod _{i=0}^{n-1}{x}_i{z}_i+(1-x_i)(1-z_i)$$

The Sum-Check sum naturally evaluates to

$$\sum _{\underset{―}{x}\in \{0,1{\}}^n}{\tilde{f}}_M(\underset{―}{x})=f_M(\underset{―}{z})$$

which, by definition of a Multi-Linear Extension (MLE), provides the desired sample at

$\underset{―}{z}$.
At the end of the protocol, the Verifier checks that

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

where

$c_r$ and

${\tilde{f}}_M(\underset{―}{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(\underset{―}{z})$ and FRI as its random oracle instance, binding Sum-Check to the random sample

$f_M(\underset{―}{r})$.
We identify two shortcomings of this method that are not addressed in this blog:

1. The randomness sequence
   $\underset{―}{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. 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
   $\underset{―}{z}$ but different randomness sequences
   $\underset{―}{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, DeepFold, and Khatam.

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(\underset{―}{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}){|}_{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}){|}_{x=z_1}={\hat{f}}_M(x,z_1,z_2,\dots ,z_{n-1}){|}_{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})$	$\to$
0	${\hat{f}}_M(x,z_1,\dots ,z_{n-1})$	$\to$
			$\begin{array}{r}\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{array}$
		$\leftarrow$	$r_0$
1	${\hat{f}}_M(r_0,x,z_2,\dots ,z_{n-1})$	$\to$
			$\begin{array}{r}\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{array}$
		$\leftarrow$	$r_1$
$⋮$
$i$	${\hat{f}}_M(\dots ,r_{i-1},x,z_{i+1},\dots )$	$\to$
			$\begin{array}{r}\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{array}$
		$\leftarrow$	$r_i$
$⋮$
$n-1$	${\hat{f}}_M(r_0,r_1,\dots ,r_{n-2},x)$	$\to$
			$\begin{array}{r}\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{array}$

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(\underset{―}{r},\underset{―}{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(\underset{―}{r})$ to the target sample
   $f_M(\underset{―}{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(\underset{―}{z})$ to
  $f_M(\underset{―}{r})$.
• FRI, an IOP of Proximity (IOPP), functions as a constrained, in-domain PCS, providing the evaluation
  $f_M(\underset{―}{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.