Mathematizing Constraint Arrays

While defining both our AND and MUL constraints, we made use of "constraint arrays", arrays $z$ whose elements take the form

for $x \in \{0, \ldots , n_\text{cons} - 1\}$. Here, $n_\text{cons}$ is the total number of constraints (either AND or MUL), and each $L^z_x$ is a list of shifted value indices. We recall that, by definition, each shifted value index $(y, \text{op}, s) \in L^z_x$ is an element of the set $\{0, \ldots , n_\text{words} - 1\} \times \{ \mathsf{sll}, \mathsf{srl}, \mathsf{sra}\} \times \{0, \ldots , 63\}$.

Both our AND and MUL reductions closed out by outputting evaluation claims on the oblong-multilinearizations of these constraint arrays. In order to assess validity of these claims, we need to connect them mathematically to the witness.

By definition, the oblong-multilinearization of the array $z$ above is the unique oblong-multilinear polynomial

for which

holds for each $i \in \mathcal{B}_6$ and each $x \in \mathcal{B}_{\ell_\text{cons}}$. Our task now is to express this oblong-multilinearization $\widehat{z}(\widehat{I}, X)$ as a polynomial in terms of $\widetilde{w}(J, Y)$, the multilinearization of the prover's witness. The initial definition of $z[x]$ above suggests that this should be possible; on the other hand, making everything algebraic is hard. We will have to put our shifted witness polynomials to use.

Later, we will undertake the actual task of reducing a claim on $\widehat{z}(\widehat{I}, X)$ to one on $\widetilde{w}(J, Y)$.

The Constraint Matrices

We thus fix $\left( L_x^z \right)_{x = 0}^{n_\text{cons} - 1}$, a list-of-lists of shifted value indices.

We first re-express this data in matrix form. For each of the three shift types $\text{op} \in \{\mathsf{sll}, \mathsf{srl}, \mathsf{sra}\}$, we define $n_\text{cons} \times n_\text{words} \times 64$ "matrix" $Z_{\text{cons}, \text{op}}$—so, $Z_{\text{cons}, \text{op}}$ is three-dimensional—by declaring that, for each $x \in \{0, \ldots , n_\text{cons} - 1\}$, $y \in \{0, \ldots , n_\text{words} - 1\}$, and $s \in \{0, \ldots , 63\}$,

if and only if the $x$^th constraint triple $L^z_x$ contains the triple $(y, \text{op}, s)$.

Thus, we get 3 three-dimensional matrices, namely $Z_{\text{cons}, \text{op}}$ for each of the three $\text{op}$. Note that we are implicitly assuming there are no duplicate shifted value indices in any of the lists $L^z_x$. (Of course, having duplicates would be pointless, since they would get XOR'd out.)

Matrix Expressions

We now express each element $z[x]$ of the constraint array $z$, for $x \in \{0, \ldots , n_\text{cons} - 1\}$, as a matrix expression. Here, we use our shifted witness functions $\textsf{shift}_\text{op}(w)(y, s)$. For each $x \in \{0, \ldots , n_\text{cons} - 1\}$, we claim that:

We recall that $z[x] \coloneqq \bigoplus_{(y, \text{op}, s) \in L^z_x} \text{op}(w[y], s)$ by definition; the equality above follows essentially from the definition of the matrices $Z_{\text{cons}, \text{op}}$.

Multilinearizing

Now, we take multilinear extensions. At this point, we assume that $n_\text{cons} = 2^{\ell_\text{cons}}$ and $n_\text{words} = 2^{\ell_\text{words}}$ are both powers of 2.

By identifying the matrices $Z_{\text{cons}, \text{op}}$ with their multilinear extensions, we can view them now as multilinear polynomials $\widetilde{Z}_{\text{cons}, \text{op}}(X, Y, S)$, each with coefficients in $\mathbb{F}_2$, and of $\ell_\text{cons} + \ell_\text{words} + 6$ variables. Similarly, we have already seen that the shifted witness functions $\textsf{shift}_\text{op}(w)(y, s)$ can be multilinearized. Multilinearizing everything, we obtain a multilinear polynomial, on $6 + \ell_\text{cons}$ variables, $\mathbb{F}_2$-valued on the cube:

It's again true essentially by construction that, for each $i \in \mathcal{B}_6$ and $x \in \mathcal{B}_{\ell_\text{cons}}$, $\widetilde{z}(i, x) = z[x]_i$.

Using Shift Indicators

We showed already that the shifted witness polynomials $\widetilde{\textsf{shift}}_\text{op}(w)(I, y, S)$ can themselves be expressed using shift indicators. Unrolling that step now, we obtain the following equivalent expression for the multilinear $\widetilde{z}(I, X)$ defined above:

These are identically equal (as polynomials) to the above expressions we gave; they just unroll the shifted witness polynomials and rearrange the sums.

Oblong-Multilinearizing

Now, we apply the standard oblong-multilinearization construction to $\widetilde{z}(I, X)$. In this way, we obtain the expression:

The polynomial $\widehat{z}(\widehat{I}, X)$ obtained in this way indeed yields the one we set out to obtain above. Indeed, by the standard property of the oblong-multilinearization transformation, for each $i \in \mathcal{B}_6$ and each $x \in \mathcal{B}_{\ell_\text{cons}}$, $\widehat{z}(\widehat{i}, x) = \widetilde{z}(i, x)$; on the other hand, we have already seen that that latter quantity equals $z[x]_i$. Thus,

holds for each $i \in \mathcal{B}_6$ and each $x \in \mathcal{B}_{\ell_\text{cons}}$, a condition that uniquely characterizes the polynomial $\widehat{z}(\widehat{I}, X)$.