Forem: Adam

10 Questions from a ZK Meetup in Krakow

Adam — Tue, 10 Mar 2026 11:22:52 +0000

Original version with full formatting on rustarians.com.

I gave a talk about halo2 at a Rust meetup in Krakow. The audience asked 10 questions I didn't have time to answer properly on stage, so I wrote them up.

Questions

Where would I actually use this?
How does an execution trace work if you don't know the next row?
Where do I start learning?
Why only addition and multiplication?
How would mObywatel work with ZK?
Can I use bounds larger than 8 bits?
Can you formally prove a circuit is correct, e.g. with Lean?
Is this a SNARK or a STARK?
ZK in electronic voting
Is ZK verification cost-effective on-chain?

#1 "I'm missing a real use case. I don't know where I'd use this."

Two people asked for the same thing: show me a real-world example, not an abstract circuit.

You're checking into a hotel. They need to verify your ID belongs to an adult. In Poland there are ID cards issued to minors (dowod osobisty dla osoby niepelnoletniej), and you can't tell from the document number alone whether the holder is 18+.

With a ZK proof, the hotel verifies: "this person has a valid government-issued ID, and the date of birth in that ID satisfies age >= 18." The hotel sees yes or no. No date of birth, no name, no document number.

This is a range check: prove that (current_date - date_of_birth) >= 6570 days without revealing date_of_birth. Range checks are one of the most basic operations you can build in a circuit (see question #6 for how they work), and age verification is one of the most practical applications.

Technically: you have your digital ID (e-dowod) on your phone. At check-in the phone generates a ZK proof locally and presents it as a QR code. The hotel scans the code, verifies the proof, gets the yes/no answer. Everything happens locally, no server required.

This isn't theoretical. The EU Digital Identity Wallet (eIDAS 2.0) is designed to support exactly this kind of selective disclosure. mObywatel 3.0 is planned for late 2026 as part of this framework (more on mObywatel in question #5).

#2 "How can I know what's in the next row of the execution trace if I'm only at the current one?"

This is the most common confusion: people think proving IS executing. It's not. These are two separate steps.

First, you do the execution. The prover takes the program, runs it on the inputs, and records every intermediate value into a table. That table is the execution trace. At this point the prover knows everything: every input, every output, every step.

Then you do the proving. The prover takes the completed trace with all constraints and turns it into a proof. You don't need to "know the next row" during proving, because the full trace is already there.

(The original post includes the full execution trace table from my talk slides, showing a range check for proving that 42 is between 10 and 100 by decomposing the differences into bits.)

#3 "Do I need to learn the fundamentals first, and where?"

Best book to start: "Proofs, Arguments, and Zero-Knowledge" by Justin Thaler. People in the audience were taking photos when I showed it.

You don't need to read the whole thing. Chapters 1-4 give you the foundation: randomized algorithms, interactive proofs, and the sum-check protocol. Polynomial commitments come later (chapters 14-16), but without the foundation from 1-4 the rest won't make sense.

If you'd rather skip the book: my posts on rustarians.com start from zero (polynomials, roots of unity, execution traces) and include interactive code.

#4 "Why can't I just use a comparison? Why only multiplication and addition?"

Because a circuit is not a program. In regular code you have if, else, comparisons, loops. In an arithmetic circuit the building blocks are addition and multiplication over field elements. In PLONKish systems like halo2 you can define custom gates, which combine multiple additions and multiplications into a single constraint (e.g. a * (b + c) = d in one gate). But the building blocks are still the same.

Why can't you just compare? You might think it's because finite fields have no ordering. But even over integers (which do have ordering), you'd have the same problem: comparison is not a polynomial operation. You can't write a < b as a polynomial equation. And every constraint ultimately has to be a polynomial, because that's what fits into the polynomial commitment scheme that makes the proof work.

So you decompose comparisons into operations the circuit can express. For example, a < 256 becomes: check that a fits in 8 bits. You take a, decompose it into bits (b0, b1, ..., b7), check that each bit is 0 or 1 (bit * (1 - bit) == 0), and that the sum b0 + 2*b1 + 4*b2 + ... + 128*b7 == a. All additions and multiplications. The proof boils down to: the number can be expressed as a polynomial encoding its bits, and that polynomial satisfies all the constraints.

#5 "How would mObywatel work with ZK?"

Same use case as question #1, but now the question is how to build it. You have a digital ID on your phone (mObywatel). You want to prove you're 18+ without revealing your date of birth or any other personal data.

The prover (your phone) puts three things into the circuit: your certificate from mObywatel, the government's public key, and the age constraint (age >= 18). The circuit verifies the signature on the certificate, extracts the date of birth, checks the constraint, and produces a proof.

The verifier (the hotel) takes three things: the proof, the government's public key, and the same age constraint. That's it. No certificate, no personal data, just the proof and the public inputs.

If I were building this, I'd use Schnorr or EdDSA for the document signature, not RSA. Schnorr verification in a ZK circuit costs ~10-11k constraints, RSA-2048 costs ~536k, roughly 50x more. The choice of cryptographic primitives matters in ZK: pick the wrong ones and your proof size and proving time explode.

#6 "Can I use bounds larger than 8 bits in the example?"

Yes, but the cost grows linearly with the number of bits. 8 bits = 8 bit decomposition gates + 1 for the sum. And for a range check you need two decompositions: one for the lower bound, one for the upper bound. So 8-bit range = 2 x 8 bit decomposition gates. 16 bits = 2 x 16. 256 bits = 2 x 256.

For large ranges, bit decomposition gets expensive. You can use lookup tables instead: you have a table of allowed values and check whether your value is in the table. halo2 has built-in lookup tables, and for large ranges they're faster than bit decomposition.

#7 "Can you formally prove a circuit is correct, e.g. with Lean?"

Yes, and this is not theory. People already do it on production circuits.

Nethermind built Halva: a framework for formal verification of halo2 circuits in Lean. They used it on Scroll's Keccak-256 circuit and found a critical bug in production.

The same team built CertiPlonk for formalizing the PlonK protocol IOP in Lean, and sp1-lean together with Succinct Labs for verifying chips from SP1 zkVM.

CODA (from UT Austin) uses Coq and verified 77 existing circom circuits. They found 6 new vulnerabilities nobody had noticed before.

Lean has become the dominant proof assistant for ZK. For a comparison of frameworks, see this zkSecurity overview.

This is still expensive though. Each circuit needs a separate proof, and verifying a production circuit takes weeks or months.

What people do when they don't have the budget for formal verification: property-based testing (generate random inputs and check the circuit behaves correctly) + MockProver in halo2 (catches under-constrained circuits during development). Property-based testing won't catch all corner cases, but it's much cheaper than a formal proof and catches most of the obvious bugs.

#8 "Is what you showed a SNARK or a STARK?"

It depends on what you mean by SNARK. halo2 is a proof system based on PLONKish arithmetization with polynomial commitments. Whether it's a "SNARK" depends on which backend you use and how strictly you define the "S."

SNARK stands for Succinct Non-interactive ARgument of Knowledge. "Succinct" means small proof and fast verification. With KZG commitments (used by Scroll, PSE), halo2 is a SNARK: O(1) proof size, O(1) verification, but requires a trusted setup.

With IPA (Inner Product Argument), the proof is O(log n), which is small, but verification requires a linear-time multi-scalar multiplication: O(n). So the proof is succinct, but verification is not. The original Halo paper avoids calling it a SNARK, using "non-interactive argument of knowledge" instead. In practice, people call it a SNARK anyway because the proof is small and the accumulation scheme amortizes the linear verification cost across recursive steps. But strictly speaking: IPA verification is not succinct.

STARK (Scalable Transparent ARgument of Knowledge)

Larger proof (tens of KB)
No trusted setup (transparent)
Quantum-resistant (based on hashes, not curves)
Prover is usually faster for large circuits, but verification is slower and the proof is bigger. That's why RISC Zero wraps its STARK proof in a Groth16 SNARK for on-chain verification

#9 "ZK in electronic voting"

This works through nullifiers. Each voter has a secret key, and from that key and the election ID they compute a hash called the nullifier. If someone tries to vote twice, the same nullifier already exists and the transaction gets rejected, but nobody can tell whose nullifier it is because hashing is one-way. Zcash uses the same mechanism for private transactions and Semaphore uses it for anonymous signaling.

An eVoting system with ZK works like this:

Registration: each eligible voter gets a secret key. Their public key goes into a merkle tree on-chain.
Voting: the voter creates a ZK proof: "my key is in the merkle tree of eligible voters, I vote for option X, here's my nullifier."
Verification: the smart contract checks the proof, checks the nullifier hasn't been used, records the vote.
Counting: votes are public (option A: 47, option B: 53), but who voted for what is hidden.

Projects that do this: MACI (Minimal Anti-Collusion Infrastructure, concept by Vitalik, built by Privacy & Scaling Explorations / Ethereum Foundation, actively developed, v3 on the way), Vocdoni (building DAVINCI, a zkRollup for voting with recursive proofs), and Semaphore-based voting.

The hard part is coercion resistance: how do you guarantee nobody is forcing you to vote a certain way? MACI solves this through key rotation. You can change your key after voting, so even if someone saw your vote, they don't know if you changed it afterwards.

#10 "Is ZK verification cost-effective on-chain?"

General rule: verifying a ZK proof on-chain is cheap (compared to executing the full computation on-chain). Generating the proof is expensive (off-chain, on the prover's CPU/GPU).

Some numbers: a Groth16 verification on Ethereum costs roughly 200k-300k gas depending on the number of public inputs (formula: ~181k + 6k per public input). The underlying ecPairing precompile (EIP-1108) costs 34,000 * k + 45,000 gas where k is the number of pairings. At 5 gwei and ETH at $2,500, that's roughly $3 per verification, less when gas is low.

When ZK makes economic sense:

The computation is expensive on-chain but cheap off-chain (e.g. batch processing 1000 transactions, proved with a single proof)
Privacy has value (user pays a premium for anonymity)
Regulations require privacy (GDPR, personal data)

When ZK does not make sense:

Simple computations (cheaper to execute directly)
You don't need privacy or compression
Latency is critical (proving takes seconds to minutes)

Next Up

I'm turning the meetup demo into a full interactive post: building a range check circuit in halo2, step by step, with runnable code. If you want to go from "I get the concept" to "I can write this," that's the one.

These are questions from the Krakow Rust meetup (27.02.2026). Original post on rustarians.com.

I'm running a free live session on March 17: From Polynomials to Proof in 60 Minutes. If you want to see a range check circuit built step by step, that's where it happens.

Questions? Found a bug? linkedin.com/in/adam-smolarek

Execution Traces: Packing Data for Polynomials

Adam — Tue, 10 Mar 2026 11:16:39 +0000

This post has interactive code editors and animations on the original version where you can run and modify every Rust snippet in the browser.

Execution Traces: Packing Data for Polynomials

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 comes the question everyone skips: before the polynomial checks anything, where does the data come from?

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

Polynomials and finite fields
Roots of unity
Execution traces <- you are here
FFT/NTT interpolation
Constraints
Polynomial packing
KZG commitment
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-dowod) 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 Krakow 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?

Here's where it gets interesting.

ZK proofs operate over finite fields. In a finite field with modulus p, 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 algebraic 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:

fn main() {
    let p: i64 = 101;

    // invalid: x = 5, below lower bound
    // in F_101: 5 - 18 = -13, and -13 mod 101 = 88
    println!("x=5:  x-18 mod p = {}", (5  - 18_i64).rem_euclid(p)); // 88

    // valid: x = 45, inside [18, 90]
    println!("x=45: x-18 mod p = {}", (45 - 18_i64).rem_euclid(p)); // 27
}

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???

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.

use ark_bn254::Fr;

fn main() {
    // x = 91 (one above upper bound)
    let x = Fr::from(91u64);
    println!("x = 91:");
    println!("  x - 18 = {}", x - Fr::from(18u64));       // 73, small
    println!("  90 - x = {}", Fr::from(90u64) - x);       // huge wrapped number
    println!();

    // x = 17 (one below lower bound)
    let x = Fr::from(17u64);
    println!("x = 17:");
    println!("  x - 18 = {}", x - Fr::from(18u64));       // huge wrapped number
    println!("  90 - x = {}", Fr::from(90u64) - x);       // 73, small
}

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

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):

