BEP(v0.4): State Expiry With Verkle Tree
Motivation
BSC has completed the preliminary design and implementation of state expiry before, but BSC will always maintain full compatibility with the EVM ecosystem, so based on previous practice and design experience, it will bring State Expiry to the latest verkle tree design.
Verkle Tree is the next important feature after Eth’s Dencun hard fork. It will impact a lot in the EVM ecosystem, like state proof, witness, statelessness, etc. This proposal will be based on Verkle Tree and promise to be compatible with the statelessness feature.
Specification
Verkle Tree Transition
Verkle Tree is the next generation state trie structure, the purpose is to further reduce the state proof size, in preparation for the subsequent statelessness.
The main differences between it and MPT are as follows:
- The trie structure is extended from 16-ary to 256-ary;
- Merge the two-layer trie structure, L1 Account Trie and L2 Contract Storage Tries into a single huge trie;
- Divide the Contract Code into Code Chunks and save them in the trie;
- The cryptographic proof is switched to Pedersen+IPA instead of hash-based;
The above pic is from Verkle tree structure | Ethereum Foundation Blog.
In order to implement State Expiry in the verkle tree, it is necessary to convert the MPT of the BSC to VKT. This part will not be described in detail, but it is an important part of the scheme.
State Epoch
The state is generated on the chain through the transaction initiated by the user. Before, the user only needs to pay once to store it permanently, but now all the states accessed by the user exchange cannot exceed two state epochs.
At the same time, in order to greatly improve the user experience, whenever the state is accessed, the status will be automatically renewed, and the state will be expired in the next of the next epoch.
This proposal will not change the current transaction gas pricing mechanism, and only contract storage slots could expire, other states will never be expired.
Epoch-based Metadata
The proposal only adds epoch as metadata in the value node. Since the value in the verkle tree is divided into two parts, the epoch information is encoded at the end of the second part, and the epoch is generally expressed as 2 bytes in size, which also does not exceed the limit of the IPA algorithm.
In addition to the verkle tree, the epoch metadata is also saved redundantly in the snapshot, especially after the value node expires, which is used to judge expired data.
LeafNode Operation
Because the state expires only in the value node of the LeafNode, there are two situations for the commitment update of the LeafNode:
- The children’s value node is not expired, and the operation is as usual;
- If any number of children value nodes expire, any access to expired value nodes will be reverted, and when CRUD other nodes, the LeafNode will be updated by
commitment diff;
Resurrection Conflict
Generally speaking, there are two cases of resurrection conflict:
- After a status expires, the user creates a new state in the same slot, which conflicts with the previous expired state;
- The state has expired many times in history, and the user revives the non-recently expired state when reviving;
Both of these can lead to abnormal user behavior and the risk of attack. However, this proposal can avoid the above two situations.
After the slot expires, the original cryptographic proof will still be retained in the Verkle Tree. Therefore, the corresponding proof must be provided to resume it. When the slot expires multiple times, the latest expired proof will be used.
Witness
Since only the value of the LeafNode in the whole tree will expire, when generating the witness, it is only necessary to prove that the value is included in the commitment of C1 or C2 of the LeafNode, and the value should carry the expired epoch information, and the EVM will automatically refresh the epoch metadata after resurrection.
type ReviveWitness struct {
witnessType byte // only support leaf value IPA Proof for now
address *common.Address // target account address
proofList []LeafValueIPAProof // revive multiple slots (same address)
}
type LeafValueIPAProof struct {
key []byte // key, to find stem & leaf index
proof []byte // proof value for commitment of C1 or C2
value []byte // value with history epoch metadata
}
Witness Size
The size of the witness is small enough, and the most important thing is the constant size, so the cost of restoring a fixed number of states grows linearly and is predictable.
New Transaction type
To support state revive, this BEP introduces a new transaction type, while the current transaction type can still be used in most scenarios, called LegacyTx, the new transaction type in order to maintain compatibility, begin with a single byte REVIVE_STATE_TX_TYPE in the RLP format, the complete transaction definition is as follows:
type SignedReviveStateTx struct {
message: ReviveStateTx
signature: ECDSASignature
}
type ReviveStateTx struct {
Nonce uint64 // nonce of sender account
GasPrice *big.Int // wei per gas
Gas uint64 // gas limit
To *common.Address // nil means contract creation
Value *big.Int // wei amount
Data []byte // contract invocation input data
WitnessList []ReviveWitness
}
The ReviveStateTx structure is similar to LegacyTx, with the StateWitness array added for batch state revival. ReviveStateTx will verify witness and revive state first, and continue to execute transfer, contract calls and other behaviors as normal transactions.
If the user only wants to revive the states of the contract, it is suggested to simply read the contract or guarantee that the transaction can not revert.
State Expire & Prune
A state with no access in two epochs will be marked as expired, and all expired states cannot be accessed again, and the expired value will be deleted through asynchronous prune.
Any access behavior with expired status will cause revert and return the corresponding error code to the user.
Rationale
Why Keep All Account Data And Contract Codes
There are several reasons to keep it:
- The size of the account data is relatively small, constituting only around 4% of the storage slots on BSC as of the end of 2022.
- The account data contains crucial information about user accounts, such as their balance and nonce. If users were required to revive their accounts before accessing their assets, it would significantly impact their experience.
Reasonable Epoch Period
The state will expire if it has not been accessed for at least 1 epoch or at most 2 epochs. On average, the expiry period is 1.5 epochs. If we set the epoch period to represent 2/3 of a year, then the average state expiry period would be one year, which seems like a reasonable value.
Why Not Expire Intermediate Nodes of The Trie
Because in the Verkle Tree proposal, all Account Data, Contract Code Chunks, and Contract Storage Slots are stored in one tree. At the same time, the width of each node in the tree is expanded to 256.
So if only Storage Slots expire, there is a very small probability that a large number of subtrees will expire as a whole, and at the same time, the storage cost of adding more Archive Nodes to the previous shadow tree is avoided.
Finally, the intermediate nodes of VKT are reserved, and only the leaf value nodes are expired.
Storage Growth
This proposal is not a perfect solution. The purpose is to slow down the state growth of BSC in the future. At the same time, it can reduce the state maintenance of historically low-frequency access and make the validator/full node lighter.
However, this proposal retains the intermediate nodes, and cannot completely remove the storage impact of the existing state or the new state. Yes, it can only reduce the speed of storage increase.
Forward Compatibility
Account Abstraction
Account abstraction implementation will be impacted, as these accounts could be stored in the L2 storage trie and could be expired.
L2 Rollup: Optimism & ZK
Rollups could be impacted if the rollup transactions try to access expired storage.
Statelessness
Statelessness is a proposal with great influence in the community, which can further improve decentralization and reduce node operating costs.
Fortunately, this proposal has the greatest flexibility, retains the original tree structure, can continue to optimize the solution in the future, and upgrade to statelessness is also supported.
Backward Compatibility
Transaction Execution
The current transaction types will be supported, but if the transaction tries to access or insert through expired nodes, then it could be reverted.
User Experience
There are several changes that could affect user experience. The behavior of many DApps may change and users will have to pay to revive their expired storage. If the revival size is very large, the cost could be expensive.
Web3 API
Some of the APIs could be impacted, such as getProof, eth_getStorageAt…
Snap Sync
The snap sync mode will heal the world state after the initial block sync. The procedure of world state healing in snap sync mode will need to be updated.
Archive Node
More storage volume would be needed for the archive node, since more metadata will be generated in each epoch. Archive service may have to be supported by other approaches.
Light Client
The implementation of the light client would be impacted since the proof of expired state would also be needed. And in this proposal, only the archive node could prove an expired state.
License
The content is licensed under CC0.