The central cryptographic innovation in our research paper behind Binius, called Succinct Arguments Over Towers of Binary Fields, is a multilinear polynomial commitment scheme (PCS) over binary towers that charges computation by the bit. The PCS commits polynomials without embedding overhead, meaning the computational cost of committing a polynomial depends only on its total byte-size, irrespective of whether the coefficients live in a small 32-bit field or a tiny 1-bit field. This original scheme, however, only eliminates embedding overhead in the polynomial commitment phase, and still presents overhead for tiny fields in the proof size and cost to generate and verify opening proofs. Concretely, a polynomial with 2²⁸ \(\mathbb{F}_2\) coefficients and a polynomial with 2²³ \(\mathbb{F}_{2^{32}}\) coefficients require 0.74 and 1.2 seconds to commit, respectively, but the proof sizes are 2.3 MB and 0.64 MB.

The large proof sizes of this original PCS posed an issue for efficient proof recursion. In April, we released a follow-up work, Polylogarithmic Proofs for Multilinears over Binary Towers, that gave concretely better proof sizes than the original PCS and better asymptotic scaling guarantees. That construction, which we referred to as FRI-Binius, also suffered from the problem of embedding overhead in the evaluation phase of the commitment protocol, however. The proof size for an \(\mathbb{F}_2\) polynomial with 0.5 GiB of data was still close to 5 MiB. On the other hand, the size of a proof for a polynomial with the same amount data but coefficients in \(\mathbb{F}_{2^{64}}\) was just over 0.5 MiB, nearly 90% smaller.

Today we're proud to announce our work on a new technique that closes the gap for tiny fields and completely eliminates the problem of embedding overhead. We call this technique "ring-switching", as it is partly inspired by the code-switching idea from Local Proofs Approaching the Witness Length. Ring-switching is a special sumcheck-based protocol that produces a polynomial commitment for any field, as small as \(\mathbb{F}_2\), by a reduction to a polynomial commitment for the "packed" version of that polynomial over a field extension. One could, for example, use the ring-switching reduction to construct an \(\mathbb{F}_2\) PCS from a FRI multilinear PCS over \(\mathbb{F}_{2^{128}}\). We take this idea a step further and interleave the ring-switching sumcheck with the FRI protocol, building on the fundamental ideas of FRI-Binius. The result is a FRI-based multilinear PCS that truly charges by the bit, not just in commitment time but also proof size.

Instead of release a new paper, we opt to update Polylogarithmic Proofs for Multilinears over Binary Towers with the new construction, as it supersedes the original. Curious readers should see Sections 4 and 5 for the new content, which is also summarized in the technical overview in Section 1.

The new version of FRI-Binius has several more desirable properties. The FRI protocol operates normally over large fields, whereas the previous version defined a FRI protocol over tower algebra elements. This enables the use of a special proximity gap result for Reed–Solomon codes that brings down the proof size. Also, the new protocol allows for batching the FRI protocol invocations across polynomial evaluation proofs for different coefficient fields. This kind of batching was not possible with our previous PCS protocols.

The update to the FRI-Binius paper comes complete with a performance evaluation section. We compare the concrete performance of the new FRI-Binius PCS* to the original Binius PCS, from Succinct Arguments, and the univariate FRI PCS in Plonky3. We summarize the performance results for polynomials with 2²⁴ coefficients in the table below. The current implementation completed for this release of the paper does not implement several well-known FRI optimizations such as high-arity folding and Merkle caps, pioneered by the ethSTARK and plonky2 projects. (We note that Plonky3 does not implement those techniques yet either.) The table below also shows the proof size achievable if those optimizations were applied. We intend to implement them in Binius in the coming weeks. The methodology for performance evaluation is explained in greater detail in Section 5.2 of the paper.

| Scheme            | Coeff Bits | Current Size (MiB) | Optimized Size (MiB) | Commit + Prove Time (s) |
| :---------------: | :--------: | :----------------: | :------------------: | :---------------------: |
| Plonky3 FRI       | 31         |               1.10 |                0.313 | 9.55                    |
| Original Binius   | 1          |              0.724 |                0.724 | 0.11                    |
|                   | 8          |              0.746 |                0.746 | 0.50                    |
|                   | 32         |               1.01 |                 1.01 | 2.0                     |
| FRI-Binius        | 1          |              0.844 |                0.162 | 0.91                    |
|                   | 8          |              1.089 |                0.203 | 7.6                     |
|                   | 32         |              1.289 |                0.235 | 28.9

This new research result should dispel any lingering doubt whether Binius can attain the recursion efficiency of popular FRI-based SNARKs/STARKs like plonky2, Boojum, and RISC Zero. In fact, we fully expect recursive SNARKs built with Binius to be substantially more performant, thanks to the efficient arithmetic of binary fields and efficient arithmetization of fast, classical hash functions, points we have argued in prior blog posts and public presentations.

Irreducible is obsessed with making Binius the most performant system for verifiable computing in the world, and this invention is another big step towards making that happen. If you want to help us change the future of ZK, see the open positions we are hiring for!

* At the time of writing, our implementation is still a prototype that lives in a git branch called fri-binius. We will be polishing the code and merging it into the main branch of the Binius repo in the coming weeks.

Update (July 17, 2024): The original version of this announcement reported much slower Plonky3 performance than this version does. We realized that our initial evaluation of that protocol failed to leverage that protocol's extensive optimizations targeting the case of batched polynomial commitments. We've rerun our benchmarks in the batched setting, and have updated the both paper and numbers reported in the table above.