row	col_x	col_lower (x-18)	col_upper (90-x)
0	45	27	45
1	0	1	1
2	0	1	0
3	0	0	1
4	0	1	1
5	0	1	0
6	0	0	1
7	0	0	0
8	0	0	0

col_x is there because without it there's no way to prove that col_lower[0] actually equals x - 18 and not some arbitrary value. Same for col_upper[0] and 90 - x.
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. to_bits_le extracts k least-significant bits from a field element.

fn to_bits_le(val: Fr, k: usize) -> Vec<Fr> {
    let n = val.into_bigint().0[0]; // first u64 limb, valid for small values
    (0..k).map(|i| Fr::from((n >> i) & 1)).collect()
}

let bits_lower = to_bits_le(lower_bound, 8); // [1, 1, 0, 1, 1, 0, 0, 0]
let bits_upper = to_bits_le(upper_bound, 8); // [1, 0, 1, 1, 0, 1, 0, 0]

Now we assemble the trace. Each column holds the value in row 0 followed by its 8 bits.

// each column: [value, b0, b1, b2, b3, b4, b5, b6, b7]
// col_x carries x itself, needed to prove col_lower[0] = x - 18

let col_x:     Vec<Fr> = [vec![x],           vec![Fr::zero(); 8]].concat();
let col_lower: Vec<Fr> = [vec![lower_bound],  to_bits_le(lower_bound, 8)].concat();
let col_upper: Vec<Fr> = [vec![upper_bound], to_bits_le(upper_bound, 8)].concat();

