Why is the Keccak-256 hash function, used throughout the Ethereum protocol, so fast on CPUs yet such a notorious bottleneck for zk-SNARKs? This discrepancy currently hinders many efforts to build zk-rollups, zk-bridges, and other solutions intending to scale blockchain computation using cryptographic proofs. The problem stems from a mismatch between the fundamental data types used by computers and those used by today's SNARKs. In a new research paper from the Ulvetanna team, Succinct Arguments over Towers of Binary Fields, we offer a new approach to SNARK construction that will ultimately deliver orders of magnitude performance improvements for real-world computations. In addition, we are open-sourcing our in-progress Rust implementation of the system, called Binius.

Bits—zeros and ones—are the fundamental units of information. In all common methods of computing, from semiconductor gates to high-level programming languages, we deal with bits, 8-bit bytes, and 32- or 64-bit words. On the other hand, today's widely used SNARKs compute fundamentally over finite fields of prime order, often on the order of 256 bits. Teams like Polygon Zero and RISC Zero have achieved performance breakthroughs by moving from 256-bit prime fields to smaller prime fields, on the order of 64-bits and 32-bits, respectively. At Ulvetanna, we began wondering why we couldn't extend the advantages of small fields all the way down to the smallest field: the single-bit field.

Mathematically, the 1-bit field is known as GF(2), and it belongs to a family called binary fields. Binary fields may seem strange at first for those who haven't encountered them before. The addition of \(k\)-bit binary field elements amounts to the exclusive or (XOR) operation on \(k\)-bit strings. And multiplying binary field elements resembles the modular multiplication of polynomials more than it does the modular multiplication of integers. However, these fields possess some remarkable properties that allow for exceptionally efficient implementation in digital circuits. Binary fields are far from a new concept in cryptography; in fact, the AES-GCM encryption standard makes use of two different binary fields, GF(2⁸) and GF(2¹²⁸). In the world of SNARKs and verifiable computing, it is widely overlooked that the much-celebrated Fast Reed–Solomon IOP of Proximity (FRI), at the heart of the STARK protocol, was originally designed for binary fields as well.

The data type mismatch is more than just a theoretical point; many ZK circuits, including ones designed to verify a Keccak-256 hash, actually do represent bits using much larger field elements. For example, elliptic curve SNARKs like PLONK and Groth16, which require 256-bit prime fields for security, often use circuits with 256-bit field elements that take the values 0 or 1 on many of their wires. This practice wastes 255 bits and accounts for the massive amount of memory required to prove SNARKs for meaningful statements. We call this phenomenon the overhead of embedding. Fields like Goldilocks, which we wrote about in a prior blog post, reduce this embedding overhead but still leave a 64x savings on the table. This is precisely the improvement we seek to capture with our techniques.

As appealing as binary fields seem, there were various technical issues that, until this point, prevented their adoption in our industry. We find, however, that by applying and adapting techniques from works published only in the last few years, such as Brakedown, HyperPlonk, and Lasso, we manage to circumvent these issues. The result of our research is a practical and highly efficient SNARK protocol that works for GF(2). We develop, among other contributions, a polynomial commitment scheme for GF(2) that incurs no embedding overhead, meaning committing bits of data is as efficient as committing 64-bit chunks. The Binius construction applies not only to GF(2) but to a whole family of binary fields of power-of-two sizes, known as a tower of binary fields. This percolates all the way to the arithmetization level, meaning the PLONKish and AIR constraint systems that our SNARK supports have access simultaneously to the whole tower. In effect, the constraint system layer can use data types with sizes matching bits, bytes, and words, which allows for further performance improvements.

One potential drawback of using binary fields in SNARKs is that integer addition and multiplication cannot be performed "natively" in the constraint system. The advent of efficient lookup arguments like Lasso, however, has driven down the cost of non-native circuit operations. While Lasso itself was previously only recognized to outperform alternative lookup arguments for elliptic curve-based SNARKS, binary tower fields present another setting that can capture Lasso's improvements. Taking advantage of our ability to cheaply operate directly on bits, of efficient lookup protocols, and of several other multilinear polynomial protocols we developed, our paper offers constraint system gadgets that efficiently perform integer addition and multiplication. As another demonstration, we also give a constraint system for verifying the full Keccak-256 hash function that only needs to commit 12 kilobytes of data per Keccak-f permutation.

We see three main advantages to binary tower field SNARKs. First, this approach offers much lower memory usage and computational cost by maximizing the benefits of small fields. Binius is already 50x more efficient than the next-best system that we benchmarked, plonky2, at committing 1-bit elements, and there are plenty of optimizations to come. The second benefit is compatibility with standard hash functions. Binary tower field SNARKs can efficiently perform bitwise operations like XOR and logical shifts, which are heavily used throughout SHA-256, Keccak-256, and other symmetric cryptography primitives. We identify Grøstl, in particular, as an attractive hash function for verification with our techniques. Though not as widely known as Keccak and Blake2, Grøstl appeared alongside them as a SHA-3 competition finalist. Grøstl's design is based on AES and has undergone extensive cryptanalysis, which inspires more confidence than the Poseidon hash function that many SNARKs today rely on. Looking ahead to future work, we expect Binius also to be able to efficiently prove and verify properties of AES-GCM-encrypted ciphertexts in zero-knowledge. Finally, the third significant benefit is the very hardware-friendly implementation that binary fields promise.

Binary field arithmetic operations rely solely upon simple logic gates (eg. XOR) and bit-shifts, which come for free. This is in contrast to prime fields, which require complex, wide integer multipliers. This is particularly consequential in hasher circuits: the compute bottlenecks that Poseidon and Poseidon2 create completely disappear with Grøstl. This means we can fit more arithmetic and hashing accelerators on the same silicon area, and run them at a higher clock frequency, than we could with even carefully chosen prime fields. Moreover, the reduced memory requirements of the Binius prover, arising from the elimination of embedding overhead, results in less on-chip memory usage and bandwidth pressure between host and accelerator.

Irreducible is a cryptographic acceleration company, and our mission is to accelerate the ZK revolution. The team leveraged our combined expertise in hardware implementation, high-performance computing, and cryptography in the effort behind Binius. While the software implementation already demonstrates great performance, our system will really shine with hardware acceleration. We have internally implemented several of the key modules in FPGAs. The results we are seeing promise to deliver orders of magnitude improvements in proving performance. Stay tuned for a follow-up technical report.

This work is far from over – we’re just getting started. We look forward to working with the web3 and zero-knowledge communities to deliver next-level SNARK performance with binary tower fields and Binius. Follow our blog and @UlvetannaHQ on X (formerly Twitter) for future updates. 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!

‍

Thanks to Justin Thaler for the many conversations that contributed to our research effort. Thanks to Eli Ben-Sasson for answering several of our questions regarding binary field STARKs. Thanks to Achal Srinivasan and the Paradigm design team for their help with the Binius logo.