Switching to small fields to reduce the transaction fees
Currently, the arithmetization and the prover of Linea work over the scalar field of the BLS12-377 elliptic curve (introduced by the ZEXE paper). This field can store up to 252 bits per element (recall that we use the scalar field and not the 377 base field). And we have it for historical reasons. Initially (before Linea had implemented the proof aggregation mechanism), we had chosen the BN254 scalar field to have off-the-shelf Ethereum compatibility.
The switch to BLS12 was motivated by the fact that it allows a simple and efficient aggregation mechanism for us. In substance, BLS12-377 is part of an efficient 2-chain: a combination of elliptic curves thanks to which we can very efficiently verify BLS12-377 Plonk into another proof. The chain that we used has been discovered) by Youssef El Housni, from our amazing cryptography team.
Both the BN254 and the BLS12-377 fields are relatively large. But smaller, much smaller fields have gained traction in the past years as they allow faster (and therefore cheaper) proof generation. The incentive to optimize the prover costs on Linea is quite strong as the prover costs represent the major part of the operating, the rest being essentially the L1 costs that we have optimized a lot over the past year. Thus, reducing the prover costs will allow cheaper transactions on Linea.
This post describes a plan to move to a 32-bit field. At this point, we are considering two prime fields:
- KoalaBear ($p = 2^{32} - 2^{24} + 1$)
- BabyBear ($p = 2^{32} - 2^{27} + 1$)
Which one is better?
In addition to being small, these two fields have two important properties that make them attractive for Linea:
-
They have a good 2-adicity, meaning that $p$ is divisible by $2$ a lot of times: respectively 24 and 27 times for KoalaBear and BabyBear. This enables the FFT (Fast-Fourier Transform) for vectors of size $2^{24}$ and $2^{27}$ which is required by the the proof system. BabyBear is a little bit ahead on that metric.
-
They are very efficient to implement SNARK-friendly hash functions. These hash functions are built using what is called a “power S-box”: a mathematical function $f: x \rightarrow x^\alpha$ such that $\alpha$ and $p-1$ are coprime and $\alpha$ is prime. For efficiency, it’s better if $\alpha$ is small. With Baby and Koala bear, we have $\alpha=7$ and $\alpha=3$. KoalaBear stands out a little better than BabyBear here.
Why small fields = faster
Numerous projects have reported massive improvements on their provers due to using small fields. To understand why, we need to first understand that 90% of what the prover does is a combination of field arithmetic operations. With this in consideration, it follows that using a field with faster operations vertically improves every operation that the prover does. Small fields are faster, much faster, and for multiple reasons.
-
The runtime of a field multiplication grows super-linearly with the size of the field. One of the best algorithms for multiplying ~256 bits fields is CIOS, gnark uses an optimized variant introduced in a subsequent work. The time complexity of the algorithm is somewhere between loglinear and quadratic. In contrast, for 32 bits fields only a few 32 bits multiplications are needed.
-
32-bit operations are also better supported by hardware: AVX512 supports the vectorized MulHi and MulLo operations thanks to which we can implement native vector multiplications for finite fields. Additionally, 32-bit operations are well supported by GPUs and this opens an avenue for a GPU implementation of the prover of Linea in the future.
With all that combined finite field arithmetic operations are a lot faster for smaller fields. For illustration, we have the following throughput metrics on an AVX-512 implementation of vector field multiplications.
| Field | #Op | Runtime (ns) |
|---|---|---|
| BLS12-377 | 256 | 3368 |
| KoalaBear | 256 | 66.8 |
| BabyBear | 256 | 67.1 |
But small field = more field operations
A counterargument for small fields is that components of the prover require more field operations when using a small field. Fortunately, we anticipate that the massive benefits of using small fields far outweigh the drawbacks.
- Probabilistic checks
Internally, the prover performs various probabilistic checks. These all follow from the Schwartz-Zipfel lemma.
:::info
Schwarz-Zipfel Lemma
Let $P$ be a non-zero polynomial of degree $n$ over the field $\mathbb{F}$. Then $P$ vanishes at most $d$ times.
:::
A consequence of this famous lemma is if $P$ and $Q$ are two polynomials of degree less or equal to $n$ then for a random an uniform $r \in \mathbb{F}$
$$\mathbb{Prob}_r\left[P(r) = Q(r)\right] \leq \frac{n}{|\mathbb{F}|}$$
This techniques allows testing whether two polynomials are equals and is ubiquitous in many proof systems, including Vortex. The challenge with small fields is that $|\mathbb{F}|$ is not large enough for the test to be reliable enough for cryptographic applications. The solution is to do these checks using finite field extensions. They are like complex numbers but for finite fields and can be used to construct larger fields from the base field $\mathbb{F}$. The drawback is that on top of adding complexity to the implementation, they are also slower than the base field. But still faster than a 256 bits base field.
- Non-native arithmetic
Although ZK-proof systems natively work over fields as atomic elements. The EVM is designed to interact with bytes and integers of various size.
Most of the time, we can be confident that the integers are much smaller than the fields: for instance a variable storing the number of transaction or the amount of gas consumed. In this case, this is a no-brainer we can simply emulate the variable with a field element directly and say that the field operation will coincide with the emulated integer operations. Using a 256-bits field, this logic can be be applied most of the time.
With a 32 bit field, there are more nuances to that and we encounter more cases where we need to emulate large integers and large integers operations using several fields elements to represent a single large integer. We call that non-native arithmetic and it the smaller the field is the more field operations are required to emulate a large integer.
Migrating to small fields
Several parts of the Linea prover stack will have to be adjusted to support small fields optimally. We will proceed gradually, targetting 80% of the benefits with 20% of the efforts at first. The goal is to narrow down the changes in the execution proof
- Recursion on a Plonk circuit
An upside of using the scalar field of a curve as a base field for our proof system is that is allows us to very efficiently do recursive composition: generating a proof that one or multiple proofs are correct. We use this techniques at multiple levels in our stack. One of these level converts a Vortex proof (faster to generate but larger proof size) into a Plonk proof (slower to generate but smaller proof size). Switching to another field will break this compatibility. Fortunately, this can be overcome with reasonable overheads.
Conclusion
The positive side is that most of the EVM arithmetization relies only on operations between already small numbers or boolean operations. This part will remain identical to what we have today and will benefit from a direct speed-up. The other parts will require more field operations but they are so much cheaper that it will still be faster. A second benefit that we foresee, is that since the fields are also 8 times smaller we will be saving memory.