Thanks to Jim, Brecht, Cecilia and Lauri for review.

TL;DR

• Binary fields {0,1} are fundamental in cryptography, offering efficient operations for digital systems.

• SNARKs (Succinct Non-Interactive Arguments of Knowledge) use fields for complex calculations and proofs.

• Current trend; reducing field size in SNARKs for better efficiency (i.e., Mersenne Prime fields and tower of binary fields).

• Binary fields can build a "tower" structure: F2 → F2^2 → F2^4 → F2^8 → ..., allowing flexible computations.

• Advantages: No embedding overhead, efficient operations (XOR for addition), and natural fit for digital systems.

Content

• What are Fields

• Why We Need Fields

• The SNARKs Landscape

  • Elliptic and hash based

  • SNARKs operations and performance challenges

• What We Have Now?

• SNARKs over Smallest Field

  • Tower of binary fields, advantages and future

• Resources

We're in an era where ZK is maturing rapidly in every respect. In terms of theory (folding schemes, new STARKs), implementations (efficient zkVMs), hardware (ZK-specific chips) and also benchmarks. Even if we're not quite there yet in terms of real-time proving, the current trend will get us there faster than we thought.

Another key way to make ZK more efficient is to improve the "fields," which are the foundation of cryptography and set the boundaries for the entire theory. Our brains are wired to think in smaller, more manageable chunks, which makes sense from an efficiency standpoint. Binius, introduced by Irreducible, allows to build SNARKs over the smallest field.

Before we get to this part, we are going to create a foundation of fields and SNARKs.

In cryptography, fields refer to a mathematical concept that helps explain how cryptographic algorithms work. Think of a field as a set of numbers where you can perform basic arithmetic operations such as addition, subtraction, multiplication and division and still stay within the set.

To be considered a field, this structure must satisfy certain rules. Let's break this down:

• Commutativity: Addition and multiplication operations should be commutable.

  $$x_1,x_2 ∈ F,~~~ x_1 ·x_2 = x_2 ·x_1$$

The simplest and smallest example of a field used in cryptography is the 2-element finite field known as GF(2) or F2. This field contains only two elements: 0 and 1.

We need fields because we perform arithmetic operations in fields to generate a key. It's possible to do arithmetic in infinite fields, but the computer itself works in finite fields (it works in 2^64-bit fields). We use finite fields for efficiency.

It is important to remember that our mental model always tends to operate on smaller fields, because a smaller field means more efficient arithmetic. We'll come back to this later, now it’s time to cover SNARKs.

SNARKs are a way of checking the correctness of complex calculations. They reduce the resources needed for verification, making it possible to verify large calculations even in resource-constrained environments. This allows verification in scenarios where recomputation is impractical or too expensive. There are two types of SNARKs;

Elliptic Curve Based

• Extremely small proofs (1 KiB) and cheap verification in constant time.

