This note attempts to be a summary of the Basefold paper and talk by Binyi Chen.

The paper makes three major contributions that are all interlinked. It introduces

1. a linear code (which we call "foldable code") that generalizes the Reed-Solomon code such that it no longer requires FFT-friendly fields,
2. an Interactive Oracle of Proximity (IOPP), which uses the foldable code, and can be thought of as FRI but for multilinear polynomials, and
3. a polynomial commitment scheme for multilinear polynomials, which mixes the IOPP and sum-check together.

Let's dive in!

Foldable code

The authors present a code family that generalizes Reed-Solomon code such that the code is still linear, but doesn't rely on FFT-friendly fields. The code family is defined as

$$\begin{array}{rl}En{c}_{d+1}(m_l||m_r)=& [En{c}_d(m_l)+t_l^{(d)}\circ En{c}_d(m_r)]||\\ & [En{c}_d(m_l)+t_r^{(d)}\circ En{c}_d(m_r)]\end{array}$$

where "

$||$" represents concatenation, and

$$\begin{array}{rl}m& =m_l||m_r,m\in {\mathbb{F}}^{2^{d+1}},\\ En{c}_d:& {\mathbb{F}}^{2^d}\to {\mathbb{F}}^{2^{d+c}},\\ t_l^{(d)}& \in {\mathbb{F}}^{2^{d+c}},\\ t_r^{(d)}& \in {\mathbb{F}}^{2^{d+c}}.\end{array}$$

In words,

$2^c$ is the blowup factor.

$t_l^{(d)}$ and

$t_r^{(d)}$ are parameters of the code.

The Basefold authors define

$En{c}_{d+1}$ as being "foldable".

Notice that

$\{t_l^{(d)}{\}}_{d=0}^{d=k}$,

$\{t_r^{(d)}{\}}_{d=0}^{d=k}$ and

$En{c}_0$, where

$2^k$ is the length of the original message to encode, fully define the code. That is, each assignment of values to these parameters results in a different code. We will defer to the paper and the talk for how those values are chosen in practice.

Linearity of the code

The only property of interest for this discussion is that

$En{c}_0$ is a linear function; that is, it can be represented is a

$1\times 2^c$ matrix. We can then show by induction that

$En{c}_d$ for all

$d$ are also linear. That is, assuming that

$En{c}_d$ is linear, show that

$En{c}_{d+1}$ is linear. Let

$M$ be the matrix that represents

$En{c}_d$. Then,

$$\begin{array}{rl}En{c}_{d+1}(m_l||m_r)& =[M{m}_l+t_l^{(d)}\circ M{m}_r]||[M{m}_l+t_r^{(d)}\circ M{m}_r]\\ & =[M{m}_l+T_{l}M{m}_r]||[M{m}_l+T_{r}M{m}_r]\\ & =\left[\begin{array}{cccc}M& T_{l}M& 0& 0\\ 0& 0& M& T_{r}M\end{array}\right]\left[\begin{array}{c}{m}_l\\ m_r\end{array}\right]\end{array}$$

where

$T_l^{(d)}$ is a diagonal matrix where the entries along the diagonal are the elements of

$t_l^{(d)}$ (and similarly for

$T_r^{(d)}$). Hence, since

$En{c}_{d+1}$ can be represented by a matrix, it is linear, which completes the proof sketch.

Reed-Solomon generalization check

This section can be safely skipped upon first read

We claimed earlier that the code presented above is a generalization of the Reed-Solomon code. Hence, we need to show that there exists

$\{t_l^{(d)}{\}}_{d=0}^{d=k}$,

$\{t_r^{(d)}{\}}_{d=0}^{d=k}$ and

$En{c}_0$ which result in a Reed-Solomon code.

Recall the definition of a Reed-Solomon code. For

$f(x)\in F[X{]}^{\le 2^{d+1}}$ (i.e.

$f(x)$ is a polynomial of degree less or equal than

$2^{d+1}$),

$$R{S}_{d+1}(f(x))=f(x)[\omega ,{\omega }^2,\dots ,{\omega }^{2^{d+1+c}}]$$

where the brackets signify that

$f(x)$ is evaluated over all these points, the result stored in a list of corresponding length.

$\omega$ is the generator of a group of size

$2^{d+1+c}$.

f(x) even/odd decomposition

Next, define

$f_e(x)$ and

$f_o(x)$ to be the polynomials whose coefficients correspond to the event and odd coefficients of

$f(x)$, respectively. For example, if

$f(x)=a{x}^3+b{x}^2+cx+d$, then

$f_e(x)=ax+c$ and

$f_o(x)=bx+d$. Formally, this is written as

