home for rusting ppl

Roots of Unity

Written by

admin

in

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 this is ← here
  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 [1, 2, 3], you store $[P(x_0), P(x_1), \ldots, P(x_{n-1})]$. 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 evaluation at multiple points, evaluations form for addition and 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 $N = 2^{20}$ coefficients (a common ZK domain size), each flip costs $(2^{20})^2 = 2^{40}$: about a trillion multiplications. Evaluation form is where the heavy operations happen, but the flips are the bottleneck.

Unless you pick the right evaluation points.

So What Are Roots of Unity?

The 8-pointed Star of Chaos from Warhammer
They are just fancy Chaos star. Change my mind.
On the complex plane, multiplying by $\omega$ rotates a point 45° around the unit circle. After 8 steps, the cycle wraps: $\omega^8$ lands back on $\omega^0$. In a finite field, nothing visually rotates, but the algebraic cycle is the same.

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.

There's one more thing to see here. 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$$

This will matter later: the polynomial $z^8 - 1$ has all eight roots of unity as its roots, which means that no matter what $\omega$ you put into that equation, you will always get 0.

That fact gives us a way to check constraints across all roots at once, and of course we can use roots of unity as the x coordinate for encoding our data, instead of one by one (post #5).

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.

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$.

The $\omega^k$ multiplier is called the twiddle factor: it's just a power of $\omega$ that changes at each level. At the first level it's 1, so the butterfly simplifies to plain $a + b$ and $a - b$:

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.

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

$$\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$)

$$\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. That's the butterfly: same work, two outputs.

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 diagram for our polynomial. The inputs enter in bit-reversed order, a direct result of the recursive even/odd splitting:

Stage 1 Stage 2 Stage 3 3542 1916 a₀a₄a₂a₆ a₁a₅a₃a₇ 8 −2 6 2 10 −8 7 −5 14 −2+2ω² 2 −2−2ω² 17 −8−5ω² 3 −8+5ω² P(ω⁰)=31P(ω¹) P(ω²)P(ω³) P(ω⁴)=−3P(ω⁵) P(ω⁶)P(ω⁷) 1 1 1 1 1 1 1 1 Peven_even Peven_odd Podd_even Podd_odd Peven Podd P 1 1 ω² ω² 1 1 ω² ω² 1 1 ω ω ω² ω² ω³ ω³ Each crossing: top = a + ωᵏ·b, bottom = a − ωᵏ·b

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)$.

Why does the halving work? On the complex plane you can see it: $\omega^1$ and $\omega^5$ sit opposite each other on the circle, so squaring both gives the same result: $(\omega^1)^2 = (\omega^5)^2 = \omega^2$. Eight roots collapse to four distinct squared values, four to two, two to one. The code below shows this cascade in a finite field, where there's no circle but the algebra is the same.

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$.

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, 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). Not an arbitrary design choice.
When a ZK tutorial says “pad your trace to a power of two,” this is for efficiency. We'll talk about traces in the next 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.