Skip to main content

prove

Function prove 

Source
pub fn prove<A, F, P, Channel>(
    columns: [&[Word]; 6],
    channel: &mut Channel,
    alloc: &A,
) -> BinMulOutput<F>
where A: Allocator, F: BinaryField + From<u128>, P: PackedField<Scalar = F>, Channel: IPProverChannel<F>,
Expand description

Prove the binary-field multiplication check (BinMul) reduction.

Proves $\widetilde{A}(x) \cdot \widetilde{B}(x) = \widetilde{C}(x)$ for every $x$ on the boolean hypercube $\mathbb{B}_\ell$ over the GHASH field, where each element is carried by a (lo, hi) pair of 64-bit words. See [binius_verifier::protocols::binmul::verify] for the protocol description and output shape.

The six columns are the (lo, hi) word pairs of the two multiplicands and the product, in the order [a_lo, a_hi, b_lo, b_hi, c_lo, c_hi], all of equal length. That length need not be a power of two: the hypercube is $\mathbb{B}\ell$ for $\ell = \lceil \log_2 n \rceil$, and a row at or past the columns’ end reads as the zero field element. A zero row satisfies $0 \cdot 0 = 0$, so it contributes nothing to the zerocheck. The GHASH-field element for row $x$ is $\langle\langle z{\textsf{lo}}, z_{\textsf{hi}} \rangle\rangle = \sum_{i=0}^{63} z_{\textsf{lo},x,i} \cdot X^i + \sum_{i=0}^{63} z_{\textsf{hi},x,i} \cdot X^{64+i}$ for each of $z \in {a, b, c}$.