pub fn verify<F, C>(
n_vars: usize,
channel: &mut C,
) -> Result<BinMulOutput<C::Elem>, Error>Expand description
Verify the binary-field multiplication check (BinMul) reduction.
The BinMul reduction proves the constraint $\widetilde{A}(x) \cdot \widetilde{B}(x) =
\widetilde{C}(x)$ for every $x$ on the boolean hypercube $\mathbb{B}\ell$ (where $\ell =$
n_vars), over the GHASH field $\mathbb{F}{2^{128}}$. Each field element is carried by a
(lo, hi) pair of 64-bit words via $\langle\langle z_{\textsf{lo}}, z_{\textsf{hi}}
\rangle\rangle = \sum_{i=0}^{63} z_{\textsf{lo},i} \cdot X^i + \sum_{i=0}^{63}
z_{\textsf{hi},i} \cdot X^{64+i}$, so $\widetilde{A}, \widetilde{B}, \widetilde{C}$ are the
$\mathbb{F}_{2^{128}}$-valued multilinears with those packed hypercube values.
ยงProtocol
- The verifier samples $r_z \in K^\ell$.
- The parties run an $\ell$-round MLE-check on $0 = \sum_x \textsf{eq}(r_z, x) \cdot
(\widetilde{A}(x) \cdot \widetilde{B}(x) - \widetilde{C}(x))$, yielding a challenge point
$r_x$ and a final target
eval. The composition $A \cdot B - C$ has degree 2; the eq factor is folded internally by the MLE-check. - The prover sends the six
Word::BITS-wide per-bit evaluation columns at $r_x$; the verifier recombines $\alpha_A = \sum_i \textsf{basis}(i) \cdot \widetilde{a}{\textsf{lo}}(r_x, i) + \textsf{basis}(64+i) \cdot \widetilde{a}{\textsf{hi}}(r_x, i)$ (and $\alpha_B, \alpha_C$ likewise), and checks $\textsf{eval} = \alpha_A \cdot \alpha_B - \alpha_C$.
The reduction outputs the six per-bit evaluation columns at the shared point $r_x$.