The Procedure

We've already explained in rough detail the idea of error-correcting codes, as well as our most important particular code, the binary-field Reed–Solomon code. At this point, we're ready to describe Binius's multilinear polynomial commitment procedure.

Again, the problem is to describe what we should do to a multilinear polynomial in order to commit it. To fix notation, we again pick an integer $\ell \geq 0$ and a huge tower field $\mathcal{T}_\tau$. Our input thus will be an $\ell$-variate multilinear $t(X_0, \ldots , X_{\ell - 1}) \in \mathcal{T}_\tau[X_0, \ldots , X_{\ell - 1}]^{\preceq 1}$. (We will describe how to commit to small-field polynomials—or that is, how to reduce the small-field case to the large-field case—shortly.)

We're also going to pick a rate parameter $\mathcal{R} \geq 1$, a positive integer. We can think of $\mathcal{R}$ as a "blowup factor" parameter: during the prover's commitment phase, he will "stretch" his polynomial $2^{\mathcal{R}}$-fold. Thus, if $\mathcal{R} = 1$, it will double in length; if $\mathcal{R} = 2$, it will quadruple in length, and so on. As we hinted at earlier, our rate parameter $\mathcal{R}$ controls a prover–verifier tradeoff. The higher $\mathcal{R}$ gets, the costlier things get for the prover (because the code's rate gets worse), while the cheaper they get for the verifier (because the code's distance gets better). The real-life selection of $\mathcal{R}$ is quite complicated (the verifier's returns on higher $\mathcal{R}$ diminish very quickly, for example).

Finally, we fix a domain $S \subset \mathcal{T}_\tau$ of size $2^{\ell + \mathcal{R}}$. In fact, as usual, we will set $S \coloneqq \left< \beta_0, \ldots , \beta_{\ell + \mathcal{R} - 1} \right>$, where $(\beta_0, \ldots , \beta_{2^\tau - 1})$ is the $\mathbb{F}_2$-basis of $\mathcal{T}_\tau$ we used to construct the novel polynomial basis.

The Steps

There are just a few short steps we need to do to our input $t(X_0, \ldots , X_{\ell - 1})$.

• We first take our input $t(X_0, \ldots , X_{\ell - 1})$'s coordinates in the multilinear Lagrange basis, or in other words its evaluations $\left( t(v) \right)_{v \in \mathcal{B}_\ell}$ over the $\ell$-dimensional cube. (In practice, $t$ will be represented concretely this way at rest to begin with! So this is a no-op.)
• We're now do a flattening step. We already know how to identify $\mathcal{B}_\ell$ with the flat, ordered integer range $\{0, \ldots, 2^\ell - 1\}$: we use the little-endian lexicographic identification $v \mapsto \sum_{i = 0}^{\ell - 1} 2^i \cdot v_i$. Using this identification, we flatten $t$'s coefficients into a list $(t_0, \ldots , t_{2^\ell - 1})$—indeed, we just need to set $t_{\{v\}} \coloneqq t(v)$.
• We use this flattened list as the coefficients of a univariate polynomial in the novel polynomial basis. That is, we write $P(X) \coloneqq t_0 + t_1 \cdot X_1(X) + \cdots + t_{2^\ell - 1} \cdot X_{2^\ell - 1}(X)$.
• We then evaluate this polynomial $P(X)$ over our domain $S \subset \mathcal{T}_\tau$. Using the additive NTT, this key step can be performed in quasilinear—that is, $\Theta(\ell \cdot 2^{\ell + \mathcal{R}})$—time. In this way, we get a long list, say $(b_0, \ldots , b_{2^{\ell + \mathcal{R}} - 1})$; this list can be viewed as constituting a function $f : S \to \mathcal{T}_\tau$.
• The prover submits the entire list $(b_0, \ldots , b_{2^{\ell + \mathcal{R}}})$ to the string oracle, which "sits on it" and notifies the verifier of receipt.

At this point, the commitment is complete. In the last step above, we exploit our use of the string oracle, an abstract machine present in the IOP model (by definition of that model). In practice, the prover will rather compute a Merkle commitment to this list, and send the resulting Merkle root to the verifier.