# BaseFold

BaseFold is a new multilinear polynomial commitment scheme. This scheme is the combination of sum-check and a generalized version of FRI.

This article will first introduce the generalization of FRI, then explain how to combine this generalized FRI protocol with sum-check to get a PCS.

## Generalization of FRI

### New Linear Code

BaseFold introduces a new linear code that has the following properties compared to Reed-Solomon code:

- The **same complexity** for encoding a vector (message): they are both $ O(N\log N) $ where $N$ is the vector size.
- The new linear code **does not put any restriction** on the finite field, while Reed-Solomon code requires the field to have large 2-adic multiplicative subgroup so that FFT can work.
- The new linear code has **smaller minimal distance** compared to Reed-Solomon code. This implies more queries later in the IOPP, and slower verifier and bigger proof size, for the same security level.

In short, this new linear code sacrifices the minimal distance in exchange for the freedom in finite field choice.

The generator matrix for this linear code is defined recursively in the following way:

1. Let $G_{0}$ be any matrix of size $m_{0}\times n_{0}$, where $m_{0}<n_{0}$.
2. For $i$ from $0$ to $d-1$, let

$$
G_{i+1}=\begin{pmatrix}G_{i}&G_{i}\\G_{i}\cdot T_i&-G_{i}\cdot T_{i}\end{pmatrix}
$$

Here $T_i$ is a diagonal matrix, and the diagonal elements are randomly selected.

Let $m_{i+1}=2m_i$ and $n_{i+1}=2n_i$.

Finally, let $G_{d-1}$ be the generator matrix of the linear code.

Because of the recursive structure, the encoding can proceed in the split-and-conquer manner as follows:

1. Given message $\vec{m}$ of size $m_d$, split $\vec{m}$ into $\vec{m}_{\ell}$ and $\vec{m}_r$ each of size $m_{d-1}=m_d/2$.
2. Encode $\vec{m}_{\ell}$ into $\ell$ and $\vec{m}_r$ into $r$, respectively.
3. Output $(\ell+r\cdot T_{d-1},\ell-r\cdot T_{d-1})$.

Note that because $T_i$ is a diagonal matrix, the last step is linear in $N$.

### Proximity Check IOP for This Code

Given a string oracle for a vector $\vec{v}$, prove that it is close to a codeword in a similar way as FRI.

#### Commit Phase

1. The verifier samples a random $\alpha$ and sends it to the prover.
2. The prover splits $\vec{v}$ into $(\ell+r\cdot T_{d-1},\ell-r\cdot T_{d-1})$, since $ \vec{v} $ is a valid codeword.
3. The prover sends the string oracle for $\ell+\alpha\cdot r$ to the verifier, which is also a valid codeword if $\vec{v}$ is.
4. Repeat with this new folded codeword, until the string oracle is a codeword generated by $G_0$. In this case, the prover sends the entire string in clear, instead of in the oracle. The verifier checks that it is indeed a valid codeword.

#### Query Phase

The verifier samples an index $t$ from $0$ to $n_d$, and queries the string oracles respectively

