Skip to main content

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}