Batched Commitment

Committing to many, differently-sized polynomials

We now know how to commit to an $\ell$ -variate multilinear polynomial $t(X_0, \ldots, X_{\ell - 1})$ over the huge field $\mathcal{T}_\tau$ . In practical applications, on the other hand, we will have many different multilinear polynomials at play. For the sake of concrete efficiency, it is crucial that we commit to these in a batched way, which allows, in particular, these polynomials' respective evaluation protocols to also be batched.

Of course, we haven't even yet seen how to evaluate a single polynomial, let alone many. For now, then, we will just record our batched commitment procedure, acknowledging all the while that it will appear unmotivated. We will refer back to this page when we discuss evaluation (see in particular this page).

Things are a bit easier when the number $\mu$ of polynomials at hand is a power of 2, and all the polynomials are of the same number of variables $\ell$ . In real life, this assumption is too simplifying. Here, we fix an arbitrary number $n$ of polynomials $t_0, \ldots , t_{n - 1}$ , of arbitrary different sizes $\ell_0, \ldots, \ell_{n - 1}$ . We still require for now that these all be defined over the big field $\mathcal{T}_\tau$ (we will show shortly how this restriction gets relaxed).

The Steps

The simplest description of our batched scheme proceeds as follows:

Up to a reindexing, we freely assume that the input polynomials $t_0, \ldots , t_{n - 1}$ are sorted in such a way that $\ell_0 \geq \cdots \geq \ell_{n - 1}$ .
Collect the input polynomials' respective individual, flattened lists $\left( t_{0, i} \right)_{i = 0}^{2^{\ell_0} - 1}, \ldots , \left( t_{n - 1, i} \right)_{i = 0}^{2^{\ell_{n - 1}} - 1}$ of Lagrange coefficient vectors. Concatenate these lists into a huge master list, say $\left( t^*_i \right)_{i = 0}^{n^* - 1}$ .
By possibly padding this list with trailing zeros, extend it until it becomes of power-of-2 size—say, $\left( t^*_i \right)_{i = 0}^{2^{\ell^*} - 1}$ .
Commit to this list exactly as if it were a single polynomial on its own right. That is, additive-NTT the list $\left( t^*_i \right)_{i = 0}^{2^{\ell^*} - 1}$ , and send the result—a list of length $2^{\ell^* + \mathcal{R}}$ —to the string oracle.

A Piecewise Description

While the description above is valid and correct, it's a tiny bit unsatisfying, since it only works in the language of lists, as opposed to in the language of cubes (we have always worked across a duality between these two paradigms). As there usually tends to be, there is a geometric way of seeing what's going on. The $\ell^*$ -variate multilinear $t^*(X_0, \ldots , X_{\ell^* - 1})$ we just committed to above can be viewed as a piecewise multilinear, which takes the values that the individual polynomials $t_0, \ldots, t_{n - 1}$ respectively do on various subcubes of $\mathcal{B}_{\ell^*}$ . That is, on its "lexicographically smallest" $\ell_0$ -dimensional subcube (or "facet"), $t^*$ agrees identically with $t_0$ . On the next, $\ell_1$ -dimensional subcube, $t^*$ agrees with $t_1$ . And so on. If there are "missing" facets or vertices of the $\ell^*$ -cube still not yet covered when this process ends, we fill them with 0s.

As a concrete example, we can take $n = 3$ , and the size parameters

\begin{equation*}(\ell_0, \ell_1, \ell_2) = (2, 1, 0).\end{equation*}

Here, after concatenating all the lists, we get a master list of size $n^* = 2^2 + 2^1 + 2^0 = 7$ . We thus append one zero to get the power of two $8 = 2^3$ , and wind up with $\ell^* = 3$ . We thus have a cube's worth of values to fill.

To represent $t_0(X_0, X_1)$ 's values, we need a two-dimensional cube, or a square. We can thus write these values into the bottom face of our cube—i.e., where $X_2 = 0$ (and $X_0$ and $X_1$ are arbitrary). The 1-variate multilinear $t_1(X_0)$ takes up just a 1-dimensional cube, or an edge. We can inscribe these two values into the next available edge, which resides where $X_2 = 1$ and $X_1 = 0$ (and $X_0$ is arbitrary). Finally, the 0-variate multilinear takes just a 0-dimensional cube, or a point. We can inscribe its single value in the next available point, namely where $X_2 = 1$ , $X_1 = 1$ , and $X_0 = 0$ . Finally, we write a zero into the very final point, at $(1, 1, 1)$ .

Doing this gives us a mapping from $\mathcal{B}_{\ell^*} = \mathcal{B}_3$ to $\mathcal{T}_\tau$ , which is exactly the kind of thing we're prepared to commit to.