Category: Uncategorized

Welcome, fellow zk-enjoyer.

If you’ve been following along, you know how polynomials work as a data structure and why roots of unity make evaluating them fast. Now the question: before the polynomial checks anything, where does the data come from?

This is post #3 in the “first principles” ZK series:

1. Polynomials and finite fields
2. Roots of unity
3. Execution traces ← you are here
4. FFT/NTT interpolation
5. Constraints
6. Polynomial packing
7. KZG commitment
8. Proof and verification

---

You already know how to do this

Here’s a function you’ve written a hundred times:

fn is_valid_age(x: u32) -> bool {
    x >= 18 && x <= 90
}

The CPU runs it, checks the condition, returns true or false. The result is immediate. You trust the machine.

This isn’t hypothetical. Poland’s digital ID (e-dowód) on mobile phones could generate exactly this kind of proof: a hotel checks you’re 18+ from a QR code without seeing your birth date. The circuit behind it is a range check like the one we’re building here. (More on real-world ZK use cases in the Kraków meetup Q&A.)

Now imagine you need to prove to someone that this returned true for a specific value of x, without revealing x. The verifier can’t run your code on your private inputs. They get a proof, a small piece of data, and they verify it mathematically.

To produce that proof, you need an execution trace.

---

What is an execution trace?

An execution trace is a table. Each row captures a value that was relevant to your computation. You fill it in while running the program, before any proving happens.

For is_valid_age(45), the two conditions x >= 18 and x <= 90 get rewritten as subtractions: x - 18 (should be non-negative if x >= 18) and 90 - x (should be non-negative if x <= 90). This rewriting is part of translating code into polynomials. It’s usually the hardest part of writing circuits, because the equations have to catch every corner case and enforce the same conditions as the original code. More on how constraints work in later posts. For now, these are the values we track:

step	value
x	45
x – 18	27
90 – x	45

That’s it. You’re writing down every intermediate value so a polynomial can encode them later. The polynomial doesn’t execute your logic. It encodes this table, and constraints check that the numbers are consistent.

OK, so we rewrote the comparison from the if as subtractions. But we still need to check that the result is non-negative, which looks like the same kind of check we started with. It is, almost, but not quite.

---

Why not just compare directly?

This is where your intuition will fight you. In finite fields, there are no negative numbers, everything wraps around. If this section feels weird, that’s normal, read it slowly.

Think of a car odometer that only goes to 999,999. Drive one more mile past that and it shows 000,000, not 1,000,000. Try to go backwards from 000,000 and you get 999,999, not -1.

ZK proofs operate over finite fields, which work the same way but with a much bigger odometer. Every number is in the range [0, p-1] and arithmetic wraps around. There is no concept of “greater than” or “less than” in the strict sense.

This means x - 18 >= 0 is meaningless. If x = 5, then x - 18 doesn’t equal -13. It equals p - 13, which is a large positive-looking number:

Click Run. Both results look nonnegative, the field can’t tell them apart by sign.

So at this point it looks like rewriting comparisons as subtractions and checking for non-negative results was completely pointless. In a finite field every result looks non-negative. Bear with me, we’re getting there. (If you want more on why circuits only speak addition and multiplication, see Q4 in the meetup Q&A.)

---

Do you even range-check?

You use bit decomposition.

Wait what???

Yes, we’re counting bits. Like it’s 1975. Welcome to cryptography.

You take the result of the subtraction and break it down into bits. If it fits in k bits, you know it’s a small number. If it doesn’t fit, it’s huge (because the finite field wrapped it around, and those wrapped numbers are huuuge), and the check fails. That’s it. 8 bits can hold 0 to 255, so if x – 18 fits in 8 bits, x is somewhere between 18 and 273.

One check isn’t enough. You need two: one for the lower bound (x - 18 fits in k bits, so x >= 18) and one for the upper bound (90 - x fits in k bits, so x <= 90). Both together prove x is between 18 and 90. That’s why the trace ends up with two bit decompositions, one per bound.

The gap between 18 and 90 is 72, so 8 bits is more than enough (8 bits can hold up to 255). But each check alone has a range that is too wide:

• col_lower alone accepts x from 18 up to 273 (because x – 18 just needs to fit in 8 bits)
• col_upper alone accepts x from -165 up to 90 (because 90 – x just needs to fit in 8 bits)
• both together accept only x from 18 to 90

