SNARKs vs STARKs: The Great ZK Showdown
Part 2 of 3 in the Zero-Knowledge Proofs series. We go from "proving you know a secret" to "proving an entire computer program ran correctly."
SNARKs vs STARKs: The Great ZK Showdown
Part 2 of 3 in the Zero-Knowledge Proofs series. We go from "proving you know a secret" to "proving an entire computer program ran correctly."
In Part 1, we learned how to prove knowledge of a discrete logarithm using the Schnorr protocol. Clean. Elegant. Mathematically beautiful.
But here's the problem.
The real world doesn't care about discrete logarithms.
The real world wants to prove things like:
"I executed 10,000 Ethereum transactions correctly"
"This smart contract ran without errors and produced this output"
"This batch of DeFi trades is valid and nobody got cheated"
Schnorr can't do any of that. You need something more powerful. Something that can turn any computation into a Zero-Knowledge Proof.
That something has two names: zk-SNARKs and zk-STARKs.
They're both trying to solve the same problem. They chose completely different paths to get there. And the differences between them matter enormously for anyone building in Web3.
Let's break it down.
The Core Challenge: Proving Arbitrary Computation
Before we talk about SNARKs and STARKs, we need to understand what problem they're actually solving.
Imagine you want to prove to someone that you correctly ran a program — say, a function that checks whether a Sudoku solution is valid — without revealing the solution itself.
The naive approach: just run the program and show them. But then they see the solution. Zero-knowledge is gone.
The ZK approach: convert the program into a mathematical object that can be verified without re-running it.
But how do you turn a program — with loops, conditionals, memory access — into math?
That's the hard part. And the answer involves a concept called arithmetic circuits.
Step 1: Turning Programs Into Circuits
Every computation can be broken down into two basic operations: addition and multiplication.
An arithmetic circuit is exactly that — a directed graph of addition and multiplication gates over a finite field (integers modulo a prime number p).
Example: prove you know x such that x³ + x + 5 = 35
Break it into gates:
Gate 1: x * x = x² (multiplication)
Gate 2: x² * x = x³ (multiplication)
Gate 3: x³ + x = x³+x (addition)
Gate 4: x³+x + 5 = output (addition with constant)
Circuit:
x ──┬──[×]──── x²
│ │
│ └──[×]──── x³
│ │
└────────────[+]──── x³+x
│
5 ──[+]──── 35 ✓
This circuit has 4 gates. For the solution x = 3:
3 * 3 = 9
9 * 3 = 27
27 + 3 = 30
30 + 5 = 35 ✓
Now here's the key insight: if you can prove you have a valid assignment of values to all the wires in this circuit — you've proven you ran the computation correctly.
The secret (x = 3) is your witness. The output (35) is your public statement. The circuit is the program.
Step 2: R1CS — Formalizing the Constraints
Circuits need to be converted into a standard mathematical form that proof systems can work with. That form is called Rank-1 Constraint System (R1CS).
Every gate in the circuit becomes a constraint of the form:
(A · z) * (B · z) = (C · z)
Where z is a vector containing all the wire values (both public and private), and A, B, C are selector vectors that pick out the relevant wires for each constraint.
For our example:
Constraint 1 (x * x = x²): (x) * (x) = (x²)
Constraint 2 (x² * x = x³): (x²) * (x) = (x³)
Constraint 3 (x³ + x = out): addition constraints are handled differently
The full witness vector z for x = 3:
z = [1, 35, 3, 9, 27, 30]
[constant, output, x, x², x³, x³+x]
An R1CS is a list of these constraints. For a simple computation, you might have hundreds. For a full Ethereum transaction, you might have millions.
Now the goal is clear: prove you know a vector z satisfying all constraints, without revealing the private parts of z.
Step 3: QAP — Turning Constraints Into Polynomials
This is where SNARKs do something genuinely clever.
Instead of checking each constraint one by one (which would be slow and would leak information), SNARKs encode all constraints simultaneously as a single polynomial equation.
This conversion from R1CS to Quadratic Arithmetic Program (QAP) works by:
Assigning each constraint to a point on a number line
Interpolating polynomials through those points
Converting the constraint-check into: does this polynomial divide evenly by a target polynomial?
Instead of checking 1,000 constraints individually:
Check: A(x) * B(x) - C(x) = H(x) * Z(x)
Where Z(x) = (x-1)(x-2)...(x-n) is the target polynomial
And H(x) is a quotient polynomial the prover computes
If this equation holds for ALL x simultaneously:
→ All 1,000 constraints are satisfied
→ Verified in ONE check instead of 1,000
This is the magic of QAPs: one polynomial check replaces millions of individual constraint checks.
Now the question is: how does the verifier check this polynomial equation without seeing the polynomials themselves?
Enter KZG Commitments — The Heart of SNARKs
A polynomial commitment scheme lets you:
Commit to a polynomial (send a small fingerprint of it)
Later prove that the polynomial evaluates to a specific value at a specific point
Without revealing the polynomial itself
The KZG commitment scheme (Kate-Zaverucha-Goldberg, 2010) does this using elliptic curve pairings.
The setup: someone computes a Structured Reference String (SRS):
SRS = {g, g^τ, g^(τ²), g^(τ³), ..., g^(τ^n)}
Where g is a generator of an elliptic curve group, and τ (tau) is a secret number — the toxic waste.
To commit to a polynomial f(x) = a₀ + a₁x + a₂x² + ...:
Commitment = a₀·g + a₁·g^τ + a₂·g^(τ²) + ...
= g^(f(τ))
The commitment is a single elliptic curve point — ~48 bytes. No matter how large the polynomial.
To verify: use pairing operations to check relationships between commitments without knowing τ or the polynomials themselves.
This is why Groth16 SNARK proofs are only ~200 bytes — the entire proof is just a few elliptic curve points, regardless of how complex the underlying computation was.
The Trusted Setup Problem
Here's the catch. A big one.
That secret τ used to generate the SRS? It must be destroyed.
If anyone ever recovers τ, they can generate fake proofs for false statements. They could prove they have funds they don't have. They could prove a transaction is valid when it isn't.
This is called the toxic waste problem and it's SNARKs' original sin.
To mitigate this, projects run trusted setup ceremonies — multi-party computations where dozens or hundreds of people each contribute randomness:
Participant 1 generates random τ₁, produces partial SRS, destroys τ₁
Participant 2 takes partial SRS, mixes in τ₂, destroys τ₂
Participant 3 takes partial SRS, mixes in τ₃, destroys τ₃
...
Final SRS is secure as long as AT LEAST ONE participant honestly destroyed their contribution
Zcash ran the famous "Powers of Tau" ceremony with dozens of participants, including some theatrical contributions — one participant generated their randomness on an air-gapped computer, then physically destroyed the hardware.
The problem: you can't prove the ceremony was honest. You take it on faith.
For PLONK-based SNARKs (the newer generation), there's a "universal" trusted setup — one ceremony works for all circuits, not just one specific circuit. Better, but the trust assumption remains.
This bothered a lot of cryptographers. Enough that they built something entirely different.
zk-STARKs: The Trustless Alternative
STARKs — Scalable Transparent Arguments of Knowledge — were developed by StarkWare in 2018 with one primary goal: eliminate the trusted setup entirely.
Instead of elliptic curve pairings and KZG commitments, STARKs use:
Hash functions (collision-resistant, quantum-safe)
Merkle trees (for committing to execution traces)
FRI protocol (for polynomial proximity testing)
No secret τ. No ceremony. No toxic waste. Anyone can verify the setup from scratch.
How STARKs Work (Conceptually)
Instead of converting a program to R1CS → QAP → polynomial commitments, STARKs:
Build an execution trace — a table showing the state of all registers at every step of the computation
Encode the trace as polynomials over a finite field
Use FRI (Fast Reed-Solomon IOP of Proximity) to prove the polynomials have low degree — which proves the execution trace is valid
Execution trace for x³ + x + 5 = 35:
Step | x | x² | x³ | x³+x | output
-----|----|----|-----|------|-------
1 | 3 | 9 | 27 | 30 | 35
STARK proves this trace is consistent with the program
without revealing x = 3
The FRI protocol works by asking the prover to commit to the polynomial via a Merkle tree, then randomly sampling positions to check consistency. The prover provides Merkle proofs for each queried position.
Why STARKs Are Bigger
Here's the trade-off that explains the size difference:
SNARKs use elliptic curve pairings for commitments. One pairing = ~48 bytes. A Groth16 proof is 3 curve points = ~200 bytes total.
STARKs use Merkle trees for commitments. Each commitment is a Merkle root + a path of hashes for each query. For a 20-query FRI check, with 30 levels of Merkle tree, that's 20 × 30 × 32 bytes = ~19KB just for the Merkle proofs.
A STARK proof for a moderately complex computation: 50–200KB. A Groth16 SNARK for the same: ~200 bytes.
On Ethereum, posting data costs gas. This size difference translates directly to transaction costs.
Proof Type | Size | Verify Gas Cost
--------------|-----------|----------------
Groth16 SNARK | ~200 bytes| ~250,000 gas
PLONK SNARK | ~400 bytes| ~300,000 gas
zk-STARK | ~50-200KB | ~5,000,000 gas
SNARKs vs STARKs: The Full Picture
Let's put everything side by side:
SNARKs STARKs
─────────────────────────────────────────────────────
Proof size ~200-400 bytes 50-500 KB
Verify cost (gas) ~250K gas ~5M gas
Prove time Seconds Minutes
Trusted setup Required None (transparent)
Quantum safe No (ECC-based) Yes (hash-based)
Math foundation Elliptic curves Hash functions
Main projects zkSync, Polygon StarkNet, StarkEx
Best for On-chain verify Large computations
Neither is universally better. The choice depends entirely on your constraints:
On-chain verification cost is your bottleneck → SNARKs win (smaller proofs, less gas)
You need trustlessness / no ceremony → STARKs win
Quantum resistance matters → STARKs win
Fastest possible proving → SNARKs win (Groth16 is extremely fast)
Large scale computations → STARKs scale better
ZK Rollups: Where This All Comes Together
Now we can talk about ZK rollups properly — because you actually understand what's happening underneath.
A ZK rollup is a Layer 2 scaling solution for Ethereum. The core idea:
Execute thousands of transactions off-chain. Generate a ZK proof that all of them were valid. Post only the proof (and compressed data) to Ethereum Layer 1.
Here's the full architecture:
Users
│
│ submit transactions
▼
L2 Sequencer
│ batches transactions
│ executes them off-chain
│ computes new state root
▼
ZK Prover
│ generates proof π that:
│ "I executed N transactions correctly
│ starting from root R_old → R_new"
▼
Ethereum L1
│ Verifier contract receives:
│ (π, R_old, R_new, compressed_tx_data)
│
│ runs: verify(π, R_old, R_new)
│ → true: update state root ✓
│ → false: reject batch ✗
The verifier contract only sees:
The old state root (a hash of the previous state)
The new state root (a hash of the new state)
The proof π
It never sees individual transaction amounts, sender addresses, or any private data. The proof mathematically guarantees the state transition was computed correctly — that's all the contract needs to know.
How The Verifier Checks Without Knowing Inputs
This is the part that trips people up. How can a smart contract verify that 10,000 transactions were valid without seeing any of them?
Think back to our QAP from earlier. The circuit encodes all the rules:
Valid signatures ✓
No double spends ✓
Balances never go negative ✓
Correct arithmetic throughout ✓
The proof π is a mathematical commitment that a valid witness (all transaction data) satisfying all these constraints exists. The verifier checks the proof against the public inputs (state roots) using pairing operations or hash checks.
Verifier checks:
e(π_a, π_b) = e(α, β) · e(vk_inputs, γ) · e(π_c, δ)
This pairing equation holds IF AND ONLY IF:
→ A valid witness satisfying all circuit constraints exists
→ The public inputs (R_old, R_new) are consistent with that witness
The verifier never learns the witness (transaction details)
One mathematical check. 10,000 transactions verified. That's the power.
ZK Rollups vs Optimistic Rollups
Now that you understand ZK rollups, the comparison to optimistic rollups makes intuitive sense:
Optimistic Rollups (Optimism, Arbitrum, Base):
Assume all transactions are valid — optimistically
Post transactions to L1 with no proof
Anyone can submit a fraud proof within 7 days if they find an invalid transaction
If nobody challenges: batch is finalized after 7 days
Withdrawals take 7 days (waiting for challenge window)
ZK Rollups (zkSync Era, StarkNet, Polygon zkEVM):
Generate a cryptographic validity proof for every batch
Post proof to L1 — verified immediately by smart contract
Finality in minutes, not days
Withdrawals are fast
Optimistic ZK Rollup
────────────────────────────────────────────────
Security model Economic game Cryptographic proof
Finality 7 days Minutes
Withdrawal 7 days Fast
Computation Cheap Expensive (proving)
EVM compat Native Hard (zkEVM)
Trust model Fraud proof exists Math is correct
The key philosophical difference:
Optimistic: "We assume you're honest. Prove us wrong within 7 days."
ZK: "We prove we're honest. Math says so. No waiting required."
For financial applications where finality matters — ZK is the direction the industry is moving.
The zkEVM Problem
One important limitation worth understanding: the EVM was not designed with ZK in mind.
Ethereum's virtual machine uses 256-bit arithmetic, SHA-256, Keccak hashing, and memory access patterns that are extremely expensive to express as arithmetic circuits. Building a zkEVM — a ZK proof system that can prove arbitrary EVM execution — is one of the hardest engineering problems in crypto.
EVM opcode costs in ZK circuits (approximate):
Addition: ~1 constraint (cheap)
Keccak hash: ~150,000 constraints (very expensive)
Memory read: ~10,000 constraints (expensive)
Projects like zkSync Era, Polygon zkEVM, and Scroll have built working zkEVMs — but proving a single Ethereum block takes minutes and requires clusters of high-end hardware.
This is an active area of research. Hardware acceleration (GPUs, FPGAs, custom ASICs) is reducing prove times. But it's not solved yet.
Where We Are Now
Part 1 gave us:
→ Why ZK proofs exist
→ The three properties: Completeness, Soundness, Zero-Knowledge
→ The simulator argument
→ Sigma protocols + Schnorr
→ Fiat-Shamir: making proofs non-interactive
Part 2 added:
→ Arithmetic circuits: turning programs into math
→ R1CS: formalizing constraints
→ QAP: turning constraints into polynomials
→ KZG commitments: the heart of SNARKs
→ Trusted setup: SNARKs' original sin
→ STARKs: trustless ZK via hashes
→ ZK rollups: the full architecture
→ ZK vs Optimistic rollups
That's ZK proofs in the blockchain context — fully understood.
But we started this series by mentioning something more ambitious: proving that an AI model ran correctly. Proving that a neural network — with billions of parameters — produced a specific output, without revealing the model weights.
That's the frontier. That's where ZK gets genuinely hard, genuinely interesting, and genuinely important for the future of AI.
Part 3 is where we go there.
I'm Niranjan — Full Stack & Web3 Developer at Alkimi Exchange, M.Sc. student in Data Science & Generative AI. Writing about what I'm actually learning, not what sounds impressive.
Follow me on X / Twitter | Read the full series on Hashnode
Up next: Part 3 — Can You Prove an AI Ran Correctly? zkML, why neural networks hate ZK circuits, the floating point problem, EZKL, and a working Circom proof from scratch.