In November 2023, we published Succinct Arguments over Towers of Binary Fields, our cryptography research that provides the theoretical results underpinning Binius. Today, we released a follow-up work that leverages the Fast Reed-Solomon IOPP (FRI) to construct a new polynomial commitment scheme (PCS) for binary tower fields. Binius initially used a variation of the Brakedown PCS, which yielded proof sizes that are asymptotically of size \(O(\sqrt n)\) for polynomials with \(n\) coefficients. The key innovation in Succinct Arguments over Towers of Binary Fields was to adapt Brakedown to work with Reed–Solomon codes even on polynomials over tiny binary fields like \(\mathbb{F}_2\). This would be impossible without our block-level encoding variant, due to the limitation that the alphabet of a Reed–Solomon must be larger than the codeword length.

In Polylogarithmic Proofs for Multilinears over Binary Towers, we construct a multilinear PCS that combines ideas from the binary field FRI protocol of Ben-Sasson et al., the BaseFold multilinear PCS of Zeilberger, Chen, and Fisch, and the Binius block-level encoding technique due to Irreducible's research team. By reducing the cost of PCS verification, the new argument, which we call FRI-Binius, will enable more efficient recursive proof composition. Our paper's contributions are

1. We draw a new connection between the Novel Polynomial Basis additive NTT and binary field FRI. Based on that connection, we prescribe a specific and convenient choice of mathematical objects left generic by the original FRI paper.

2. We adapt the BaseFold multilinear PCS to binary towers with block-level encoding, thereby supporting tiny binary fields like \(\mathbb{F}_2\) with no embedding overhead during the commitment phase.

3. We show how the new PCS is a generalization of the Brakedown-style PCS, allowing for a rich trade-off spectrum between prover and verifier efficiency.

4. We present improved proof sizes for PCS proofs for a range of polynomial sizes. The size of an opening proof for a polynomial over \(\mathbb{F}_2\) with \(2^{32}\) coefficients is now 3.5 MiB with FRI-Binius compared to 11.5 MiB with the original PCS.

We are actively looking for more exceptional engineers and computer scientists to help us push the limits of verifiable computing. Please see our careers page if you want to join us on this journey!