Oblong-Multilinearization

We've already discussed multilinear polynomials. Here, we discuss a variant of that idea.

We fix nonnegative integer parameters $k$ and $\ell$. We fix a $k$-dimensional $\mathbb{F}_2$-linear subspace $D \subset \mathbb{F}_{2^{128}}$. If we pick an $\mathbb{F}_2$-basis $(\zeta_0, \ldots , \zeta_{k - 1})$ of $D$, then we can identify $\mathcal{B}_k \cong D$; indeed, it's enough to send

We will write $\widehat{i} \in D$ for this latter element.

We now fix a $k + \ell$-variate multilinear:

over $\mathbb{F}_2$. We are going to create a further polynomial, called

in $1 + \ell$ variables, such that:

• $\widehat{t}(\widehat{I}, X_0, \ldots , X_{\ell - 1})$'s restriction to $D \times \mathcal{B}_\ell$ equals $t(I_0, \ldots , I_{k - 1}, X_0, \ldots , X_{\ell - 1})$'s restriction to $\mathcal{B}_k \times \mathcal{B}_\ell$; i.e., for each $i \in \mathcal{B}_k$ and $x \in \mathcal{B}_\ell$, $t(i, x) = \widehat{t}(\widehat{i}, x)$.
• $\widehat{t}(\widehat{I}, X_0, \ldots , X_{\ell - 1})$ is "low-degree"; that is, it's of degree less than $2^k$ in $\widehat{I}$ and of degree less than or equal to 1 in each further variable.

We will call $\widehat{t}(\widehat{I}, X_0, \ldots , X_{\ell - 1})$ the oblong-multilinearization of $t(I_0, \ldots , I_{k - 1}, X_0, \ldots , X_{\ell - 1})$. In general, we will use "hats" to signify variables that take values along the "long" axis of the domain.

Existence and Uniqueness

The oblong-multilinearization $\widehat{t}(\widehat{I}, X_0, \ldots , X_{\ell - 1})$ exists and is unique, essentially for reasons similar to ones we've already seen. As before, it's enough to prove existence, by a dimension count.

We write $\delta_D$ for the bivariate polynomial, of individual degree less than $2^k$ in both variables, whose restriction to $D \times D$ is the equality indicator function. We claim without proof that this thing exists and is unique. Note that $\delta_D$'s partial specializations within $D$ recover the usual univariate Lagrange interpolation polynomials. That is, for each $\widehat{i} \in D$, $\delta_D(\widehat{I}, \widehat{i})$ is the unique univariate Lagrange polynomial of degree less than $2^k$ whose restriction to $D$ equals 1 exactly at $\widehat{i}$ and 0 elsewhere on $D$.

To construct $\widehat{t}(\widehat{I}, X_0, \ldots , X_{\ell - 1})$, we use $\delta_D$. We claim that the construction:

gives us what we want. We need to check that $\widehat{t}(\widehat{I}, X_0, \ldots , X_{\ell - 1})$ has the right degrees both in $\widehat{I}$ and in the variables $X_0, \ldots , X_{\ell - 1}$ (it does) and that its restriction to $D \times \mathcal{B}_\ell$ takes the right values (it does).

Partial Specialization

We will also encounter the following problem a few times. Given a multilinear $t(I_0, \ldots , I_{k - 1}, X_0, \ldots , X_{\ell - 1})$ and its oblong-multilinearization $\widehat{t}(\widehat{I}, X_0, \ldots , X_{\ell - 1})$ as above, and given some scalar $r_{\widehat{i}} \in \mathbb{F}_{2^{128}}$, the partial specialization $\widehat{t}(r_{\widehat{i}}, X_0, \ldots , X_{\ell - 1})$ is an $\ell$-variate multilinear. How can we compute its table of values on the cube $\mathcal{B}_\ell$?

To answer this question, we just need to look at the expression for $\widehat{t}(\widehat{I}, X_0, \ldots , X_{\ell - 1})$ above. It follows from that expression that, for each $x \in \mathcal{B}_\ell$,

This fact suggests the following algorithm.