let trace: Vec<Vec<Fr>> = vec![col_x, col_lower, col_upper];

Visualized:

row	col_x	col_lower (x-18)	col_upper (90-x)
0	45	27	45
1	0	1	1
2	0	1	0
3	0	0	1
4	0	1	1
5	0	1	0
6	0	0	1
7	0	0	0
8	0	0	0

What the trace is for

"OK I built this trace, but what's it for?"

Glad you asked.

A common confusion: people think proving IS executing. It's not. These are two separate steps. First, the prover runs the program on the inputs and records every intermediate value into a table, that's exactly what the first snippet in the arkworks section does. That's the execution trace. At this point the prover knows everything: every input, every output, every step.

Then the prover takes the completed trace and turns it into a proof. The constraints don't walk through the execution trace row by row, discovering what happens next. The full trace is already there. They just check that all the numbers are correct. This separation is what allows the verifier to check correctness without re-running the computation.

You pack the data, and the constraints check it. AND you can pack the data if and only if constraints are satisfied.

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.

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

This is post #3 in my "first principles" ZK series for Rust devs. Interactive version with runnable code and animations on rustarians.com.

I'm running a free live session on March 17: From Polynomials to Proof in 60 Minutes. Range check circuit built step by step, with a real use case.

Questions? Found a bug? linkedin.com/in/adam-smolarek

