The Polynomial Commitment

There are many ways of constructing polynomial commitments, including the KZG commitment which relies on elliptic curves and the FRI commitment. Binius will rely on a different kind of polynomial commitment, which has the advantage that it can be made compatible with bits without much memory overhead.

The Brakedown Polynomial Commitment

Suppose we’d like a way for the prover to commit to some data $\bar{w}$ in a way that’s compatible with the verifier learning (with help from the prover) a value $\tilde{w}(\zeta)$ in the multilinear extension of $\bar{w}$ where $\zeta \in \mathbb{F}^m$. As a first attempt, one could simply have the prover hash the values $\bar{w}$, but there’s not a good way to reveal the value $\tilde{w}(\zeta)$ without opening the entire commitment and computing $\tilde{w}(\zeta)$ from scratch. Alternatively, one could write down all the values of $\tilde{w}$ over $\mathbb{F}^m$ and commit to these. The benefit of this approach is that revealing $\tilde{w}(\zeta)$ requires just opening the commitment at a single location. However, this would require $|\mathbb{F}|^m = (2^m)^{\log |\mathbb{F}|}$ computation from the prover, which is far too expensive compared to the amount of raw data ($|\bar{w}| = 2^m$) the prover is actually trying to commit to. What’d we really like is a polynomial commitment scheme that uses a small linear factor overhead in the amount of computation needed.

Instead, we will rearrange the data $\bar{w}$ so that instead of lying in a $m$ dimensional hybercube of length $2$, it now lies in a $2$ dimensional square of length $2^{m/2}$. Then, we will commit to a low degree extension of this square, which will only require the prover to compute $O(2^m)$ additional values. But – the verifier wants to learn a point in the multilinear extension of $\bar{w}$, not the square extension – how can a square extension possibly be compatible with this task? It turns out that if we re-format $\bar{w}$ into a square in the correct way, a random point in the multilinear extension of $\tilde{w}$ becomes a random point in the square extension of the square $\bar{w}$.

Mathematically, to turn the multilinear extension $\tilde{w}$ into a square extension $W$, we will simply partition the $m$ variables $x_1, \dots, x_m$ of $\tilde{w}$ into two parts, $(x_1, \dots, x_{m/2})$ and $(x_{m/2+1}, \dots, x_m)$, and treat each part as a single variable. That is, we can view any tuple $(x_1, \dots, x_{m/2}) \in \{ 0 , 1 \}^{m/2}$ as a number in $\mathbb{F}$ via an injective map $u : \{0,1\}^{m/2} \rightarrow \mathbb{F}$. It might be helpful for now to imagine $u$ as the map sending a binary representation $x_1, \dots x_{m/2}$ to its integer value, though later we will want a different $u$ to work over extension fields of $\mathbb{F}_2$. Our square encoding will be the $2$-variate polynomial $W : \mathbb{F} \times \mathbb{F} \rightarrow \mathbb{F}$ defined via $W(x,y) = \tilde{w}(u^{-1}(x), u^{-1}(y))$. Note that the original values of $\bar{w}$ are now located in the grid $[2^{m/2}] \times [2^{m/2}]$, and $W$ is the low degree extension of this square.

It turns out that as long as $u$ is a linear map, $\tilde{w}(\zeta)$ gets mapped to a random point in $\mathbb{F}^2$ via the identity $$\tilde{w}(\zeta_1, \dots, \zeta_m) = W(u(\zeta_1, \dots, \zeta_{m/2}), u(\zeta_{m/2+1}, \dots, \zeta_m)).$$ So now our task is simply to commit to $W$, in a way that allows the verifier to learn a random point $W(\zeta_1, \zeta_2)$.

The Commitment

The prover begins with some values $\bar{w}$ arranged into a $2^{m/2} \times 2^{m/2}$ square. She will first compute the horizontal encoding of $\bar{w}$ as given by $W$, namely the values

$W(1,1)$	$W(1,2)$	$\dots$	$W(1, 2^{m/2})$	$W(1, \alpha_1)$	$\dots$	$W(1, \alpha_{n-2^{m/2}})$
$W(2,1)$	$W(2,2)$	$\dots$	$W(2, 2^{m/2})$	$W(2, \alpha_1)$	$\dots$	$W(2, \alpha_{n-2^{m/2}})$
$\vdots$	$\vdots$	$\ddots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$
$W(2^{m/2},1)$	$W(2^{m/2},2)$	$\dots$	$W(2^{m/2}, 2^{m/2})$	$W(2^{m/2}, \alpha_1)$	$\dots$	$W(2^{m/2}, \alpha_{n-2^{m/2}})$

