Roots of Unity

Welcome back, fellow zk-enjoyer.

In the last post, we used polynomials as a data structure and verified them with a single number (Schwartz-Zippel, remember?). But there’s a question that should be bugging you: “how do we do this efficiently?”

The answer is called “roots of unity.” I promise the idea is simpler than the name suggests, and it’s what makes ZK proofs better (about 50,000 times better, for a typical ZK circuit, terms and conditions may apply [TM]).

---

The Road Map

1. Polynomials over finite fields
2. Roots of unity ← you are here
3. Execution trace
4. Polynomial interpolation via FFT/NTT
5. Applying constraints to polynomials
6. Packing into a single polynomial
7. Commitment scheme (starting with KZG)
8. Proof AND Verification

---

Why Are There Two Ways to Store a Polynomial?

Before we get to roots of unity, you need to see the problem they solve.

You can represent a polynomial in two different ways.

Coefficient form is what you already know: store the coefficients as a vector. $P(x) = 1 + 2x + 3x^2$ becomes [1, 2, 3]. Adding two polynomials is cheap: add the vectors element by element, $O(N)$. But multiplying them? Every coefficient of P has to multiply with every coefficient of Q. That’s $O(N^2)$.

Evaluation form stores what the polynomial outputs at N chosen points. Instead of storing the recipe (coefficients), you store the dishes already cooked: $[P(x_0), P(x_1), \ldots, P(x_{n-1})]$. Think of it as a lookup table. You don’t know the formula, but you know what it produces at each point. Now multiplying two polynomials is trivial: just multiply the values at each point, $O(N)$.

Think of it like a coin. Coefficient form and evaluation form are two views of the same polynomial. Each view makes a different operation cheap: coefficients for addition, evaluations for multiplication. The catch is flipping the coin.

Flipping from coefficients to points is evaluation: plug N points into the polynomial, $O(N^2)$. Flipping back is interpolation: find the polynomial that passes through N given points, also $O(N^2)$.

For our 8-coefficient polynomial, that’s $8^2 = 64$ multiplications per flip. Fine. But real ZK circuits use $N = 2^{20}$ coefficients (about a million). Each flip costs $(2^{20})^2 = 2^{40}$: roughly a trillion field multiplications. The flips are the bottleneck.

Unless you pick the right evaluation points.

---

So What Are Roots of Unity?

For the 8 roots of unity, you start with a number $\omega$ (omega). Then $\omega^0 = 1, \omega^1, \omega^2, \ldots, \omega^7$ gives you 8 distinct values, and $\omega^8 = 1$ again.

The animations show this on the complex plane, where roots of unity sit on a circle and multiplying by $\omega$ is a visible rotation. That’s the intuition.

In a finite field, there’s no circle: $\omega$ is a single integer (a big one), and “multiply by $\omega$” is just modular multiplication. Nothing rotates. But the algebra is the same: N distinct values that cycle back to 1, with identical symmetries. The circle helps you see the structure. The code below is how roots of unity actually look in ZK.

But in many zkSNARK frameworks and libraries you will see a thing named omega and an operation called rotation. This makes no sense for integers. The name comes from the complex plane, where it does make sense. This is why those operations and primitives are named that way.

Click Run.

Those numbers are huge (welcome to finite fields), but the punchline is at the bottom: $\omega^0$ and $\omega^8$ are the same value. The cycle is the same as in the complex plane, and it also has exactly 8 distinct values.

