Stateful vs stateless ZK proving

Every zk L2 stands on its prover. Each batch of transactions needs a cryptographic proof that the execution was correct — L1 verifies the proof, not the transactions. So proving capacity decides your throughput and your costs.

Proving needs state. To re-execute a batch, the prover has to see every account and storage slot the batch touches. And state is big — gigabytes on a young chain, terabytes on a busy one. Anything that has to hold it becomes expensive to run, and worse, expensive to copy.

There are two ways to connect the prover to the state. The naive one: plug the prover into the node's state database and let it read as it goes. That is stateful proving. The other: have the node hand over a witness — a self-contained slice of state, exactly what the batch touches, verifiable against the state root. That is stateless proving.

Ethereum asked the same question about its own nodes in 2020, in the Eth 1.x project — research on improving state management in the execution layer. I was working on it back then. Inside zk proving, the same question played out the same way.

Before: stateful proving

The Hermez prover in its research era read the state as it went. So it sat coupled to a state database. Cozy, and hard to move.

The costs are the same costs stateful Ethereum has:

• Coupling. The prover inherits the node's internals — storage layout, access paths, caching. Change the client and you are rebuilding the prover.
• State. The proving side has to hold it and maintain it.
• Scaling. More provers means replicating the state.
• Performance. State access leaks into proving time.

After: witness in, proof out

With cdk-erigon — the zkEVM client our team at Gateway.fm builds — the model flipped. The node produces a witness, the exact slice of state a batch touches. The prover consumes it. It does not know or care how the node stores state.

Proving becomes almost a pure function: batch plus witness in, proof out. No state database on the proving side. Provers scale out like any stateless worker.

Before: the prover reads state as it executes. After: the witness travels with the batch, and the prover is a pure function.

The numbers came first

None of this was a guess. In 2020, as part of Ethereum Foundation stateless research, I measured witnesses on mainnet and published the raw data:

• Trie shape. Binary tries shrink witnesses versus hexary ones — the experiment, the data (Jan 2020).
• Sync. Witnesses pre-build caches during initial sync, from block 5M up — the experiment (Feb 2020).
• Overhead. Witness-resolution quantiles over blocks 3,000,000–6,000,000 — the data (Feb 2020).
• Formats. Opcode witnesses versus the key-value format, blocks 5,000,000–8,000,000, seventeen days of compute — KV-Witness, the data (Jul 2020).

The archives are still up. Anyone can re-run them. Bring seventeen days.

The flip is in the commit logs

You can watch it happen in both halves at once:

• cdk-erigon grew SMT witness generation on January 17, 2024 (#50). eth_getWitness and the witness spec followed the same week.
• Three days later the prover gained its first witness decoder (src/prover/witness.cpp, Jan 20).
• Stateless batch proving merged on January 31, 2024 — PR #765, from a branch literally named erigon_witness.

Everything before that in the prover's history is coupled to its state database.

This was not a solo act. The node half — witness generation, eth_getWitness, the spec — was our engineers at Gateway. The prover half was Polygon's team. Two teams, one seam, eleven days.

The same spec, carried across

The first-generation format has a formal spec. I wrote it — the Block Witness Formal Specification for stateless Ethereum. First commit: March 26, 2020.

Four years later, the person who added the witness spec to cdk-erigon was also me — #59, the same week the prover learned to decode it (Jan 2024). It lives in the tree today.

KV-Witness was my proposed second generation. Production picked gen one — the one I specified. Not on merit: that code already existed, and nobody had time to debug a new format. I lost the argument with myself and won it anyway.

The first-generation format. A witness is a small program: a stack machine executes the opcode tape and rebuilds the partial trie — touched state as data, everything untouched as a hash.

Stateless Ethereum never shipped on L1. Its core mechanism ships every day inside the rollups we build at Gateway.fm.

Where the idea shows up

• Block Witness Formal Specification (2020) — the gen-1 spec, written for stateless Ethereum.
• The witness spec in cdk-erigon (2024) — the same lineage, added for the stateless prover.
• KV-Witness — the 2020 second-generation proposal: what a key-value shape buys over opcodes.
• Semi-Stateless Initial Sync and Binary Tries — the mainnet experiments behind the numbers above.
• cdk-erigon — the witness-based pipeline in production rollups.