Next, she will compute a Merkle commitment of this table. If you aren’t familiar with Merkle commitments, their key property is that you can open parts of the committed word without opening the entire string. So for our case, this means that the prover can later reveal a value $W(i, j)$ at a fraction of the cost of revealing the entire table. This Merkle hash will be the commitment to our polynomial $W$.

Now, we have to answer two questions. First, how does the verifier know that the prover gave him a good, well formed commitment and not just some random string? And second, how can the verifier learn a value $W(\zeta_1, \zeta_2)$?

Testing

For the first question, the verifier simply wants to check that the prover’s committed to a table where each row is a low degree polynomial. He’ll ask the prover for a random linear combination of the rows, which, if the prover were honest, would be a low degree polynomial. To save a bit on communication, the prover can simply send him the values of the sum on the first $2^{m/2}$ columns, which uniquely determines the rest of the low degree polynomial. The verifier also needs to check that the received low degree polynomial is in fact the random linear combination he asked for. To do this, he will spot check the claimed linear combination by asking for the values of the rows at a few random columns $\zeta_2 \in \mathbb{F}$ and checking them with the value of the claimed linear combination at $\zeta_2$. This ensures that the prover is actually giving the verifier the correct linear combination of the rows.

Why is this test good? It turns out that there’s a property of codes known as proximity testing which essentially states that if any of the committed rows are far from the code space, then a random linear combination will also be far from the code space with high probability. This means that if any of the rows aren’t low degree polynomials (or at least close to one), then their sum can’t possibly be the claimed low degree polynomial, so some of the spot checks should fail.

Evaluation

The second question is: how can the verifier evaluate $W(\zeta_1, \zeta_2)$? It turns out he can do this the same way that testing works. He’ll ask for the linear combination of the rows given by $\zeta_1$, check consistency with the Merkle commitment, and then can simply take the $\zeta_2$‘th value of the linear combination.

The Binius Polynomial Commitment

So far, we’ve described a polynomial commitment that works over large fields $\mathbb{F}$. In particular, each of the entries in each row and column is a field element. Even if the data values $\bar{w}$ are binary values, they are treated and stored as (many bit) field elements, which can result in huge constant overhead in SNARK size. The innovation of the Binius polynomial commitment is the ability to work with bit values, without having to embed the bits in large fields first.

The key idea in the Binius commitment is the following: We can save representation overhead by batching bits into field elements. Already, a field element requires $\log |\mathbb{F}|$ bits to represent: why not have these $\log |\mathbb{F}|$ bits be the binary bits we were trying to encode? Specifically, let us group the $2^{m/2}$ bits in each row into $2^{m/2}/|\log \mathbb{F}|$ groups of size $\log |\mathbb{F}|$, view each group as a single field element (so now we have a $2^{m/2} \times \frac{2^{m/2}}{\log |\mathbb{F}|}$ table of field elements), and then perform the encoding over this new table.

Testing and evaluation will still operate as before: the verifier will ask the prover for a linear combination of the rows, and then will check consistency via spot checks. This ensures that the commitment is to a well formed table of field elements where each row is a low degree polynomial.

However, for evaluation, we need to actually evaluate a given linear combination of the bits, not of the field elements. Currently, testing and evaluation are over field elements, that is, the verifier asks for a random linear combination of the rows in field element form. Instead, we need the verifier to be able to ask for any linear combination of the rows in bit form that it chooses.

Let us elaborate a bit on exactly what we need. At the end of the IOP, the verifier is looking to learn a given linear combination of $\bar{w}$. This linear combination is given by two sets of coefficients, $\zeta_1$ and $\zeta_2$. The first set of coefficients $\zeta_1 \in \mathbb{F}^{2^{m/2}}$ tells how to sum the rows of bits to get a row of field elements, and $\zeta_2 \in \mathbb{F}^{2^{m/2}}$ tells how to sum the field elements within the row sum. If we could compute the $\zeta_1$ row sum, then computing the final answer is straightforward. Unfortunately, since we’ve batched the bits into field elements, taking a linear combination of the rows could scramble the bits making up each field element, so that nowhere can we read the $\zeta_1$ sum of the bits in each row.

The Tower Field

