binius_verifier/protocols/binmul.rs
1// Copyright 2026 The Binius Developers
2
3use binius_core::word::Word;
4use binius_field::{BinaryField, field::FieldOps};
5use binius_ip::{channel::IPVerifierChannel, mlecheck, sumcheck::SumcheckOutput};
6use binius_math::inner_product::inner_product;
7
8use crate::{Error, protocols::rerand::OperandClaims};
9
10/// Output of the BinMul reduction.
11///
12/// The reduction proves the constraint $\widetilde{A}(x) \cdot \widetilde{B}(x) =
13/// \widetilde{C}(x)$ for every $x$ on the boolean hypercube $\mathbb{B}_\ell$, where each
14/// $\mathbb{F}_{2^{128}}$ element is carried by a `(lo, hi)` pair of 64-bit words. It reduces the
15/// constraint to per-bit evaluation claims on the six word columns at a common evaluation point
16/// `eval_point` ($r_x \in K^\ell$).
17///
18/// Each `*_evals` array holds `Word::BITS` per-bit evaluation claims $\widetilde{z}(r_x, i)$ for
19/// $i \in \{0, \ldots, 63\}$.
20#[derive(Clone, Debug, PartialEq, Eq)]
21pub struct BinMulOutput<F> {
22 pub eval_point: Vec<F>,
23 pub a_lo_evals: [F; Word::BITS],
24 pub a_hi_evals: [F; Word::BITS],
25 pub b_lo_evals: [F; Word::BITS],
26 pub b_hi_evals: [F; Word::BITS],
27 pub c_lo_evals: [F; Word::BITS],
28 pub c_hi_evals: [F; Word::BITS],
29}
30
31impl<F> BinMulOutput<F> {
32 /// The operand claims, in the shift operand order `[a_lo, a_hi, b_lo, b_hi, c_lo, c_hi]`.
33 pub fn operand_claims(&self) -> OperandClaims<'_, F> {
34 OperandClaims {
35 point: &self.eval_point,
36 columns: vec![
37 &self.a_lo_evals,
38 &self.a_hi_evals,
39 &self.b_lo_evals,
40 &self.b_hi_evals,
41 &self.c_lo_evals,
42 &self.c_hi_evals,
43 ],
44 }
45 }
46}
47
48/// Verify the binary-field multiplication check (BinMul) reduction.
49///
50/// The BinMul reduction proves the constraint $\widetilde{A}(x) \cdot \widetilde{B}(x) =
51/// \widetilde{C}(x)$ for every $x$ on the boolean hypercube $\mathbb{B}_\ell$ (where $\ell =$
52/// `n_vars`), over the GHASH field $\mathbb{F}_{2^{128}}$. Each field element is carried by a
53/// `(lo, hi)` pair of 64-bit words via $\langle\langle z_{\textsf{lo}}, z_{\textsf{hi}}
54/// \rangle\rangle = \sum_{i=0}^{63} z_{\textsf{lo},i} \cdot X^i + \sum_{i=0}^{63}
55/// z_{\textsf{hi},i} \cdot X^{64+i}$, so $\widetilde{A}, \widetilde{B}, \widetilde{C}$ are the
56/// $\mathbb{F}_{2^{128}}$-valued multilinears with those packed hypercube values.
57///
58/// ## Protocol
59///
60/// 1. The verifier samples $r_z \in K^\ell$.
61/// 2. The parties run an $\ell$-round MLE-check on $0 = \sum_x \textsf{eq}(r_z, x) \cdot
62/// (\widetilde{A}(x) \cdot \widetilde{B}(x) - \widetilde{C}(x))$, yielding a challenge point
63/// $r_x$ and a final target `eval`. The composition $A \cdot B - C$ has degree 2; the eq factor
64/// is folded internally by the MLE-check.
65/// 3. The prover sends the six `Word::BITS`-wide per-bit evaluation columns at $r_x$; the verifier
66/// recombines $\alpha_A = \sum_i \textsf{basis}(i) \cdot \widetilde{a}_{\textsf{lo}}(r_x, i) +
67/// \textsf{basis}(64+i) \cdot \widetilde{a}_{\textsf{hi}}(r_x, i)$ (and $\alpha_B, \alpha_C$
68/// likewise), and checks $\textsf{eval} = \alpha_A \cdot \alpha_B - \alpha_C$.
69///
70/// The reduction outputs the six per-bit evaluation columns at the shared point $r_x$.
71pub fn verify<F, C>(n_vars: usize, channel: &mut C) -> Result<BinMulOutput<C::Elem>, Error>
72where
73 F: BinaryField,
74 C: IPVerifierChannel<F>,
75 C::Elem: From<F>,
76{
77 // Sample the zerocheck challenge r_z.
78 let r_z = channel.sample_many(n_vars);
79
80 // Run the degree-2 product MLE-check; the claimed value is zero. The eq factor is folded
81 // internally by `mlecheck::verify`.
82 let SumcheckOutput {
83 eval,
84 challenges: mut eval_point,
85 } = mlecheck::verify(&r_z, 2, C::Elem::zero(), channel)?;
86 eval_point.reverse();
87
88 // The prover sends the six per-bit evaluation columns at r_x.
89 let a_lo_evals = channel.recv_array::<{ Word::BITS }>()?;
90 let a_hi_evals = channel.recv_array::<{ Word::BITS }>()?;
91 let b_lo_evals = channel.recv_array::<{ Word::BITS }>()?;
92 let b_hi_evals = channel.recv_array::<{ Word::BITS }>()?;
93 let c_lo_evals = channel.recv_array::<{ Word::BITS }>()?;
94 let c_hi_evals = channel.recv_array::<{ Word::BITS }>()?;
95
96 // Precompute the basis-element vectors used to recombine a (lo, hi) per-bit column pair into
97 // the packed field element evaluation alpha = sum_i basis(i) * lo[i] + basis(64 + i) * hi[i].
98 let basis_lo: Vec<C::Elem> = (0..Word::BITS)
99 .map(|i| C::Elem::from(F::basis(i)))
100 .collect();
101 let basis_hi: Vec<C::Elem> = (0..Word::BITS)
102 .map(|i| C::Elem::from(F::basis(Word::BITS + i)))
103 .collect();
104 let recombine = |lo: &[C::Elem], hi: &[C::Elem]| -> C::Elem {
105 inner_product(lo.iter().cloned(), basis_lo.iter().cloned())
106 + inner_product(hi.iter().cloned(), basis_hi.iter().cloned())
107 };
108 let alpha_a = recombine(&a_lo_evals, &a_hi_evals);
109 let alpha_b = recombine(&b_lo_evals, &b_hi_evals);
110 let alpha_c = recombine(&c_lo_evals, &c_hi_evals);
111
112 // The MLE-check already folded the eq factor, so no explicit eq(r_z, r_x) term appears here.
113 channel.assert_zero(alpha_a * &alpha_b - &alpha_c - &eval)?;
114
115 Ok(BinMulOutput {
116 eval_point,
117 a_lo_evals,
118 a_hi_evals,
119 b_lo_evals,
120 b_hi_evals,
121 c_lo_evals,
122 c_hi_evals,
123 })
124}