The MUL Reduction

Here, we turn to our prover's MUL constraints. Our multiplication protocol is the second, large "entrypoint protocol" in Binius64. Like our AND reduction, our MUL reduction ingests the constraint system, and reduces the prover's satisfaction of these constraints—its MUL constraints, this time—to evaluation claims on oblong-multilinearizations of the prover's constraint arrays. Claims of this latter form are exactly what our shift reduction is designed to treat, so we defer the problem of the assessment of those evaluation claims' validity to that reduction. We note that the shift reduction is a common reduction target of both the AND and MUL reductions.

Our MUL reduction is mathematically involved, and builds on two key ideas. First, we work "in the exponent"; second, we use GKR. The content of this section can be viewed as an improved variant of an idea previously put out in an Irreducible blog post.

• Multiplying in the Exponent. Since $(g^r)^s = g^{r \cdot s}$ holds for each ring-element $g$ and each pair of integers $r$ and $s$, we can hope to reduce the condition $r \cdot s \stackrel{?}= t$ instead to the condition $(g^r)^s \stackrel{?}= g^t$. Here, we work out the details of this reduction.
• Exponentiating Multilinears. This is the GKR-based core of our multiplication reduction. Here, we show how to use GKR to evaluate the multilinear extension of a multilinear defined pointwise, on the cube, as the exponentiation of a variable base by a variable exponent.
• Combined Protocol. Here, we give an outline of our full multiplication protocol. The idea is mainly to combine the previous two parts, but there are details to work out.