Blockchain’s State Explosion Dilemma
secondary title
Layer 1 should focus on state
If we believe that blockchain layering is the future direction of development, we should consider the needs of upper-layer protocols and layered networks from the very beginning, and design blockchain protocols in a layered framework.
In other words, from a layered perspective, existing blockchain designs are outdated. Existing blockchains are designed with specific functions in mind (such as payment, or running DApps), and hope that the upper layer protocol will adapt to itself after a period of operation. However, if we read the history of the Internet, we know that the protocol layering of the Internet today is not patched in this way, but after absorbing past experience. This is why the blockchain is not naturally Layer 1, and Layer 1 needs to be designed.
To figure out what Layer 1 should focus on, we must first figure out the difference between it and the upper layer protocol. The origin of Layer 2 is related to our discovery that the performance of the public chain (here refers to the permissionless blockchain) is insufficient, and it is difficult to expand to meet the needs of the entire encryption economy. Slowly evolved a series of Layer 2 protocols that can be secured by blockchain, such as payment channel, plasma, etc.
The common feature of these protocols is to sacrifice consensus range in exchange for performance. The most amazing thing about the public chain is that it provides uninterrupted services covering the world through an open network, which means global consensus and low performance.
The best way to solve this problem is to transfer most of the transactions to an upper-layer protocol with a smaller consensus scope but better performance, and to ensure that participants in the upper-layer protocol can always return to the blockchain to solve the problem when they are dissatisfied , the cost is only some time cost.
secondary title
what is the status
Every full node in the blockchain network will leave some data on the local storage after running in the network for a period of time. We can divide them into two categories according to history and present:
Every full node in the blockchain network will leave some data on the local storage after running in the network for a period of time. We can divide them into two categories according to history and present:
History: Both block data and transaction data are history, and history is the path from Genesis to the current state.
State (ie now): The final result formed by the node after processing all blocks and transactions from Genesis to the current height. The state is always changing with the addition of blocks, and the transaction is the cause of the change.
The role of the consensus protocol is to ensure that the current state seen by each node is the same through a series of message exchanges, and the way to achieve this goal is to ensure that the history seen by each node is the same. As long as the history is the same (that is, the ordering of all transactions is the same), the way of processing transactions is the same (executing the transactions in the same deterministic virtual machine), and the current state seen at the end is the same. When we say "the blockchain is immutable", it means that the history of the blockchain cannot be tampered with, on the contrary, the state is always changing.
secondary title
Example: History and State of Bitcoin
The state of Bitcoin refers to the current state of the Bitcoin ledger. The state of Bitcoin is composed of UTXOs (transaction outputs that have not yet been spent), each UTXO represents a certain amount of Bitcoin, and a name (scriptPubkey) is written on each UTXO to record who the owner of this UTXO is. If an analogy were to be made, the current state of Bitcoin is a bag full of gold coins, each engraved with the owner's name.
The history of Bitcoin consists of a series of transactions, and the main structure within the transaction is the input and output. A transaction changes state by marking some UTXOs contained in the current state (those referenced by transaction inputs) as spent, removing them from the UTXO set, and then adding some new UTXOs (the outputs of this transaction) to the UTXO set go.
It can be seen that the output (TXO, Transaction Output) of the Bitcoin transaction is exactly the UTXO mentioned above, and UTXO is just a TXO in a special stage (not yet spent). Because the components that make up the state of Bitcoin (UTXO) are also the components that make up transactions (TXO).
Therefore, Bitcoin has a wonderful property: the state at any time is a subset of history, and the data types contained in history and state are of the same dimension. The history of transactions (the collection of all packaged transactions, that is, the collection of all generated TXOs) is the history of the state (the collection of UTXOs corresponding to each block, which is also the collection of all generated TXOs), the history of Bitcoin Contains only transactions.
secondary title
Another example: the history and state of Ethereum
The state of Ethereum, also known as the "state of the world", refers to the current state of the Ethereum ledger. The state of Ethereum is a Merkle tree composed of accounts (accounts are leaves). Accounts not only record balances (representing a certain amount of ether), but also contract data (such as the data of each encrypted cat). The state of Ethereum can be regarded as a large ledger. The first column of the ledger is the name, the second column is the balance, and the third column is the contract data.
The history of Ethereum is also composed of transactions. The main structure inside the transaction is:
to: another account, representing the sender of the transaction
value: the amount of ether carried by the transaction
data: any information carried by the transaction
The way the transaction changes state is that the EVM finds the target account to which the transaction is sent,
1. Calculate the new balance of the target account according to the value of the transaction;
2. Pass the data carried by the transaction as a parameter to the smart contract of the target account, run the logic of the smart contract, and may modify the internal state of any account during operation to generate a new state;
3. Construct a new leaf to store the new state, and update the state Merkle tree.
It can be seen that the history and transaction structure of Ethereum is very different compared to Bitcoin. The state of Ethereum is composed of accounts, while transactions are composed of information that triggers account changes. The state and transactions record completely different types of data. There is no superset and subset relationship between the two. History and state contain The data type of is two-dimensional, and there is no necessary connection between the size of the transaction history and the size of the state.
After the transaction modifies the state, it will not only generate a new state (leaves in the solid line box in the figure), but also leave the old state (leaves in the dotted line box in the figure) as a historical state, so the history of Ethereum not only includes transactions, but also Contains historical state.
Because the history and state belong to different dimensions, the Ethereum block header not only contains the merkle root of the transaction, but also needs to explicitly contain the merkle root of the state.
Every block and every account in Ethereum will continue to occupy the storage space of the node. Ethereum nodes have multiple modes when synchronizing. In Archive mode, all history and status will be preserved, including history transactions and historical status. The combined size of all data exceeds 2TB; in Default mode, the historical status will be It is cut off, and only the historical transaction and current state are kept locally. The total data is about 170G, of which the transaction history size is 150G, and the current state size is 10G.
All overhead management in Ethereum is unified under the gas billing model. The size of the transaction needs to consume the corresponding gas, and the gas consumed by each EVM instruction not only considers the computing overhead, but also takes into account the storage overhead. Through the gaslimit of each block, the growth rate of history and state is indirectly limited.
ps. A common misunderstanding is that the "blockchain size" of Ethereum has exceeded 1T. From the above analysis, we can see that "blockchain size" is a very vague definition. If the historical state is counted, it is indeed exceeded, but for all nodes, there is no problem in deleting the historical state, because As long as there is Genesis and transaction history, the historical state at any moment can be recalculated (regardless of the time required for calculation).
The truly meaningful data is the size of data necessary for a full node. Bitcoin is 200G, and Ethereum is 170G. The two are basically the same, and can be installed on an averagely configured cloud host. The reduction is not due to increased storage (the root cause is computational overhead at synchronization).
secondary title
The Tragedy of (Storage) Commons: The Blockchain Version of the Tragedy of the Commons
The tragedy of the commons refers to a situation where a limited shared resource is over-consumed by people with unrestricted use. The storage paid by blockchain nodes to preserve history and state is just such a shared resource.
There are three types of resources consumed by blockchain nodes to process transactions, CPU, storage and network bandwidth. Both CPU and bandwidth are resources that will be refreshed in each block. We can think that the same amount of CPU and bandwidth are available for use in each block interval. The CPU and bandwidth consumed by the previous block will not let the next block Less CPU and bandwidth available for blocks. For refreshable resources, we can compensate nodes through a one-time payment of transaction fees (refer to RFC0015Appendix for the correlation between fees and computational complexity and transaction size).
Unlike CPU and bandwidth, storage is an occupied resource. The storage that is occupied in a block cannot be used by other users in subsequent blocks unless the user actively releases it. Nodes need to pay for storage continuously, but users do not need to pay for storage continuously (remember that transaction fees only need to be paid once).
Users only need to pay a small fee when writing data to the blockchain, and then they can permanently use a storage whose availability exceeds Amazon S3, and its infinite permanent storage costs need to be borne by all full nodes in the blockchain network .
Due to the existence of various DApps on Ethereum, The Tragedy of (Storage) Commons is relatively more serious. For example, at the time of block 5700001 (May 30, 2018), the 5 most used contracts are:
EtherDelta, 5.09%
IDEX, 4.17%
CryptoKitties, 3.05%
ENS, 1.92%
EOS Sale, 1.73%
More interesting is the last one, EOS Sale. Although the EOS crowdfunding has been completed and the EOS tokens have been circulated on the EOS chain, the records of the EOS crowdfunding remain on the Ethereum nodes forever, consuming the storage resources of the entire Ethereum node.
state explosion
state explosion
You might say, is it possible that the improvement of the average level of hardware will exceed the accumulation speed of history and status? My answer is very unlikely:
You might say, is it possible that the improvement of the average level of hardware will exceed the accumulation speed of history and status? My answer is very unlikely:
From this graph we can see that as the Ethereum network develops, the amount of state data accumulated increases exponentially. It took 10 years for the status data of Bitcoin to accumulate from 0 to 3G; it took 4 years for the status data of Ethereum to accumulate from 0 to 10G; and this is before we have solved the scalability problem, and the blockchain is still a niche technology case growth rate.
When we solve the scalability problem, the blockchain really gets mass adoption, and the number of DApps and users explodes, at what speed will blockchain history and status data accumulate?
This is the state explosion problem, which we classify as a post-scalability problem, because it will be very obvious after solving the scalability problem. We first noticed this problem when we were working on the licensed chain scenario, because the performance of the licensed chain is much higher than that of the public chain, and it is just in the post-scalability stage.
The accumulation of historical data is relatively easy to handle. In the future, it can be compressed by technologies such as decentralized Checkpoint or zero-knowledge proof. Before that, the full node can even discard the history directly and still operate normally. The accumulation of state data is much troublesome, because it is necessary data for full node operation.
Many blockchain projects have seen this problem and proposed some solutions. EOS RAM is a useful attempt to solve the problem of state explosion: RAM represents the memory resources available to the super node server, whether it is account, contract state or code, it needs to occupy a certain amount of RAM to run.
The design of RAM also has many problems. It needs to be purchased through the built-in trading market. It is non-transferable and cannot be rented. It mixes the short-term memory requirements during contract execution and the long-term storage requirements of the contract state, and the total amount of RAM is set. There are no definite rules, and it depends more on the hardware configuration that supernodes can afford than the cost of consensus space.
The Ethereum community has also seen this problem and proposed a Storage Rent solution: users are required to pay a rent in advance for the use of storage resources. Occupying storage resources will continue to consume this rent. The longer the occupation time, the rent that users need to pay more. There are two problems with the Storage Rent solution:
1. The prepaid rent will be used up one day, how to deal with the status of occupancy at this time? To solve this problem, Storage Rent needs mechanisms such as recovery, which increases the complexity of the design, greatly reduces the immutability of smart contracts, and brings trouble to the user experience;
2. Ethereum's state model is a shared state model, not a First-class State. Taking ERC20Token as an example, all user asset records are stored in the storage of a single ERC20 contract. In this case, who should pay the rent?
Solving the problem of state explosion is also one of the design goals of Nervos CKB, so we have taken a completely different and more radical change path. In short, in Nervos CKB, a token represents a unit of storage space. Through the design of the economic model, we limit the size of the world state, use market means to adjust the supply and demand of state storage, and continue to provide users who occupy the state through the design of additional issuance. Fees are used to coordinate the interests of all parties in the ecology to achieve long-term security and lasting stability.
