The goal of this dev update is to clarify and contextualize the efforts to moves towards state expiry in Ethereum. There is a lot written on the topic, including multiple summaries and roadmaps, and this post attempts to put everything together as of the end of June 2021. Links to the primary sources will be provided, including a master list at the end of this post.
The Ethereum Virtual Machine (EVM) maintains a memory store. In addition to account balances, nonces and contract code, any contract can request the allocation of a piece of storage. Transaction must pay for allocated storage (which we'll often refer to as "state"), as well as subsequent reads and writes. As long as the state is accessed frequently, the cost of reads and writes should be enough to pay for the cost of maintaining the state. However, even state that is never accessed must be maintained. Not only does this state live rent-free on every full node, but as dead state accretes, it makes bringing a full node online (a process known as "sync") significantly more difficult than it would be otherwise.
To give you an idea, a full node (which maintains the state, but does only keeps the N (usually N=128) latest blocks) must currently store > 400 GB (or more than double that if using Geth). Of this, the state only comprises only about 30-60GB (however it is the only part who could grow unbounded). This is still better than archive nodes (who keep the whole block history), which must store a whopping 7.5 TB.
This is a good point to mention a related issue. In any scheme we can come up with, someone will have to know about the state (although maybe only a small fraction of all nodes). How can we make sure that other people can learn about the state when they need to? If full state storage is required for some node, can we devise a more efficient solution to acquire this state than to download the full blockchain (7.5TB!) and replay every single transaction to find the current state?
Before looking at solutions, one precision that will become hugely relevant later. State in Ethereum is represented by key-value stores, stored in Merkle trees. A Merkle tree is a radix tree (a compressed trie) where each node is labelled with the hash of its children (or the hash of the data for leaf nodes). The keys are always keccak hashes of the "real" key — this ensures that all keys have the same size (256 bits) and makes it difficult to find key that share a prefix, which could by an attacker to forcibly reduce the amount of compression in the tree. There is a Merkle tree mapping (hashes of) accounts to account data (the state trie). The account data itself includes the hash of (the root of) another Merkle tree storing the memory for the account. These storage tries (one per account) are separate from the state tree, but make up for the bulk of what the call "the state". See this illustration.
These trees are often called "modified patricia Merkle trees", which is just another way to say these are radix trees of branching factor 16 annotated whose nodes are annonated with a Merkle hash.
<aside> ⚙️ How are those trees actually stored in practice? We can't just build the Merkle trees in- memory — hundreds of GB of RAM is too much. In practice, most nodes use the LevelDB (or its fork RocksDB) key-value store. Because these stores are not implemented using Merkle trees, we need to store the hashes for the internal nodes of the Merkle trees as separate key-value pairs!
</aside>
There are a few ways to attack the problem, but there are two major directions we can go in:
A first idea, dating back to 2015, was called "state rent", a form of state expiry. Under this proposal, rent would be extracted from the balance of the contracts making use of the state. Its major inconvenient is that the proposal is not backward compatible with existing contracts, as fees are paid on an ongoing basis, and not only when processing a transaction — instantly bankrupting existing contracts with an empty balance (and disrupting the correct operation of others). The mechanics of keeping a contract funded so that it may pay its rent are also a bit awkward. Ideally, the costs would be passed transparently to users of the contract, just like other gas fees.
A subsequent idea is that of statelessness. This is outlined in "The Stateless Client Concept" post. The idea relies on the ability to build proofs (also called "witnesses") that particular pieces of state have a certain value. Only the hash of the root of the account's data trie is required to validate this proof. Under this model, miners could bundle witnesses along with the transactions, which would enable other full nodes to validate them without storing any state. This is known as "weak statelessness".
The post takes the idea further: could we make miners stateless and achieve "full statelessness"? We could, if we push the responsibility of supplying the witnesses to the transaction originators. This runs into two issues. First, the value of a piece of storage might change between transaction origination and transaction execution. This is easily fixed by letting miners store all recent (~24h) state changes and letting them alter the witnesses in case the state changed. The other issue is that originators might only be light nodes (i.e. nodes that do not validate blocks, but instead trust some other well-known nodes). There must be an easy way for such nodes to get hold of a witness for the data it is trying to access. We'll talk about some of what is available today and planned for the future in the Distributing State section.
Another issue with full statelessness is that currently, a contract might not know in advance which state it is going to access (this is called dynamic state access) — which makes it impossible to provide proof for! This is potentially a big issue, because it makes statelessness backward incompatible with old contracts.
<aside> ℹ️ In passing, there is currently an optional way to specify which accounts you'll interact with, address lists, though it's meant as a way to make transaction processing easier. In particular it enables parallel transaction processing in some cases.
</aside>
A final hurdle is the large size of proofs when using Merkle trees. As we'll see in a bit, this problem finds a solution in the Verkle tree data structure, which enables much smaller proofs.
Finally, the direction currently being pursued by the Ethereum core developers is that of state expiry, but without rent. Under this proposal, nodes must only maintain state that has been accessed recently (e.g. in the last year). If a transaction wants to access older state, it must supply the state's value, as well as a witness (proof) for that value.
Compared to statelessness, this require all full nodes to keep track of some state — although the size of this state becomes effectively bounded (as the number of blocks in a period is limited, and the gas limit for each block is finite). However, it comes with the advantage that blocks do not need to bundle witnesses, nor do these witnesses need to be transmitted on the network when propagating transaction.
