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.

• the verifier samples a random point $r \gets \mathbb{F}_{2^{128}}^{\ell_\text{mul}}$ and sends that point to the prover. the prover responds with a single value $s$, claimed to simultaneously equal $\widetilde{Q}(r)$ and $\sum_{x \in \mathcal{B}_{\ell_\text{mul}}} \widetilde{\texttt{eq}}(r, x) \cdot \widetilde{\text{LO}}(x) \cdot \widetilde{\text{HI}}(x)$ (the latter is the evaluation of the MLE of the pointwise product $\widetilde{\text{LO}}(x) \cdot \widetilde{\text{HI}}(x)$ at $r$).

• the parties begin by running just the GKR step on the first of these claims, namely $s \stackrel{?}= \widetilde{Q}(r)$. In this way, the verifier reduces that claim to further claims, now of the form $s'_{Q, i} \stackrel{?}= \widetilde{Q_i}(r')$, for $i \in \{0, \ldots , 63\}$.

• the parties now batch the following two $\ell_\text{mul}$-round sumchecks:

  • the Frobenius step associated with the intermediate claims $s'_{Q, i} \stackrel{?}= \widetilde{Q_i}(r')$ just above.
  • the initial sumcheck $s \stackrel{?}= \sum_{x \in \mathcal{B}_{\ell_\text{mul}}} \widetilde{\texttt{eq}}(r, x) \cdot \widetilde{\text{LO}}(x) \cdot \widetilde{\text{HI}}(x)$ deferred above.

  
  the parties thus obtain new root claims, now of the form $s_P \stackrel{?}= \widetilde{P}(r'')$, $s_\text{HI} \stackrel{?}= \widetilde{\text{HI}}(r'')$, and $s_\text{LO} \stackrel{?}= \widetilde{\text{LO}}(r'')$, as well as exponent evaluation claims, of the form $s_{q, i} \stackrel{?}= \widetilde{q_i}(r'')$, for $i \in \{0, \ldots , 63\}$.

• in a batched way, the parties now run just the respective GKR phases associated with the three root claims $s_P \stackrel{?}= \widetilde{P}(r'')$, $s_\text{HI} \stackrel{?}= \widetilde{\text{HI}}(r'')$, and $s_\text{LO} \stackrel{?}= \widetilde{\text{LO}}(r'')$. in the very last layer of that batched GKR step, the parties moreover splice in a rerandomization sumcheck on the above claims $s_{q, i} \stackrel{?}= \widetilde{q_i}(r'')$. in this way, the parties obtain further intermediate claims, now of the form $s'_{P, i} \stackrel{?}= \widetilde{P_i}(r_x)$, $s'_{\text{HI}, i} \stackrel{?}= \widetilde{\text{HI}_i}(r_x)$, and $s'_{\text{LO}, i} \stackrel{?}= \widetilde{\text{LO}_i}(r_x)$, as well as rerandomized exponent claims $s'_{q, i} \stackrel{?}= \widetilde{q_i}(r_x)$, for $i \in \{0, \ldots , 63\}$.

• the first three, "capital-letter" claims above pertain to exponents of fixed bases; we claim that the Frobenius steps attached to them can be skipped. In the case of $\widetilde{P_i}(r_x)$ for example, for each $i \in \{0, \ldots , 63\}$, our claim amounts to:

  $$\begin{align*} s'_{P, i} &\stackrel{?}= \sum_{x \in \mathcal{B}_{\ell_\text{mul}}} \widetilde{\texttt{eq}}(r_x, x) \cdot \left( 1 + p_i(x) \cdot \left( g^{2^i} - 1 \right) \right) \\ &= 1 + \left( g^{2^i} - 1 \right) \sum_{x \in \mathcal{B}_{\ell_\text{mul}}} \widetilde{\texttt{eq}}(r_x, x) \cdot p_i(x) \\ &= 1 + \left( g^{2^i} - 1 \right) \widetilde{p_i}(r_x). \end{align*}$$

  By performing some basic algebra, the verifier can thus locally reduce the above claims to further claims, now of the form $s_{p, i} \stackrel{?}= \widetilde{p_i}(r_x)$, $s_{\text{hi}, i} \stackrel{?}= \widetilde{\text{hi}_i}(r_x)$, and $s_{\text{lo}, i} \stackrel{?}= \widetilde{\text{LO}}(r_x)$, for $i \in \{0, \ldots , 63\}$. We now have claims on $\widetilde{p_i}(X)$, $\widetilde{q_i}(X)$, $\widetilde{\text{hi}_i}(X)$ and $\widetilde{\text{lo}_i}(X)$, for $i \in \{0, \ldots , 63\}$, all at the same point $r_x$.

• 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.