Try x = 91 (one above the upper bound). col_lower: 91 – 18 = 73, fits in 8 bits, passes. col_upper: 90 – 91 = p – 1, a ~254-bit number, does not fit in 8 bits, fails. The lower check alone would have let x = 91 through. You need both.

Try x = 17 (one below the lower bound). col_upper: 90 – 17 = 73, fits, passes. col_lower: 17 – 18 = p – 1, does not fit in 8 bits, fails.

Click Run. For x = 91, the lower check gives 73 (small, fits in 8 bits), but the upper check wraps around to a ~254-bit number. For x = 17, it’s the other way around. Those giant numbers will never fit in 8 bits.

Here’s why that’s a hard constraint, not just a flag. To prove a k-bit decomposition, the prover has to provide k individual bits, each either 0 or 1, that add up to the original value when weighted by powers of two. For 27 that looks like:

1·1 + 1·2 + 0·4 + 1·8 + 1·16 + 0·32 + 0·64 + 0·128 = 27

Wait, wait, stop. Do you see what this is? Do you see it?

The most you can reach with 8 bits is 1+2+4+8+16+32+64+128 = 255. If the value is 256 or more, no combination of 0s and 1s adds up to it. So we effectively have a non-negative check that works over a finite field, in the form of a polynomial: if the number is genuinely small (a valid subtraction result), it can be represented as the polynomial above. If the field wrapped it around into a giant number, it can’t.

There’s one more thing needed: a constraint that forces each bit to actually be 0 or 1, not some other field element. More on that in the constraints post.

---

The full trace

Now you can see why the trace looks the way it does. For is_valid_age(45), the trace has three columns. col_x holds the secret value. col_lower and col_upper hold the subtraction results and their bit decompositions. Without col_x in the trace, there would be no way to prove that col_lower[0] actually equals x - 18 and not some arbitrary number.

row	col_x	col_lower (x-18)	col_upper (90-x)
0	45	27	45	← values
1	0	1	1	← b0
2	0	1	0	← b1
3	0	0	1	← b2
4	0	1	1	← b3
5	0	1	0	← b4
6	0	0	1	← b5
7	0	0	0	← b6
8	0	0	0	← b7

Row 0 holds the subtraction results. Rows 1 through 8 hold the individual bits. That’s the whole structure.

You didn’t write if. You wrote down what had to be true for the if to pass, for specific case of secret value x.

---

In arkworks: the trace as field elements

Throughout this series we build PLONK by hand using ark-ff, just field arithmetic. Each cell in the trace is a field element.

The snippet below computes the subtraction results and breaks them into bits, the same bit decomposition from the previous section, but now in arkworks code. The key line is (n >> i) & 1 inside to_bits_le: it extracts bit i from the number. Everything else is plumbing.

Now we assemble the trace. Each column is a vector: the value in position 0, followed by 8 bits. That’s the whole trace.

Click Run. The output matches the trace table: row 0 holds subtraction related values, rows 1-8 hold bit decompositions.

---

What the trace is for

“OK I built this trace, but what’s it for?”

A common confusion: people think proving IS executing. It’s not. Three separate steps, three different roles:

Step	Who	What	Knows everything?
1. Execute	Prover	Runs program, fills the trace	Yes, all inputs/outputs/steps
2. Prove	Prover	Turns completed trace into a proof	Yes, but hides the secrets
3. Verify	Verifier	Checks the proof	No, sees only proof + public inputs

The constraints don’t walk through the trace row by row, discovering what happens next. The full trace is already there. They just check that all the numbers are consistent.

---

One thing to take away from this post: the prover doesn’t prove by re-running your code. The prover fills in a table, and the math checks that the table is consistent. Execution first, proof second. Always.

Next up

Post #4, FFT/NTT interpolation: how to turn this table into polynomials. And do some cool stuff with it.

Coming soon.

The FFT/NTT algorithm is covered in Roots of Unity.

---

Playground

This editor is interactive. Copy code from above, modify it, break it, experiment. Try changing x to a value outside [18, 90] and see how the trace changes.

---

If you have questions or want to discuss this post, join the ZK for Rust Devs Discord.

---

This is post #3 in the “first principles” ZK series on rustarians.com.

(more…)

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.

Welcome, fellow zk-enjoyer.

You’ve spent evenings staring at tutorials that don’t compile, explanations that assume you have a PhD in algebra, and AI-generated content that looks legit until you run the code.

I’ve been in blockchain since 2016. I’ve written production zk code. This guide teaches polynomials the way I wish someone taught me.

No PhD required. Code that runs. Let’s go.

(more…)