This article provides a friendly exposition to our new paper: “Really Complex Codes with Application to STARKs” by @Yuval_Domb
Intro: My Secret Playbook for Consuming Research
For over a decade I’ve been diving into cryptography research papers. For the longest time, I had this ritual: to truly grasp a paper, I’d read it three times. The first pass was just to get the lay of the land — skimming the main results and understanding the structure. The second read was more thorough; I’d dig into the introduction and make sure I understood all the key constructions. The third time reading was the most time-consuming — it was all about learning the proof techniques, the primitives, and their security definitions.
But there are always exceptions. Some papers are masterpieces; others are just plain cool. There are some I even know by heart (shoutout to L17). Lately, though, my attention span isn’t what it used to be. Usually I only have time for a quick pass before deciding on any action items. Weekends are my time for those deeper dives — the second and third reads — but the papers I choose then are more for the soul. I guess I’ve gained enough experience to zero in on the parts that matter most to me and extract the knowledge I need.
In recent years, I’ve added a new twist to my reading habit that makes it a lot more fun. With every paper I read, I try to reverse-engineer the author’s journey: How did this paper come to be? Thinking of it like a mystery novel, I ask myself questions like: What’s the real discovery here? Why hasn’t anyone else thought of this before — why now? Why this specific author and not someone else? Why are the results presented in this specific way? What results are missing? And so on..
Answering these questions helps me navigate those hefty 40- or 50-page papers with much more ease. Usually, the “core” of a paper boils down to a very specific idea. Often, that idea is simple, and the rest of the work is about proving it or wrapping it up in a way that delivers a more complete system or story. For example, a paper about running a zero-knowledge prover with multi-party computation (MPC) might boil down to a single clever trick on how to efficiently divide the multi-scalar multiplication (MSM) primitive between two parties. The rest is mostly repeating known results to ensure a full ZK protocol can run in the same MPC setup.
Getting into the author’s mind is an art, but when it works, it turns a paper into a story — a reflection of the author’s struggles and victories on their journey to a finished work. I believe that good papers should be written with this narrative in mind.
Here’s My Take on How the Circle STARK Paper Came to Be
STARKs are incredibly powerful.
The Mersenne prime with 31 bits, often referred to as M31, has unique properties that make it exceptionally attractive. However, using M31 as the base field for STARKs isn’t efficient because M31 has a low 2-adicity, meaning we can’t use the Fast Fourier Transform (FFT) directly — and FFTs are crucial for STARK performance in areas like low-degree extensions (LDEs) and Reed-Solomon (RS) code evaluations.
The authors of the Circle STARK paper were trying to tackle this problem. They wanted a transform similar to FFT that takes elements from the M31 field and outputs elements in the same field. Their first key observation was that while M31 doesn’t have a high enough order of 2, its first field extension does. The rest of the paper is dedicated to developing the required FFT-like transform. The end result is a new transform with the essential 2:1 folding property, enabling STARKs to work over M31 and achieve significant efficiency gains. The paper involves some pretty complex mathematical gymnastics to achieve this novel result.
So Far, So Good, So What
But here’s the thing: the new transform is FFT-like, but it’s not the FFT we know and love. For example, we don’t yet know if there’s a way to support radices larger than 2. When we implement FFTs in hardware, we rely on higher-order radices because they help us save on memory — which is the bottleneck we’re always trying to avoid with FFTs.
Yuval’s paper tells a different story. Yuval is the lead author of our textbook on NTTs, and his work feels like he pulled a few pages straight from that book. His paper doesn’t present a novel idea; instead, it constructs an FFT based on concepts that have been known for decades. Essentially, the paper presents an FFT over the complex field. The main breakthrough is identifying the right symmetry in the problem, allowing the evaluations (or coefficients) to come from the real numbers — in this case, the elements of M31.
This leads to a straightforward integration into a STARK system, replacing the Circle STARK transform almost one-to-one. The complexity is roughly the same as in the Circle STARK approach, but now we can immediately leverage existing hardware optimizations for efficient memory management, thanks to the massive amount of work that’s been put into FFTs over the past 50 years.
To add some color, the table below, taken from the paper, shows that the number of multiplications for Circle STARK (left column) is comparable to the number of multiplications with our FFT (rightmost column). Refer to section 6 in the paper for a full analysis.
Important note: I oversimplified what it takes to go from our new RC-Code to a full production ready STARK like Stwo. I also downplayed the genius in Yuval’s work. My goal is just to make a point ❤️.
Takeaway
In his book Skunk Works: A Personal Memoir, Ben Rich quotes his predecessor, Kelly Johnson, saying, “Planes that look beautiful fly beautiful.” This sentence captures a profound truth: aerodynamics obey the laws of physics. Physics describes nature and is encoded through mathematics. Math is elegant, and so are airplanes. The same goes for science. Just think about the elegance of Maxwell’s equations. The FFT is another example — it’s often the first algorithm taught in any algorithms class or book. It has a certain beauty and is incredibly powerful. Our work is not groundbreaking, Circle STARK is. Our work is effective: we leverage symmetries in the problem to keep STARK classy, even with the challenges introduced by M31.
When I say this is worth your attention, I mean it embodies in the most perfect way what we are here to do: ZK. Effective.
Needless to say, this work was not possible without the support of @StarkWareLtd and @StarknetFndn.