What are Roots of Unity (and why do they matter in ZK)?

Adam — Tue, 10 Mar 2026 11:15:07 +0000

This post has interactive code editors and animations on the original version where you can run and modify every Rust snippet in the browser.

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

Polynomials over finite fields
Roots of unity <- you are here
Execution trace
Polynomial interpolation via FFT/NTT
Applying constraints to polynomials
Packing into a single polynomial
Commitment scheme (starting with KZG)
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), ..., 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 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 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?

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

On the complex plane, 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 operations called rotation. This makes no sense for integers. The name comes from the complex plane, where it does make sense, and that's why those operations and primitives are named that way.

use ark_bn254::Fr;
use ark_ff::FftField;

fn main() {
    // The primitive 8th root of unity for BN254.
    // "Primitive" means: omega^8 = 1,
    // and omega^k != 1 for 0 < k < 8.
    let omega = Fr::get_root_of_unity(8 as u64).expect("Field has this root");

    println!("All 8th roots of unity for BN254:\n");

    let mut current = Fr::from(1); // start at omega^0 = 1
    for i in 0..=8 {
        if i == 8 {
            println!("  omega^{}  = {:?}  <-- back to 1!", i, current);
        } else {
            println!("  omega^{}  = {:?}", i, current);
        }
        current *= omega;
    }
}

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:

(omega^0)^8 = 1
(omega^1)^8 = 1
(omega^2)^8 = 1
...
(omega^7)^8 = 1

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

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

use ark_bn254::Fr;
use ark_ff::{FftField, Field};

fn main() {
    let n: u64 = 8;
    let omega = Fr::get_root_of_unity(n).expect("Field has this root");
    let one = Fr::from(1);

    println!("Every 8th root of unity, raised to the 8th power:\n");

    for k in 0..n {
        let omega_k = omega.pow([k]);       // first: omega^k
        let result = omega_k.pow([n]);      // then: (omega^k)^8
        println!("  (omega^{})^8 = {:?}", k, result);
        assert_eq!(result, one);
    }

    println!("\nAll equal 1. They're all roots of z^8 - 1 = 0.");
}

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_even(x^2) + x * P_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):

P_even(y) = 3 + 4y + 5y^2 + 2y^3
P_odd(y) = 1 + 1y + 9y^2 + 6y^3

Plug in y = x^2 and recombine:

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

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

P_even_even(y) = 3 + 5y
P_even_odd(y) = 4 + 2y

And split P_odd the same way:

P_odd_even(y) = 1 + 9y
P_odd_odd(y) = 1 + 6y

Four degree-1 polynomials. Split once more, each has two coefficients, so the split produces eight degree-0 polynomials (just the constants: 3, 5, 4, 2, 1, 9, 1, 6).

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

The full cascade: 8 -> 4 -> 2 -> 1 coefficients per sub-polynomial, log2(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 * b and a - omega^k * 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)

P_even_even(omega^0) = 3 + 1*5 = 8, P_even_even(omega^4) = 3 - 1*5 = -2
P_even_odd(omega^0) = 4 + 1*2 = 6, P_even_odd(omega^4) = 4 - 1*2 = 2
P_odd_even(omega^0) = 1 + 1*9 = 10, P_odd_even(omega^4) = 1 - 1*9 = -8
P_odd_odd(omega^0) = 1 + 1*6 = 7, P_odd_odd(omega^4) = 1 - 1*6 = -5

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)