One more thing, and this one matters later. The polynomial $z^8 - 1$ equals zero at every root of unity. That gives us a way to check constraints across all rows of a trace at once (post #5). Here’s why it works.

The “root” in “root of unity” means the same as in “root of an equation”: a number that makes the equation equal zero. Every root of unity satisfies $\omega^8 = 1$, or equivalently $\omega^8 - 1 = 0$. Not just one $\omega$, but every root:

$$\begin{gathered} (\omega^0)^8 = 1 \\ (\omega^1)^8 = 1 \\ (\omega^2)^8 = 1 \\ \vdots \\ (\omega^7)^8 = 1 \end{gathered}$$

That's the definition. Why? Because you can reorder the exponents:

$$(\omega^2)^8 = (\omega^8)^2 = 1^2 = 1$$

So $z^8 - 1$ has all eight roots of unity as its roots. No matter which $\omega^k$ you plug in, you get 0. We can also use these roots as the x coordinates for encoding data into polynomials, instead of picking points by hand like we did in post #1.

---

How Does This Speed Things Up?

Take a polynomial $P(x)$ and split it by even and odd coefficients:

$$P(x) = P_{\text{even}}(x^2) + x \cdot P_{\text{odd}}(x^2)$$

For example, take a degree-7 polynomial with 8 coefficients:

$$P(x) = 3 + 1x + 4x^2 + 1x^3 + 5x^4 + 9x^5 + 2x^6 + 6x^7$$

Pull out the even-index coefficients (positions 0, 2, 4, 6) and the odd-index coefficients (positions 1, 3, 5, 7):

$$\begin{aligned} P_{\text{even}}(y) &= 3 + 4y + 5y^2 + 2y^3 \\ P_{\text{odd}}(y) &= 1 + 1y + 9y^2 + 6y^3 \end{aligned}$$

Plug in $y = x^2$ and recombine:

$$P(x) = \underbrace{(3 + 4x^2 + 5x^4 + 2x^6)}_{P_{\text{even}}(x^2)} + x \cdot \underbrace{(1 + 1x^2 + 9x^4 + 6x^6)}_{P_{\text{odd}}(x^2)}$$

One degree-7 polynomial just became two degree-3 polynomials. Each of those can be split the same way. Split $P_{\text{even}}$ by its even/odd coefficients:

$$\begin{aligned} P_{\text{even\_even}}(y) &= 3 + 5y \\ P_{\text{even\_odd}}(y) &= 4 + 2y \end{aligned}$$

And split $P_{\text{odd}}$ the same way:

$$\begin{aligned} P_{\text{odd\_even}}(y) &= 1 + 9y \\ P_{\text{odd\_odd}}(y) &= 1 + 6y \end{aligned}$$

Four degree-1 polynomials. Split once more. Each has two coefficients, so the split produces eight degree-0 polynomials:

$$\begin{aligned} P_{\text{even\_even\_even}}(y) &= 3 &\qquad P_{\text{even\_even\_odd}}(y) &= 5 \\ P_{\text{even\_odd\_even}}(y) &= 4 &\qquad P_{\text{even\_odd\_odd}}(y) &= 2 \\ P_{\text{odd\_even\_even}}(y) &= 1 &\qquad P_{\text{odd\_even\_odd}}(y) &= 9 \\ P_{\text{odd\_odd\_even}}(y) &= 1 &\qquad P_{\text{odd\_odd\_odd}}(y) &= 6 \end{aligned}$$

Eight constants. “Evaluation” of a degree-0 polynomial is just returning the number. That's the base case.

If you’re lost in the subscripts: that’s normal. We’re doing one thing: splitting a big problem into smaller identical problems. Like merge sort, but for polynomials. $P_{\text{even\_odd}}$ just means “take the even half, then the odd half of that.” The name tracks the path down the tree.

The full cascade: $8 \to 4 \to 2 \to 1$ coefficients per sub-polynomial, $\log_2(8) = 3$ levels of splitting.

Now the computation runs in reverse, from the bottom up. At each level, the butterfly combines two values $a$ and $b$ into $a + \omega^k \cdot b$ and $a - \omega^k \cdot b$.

That $\omega^k$ multiplier changes at each level. At Level 1 it’s just 1, so the butterfly simplifies to plain $a + b$ and $a - b$. At Level 2 it alternates between $1$ and $\omega^2$. At Level 3 it cycles through $1, \omega, \omega^2, \omega^3$. This multiplier has a name: twiddle factor. Just a power of $\omega$ that gets more varied as you go up.

The next three sections walk through the butterfly computation level by level. If you trust the pattern after Level 1, you can skip to the result.

Level 1: evaluate degree-1 polynomials at 2nd roots ($\omega^k = 1$)

$$\begin{aligned} P_{\text{even\_even}}(\omega^0) &= 3 + 1 \cdot 5 = 8 &\qquad P_{\text{even\_even}}(\omega^4) &= 3 - 1 \cdot 5 = -2 \\ P_{\text{even\_odd}}(\omega^0) &= 4 + 1 \cdot 2 = 6 &\qquad P_{\text{even\_odd}}(\omega^4) &= 4 - 1 \cdot 2 = 2 \\ P_{\text{odd\_even}}(\omega^0) &= 1 + 1 \cdot 9 = 10 &\qquad P_{\text{odd\_even}}(\omega^4) &= 1 - 1 \cdot 9 = -8 \\ P_{\text{odd\_odd}}(\omega^0) &= 1 + 1 \cdot 6 = 7 &\qquad P_{\text{odd\_odd}}(\omega^4) &= 1 - 1 \cdot 6 = -5 \end{aligned}$$

All additions and subtractions. The twiddle factor at this level is just 1.

Still with me? Good. Same operation at every level, just b multiplier changes.

Level 2: combine Level 1 results into degree-3 polynomials (twiddle factors: $1$ and $\omega^2$)

Same butterfly as Level 1, one difference: the twiddle factor is no longer always 1.

$$\begin{aligned} P_{\text{even}}(\omega^0) &= 8 + 1 \cdot 6 = 14 &\qquad P_{\text{even}}(\omega^4) &= 8 - 1 \cdot 6 = 2 \\ P_{\text{even}}(\omega^2) &= -2 + \omega^2 \cdot 2 &\qquad P_{\text{even}}(\omega^6) &= -2 - \omega^2 \cdot 2 \end{aligned}$$ $$\begin{aligned} P_{\text{odd}}(\omega^0) &= 10 + 1 \cdot 7 = 17 &\qquad P_{\text{odd}}(\omega^4) &= 10 - 1 \cdot 7 = 3 \\ P_{\text{odd}}(\omega^2) &= -8 + \omega^2 \cdot (-5) &\qquad P_{\text{odd}}(\omega^6) &= -8 - \omega^2 \cdot (-5) \end{aligned}$$

Same butterfly, but now the twiddle factor alternates between $1$ and $\omega^2$. Where it's 1, we get clean numbers. Where it's $\omega^2$, the expression stays symbolic, but in a finite field $\omega$ is a concrete integer, so these all resolve to specific values.

Level 3: combine Level 2 results into the full degree-7 polynomial (twiddle factors: $1$, $\omega$, $\omega^2$, $\omega^3$)

Last level. Four different twiddle factors now, but the operation is still the same: $a + \text{twiddle} \cdot b$ and $a - \text{twiddle} \cdot b$.

$$\begin{aligned} P(\omega^0) &= 14 + 1 \cdot 17 = 31 &\qquad P(\omega^4) &= 14 - 1 \cdot 17 = -3 \\ P(\omega^1) &= P_{\text{even}}(\omega^2) + \omega \cdot P_{\text{odd}}(\omega^2) &\qquad P(\omega^5) &= P_{\text{even}}(\omega^2) - \omega \cdot P_{\text{odd}}(\omega^2) \\ P(\omega^2) &= 2 + \omega^2 \cdot 3 &\qquad P(\omega^6) &= 2 - \omega^2 \cdot 3 \\ P(\omega^3) &= P_{\text{even}}(\omega^6) + \omega^3 \cdot P_{\text{odd}}(\omega^6) &\qquad P(\omega^7) &= P_{\text{even}}(\omega^6) - \omega^3 \cdot P_{\text{odd}}(\omega^6) \end{aligned}$$

All eight evaluations, four twiddle factors. Each line: left and right share the same computation, the right just flips the sign.

If you made it through those three levels, you just survived the hardest part of this post. Everything after this is downhill.

Why “butterfly”? Look at each crossing in the diagram below: two lines cross and diverge, like a pair of wings. If you squint hard enough, you can see it. It would be a shame to waste such a cool name.

Here’s the full butterfly for our polynomial. On the left: coefficients a₀ through a₇ (shuffled by the even/odd splitting). On the right: the polynomial evaluated at each root of unity, P(ω⁰) through P(ω⁷).

The pattern widens at each stage: stage 1 combines adjacent pairs (blue), stage 2 reaches across two (orange), stage 3 across four (green). At every crossing, two inputs produce two outputs. Same computation, just + and −.

For our 8-coefficient polynomial, that's 3 stages of 8 operations each. $N \times \log_2 N$ total instead of $N^2$. That's $O(N \log N)$ vs $O(N^2)$.

Here's the full cascade: all 8 roots of unity, squaring down level by level. Each level, paired roots produce the same squared value, halving the distinct values.

Three levels of halving, so half the computation at each level is shared with the level above.

Here's the math for a real ZK domain:

$N = 2^{20}$ (1,048,576 points, a common circuit size):

$$\begin{aligned} \text{Naive:} &\quad N^2 = 2^{40} \approx 1.1 \text{ trillion field multiplications} \\ \text{NTT:} &\quad N \times \log_2 N = 2^{20} \times 20 \approx 21 \text{ million} \\ \text{Speedup:} &\quad \sim 50{,}000 \times \end{aligned}$$

$N = 2^{25}$ (≈ 33 million points, large production circuits):

$$\begin{aligned} \text{Naive:} &\quad N^2 = 2^{50} \approx 10^{15} \\ \text{NTT:} &\quad N \times \log_2 N = 2^{25} \times 25 \approx 839 \text{ million} \\ \text{Speedup:} &\quad > 1{,}000{,}000 \times \end{aligned}$$

Here are both approaches side by side, step by step, counting every field multiplication. First, the naive way: for each root of unity, walk all coefficients and compute $P(x) = a_0 + a_1 x + a_2 x^2 + \ldots$ Click Run.

Now the same polynomial, same roots, but using the butterfly. Split into even/odd, recurse, combine with + and -. Count the multiplications.

Same results, different cost. For $N = 8$ the naive approach uses 127 field multiplications, the butterfly uses 17. That’s already 7x fewer, and the ratio keeps growing with $N$.

Roots of unity turn $O(N^2)$ into $O(N \log N)$. For a real ZK circuit with a million points, that’s the difference between “takes a year” and “takes a second.”

This algorithm is the Fast Fourier Transform (FFT). When it runs over finite fields instead of complex numbers, it’s called the Number Theoretic Transform (NTT). Same structure, same recursion, just different arithmetic.

One more thing: the recursive halving needs to split cleanly at every level ($N \to N/2 \to N/4 \to \cdots \to 1$). That only works if $N$ is a power of two.

This is why every ZK framework uses domain sizes like $2^{16}$ (65,536) or $2^{20}$ (1,048,576). This is consequence of the algorithm. When a ZK tutorial says “pad your trace to a power of two,” now you know why. You can see that in execution trace post.

The field itself also needs to support this: $p - 1$ must be divisible by large powers of 2 so the recursive halving has room to work. This is called “2-adicity.”

BN254 has a 2-adicity of 28, meaning it supports NTT domains up to $2^{28}$ (about 268 million points). Plenty for most ZK circuits.

---

Let's See It Work

Enough theory. Let's use roots of unity for what they're actually for in ZK.

Remember post #1? We stored data inside a polynomial by choosing x values and evaluating.

Roots of unity give us those x values for free: $\omega^0, \omega^1, \ldots, \omega^{n-1}$. You assign each data value to a root, run the inverse NTT, and out come the polynomial's coefficients. That's interpolation in $O(N \log N)$.

This is what a ZK prover does with the execution trace to get the data in polynomial form (next post).

The inverse NTT took four ASCII values and found a polynomial that encodes them. We verified it the old-fashioned way: by calling evaluate() at $\omega^0, \omega^1, \omega^2, \omega^3$ and getting back 99, 111, 111, 108. Same evaluate() from post #1, but now the x values are roots of unity instead of arbitrary numbers.

The EvaluationDomain trait covers more operations beyond FFT/iFFT, but these two are the core.

---

What You Just Did

You generated roots of unity over a finite field, saw why their symmetry enables $O(N \log N)$ evaluation, and used the inverse NTT to interpolate a polynomial from raw data. Same evaluate() from post #1, but with roots of unity as the x values.

“Roots of unity”? It is just another name. “Unity” means 1 (the multiplicative identity), “roots” means solutions to an equation. So the whole thing literally means “solutions to $z^n = 1$.”

Leonhard Euler studied them in 1751 in Recherches sur les racines imaginaires des équations. Carl Friedrich Gauss wrote 74 pages formalizing the theory in 1801 in Disquisitiones Arithmeticae, Section VII. The name comes from their work. Now you've used the tool behind it.

---

Next Up: Execution Trace

We have our fast polynomial engine. Now: how do we represent an actual program, with all its steps and state, as polynomials?

That's the execution trace. See you there.

If you want to discuss this with other Rust devs learning ZK, join the Discord.

---

Playground

This editor is interactive. Copy code from above, modify it, break it, experiment. Try generating the 16th roots of unity. Or change the data values and check if interpolation still works.

---

What stuck with me the most: when I first saw $\omega$ and “rotation” in ZK code, I had no idea what was going on. It felt like geometry, not finite fields.

In geometry, Greek letters usually name angles, and rotating by angle $\omega$ makes perfect sense. In integers modulo a prime? Not so much.

But then I started looking for roots of unity in other places in mathematics and found them in FFT. And I figured out that (yet again) these are just names. They convey some meaning, but they're also misleading if you take them literally. When you know the origin story, it kinda makes sense why they're called roots of unity even for finite fields.

Questions? Found a bug? Hit me up on Discord. Code should work: if it doesn't, that's on me to fix.