## ❌ State Bloat: The Killer of all Blockchains

On Ethereum, **State** consists of the following:
- Account balances
- Account nonces
- Contract code
- Contract storage

At any given time, nodes need to know the current state to process new blocks and transactions. As more users join the network, more states are created (more accounts and contracts). As the state grows, the storage requirement for a node increases because they need to store the full state. When a blockchain's state grows significantly, it hinders the network's performance, making it difficult for many people to run nodes, leading to centralization. This issue is known as the **State Bloat** problem.

## 📖 Theory

### ReGenesis
> 💣 Nuke everything and let's start over!!!

*Refer to [Regenesis Explained.](https://medium.com/@mandrigin/regenesis-explained-97540f457807)*


The general idea of ReGenesis is for blockchain nodes to delete the entire blockchain state and start anew, while retaining only the pre-ReGenesis state's root hash. This process occurs at fixed intervals, such as every 1,000,000 blocks, to limit state growth and address the state bloat problem.

But what if a user wants to access the old state and perform actions with it? Users can send a transaction containing the operation (e.g., sending Ether) and the witness (i.e., useful state and proof). The state included in each transaction is merged back with the primary blockchain state. This means that with every ReGenesis, redundant state is guaranteed to be removed from the blockchain state.

However, a caveat remains: the pre-ReGenesis state still needs to be stored somewhere, such as IPFS, Portal Network, a self-hosted database, or any accessible location. Additionally, Merkle proofs can be too large and impact network bandwidth, which could potentially be addressed with Verkle Trees.

### Blockchain Rent
> 💸 Pay rent or say bye bye to your data.

*Refer to [EIP 103 (Serenity).](https://github.com/ethereum/EIPs/issues/35)*

The concept of blockchain rent is simple – rather than paying a one-time cost to store data permanently on a blockchain, users must now pay rent to keep the data on the blockchain.

However, implementing this on existing chains like Ethereum is not straightforward, as it adds complexity to the existing economic model. Blockchain rent also introduces uncertainties into accounts, which creates new attack vectors.

### Statelessness
> 🧊 Ain't nobody got time to store states!

*Refer to [A Theory of Ethereum State Size Management.](https://hackmd.io/@vbuterin/state_size_management)*

The general idea is that block verification no longer requires the full state. Instead, blocks can be executed standalone, allowing nodes to verify using only the information contained in the blocks. To achieve this, blocks need to come with witnesses that prove the correctness of the new state root after executing the block.

Vitalik's article outlines two forms of statelessness:
- **Weak statelessness**: only block producers require the full state so that they can generate witnesses for block creation, but other nodes can be stateless by using blocks to perform verification
- **Strong statelessness**: full state is not necessary for all nodes. Users need to provide witnesses whenever sending a transaction. Block producers would aggregate the witnesses and still store portions of the state tree to generate witnesses for accounts that they care about.

While weak statelessness doesn't solve the state bloat problem, it eases the burden of storing the full state for non-block producers, enabling regular people to run nodes with lower hardware requirements and increasing decentralization.

Strong statelessness shifts the responsibility of "knowing the state" to users, which may impact user experience. Additionally, strong statelessness may have a higher impact on network bandwidth, as transactions need to contain more information, such as accounts and storage keys they access.

### State Expiry
> 👋 Not using your data anymore? Then go away.

*Refer to [A Theory of Ethereum State Size Management.](https://hackmd.io/@vbuterin/state_size_management)*

If a state is no longer accessed for a long time, then why should we store them? State expiry is a solution to label if a state is inactive or active and temporarily removes the inactive state from the blockchain. Inactive state can be revived by providing some witnesses and be active again.

From Vitalik's article, there are a few ways to determine the inactivity of a state (I rewrote it in my own words):
- **Automatic rent on account balance**: each account has a default "rent-free" period. After that, the account balance automatically gets deducted. The account is deemed inactive and expired when its balance reaches zero.
- **Subscription model**: each state object has a time period to stay in the blockchain and can be extended by paying a fee.
- **Refresh by touching**: each state object has a time period to stay in the blockchain and it is automatically extended by reading or writing to the object.
- **ReGenesis**: all states expire automatically at a fixed interval

The key challenge with state expiry schemes is **resurrection conflict**. Supposed that Alice had an account 5 years ago with a balance of 10 ETH. It is expired due to inactivity. Alice now creates a new account at the same address and has a balance of 5 ETH. Finally, a resurrection of the original account is executed. How do we handle this scenario?

From Vitalik's article, there are a few possible solutions (again, rewriting in my own words):
- **Account merge**: accounts that expired and accounts that got created at the same address are merged. Merging logic for contract level may be customized, only the latest state or only the old state. Account balance may be merged together as well.
- **Eliminate same-address re-creation**: CREATE2 opcode now adds the current year so that address generated in different years cannot be the same.
- **Add a "stub" at expired location**: if reading or writing to a state passes through a "stub", transaction will be reverted. For a transaction to succeed, it needs to recover the expired location first.
- **Account creations with non-prior-expiry proofs**: all account creations must come with some witnesses to prove that it does not expire previously.

All of the solutions have its own tradeoffs. Merging account introduces complexity and things become super messy. Preventing users from re-creating addresses and requiring account creations to come with non-prior-expiry proofs affect user experience. In this case, adding a stub seems like the best solution among all, but it has the tree rot problem (see [this](https://hackmd.io/@vbuterin/state_size_management#Tree-rot)).

To summarize, state expiry is an "elegant" way of eliminating inactive state while providing the capability of resurrecting inactive state to active state again.

## 🛠️ Ideas & Implementations

### Ethereum's State Expiry
> 🌲 Many Verkle Trees + Address extension + Refresh by touching

*Refer to [State Expiry EIP](https://notes.ethereum.org/@vbuterin/state_expiry_eip)*


*Diagram by Vitalik*

Instead of having only a single state tree, this proposal suggests creating a new tree at fixed epochs, such as every year, so that the blockchain generates a new state tree annually. State modifications can only be done on the current and previous state trees. If a state does not exist in these trees, it is considered expired. Users must provide witnesses to resurrect expired states for use. The revived state then becomes part of the current state tree and can be modified as usual.

Concerns about this EIP include data redundancy, as the two most recent state trees could be identical, doubling node storage costs. Another concern is I/O cost, as each epoch has its own isolated tree, which may increase the number of reads/writes to disk, affecting client performance.

### BSC's State Expiry (MPT)
> 💐 One MPT + Stub + Refresh by touching

*Refer to [BSC State Expiry.](https://github.com/bnb-chain/BSC-State-Expiry)*


This proposal is inspired by Ethereum's State Expiry but uses only one Merkle Patricia Tree (MPT) and introduces a separate structure called ShadowTree. ShadowTree stores metadata corresponding to the MPT, and each node in the ShadowTree called ShadowNode records the epoch information that corresponds to an MPT node, determining if an MPT node has expired or not.

It uses the "refresh by touching" method, which means that once a node is accessed, its epoch will be updated to the current epoch in the blockchain. When a node or a subtree is expired, it will be replaced with a "stub" node, which is just a hash node (root hash of expired subtree).

To perform state revive, users can send a transaction that includes the necessary witnesses to revive the desired state.

There's already a demo for this, and you can try it out yourselves [here](https://github.com/node-real/state-expiry-poc/).

At first glance, we know that this definitely wouldn't on a mainnet. Why? Because it's using MPT proofs, and MPT proofs are way too large.

### BSC's State Expiry (Verkle Tree)
> 🍃 Only expire values from the leaf nodes

*Refer to [BSC State Expiry (VKT)](https://forum.bnbchain.org/t/bep-idea-state-expiry-on-bnb-chain/646/6?u=0xbundler)*


In this variation of BSC's State Expiry, the proposal again resembles the previous one but utilizes a Verkle Tree instead of a Merkle Patricia Tree. Instead of expiring entire subtrees with "stub" nodes, only the values in the leaf nodes are expired. Each value in the leaf node is associated with its own metadata, including an epoch value that determines whether it has expired or not.

To revive an expired value, a Verkle proof needs to be provided, but in this case, the proof only needs to demonstrate that the value is included in the commitment.

This implementation is more straightforward, but the effect of expiring values may not be as significant as it appears, as intermediate nodes still exist in the tree and could also be redundant.

### Solana's State Rent
> 💰 No pay no gain

*Refer to [Solana Docs.](https://docs.solana.com/developing/intro/rent)*

In Solana, the state is stored using accounts. An account includes metadata for the lifetime of the file, and it is expressed by a number of fractional native tokens called lamports.

The fee for every Solana Account to store data on the blockchain is called rent. Since Solana clusters must actively maintain this data, there is a time and space-based fee required to keep an account and its data alive on the blockchain. Accounts pay "rent" to hold their data in validators' memory. Each validator occasionally collects rent from all accounts. If an account is unavailable to pay rent (i.e. zero lamports), it is purged and removed from the network in a process known as garbage collection.

However, an account can become rent exempted if the account maintains a high enough lamport balance. A rent-exempted account does not have to pay rent and can still remain on the blockchain.

To summarize, by ensuring that accounts pay certain amount of fees to be stored on Solana, it reduces the amount of redundant data and ensure that accounts on the blockchain are the active ones.

### Mina's Recursive Proof
> 🤯 Constant 22kB blockchain size

*Refer to [What is Mina Protocol? - SK Kai.](https://skkai.substack.com/p/what-is-mina-protocol)*


Mina's design differs significantly from EVM chains, but its approach to maintaining a small blockchain size is intriguing. Mina utilizes a recursive SNARK system, where one SNARK can verify other snarks. This process creates multiple proofs that can be aggregated into a single block proof, submitted to the mainnet.

However, there are concerns regarding the time it takes to generate the proof, which can impact user experience. While the size of the blockchain may be small, processing the proofs requires a well-equipped machine.

### Soroban's State Expiration
> 👯‍♂️ Rent + Secondary DB

*Refer to [How Soroban is Solving State Bloat.](https://www.stellar.org/developers-blog/not-all-data-is-equal-how-soroban-is-solving-state-bloat-with-state-expiration)*


Soroban introduces two types of contracts: Persistent and Temporary. All states are stored in a specialized database model called BucketListDB. Temporary contracts are permanently deleted from the blockchain when expired, while persistent contracts are stored in Expired State Storage (ESS), another database. Users can use operations to recover desired contracts from ESS back to BucketListDB.

Persistent contracts expire based on rent, and the rent rate depends on the contract's storage size and duration on the blockchain.

While the proposal aims to improve node performance by removing unused data from BucketListDB, there are questions about its effectiveness in solving the state bloat problem, as the amount of expired data may grow as the blockchain expands, requiring additional hardware to maintain ESS.

## Thoughts
After examining all the proposed solutions, there doesn't appear to be a one-size-fits-all solution. Each approach has its tradeoffs, and the choice ultimately depends on what tradeoffs are deemed acceptable.

I'm also exploring some combination of the solutions. Here are some of them:

**Rent + Refresh by touching**
Every contract accounts will have an epoch. Contract accounts can forever stay on the blockchain. However, if a contract account has never been called or accessed, its balance will be deducted until its balance is 0, and the contract will be forever removed from the blockchain. The deduction amount is based on the contract's storage size. The deducted fee will also be reimbursed to validators.

Another variance of this idea is that, instead of determining whether to deduct contract balance based on whether the contract is being accessed or not in an epoch, we can determine whether to deduct the contract balance based on the amount of data being accessed in an epoch.

Let's say we set a rule such that if less than 20% of contract storage is being accessed in an epoch, then its contract balance will be deducted. For example, if a contract storage size is 100MB, in epoch 1, only 10MB is being accessed (<20%), then its contract balance is deducted.

The rationale behind this idea is to make it fair for all network participants. Validators should be compensated if they are storing your data permanently on a blockchain. But at the same time, if your contracts has high user activity, then validators wouldn't mind storing data for free.

**Cold DB + Hot DB**
Inspired by Soroban, why not have separate storage for "hot" data and "cold" data? Hot data refers to the state being accessed frequently, while cold data means that the state has not been accessed for a long time. Accessing cold data would incur a higher gas cost.

**Ethereum's State Expiry without ASE**
Address Space Extension (ASE) itself is a highly debatable topic within the community. Combining both State Expiry and ASE could potentially hinder the progress of State Expiry for an extended period. Is there a way we can implement State Expiry without relying on ASE?

Also, it'll be quite interesting if we can know how much states are active/inactive in the past 1 or 2 years. Might be working on a quick tooling for this.