Blockchain state explosion dilemma | hard core series

The development of the blockchain has been nearly 10 years old. With the blossoming of the public chain and the emergence of more and more cutting-edge technical solutions, we are facing an increasingly complicated and chaotic industry situation.

In order to explore more important and hard-core technical and ideological problems, the Chain Catcher (ID: iqklbs) will invite entrepreneurs, scholars, and technical tycoons with considerable achievements in a series of fields such as public chains and exchanges to share. They have undergone a lot of practical industry judgments and reflections in their professional fields to help readers further deepen their understanding of the blockchain.

The Chain Catcher (ID: iqklbs) was reprinted from the Talk Forum, and Nervos Chief Architect Jan wrote this article. His Nervos Network is a Layer 1 underlying public chain for Layer 2, dedicated to building the foundation for future encryption economies. facility. I believe that Jan's wonderful sharing should bring you inspiration.

01 Layer 1 should pay attention to the status

If we believe that blockchain stratification is the future direction of development, we should consider the requirements of upper-layer protocols and tiered networks from the very beginning, and design blockchain protocols in the tiered framework.

In other words, from a layered perspective, existing blockchain designs are outdated. Existing blockchains are designed with specific features in mind (such as paying, or running a DApp), and hope to allow the upper layer protocol to adapt to itself after a period of operation. However, if we read the history of the Internet, we know that the Internet tiering of the Internet is not patched in this way. Instead, it is 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, first figure out the difference between it and the upper layer protocol. The origin of Layer 2 and the discovery of the public chain (here referred to as the permissionless blockchain) are insufficient, and it is difficult to expand to meet the needs of the entire encryption economy. At the same time, we are very obsessed with the availability and great service range provided by the public chain, so it is slow. Slowly evolved a series of Layer 2 protocols that can be secured by blockchains, such as payment channels, plasma, etc.

A common feature of these protocols is the sacrifice of consensus to trade for performance. The most amazing thing about the public chain is the uninterrupted global coverage of services through open networks, which means global consensus and performance.

The best way to solve this problem is to transfer most of the transactions to the upper-layer protocol with a smaller consensus but better performance, and ensure that the participants of the upper-level protocol can always return to the blockchain when they are not satisfied to solve the problem. The price is only some time cost.

Therefore, as the blockchain of Layer 1, the focus should obviously not be performance, because Layer 2 will assume this responsibility. Layer 1 is the last line of defense for upper-level agreement participants. Its focus should be on security and decentralization. If we look at the pattern in which the Layer 2 protocol interacts with Layer 1, we will also find that Layer 1 is responsible for state consensus (storage) and Layer 2 is responsible for state generation (calculation).

02 What is the state?

If the focus of Layer 1 should be state rather than computation, when designing the Layer 1 blockchain, we need to understand what the state of the blockchain is. Understand what the state is, and we can understand what the state explosion is.

Every node in the blockchain network will leave some data on the local storage after running for a while in the network. We can divide them into two categories according to history and now:

History: Block data and transaction data are historical, and history is the path from Genesis to the current state.

Status (ie now): The final result of the node after processing all the blocks and transactions from Genesis to the current height. The state has been changing with the increase of the block, 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, all transactions are sorted the same), the transactions are processed in the same way (putting the transactions in the same deterministic virtual machine), and the current state of the transaction is the same. When we say that "blockchains are inextricably modified," it means that the history of blockchains cannot be tampered with, and the opposite state is constantly changing.

Interestingly, different blockchains have different ways of preserving history and state, and the differences make different blockchains form their own characteristics. Since the topic discussed in this article is state, and the historical data affecting the state is mainly the transaction (rather than the block header), the discussion of the history will focus on the transaction and ignore the block header.

03 For example: History and status of Bitcoin

The status of Bitcoin refers to the current appearance of the Bitcoin ledger. The state of Bitcoin consists of one UTXO (unused transaction output). Each UTXO represents a certain number of Bitcoins. Each UTXO has a name (scriptPubkey) written to record who the owner of the UTXO is. If you want to make a metaphor, Bitcoin's current state is a bag full of gold coins, each with the owner's name engraved.

Bitcoin's history consists of a series of transactions, the main structure inside the transaction is the input and output. The way to change the status of a transaction is to mark some UTXOs (those referenced by the transaction input) contained in the current state as spent, remove them from the UTXO collection, and then add some new UTXO (the output of this transaction) to the UTXO collection. go with.

