"Ethereum 2.0 Fragmentation Design" that everyone can understand
Editor's Note: This article comes fromCarbon chain value (ID: cc-value)Editor's Note: This article comes from
Carbon chain value (ID: cc-value)
Carbon chain value (ID: cc-value)
When we buy breakfast at 7-11, if there is only one cashier, we have to wait in a long line for the checkout; if there are two cashiers, it will be doubled immediately; if there are four cashiers, maybe There is no need to queue. This is the basic logic of sharding, which distributes the work of one person to multiple people to improve efficiency.
From the point of view of the distributed ledger of Ethereum: before sharding, there is only the ledger of the main chain, which can process about 12 to 45 transactions per second. When the transaction volume is greater than this data, it needs to queue up, that is, the network will be congested; Sharding is to turn one ledger into 64 ledgers and let them process transactions at the same time, which is equivalent to opening 64 cash registers at 7-11 to collect cash.
The logic of sharding is simple, but why is it so difficult to implement? Because dividing a ledger into 64 ledgers will face many new problems, what sharding technology needs to do is to solve them. This article will start from these questions to find out what the sharding of Ethereum 2.0 is all about.
secondary title
How to fragment
1. Assign transactions to shards
A shard contains transactions and validators who package transactions into blocks. The first step in completing a shard is to determine how to assign transactions and validators to a shard. Let's look at allocation transactions first.
Let us use the story of three villages to understand: there is a fishing village, a hunter village, and a farmer village. There are often transactions within and between villages, but there is no currency, and everyone keeps accounts. In the past, one account book was used to keep the accounts of the three villages, which was a bit slow, but now it is changed to three account books, so which account book is used to keep which accounts?
One method is to put three ledgers there, and after a transaction comes, it will be recorded in which ledger if there is no queue in front of it; but this will bring about a problem that each ledger must have an owner account information, otherwise I will come to you to queue up, and you do not have my account.
Because of this, one of the main problems of this sharding method is that it cannot reduce the amount of data stored on a single ledger, and this storage requirement is a high threshold for nodes that want to participate in bookkeeping; this method also needs to solve the double spending problem, Because one person can spend the same money in different shards at the same time.
Another method is that fishing villages have one ledger, Orion villages have one ledger, and farmer villages have one ledger. The ledgers only contain the account information of their own villages, and only record transactions within their own villages. In this way, the three ledgers can be kept at the same time, with high bookkeeping efficiency and less storage requirements. This is exactly the sharding method adopted by Ethereum: state sharding, each shard stores and only stores the account status belonging to its own shard. In terms of implementation, users of Ethereum choose which shard to join, rather than sharding by natural village.
The biggest problem with state sharding is, what if the people in the fishing village want to trade with the people in the Orion village? There are no accounts of Orion villagers in the ledger of the fishing village, and there are no accounts of fishermen in the ledger of Orion Village. In fact, this is the biggest test facing sharding technology, cross-shard communication. When this problem is completely solved, Ethereum 2.0 can be used. This article discusses some solutions to this problem in Part II.
2. Assign validators to shards
After arranging transactions to different shards, the next problem to be solved is how to assign bookkeepers to a shard, that is, assign verifiers.
There are 64 shards in Ethereum, and each shard has 128 verifiers. If the verifiers of the shards are fixed or predictable, the attacker controls the shards, that is, buying 2/3 of the 128 is one What is an easy thing to do? Ethereum's solution is to randomly select a validator for a shard from all validators, and change the validator every 6.4 minutes (the length of one epoch). In this way, the attacker has less than a one-in-a-trillion chance of controlling 2/3 of the people in a shard (see Reference 1 for reasoning).
One of the main tasks of the beacon chain is to assign verifiers to the shard chains, and the most important thing in this work is the realization of randomness. The first is the importance of randomness. If verifiers cannot be randomly assigned, the security of the ledger cannot be guaranteed; the second is the difficulty of randomness. It is extremely difficult to achieve randomness on the blockchain. It can be considered that so far There is no proven random algorithm that can really be called an engineering implementation.
Ethereum's solution is to use RANDAO+VDF to provide random numbers to achieve randomness. It is easy to understand by dismantling RANDAO into RAN (random) and DAO. It means that each person in a group proposes a random number independently, and then combines the random numbers of all people to generate the last random number used. . Because it is difficult for anyone to know the numbers provided by others, it is also difficult to predict the final numbers that will be combined.
However, there is a flaw in the RANDAO model, that is, the person who provided the last number has the opportunity to cheat: he knows the sum of the random numbers provided by all the previous people, and can adjust the number provided by himself to make the final result beneficial to himself.
To solve this problem, Ethereum introduced VDF (Verifiable Delay Function), its function is very simple, it is to prevent the last person who provided the random number from calculating the sum of the random numbers of all previous people before providing the number himself, so There is no way to manipulate random numbers. (For a detailed introduction of RANDAO+VDF, see Reference 2)
3. Shards are stored by relayers
I don’t know if you have noticed that the verifier of the rotating ledger will bring a new problem: the verifier will be assigned to the fishing village to keep accounts for a while, and will be assigned to the Orion Village for a while. If he does not have all the account information in hand, how to keep accounts? account? If he has all the account information, he is holding a full ledger again, without state sharding.
To solve this problem, Ethereum proposed an important new design: stateless client. Simplified understanding is that the ledger of the fishing village is placed in the fishing village, and the ledger of the Orion Village is placed in the Orion Village. The verifier does not hold the ledger, but is only responsible for running around between different villages to keep accounts.
So who will keep the ledgers of the different villages? Ethereum introduced the role of relayers (status providers), who are responsible for storing the account status of different shards, and can only serve a certain shard. The work of relayers is easy to understand, but how to pay for their services, how to ensure their honesty... The design of these related mechanisms is a new problem that needs to be solved, and it is also a governance problem that community members should participate in the discussion.
But we cannot require each user to store all the old accounts so that the transaction can be proved after the transaction is initiated. At this time, a "relay" is needed, which stores all the account status of the shard. As long as the user raises a demand, it will It can help users provide witness data of transactions to verifiers.
Vitalik Buterin published an article on March 11 proposing to replace the state root with a polynomial commitment. This technology is used here. It uses a zero-knowledge proof method to provide proof for the transaction, which can be understood as providing the calculation result of the data. Instead of directly providing all relevant data to the verifier for verification, this method can greatly reduce the size of the witness data and effectively reduce various overheads. (For a detailed introduction of Vitalik's new method, see Reference 3, and for a detailed introduction of the stateless client, see Reference 4)
At this point, the work of dividing a ledger into multiple ledgers, that is, dividing into shards, is completed.
secondary title
Transactions across shards
If the people in the fishing village only trade with the people in the fishing village, and the people in the Orion village only trade with the people in the Orion village, then each village can keep its own accounts. This does not require any new technology. But what if the people in the fishing village want to trade with the people in the Orion village? How can different ledgers communicate with each other? This is the thorniest problem facing state sharding.
There are two ways to solve this problem, one is synchronous (tightly coupled), and the other is asynchronous (loosely coupled).
Suppose there is a person named A in the fishing village, and a person named B in the Orion village. A wants to give B 100 yuan. Synchronization means: when A initiates the transfer, the bookkeepers in the fishing village and Orion village know the transaction and the progress of the transaction. The accountant subtracts 100 from A on the ledger, and the bookkeeper of Orion Village adds 100 to B on the ledger. After the transaction is completed, the two villages generate new blocks simultaneously.
Asynchronous means: when A initiates the transfer, the account book of the fishing village reduces A by 100, and a new block is generated; the bookkeeper of Orion Village receives this message in some way later, and after confirming that A’s money has indeed been reduced, he will Add 100 to B on his own account book, and the transaction is completed, but the two villages generate new blocks asynchronously.
The synchronization method looks friendly, and the look and feel of the transaction execution process is the same as that of non-sharding, but it hides a big problem, that is, it is difficult to deal with "continuous state changes". What does it mean?
If A only transfers 100 yuan to B, after hearing the transaction, the fishing village and Orion Village can easily confirm that everyone keeps accounts in this way. The account book of the fishing village will be reduced by 100 for A, and Orion Village will add 100 to B. Complete bookkeeping. However, if A transfers 100 to B, and then transfers to B 50, continuous state changes occur, but A has only 120 in total. At this time, it is difficult for the two villages to confirm how the other party keeps accounts:
If each validator goes to communicate with the other’s validator by himself, the communication overhead will increase sharply, and it will be extremely difficult to achieve a certain result; if the communication is through the village chiefs of both sides, each village needs to conduct a round of consensus in advance, and then The village chief tells the other party a definite result. In addition to increasing the cost, it is also difficult to achieve, because the consensus mechanism of Ethereum itself cannot achieve a definite result (finality).
The asynchronous method will not be troubled by continuous state changes, because its approach is to "wait". When your state is confirmed, I will proceed to the next step; After subtracting 100 or 50, decide to add 100 or 50 to B.
The problem with the asynchronous approach is atomic failure. The transaction should be atomic, either executed or not executed, but in an asynchronous manner, it is possible that part of the transaction is confirmed, but the other part is discarded.
For example, the block in which the fishing village subtracted 100 from A was finally confirmed on the main chain of the fishing village, but the block in which Orion Village added 100 to B was finally abandoned on the side chain of Orion Village. Atomic failure is a problem, but it can be solved by design. For a detailed introduction to this part, see reference 5 at the end of the article.
Ethereum has discussed some asynchronous architecture models. The latest one was proposed by Vitalik at the DevCon 5 conference in October 2019. The basic idea is to use the beacon chain to transmit information: in each slot (12 seconds), minutes The slice chain generates blocks and cross-links with the beacon chain blocks. The connection method is as shown in the figure below. In this way, any fragment can know the information of all other fragments through the beacon chain when packaging its own new transaction. A slot is asynchronous between different shards.
This method reduces the latency of cross-shard transactions, but increases the requirements on the beacon chain, which needs to store proof data for all shards; this method also increases the number of cross-linked links (originally designed as Each epoch, that is, 6.4 minutes, 32 blocks crosslink once), which will inevitably increase various related overheads, and because of this, the number of fragments in Ethereum has been changed from 1024 to 64, from another design direction Reduce the total number of links. (See Reference 6 for a detailed introduction to the architecture)
Judging from some current sharding design schemes, the synchronous model is more inclined to communicate between shards and shards themselves, while the asynchronous model is more inclined to communicate between shards and shards through a third party; the former faces traffic constraints problem, the latter faces a balancing problem of multiple overheads. The design and implementation of cross-shard transactions is still in progress, and it is uncertain which architecture Ethereum 2.0 will eventually adopt.
secondary title
Smart contracts across shards
After introducing sharding and cross-shard transactions, the ultimate big boss on the road to Ethereum 2.0 development comes, which is the cross-shard smart contract. The difference between cross-shard transactions and cross-shard smart contracts is that transactions only have global variables, while smart contracts have local variables. What trouble do local variables cause?
After sharding, Ethereum has 64 ledgers from a physical point of view, but only one ledger from an abstract point of view: the ledger can be imagined as a big tree, each leaf of the tree stores an account status data, 64 The ledger is 64 trees, and then the roots of these trees are given to the beacon chain to form a new big tree, and 64 ledgers are combined into a ledger (this is just an approximate metaphor).
In cross-shard transactions, when a shard needs to know the account status of another shard, it can always follow the tree to find the leaf that stores the state, and then change its own shard account status and complete the transaction. It can be considered that through this tree, different shards complete the communication of information.
But for smart contracts across shards, the problem arises. The data stored on the leaves of this tree are all global variables, and there are no local variables. If a smart contract in one shard calls a smart contract in another shard, what happens to the two Pass information to local variables? The tree cannot serve them.
At present, there is no systematic smart contract cross-shard design scheme, but there are two proposals, one is to put the associated smart contracts into the same shard for execution, that is, to eliminate the smart contract cross-shard One is to propose the use of SIMD (Single Instruction Stream Multiple Data Stream) technology, so that the smart contract itself can be executed in parallel.
References:
1.《 Minimum Committee Size Explained》Ethereum 2.0 will introduce smart contracts in Phase 2, which means that the cross-sharding of smart contracts will not be realized until Phase 2, and only after this step can truly declare that Ethereum has entered the 2.0 era.
3.《Using polynomial commitments to replace state roots》; Author, Chih-Cheng Liang;
4."Ethereum 2.0: Randomness"; Author, Bruno Škvorc; Translator, Jhonny, A Jian;
5.; Author, Vitalik Buterin;"Eth2.0 Relay Network and Fee Mechanism"
6.《Eth2 shard chain simplification proposal》; Author, John Adler; Translator, IAN LIU, A Jian;
7."The Concept and Challenges of Blockchain Fragmentation"; Author, Alexander Skidanov; Translator, Jhonny, Echo, A Jian;
8.《Merge blocks and synchronous cross-shard state execution》; Author, Vitalik Buterin;