$$f(x)=f_e(x^2)+x\cdot f_o(x^2)$$

$R{S}_{d+1}$ decomposition

Next, since the Reed-Solomon code is linear, the following holds:

$$\begin{array}{rl}R{S}_{d+1}(f(x))& =R{S}_{d+1}(f_e(x^2)+x\cdot f_o(x^2))\\ & =R{S}_{d+1}(f_e(x^2))+R{S}_{d+1}(x)\circ R{S}_{d+1}(f_o(x^2))\end{array}$$

where

$\circ$ is the Hadamard product.

Next, notice the following

$$\begin{array}{rl}R{S}_{d+1}(f_e(x^2))& =f_e(x^2)[\omega ,{\omega }^2,\dots ,{\omega }^{2^{d+1+c}}]\\ & =f_e(x)[{\omega }^2,{\omega }^4,\dots ,{\omega }^{2^{d+2+c}}]\\ & =f_e(x)[{\omega }^2,{\omega }^4,\dots ,{\omega }^{2^{d+1+c}},{\omega }^2,{\omega }^4,{\omega }^{2^{d+1+c}}]\\ & =R{S}_d(f_e(x))||R{S}_d(f_e(x))\end{array}$$

Naturally, the same holds for

$R{S}_{d+1}(f_o(x^2))$. Therefore, we can rewrite

$R{S}_{d+1}(f(x))$ as

$$\begin{array}{rl}& R{S}_{d+1}(f(x))=\\ & R{S}_d(f_e(x))+[\omega ,{\omega }^2,\dots ,{\omega }^{2^{d+c}}]\circ R{S}_d(f_o(x))||\\ & R{S}_d(f_e(x))+[{\omega }^{2^{d+c}+1},\dots ,{\omega }^{2^{d+c+1}}]\circ R{S}_d(f_o(x))\end{array}$$

Notice that this fits the foldability property, where

$$\begin{array}{rl}& m_l=f_e(x)\\ & m_r=f_o(x)\\ & t_l=[\omega ,{\omega }^2,\dots ,{\omega }^{2^{d+c}}]\\ & t_r=[{\omega }^{2^{d+c}+1},\dots ,{\omega }^{2^{d+c+1}}]\end{array}$$

This comes with a caveat. The foldability property requires the coefficients of

$f_e(x)$ to be stored in the left part of

$m$, followed by the coefficients of

$f_o(x)$. And this must be true recursively. Hence, if

$$f(x)=a_7{x}^7+\cdots +a_{1}x+a_0$$

then

$f(x)$'s coefficients must be stored as

$$[a_0,a_4,a_2,a_6,a_1,a_5,a_3,a_7]$$

We leave it as an exercise to verify why this is correct.

IOPP

The Basefold paper introduces a new Interactive Oracle Proof of Proximity (IOPP) analogous to FRI, but for multilinear polynomials. That is, the protocol convinces the verifier that the prover has a multilinear polynomial (or, to be more precise, a function "close" to one). Where FRI uses Reed-Solomon codes, Basefold's IOPP uses the foldable code presented in the previous sections. Finally, similar to FRI, Basefold's IOPP also has a "commit" phase, where the prover commits to codes using Merkle trees for a number of layers, and a "query" phase, where the verifier queries random points in the codes to check for consistency between the layers.

Formally, the goal of the prover is to show that it has some polynomial

$f^{(d)}\in F[X_1,\dots ,X_d{]}^{\le 1}$. Throughout this post, we will assume that all multilinear polynomials

$f(x_1,\dots ,x_n)=f_l(x_1,\dots ,x_{n-1})+x_n\cdot f_r(x_1,\dots ,x_{n-1})$ are stored as

$f=f_l(x_1,\dots ,x_{n-1})||f_r(x_1,\dots ,x_{n-1})$ in coefficient form. In words,

$f_l$ is the multilinear polynomial formed from all the coefficients of

$f$ which do not have an

$x_n$ term, while

$f_r$ is the multilinear polynomial formed formed from the coefficients which do have an

$x_n$ term.

For example, if

$f(x_1,x_2)=a{x}_1{x}_2+b{x}_1+c{x}_2+d$, then

$f_l(x_1)=b{x}_1+d$ and

$f_r(x_1)=a{x}_1+c$. Therefore,

$f$ would be stored as an array of coefficients in the following order:

$[b,d,a,c]$.

Commit phase

In the first round, the prover encodes

$f^{(d)}(x_1,\dots ,x_d)$ as

${\pi }^{(d)}=En{c}_d(f^{(d)})$, where

${\pi }^{(d)}\in {\mathbb{F}}^{2^{d+c}}$. It builds a Merkle tree, where elements of

