My neighbor once called me over to taste a pot of phở. One spoonful was all it took to know whether the broth was good — whether the pot held one liter or a hundred. But cooking that broth took hours. That is the story of zero-knowledge proofs in a nutshell: proving time zk is long, while verification is nearly instantaneous. In this article, we will dig into why generating a zk proof is slow but checking it is shockingly fast — and why this asymmetry is the beating heart of scaling blockchains like zk-rollups.
Figure 1: The cook (prover) vs the taster (verifier) — the asymmetry
Two Roles in One Play
Every zero-knowledge proof has two sides:
- The prover — the cook. This party performs one very heavy computation to produce a proof that some statement is true, without revealing the secret inside.
- The verifier — the taster. This party receives the proof and only needs a few light math steps to confirm "true" or "false."
In the phở analogy: the prover is the cook, the verifier is the taster. Cooking takes time; tasting takes a second. The bigger the pot, the longer the cooking — but one spoonful always takes the same one second.
This gap is not an accident. It is a deliberate design. The heavy cost is paid once (when the proof is created) so that millions of others pay almost nothing (when they verify). This is exactly why the economics of zk-rollups work: one machine pays a high price to prove an entire batch of transactions, and every node on the blockchain just verifies one small proof.
Why Proving Time ZK Is So Long
Step 1: Turn the computation into a circuit
First, the computation to be proven is translated into a circuit — a network of basic operations (additions, multiplications) called constraints. A complex financial computation can require a million constraints. This is where the recipe is written down: more ingredients, longer recipe.
Step 2: Generate the witness
The prover runs the circuit with the secret data to produce a witness — all the intermediate values of the computation. In essence this step re-executes the computation itself. It is a bit cheaper than the full proving, but it is still real work.
Step 3: The Fourier transform (FFT / NTT)
Here the mathematical magic begins. The circuit is represented as polynomials, and to work with polynomials efficiently the prover must run a Number Theoretic Transform (NTT) — a discrete cousin of the Fourier transform. For a million-constraint circuit, each NTT processes millions of data points. FFT/NTT eats a large share of total proving time — and once the MSM step below is optimized, NTT typically becomes the single largest remaining cost.
Step 4: MSM — the number-one time sink
Multi-Scalar Multiplication (MSM) multiplies millions of 256-bit scalars by points on an elliptic curve, then sums them all. This is the slowest step of the entire pipeline. According to the DistMSM research paper (ACM 2024), MSM accounts for roughly 78.2% of the proof-generation workload. In production systems (Bellperson from Zcash), MSM plus NTT together account for around 90% of the time.
Why is MSM so slow? Because each point-addition on a 256-bit (or 377-bit) elliptic curve is a long chain of finite-field arithmetic. Millions of such additions cannot be perfectly parallelized — even with Pippenger's algorithm reducing the number of multiplications, the total time remains large.
The result: for an average circuit, proving takes from a few seconds to a few minutes on a CPU. Dedicated GPUs can cut that to seconds, but it is never "instant."
What about polynomial commitments?
Before moving on, one concept ties all these steps together: the polynomial commitment. After the computation becomes polynomials, the prover must commit to them so the verifier can later check specific claims without re-reading the whole computation. Two families dominate:
- KZG commitments (used by Groth16, PLONK, and most SNARKs) bind a polynomial to a single short value using pairings. They produce tiny proofs, but they need a trusted setup that supplies the secret evaluation point.
- FRI-based commitments (used by STARKs) commit to the polynomial's evaluations with a Merkle tree. No trusted setup at all, but proofs are much larger.
Commitment cost is one more reason the prover is slow — especially for KZG, where the prover runs the MSM-heavy opening algorithm. The verifier, by contrast, only touches the commitment at the very end, inside those few pairing checks.
Figure 2: Inside the prover — where proving time zk goes
Why Verification Is Shockingly Fast
Now the taster's role. The verifier does not re-run the computation. It only checks a few algebraic identities — pairings — built from the proof and a public verification key.
For Groth16 (the most common SNARK):
- The proof is a compact 192 bytes (3 elliptic-curve points).
- Verification is just 3 pairing operations.
- Verification time is essentially constant, no matter how large the circuit. This is the biggest difference from STARK, where verification grows polylogarithmically with computation size — still very fast, but not constant.
On ordinary hardware, Groth16 verification takes about 3-5 milliseconds. On Ethereum, one Groth16 verification costs roughly 200,000-250,000 gas — tiny compared to re-running the original computation on-chain. This is thanks to EIP-1108, which cut the alt_bn128 precompile cost (each pairing now 34,000 gas), live since 2019.
In other words: the verifier does not "regrade the exam" by solving it again. It holds the answer key (verification key) and checks a few short steps to be sure the exam was not faked.
Figure 3: Inside the verifier — why zk verification is so fast
Complexity — Two Lines That Part Ways
Let's zoom out with complexity theory:
- Prover: time grows linearly with circuit size — O(n). If the circuit grows 10x, proving time grows roughly 10x, plus the big constants from MSM and NTT.
- Verifier (SNARK): time is constant — O(1). A 100,000-constraint circuit and a 10,000,000-constraint circuit both verify in a few milliseconds.
- Verifier (STARK): time grows as O(log n) — far slower than any linear growth, but not constant.
A concrete example — a circuit of 1,000,000 constraints:
| Circuit size | Proving time (CPU) | Verification time |
|---|---|---|
| 100,000 constraints | ~1-3 seconds | ~3-5 ms |
| 1,000,000 constraints | ~30 seconds - 2 minutes | ~3-5 ms |
| 10,000,000 constraints | ~10-30 minutes (GPU needed) | ~3-5 ms |
The proving-time line climbs steeply; the verification line stays flat. That is why zk-rollups can claim to "scale": they push the steep cost off-chain (to the prover) and keep only the flat part (verification) on-chain.
Figure 4: Scaling — proving grows, verification stays flat
Why This Asymmetry Matters
1. Zk-rollups: cook a giant pot, taste one spoon
In a zk-rollup, the cook (a centralized prover or a prover network) collects thousands of transactions, batches them, and produces one proof for the whole batch. That may take minutes. But on Ethereum, one verification — a few seconds and ~200k gas — confirms the entire batch. The volume of computation is "compressed" into one small proof.
2. Phones: can taste, cannot cook
A smartphone can verify a zk proof in milliseconds without meaningful battery drain. But generating a proof for a large circuit on a phone is impractical — it takes minutes to hours and drains the battery fast. That is why modern mobile systems use proving networks: servers generate proofs on the user's behalf, and the phone stays a verifier. "Client-side proving" is only feasible for very small circuits.
3. History: the war on two time sinks
Between 2016 and 2024, proving time dropped from minutes to milliseconds in many systems. What happened? The community attacked exactly the two bottlenecks: MSM (Pippenger improvements, 4-way parallelization) and FFT/NTT (batching, pipelining). This is clear evidence that slow proving is not an immutable law — it is being pushed back every year.
4. Prover networks: renting the kitchen
Because the cook's job is heavy, a whole industry exists to rent the kitchen. Prover networks (distributed proving marketplaces) split one huge circuit across many machines, each computing a slice, then assemble the final proof. They exist precisely because of the asymmetry: since verification is cheap, anyone can confirm a proof produced by a network they do not fully trust — as long as the proof itself is sound. If proving were as cheap as verification, this market would never have formed.
FAQ
Q: Why can't proving time zk match verification speed? A: Because the prover must execute the whole computation (witness generation), run the Fourier transform (FFT/NTT), and do millions of elliptic-curve point multiplications (MSM) — a workload proportional to circuit size. The verifier only checks a few pre-built identities (pairings), so its time is essentially constant.
Q: What does "zk proof performance" really mean? A: "Zk proof performance" refers to the tradeoff between proof-generation cost and verification cost. A high-performance system picks the right balance: a proof small enough, proving fast enough for the environment that runs the prover, and verification cheap enough for the environment that runs the verifier — especially on-chain.
Q: How much gas does on-chain verification cost? A: For Groth16 on Ethereum, roughly 200,000-250,000 gas (thanks to EIP-1108). STARK proofs are larger and cost up to about 5 million gas to verify on-chain — which is why many systems "wrap" STARK into SNARK (STARK-to-SNARK) to pay a smaller bill.
Q: Can a phone generate zk proofs? A: In principle yes, but only for very small circuits. For large circuits, time and battery make it unrealistic. In practice, proving networks are used — servers generate proofs, devices only verify.
Q: If verification is so fast, why not use ZK for everything? A: Because the cost sits on the prover side. Every time there is new data to prove, you pay the proving cost from scratch. For systems with thousands of transactions per second, proving cost is a serious infrastructure problem — precisely why proving networks and GPU farms exist.
Summary
A zero-knowledge proof is a two-role play: the cook (prover) pours serious effort into preparing a pot of proof, and the taster (verifier) needs just one spoon to judge it. Proving time zk grows with computation size — dominated by MSM (~78%) and FFT/NTT — while verification stays nearly constant. This asymmetry is the foundation of zk-rollups, of blockchain scaling, and of the whole "cook once, taste for everyone" model. Understand it, and you understand why ZK is not just math — it is an economic architecture.