P_even(omega^0) = 8 + 1*6 = 14, P_even(omega^4) = 8 - 1*6 = 2
P_even(omega^2) = -2 + omega^2 * 2, P_even(omega^6) = -2 - omega^2 * 2
P_odd(omega^0) = 10 + 1*7 = 17, P_odd(omega^4) = 10 - 1*7 = 3
P_odd(omega^2) = -8 + omega^2 * (-5), P_odd(omega^6) = -8 - omega^2 * (-5)

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)

P(omega^0) = 14 + 1*17 = 31, P(omega^4) = 14 - 1*17 = -3
P(omega^1) = P_even(omega^2) + omega * P_odd(omega^2)
P(omega^2) = 2 + omega^2 * 3, P(omega^6) = 2 - omega^2 * 3

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

(The original post has an interactive SVG butterfly diagram showing the full 8-point FFT with all three stages.)

The pattern widens at each stage: stage 1 combines adjacent pairs, stage 2 reaches across two, stage 3 across four. 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 * log2(N) total instead of N^2. That's O(N log N) vs O(N^2).

Why does the halving work? 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.

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.

use ark_bn254::Fr;
use ark_ff::{FftField, Field};

fn main() {
    let omega = Fr::get_root_of_unity(8 as u64).expect("8th root exists");
    let roots: Vec<Fr> = (0..8).map(|k| omega.pow([k])).collect();

    // Square every root: opposite pairs collapse.
    // 8 inputs -> only 4 distinct squared values.
    println!("8 roots -> square -> 4 distinct values:");
    for k in 0..4 {
        let sq_k   = roots[k] * roots[k];
        let sq_opp = roots[k + 4] * roots[k + 4];
        assert_eq!(sq_k, sq_opp);
        println!("  (omega^{})^2 == (omega^{})^2  check", k, k + 4);
    }

    // Square again: 4 -> 2 distinct values.
    let level1: Vec<Fr> = (0..4).map(|k| roots[k] * roots[k]).collect();
    println!("\n4 values -> square -> 2 distinct values:");
    for k in 0..2 {
        assert_eq!(level1[k] * level1[k], level1[k + 2] * level1[k + 2]);
        println!("  level1[{}]^2 == level1[{}]^2  check", k, k + 2);
    }

    // Once more: 2 -> 1.
    let level2: Vec<Fr> = (0..2).map(|k| level1[k] * level1[k]).collect();
    assert_eq!(level2[0] * level2[0], level2[1] * level2[1]);
    println!("\n2 values -> square -> 1 value  check");

}

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):

Naive: N^2 = 2^40 ~ 1.1 trillion field multiplications
NTT: N * log2(N) = 2^20 * 20 ~ 21 million
Speedup: ~50,000x

N = 2^25 (~33 million points, large production circuits):

Naive: N^2 = 2^50 ~ 10^15
NTT: N * log2(N) = 2^25 * 25 ~ 839 million
Speedup: > 1,000,000x

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

use ark_bn254::Fr;
use ark_ff::FftField;

fn main() {
    let n = 8usize;
    let omega = Fr::get_root_of_unity(n as u64).expect("root exists");
    let coeffs: Vec<Fr> = vec![10, 20, 30, 40, 0, 0, 0, 0]
        .into_iter().map(|v| Fr::from(v)).collect();

    let mut total_muls = 0u64;
    let mut results = Vec::new();
    println!("Naive: evaluate P(x) at each root, one by one");
    println!("(each * = one field multiplication)\n");

    let mut point = Fr::from(1);
    for k in 0..n {
        let mut muls_here = 0u64;
        let mut result = Fr::from(0);
        let mut x_pow = Fr::from(1);
        for j in 0..n {
            result += coeffs[j] * x_pow;
            muls_here += 1;
            if j < n - 1 {
                x_pow *= point;
                muls_here += 1;
            }
        }
        if k < n - 1 {
            point *= omega;
            muls_here += 1;
        }
        total_muls += muls_here;
        results.push(result);
        println!("  P(w^{}): {} ({} muls)", k, "*".repeat(muls_here as usize), muls_here);
    }
    println!();
    for k in 0..n {
        println!("  P(omega^{}) = {:?}", k, results[k]);
    }
    println!("\nTotal field multiplications: {}", total_muls);
}

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

use ark_bn254::Fr;
use ark_ff::FftField;