${\pi }^{(d)}$ are the leaves of the tree, and sends the Merkle root to the verifier.

The verifier then sends a random

$r_d{\in }_R\mathbb{F}$. The prover uses this random value to build the multilinear polynomial for the next layer:

$$f^{(d-1)}(x_1,\dots ,x_{d-1})=f_l^{(d)}(x_1,\dots ,x_{d-1})+r_d\cdot f_r^{(d)}(x_1,\dots ,x_{d-1})$$

The protocol repeats similarly for another

$d-1$ rounds.

Notice: by construction,

$f^{d-1}(x_1,\dots ,x_{d-1})=f^d(x_1,\dots ,x_{d-1},r_d)$. In words,

$f^{d-1}$ is

$f^d$ where the last variable has been fixed to

$r_d$. If we extend this observation all the way down to the last round,

$f^0=f^d(r_1,\dots ,r_d)$, for random

$r_1\dots r_d$. This will be an important point in the last section when we talk about the Basefold polynomial commitment scheme.

Query phase

The goal of the query phase is for the verifier to check the consistency between

${\pi }^{(j)}$ and

${\pi }^{(j-1)}$ for

$j\in \{d,\dots 1\}$. Concretely, from 2 points in

${\pi }^{(j)}$, the verifier will be able to compute a single point in

${\pi }^{(j-1)}$, for which the prover will send a Merkle proof. In order to do that, we will need to make use of the foldability property and linearity of the code.

Let

${\pi }^{(d)}={\pi }_l^{(d)}||{\pi }_r^{(d)}$. Recall that the foldability property of the code states that

$$\begin{array}{rl}{\pi }_l^{(d)}& =En{c}_{d-1}(f_l^{(d)})+t_l^{(d)}\circ En{c}_{d-1}(f_r^{(d)})\\ {\pi }_r^{(d)}& =En{c}_{d-1}(f_l^{(d)})+t_r^{(d)}\circ En{c}_{d-1}(f_r^{(d)})\end{array}$$

For readability purposes, we will define the following variables

$$\begin{array}{r}{E}_l=En{c}_{d-1}(f_l^{(d)})\\ E_r=En{c}_{d-1}(f_r^{(d)})\end{array}$$

With this we are ready to start discussing how queries work. The verifier samples

$i\in \{0,\dots ,2^{d+c-1}\}$. The prover sends

${\pi }_l^{(d)}[i]$,

${\pi }_r^{(d)}[i]$, and their corresponding Merkle proofs.

Next, the verifier infers

$E_l[i]$ and

$E_r[i]$. The previous definition of

${\pi }_l^{(d)}$ and

${\pi }_r^{(d)}$, when zooming in on the

$i^{th}$ index, can be written as

$$\left[\begin{array}{cc}1& t_l^{(d)}[i]\\ 1& t_r^{(d)}[i]\end{array}\right]\left[\begin{array}{c}{E}_l[i]\\ E_r[i]\end{array}\right]=\left[\begin{array}{c}{\pi }_l^{(d)}[i]\\ {\pi }_r^{(d)}[i]\end{array}\right]$$

or equivalently,

$$\left[\begin{array}{c}{E}_l[i]\\ E_r[i]\end{array}\right]={\left[\begin{array}{cc}1& t_l^{(d)}[i]\\ 1& t_r^{(d)}[i]\end{array}\right]}^{-1}\left[\begin{array}{c}{\pi }_l^{(d)}[i]\\ {\pi }_r^{(d)}[i]\end{array}\right]$$

Finally, recall from the commit phase that

$${\pi }^{(d-1)}=En{c}_{d-1}(f^{(d-1)})=En{c}_{d-1}(f_l^{(d)}+r_d\cdot f_r^{(d)})$$

We can use the linearity property of the code to get

$$En{c}_{d-1}(f_l^{(d)}+r_d\cdot f_r^{(d)})=En{c}_{d-1}(f_l^{(d)})+r_d\cdot En{c}_{d-1}(f_r^{(d)})=E_l+r_d\cdot E_r$$

When we focus on a single index

$i$, we get

$${\pi }^{(d-1)}[i]=E_l[i]+r_d\cdot E_r[i]$$

Hence, the verifier was able to compute

${\pi }^{(d-1)}[i]$, which was our initial goal.

Note that

${\pi }^{(d-1)}[i]$ either lies in the first or second half of

${\pi }^{(d-1)}$; that is,

${\pi }^{(d-1)}[i]={\pi }_l^{(d-1)}[\frac{i}{2}]$ when

$i<\frac{|{\pi }^{(d-1)}|}{2}$, or