- The original oracle at $t$ and $t'=t\pm n_{d-1}$, get $x$ and $x'$
- The next oracle at $s=t\bmod n_{d-1}$, get $y$
- Check that the three points are colinear: $(T_{d-1}[s],x),(-T_{d-1}[s],x'),(\alpha,y)$
- Repeat this with $s$ and the next oracle, until reaching the last string that is sent in clear.

## Multilinear PCS by Combining FRI with Sum-check

Just like any other multilinear PCS, given the polynomial $f(\vec{X})$ of $\mu$ variables such that $N=2^{\mu}$, we collect its coefficients into a vector $\vec{m}$. Them we treat this vector as a message, encode it with the linear code to get a codeword $\vec{v}$. Now the string oracle (instantiated using Merkle tree) is viewed as the commitment to $f(\vec{X})$.

Therefore, just like FRI, the commitment generation for this PCS costs $O(N\cdot\mu)$ field operations and $O(N)$ hashes for computing the Merkle root.

Now comes the important part: given the commitment, how to open this polynomial at any point $\vec{z}$?

Before explaining the idea behind the opening protocol, let's have another look at the commit phase of the proximity check of the linear code, and try to answer the following question: if we treat the string oracles sent from the prover to the verifier also as polynomial oracles, what is the committed polynomial?

Recall that, to commit $\vec{m}$, we split it into $\vec{m}_{\ell}$ and $\vec{m}_r$, and encode them respectively to $\ell$ and $r$. Now, the question is, what is $\vec{m}_{\ell}$ and $\vec{m}_r$?

Right, they are just the coefficients of $f(\vec{X})$ with and without $X_{\mu}$, respectively. In another word, since $f(\vec{X})$ is multilinear, we can rewrite it as if it is a linear univariate polynomial w\.r.t. $X_{\mu}$, such that the coefficients are polynomials in $X_1,\cdots,X_{\mu-1}$. In detail,

$$
f(\vec{X})=f_1(\vec{X}_{1..\mu-1})+f_2(\vec{X}_{1..\mu-1})\cdot X_{\mu}
$$

Note that the coefficients of $f_1$ are just the left half of the message vector, i.e., $\vec{m}_{\ell}$, and the coefficients of $f_2$ are just the right half $\vec{m}_r$.

Therefore, by definition, the string oracles for $\ell$ and $r$ are exactly the polynomial commitments to $f_1$ and $f_2$, respectively.

Recall that in the first round of the commit phase of the IOPP, the prover sends the folded codeword that is equal to $\ell+\alpha\cdot r$. Therefore, this oracle string is the commitment to the polynomial $f_1+\alpha\cdot f_2$. This is exactly $f(X_1,\cdots,X_{\mu-1},\alpha)$, i.e., subtituting $\alpha$ into the last variable.

The following rounds are just the same. So in the end of the commitment phase, the verifier ends up with a polynomial of the form $f(X_1,\cdots,X_k,\alpha_{k+1},\cdots,\alpha_{\mu})$. Here $k$ is a small integer such that the size of this polynomial is relatively small.

What does this remind you? Yes, this looks very similar to the procedure of the sum-check protocol.

The key observation is that, after the commitment phase is over, **the verifier obtains an evaluation** of $f(\vec{X})$, which can be authenticated later by the query phase. And remember that in the end of the sum-check protocol, to accomplish the final check, the verifier is exactly **in need of an evaluation**.

Therefore, if we run the sum-check protocol and the IOPP in parallel, using the same verifier randomness, we get **a sum-check** for the committed polynomial, **without the final evaluation query**.

That's the basic idea of BaseFold. Of course, there are some details to care about:

- In the end, we want a protocol to open the polynomial at $\vec{z}$, not a sum-check. No problem, evaluating the polynomial is exactly computing the sum of the polynomial $f(\vec{X})\cdot eq_{\vec{z}}(\vec{X})$ over the hypercube. So the prover and the verifier should execute the sum-check protocol with this polynomial instead. In the end, the verifier needs a polynomial evaluation of $f(\vec{X})\cdot eq_{\vec{z}}(\vec{X})$ at the random point $\vec{\alpha}$. The verifier computes $eq_{\vec{z}}(\vec{\alpha})$ by its definition, and the evaluation $f(\vec{\alpha})$ is provided by the last string oracle in the IOPP.
- The IOPP stops early, i.e., it stops when the polynomial still has $k$ variables. Therefore, the sum-check protocol may also stop earlier than the traditional sum-check protocol. See the following protocol description for more detail.&#x20;

Like the proximity check for the linear code, the opening protocol for the BaseFold MPCS also proceeds in two phases: the committing phase and the query phase.

#### Commit Phase

The prover is given the polynomial $f(\vec{X})$, and the verifier is given the oracle string to the encoding of the coefficients of $f$. The claimed evaluation is $y$.

The prover computes the sum of the polynomial $f(\vec{X})\cdot eq_{\vec{z}}(\vec{X})$ over the hypercube $\{0,1\}^{\mu-1}$ and obtains a univariate low-degree polynomial $h(X_{\mu})$. The prover sends $h(X_{\mu})$ to the verifier. The verifier checks that $h(0)+h(1)$ is equal to the claimed evaluation $y$.

The verifier samples $\alpha$ and sends it to the prover.

The prover sends the oracle string of $f(\vec{X}_{1..\mu-1},\alpha)$ to the verifier. Note that the prover does not need to repeat the encoding algorithm. The prover just folds the two halves of the oracle string for $f$. This is exactly the same as in the proximity check.

The parties then repeat the above process, but with $f(\vec{X})$ replaced with $f(\vec{X}_{1..\mu-1},\alpha)$, $eq_{\vec{z}}(\vec{X})$ replaced with $eq_{\vec{z}}(\vec{X}_{1..\mu-1},\alpha)$, and $y$ replaced with $h(\alpha)$. And so on. Until one step, the prover sends the polynomial $f(X_1,\cdots,X_k,\alpha_{k+1},\cdots,\alpha_{\mu})$ instead of its oracle string to the verifier. In this case, the verifier directly computes the sum of the polynomial $f(X_1,\cdots,X_k,\alpha_{k+1},\cdots,\alpha_{\mu})\cdot eq_{\vec{z}}(X_1,\cdots,X_k,\alpha_{k+1},\cdots,\alpha_{\mu})$ over the hypercube of dimension $k$, and compare it with the $h(\alpha)$ in this round.

#### Query Phase

The verifier encodes the coefficients of $f(X_1,\cdots,X_k,\alpha_{k+1},\cdots,\alpha_{\mu})$ sent from the prover in the last step of the committing phase. Then everything is exactly the same as the proximity check for the linear code.

## Efficiency

The commitment generation is the same as FRI-based univariate PCS, except that the field can be arbitrary field of sufficient size.

The opening protocol is one sum-check plus one FRI-like procedure. The prover is linear for both of them. Unlike the traditional sum-check, there is no additional evaluation of a committed polynomial.

The verifier cost and the proof size is also that of one sum-check plus one FRI-like procedure, and is likely to be dominated by the FRI-like procedure. Moreover, because the code distance is smaller, the verifier and the proof size is likely to be worse than FRI.