Binius: Surfing on Binary Fields

Taiko Labs

0x5b79

September 24th, 2024

Thanks to 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

Mental Model

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.

What are Fields

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$
Associativity: Addition and multiplication must be associative.
$x_1,x_2,x_3 ∈ F,~~~ x_1(x_2 · x_3) = x_3(x_1 · x_2)$
Existence of a neutral element: There are neutral elements (a number which, when added to or multiplied by any other number in the field, leaves that number unchanged), zero (0) for addition and one (1) for multiplication.
$x ∈ F, ~~~ e·x = x$
Existence of an inverse: Every element except zero has an additive and multiplicative inverse (an element that, when combined with another element using the field's operation, produces the neutral element for that operation).
$x ∈ F,~~~ x·x^-1 = e$

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.

Why We Need Fields

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.

The SNARKs Landscape

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.

SNARKs Operations

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

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.
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).
Vanishing Argument: This step involves lots of arithmetic circuit evaluations. It's where the bulk of the proof generation occurs.
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.

SNARKs Performance Challenges

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.

What We Have Now?

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.

SNARKs Over the Smallest Field

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