${\pi }^{(d-1)}[i]={\pi }_r^{(d-1)}[\frac{i}{2}]$ otherwise. Whichever one it is, the prover only needs to send the Merkle proof for it, since the verifier already computed the value. Naturally, the prover also needs to send the value & Merkle proof for the other half (which the verifier didn't compute).

The same process then repeats for each round. In the last round, the prover only sends the Merkle proof for

${\pi }^{(0)}[i^{(0)}]$. The verifier ensures that the Merkle proof check passes with the value of

${\pi }^{(0)}[i^{(0)}]$ that it computed, completing the query.

Note: we use

$i^{(0)}$ to signify the index in the last round, where

$i^{(0)}=\frac{i}{2^d}$.

As in FRI, the verifier performs a number of queries, depending on the desired security level (i.e. the more queries, the more secure).

Polynomial commitment scheme

The Basefold polynomial commitment scheme relies heavily on sum-check. Refer to this article for a refresher.

The Basefold paper culiminates into a polynomial commitment scheme (PCS) for multilinear polynomials. That is, it allows a prover to commit to a multilinear polynomial

$f$, and convince the verifier that

$f(z)=y$ for some point

$z\in {\mathbb{F}}^d$ chosen by the verifier. The core idea is to interleave sum-check and the IOPP.

In this section, we will freely switch between the equalivalent notations for vectors

$z\in {\mathbb{F}}^d$:

$z=(z_1,\dots ,z_d)$.

First, we rewrite

$f(z_1,\dots ,z_d)$ in a form that is amenable to being sum-checked.

$$f(z_1,\dots ,z_d)=\sum _{(x_1,\dots ,x_d)\in B_d}f(x_1,\dots ,x_d)\cdot e{q}_z(x_1,\dots ,x_d)$$

where

$B_d=\{0,1{\}}^d$ is the

$d$-dimensional boolean hypercube, and

$e{q}_z(x_1,\dots ,x_d)=\prod _{i=1}^d{x}_i{z}_i+(1-x_i)(1-z_i)$. The above equality is true by definition of multilinear polynomials.

For a refresher on multilinear polynomials, see this article.

Recall that sum-check requires the verifier to be able to evaluate

$f(x)\cdot e{q}_z(x)$ at a random point

$r=(r_1,\dots ,r_d)$ generated during the protocol. The key realization to make is that in the commit phase of IOPP, the last polynomial computed by the prover

$f^{(0)}=f^{(d)}(r_1,\dots ,r_d)$! So if we reuse the same random

$r$ generated in the IOPP for sum-check, then the verifier can use

$f^{(0)}$ sent by the prover as its query

$f^{(d)}(r)$.

Note: this requires the prover to send

$f^{(0)}$ in the last step of the IOPP instead of

${\pi }^{(0)}$. The verifier can then compute

${\pi }^{(0)}=En{c}_0(f^{(0)})$ on its own in constant time.

Hence, the PCS protocol is as follows:

1. Run the commit phase of the IOPP.
   • This generates
     $r=(r_1,\dots ,r_d)$
2. Run sum-check, except reusing
   $(r_1,\dots ,r_d)$ as random values
   • Use
     $f^{(0)}$ as the value for
     $f^{(d)}(r_1,\dots ,r_d)$
   • The final verifier check is
     $g_1(r_1)=f^{(0)}\cdot e{q}_z(r)$, where
     $g_1$ is the last round polynomial sent by the prover.
3. Run the query phase of the IOPP

Pause and ponder

In a sense, sum-check almost gives you a multilinear PCS; the only missing piece is that last query

$f^{(d)}(r)$. But the prover already computes that query

$f^{(d)}(r)$, as well as all intermediary polynomials (

$f^{(d-1)}(x_1,\dots ,x_{d-1})=f^{(d)}(x_1,\dots ,x_{d-1},r_d)$,

$f^{(d-2)}(x_1,\dots ,x_{d-2})=f^{(d)}(x_1,\dots ,x_{d-2},r_{d-1},r_d)$, etc) during the protocol. Hence, the core idea of the Basefold PCS is to commit to these intermediary polynomials, and in a way, have the verifier track the correct transformation from

$f^{(i)}$ to

$f^{(i-1)}$.

But in order to do that, what was missing is a linear code for multilinear polynomials that allows the verifier to track the correct transformation between codewords (i.e. the "foldable" property). Additionally, it's crucial for the IOPP to be computing

$f^{(i-1)}=f_l^{(i)}+r_i{f}_r^{(i)}$ (that is, the same computation done during sum-check).

All in all, the Basefold PCS is a very clever construction at the intersection of all these ideas.