Combined Protocol

Here, we put the previous two pages together. Indeed, we've already seen that $p[x] \cdot q[x] = 2^{64} \cdot \text{hi}[x] + \text{lo}[x]$ holds as integers if and only if $\big(g^{p[x]}\big)^{q[x]} \stackrel{?}= \big( g^{2^{64}} \big)^{\text{hi}[x]} \cdot g^{\text{lo}[x]}$, where $g \in \mathbb{F}_{2^{128}}^*$ is a multiplicative generator (up to an exceptional case that we can manually rule out). Moreover, we've seen how to multilinearize the exponentiation operation. It remains just to put these parts together.

We write $\widehat{p}(\widehat{I}, X)$, $\widehat{q}(\widehat{I}, X)$, $\widehat{\text{lo}}(\widehat{I}, X)$, and $\widehat{\text{hi}}(\widehat{I}, X)$ for the oblong-multilinearizations of the prover's constraint arrays $p$, $q$, $\text{lo}$ and $\text{hi}$. Our goal will be to reduce the question of the satisfaction of the prover's MUL constraints to evaluation claims these oblong-multilinearized constraint arrays. Evaluation claims of this latter form are exactly what our shift reduction is designed to assess. In fact, we moreover need all of the evaluation claims to pertain to the same evaluation point. This requirement will make things a bit tricky below.

Some Preparation

We write $G(X_0, \ldots , X_{\ell_\text{mul} - 1})$ for the constant multilinear that equals $g$ everywhere, and $G_{64}(X_0, \ldots , X_{\ell_\text{mul} - 1})$ for the constant multilinear that equals $g^{2^{64}}$ everywhere.

For each pair consisting of a base multilinear $\widetilde{V}(X)$ and an exponent oblong-multilinear $\widehat{z}(\widehat{I}, X)$, the exponent protocol yields "query access" to the virtual multilinear $\widetilde{W}(X)$, defined pointwise on the cube as $V(x)^{z[x]}$ for each $x \in \mathcal{B}_{\ell_\text{mul}}$. The prover prepares for four executions of that protocol, preparing four virtual multilinears:

• using the base $G$ and the exponent $\widehat{p}(\widehat{I}, X)$, obtain the exponentiation $\widetilde{P}(X)$.
• using the base $\widetilde{P}(X)$ and the exponent $\widehat{q}(\widehat{I}, X)$, obtain the exponentiation $\widetilde{Q}(X)$.
• using the base $G$ and the exponent $\widehat{\text{lo}}(\widehat{I}, X)$, obtain the exponentiation $\widetilde{\text{LO}}(X)$.
• using the base $G_{64}$ and the exponent $\widehat{\text{hi}}(\widehat{I}, X)$, obtain the exponentiation $\widetilde{\text{HI}}(X)$.

We note first that for each $x \in \mathcal{B}_{\ell_\text{mul}}$,

and

both hold. For this reason, our claim of interest, whereby $\big(g^{p[x]}\big)^{q[x]} \stackrel{?}= \big( g^{2^{64}} \big)^{\text{hi}[x]} \cdot g^{\text{lo}[x]}$ holds for each $x \in \mathcal{B}_{\ell_\text{mul}}$, is equivalent to that whereby

does.

The Protocol

Here is the protocol. The basic idea is to start with the vanishing identity above, run a zerocheck on it, and then unroll everything. But since we need the final evaluation claims on $\widehat{p}(\widehat{I}, X)$, $\widehat{q}(\widehat{I}, X)$, $\widehat{\text{lo}}(\widehat{I}, X)$, and $\widehat{\text{hi}}(\widehat{I}, X)$ to pertain to the same evaluation point, we need to be a bit tricky. Below, we sketch a slightly simplified version of the protocol that we actually run.

• by running a standard zerocheck on the virtual multivariate $\widetilde{\text{LO}}(X) \cdot \widetilde{\text{HI}}(X) - \widetilde{Q}(X)$, the parties reduce the initial claim above to evaluation claims, say $s_\text{LO} \stackrel{?}= \widetilde{\text{LO}}(r_0)$, $s_\text{HI} \stackrel{?}= \widetilde{\text{HI}}(r_0)$ and $s_Q \stackrel{?}= \widetilde{Q}(r_0)$.

• on the root claim $s_Q \stackrel{?}= \widetilde{Q}(r_0)$, the parties run just the GKR and Frobenius steps of the exponentiation protocol. In this way, they reduce that claim to further claims, now of the form $s_P \stackrel{?}= \widetilde{P}(r_1)$ and $s_{q, i} \stackrel{?}= \widehat{q}(\widehat{i}, r_1)$ for $i \in \{0, \ldots , 63\}$, say.

• now, in a batched way, the parties simultaneously run just the respective GKR phases associated with the three root claims $s_P \stackrel{?}= \widetilde{P}(r_1)$, $s_\text{LO} \stackrel{?}= \widetilde{\text{LO}}(r_0)$, and $s_\text{HI} \stackrel{?}= \widetilde{\text{HI}}(r_0)$. In this way, they get further intermediate claims, pertaining to $\widehat{p}(\widehat{I}, X)$, $\widehat{\text{lo}}(\widehat{I}, X)$ and $\widehat{\text{hi}}(\widehat{I}, X)$.

• in a batched way, the parties now run four $\ell_\text{mul}$-round sumchecks:

  • the respective Frobenius phases associated with $\widehat{p}(\widehat{I}, X)$, $\widehat{\text{lo}}(\widehat{I}, X)$ and $\widehat{\text{hi}}(\widehat{I}, X)$, and
  • a separate, MLE-rerandomization sumcheck that reduces the evaluation claims $s_{q, i} \stackrel{?}= \widehat{q}(\widehat{i}, r_1)$ for $i \in \{0, \ldots , 63\}$ above to similar claims at a completely fresh point.

  
  in this way, the parties obtain evaluation claims of the form $\widehat{p}(\widehat{i}, r'_x)$, $\widehat{q}(\widehat{i}, r'_x)$, $\widehat{\text{lo}}(\widehat{i}, r'_x)$, and $\widehat{\text{hi}}(\widehat{i}, r'_x)$, for all $i \in \{0, \ldots, 63\}$, i.e. for which the point $r'_x$ is the same everywhere.

• the parties now run the oblong-multilinearization step just once across all four oblong-multilinears. In this way, they obtain evaluation claims of the form $\widehat{p}(r_{\widehat{i}}, r'_x)$, $\widehat{q}(r_{\widehat{i}}, r'_x)$, $\widehat{\text{lo}}(r_{\widehat{i}}, r'_x)$, and $\widehat{\text{hi}}(r_{\widehat{i}}, r'_x)$, i.e. for which the values $r_{\widehat{i}}$ and $r'_x$ are the same in all four claims.

This completes our treatment of the MUL reduction.