Skip to main content

verify

Function verify 

Source
pub fn verify<F, C>(
    n_vars: usize,
    channel: &mut C,
) -> Result<IntMulOutput<C::Elem>, Error>
where F: BinaryField, C: IOPVerifierChannel<F>, C::Elem: FieldOps<Scalar = F> + From<F>,
Expand description

Verify the integer multiplication check (IntMul) protocol.

The IntMul protocol is a reduction that checks a relation on four virtual multilinear polynomials: $\widetilde{a}, \widetilde{b}, \widetilde{c}{\textsf{lo}}, \widetilde{c}{\textsf{hi}}$. These multilinear polynomials are over $\mathbb{F}2$ and have $k + n$ variables. We write $a, b, c{\textsf{lo}}, c_{\textsf{hi}} \in \mathbb{F}_2^{n \times k}$ for their boolean hypercube evaluations. Let $\textsf{int}(M) \in \mathbb{N}^n$ map one of the four matrices, $M$, to a vector of their interpretations as a $k$-bit unsigned integer. That is, it embeds the $\mathbb{F}_2$ elements into $\mathbb{N}$ and multiplies by $(2^0, 2^1, \ldots, 2^{k-1})$.

§Protocol

The IntMul protocol reduces this relation to claims on the partial multilinear evaluations of $\widetilde{a}, \widetilde{b}, \widetilde{c}{\textsf{lo}}, \widetilde{c}{\textsf{hi}}$ at a common $n$-coordinate random evaluation point.

§Exponentiation identity

The core technique reduces integer multiplication to field arithmetic via exponentiation. Let $g$ be a generator of the multiplicative group of $\mathbb{F}{2^{2k}}$, which has order $2^{2k} - 1$. Then $\textsf{int}(a) \cdot \textsf{int}(b) = \textsf{int}(c{\textsf{hi}}) \cdot 2^k + \textsf{int}(c_{\textsf{lo}})$ over the integers is equivalent to

$$\widetilde{Q}(x) = \widetilde{\textsf{LO}}(x) \cdot \widetilde{\textsf{HI}}(x) \quad \forall x \in {0, 1}^n$$

where $\widetilde{Q}$ is obtained by exponentiating $g^{\widetilde{a}}$ by $\widetilde{b}$, $\widetilde{\textsf{LO}} = g^{\widetilde{c}{\textsf{lo}}}$, and $\widetilde{\textsf{HI}} = (g^{2^k})^{\widetilde{c}{\textsf{hi}}}$.

There is a wraparound edge case: when $a \cdot b = 0$, a malicious prover could set $c_{\textsf{hi}} | c_{\textsf{lo}} = 2^{2k} - 1$, which satisfies the exponentiation identity modulo $2^{2k} - 1$ but not over the integers. A parity check on the least significant bits ($a_0 \cdot b_0 = c_{\textsf{lo},0}$) rules this out.

§Phases

  • Phase 1 — GKR step on $\widetilde{Q}$: The verifier samples a random evaluation point $r$ and the prover sends the claimed evaluation $s = \widetilde{Q}(r)$. The parties run a GKR step ($k$-layer balanced binary tree of bivariate products) reducing $s$ to $2^k$ leaf claims $s’_{Q,i} = \widetilde{Q_i}(r’)$.

  • Phase 2 — Frobenius step: The verifier applies $\varphi^{-i}$ (inverse Frobenius) to each leaf claim, reducing degree-$2^i$ expressions to degree-1. This is a local verifier computation with no interaction.

  • Phase 3 — Batched Frobenius sumcheck + $\widetilde{\textsf{LO}} \cdot \widetilde{\textsf{HI}}$ product sumcheck: Two sumchecks batched into one: (a) The Frobenius-twisted selector sumcheck on the $\widetilde{Q_i}$ claims, reducing to claims on $\widetilde{b}$ exponent evaluations and the base $\widetilde{P}$ (i.e. $g^{\widetilde{a}}$). (b) The deferred product claim $s = \sum \textsf{eq}(r, x) \cdot \widetilde{\textsf{LO}}(x) \cdot \widetilde{\textsf{HI}}(x)$. This yields root claims on $\widetilde{P}$ (the $\widetilde{a}$ selector), $\widetilde{\textsf{LO}}$, $\widetilde{\textsf{HI}}$, plus $2^k$ exponent claims on $\widetilde{b}$. The verifier then samples a recombination point $r_I^b \in K^k$ and collapses the $2^k$ exponent claims into a single claim $\widetilde{b}(r_I^b, r) = \sum_i \textsf{eq}(r_I^b, i) \cdot \widetilde{b}(i, r)$, carried into Phases 4 and 5.

  • Phase 4 — GKR on $\widetilde{a}$, $\widetilde{c}{\textsf{lo}}$, $\widetilde{c}{\textsf{hi}}$, down to per-limb claims: Each exponent word splits into N_LIMBS limbs, so each of the three constant-base exponentiations factors as a product of N_LIMBS limb columns. A batched GKR product check over the three (depth-LOG_N_LIMBS) trees reduces the root claims to one evaluation claim per limb column at a shared content point.

  • Phase 5 — logup lookup + $\widetilde{b}$ rerandomization + parity check:* Limb column $(t, l)$ is the Frobenius power $\varphi^{ws}$ of the looked-up column $T[e_{t,l}(\cdot)]$ over the shared table $T\colon i \mapsto g^i$ of $2^w$ generator powers (where $w$ is the limb bit width). The per-limb claims are Frobenius-twisted onto $T$, batched to one stacked lookup claim, and reduced via committed logup* (Soukhanov25): the pushforward oracle is committed mid-protocol and its two opening relations returned to the caller, the second weighing it against the table’s succinct product-of-selects MLE, so the table needs no claim of its own; the index claim is bound to the per-bit output evals in a final batched sumcheck, together with (a) a single-claim rerandomization of the recombined $\widetilde{b}(r_I^b, \cdot)$ exponent claim from Phase 3 and (b) a zerocheck verifying $a_0 \cdot b_0 = c_{\textsf{lo},0}$ (least significant bits), ruling out the wraparound edge case.

§Output

The protocol outputs evaluation claims on $\widetilde{a}i$, $\widetilde{b}i$, $\widetilde{c}{\textsf{lo},i}$, $\widetilde{c}{\textsf{hi},i}$ (for $i \in {0, \ldots, 2^k - 1}$) at a common $n$-dimensional evaluation point. The claims are passed to the shift reduction; the logup* pushforward commitment carries its two relations into the channel inside phase 5.

§Parameters

  • n_vars: Number of variables in the row dimension — the $\log_2$ of the operand column length, which the prover zero-pads up to a power of two. The single-instance verifier passes $\lceil \log_2 n \rceil$ for $n$ IMUL constraints; the batched M4 verifier adds its $\log_2$ instance count.

The integer operands are fixed at the Word::BITS bit width.