Module booleanity 

Booleanity (binary-polynomial lookup) argument.

Proves that every coefficient of every witness binary-polynomial column is a bit $\in \{0,1\}$. The argument is structured as a single MultiDegreeSumcheckGroup of degree 3, batched alongside the existing CPR group with shared randomness, and discharges its bit-slice claims for free against the existing lifted_evals payload.

Relation

For each witness binary-poly column $u_j \in (F_q^{<D}[X])^n$ with $n = 2^\mu$, decompose row-wise as

$$ {u_j}b = \sum_{i=0}^{D-1} v_{j,i,b} * X^i $$

The booleanity claim is:

$$ \forall j, i, b: v_{j,i,b} \in \{0,1\} $$

Equivalently, the MLE statement $\widetilde{v_{j,i}}(b)*(\widetilde{v_{j,i}}(b)-1) = 0$ for all $b \in {0,1}^\mu$. The protocol reduces this to a single batched sumcheck

$$ \sum_{b in {0,1}^\mu} eq(r, b) * \sum_{j=0}^{N-1} \sum_{i=0}^{D-1} \delta^j * \gamma^i * \widetilde{v_{j,i}}(b) * (\widetilde{v_{j,i}}(b) - 1) = 0 $$

with batching challenges $\gamma$ (over the D bit-slices) and $\delta$ (over the N witness binary-poly columns), and zerocheck point $r$. After the sumcheck reaches $r*$, the prover sends bit_slice_evals = $(\widetilde{v_{j,i}}(r*))$ to the verifier; these are then folded by MultipointEval into the standard evaluation point $r_0$ together with the CPR up/down evals. At $r_0$ the bit-slice MLE evaluations are exactly the coefficients of the polynomial-valued lifted_evals (by the MLE-commutes-with-coefficient-extraction identity), so the verifier discharges them for free.

Structs

BoolProverAncillary

Ancillary data produced by BooleanityChecker::prepare_sumcheck_group and consumed by BooleanityChecker::finalize_prover.

BoolVerifierAncillary

Ancillary data produced by BooleanityChecker::prepare_verifier and consumed by BooleanityChecker::finalize_verifier.

BoolVerifierSubclaim

Subclaim emitted by BooleanityChecker::finalize_verifier.

BooleanityChecker

Booleanity sumcheck group constructor / verifier.

BooleanityProof

Proof produced by the booleanity prover. Carries only the flat list of bit-slice MLE evaluations at the multi-degree sumcheck output point $r*$. The remaining open-eval consistency check at $r_0$ is discharged by the protocol-layer caller against lifted_evals.coeffs.

Enums

BooleanityError

Errors from the booleanity subprotocol.

Functions

build_witness_bit_slice_mles

Build per-bit-slice MLEs for a set of binary-poly columns.