Streams of teal and gold binary digits converging into a triangular lattice against a dark navy background.

LaBinius: Lattice-Based Polynomial Commitments for Binary Computations

16 Sep 2026

Lattice-based proofs can be fast for algebraic statements, but proving a standard hash function exposes a mismatch. Keccak-256, SHA-256 and BLAKE3 rely heavily on bitwise operations, while existing lattice proof systems typically express constraints over fields of much larger characteristic.

Akita [DBK+26] provides a route to proving these computations through its integration with the Jolt zkVM. This supports well general-purpose programs, but proving a hash this way also incurs the overhead of representing and executing it within the virtual machine. For hash computations, this motivates connecting a lattice-based polynomial commitment directly to a specialised binary arithmetisation.

In joint work with Gregor Seiler, we introduce LaBinius [OS26], a lattice-based polynomial commitment scheme that separates the arithmetic used for commitments from the arithmetic used for evaluation claims. This lets us choose each for its own task. We connect it to existing front ends, Flock [BRW26] and Binius [DP25, DP26, Irr26], retaining their binary arithmetisations to prove standard hash computations.

The underlying commitment is an Ajtai commitment \(\mat{Y} = \mat{F}\mat{W} \bmod q\), with an arbitrary modulus \(q\). It need not even be prime! Here, \(\ring\) is a cyclotomic ring whose choice we explain below, and \(\ring_q = \ring/q\ring\). The public commitment key is \(\mat{F} \in \ring_q^{n \times m}\) and \(\mat{W} \in \ring^{m \times r}\) arranges the witness into a roughly square matrix of ring elements with binary coefficients. Additionally, writing \(\ring_2 = \ring/2\ring\), the relation includes the evaluation claim

\[ \widetilde{\vec{w}}(\vec{r}) = t \bmod 2.\]

Assuming \(m\) and \(r\) are powers of two, let \(\nu = \log_2(mr)\). Then \(\widetilde{\vec{w}} \in \ring_2[X_0, \dots, X_{\nu-1}]\) is the multilinear extension whose values on \(\{0,1\}^{\nu}\) are the entries of the vectorised witness \(\mat{W} \bmod 2\). The public evaluation point is \(\vec{r} \in \ring_2^{\nu}\), and \(t \in \ring_2\) is the claimed value.

As usual in lattice-based arguments, the standard trick is to let the verifier sample a short challenge \(\vec{c} \in \ring^r\) and check that the prover's opening \(\vec{v}\) satisfies \(\mat{F}\vec{v} = \mat{Y}\vec{c} \bmod q\). The prover's honest opening is a linear combination of the witness columns, \(\vec{v} = \mat{W}\vec{c} \in \ring^m\). Before sampling \(\vec{c}\), the prover supplies partial evaluations whose recombination the verifier checks against \(t\). A second linear check over \(\ring_2\) connects these partial evaluations to \(\vec{v}\), and the verifier also checks that \(\vec{v}\) is short.

The technical obstacle is extraction, which is a standard technique to show that a prover cannot cheat. Precisely, we construct an extractor algorithm which can rewind a (potentially cheating) prover and, after obtaining a few openings, recover a valid witness, proving knowledge soundness of the argument. Standard approaches recover a witness by dividing the difference of two accepting openings by a challenge difference. Requiring that difference to be invertible modulo \(q\) restricts the commitment arithmetic. As we do not care about actual shortness, we instead retain these differences as slack factors \(\vec{s} \in \ring^r\) in a relaxed opening:

\[\mat{F}\mat{W} = \mat{Y}\mathsf{diag}(\vec{s}) \bmod q.\]

We only need to invert the slack factors in the binary evaluation field, where our challenge set guarantees invertibility. This gives

\[\mat{W}' = (\mat{W} \bmod 2)\mathsf{diag}(\vec{s} \bmod 2)^{-1}\,\]

whose vectorisation has a multilinear extension satisfying the evaluation claim. The commitment binds this witness.

We use a power-of-three cyclotomic ring, concretely \(\ring = \ZZ[X]/(X^{162}+X^{81}+1)\), of conductor \(3^5 = 243\). Its reduction modulo two is the binary extension field \(\ring_2 = \ring/2\ring \cong \mathbb{F}_{2^{162}}\), where the polynomial evaluation claim lives. The binary witness is interpreted through reduction modulo two, so we do not need a separate proof that the committed coefficients are bits!

The usual power-of-two cyclotomics do not give us this large binary field. In \(\ring' = \ZZ[X]/(X^N+1)\), with \(N \geq 2\) a power of two, \(X^N+1 = (X+1)^N\) modulo two. The prime \(2\) totally ramifies: the prime ideal above it has norm \(2\), meaning its residue field has only two elements. Consequently, \(\ring'/2\ring'\) has nonzero nilpotents, and a challenge set with pairwise invertible (mod 2) differences can contain at most two elements. In the power-of-three ring, \(2\) is inert, giving the desired large field \(\ring/2\ring\). Furthermore, elements with binary coefficients in \(\ring\) remain distinct (mod 2), enabling the construction of a large challenge set.

A field-switching reduction (inspired by [DP26]) connects the front ends' evaluation claims over \(\mathbb{F}_{2^{128}}\) to our field. Flock and Binius keep their constraint reductions (PIOP), while LaBinius supplies the polynomial commitment and opening layers.

In our Rust implementation, we choose \(q\) as the product of two or three small NTT-friendly primes, with enough factors to reach the target \(\SIS\) security level. We represent arithmetic modulo this composite \(q\) in a residue number system (RNS), with one limb per prime factor. Since our witness is very low-norm, folding needs only one limb: we retain the witness transform modulo a single prime and compute \(\vec{v}=\mat{W}\vec{c}\) there.

For further commitment efficiency, we pack four elements of \(\ring\) into a cyclotomic super-ring \(\mathcal{S}\) of conductor \(8\cdot3^5\) and degree \(648\). In other words, we observe that \(\mathcal{S}\) is an \(\ring\)-module of rank four. It enables transforms with radix-two and radix-three steps. Our dedicated AVX-512 NTT exploits the binary input: the first three layers and the following twiddle factors are precomputed as small lookup tables. This replaces those layers' arithmetic with lookups indexed by groups of input bits.

For a concrete example, we report the following results for 131,072 independent BLAKE3 compression calls using Flock's front end. These measurements use one core of an AMD EPYC 9R05 with AVX-512, target 100-bit security, and include witness generation in prover time.

Scheme	Prover (s)	Verifier (ms)	Proof (KiB)
Flock	2.122	27.3	490.0
LaBinius	1.954	38.6	5,130.3
LaBinius + LaBRADOR	3.072	729.0	96.4

The direct opening gives roughly 67,000 compression calls per second, but its proof is somewhat large, i.e. asymptotically square-root of the witness. LaBRADOR [BS23] compresses the commitment and opening checks into a much smaller argument: here, below 100 KiB, about five times smaller than Flock's proof, with less than twice its prover time. In turn, verification becomes slower, so the choice depends on which cost matters most given specific applications.

Combining the fast verification of the direct opening with the compact proofs of the recursive variant is an exciting direction for future work, potentially using RoKoko [KLNOT26] or an argument tailored to these checks. Zero knowledge also remains a natural extension.

LaBinius: Lattice-Based Polynomial Commitments for Binary Computations

References