BEP(Idea v0.1): State Expiry On BNB Chain
1.Motivation
Storage has always been a big challenge for blockchain, since the data may not be deleted and it keeps growing.
Ethereum proposed EIP-4444, trying to prune history block, header, receipt to make the node lighter. But it didn’t touch the storage, which could be even larger than blocks.
Before addressing the storage challenge, there are some universal rules that we think are reasonable:
- Very old data is most likely seldomly used.
- The on-chain storage is very expensive, it would be better for users to delete unused data timely. But if they fail to do it, old data can be dropped from the chain.
- Simply deleting is not acceptable, since the user should have the ownership of its own data. It is necessary to provide a mechanism to restore it in case the user wants it back and they may need to pay for it.
- Users should be able to know the state of its account.
Keeping these rules in mind, helps us find potential solutions to address the storage challenges.
2.Where We Are
There are several different approaches to address the state growing problem across the blockchain industry during the past few years.
2.1.ReGenesis: Stateless
It was posted at June 2020, refer: ReGenesis Explained
Generally it is about only keeping the root hash and rebuilding the world state from scratch at a deterministic schedule, like 1,000,000 blocks. The block producer(miner or validator) only needs to keep the latest rebuilt state, which is much smaller and the unused state no longer needs to be revived.
It is a bit like the concept of Stateless, users can revive the useful state by sending transactions with witnesses.
The problem is that it could have a very heavy state revive at the beginning of ReGenesis, since it empties the whole state on ReGenesis.
2.2.Economy: Pay For Storage
Some of the chains try to solve this problem by economy, they may use different storage rent policies, but generally, users need to pay for the storage, as long as users stop paying for it, their data would be deleted.
Some of the projects you may refer:
Actually it is a good idea, but it needs to be done at the very beginning. For chains that are already running, it is not easy to change its economy model.
2.3.Epoch Based State Expiry By Vitalik
Vitalik introduced the idea of epoch based state expiry and posted several articles on it:
#1: 2021.01.30: Alternative bounded-state-friendly address scheme
#2: 2021.02.12: Theory of Ethereum State Size Management (recommend)
#3: 2021.02.23: Resurrection-conflict-minimized state bounding, take 2
#4: 2022.01.04: A few paths to statelessness and state expiry (recommend)
The main points include:
- Refresh by touching
- 4 bytes epoch prefix for account address
- Epoch State Trees
- A new opcode: Create3
- Verkle Tree
I think valitak has explained his idea clearly in his blog, I will not repeat it here, you may directly refer article #2 and #4 to understand his proposal.
It is a great design, but it is quite complicated and there is tremendous work that needs to be done. And the Ethereum community is not quite active on this topic, maybe it is not that urgent for Ethereum and has a relatively low priority compared to other EIPs like staking withdrawal or proto-danksharding. There is no EIP for it yet, it could take a very long time to make it in ethereum.
3.Proposal For BNB Smart Chain
Although BSC(BNB Smart Chain) was launched at around Aug 2020, it now has much bigger storage size compared to Ethereum and gives state expiry a higher priority.
I would propose an idea trying to eliminate the storage pressure for BSC at some level and make a tradeoff between perfectness and complexity.
It is still an idea yet, needs to be improved.
3.1.General Workflow
a.ExpireDepth & TouchedBlock
There will be a configuration: ExpireDepth, which demonstrates the maximum block depth that can be accessed, it could be: 10,000,000.
There will be another element TouchedBlock added into the Account structure to record the latest block that an account has been successfully touched.
type Account struct {
Nonce uint64
Balance *big.Int
Root []byte
CodeHash []byte
TouchedBlock uint64
}
When a transaction tries to access a contract storage, it has to check the TouchedBlock of the target account. If the account is expired, i.e. it has not been accessed for a long time, the access will be denied and the transaction will be reverted. Otherwise, the access will be ok.
b.State Expire Operation
There is nothing that needs to be done, since state expiration occurs automatically as long as the TouchedBlock has not been updated for a long time.
When the contract account expires, its storage state would no longer be accessible.
Quite similar to downgrade a contract account to an EOA account, but the “EOA” account has: root, nonce, balance, codehash, LastAccessedBlock. And the “EOA” account can be revived later to upgrade back to a contract account.
c.State Revive Operation
- A new transaction type will be added, it can provide witnesses to revive the state,the witness data could have a size limit.
- The state object can be revived through several transactions, if the witness is too large, which means partial revive will be supported
- Anyone can restore the data as long as it is willing to pay, once all the state of the object is ready, the validator could update its LastAccessedBlock to activate it.
d.Witness Tree & Node
Introduce these 2 concepts to support partial revival.
- Witness Tree: it is the partial revived tree.
- Witness Node: it is a special node type in Witness Tree, it provides proof but its branch nodes are not revived. Accessing the branch nodes of Witness Node will cause the transaction to revert as well.
e.EOA Account
Currently the EOA accounts will never expire, since it does not take too much storage compared to contract accounts. Only contract storage will expire.
But in the future, if EOA accounts grow to an unacceptable level, maybe they can be aggregated into an Witness Node, but it could face the same problem as Vitalik described: the shrink of the usable address space. It is that urgent for BNB Chain yet, could leave it right now.
3.2.Some Thoughts
a.Opcode: Create2
Create2 could generate contracts at the same address.
It is not allowed to create a new contract on an expired address, and will revert the transaction. The expired contract has to be fully revived before Create2 opcode can be executed.
b.Account Level or Key Level
Key level could add more complexity, if we add the TouchedBlock for every Key, it also gives pressure to storage.
So Account level is preferred.
c.Rollups & Abstract Account & Verkle Tree
Need further investigation to see if it will impact the implementation of Rollups, Abstract Account and Verkle Tree.
d.The Block Size
If the block is full of state recovery transactions, which contains lots of witness data, it could make the block very big. It should be avoided.
e. MEV & Incentive
Validator may prefer or not prefer these witness transactions?
How to encourage validators to include such kinds of transactions, low incentive would make validators unwilling to include it.
And some accounts could do extra work to prevent its data from being dropped, they may send heartbeat transactions to keep it alive. This is not what we intended, and we need to fix it.
f. Security
Need further investigation.
g.Compatibility
More transactions could be reverted, if they access expired state.
