State scale is a deteriorating problem, and the solution of state scale can also pave the way for significantly increasing the block gas upper limit. We should reach a consensus on some form of state expiration plan and implement it.
Original title: “Views | Ethereum State Scale Management Proposals”
Written by: Vitalik Buterin
Translation: Ah Jian, from an Ethereum enthusiast
One of the longest and unresolved challenges facing the Ethereum protocol is the problem caused by the growing scale of state data. Many operations on the Ethereum blockchain (create an account, write into a contract storage slot, send ETH to a new account…) will add state content to Ethereum (that is, add data objects to state data), and All full nodes must store the full amount of state data so that new blocks can be verified and new blocks can be manufactured. These operations simply send a one-time transaction’s amount to pay by Gas metering fee, but will cause permanent ongoing costs to the entire network, since nodes need to store new data (and the next node also needs to join in sync Download these data in the process).
This is a significant imbalance in the system design, which may make the Ethereum system more and more difficult to use, because the state is full of “junk data” that is no longer useful. The purpose of this article is to explain in detail the root cause of the problem and some ways to solve the problem. If we can implement a certain solution, this will pave the way to safely and significantly increase the block Gas upper limit.
The research field discussed in this article is still advancing, and newer, better ideas and more elegant trade-offs may appear at any time.
Introduction: Where is the problem?
” State ” refers to the information that a node must have if it wants to process newly generated blocks and transactions. State is completely different from ” history “. The latter is information about past time. Nodes can save this information for rebroadcasting or archiving in the future, but it is not necessary for processing the blockchain.
In the Ethereum protocol, status information includes:
- ETH balance and nonce (serial number) of the account
- Smart contract code
- Smart contract storage items (storage)
- Data related to the consensus mechanism (recent block hash value, uncle block; consensus data for proof of equity also includes the verifier’s public key and its activities recorded on the beacon chain, etc.)
The historical information consists of old blocks and receipts. There is no opcode in the EVM that allows you to access old blocks, old transactions and content and receipt output, so nodes discarding these data can still verify new blocks, so these are historical information.
The last item in the above state information list-the consensus mechanism-related data-has been carefully designed to limit its scale, so we don’t need to worry about it. But the first three items are really daunting. The scale of these three types of status information will continue to increase over time, because new users will continue to join the network, they will create new accounts, new contracts, join contracts, receive tokens and so on.
What is difficult is that after many states are used, they will lie there quietly (will not be touched again); once a user disables an application, some “junk states” will be generated-no more It comes in handy, but it will always be there.
Theoretically, users can achieve “the garbage does not fall.” Users can only publish a contract with SELFDESTRUCT conditions, and when they can no longer use the contract, they can call this opcode to remove the contract and clear their token balance; they can also use a smart contract wallet to pass an existing Externally held account (EOA) to send transactions without generating a new EOA (EOA status cannot be deleted).
But in practice, such incentives are very few, and the technical complexity of proper state cleaning is too great. In many contracts, it is not appropriate to give anyone the permission to call SELFDESTRUCT in this way (what people want is an ” SELFDESTRUCT ” application!), and it will also add a lot of complexity to the user experience and code. . In fact, since SELFDESTRUCT extremely limited usefulness and great side effects, I prefer to remove this opcode forever. If we really want to control the size of the state of the data, what we need is a node in the network “junk status” is no longer used to discard method may default.
Stateless client
One type of solution to this problem is based on the concept of ” stateless clients ” (this article discusses the source of this concept, here is the speech video). The basic principle is that block verification is no longer premised on holding global state. On the contrary, the block will bring its own evidence (or ” witness “) to prove the value of the state it is visiting. Just like the current design, the block will contain a ” state root “, and the accessed value can be proved corresponding to the state root (Translator’s Note: Merkel proof is a common proof technique ). Ethereum’s current state tree scheme (Merkel Patricia tree) supports such proof technology, and more efficient schemes such as binary trees or Verkle Trie are also available. The witness data will also prove the correctness of the new state root after processing the block.
There are two forms of statelessness:
Weak statelessness : The block producer still needs a complete state to generate witness data for the block (made by itself); but the stage of verifying the block can be stateless;
Strong statelessness : no node needs a complete turntable. In turn, the transaction sender needs to provide witness data, and the block producer can aggregate these data. The transaction sender is responsible for storing part of the state tree required to generate witness data for the account in question.
Strong statelessness is a very “elegant” solution, because it completely transfers the responsibility to the user, although in order to ensure a good user experience in practice, we need to create certain types of protocols to help users who do not run personal nodes Maintain status and handle situations where users need to interact with unexpected accounts. It is very difficult to build such an agreement.
In addition, all types of statelessness increase the data bandwidth required by the network; and strong statelessness also requires transactions to declare the keys of the accounts and storage items they interact with (conceptually this is called an ” access list “).
A more gentle solution: status expired
A more moderate solution can be boiled down to different forms of ” status expiration ” solutions. The state that must be continuously accessed can be maintained in the “active state”; and the state that has been unattended for a long time will become “inactivated” (or “expired”). There are many options for the specific mechanism to update the state (for example, prepaying the “rent”, or simply accessing that state), but the general principle is that unless a state object is explicitly updated, it will be in some form of failure. Alive. Therefore, any activity that creates a new state object (and updates an existing state object) can only become a burden on the node for a period of time, instead of becoming a permanent burden like it is now.
The deactivated state, as the name suggests, is not part of the “state”; nodes that want to process or create blocks do not need to store the deactivated state. However, the deactivated state is not completely deleted! In all types of state expiration proposals, a certain method is preset to “resurrect” the inactivated state .
The general principle is that the use of the active state is the same as the current one, while the inactive state needs to be used through the aforementioned stateless client mechanism. A transaction that resurrects an object in an expired state needs to provide a proof (witness data) to prove that the object is part of the inactive state. In order to be able to generate such evidence, the user himself needs to store and maintain at least a part of the deactivated state (corresponding to the part of the deactivated state object that he is concerned about).
When will it expire
There are also many designs that determine expiration conditions. The most common ones are:
- Direct rent : Collect the “rent” block by block, and pay directly with the balance of each account (or other state object); when the balance of the state object drops to zero, the account expires.
- Remaining survival time value : each state object stores a “remaining survival time” value, which can be increased by paying a fee
- Refresh when touched : Each state object stores a “remaining time to live” value, and this value is increased every time the account is read or written
- All state objects expire regularly (for example, once every 6 months): that is, the ReGenesis proposal
I personally like the “touch-and-refresh” solution more and more because (1) it avoids the need for applications to create complex economic models to allow users to bear the state rent; and (2) it ensures that the scale of the activation state has a clear Upper limit (区块Gas 上限/ 触达状态对象的Gas 消耗量× 状态存活的时长). The scheme that allows a large number of states to expire at regular intervals (aka ReGenesis) has the same benefits, but there are also some interesting trade-offs: the key advantage is that the expiration scheme is simpler (no need to traverse the entire state tree and inactivate the states one by one. Object), but the key shortcoming is that when you activate your own state object after an expiration point in time, how much witness data you need will depend on the time point when you touch the state object.
Expiration at the account level vs. Expiration at the storage slot level
The logic of state expiration can be operated at the account level or at the level of a single storage slot. Currently, I strongly prefer to implement the state expiration scheme at the storage slot level. Because the number of storage slots in many contract accounts is unlimited, any user can join the contract and increase the number of storage slots under the contract name (for example, airdrops are a case that has already occurred). Regardless of the account-level expiration scheme used, if you want to actually limit the scale of the state, the amount of rent must be proportional to the number of storage slots in the contract (or the survival time is inversely proportional to it). As a result, the user is able to pay only a one-time fee and give the user applies a permanent contract for ongoing costs.
To solve this problem, the contract must either add complex internal logic to “pass on” the storage operation rent to the user, or redesign the model of your own contract, switch to using the CREATE2 opcode to create new contracts and use these contracts as storage slots. Either way, it will eventually become an expiration scheme equivalent to the storage slot level. Therefore, I personally believe that we should only implement the state expiration scheme at the contract storage slot level.
However, the expiration scheme at the storage slot level also has its own shortcomings: each storage slot needs to add a metadata indicating when it expires (or whether it has been inactivated), which also means “resurrection conflict problem” (see Below) will not only affect the account, but also the storage slot.
Remove from the state tree vs. Arrange a “retirement” part of the state tree
Another technical point of view to distinguish between different state expiration proposals is “one tree flow” and “two tree flow”. In other words, do we have only one state tree like now, but mark some states as expired; or directly remove the inactive state from the main state tree and transfer it to another special ( On the tree (or other data) that only contains the expired state?
One tree stream
Active nodes are marked in white, and deactivated nodes are marked in gray
Note that even the intermediate nodes on the tree will be marked as activated or misfired (or, in a more realistic scheme, each node will be marked with the deactivation date, so its activity can be easily checked); the marking can be done It is done at each node (leaf node and intermediate node) on the state tree.
Two Tree Stream
The white tree contains the active state; the gray tree stores the inactive state
The advantage of a tree flow is that, at least, its working method looks similar to the current state tree, and the process of deactivation and resurrection is relatively simple: the resurrection process only needs to refresh the “expiration date” parameter of the relevant node on the tree, and Inactivation is automated. But its disadvantage is that it needs a tree structure that can store intermediate information in this way in the nodes, and it cannot be extended to Verkle trees well. In addition, it also requires additional Merkel proof components, not only to be able to sink to the leaf node, but also to be able to stop at the intermediate node (when it needs to prove that a certain part of the state has expired).
The advantage of the two-tree flow is that the current, purely state accumulator can support this kind of scheme without adding metadata for each node. The disadvantage is that it requires some deeper changes to the entire protocol, and an explicit process is needed to inactivate the state (so expiration is no longer automated). In addition, it does not provide a built-in solution to the resurrection conflict dilemma (see the next section), so you need to choose between two methods.
Note that in the two-tree stream, the data structure that stores the deactivated state is not a tree. In fact, such a design is entirely possible: When a state object needs to be resurrected, only a Merkel tree pointing to the receipt when the object is deactivated is provided, and some cryptographic evidence is attached to prove that the object has not been It has been resurrected (or re-expired recently).
Resurrection conflict
Then we come to a key problem of the state expiration scheme: ” resurrection conflict “. The concept of resurrection conflict is as follows. Suppose an account is generated by address A; this account expires; then, address A creates a new account (for example, use the CREATE2 opcode to ensure that the address of the account generated twice is the same); finally, address A again Try to revive the original account. What will happen at this time?
There are several possible solutions:
Explicit “account consolidation” process : similar to the stipulation that “except for the accumulation of ETH balances of the two accounts, the status of the old account shall prevail” or “except for the accumulation of ETH, the status of the new account shall prevail”; Therefore, the special merger process can be specified by the contract code of the old account
By eliminating the repeated deployment of the same address to ensure that the resurrection conflict does not occur : that is, adjusting the function of CREATE2, such as including the current time in the original image of the final hashed address, so even if the same data is used in the future to generate Can’t get the same address
Add a “stub” to the state object to prevent new accounts from being generated at the same location (the above-mentioned one-tree flow method automatically implements this function)
When a new account is required to be generated, it must be accompanied by proof that the account has not expired before : in a sense, it is equivalent to the stub scheme, but this method is to put the stub in a separate part of the state, so anyone who wants to create a contract account Of users must track this part of the state
(Note that if we use the storage slot expiration solution, any of the above solutions must be extended to the single storage slot level, not the account level)
The main concerns are: (1) It will add a lot of complexity to the application, they need to add the logic of merging; (2) After doing this, unless an address is “registered” on the chain, the user will not be able to easily obtain it. Interact with it and accumulate the addresses of assets (such as ERC20 tokens). An unregistered address is important: any user who receives ETH for the first time is using an unregistered address. The root of this concern (2) is that the unregistered address actually has a time limit. If a user generates an address and receives funds, but forgot to send the transaction in the next year (that is, forget ” Register”), then his funds will be locked.
Note that EOA is not immune. Although it seems to be possible, because the merger process of EOA is relatively simple (just add the old ETH balance to the new one, for nonce there is EIP 169). However, there are also two problems here. First of all, the goal of account abstraction is to replace EOA with contracts, and the merger process of account abstraction contracts may not be simple. Secondly, it is not only the EOA itself that will be affected by the expiration and resurrection events, but also the related storage keys (such as the ERC20 token balance) in the applications that the EOA participates in, so complex merging logic is still required.
Therefore, from my perspective, the least disruptive is some form of stub scheme. However, there is an information theory problem in the stub solution that can lead to some strange results. In order to prevent new state objects from being created at N expired state object locations, a set that covers these N addresses (and/or storage keys) must be part of the state. If this set is information-minimized (that is, only contains these addresses), then the size of this set will be O(N), so its state size will also be O(N); then, the size of the activation state will be the same as the loss The scale of the living state is proportional , so in fact we did not solve this problem.
Tree rot
The only way to solve this problem is to cover the information of more than N accounts; in fact, we will have to make the entire tree inaccessible (again, this is the essence of the one-tree flow solution: if two accounts Expired, all the space between them will be implicitly expired (if two accounts get expired, all the space in between them also implicitly gets expired).
And here is another problem: this creates a form of “tree rot”, over time, for the creation of new accounts, all parts of the state tree are inaccessible, at least for those This is true for users who have not tracked the expired status of the area.
The secondary problems caused by moldy trees must also be resolved. For example: if a contract is to create a sub-contract, it must be able to create a contract in a state area where either it is not moldy or the user has witness data (may require a “reminder” provided by the user). A solution to the moldy tree problem can be found here: continuously open new areas for account creation. Another idea is that each user selects certain areas of the state (for example, 1/256 of the state), tracks changes in this area (including the expired state) in order to be able to create witness messages, and only create accounts in this area.
Another problem with moldy trees is that it requires an explicit data structure to store and check ranges. If a tree has data that can be placed in a node to indicate which parts of the node have expired (as used in the one-tree flow solution), that is the best, but a key-value pair storage is required This is still quite difficult.
Strong statelessness
Many problems arising from using the tree structure in the state expiration scheme can be traced back to the fact that we need to reach a consensus on which states are active and which states are inactive . In the two-tree stream mode, this is more obvious; but even in the one-tree stream mode, an explicit mark is required on the state tree so that the Ethereum node that has downloaded the state using fast synchronization in the near future can determine an attempt A transaction that accesses an account without providing a witness message should succeed or fail. Can we make this distinction unnecessary?
If we achieve complete statelessness, and then can help transaction senders and block producers to reliably obtain the state required for witness message generation, wouldn’t this problem be solved? So what can help transaction senders and block producers do this?
A natural way is: the nodes in the network only store a part of the state tree, for example, the part visited in the past year. Just add a voluntary setting in the client settings. If we want to be more reliable, we can introduce a proof of custody scheme to force at least the miner (the validator of PoS behind) to store some data.
One thing to note: If the consensus layer cannot perceive which states are active and which states are inactive, then the gas cost of accessing the recent state and the old state is the same. This leads to two results:
Gas overhead for accessing recent status also needs to be further increased
The upper limit of the block size containing the witness message may be very large. If a block is full of transactions accessing the old state (about
800 bytes * 12.5 m gas / 2400 gas per access ~= 4.1 MB, it is assumed to be implemented) EIP-2929 was converted into a binary tree)
If we want to avoid these unfavorable factors, we need to track which state objects (including the unfilled address space area) are active in the consensus, which will bring us back to the attributes close to the state expiration scheme. This once again illustrates that “statelessness vs. state expiration (state rent)” is a spectrum, a complex space for weighing, and not an either-or choice.
Rollup also needs, and can use the same solution
An important medium-term scalability solution for Ethereum is rollups. However, rollup itself does not no longer need to worry about the state data scale problem; in fact, the state scale problem of the rollup system is exactly the same as that of the Ethereum chain itself.
Fortunately, if we can launch a solution, at least EVM rollup (a rollup solution that tries to replicate the Ethereum operating environment to the greatest extent) can use the same solution to solve the scale problem of its internal state. Therefore, state size management solutions are complementary to rollup and sharding scalability solutions (state size management is complementary to rollups, sharding and other scaling strategies).
(Translator’s Note: I personally think that the term “complementary” here is seriously misleading.)
in conclusion
State scale is a deteriorating problem, and the solution of state scale can also pave the way for significantly increasing the block gas upper limit. We should reach a consensus on some form of state expiration plan and implement it. However, there are major technical trade-offs between different solutions, especially if we still want to maintain some important attributes of the current design.
Some attributes that we may need to sacrifice include:
The user can generate an account offline and receive funds with this address, and can be silent for any length of time before making the address visible on the chain
The address keeps the length of 20 bytes (the rolling state expansion scheme requires a larger address space, although the length of the address may have to be changed quickly for the sake of collision resistance)
The state can be regarded as a “pure” key-value pair storage attribute, and the attribute that does not need to store metadata in each node on the state tree
Existing applications require varying degrees of rewriting to ensure that users can generate witness data without storing all inactive states
Gas consumption; or difficulty of creating new contracts and writing to new storage slots
If we are ready to make sacrifices, some plans can begin to be realized soon. On the other hand, maybe in time, we can fix or better aggregate these ideas, reduce problems, especially to make them technically easier to implement (for example, allow the use of “pure” key-value storage). We should have a deeper understanding of what sacrifices we are more willing / less willing to accept, and continue to actively study improvement proposals.
Source link: hackmd.io