fn ntt(coeffs: &[Fr], omega: Fr, depth: usize, muls_per_depth: &mut Vec<u64>) -> Vec<Fr> {
    let n = coeffs.len();
    if n == 1 {
        return coeffs.to_vec();
    }
    if depth >= muls_per_depth.len() {
        muls_per_depth.resize(depth + 1, 0);
    }

    let even: Vec<Fr> = coeffs.iter().step_by(2).cloned().collect();
    let odd: Vec<Fr> = coeffs.iter().skip(1).step_by(2).cloned().collect();

    let omega_sq = omega * omega;

    let y_even = ntt(&even, omega_sq, depth + 1, muls_per_depth);
    let y_odd = ntt(&odd, omega_sq, depth + 1, muls_per_depth);

    let mut result = vec![Fr::from(0); n];
    let mut twiddle = Fr::from(1);
    for k in 0..n / 2 {
        let t = twiddle * y_odd[k];
        muls_per_depth[depth] += 1;
        result[k] = y_even[k] + t;
        result[k + n / 2] = y_even[k] - t;
        if k < n / 2 - 1 {
            twiddle *= omega;
            muls_per_depth[depth] += 1;
        }
    }
    result
}

fn main() {
    let n = 8usize;
    let omega = Fr::get_root_of_unity(n as u64).expect("root exists");
    let coeffs: Vec<Fr> = vec![10, 20, 30, 40, 0, 0, 0, 0]
        .into_iter().map(|v| Fr::from(v)).collect();

    let mut muls_per_depth: Vec<u64> = Vec::new();
    let result = ntt(&coeffs, omega, 0, &mut muls_per_depth);

    println!("NTT butterfly: all evaluations at once");
    println!("(each * = one field multiplication)\n");

    let mut total = 0u64;
    for (d, &m) in muls_per_depth.iter().enumerate() {
        total += m;
        let size = n >> d;
        println!("  depth {} (n={:>2}): {} ({} muls)", d, size, "*".repeat(m as usize), m);
    }
    println!();
    for k in 0..n {
        println!("  P(omega^{}) = {:?}", k, result[k]);
    }
    println!("\nTotal field multiplications: {}", total);
}

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 -> N/2 -> N/4 -> ... -> 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: a direct consequence of the algorithm. When a ZK tutorial says "pad your trace to a power of two," now you know why. 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, ..., 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).

use ark_bn254::Fr;
use ark_poly::{
    EvaluationDomain, Radix2EvaluationDomain,
    DenseUVPolynomial, Polynomial, univariate::DensePolynomial,
};

fn main() {
    // Build a domain of 4 roots of unity
    let domain = Radix2EvaluationDomain::<Fr>::new(4).unwrap();
    let omega = domain.group_gen();
    println!("Domain size: {}", domain.size());
    println!("Generator (omega): {:?}\n", omega);

    // Encode the word "cool" as ASCII values:
    // 'c'=99, 'o'=111, 'o'=111, 'l'=108
    // Each value is assigned to a root of unity:
    //   data[0] at omega^0, data[1] at omega^1, ..., data[3] at omega^3
    let mut data = vec![
        Fr::from(99), Fr::from(111), Fr::from(111), Fr::from(108),
    ];

    // Inverse NTT: find the polynomial whose evaluations at roots of unity
    // give back this data. This is interpolation. O(N log N).
    domain.ifft_in_place(&mut data);

    // data now holds coefficients. Build the polynomial.
    let poly = DensePolynomial::from_coefficients_vec(data);

    // Verify by evaluating at roots of unity, just like post #1.
    // If interpolation worked, P(omega^i) gives back our original data.
    println!("Evaluating the interpolated polynomial:\n");
    let mut point = Fr::from(1); // omega^0 = 1
    for i in 0..4 {
        let value = poly.evaluate(&point);
        println!("  P(omega^{}) = {:?}", i, value);
        point *= omega;
    }

    println!("\nThat's [99, 111, 111, 108] = \"cool\" in ASCII.");
    println!("The inverse NTT found the right polynomial.");
}

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.

"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 equations. 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.

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.

This is post #2 in my "first principles" ZK series for Rust devs. Interactive version with runnable code and animations on rustarians.com.

I'm running a free live session on March 17: From Polynomials to Proof in 60 Minutes. Range check circuit built step by step, with a real use case.

Questions? Found a bug? linkedin.com/in/adam-smolarek

Polynomials in ZK SNARKs published: true

Adam — Tue, 10 Mar 2026 10:27:09 +0000

This post has interactive code editors on the original version where you can run and modify every Rust snippet in the browser.

Welcome, fellow zk-enjoyer.

You've spent evenings staring at tutorials that don't compile. Explanations that assume you have a PhD in algebra. 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.

What to Expect

Non-formal introductions to zkSNARKs internals. Yes, with scary names: Fast Fourier Transform, KZG commitment scheme, univariate polynomials over finite fields. But without eye-bleeding math.

I include fancy names so you'll recognize them in whitepapers later.

The code is written in Rust, edition 2024, using Arkworks libraries. As of January 2026, it compiles and runs.
If something breaks, I'll update it. That's the difference between a real human and a content mill.

The Road Map

