Original Author: Beam
Disclaimer: This article is only used as an industry research discussion and does not represent any investment advice.
On September 15, 2022, Ethereum merged (Merge). This is a historic moment. Ethereum has prepared for it for 5 years and postponed it 6 times. Due to repeated debugging and long-term development, and the highly anticipated halo effect, many people mistakenly believe that the merger will naturally bring higher Scalability, security, and sustainability are not actually—we still use the metaphor of two trains, the transition from PoW (proof of work) to PoS (proof of equity) just replaces the tracks and wheels, it It will not directly bring faster speed, larger capacity, and lower ticket fees. What can really accomplish the above three points is a complete set of solutions: the main network with sharding capabilities and Layer 2 with enhanced scalability solution.
image description
Figure 1 Simple logic of sharding
first level title
1. About "sharding"
To put it simply, considering the constraints of the Impossible Triangle, starting from Ethereum as the origin of the coordinate system (0,0), according to the two ideas of "vertical" and "horizontal", we divide the current blockchain scalability methods into Two categories:
Vertical Scaling: It is realized by improving the performance of the existing hardware of the system. Building a decentralized network where every node in the network has supercomputing power, i.e. every node needs "better" hardware - this is a simple and effective way to achieve initial improvements in throughput, especially for It is suitable for high-frequency trading, games and other application scenarios that are sensitive to delay. However, this expansion method will limit the level of decentralization of the network, because the cost of running a verification node or a full node becomes higher. Maintaining a level of decentralization is limited by the approximate growth rate of computing hardware performance (this is the so-called "Moore's Law": the number of transistors on a chip will double every two years, and the cost of computing will be halved).
Horizontal Scaling: There are generally several ideas for horizontal expansion. One is to disperse the transaction calculation amount in a certain ecology to multiple independent blockchains in the context of blockchain, and each chain has its own block producers and execution capabilities. The execution layer of each chain can be fully customized, such as node hardware requirements, privacy features, gas fees, virtual machines, and permission settings. Another horizontal expansion solution is a modular blockchain, which divides the blockchain infrastructure into an execution layer, a data availability layer (DA) and a consensus layer. The most mainstream blockchain modularization mechanism is rollup. Another is to divide a blockchain into many pieces and execute them in parallel. Each shard can be regarded as a blockchain, which means that many blockchains can be executed in parallel. Additionally, there is usually a main chain whose only job is to keep all the shards in sync.
It should be pointed out that none of the above expansion ideas exist in isolation. Each solution is to find a trade-off point in the impossible triangle, cooperate with the design of the incentive mechanism created by the economic forces in the system, and achieve effective macro and micro levels. balance.
In order to discuss "sharding", we need to start from scratch.
Still assuming such a scenario, Walmart shopping checkout, in order to improve checkout efficiency and reduce customer waiting time, we expanded from a single checkout channel to 10 checkout windows. In order to avoid account errors, we need to formulate unified rules at this time:
First, if we have 10 cashiers, how do we assign them which window to work?
Second, if we have 1000 customers waiting in line, how do we decide which window each customer goes to check out?
Third, how to summarize the 10 separate ledgers corresponding to these 10 windows?
Fourth, how do you prevent cashiers from making mistakes in order to avoid account mismatches?
These questions actually correspond to several key questions in sharding, namely:
How to determine which shard the nodes/validators of the entire network belong to? That is: how to perform network sharding (NetworkSharding);
How to determine which shard each transaction is assigned to? That is: how to perform transaction sharding (Transaction Sharding);
How are blockchain data stored in different shards? That is: how to perform state sharding (State Sharding);
secondary title
01 Network Sharding
If we simply understand the blockchain as a decentralized ledger, whether it is a PoS or PoW consensus mechanism, it is to allow each node to compete for the right to bookkeeping according to certain established rules, and to ensure the correctness of the ledger in the process. And network sharding means that another established rule is needed to shard the blockchain network. Under the premise of minimizing mutual communication, each shard handles transactions on the chain and competes for the right to bookkeeping—that is, the node’s grouping rules.
The problem encountered in this process is that as the internal nodes of the blockchain are divided into different pieces, the difficulty and cost of the attacker will plummet. We can reason, assuming that the rules and results of this grouping process are fixed and predictable, then an attacker who wants to control the entire blockchain network only needs to control one of the shards in a targeted manner and buy some nodes in the shard. .
image description
Figure 2 The difficulty of attacking a shard is greatly reduced
image description
Figure 3 Validator rotation as envisioned in Ethereum 2.0
To put it simply, the nodes are randomly grouped, and then the work is assigned to each group of nodes for independent verification.
secondary title
02 Transaction Sharding
Transaction sharding refers to the formulation of rules about "which transactions should be assigned to which shards", which can not only achieve the purpose of parallel processing but also avoid the occurrence of double spending problems. The difference in the ledger model of the blockchain will affect the development of transaction sharding.
At present, there are two types of bookkeeping methods in the blockchain network, namely the UTXO (Unspent Transaction Outputs, unused transaction output) model and the account/balance model. The typical representative of the former is BTC, and the latter is like ETH.
image description
Figure 4 A possible transaction sharding idea for UTXO
To ensure that entries are placed in the correct shard in a consistent manner, the values fed into the hash function should all come from the same column. This column is called the Shard Key. Afterwards, all transactions with a value of 1 are divided into shard 1, and transactions with a value of 2 are divided into shard 2. The disadvantage of this method is that the shards have to communicate to avoid double-spending attacks. Restricting cross-shard transactions will limit the usability of the platform, while allowing cross-shard transactions will have to weigh the cost of cross-shard communication and the benefits of performance improvements.
secondary title
03 State Sharding (State Sharding)
State sharding refers to how blockchain data is distributed and stored in different shards.
Still using our Walmart queuing example, each window has an account, how are their accounts recorded? If: Whichever queue the customer comes to, the account will be recorded. For example, if customer A goes to window A, then the customer goes to another checkout window such as window B the next day, and window B does not have the customer's past account information (such as It involves payment methods such as stored value cards), what should I do? Call the customer's account information to window A?
State sharding is the biggest problem of sharding, which is more difficult than the above-mentioned network sharding and transaction sharding. Because under the sharding mechanism, the transaction will be processed in different shards according to the address allocation, that is to say, the state will only be stored in the shard where the address is located. One problem to be faced at this time is that the transaction will not only be in In a shard, it often involves cross-sharding (Cross-Sharding).
Consider a transfer situation, account A transfers 10U to account B, and A's address is allocated in shard 1, and the transaction records will also be stored in shard 1. B's address is allocated in shard 2, and the transaction records will be stored in shard 2.
Once A wants to transfer money to B, a cross-shard transaction will be formed, and shard 2 will call the past transaction records to shard 1 to confirm the validity of the transaction. If A sends coins to B frequently, shard 2 will It must constantly interact with shard 1, and the processing efficiency of transactions will be reduced. However, without downloading and verifying the entire history of a particular shard, participants cannot necessarily be sure that the state of their interactions among them is the result of some valid sequence of blocks, and that such sequence of blocks is indeed the canonical chain in the shard.
Therefore, compared to a single chain without sharding, a new challenge for a sharded system is that users cannot directly and fully verify the validity and availability of any given chain because there is too much data. There must be a maximum trustless and practical indirect way for users to verify which chain is fully available and valid so that they can determine which chain is the canonical chain. In practice, blockchain developers can use techniques such as committees, SNARKs/STARKs, fisherman mechanisms, and proofs of fraud and data availability to solve some of the problems in verification.
There are two ways to solve this problem. One is synchronous cross-sharding (Synchronous), that is, tight coupling (Tight Coupling). Whenever a cross-shard transaction needs to be executed, related blocks containing state transitions occur at the same time, and each shard On-chip nodes collaborate to execute transactions. Natural to look at and best to use, the model's most famous design is called Merge Blocks, but achieving this in practice is complicated. To accomplish the above, validators between shards need to communicate with each other synchronously. If the demand for cross-shard transactions is high enough, performance may degrade as more shard workers have to collaborate together to process cross-shard transactions.
Another way is asynchronous cross-sharding (Asynchronous), that is, loosely coupled (Loosely Coupling). This idea is more widely adopted, such as NEAR, Ethereum, Cosmos, Kadena, etc. In this process, the most challenging thing is the atomicity of the transaction. According to Jordan Clifford, co-founder of Scalar Capital, if we imagine the concept of a receipt (Receipt), the receiver proves that they will receive the Token from the external shard by providing the Merkle path of the transaction in the source shard. The destination shard consumes the receipt and credits it to the recipient's account. This must be done atomically. The sender's and recipient's accounts are either modified together or not. If there is a gap or one end fails, the sender can trick the recipient into believing they have received funds that they never will.
first level title
2. Exploration and attempt of sharding
Let's review some of the key issues mentioned above in the discussion about sharding:
One is how to perform state sharding, that is, how blockchain data is allocated and stored in different shards, and how to ensure the balance of benefits when cross-shard communication is required.
The second is how to deal with the atomicity of transactions. One shard needs to let the other shard know about the modification of the common access state in a timely manner, otherwise state disorder will easily occur.
secondary title
01 Calculation sharding
Zilliqa is one of the earliest smart contract platforms to try sharding, and it is a very beneficial and effective attempt of sharding technology.
Founded in 2017, it is driven by a team of dedicated researchers and academics associated with the National University of Singapore. Its main goal is to solve the scalability problem and it is purpose-built for computationally intensive tasks. The Zilliqa network is able to process high-throughput transactions across its network through a parallelization process called computational sharding. On a sharded blockchain network, the task of computing transactions is distributed across the shards of the network.
From the sharding process, Zilliqa divides it into two parts. First, directory service (DS) committee nodes are selected, then the sharding process is started and nodes are assigned to each shard. Once a transaction is verified in a shard, it can be verified by the entire network into a global state that combines transactions from all shards into a single verifiable source of truth on the Zilliqa blockchain.
In simple terms, there are three main functions for nodes in the blockchain:
- Process transactions
- Package the transaction and broadcast to other nodes
- Store the historical ledger of the entire network
secondary title
02 Static state sharding
A more general approach to sharding is to divide an account's address space into multiple fixed-size regions called shards, and assign nodes in the network to different shards. This is called state sharding. Platforms such as Near, Elrond, and Harmony are taking this approach. While ethereum initially planned to implement state sharding, the new approach only shards the data to increase accessibility.
2.1 Data fragmentation idea of Ethereum
In the context of Ethereum, sharding will work in tandem with Layer 2 by offloading the burden of processing the large amounts of data needed to aggregate across the network. This will continue to reduce network congestion and increase transactions per second.
It should be noted that Ethereum's sharding plans are constantly evolving as more efficient scaling paths are developed. One of Ethereum's plans for future sharding is based on "data availability" sharding. "Danksharding" is a new sharding method that does not use the concept of sharding "Chain". Blob" to split the data while using "Data Availability Sampling" to confirm that all data is available.
The other solution version involves adding additional functions to each shard on the basis of solution 1, making each shard more like today's Ethereum mainnet, allowing shards to store and execute code and process transactions, because Each shard will contain its unique set of smart contracts and account balances, and cross-shard communication will allow transactions between shards. However, this scheme is still under debate in the community, because the data availability of scheme 1 and the coordination of Layer 2 can already provide sufficient scalability for Ethereum, so the community is still evaluating the economic cost and benefit value of version 2.
2.2 Harmony
Harmony is a PoS-based sharding network that takes a more standard approach to sharding, the idea of which is to have multiple small blockchains called shards, each responsible for a portion of the state, and a blockchain that coordinates them, called the Beacon Chain in Harmony. Let's follow the previous discussion and see how Harmony solves the problems of network sharding, transaction sharding, and state sharding from bottom to top.
Network sharding: Harmony divides the validator network into shards, each shard contains a different set of validators closely connected to each other, and runs consensus between them.
Transaction Sharding: Harmony's transactions are handled and processed by a single shard. This enables shards to process transactions concurrently, increasing the overall transaction capacity of the blockchain. For transactions, users only need to specify the shard_id field in the signed transaction, indicating the shard to which the transaction belongs.
State sharding: In Harmony, validators for each shard need to store 1/N of the global state, since they maintain their own blockchain and state database (N=number of shards). This alleviates validators' concerns about data availability. Additionally, cross-sharding further improves state consistency between shards.
The Harmony mainnet supports thousands of nodes across multiple shards, producing blocks in seconds with instant finality. Centralization is reduced through the arrangement of the pledge mechanism, while supporting pledge delegation, reward compounding, and double-signature reduction. Using the effective mortgage mechanism of EPoS (Effective Proof-of-Stake) and the safe random sharding technology (Random Sharding), relying on the provisions of the agreement to break up the tokens mortgaged by large households into many small parts, and randomly distribute them to multiple In this way, no one can concentrate his mortgaged tokens in a single shard, so that he cannot attack a single shard.
And regarding cross-shards, in the case of cross-shard transactions and beacon chain synchronization, validators from different shards send messages across shards through a globally connected network. According to Harmony's official documents, "Kademlia cross-shard routing technology" is adopted to control the network overhead of cross-shard communication, and the "erasure code" is used to optimize the block broadcast process, so that the broadcaster's network pressure is less and avoid The sender's network bottleneck problem, so as to achieve efficient horizontal sharding expansion. Already equipped itself to be the first sharded blockchain to accomplish cross-shard messaging. With an efficient cross-shard messaging protocol and a full-mesh design, shards will be able to communicate seamlessly between each other, and as the team actively works toward this goal, users and developers can look forward to the release on Harmony later this year. Cross-shard messaging protocol.
This is a major breakthrough for builders and developers on Harmony, as they can build by collating features and using data residing on different shards. In addition, the consistency of data between shards is also important. These two pursuits will determine the sustainability of this infinite scalability.
2.3 Elrond
Elrond is a high-throughput public blockchain designed to provide security, efficiency, scalability and interoperability. The two most important features that set Elrond apart are adaptive state sharding and a secure proof-of-stake consensus mechanism.
Elrond employs all levels of adaptive state sharding for transactions, data, and networking. A dynamic adaptive sharding mechanism will perform shard merging and shard splitting, taking into account the number of available validators and network usage. Remains highly resilient to malicious attacks due to periodic node shuffling across shards. Every epoch, at most 1/3 of the nodes in each shard are reshuffled to other shards to prevent collusion. In terms of randomness, the source of randomness is secured using BLS signatures, which make it unbiased and unpredictable.
For the smart contract on the shard state architecture, the cross-shard execution process is used, and the shard load is balanced. Balancing smart contracts across shards allows Elrond to run multiple smart contracts in parallel.
At the same time, for cross-shards, Elrond adopts a design they call Meta Chain, which can quickly determine cross-shard transactions (Finality) within a few seconds. By studying its technical white paper, we simplify its process as follows: Assume that the Elrond network has only two shards and metachains. Assuming that a user generates a transaction from his wallet whose address is in shard 0 and wants to send EGLD to another user whose wallet address is in shard 1, the steps shown in the figure below are required to process cross-shard piece deal.
The structure of a block is represented by a block header containing information about the block (block nonce, round, proposer, validator timestamp, etc.), and a list of miniblocks per shard containing the actual transactions inside. In our case, for a block in shard 0, there are usually 3 miniblocks:
miniblock 0: Contains intra-shard transactions of shard 0
miniblock 1: Contains cross-shard transactions with a sender in shard 0 and a destination in shard 1
miniblock 2: contains cross-shard transactions, the sender is in shard 1, and the destination is in shard 0. These transactions have already been processed in the sender shard 1 and will be completed after the current shard is processed.
There is no limit to the number of small blocks with the same sender and receiver in a block. This means that multiple miniblocks with the same sender and receiver can appear in the same block. In this process, the atomic processing unit executed across shards is a miniblock: either immediately process all transactions of the miniblock, or not, and the execution of the miniblock will be retried in the next round .
Elrond's cross-shard transaction strategy uses an asynchronous model. Validation and processing is done first in the sender's shard and then in the receiver's shard. Transactions are first dispatched in the sender's shard, since it can fully verify any transaction initiated from an account in that shard. After that, in the receiver's shard, the node only needs the execution proof provided by the meta-chain, performs signature verification and checks for replay attacks, and finally updates the balance for the receiver and adds the transaction amount.
Shard 0 handles an intra-shard transaction in miniblock 0 and a set of cross-shard transactions whose addresses come from shard 1 as receivers in miniblock 1. Block headers and miniblocks are sent to the metachain. The metachain notarizes the blocks of shard 0 by creating a new metachain block (metablock) that contains the following information about each miniblock: sender shard ID, receiver shard ID, miniblock hash.
image description
Figure 5 Elrond's cross-shard asynchronous model
2.4 Near
Near is a fully state-sharded, developer-friendly scalable public chain. They proposed a new protocol and solution called Nightshade.
image description
Figure 6 Near abandoned the beacon chain approach and adopted the Nightshade design
Nightshade models the system as a single blockchain, where each block logically contains all transactions from all shards, and changes the overall state of all shards. Physically, no participant downloads the full state or the full logical block. Instead, each participant of the network only maintains state corresponding to the shards they validated transactions on, and the list of all transactions in a block is divided into physical chunks, one block per shard.
Under ideal conditions, each shard of each block contains exactly one block, which roughly corresponds to a model with a shard chain that generates blocks at the same rate as the beacon chain. However, some blocks may be lost due to network latency, so each shard of each block actually contains one or zero blocks.
There are two roles in Nightshade: block producers and validators. At any time, the system contains w block producers (Block Producer) and wv validators (Validator), in the near model w=100 v = 100, wv = 10,000. The system contains n shards, n = 1000 in the near model. There are no shard chains in Nightshade, instead all block producers and validators are building a single blockchain, called the main chain. The state of the main chain is divided into n shards, and each block producer and verifier only locally downloads the state subset corresponding to a certain subset of the shard at any time, and only processes and verifies the The transaction status of these parts. Maintenance of the network is done in periods, where a period is a period of days.
Block producers and block producers rotate each block according to a fixed schedule. Block producers have an order and repeatedly produce blocks in that order. For example, if there are 100 block producers, the first block producer is responsible for producing blocks 1, 101, 201, etc., and the second block producer is responsible for producing blocks 2, 102, 202, etc.). Since block production is different from block production, state needs to be maintained, and for each shard, only sww/n block producers maintain the state of each shard, correspondingly, only those sww/n block producers rotate to create blocks .
image description
first level title
text
text
text
text
When transacting across shards, how to avoid the continuous execution of shards while ensuring the atomic processing of transactions? 2. If the number of nodes less than one shard node is added to the network, how does the network deal with the extra nodes?
secondary title
3.1 Shardeum and transaction-level consensus
Shardeum has formed a unique technology and consensus algorithm that combines Proof of Quorum (PoQ) with Proof of Stake (PoS). The consensus algorithm will help secure the network through trustless voting to collect and verify the pledge of nodes. Each transaction is processed in the order received before being grouped into a block/partition.
secondary title
3.2 Shardeum and linear expansion
To explain what linear scaling is, we need to imagine the following situation:
One shard of 100 nodes on the Near main network. It is expected that more shards will be added in the future. Harmony has 4 shards, each with 250 nodes, and the main network has a total of 1,000 nodes. All contracts are in the same shard. Elrond has 3 shards and 1 metachain, each shard has 800 nodes, and the main network has a total of 3200 nodes.
If you add 100 nodes to Harmony, which is less than the 250 nodes required in a shard, how does Harmony handle these nodes? Is it possible to consider dividing this total of 1100 nodes into 11 shards of 100 nodes each?
Sounds better, but due to the static nature of some shards, many additional nodes need to join the network to create new shards. If we want to add some nodes to the above network, if only adding a single node, it is impossible to improve the performance of the entire block, at least the current "minimum shard size" number of nodes (in Near 100 nodes) - because the current shards are all static shards and do not support linear expansion, and no production network can actually split and merge static shards.
Beyond "transaction-level consensus", Shardeum's white paper mentions that a unique feature is that it uses dynamic state sharding, unlike static shards where all nodes cover the same address range, Shardeum's virtual shards (also i.e. dynamic sharding) can have each node hold a different address range, covering addresses with overlapping nodes - this has more complexity, but the benefit is that it allows true linear scaling.
Through the dynamic change of address space and node correspondence, plus a new data availability proof for cross-shard verification, Shardeum can achieve fitting or approximate "linear expansion". This method of verification and confirmation according to the "transaction level" may sacrifice the performance of a single chip to a certain extent, but it is a very beneficial expansion for the network as a whole.
image description
Figure 8 In the third quarter of 2021, Shardus has been proven to achieve cross-shard transactions of 5000 TPS
first level title
Four. Conclusion
A truly sharded and scalable blockchain needs to start from scratch. Similarly, a community with a diamond-like consensus also needs to be built from scratch, and community building has never been easier than technological research and breakthroughs. We have seen the number of active testers and the number of test transactions after the Shardeum testnet was launched. We are excited that more people are walking hand in hand on the road of innovation we have discovered. At the same time, we have seen some voices of doubt, but we believe that the road of progress is a spiral And twists and turns, any creativity and exploration are worth a try.
first level title
Reference
1.https://blog.chain.link/blockchain-scalability-approaches-zh/
2.https://www.odaily.news/post/5147856
3.https://docs.near.org/concepts/basics/transactions/overview
4.https://medium.com/nearprotocol/the-authoritative-guide-to-blockchain-sharding-part-1-1b53ed31e060
5.https://medium.com/nearprotocol/unsolved-problems-in-blockchain-sharding-2327d6517f43
6.https://medium.com/nearprotocol/why-doesnt-near-just-replicate-ethereum-serenity-design-3e2cfa2f960c
7.https://ethereum.org/en/upgrades/sharding/#what-is-sharding
8.https://blog.ethereum.org/2020/03/27/sharding-consensus
9.https://www.web3.university/article/ethereum-sharding-an-introduction-to-blockchain-sharding
10.https://medium.com/harmony-one/enabling-cross-shard-communication-at-harmony-22f26483d0d1
11.https://en.elrondwiki.com/article/multi-shard-the-answers-to-certain-questions
12.https://docs.elrond.com/technology/cross-shard-transactions/
13.https://near.org/papers/nightshade/
14.https://shardus.com/whitepaper.pdf
text
text
textwww.jsquare.co
Twitter｜@JSquare_co
