# Ethereum statelessness roadmap
Goal: Make Ethereum [weakly stateless](https://dankradfeist.de/ethereum/2021/02/14/why-stateless.html) so that block validation can be fully stateless, enabling:
* Validation on light machines, e.g. Raspberry Pi (without SSD) and mobile phones
* Fraud proofs for the EVM
* Fraud proof protected light client
* EVM as a shard
* Use [verkle tries](https://dankradfeist.de/ethereum/2021/06/18/verkle-trie-for-eth1.html) as state commitment scheme because witnesses are small and efficient to verify
* Gas cost changes to make state access cost reflect (more or less) the cost of witnesses
* (+ state expiry to keep active state under control, which is still relevant for block builders)
This is the **stateless roadmap**. We do not address the third point, state expiry, which is part of a [separate roadmap](https://notes.ethereum.org/@vbuterin/state_expiry_eip). We are ensuring that these two can be executed independently in order to allow teams to work on both of them at the same time with less coordination.
## Suggested roadmap
The suggested roadmap is to introduce the changes required for statelessness in three hard forks. "Shanghai" is the name for the hard fork after the merge. "Shanghai+1" and "Shanghai+2" refer to the subsequent hard forks, however if there are technical challenges this may have to be pushed back. The changes introduced over the three hard forks are:
* Shanghai -- gas cost changes
* Shanghai+1 -- freeze MPT root add verkle trie commitment
* Shanghai+2 -- replace frozen MPT root with verkle trie root
### Shanghai -- gas cost changes
[Statelessness gas cost changes EIP draft](https://notes.ethereum.org/-fJSOrnYQl-mqoWKpaTIsQ)
We need to make some changes to the gas cost to bring the cost for state access closer to the cost of witnesses. The reason for doing this early (and before actually switching to verkle tries) is that gas costs serve as an important signal to smart contract developers for optimizations. By bringing these in as early as possible, we get the signal out and more contracts will benefit from making these optimizations early.
The changes are concretely:
* Associate with each account/storage leaf a 32-byte key, as defined in the EIP draft
* Logically partition the leaf space in groups of 256 leaves, defined by the first 31 bytes of the key (a.k.a the "stem") and the last byte as the suffix. Keys are constructed in a way such that adjacent storage and code location share the same stem
* Charge `WITNESS_BRANCH_COST == 1900` each time any stem is accessed for the first time during the execution of a tx.
* Charge `WITNESS_CHUNK_COST == 200` each time a stem+suffix is accessed for the first time during the execution of a tx
* Charge `SUBTREE_EDIT_COST == 3000` for each stem that is written to (if the same stem is written to again this is not charged again).
* Charge `CHUNK_EDIT_COST == 500` for each leaf (stem+suffix) that is written to
* Charge `CHUNK_FILL_COST == 6200` for each leaf that was previously empty and is written to
* The `SELFDESTRUCT` opcode is renamed to `SENDALL`, and now only immediately moves all ETH in the account to the target; it no longer destroys code or storage or alters the nonce; there are no refunds
Note that these changes will require clients to make some changes to their databases. Since the cost of certain storage operations (accessing within the same suffix tree) will be *lower* than it is now, it is important that the database is structured to reflect this.
### Shanghai+1 -- freeze MPT root add verkle trie commitment
At the Shanghai+1 hard fork we will change the commitment scheme. We do this in a way that does not require any state recomputation:
* The current state root (Merkle Patricia Tree/MPT root) is **frozen** and no further changes are made to it.
* At the hard fork, we add a Verkle trie root that is initially an empty Verkle trie. All state changes from that point onward are written to this root, and do not affect the frozen MPT anymore
### Shanghai+2 -- replace frozen MPT root with verkle trie root
(EIP not yet drafted)
At the Shanghai+2 hard fork, we replace the frozen MPT root with an equivalent Verkle root. The result is that there are now two verkle trie roots:
* The frozen root with all state that was created before the Shanghai+1 HF
* The current state root that commits to all updates that happened since then
This hard fork requires that the old MPT state is now available as a verkle trie to clients as well. This can be achieved in different ways:
* Clients can provide a way to recompute the new database locally. This can be done in background as there will be several months between the hard forks and that part of the DB is frozen
* As an alternative, the converted database can be provided as a torrent. In terms of security, this would be similar to a snap sync and would mean not everyone has to do the local database update (which might require a large amount of computation and disk space)
* *IF* state expiry is ready, we can use state expiry for the last step -- in that case, all future accesses to the frozen verkle tree would require witnesses and most clients could simply forget all old state (no conversion required)
## Result: Optional statelessness
This roadmap does not actually include any mandatory block witnesses. It simply ensures that anyone who requires block witnesses can easily add them, and the work on verkle tries will ensure that
* they are reasonably small -- 10s to 100s of kB for average blocks and <10MB for worst case attack blocks
* they are quick to verify -- verification will take 100s of ms in the worst case
* they are easy to produce, assuming the block builder has access to the state. They should typically take a few seconds to compute.
Once we have reached this state, we have achieved "optional statelessness": Even before we enforce any kind of witness, anyone can now add these in a separate network and experiment with a stateless Ethereum network. This can interface seamlessly with the existing network as long as at least one node bridges the gap and adds witnesses to blocks.
### Possible future with fully stateless consensus
So how do we actually achieve real statelessness from here, where blocks have witnesses "by default"? Here is one possible version.
Note that it will always be a necessity to have some network where the state can be synced, since some actors (in our case block builders, and anyone who wants to serve state to other nodes) will always need it. We already have this network in the form of devp2p. At the same time, we are adding libp2p as another p2p network to Ethereum with the merge, which is already serving the beacon chain.
A natural way in which things could thus evolve is to start adding stateless blocks to the libp2p network after the Shanghai+2 hard fork. At this point, all nodes connected to this network would be able to fully validate Ethereum, without any remaining connection to the devp2p network.
The idea would thus be:
* The new libp2p network would become the core network for all consensus related things on Ethereum; broadcasting both stateless blocks (with full witnesses) and transactions (with partial witnesses) for a stateless mempool
* The devp2p network is gradually phased out from being a consensus network and will continue to exist only for syncing state
### Does this require the portal network or some other way of serving state to stateless nodes?
The portal network is currently being devised as a way to serve state to stateless nodes. This is a cool way to enable stateless nodes being able to serve Dapps without requiring a central state provider.
Statelessness however does not depend on the portal network in order to be useful
* Stateless validation is immediately useful, allowing full validation with low requirements. It both increases decentralization (as at home validation becomes easier) and security (as the practical requirement to run a resource-heavy execution node may push some validators not to do it, which compromises security)
* Stateless nodes still provide a very powerful service to their operators: Verifying the head of the chain. With this information, any state information provided via an RPC (such as from Infura) can be easily verified and such providers are commoditized
## Further reading
* Summary articles on verkle tries: [Dankrad's blog post](https://dankradfeist.de/ethereum/2021/06/18/verkle-trie-for-eth1.html), [Vitalik's blog post](https://vitalik.ca/general/2021/06/18/verkle.html)
* [Peep an EIP on verkle tries](https://www.youtube.com/watch?v=RGJOQHzg3UQ)
* [State expiry EIP draft](https://notes.ethereum.org/@vbuterin/state_expiry_eip)
* [State expiry and statelessness roadmap by Vitalik](https://notes.ethereum.org/@vbuterin/verkle_and_state_expiry_proposal)