Polynomials over finite fields <- you are here
Roots of unity
Execution trace
Polynomial interpolation via FFT/NTT
Applying constraints to polynomials
Packing into a single polynomial
Commitment scheme (starting with KZG)
Proof AND Verification

Eight posts. But you'll understand what happens instead of copy-pasting circuits and praying.

Let's go

Remember polynomials from high school? The things nobody explained why they existed?

Turns out they're the fundamental building block of ZK.

Polynomials work like a data structure. Think of them as Maps that only accept numbers.
Your data is bits at a low level anyway, so translation is doable.
In addition to storage, polynomials allow you to constrain exactly which numbers go where.

Today: storing stuff (encoding). Future posts: the constraints magic (business logic).

Your First Polynomial

Here's a polynomial that encodes a message:

2x^3 - 15x^2 + 28x + 96

If you did not know how it was created, it looks like regular equation. But plug in x values 3, 1, 5, 2, and you get the message back.

use ark_bn254::Fr as Bn254Fr;
use ark_poly::{DenseUVPolynomial, Polynomial, univariate::DensePolynomial};
use std::ops::Neg;
use ark_ff::{BigInteger, PrimeField};

fn main() {
    type ScalarField = Bn254Fr;

    // P(x) = 2x^3 - 15x^2 + 28x + 96 mod Fr_curve::MODULUS
    let polynomial: DensePolynomial<ScalarField> = DensePolynomial::from_coefficients_vec(vec![
        ScalarField::from(96),
        ScalarField::from(28),
        ScalarField::from(15).neg(),
        ScalarField::from(2),
    ]);

    let evaluation1 = polynomial.evaluate(&ScalarField::from(3));
    let evaluation2 = polynomial.evaluate(&ScalarField::from(1));
    let evaluation3 = polynomial.evaluate(&ScalarField::from(5));
    let evaluation4 = polynomial.evaluate(&ScalarField::from(2));

    println!("polynomial evaluations (x,y) = {:?}",
             [(3,evaluation1), (1,evaluation2), (5,evaluation3), (2,evaluation4)]);

    let c1: char = evaluation1.into_bigint().to_bytes_le()[0].into();
    let c2: char = evaluation2.into_bigint().to_bytes_le()[0].into();
    let c3: char = evaluation3.into_bigint().to_bytes_le()[0].into();
    let c4: char = evaluation4.into_bigint().to_bytes_le()[0].into();

    println!("polynomial evaluations y as letters = {:?}", [c1,c2,c3,c4]);

    println!("how polynomial actually looks like: {:?}", polynomial);
}

You use specific x values (3, 1, 5, 2) as indices to encode the data.
Later, we'll encode business logic (constraints) as polynomials too.

Ok, cool we have it saved something in form of a polynomial but WHY?

Because there is this thing called Schwartz-Zippel lemma.
Do not be afraid young padawan, another fancy name, but tool very useful it is.

The one and only, the OG: Schwartz-Zippel lemma

Schwartz-Zippel simplified:

Two different polynomials will almost never give the same output for a random input.

If you know hash functions, this is similar. Different inputs produce different outputs. With hashes, the input is data. With Schwartz-Zippel the input is a polynomial plus a random value.

Why does this matter? You can verify someone has a specific polynomial by asking for ONE evaluation at a random point. One number checks an entire polynomial. Insanely efficient.

Below: two different polynomials evaluated at a random point. Run it a few times and see that evaluations are always different.

use ark_bn254::Fr as Bn254Fr;
use ark_poly::{DenseUVPolynomial, Polynomial, univariate::DensePolynomial};
use ark_std::{
    UniformRand,
    rand::{SeedableRng, prelude::StdRng},
};
use std::time::{SystemTime, UNIX_EPOCH};

fn main() {
    type ScalarField = Bn254Fr;

    let polynomial1: DensePolynomial<ScalarField> =
        DensePolynomial::from_coefficients_vec(vec![
            ScalarField::from(6),
            ScalarField::from(2)
        ]);

    let polynomial2: DensePolynomial<ScalarField> =
        DensePolynomial::from_coefficients_vec(vec![
            ScalarField::from(7),
            ScalarField::from(3)
        ]);

    let since_the_epoch = SystemTime::now()
        .duration_since(UNIX_EPOCH)
        .expect("I am expecting that some time has passed since EPOCH");

    let mut rng: StdRng = SeedableRng::seed_from_u64(since_the_epoch.as_secs());
    let x = ScalarField::rand(&mut rng);

    let evaluation1 = polynomial1.evaluate(&x);
    let evaluation2 = polynomial2.evaluate(&x);

    println!("polynomial1 evaluation (x,y) = {:?}", (x, evaluation1));
    println!("polynomial2 evaluation (x,y) = {:?}", (x, evaluation2));

    assert_ne!(evaluation1, evaluation2)
}

