Skip to main content

verify

Function verify 

Source
pub fn verify<F, C>(
    n_vars: usize,
    channel: &mut C,
) -> Result<BinMulOutput<C::Elem>, Error>
where F: BinaryField, C: IPVerifierChannel<F>, C::Elem: From<F>,
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

  1. The verifier samples $r_z \in K^\ell$.
  2. 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.
  3. 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$.