It can be seen that the output of Bitcoin transaction (TXO, Transaction Output) is exactly the UTXO mentioned above. UTXO is just a TXO at a special stage (not yet spent). Because the components that make up the Bitcoin state (UTXO) are also the components that make up the transaction (TXO).

Thus, Bitcoin has a wonderful property: the state at any moment is a subset of history, and the data types contained in history and state are of the same dimension. The history of the transaction (the set of all packaged transactions, ie the set of all generated TXOs) is the history of the state (the set of UTXO collections for each block, also the collection of all generated TXOs), the history of Bitcoin Only include transactions.

In the Bitcoin network, each UTXO continues to occupy the node's storage space for each block. At present, the entire history of Bitcoin (the size of all blocks combined) is about 200G, and the state is only about 3G (consisting of about 50 million UTXO). Bitcoin manages the historical growth rate by limiting the block size. Due to the subset relationship between its history and state, the state data size is inevitably much smaller than the historical data size. Therefore, the state growth is also indirectly affected by the block size. Management.

04 Another example: the history and state of Ethereum

The state of Ethereum, also known as "world state," refers to the current state of Ethereum's books. Ethereum's status is a Merkle tree (the account is a leaf) made up of accounts. The account not only records the balance (representing a certain number of ethers), but also the contract data (such as the data of each encrypted cat). The state of Ethereum can be seen as a large book, the first column of the book 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 number of ethers carried in the transaction

Data: any information carried in the transaction

The way to change the status of the transaction is that the EVM finds the target account sent by the transaction.

1. Calculate the new balance of the target account based on 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 to generate a new state during operation;

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 from that of Bitcoin. The state of Ethereum is composed of accounts, and the transaction is composed of information that triggers account changes. The status and transactions record completely different types of data. There is no superset and subset relationship between them. History and state include The data type is two dimensions, and there is no necessary relationship between the transaction history size and the state size.

After the transaction is modified, not only will the new state be generated (the leaves of the solid frame in the figure), but the old state (the leaves of the dotted frame in the figure) will be left in the historical state, so the history of Ethereum not only contains transactions, but also Contains historical status.

Because history and state belong to different dimensions, the Ethereum block header contains not only the merkle root of the transaction, but also the merkle root that explicitly contains the state.

In every block of Ethereum, each account will continue to occupy the storage space of the node. The Ethereum node has multiple modes when synchronizing. All the history and state in the Archive mode are saved. The history includes historical transactions and historical status. All the data adds up to more than 2TB. In the Default mode, the historical status will be It is cropped, the local only retains the historical transaction and the current state. All the data adds up to about 170G, in which the transaction history size is 150G, and the current state size is 10G.

All the 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 takes into account the computational 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 misconception is that Ethereum's "blockchain size" has exceeded 1T. From the above analysis, we can see that the "blockchain size" is a very vague definition. If the historical state is counted, it is indeed exceeded, but for the whole node, there is no problem in deleting the historical state because As long as there is Genesis and trading history, the historical state at any time can be recalculated (regardless of the time required for the calculation).

The really meaningful data is the size of the data required for the whole node. Bitcoin is 200G, and Ethereum is 170G. The two are basically the same, and the average configuration of the cloud host can be installed, so the Ethereum full node is observed. The reduction is not due to increased storage (the root cause is the computational overhead at the time of synchronization).

Considering the historical length of Ethereum (the timestamp of the current block minus the timestamp of genesis) is less than half of Bitcoin, it can be seen that Ethereum's history and state size grow faster.

05 The Tragedy of (Storage) Commons: Blockchain version of the tragedy of the commons

The tragedy of the commons refers to a situation in which limited shared resources are over-consumed by people without any restrictions. It is such a shared resource that blockchain nodes pay for storing history and state.

There are three types of resources that blockchain nodes spend on processing transactions, CPU, storage, and network bandwidth. CPU and bandwidth are resources that each block will refresh. We can think that the same CPU and bandwidth are available in each block interval. The CPU and bandwidth consumed by the previous block will not let the next one. The available CPU and bandwidth of the block is reduced. For refreshable resources, we can compensate the node with a one-time transaction fee (for the correlation between handling fee and calculation complexity and transaction size, please refer to RFC0015Appendix).

Unlike CPU and bandwidth, storage is a resource that is occupied in a block. Unless the user actively releases it, it cannot be used by other users in subsequent blocks. The node needs to pay for the storage continuously, but the user does not need to pay a continuous processing fee for the storage (remember that the transaction fee only needs to be paid once).