The assertion should never fail. Collision probability is less than 1 in 10^76. To give you an idea, the observable universe has 10^80 atoms.

Back to "cool" example. You can verify I have the same polynomial by picking random x (say, 42), asking me to evaluate at that point, and comparing results. Same value = same polynomial (with overwhelming probability).

This extends to constraints and business logic. But that's for future posts.

Key takeaway: Polynomials + Schwartz-Zippel = encode stuff and verify with a single number.

"Wait, Why Does -15 Look So Weird?"

When you print the polynomial, -15 shows up as:

21888242871839275222246405745257275088548364400416034343698204186575808495602

What the hell?

use ark_bn254::Fr as Bn254Fr;
use ark_poly::{DenseUVPolynomial, univariate::DensePolynomial};
use std::ops::Neg;

fn main() {
    let polynomial: DensePolynomial<Bn254Fr> =
        DensePolynomial::from_coefficients_vec(vec![
            Bn254Fr::from(96),
            Bn254Fr::from(28),
            Bn254Fr::from(15).neg(),
            Bn254Fr::from(2),
        ]);

    println!("how polynomial should look like: \n96 + \n28 * x - \n15 * x^2 + \n2 * x^3");
    println!("how polynomial actually looks like: {:?}", polynomial);
}

That giant number IS -15. BUT in modular arithmetic.

Example on smaller numbers first. Regular numbers go to infinity both ways. Modular arithmetic gives you finite numbers. With mod 29, you have 29 numbers. To get infinity working with a finite number of elements they form a circle (ring). After 28 comes 0, then 1, 2, 3... Behind 0 comes 28, then 27...

So with mod 29, what acts like -15? You need something that adds to 15 and gives 0. That's 14. Because 15 + 14 = 29. And there is no 29, after 28 you wrap back to 0. So 15 + 14 = 0 mod 29. So 14 "acts like" -15 in this case.

Let's check how -15 looks like with the big modulus:

use ark_bn254::Fr as Bn254Fr;
use ark_ff::{BigInteger, PrimeField};
use std::ops::Neg;

fn main() {
    type ScalarField = Bn254Fr;

    let negative = ScalarField::from(15).neg();
    let positive = ScalarField::from(15);

    println!(
        "negative + positive in modular arithmetic: {:?}",
        negative + positive
    );

    let negative = negative.into_bigint();
    let mut positive = positive.into_bigint();
    positive.add_with_carry(&negative);

    println!("negative + positive in regular arithmetic: {:?}", positive);
    println!("ScalarField::MODULUS: {:?}", ScalarField::MODULUS);
}

Same trick works for multiplication. Normally, if you multiply a number by its inverse you get 1. With regular numbers, inverse of 5 is 1/5. Multiply them: 5 x 1/5 = 1.

But with modular arithmetic? No such thing as a fraction (1/5). Instead, there's some integer that "acts like" 1/5. Finding it is much harder, but we can do it with extended Euclidean algorithm (another fancy name).

use ark_bn254::Fr as Bn254Fr;
use ark_ff::Field;

fn main() {
    type ScalarField = Bn254Fr;

    let five = ScalarField::from(5);
    let five_inverse = five.inverse().unwrap();

    println!("5 inverse: {:?}", five_inverse);
    println!("5 * 5_inverse: {:?}", five * five_inverse);
}

Why do we care?

Addition/subtraction and multiplication/division work a bit differently. Instead of regular numbers we have numbers modulo some prime.

Because we have all those things we can use another fancy name: Finite Field. Just a name you'll see in white papers. Now you know what it means.

We can call it many other names, like Knight of the Square Table, or Humpty Dumpty, but someone was faster and already called it Finite Field, and it kinda stuck. The guy was Evariste Galois.

Those Finite Fields have a critical property. Multiplication and powers are easy to compute. Going backwards (logarithms) is stupidly hard. ZK security depends on this asymmetry. Post #7 (KZG commitment scheme) shows exactly how.

What You Just Did

You computed evaluation of univariate polynomials over a finite field. Specifically, the scalar field of the elliptic curve BN254.

Told you at the beginning: these are names. They can't hurt you.

Next Up: Roots of Unity

How do we efficiently put data INTO polynomials? By using something called "roots of unity."

It's a bunch of numbers with useful properties. The name sounds intimidating. It isn't.

See you there.

This is post #1 in my "first principles" ZK series for Rust devs. Interactive version with runnable code on rustarians.com.

I'm running a free live session on March 17: From Polynomials to Proof in 60 Minutes. Range check circuit built step by step, with a real use case.

Questions? Found a bug? linkedin.com/in/adam-smolarek