# Stateless Ethereum With Merkle Witnesses

This post offers a path forward for implementing statelessness in Ethereum protocol without changing the trie layout. It suggests a tradeoff for eliminating the worst case size of a Merkle witness by having stateless nodes store the contract bytecodes.

Huge thanks to [@notnotstorm](https://x.com/notnotstorm) for gathering the data.

## Previous Works

Original suggestions for stateless Ethereum implementation with existing state trie layout have been turned down due to the worst case size of the witness. The worst case witness size is primarily caused by the need to include entire contract bytecode and is over 153 MiB (150MiB of contract bytecodes and 3MiB of proofs).

<details>
<summary>Worst case napkin math</summary>

Let's take an Ethereum block with current gas limit which is filled
with one transaction. The transaction repeatedly accesses unique
contract bytecodes via `EXTCODESIZE`.

The transaction loads contract addresses from storage and calls
`EXTCODESIZE` on the target. For simplicity, the calculation
excludes the cost of lookup related and stack operations.
The approximate maximum number of contract codes the transaction
can load is
(max gas used - base cost) / (SLOAD cost + EXTCODESIZE cost)
(30 000 000 - 21 000) / (2100 + 2600) =~ 6 378

Assuming each bytecode is unique and has the maximum size of
24 KiB (as defined by [EIP-170](https://eips.ethereum.org/EIPS/eip-170)),
that brings the size of the contracts included in the witness to
6 378 * (32 + 24 576) =~ 150MiB

Currently, there are around 265 mil accounts in the state trie.
The average depth of the trie is log16(265mil) =~ 7.
We can estimate the number of unique nodes in state witness using
formula `N * (C * (D - 1) + 1)`, where D is the average depth of
the trie, C is the overlap factor and N is the number of accessed
accounts (leaves). For uniformly distributed state keys we can assume
the overlap factor of 0.5 thus giving us the number of unique nodes
in the worst case state witness
6 378 * (0.5 * (6 - 1) + 1) = 25 512

Provided we store state witness as `keccak(rlp(node)): rlp(node)`
and the average size of a node is 100 bytes, the size of the state
witness in the worst case is
(100 + 32) * 25 512 =~ 3.2Mib

That brings the rough total size of worst case witness to ~153MiB.
</details>

Migration to [Verkle](https://verkle.info/) trie eliminates the worst case by chunking the contract bytecode across multiple leaves and charging the cost of access per leave. Additionally, it reduces the proof size due to a more flat trie layout with less intermediate nodes. However, this requires all Ethereum nodes to perform live database migration.

## Trading Off Worst Case Size For Storage

The contract bytecodes today are stored outside of the state trie. The account leaves only contain the commitment (code hash) to the contract code which is then used by the client implementation to retrieve the actual contract code.

**The worst case size of the Merkle witness can be significantly brought down by excluding contract bytecodes from the witness and making stateless nodes responsible for retrieving and storing contract bytecodes.**

As of Nov 24, 2024, the total _uncompressed_ size of unique Ethereum contracts is less than 14 GiB.


The size growth of unique contracts has been ranging between 100 and 330 MiB over the past 5 years.