Users only need to pay a small fee when writing data to the blockchain, and they can permanently use a storage with more than Amazon S3. The infinite permanent storage cost requires all the nodes in the blockchain network to bear. .

The Tragedy of (Storage) Commons is relatively more serious on Ethereum due to the existence of various DApps. For example, in block 5700001 (May 30, 2018), the five contracts with the most usage status are:

  1. EtherDelta, 5.09%
  2. IDEX, 4.17%
  3. CryptoKitties, 3.05%
  4. ENS, 1.92%
  5. EOS Sale, 1.73%

More interesting is the last one, EOS Sale. Although EOS crowdfunding has been completed, EOS tokens have been streamed over the EOS chain, and EOS crowdfunding records have remained on Ethereum's nodes forever, consuming Ethereum's full-node storage resources.

It can be seen that in the absence of management, the storage resources of the blockchain will be abused intentionally or unintentionally. In a well-designed economic model, the user must bear the cost of storage, which is not only proportional to the size of the occupied storage space, but also proportional to the length of the occupied time.

06 state explosion

Both historical and state data refer to storage resources in the tragedy of the commons. Through the above analysis of Bitcoin and Ethereum (the state models of other blockchains can basically be summarized as one of them), although they manage the growth of history and state, the total of history and state There is no control over the size, and the data will continue to accumulate incessantly, making the storage resources needed to run the whole node larger and larger, increasing the operating threshold of the whole node, and making the decentralization of the network lower and lower. We don't want to see it.

You might say, is it possible that the average hardware level will increase beyond the history and state of accumulation? My answer is that the probability is very low:

From this picture we can see that with the development of the Ethereum network, the amount of state data accumulation has grown exponentially. Bitcoin's state data has accumulated from 0 to 3G for 10 years; Ethereum's state data has accumulated from 0 to 10G for 4 years; and this is where we have not solved the Scalability problem, the blockchain is still niche technology. The growth rate in the case.

When we solve the scalability problem, when the blockchain really gets mass adoption, and the number of DApps and users are exploding, what speed will the blockchain history and state data accumulate?

This is the state explosion problem, we classify it as a post-scalability problem, because it will be very obvious after solving the scalability problem. We first noticed this problem when doing the licensing chain scenario, because the performance of the license chain is much higher than the public chain, just in the post-scalability phase.

The accumulation of historical data is relatively easy to handle. In the future, it can be compressed by decentralized Checkpoint or zero-knowledge proof. Until then, the whole node can even directly drop the history and still run normally. The accumulation of state data is a lot more troublesome because it is the data necessary to run the entire node.

Many blockchain projects have seen this problem and proposed some solutions. EOS RAM is a useful attempt to solve the state explosion problem: RAM represents the memory resources available to the SuperNode server, whether it is account, contract status or code, it takes a certain amount of RAM to run.

The design of RAM also has a lot of problems. It needs to be purchased through the built-in trading market, it is not transferable, it cannot be rented, and the short-term memory demand in the contract execution process and the long-term storage requirement of the contract state are mixed together, and the total amount of RAM is set. There are no definite rules, more depending on the hardware configuration that the supernode can withstand, not the cost of the consensus space .

The Ethereum community also saw this problem and proposed Storage Rent's solution: requiring users to prepay a rent for the use of storage resources, which will continue to consume the rent. The longer it takes, the rent the user needs to pay. more. There are two problems with the Storage Rent solution:

1. The prepaid rent will be used up one day. How do you handle the occupied status at this time? To solve this problem, Storage Rent needs a mechanism such as resurrection to supplement, increasing the complexity of the design, greatly reducing the immutability of the smart contract, and causing trouble for the experience;

2. Ethereum's state model is a shared state model, not a First-class State. Taking ERC20Token as an example, all user's asset records are stored in the storage of a single ERC20 contract. In this case, who should pay the rent?

Solving the state explosion problem is also one of the design goals of Nervos CKB, for which we have taken a completely different and more thorough path of change. In short, we have a token in the Nervos CKB representing a unit of storage space, through the design of the economic model, limiting the size of the world state, using market means to adjust the supply and demand of state storage, and continuing to the occupied state through the design of the additional issuance. Charges to coordinate the interests of all parties in the ecology to achieve long-term security and lasting stability.

(To be continued)

 

Author: Jan

Source: Chain Catcher

Unauthorized, declined to reprint