Once Upon a Finite Field: journeying through Towers with Goldilocks and BabyBear, in the enchanted world of small fields for ZKP performance.

Once upon a time... there was extensive research and development aimed at improving the speed of zero-knowledge proofs. Researchers had strived to optimize prover, verifier times, and proof sizes using a variety of techniques, including diverse IOPs, polynomial commitment scheme, hashes, and hardware acceleration. One technique that gained traction was the use of smaller fields. The premise was that 'smaller fields' facilitate calculations to run more efficiently on consumer hardware, such as GPUs that work with 32-bit data types and CPUs that operate on 64/32-bit types. This in turn reduces latency in applications like zkRollups.

Polygon's 'Plonky2' uses a field defined as p = 2 ⁶⁴ - 2 ³²  + 1, which is called the Goldilocks field. The zkVM Risc0 uses an even smaller field called BabyBear defined as: p = 15 * 2 ²⁷ + 1. Plonky3: utilizes one even smaller Mersenne31: p = 2 ³¹ - 1  + 1. All of these systems use FRI as the commitment scheme, can we use small fields outside of this context for example in sum-check based PCS? What are the costs and benefits of using small fields? In this article, I will delve into our understanding of using 'small' finite fields in zero-knowledge proof systems, their implementations, and potential future directions in epochs yet to come.

What kinds of small fields were there in production?

Much of the mystical lore regarding the use of small fields in zero-knowledge proof systems remains rather opaque. While there are some blog posts and a handful of videos available, often the primary source of real treasures are the inline comments within the codebase themself, detailing these fields and their purpose. For example in the Risc0 codebase we have a comment starting at line 41 which explains two benefits of using BabyBear:

1. Is less than 2^31 so that it fits within a 32 bit word. (works well on CPU)
2. Otherwise have as large a power of 2 in the factors of P-1 as possible.

The second point is out of scope for this article. The TLDR: it should work well with FFT (Fast Fourier transforms), which are used in many ZKP systems.

The initial point is quite logical. For a proving system to function optimally, the foundational data types must be highly compatible with hardware. Polygon's 'Plonky2' offers documentation that is exceptionally well-crafted, delving even deeper into this topic. They use FRI because the alternative KZG is 'elliptic curve' based, and things that are elliptic curve based require larger finite fields (like 2 ²⁵⁶ large). Goldilock's is p = 2 ⁶⁴ - 2 ³²  + 1, which is much smaller — meaning any field element fits into 64 bits. This is what works well on many CPU. In one article they claim a 40x performance improvement, just by using this smaller field!

And then, as tales of old often go, in the codebase of Polygon's newer system 'Plonky3', it was hardly a surprise to stumble upon an even smaller field being used: Mersenne31. This field is small enough to work with 32 bit data types. Which means better performance on GPU/CPU which often use 32 bits. Daniel Lubarov, the wise, explains more in the following video:

Great, so we just always use ever smaller fields now.. right?

It's not that straightforward. Systems that don't rely on elliptic curves can more readily use these small fields. However, complications arise when the proving system must interact with cryptographic primitives, such as ECDSA signatures, which necessitates the use of elliptic curves. While I haven't personally experimented with this, many seers foretell that it could significantly lengthen the prover time. One argument is that you would need to use more field elements to represent the curve data types, causing a bottleneck for the prover. While others argue that the hardware friendly fields will work very well with CPU — for the non-native 256-bit arithmetic needed.

There is a lot of nuance and subtlety here. In some systems the bottlenecks could be larger and in other settings it could matter very little at all. Generally speaking, doing field operations over smaller fields, should improve performance; To a staggering '40-fold' performance increase, or so the legends say!

Smaller fields work well with systems that do not use elliptic curves (FRI), but what about systems that do (KZG)? It is possible to use smaller fields with something called an 'extension field' to allow for non-native arithmetic such as EC operations. Extensions fields are themselves fields that restrict the operations of F. E < F. One can also stack fields, this is called 'Towers of fields' like this: F1 < F2 < .... Fn. The security of these extensions is still under scrutiny, with some research showing that they are less secure under some assumptions. It is also not clear which curves to use over these fields, which will still allow for recursion (a method used in many ZKP systems).

If some field extensions are secure what's next?

There are a few curves, with extension fields, that do not have any known vulnerabilities. For example the curve ecGFp5 mentioned here: "We describe here the choice of a secure curve, amenable to safe cryptographic operations such as digital signatures, that maps to such models, while still providing reasonable performance on general purpose computers." Or the 'Cheetah' curve mentioned here which also has a Rust implementation. The authors note: "Elliptic curves based on extension fields may suffer from specific attacks that do not apply to common elliptic curves constructed over large prime fields and may outperform regular Pollard-Rho attacks, and hence require more scrutiny when evaluating their estimated security level." For FRI based systems it seems that custom crafting these curves is a reasonable endeavour, but takes a bit of courage.

Can we simply use these smaller fields and then employ their extensions when necessary (e.g., for EC operations)? Most operations can be done in the small fields, while operations that require larger fields can be done in the extension field. This seems to be what the 'Plonky3' team is after as they note adding 128 bit extensions fields, as a feature. ⚠️ This may just be an artifact in the code-base.

Can this be used the other way around? For example an EC system using a smaller field when needed? As mentioned above this seems less likely as it would be hard to find curve pairs that support extensions and also recursion. But, 'if you keep on believing, the dream that you wish may come true'.

It seems to be possible in other systems that use field operations like the sum-check protocol. Most of the operations will be done in the small fields while some operations are pulled from the larger extension field, in this case. This research is very new and the theoretical implications have yet to be discussed publicly in any detail.

With extension fields a few complications may arise, which are contingent on other aspects of the ZKP scheme in use. For instance, there's the challenge of using the extension field for certain operations (randomness) while ensuring that only base field operations are used in the IOP. If the challenges are overcome, we can work with field extensions over small fields in more contexts — the best of many worlds. This is the fairytale ending where we all live happily ever after.

* Thanks to the wizards Brandon and Justin  for a lively discussion on the performance and theory behind smaller fields.