• precompute the list of values $\left( \delta_D(r_{\widehat{i}}, \widehat{i}) \right)_{i \in \mathcal{B}_6}$.
• initialize an empty, length-$2^\ell$ array $\mathsf{t}$ containing $\mathbb{F}_{2^{128}}$-elements.
• for each $x \in \{0, \ldots , n_\text{and} - 1\}$ do in parallel:
  • let $\mathsf{t}[x] \coloneqq \sum_{i \in \mathcal{B}_k} t(i_0, \ldots , i_{k - 1}, x_0, \ldots , x_{\ell - 1}) \cdot \delta_D(r_{\widehat{i}}, \widehat{i})$.
• return $\mathsf{t}$.

The array $\mathsf{t}$ returned by the above algorithm yields the table of values on $\mathcal{B}_\ell$ of $\widehat{t}(r_{\widehat{i}}, X_0, \ldots , X_{\ell - 1})$, as desired. Each instance of the inner bulletpoint is actually a subset sum of $\left( \delta_D(r_{\widehat{i}}, \widehat{i}) \right)_{i \in \mathcal{B}_6}$, since the coefficients of the sum expression are bits.

The computation of $\left( \delta_D(r_{\widehat{i}}, \widehat{i}) \right)_{i \in \mathcal{B}_6}$ above turns out to be a standard subroutine in Lagrange interpolation, and can be carried out extremely efficiently (we use a "division-free" variant of the Barycentric weights computation algorithm).

Evaluation

We pick an extension field, say $\mathbb{F}_{2^{128}}$, and write $(r_{\widehat{i}}, r_x)$ for an arbitrary element of $\mathbb{F}_{2^{128}} \times \mathbb{F}_{2^{128}}^\ell$. We discuss how to compute the full evaluation $\widehat{t}(r_{\widehat{i}}, r_x)$, given query access to $\widehat{t}(\widehat{I}, X_0, \ldots , X_{\ell - 1})$.

Unwinding what that evaluation means, we get:

Interestingly, this is a problem of Lagrange extrapolation: this value is exactly

where $P_{r_x}(\widehat{I})$ is the unique univariate polynomial of degree less than $2^k$ whose values on $D$ satisfy $P_{r_x}(\widehat{i}) = t(i, r_x)$ for each $i \in \mathcal{B}_6$. There are good algorithms for this problem, provided that the verifier is willing to read or obtain all $2^k$ values $t(i, r_x)$ and do $O(2^k)$ work. In practice, we assume that $k$ is so small that the verifier is willing to do $O(2^k)$ work.

If the verifier is willing to do $O(2^k)$ work but would rather evaluate $t(I, X)$ just once, the verifier can reduce the above sum—by running the sumcheck for 6 rounds—to two claims. One will be about the value of $t(r_i, r_x)$, where $r_i$ is sampled during the sumcheck. The other will be one about the value of $\delta_{D, r_{\widehat{i}}}(r_i)$, where we write $\delta_{D, r_{\widehat{i}}}$ for the multilinear whose values on $\mathcal{B}_6$ satisfy $\delta_{D, r_{\widehat{i}}}(i) = \delta_D(r_{\widehat{i}}, \widehat{i})$ for each $i \in \mathcal{B}_6$; that is, it's the multilinear whose values on the cube are those that the univariate Lagrange basis polynomials respectively take at $r_{\widehat{i}}$. The verifier can evaluate this latter quantity himself, again using Lagrange extrapolation to $r_{\widehat{i}}$, now with coefficients $\left( \widetilde{\texttt{eq}}(r_i, i) \right)_{i \in \mathcal{B}_6}$. We are not aware of a way of evaluating this that takes less than $O(2^k)$ time.

If the verifier wants to stay fully succinct in $2^k$—i.e., polynomial in $k$—there are ways to achieve this, based on ideas of Haböck (unpublished) and Papini and Haböck [PH23]. We survey those ideas here, though we don't use them in Binius64.

Practical Parameterization

In all of our applications in this site, we will use $k = 6$. We thus let $k = 6$ once and for all, so that $D \subset \mathbb{F}_{2^{128}}$ is a 6-dimensional $\mathbb{F}_2$-linear subspace. We will as above identify $\mathcal{B}_6 \cong D$ by basis combination, by sending $i \mapsto \widehat{i} \coloneqq i_0 \cdot \zeta_0 + \cdots + i_5 \cdot \zeta_5$.