• It can require a trusted setup (if you're not using IPA) and it's slower to generate proofs.

• They allows certain kind of folding for aggregation, depending on cycles of curves.

• Big prime fields like 256 bits.

Hash-Based (aka STARKs)

• The security depends on only hash functions.

• Bigger proofs (>20 KiB) and slower to verify.

• Faster to prove.

• The field used to arithmetize the recursion, can alsox” be used for generate proof.

• Support small fields like 64 and 32 bits.

Before discussing the binary fields, we need to understand SNARK's steps and possible bottlenecks related to their fields.

1. Generate Witness(Running the computation): This is the first step where the prover creates the "witness" - a set of inputs that proves the prover knows the argument.

2. Commit Witness: The purpose of this step is to create a cryptographic commitment to the witness data. For hash-based SNARKs, we use NTT(Number Theoretic Transformation, a type of discrete Fourier)+ Merkleization. For elliptic curve, MSM(Multi-Scalar Multiplication).

3. Vanishing Argument: This step involves lots of arithmetic circuit evaluations. It's where the bulk of the proof generation occurs.

4. Opening Proof: This is where the prover proves that some value is part of some commitment. The computational cost and the semantic complexity of the protocol depends on the technique used. Example techniques are KZG or FRI.

To understand where the bottleneck in the SNARK operation comes from, it is first necessary to examine where most of the time is spent during the operation of the steps mentioned above. A comparison from the Binius team's zkSummit presentation shows the where the most time is spent in Plonky3. A large amount of time is spent on committing.

Binius overcomes the committing bottleneck (by using binary fields and arithmetization friendly Grostl, an AES-based hash function) but creates another bottleneck on the vanishing argument which the Sumcheck protocol.

Since its inception in 2014 with the Pinocchio protocol and subsequent development of Zcash, ZK has made remarkable progress. We have now reached a point where we can set and meet certain standards such as;

• Verifiable VMs; EVM, RISC-V and WASM.

• Recursion of proofs. (With recursion, you can prove seemingly large programs very quickly, provided you have a provable network of machines).

• SNARKs-friendly hashes are semi-standart (Poseidon).

• Lookup arguments are widespread.

  and many more.

As we said above, fields are the most important component of cryptography. Our range of motion and arithmetic is totally limited by the field we choose.

The current trend (it’s not hype, it’s logical) is to reduce the size of fields. Because a larger field means more embedding overhead. This means paying the cost of a whole field for a value that is only defined by bits. Current initiatives such as Circle STARKs (please see Vitalik’s blog), allow to use of a more efficient prime field called Mersenne Prime (2^31 - 1). Plonky3 and Starkware’s Stwo prover now works on Mersenne field. This field provides 30% more CPU optimisation than Babybear, another commonly used 31-bit field.

Theory of Binary Fields

Binary digits (0 and 1) are the basic units of digital information. This elementary representation allows data to be efficiently encoded, processed and transmitted in all computing systems, from semiconductors to high-level languages.

A binary field, denoted as F(2^n), is a finite field with 2^n elements, where n is a positive integer. The simplest binary field is F2, which contains only two elements: 0 and 1. The smallest field is still complies with the same properties as we explained at the beginning.

Binary fields have been used in general cryptography for a long time, in the AES protocol for example. They've also been used in the FRI protocol in the SNARKs world. But building SNARKs over binary fields is a new and strong approach that was introduced by Irreducible (previously Ulvetenna).

Building a Tower of Binary Fields

Let's start with our foundation: the binary field F2, which contains only 0 and 1. It's simple, but limited. To build more powerful cryptographic tools, we need bigger fields. But how can we expand without losing the nice properties of binary arithmetic? This is where our tower comes in.

Imagine we're building a skyscraper, where each floor is a new, larger field. Our ground floor is F2. To build the first floor, we introduce a new element, let's call it x0. We define x0 by the equation (x0)^2 + x0 + 1 = 0. This gives us a new field, F2^2, with four elements: 0, 1, x0, and x0+1. We can represent these as binary pairs: {00, 01, 10, 11}.

Now, here's where it gets interesting. To build the next floor, we don't start over – we build on what we have. We introduce another new element, x1, defined by (x1)^2 + x0*x1 + 1 = 0. This gives us F2^4, with 16 elements.

We continue this process, each time introducing a new element xk defined by (xk)^2 + (xk-1)*xk + 1 = 0. It's like each floor of our skyscraper supports the one above it.

This construction, known as Wiedemann's tower, gives us a sequence of fields: F2 ⊂ F2^2 ⊂ F2^4 ⊂ F2^8 ⊂ ... ⊂ F2^(2^k). So the pattern of element counts as we go up the tower is: 2, 4, 16, 256, 65536…

In cryptography, this structure allows us to choose the right 'floor' of our tower for different operations, balancing security needs with computational efficiency. It's particularly useful in SNARKs, where we often need to switch between different field sizes.

To be summarize formally;

Advantages

• No more embedding overhead. SNARKs, like Groth16 or PLONK use big fields (n), but some values are only defined by bits only. This wastes n-1 bits.

• The beauty of this tower is that elements of smaller fields embed nicely in larger ones, and operations remain efficient. Addition is still just bitwise XOR, and multiplication, though more complex, can be done recursively.

Future of Binary Fields

As we mentioned earlier, using binary fields to build cryptography is not a new concept; it's a common practice. But building SNARKs with binary fields is a really novel and important approach. Even though it's not fully mature, it's likely that we'll see many more improvements in binary field-based proof techniques in the future. Because reducing problems to the smallest field is a really primitive and fundamental structure of human nature.

Irreducible is planning to build a zkVM on top of the Binius.

Resources

• Diamond, B. E., & Posen, J. (2023). Succinct Arguments over Towers of Binary Fields

• LambdaClass, 2023, How Binius is helping move the ZK industry forward

• Jim Posen’s Talk at StarkWare Summit

• Irreducible’s Presentation at zkStudyClub

• Irreducible’s Blog, Binius: a Hardware-Optimized SNARK

• Vitalik’s Blog, Binius: highly efficient proofs over binary fields

• Zero Knowledge Podcast episode, Episode 303 - A Dive into Binius with Ulvetanna

Explore open positions on our job board.

Get the latest from Taiko:

• Website: https://taiko.xyz.

• Discord: https://discord.gg/taikoxyz.

• GitHub: https://github.com/taikoxyz.

• Twitter: https://twitter.com/taikoxyz.

• Community forum: https://community.taiko.xyz.

• YouTube: https://www.youtube.com/@taikoxyz.

• Warpcast: https://warpcast.com/taikoxyz.

Contribute to Taiko on GitHub and earn a GitPOAP! You will also be featured as a contributor on our README. Get started with the contributing manual.