The answer, it turns out, is to use a special field $T$ that’s keeps its component bits in the same order under addition. This field is known as the tower field, and has order $2^{2^t}$ for some $t \in \mathbb{N}$. It is defined inductively as follows.

• $T_0$ is simply $\mathbb{F}_2$, and $\alpha_1 = 1$.
• $T_{i}$ is $T_{i-1}[\alpha_{i}]$, where $\alpha_{i}$ is the root of $x^2 = x + \alpha_{i-1}$, which is irreducible in $T_{i-1}$.

It is not hard to check that the size of $T_t$ is $2^{2^t}$, and that a $\mathbb{F}_2$-basis of $T_t$ consists of the $2^t$ elements

$$\left\{ \prod_{j \in S} \alpha_j \right\}_{S \subseteq [t]}.$$

For instance, an $\mathbb{F}_2$ basis of $T_3$ is given by the $8$ elements

$$1,~\alpha_1,~\alpha_2,~\alpha_1\alpha_2,~\alpha_3,~ \alpha_1\alpha_3,~\alpha_2\alpha_3,~\alpha_1\alpha_2\alpha_3.$$

This basis gives us a natural way batch bits into field elements, by regarding a collection of $2^t$ bits as the coefficients of this basis. We claim this field embedding $u$ solves our problems. Consider two field elements given by bits $\{ b_S \}_{S \subseteq [t]}$ and $\{ b'_S \}_{S \subseteq [t]}$. Then their sum equals $\{ b_S \oplus b'_S \}_{S \subseteq [t]}$ and respects the mod $2$ behavior of each of the bits. So in particular, if we take any $\mathbb{F}_2$ linear combination of the rows of our table, we get the same result whether we consider the rows as consisting of bits or field elements.

But, you say, didn’t the verifier want a $\mathbb{F}$-linear combination of the rows of bits, not just a $\mathbb{F}_2$-combination? That’s right, and we’ll solve this problem by again referring to the special properties of the tower field. Because $T_{t}$ has a $\mathbb{F}_2$ basis, the verifier simply has to learn all $2^{t}$ coefficients of this basis, each of which is a $\mathbb{F}_2$ linear combination of the rows. Then, using these $2^{t}$ linear combinations, the verifier can reconstruct what our row sum of field elements is supposed to be, sum them via $\zeta_2$, and obtain the desired linear combination of $\bar{w}$!

Testing and Evaluation

To summarize, the verifier will ask the prover for $2^{t}$ $\mathbb{F}_2$ linear combinations of the rows. In the case of testing, these linear combinations will be random, but in the case of evaluation, these linear combinations will be that obtained from the bit decomposition of $\zeta_1$ under the basis we described above. Then, once the prover gives the requested sums, the verifier will spot check the sums on a few randomly selected columns to verify that the given sums correspond to the committed bits. Finally, in the case of evaluation, the verifier can reconstruct the $\zeta_1$-row sum by summing the received rows over the $T_{t}$ basis, then compute the $\zeta_2$ sum of the resulting row.

Complexity

Finally, we discuss the complexity parameters of the polynomial commitment. Let us say that the data $\bar{w}$ is size $N = 2^m$ bits long, and that $\log \mathbb{|F|} \leq Cm$. (For example, we could take $\mathbb{F}$ to be the smallest field in the tower with at least $N$ elements.)

• The polynomial commitment is simply the Merkle commitment to the table, whose size is a constant (the security parameter $\lambda$).
• Opening to a certain linear combination of $\bar{w}$ requires $\sqrt{N} \cdot \log |\mathbb{F}|$ bits for the prover to send the verifier the row sums, along with $O(\frac{|\mathbb{F}|}{\Delta}) \cdot \log |\mathbb{F}| \cdot \lambda$ bits to perform the spot checks, where $\Delta$ is the distance of the polynomial code obtained via the low degree extension of the row. Altogether, the communication complexity when $|\mathbb{F}| = C \sqrt{N}$ is $\tilde{O}(\sqrt{N})$. The verifier’s computational complexity is similar.
• Finally, the prover’s computational complexity is dominated by the time it takes to compute the row extensions of the grid. For the Reed-Solomon (polynomial extension) code, this encoding takes $O(\sqrt{N} \log N)$ per row, for a total computational cost of $O(N \log N)$. One could also consider a linear time encodable code as Brakedown did originally, however, all known linear time encodable codes are highly inefficient to encode in practice, and polynomial codes seem to offer practical advantages.