# A Comprehensive Survey on Sharding in Blockchains

Authors: Jinwen Xi; Shihong Zou; Guoai Xu; Yanhui Guo; Yueming Lu; Jiuyun Xu; Xuanwen Zhang
Journal: Mobile Information Systems
 (2021)

---

## Abstract

Blockchain technology has been widely used in many fields, such as smart cities, smart health care, and smart manufacturing, due to its anonymity, decentralization, and tamper resistance in peer-to-peer (P2P) networks. However, poor scalability has severely affected the widespread adoption of traditional blockchain technology in high-throughput and low-latency applications. Therefore, based on the three-layer architecture, this study presents a variety of solutions to improve the scalability of the blockchain. As the scale of the network expands, one of the most practical ways to achieve horizontal scalability is sharding, where the network is divided into multiple subnetworks to avoid repeated communication overhead, storage, and calculations. This study provides a systematic and comprehensive introduction to blockchain sharding, along with a detailed comparison and evaluation for primarily considered sharding mechanisms. We also provide the detailed calculations and then analyze the characteristics of existing solutions along with our insights.


---

## Body

## 1. Introduction

Since the publication of Bitcoin, the most famous peer-to-peer (P2P) payment system presented in 2008 [1], the concept of blockchain has spread across the world. The blockchain technology is well known for leading to an increased transparency, decentralization, and tamper resistance. In recent years, these benefits have motivated the wide application of blockchain to almost all industry segments, including cryptocurrencies, Internet of Things, supply chain finance, social welfare, government affairs, and artificial intelligence [2–4]. Blockchain (the technical logic architecture is shown in Figure 1, including seven layers) is regarded as another disruptive technology after cloud computing, the Internet of Things, and Big Data. It is highly concerned by governments, financial institutions, and technology companies in various countries.Figure 1
Blockchain technical logic architecture.However, the scalability issue of blockchain has always been the focus of the industry, which means whether the era of large-scale commercial usage of blockchain will really come. In particular, Bitcoin [1] can only process 7 transactions per second, Ethereum [5] can process 15 transactions per second, and EOS [6] can process up to hundreds of transactions per second. The number of transactions that can be processed per second, that is, throughput, is far from the actual transaction processing requirements. Improving transaction throughput has become a stuck neck problem for blockchain to be implemented in multiple scenarios. By contrast, Visa can process 1,700 transactions per second. That is, the scalability issue of blockchain needs to be solved urgently.In the past literature, scalability is not well defined. However, Vitalik Buterin, the co-founder of Ethereum [7], firstly described the well-known scalability trilemma, stating that trade-offs are inevitable between three significant properties of blockchain: decentralization, security, and scalability. Decentralization is the core and the intrinsic nature of blockchain, and security is an essential property, whereas scalability is the main challenge. We can only have two of either decentralization, security, or scalability at the same time (i.e., we can pick just one side of the triangle that is shown in Figure 2). Thus, trade-offs are almost inevitable.Figure 2
Blockchain trilemma.That is, it is challenging to improve scalability without sacrificing decentralization and security in a blockchain-based system. There are several solutions proposed in the literature to solve the scalability issue. In this study, we classify these solutions into three categories in Table1 according to the blockchain technical logic architecture: Layer 0 solutions (e.g., BDN [8] and bloXroute [9]), Layer 1 solutions (e.g., Segregated Witness [10], DAG [11–13], sharding [14–17], and consensus [18–20]), and Layer 2 solutions (e.g., state channels [21], side chain [22], cross-chain [23], and off-chain computation [24]). Layer 0 solutions are designed for improving the scalability by changing the underlying data transmission protocol of blockchain; Layer 1 solutions are designed for improving the scalability by changing the basic blockchain protocol such as block data structure, consensus algorithms, and incentive measures; and Layer 2 solutions are designed for improving the scalability through the off-chain methods at the application layer.Table 1
Description of scalability solutions.
No.CategoryLayerSolutionDescription1Scaling on-chainData layer solutionsExpand blockIncreasing block size2Segregated WitnessIsolating digital signatures and increasing the block size in disguise3Directed acyclic graph (DAG)Changing chain structure to net structure4Network layer solutionsShardingParallel processing of transactions in shards to improve processing efficiency5Consensus layer solutionsBFT consensusReaching consensus through voting6Non-BFT consensusReducing block verification propagation time and consensus formation time by reducing the complexity of the consensus algorithm and reducing the number of propagation nodes7Hybrid consensusCombining multiple consensus algorithms8Scaling off-chainLayer 2 solutionsState channelsTransferring part of the transaction to the state channel, which can be opened and closed at any time9Side chainTransferring transaction to the side chain and processed by the root chain only when fraud occurs10Cross-chainRealizing transactions off-chain from a cross-chain perspective11Off-chain computationExecuting complex transactions off-chain, and the result is returned to the chain12Scaling on Layer 0Layer 0 solutionsBDN/bloXrouteImproving the scalability of the blockchain by modifying and optimizing the underlying protocol, without affecting the existing blockchainHowever, these proposed solutions cannot make significant performance gains without sacrificing decentralization or security, or both. In particular, the scalability solution that preserves both decentralization and security is sharding, which creates multiple groups (called shards) of validators and lets them process transactions in parallel [25]. Thus, we focus on sharding in this study, which is considered one of the most promising solutions to the scalability issue.New blockchain-based sharding solutions have been proposed in recent studies [10, 25–28]. Surveys of blockchain scalability [29–34] that only focused on vertical scaling and reducing overhead have been gradually taking blockchain sharding into account. However, none of them can systematically introduce the characteristics and restrictions of existing sharding solutions, as well as the challenges and future trends.


### 1.1. Summary of Main Contributions

The main contributions of this study can be summarized as follows:(1)
This study is the first to provide a comprehensive introduction of blockchain scalability mechanisms ranging from technical logic architecture to various scalability schemes. Sharding is considered as the scalability solution that preserves both decentralization and security.(2)
Then, we survey and compare shard-based blockchain mechanisms, giving our insights to analyze the features and restrictions of existing mechanisms, including intrashard consensus protocol security, cross-shard transaction atomicity, and general improvements.(3)
Finally, we propose a comprehensive comparison of all the considered sharding mechanisms and obtain the theoretical upper bound of throughput through a large number of calculations and simulation experiments.


### 1.2. Paper Organization

The remainder of this study is organized as follows. We review the existing related works in Section2 and then present the overview of sharding technology in Section 3. We provide a systematic survey of sharding solutions in Section 4, upon which the comprehensive comparison and evaluation are presented in Section 5. Finally, we conclude our survey in Section 6.


## 1.1. Summary of Main Contributions

The main contributions of this study can be summarized as follows:(1)
This study is the first to provide a comprehensive introduction of blockchain scalability mechanisms ranging from technical logic architecture to various scalability schemes. Sharding is considered as the scalability solution that preserves both decentralization and security.(2)
Then, we survey and compare shard-based blockchain mechanisms, giving our insights to analyze the features and restrictions of existing mechanisms, including intrashard consensus protocol security, cross-shard transaction atomicity, and general improvements.(3)
Finally, we propose a comprehensive comparison of all the considered sharding mechanisms and obtain the theoretical upper bound of throughput through a large number of calculations and simulation experiments.


## 1.2. Paper Organization

The remainder of this study is organized as follows. We review the existing related works in Section2 and then present the overview of sharding technology in Section 3. We provide a systematic survey of sharding solutions in Section 4, upon which the comprehensive comparison and evaluation are presented in Section 5. Finally, we conclude our survey in Section 6.


## 2. Related Work

We have investigated the existing studies [30, 33, 35–37] on the scalability of the blockchain and discussed them in conjunction with our work. Note that previous studies have mainly emphasized the development trend of future blockchain scalability and tried to scale the blockchain network. Besides, some researchers introduce new ideas to enhance blockchain scalability. These solutions include but are not limited to block expansion, Segregated Witness, DAG, scalable consensus algorithms, and multichain architecture.The previous surveys [18, 29, 31, 32, 34, 38, 39] include discussions of the above solutions, but little research on sharding. Sharding technology is not an innovative concept. It has been operating in traditional databases long before the advent of blockchain technology and is mainly used to optimize large commercial databases. The concept is to cut the data in the database into many data fragments and then allocate these fragments to different servers for storage. In this way, there will be no server overload problem due to a large number of data access requests in a short period of time. Sharding has been considered the most practical solution for horizontally scaling blockchain systems so far. Therefore, many researchers have proposed their sharding mechanisms; at the same time, some surveys have been published to summarize these solutions and propose new benchmarks. However, all of these studies only analyze and evaluate one or two sharding mechanisms, and the introduction and evaluation of sharding are vague.Some documents put their focus on sharding. Bez et al. [40] propose a scalable three-dimensional architecture and emphasize that horizontal scalability can only be improved by isolating data and consensus. However, its introduction to the Ethereum 2.0 sharding scheme is vague and [3] has the same problem. The separation of the consensus layer from the blockchain ledger data is inconsistent with reality. To benchmark sharding mechanisms, Manshaei et al. [41] propose an analytic model based on game theory. Furthermore, the Byzantine fault tolerance (BFT) algorithm [41, 42] is used to reach consensus between multiple committees in sharding, which is outdated as Ref. [43] proposes a sharding mechanism based on Nakamoto (Monoxide). In Ref. [15, 44], there is no unified comparison between Nakamoto-based sharding mechanisms and BFT-based sharding mechanisms.To the best of our knowledge, there is currently no comprehensive overview of sharding. This article introduces the fundamental concepts related to various sharding mechanisms, comprehensively compares the more typical sharding mechanisms, and provides new guidance ideas for researchers based on our insights. Besides, we provide a comparison, based on the insights and calculation, among the considered sharding mechanisms. The result is characterized in Tables2 and 3.Table 2
A comprehensive comparison of considered blockchain scalability solutions.
ParameterMonoxideElasticoOmniLedgerRapidChainChainspaceEthereum 2.0TEEChainNetwork model (S: synchronization; PS: partial synchronization; AS: asynchronization)PSPSPSIntraSPSPSPSTotalPSRandomnessExistenceNoYesYesYesUnknownYesYesUseN/A(1) The seed of PoW puzzle for the next epoch; (2) select the leader during intrashard consensus(1) Select the leader and the subgroup allocation; (2) epoch reconfiguration; (3) trust-but-verify transaction validation scheme(1) The seed of PoW puzzle for the next epoch; (2) select the leader during intrashard consensus; (3) decentralized bootstrapping; (4) epoch reconfigurationUnknown(1) Select the proposer and attesters of each shard; (2) select the validators responsible for checkpointing from the global pool(1) Decentralized bootstrapping; (2) epoch reconfigurationParticipantsNode allocationAddress-based one-off allocationPoW-based allocationR-based allocationPoW-based allocationObject-based one-off allocationR-based allocationR-based allocationSafe epoch reconfigurationN/AUnsafeYes,2/3 at a given timeYes, swapping out a constant number of nodeN/AYesYes,t/nTransaction data structureAccount-basedUTXO-basedUTXO-basedUTXO-basedObject-driven, contract-shardedAccount-basedGeneral workloadGlobal blockchainNoYesYesYesNoYesYesIntrashard consensus algorithmPoW-based Chu-ko-nu miningPBFTByzCoinX50% BFTMod start+ PBFTBFT-based PoSTEE+ PBFTSecurity modelThreat modelArbitrarily, uncoordinated majorityArbitrarily, slowly adaptiveArbitrarily, slowly adaptiveArbitrarily, slowly adaptiveArbitrarily, uncoordinated majorityArbitrarily, uncoordinated majorityArbitrarily, uncoordinated majorityFTIntrashard1/21/31/31/21/31/31/2Global1/21/41/41/31/41/31/2Cross-shard TxSupport or noSupportNoSupportSupportSupportSupportSupportMethod (S: synchronization; AS: asynchronization)AS, lock-freeN/AS, lock, or unlockS, lock, or unlockS, lock, or unlockS, lock, or unlockS, 2PC, and 2PLComplexityCommunicationMixed:Om+nlog2n Identical: Om+nOm2+nOlog2m+nOm2+mlog2nOm2+nOm2+nO2−lN2StorageOS∼OS+nShOnSOSOS+SrOS+SnhOS+nH+Sg∼OnS+SgOSTable 3
A comparison among the discussed sharding mechanisms.
ParameterMonoxideElasticoOmniLedgerRapidChainChainspaceEthereum 2.0TEEChainShard settingsNumber of shardsn210∼218<102<26<28<102<29<25Shard sizem102∼104<10222∼21022∼28<102<102<26Epoche lengthN/A10min24hours24hoursUnknown1week24hoursLatencyTransaction confirmation24 s<800s90s60s3s7s5.9∼15sEpoch reconfigurationN/AN/A1000s200∼300sUnknownUnknown80sImproving factorNn/2n1∼n/2n/21∼n/2n/3n/2Throughput1.024∼2.048Mtps38.4ktps24ktps128ktps<400tps86ktps16ktps


## 3. Preliminaries of Sharding

### 3.1. Overview of Sharding Technology

In the traditional blockchain network, transactions must be confirmed by each node to ensure security, which is one of the main reasons why it is difficult to increase the transaction speed. In addition, most blockchains are single-chain structures, and all miners compete for the accounting rights of the next block, and most of the blockchains have a fixed average time for generating blocks. For example, Bitcoin generates a block every 10 minutes. Though more and more miners join the ranks of mining, the blockchain will automatically increase the mining difficulty to guarantee that the block generation speed is fixed at a block every 10 minutes. The increase in computing power cannot improve the transaction speed; this is why the blockchain is not scalable.Sharding is first proposed by Ref. [45] and is commonly used in distributed databases and cloud infrastructure. Based on the pioneering proposals [14, 46], sharding technology is integrated with permissioned and permissionless blockchain. The way to apply the sharding technology to the blockchain network divides the blockchain network into several subnetworks (or shards). Each subnetwork will contain a part of the nodes. The data and transactions stored in the network will be randomly assigned to each shard. In this way, each node only needs to process a small part of the work and transactions in different shards can be processed in parallel, so the transaction speed of the network can be improved (as shown in Figure 3). Sharding is one of the most practical solutions to achieve a scaling blockchain system, where the calculation, storage, and processing can be conducted in parallel. It is possible that the capacity and throughput are linearly proportional to the number of shards or that of participating nodes.Figure 3
Sharding workflow.


### 3.2. Categories of Sharding

In sharding technology, the increase in blockchain computing power means an increase in the number of shards. That is to say, for the independent transactions (inputs and outputs are in the same shard), the more computing power invested in the network, the more transactions that can be processed in parallel at the same time, and the transaction speed of the entire network will increase linearly. The sharding technology used on the blockchain can be divided into three categories: network sharding, transaction sharding, and state sharding. Calculation sharding is considered to run through the entire sharding scheme [14].


#### 3.2.1. Network Sharding

Because of the strong connectivity between blocks, that is to say, when a block is added, miners need to communicate with each other to confirm the validity of the new block, although this can ensure the accuracy of transactions, but also lead to the shortcomings of nonscalability in the blockchain structure. Therefore, the first step of sharding is to shard the blockchain network, on the premise of minimizing communication with each other. Each shard handles on-chain transactions. The miners are randomly grouped, and the work is assigned to each group of miners for independent verification.There are two main schemes for network sharding to ensure the security of on-chain transactions:(i)
Random allocation: after the miners are grouped, the first problem of network sharding that needs to be solved is how to resist low-cost attacks. Assuming that under PoW, an attacker needs to master51% of the computing power for paralyzing the network, and as sharding progresses, the attacker may only need to have 1% of the entire network’s computing power to have the opportunity to paralyze one or even two of shards, but this 1% of the computing power does not work at all under the original PoW. Establishing randomness is an effective way to prevent attackers. The method of establishing randomness in the blockchain field is mainly to use verifiable random function (VRF) [47], which supports randomly selecting nodes to form shards. Such a random sampling method can prevent malicious nodes from controlling a single shard.(ii)
Consensus protocols of sharding: after solving the problem of grouping miners, we have to face the grouped miners and reach a consensus during the verification process. The consensus algorithms can choose PoW [48], PoS [49], PBFT [50], and others. In other words, network sharding is the mining rule. To avoid centralization while sharding, developers need to strike a good balance between security and efficiency, for example, the number of shards in the network and the number of nodes in each shard.


#### 3.2.2. Transaction Sharding

Transaction sharding solves which transactions will be allocated to which shards. Then, the difference in the blockchain ledger model will have an impact on transaction sharding.(i)
UTXO-based ledger model: UTXO means unspent transaction output, such as Bitcoin, and transaction records are composed of multiple inputs and multiple outputs [51]. There is no concept of an account and balance. It is impossible to split transactions according to addresses to avoid the double-spending problem effectively. The intuitive way of sharding is to divide transactions according to the last few bits of the transaction hash value. For example, if the last bit of the hash value is 0, the transaction will be allocated to shard 1; otherwise, it will be allocated to shard 2 (assuming there are two shards). However, if the initiator issues multiple transactions with the same input but different outputs within a certain period of time, if no measures are taken, different transactions may be allocated to different shards for processing and verification, leading to double-spending attacks. To solve the double-spending problem, communication between shards is necessary to ensure that the same amount is not repeatedly spent, but this violates the concept of independent verification of shards. Therefore, the UTXO ledger model is inherently difficult to achieve real sharding.(ii)
Account-based ledger model: therefore, most blockchains using sharding technology are based on the ledger account model [52] like Ethereum. On the basis of the account, each transaction will contain the sender’s address and balance. The transaction can be partitioned according to the sender’s address to ensure that multiple transactions from the same account are processed in the same shard, effectively detecting double-spending transactions. However, if when a cross-shard transaction is involved, cross-shard communication is required to verify the transaction validity. The difference from UTXO is that it only needs to be carried out between two shards rather than all shards.


#### 3.2.3. State Sharding

State sharding can be understood as assigning blockchain data to different shards, thereby reducing the storage burden of nodes. Compared with the other two sharding mechanisms, state sharding is the most difficult. At present, three challenges need to be solved to implement state sharding:(i)
The benefit balance of cross-shard transaction communication: transactions will be processed according to the address allocation in different shards. When cross-shard transactions are involved, communication between shards is required to ensure the transaction validity. Fragmentation interaction can easily lead to a decrease in overall network efficiency;(ii)
The balance between the dynamic reconfiguration of shards and the update of node status: the nodes in the blockchain network will increase over time, and if the nodes are not redistributed for a long time, it will lead to an excessive centralization of the transaction state and reduce the flexibility when being attacked. Therefore, the network needs to reconfigure the network nodes after every epoch, the transaction must be processed after the segment completes the network synchronization, which will cause some delay problems, and even cause the segmentation to be paralyzed; and(iii)
The balance between network-wide data backup and centralization risk: if certain specific shards are attacked and their verification becomes invalid, since the shards do not replicate the entire state of the system, the network cannot rely on verification of the transactions in this shard. Therefore, it is necessary to maintain data archives or node backups to help the system repair fault and restore unavailable data.


## 3.1. Overview of Sharding Technology

In the traditional blockchain network, transactions must be confirmed by each node to ensure security, which is one of the main reasons why it is difficult to increase the transaction speed. In addition, most blockchains are single-chain structures, and all miners compete for the accounting rights of the next block, and most of the blockchains have a fixed average time for generating blocks. For example, Bitcoin generates a block every 10 minutes. Though more and more miners join the ranks of mining, the blockchain will automatically increase the mining difficulty to guarantee that the block generation speed is fixed at a block every 10 minutes. The increase in computing power cannot improve the transaction speed; this is why the blockchain is not scalable.Sharding is first proposed by Ref. [45] and is commonly used in distributed databases and cloud infrastructure. Based on the pioneering proposals [14, 46], sharding technology is integrated with permissioned and permissionless blockchain. The way to apply the sharding technology to the blockchain network divides the blockchain network into several subnetworks (or shards). Each subnetwork will contain a part of the nodes. The data and transactions stored in the network will be randomly assigned to each shard. In this way, each node only needs to process a small part of the work and transactions in different shards can be processed in parallel, so the transaction speed of the network can be improved (as shown in Figure 3). Sharding is one of the most practical solutions to achieve a scaling blockchain system, where the calculation, storage, and processing can be conducted in parallel. It is possible that the capacity and throughput are linearly proportional to the number of shards or that of participating nodes.Figure 3
Sharding workflow.


## 3.2. Categories of Sharding

In sharding technology, the increase in blockchain computing power means an increase in the number of shards. That is to say, for the independent transactions (inputs and outputs are in the same shard), the more computing power invested in the network, the more transactions that can be processed in parallel at the same time, and the transaction speed of the entire network will increase linearly. The sharding technology used on the blockchain can be divided into three categories: network sharding, transaction sharding, and state sharding. Calculation sharding is considered to run through the entire sharding scheme [14].


### 3.2.1. Network Sharding

Because of the strong connectivity between blocks, that is to say, when a block is added, miners need to communicate with each other to confirm the validity of the new block, although this can ensure the accuracy of transactions, but also lead to the shortcomings of nonscalability in the blockchain structure. Therefore, the first step of sharding is to shard the blockchain network, on the premise of minimizing communication with each other. Each shard handles on-chain transactions. The miners are randomly grouped, and the work is assigned to each group of miners for independent verification.There are two main schemes for network sharding to ensure the security of on-chain transactions:(i)
Random allocation: after the miners are grouped, the first problem of network sharding that needs to be solved is how to resist low-cost attacks. Assuming that under PoW, an attacker needs to master51% of the computing power for paralyzing the network, and as sharding progresses, the attacker may only need to have 1% of the entire network’s computing power to have the opportunity to paralyze one or even two of shards, but this 1% of the computing power does not work at all under the original PoW. Establishing randomness is an effective way to prevent attackers. The method of establishing randomness in the blockchain field is mainly to use verifiable random function (VRF) [47], which supports randomly selecting nodes to form shards. Such a random sampling method can prevent malicious nodes from controlling a single shard.(ii)
Consensus protocols of sharding: after solving the problem of grouping miners, we have to face the grouped miners and reach a consensus during the verification process. The consensus algorithms can choose PoW [48], PoS [49], PBFT [50], and others. In other words, network sharding is the mining rule. To avoid centralization while sharding, developers need to strike a good balance between security and efficiency, for example, the number of shards in the network and the number of nodes in each shard.


### 3.2.2. Transaction Sharding

Transaction sharding solves which transactions will be allocated to which shards. Then, the difference in the blockchain ledger model will have an impact on transaction sharding.(i)
UTXO-based ledger model: UTXO means unspent transaction output, such as Bitcoin, and transaction records are composed of multiple inputs and multiple outputs [51]. There is no concept of an account and balance. It is impossible to split transactions according to addresses to avoid the double-spending problem effectively. The intuitive way of sharding is to divide transactions according to the last few bits of the transaction hash value. For example, if the last bit of the hash value is 0, the transaction will be allocated to shard 1; otherwise, it will be allocated to shard 2 (assuming there are two shards). However, if the initiator issues multiple transactions with the same input but different outputs within a certain period of time, if no measures are taken, different transactions may be allocated to different shards for processing and verification, leading to double-spending attacks. To solve the double-spending problem, communication between shards is necessary to ensure that the same amount is not repeatedly spent, but this violates the concept of independent verification of shards. Therefore, the UTXO ledger model is inherently difficult to achieve real sharding.(ii)
Account-based ledger model: therefore, most blockchains using sharding technology are based on the ledger account model [52] like Ethereum. On the basis of the account, each transaction will contain the sender’s address and balance. The transaction can be partitioned according to the sender’s address to ensure that multiple transactions from the same account are processed in the same shard, effectively detecting double-spending transactions. However, if when a cross-shard transaction is involved, cross-shard communication is required to verify the transaction validity. The difference from UTXO is that it only needs to be carried out between two shards rather than all shards.


### 3.2.3. State Sharding

State sharding can be understood as assigning blockchain data to different shards, thereby reducing the storage burden of nodes. Compared with the other two sharding mechanisms, state sharding is the most difficult. At present, three challenges need to be solved to implement state sharding:(i)
The benefit balance of cross-shard transaction communication: transactions will be processed according to the address allocation in different shards. When cross-shard transactions are involved, communication between shards is required to ensure the transaction validity. Fragmentation interaction can easily lead to a decrease in overall network efficiency;(ii)
The balance between the dynamic reconfiguration of shards and the update of node status: the nodes in the blockchain network will increase over time, and if the nodes are not redistributed for a long time, it will lead to an excessive centralization of the transaction state and reduce the flexibility when being attacked. Therefore, the network needs to reconfigure the network nodes after every epoch, the transaction must be processed after the segment completes the network synchronization, which will cause some delay problems, and even cause the segmentation to be paralyzed; and(iii)
The balance between network-wide data backup and centralization risk: if certain specific shards are attacked and their verification becomes invalid, since the shards do not replicate the entire state of the system, the network cannot rely on verification of the transactions in this shard. Therefore, it is necessary to maintain data archives or node backups to help the system repair fault and restore unavailable data.


## 3.2.1. Network Sharding

Because of the strong connectivity between blocks, that is to say, when a block is added, miners need to communicate with each other to confirm the validity of the new block, although this can ensure the accuracy of transactions, but also lead to the shortcomings of nonscalability in the blockchain structure. Therefore, the first step of sharding is to shard the blockchain network, on the premise of minimizing communication with each other. Each shard handles on-chain transactions. The miners are randomly grouped, and the work is assigned to each group of miners for independent verification.There are two main schemes for network sharding to ensure the security of on-chain transactions:(i)
Random allocation: after the miners are grouped, the first problem of network sharding that needs to be solved is how to resist low-cost attacks. Assuming that under PoW, an attacker needs to master51% of the computing power for paralyzing the network, and as sharding progresses, the attacker may only need to have 1% of the entire network’s computing power to have the opportunity to paralyze one or even two of shards, but this 1% of the computing power does not work at all under the original PoW. Establishing randomness is an effective way to prevent attackers. The method of establishing randomness in the blockchain field is mainly to use verifiable random function (VRF) [47], which supports randomly selecting nodes to form shards. Such a random sampling method can prevent malicious nodes from controlling a single shard.(ii)
Consensus protocols of sharding: after solving the problem of grouping miners, we have to face the grouped miners and reach a consensus during the verification process. The consensus algorithms can choose PoW [48], PoS [49], PBFT [50], and others. In other words, network sharding is the mining rule. To avoid centralization while sharding, developers need to strike a good balance between security and efficiency, for example, the number of shards in the network and the number of nodes in each shard.


## 3.2.2. Transaction Sharding

Transaction sharding solves which transactions will be allocated to which shards. Then, the difference in the blockchain ledger model will have an impact on transaction sharding.(i)
UTXO-based ledger model: UTXO means unspent transaction output, such as Bitcoin, and transaction records are composed of multiple inputs and multiple outputs [51]. There is no concept of an account and balance. It is impossible to split transactions according to addresses to avoid the double-spending problem effectively. The intuitive way of sharding is to divide transactions according to the last few bits of the transaction hash value. For example, if the last bit of the hash value is 0, the transaction will be allocated to shard 1; otherwise, it will be allocated to shard 2 (assuming there are two shards). However, if the initiator issues multiple transactions with the same input but different outputs within a certain period of time, if no measures are taken, different transactions may be allocated to different shards for processing and verification, leading to double-spending attacks. To solve the double-spending problem, communication between shards is necessary to ensure that the same amount is not repeatedly spent, but this violates the concept of independent verification of shards. Therefore, the UTXO ledger model is inherently difficult to achieve real sharding.(ii)
Account-based ledger model: therefore, most blockchains using sharding technology are based on the ledger account model [52] like Ethereum. On the basis of the account, each transaction will contain the sender’s address and balance. The transaction can be partitioned according to the sender’s address to ensure that multiple transactions from the same account are processed in the same shard, effectively detecting double-spending transactions. However, if when a cross-shard transaction is involved, cross-shard communication is required to verify the transaction validity. The difference from UTXO is that it only needs to be carried out between two shards rather than all shards.


## 3.2.3. State Sharding

State sharding can be understood as assigning blockchain data to different shards, thereby reducing the storage burden of nodes. Compared with the other two sharding mechanisms, state sharding is the most difficult. At present, three challenges need to be solved to implement state sharding:(i)
The benefit balance of cross-shard transaction communication: transactions will be processed according to the address allocation in different shards. When cross-shard transactions are involved, communication between shards is required to ensure the transaction validity. Fragmentation interaction can easily lead to a decrease in overall network efficiency;(ii)
The balance between the dynamic reconfiguration of shards and the update of node status: the nodes in the blockchain network will increase over time, and if the nodes are not redistributed for a long time, it will lead to an excessive centralization of the transaction state and reduce the flexibility when being attacked. Therefore, the network needs to reconfigure the network nodes after every epoch, the transaction must be processed after the segment completes the network synchronization, which will cause some delay problems, and even cause the segmentation to be paralyzed; and(iii)
The balance between network-wide data backup and centralization risk: if certain specific shards are attacked and their verification becomes invalid, since the shards do not replicate the entire state of the system, the network cannot rely on verification of the transactions in this shard. Therefore, it is necessary to maintain data archives or node backups to help the system repair fault and restore unavailable data.


## 4. A Systematic Survey on Sharding

New challenges have been proposed in sharding, i.e., the intrashard consensus protocol security, cross-shard transaction atomicity, and general improvements regarding the reconfiguration, latency, and storage. It is significant for all sharding mechanisms to resolve these issues.(i)
Intrashard consensus protocol security: it is to ensure that the consensus protocol on transactions within a shard is kept away from Nakamoto-based50% and BFT-based 1% attacks [40]. Note that BFT-based 1% attack is considered as a consensus-attacking strategy in a sharding network. Not as difficult as attacking the entire network, an attacker can easily control a single shard by breaking the intrashard consensus process [16].(ii)
Cross-shard transaction atomicity: as the sharding network expands, transactions between shards are inevitable. Cross-shard transaction verification and atomicity guarantee are important to the entire sharding system [17, 53, 54].(iii)
General improvements: due to the intrashard consensus security and cross-shard transaction atomicity, this study focuses on the improvement factor that optimizes the global throughput multiple of each considered sharding mechanism. Furthermore, we also consider the additional latency and overhead, and other new problems from the proposed sharding solutions. Therefore, we discuss some general improvements adopted in the considered schemes.We take these three aspects as the survey methodology and focus on sharding in a permissionless blockchain network, which is based on the typically published papers and other research references, such as Monoxide [43], Elastico [14], OmniLedger [28], RapidChain [27], Chainspace [55], Ethereum 2.0 [56], and TEEChain [26]. The used notations of necessary parameters are shown in Table 4.Table 4
Notation definition.
No.NotationDefinition1PTotal amount of mining power2ℬBlock3ℋHash function4HBlock header5SigSignature6TxTransaction7kMining factor of shards8tTotal number of validators9nNumber of shards10mSize of each shard11ℛRandom seed12eEpoch13TBlock period14hBlock height15NImproving factor16ShBlockchain with a block height ofh within a single shard17Sh^Header chain with a block height ofh within a single shard


### 4.1. Intrashard Consensus Protocol Security

Sharding technology improves throughput at the expense of security, making blockchain systems more vulnerable to attacks.In the traditional PoW consensus mechanism, due to the total mining powerP, it is difficult for a single entity to control the whole network by dominating more than 50% network mining power. After sharding the network (assuming n shards), although throughput increases, the network mining power is thus distributed into the different shards. A single shard is more vulnerable to be attacked than the entire network, because ideally a malicious node would only need to control about P/n×50% mining power to manipulate the entire shard. As the scale of sharding increases, the situation will continue to deteriorate, which is why the PoW consensus mechanism is not suitable for the intrashard consensus.Different from PoW-based consensus mechanisms, the BFT-based consensus mechanism is considered to be more effective in dealing with the abovementioned attacks. However, such design also introduces other problems as follows:(i)
Randomness generation: generating an unpredictable and unbiasable randomness is important for the sharding scheme independently in permissionless blockchains, which can be used for (1) validator allocation and (2) leader selection at the beginning of each epoch, meanwhile (3) determining the transmission route of a cross-shard transaction, etc. In this way, a strictly selected randomness is effectively used to prevent attackers from biasing the node allocation and controlling the leader election in a shard.(ii)
Shard size: the shard size is proportional to the strength of attack resistance for the BFT-based consensus algorithms. To improve security, the shard size should be increased as much as possible. However, an excessively high shard size will seriously affect the transaction throughput, resulting in greater overhead due to complex communication. We use the binomial distribution function to describe as follows:(1)Fx;m,p=PX≤x=∑i=0xmipi1−pm−i,F^x;m,p=1−Fx;m,p,whereX represents an event that a malicious miner is randomly picked; m denotes the shard size; x indicates the number of malicious members in a shard; and p denotes the global fault tolerance. Note that Fx;m,p is suggested to be larger than 99% [57], while it requires m>143, which will significantly reduce the efficiency of traditional BFT-based consensus algorithm.Next, we discuss and compare the considered intrashard consensus mechanisms, including Monoxide, Elastico, OmniLedger, RapidChain, Chainspace, Ethereum 2.0, and TEEChain.


#### 4.1.1. Monoxide: PoW-Based Chu-Ko-Nu Mining

Monoxide is the first to combine Chu-ko-nu mining with PoW-based algorithm for achieving intrashard consensus and solving the problem of computing power being diluted after partitioning, which makes attacking a single shard as difficult as attacking the entire system, where a Merkle Patricia tree (MPT) [5] is used to store all proposed blocks from multiple shards.Chu-ko-nu mining is inspired by merged mining [58], which applies the PoW-based consensus and adopts a parent-child chain to share mining power. The parent chain with total mining power can protect these child chains with relatively smaller mining power from being attacked. Furthermore, an MPT root is involved to store all proposed blocks from different shards. Furthermore, the factor of k can be used to amplify the mining power; when k⟶n, the effective mining power that contributed by shards can achieve Pk/n≃P to address 1% attack.In particular, the consensus algorithm in Monoxide is described as follows:(2)ℋφ‖ℋH‖MPTM≤ϵ,where ℋ represents the hash function; φ indicates the random nonce; H denotes the block header content; MPTM represents the MPT root that aggregated by ℬ0,ℬ1,…,ℬn−1 of each involved shard; and ϵ denotes the PoW target difficulty. φ, identities, and relay transactions are involved in each block.Chu-ko-nu mining algorithm allows miners in any shard to generate multiple blocks when successfully solving the hash puzzle, but at most one block in each shard. In this way, the computing power of miners in each shard is amplified, so that the same level of computing power is required to attack a single shard as attacking the entire system.Monoxide requires most miners in each shard to conduct Chu-ko-nu mining (i.e.,k=n) to meet Pk/n≃P. Because scattered mining power may not guarantee the security of a single shard, on the other hand, it could result in overconcentration of mining power and generate additional overhead.


#### 4.1.2. Elastico: BFT-Based

As shown in Figure4, Elastico is the first to implement an intrashard BFT-based consensus protocol. In particular, Elastico allocates validators to different shards according to the least significant bits generated by the random solutions at the beginning of each epoch and then runs a classical Byzantine agreement protocol for intrashard consensus. Members agree and sign on one valid data block, and valid blocks have 2m/3+1 signatures.Figure 4
Node allocation of Elastico.(1) Randomness Generation: A Decentralized Commit-And-Xor Scheme. This scheme is proposed to generate the randomness used in the mining process, which allows different random numbers picked by nodes to achieve unbiased and verifiably random. Each final committee member picks a random seed Ri and broadcasts the hash value ℋRi to other committee members, and these members reach an agreement on a single set of hash values S and broadcast it to the entire network. Note that S must contain at least 2m/3 signatures (m denotes the size of the final committee). Each final member broadcasts the selected Ri, and other nodes in the network will receive at least 2m/3 and at most 3m/2Ri−ℋRi pairs from the final committee members and discard the unmatched Ri−ℋRi pairs. The final randomness can be finalized by randomly picking m/2+1 pairs from the remaining matched Ri−ℋRi pairs for an XOR operation.(2) Consensus Algorithm: Restrictions of PBFT in Sharding. According to the experimental results in Ref. [59], the transaction failure probability of Elastico is close to 8% with Fx;m,p=F6;16,0.25. When the network scale is expanded to 100 shards m=100, it still incurs a 2.76% failure probability, which may be the bottleneck [28] to hinder Elastico from being practically applied. On the other hand, OmniLedger and RapidChain claim greatly improve this problem.


#### 4.1.3. OmniLedger: BFT-Based

As shown in Figure5, to resolve the bottleneck of Elastico, OmniLedger combines verifiable random function (VRF) [60] and RandHound [61] to generate an unbiased and unpredictable randomness, which is used to allocate members and select the leader. On the basis of ByzCoin [57], OmniLedger proposes ByzCoinX with larger shard size to resolve the BFT-based 1% attack in sharding.Figure 5
Shard validator assignment of OmniLedger.(1) Randomness Generation: Combination of VRF and RandHound. OmniLedger combines RandHound [61] to propose a scalable bias-resistant distributed randomness generator to maintain the system availability and robustness, in which the publicly VSS (PVSS) [62] is applied to share the secret offline in advance. Furthermore, ByzCoinX introduces the Schnorr Signature [63] to reduce the communication complexity.In particular, a VRF-based algorithm [60] is used for leader selection among participating validators randomly as follows:(3)ℛe,view,i,proofe,view,i=VRFconfige‖view,ski,where confige denotes the predefined settings of the genesis block; view denotes a view in Δ; ℛe,view,i represents the decided randomness; and proofe,view,i represents the specific proof with epoch e and view for validator i.(2) Consensus Algorithm: ByzCoinX. ByzCoin [57] proposes a hybrid scalable consensus protocol based on PoW and BFT, which implements a tree structure with signature collection to improve scalability. Compared with ByzCoin, ByzCoinX has lower latency and more robust fault tolerance for sharding. In particular, ByzCoinX implements a fixed three-depth shallow tree with an increased branching factor, generates the randomness at the beginning of current epoch and uses it to select the group leader, and then allocates the remaining validators to each group. Each group leader is responsible for managing a fixed number of members and forming a subtree according to the members. In addition, the group leader will maintain their roles until the next view occurs, thereby eliminating the shifting window and the difference between key blocks and micro-blocks. After aggregating more than 2/3 signatures from subtrees or leaves, the leader sends the signatures to the root node. Similarly, if at least 2/3 signatures are received, the decision in the root node can be finalized.However, as the number of validators increases and exceeds the threshold, the tree branching keeps increasing, and ByzCoin will outperform ByzCoinX in terms of latency. Furthermore, ByzCoinX improves the scalability by achieving an approximate1.5% failure probability with Fx;m,p=F50;145,0.25 and 1% communication overhead with F340;1000,0.3 by sacrificing transaction efficiency in large-scale networks. In addition, the combination of VRF and RandHound relies on the randomness initiated by the third party in the genesis block. There will be a fallback to inefficient solutions in an asynchronous network, which limits the scalability that RandHound can guarantee.


#### 4.1.4. RapidChain: BFT-Based

To minimize the failure probability without sacrificing transaction efficiency, RapidChain [27] generates unbiased randomness by implementing the distributed random generation (DRG) protocol based on VSS [64]. RapidChain introduces a random graph to eliminate the third-party randomness limitation problem, which can guarantee a certain proportion (around 50%) of malicious validators [27].(1) Randomness Generation: VSS-Based DRG Protocol. For fairness, RapidChain only introduces a basic VSS that shares scheme into DRG protocol to (re)allocate the participating validators to different shards.(2) Consensus Algorithm:50% BFT with Pipelining. In addition, RapidChain claims to increase the fault tolerance of the intrashard consensus up to 50% with a smaller shard size [65].In particular, in each round of the consensus phase, each committee uses the epoch randomness to select a leader who collects transactions from the clients and packs them into blocksℬi. The leader uses the information dispersal algorithm gossip (IDA-Gossip) protocol to broadcast ℬi and creates a block header Hi containing the Merkle tree and the number of rounds. The committee members initiate a consensus protocol for the header Hi. In particular, the leader adds a proposed tag to the header Hi and broadcasts Hi through the gossip network. After receiving Hi, each node responds to and adds an echo tag to Hi, which is also broadcasted through the gossip network. If nodes see a different version of Hi, it means that the leader is malicious and they can reject it by gossiping a message with tag pending. On the contrary, if nodes receive more than m/2+1 echoes and there is only one version of Hi, it means that the committee has reached a consensus on block ℬi, and they accept the header gossiping and add an accept tag and a proof to Hi.In addition, RapidChain proposes the pipeline processing to re-propose the pending blocks along with the new block for improving throughput. As shown in Figure6, Hi is proposed in the iteration i, and if a new proposed block is replied with m/2+1 votes, it can be considered secure.Figure 6
A synchronous BFT-based consensus protocol implemented by RapidChain.According to (1), the50% BFT in RapidChain achieves a 1.5% failure probability with Fx;m,p=F18;35,0.33 and 1% communication overhead with F50;100,0.40.RapidChain prevents the BFT-based1% attack and achieves 50% fault tolerance in intrashard consensus, differing from ByzCoinX in OmniLedger, which is suitable for small-sized shards. However, it is conceivable that the scheduled scheme that defines the timeout has not been proven to be sufficiently synchronized to run the 50% BFT of the pipeline.


#### 4.1.5. Chainspace: BFT-Based

Chainspace implements the optimal PBFT in the proposed S-BAC protocol, called ModSMaRt [66]. However, it ignores the issue of 1% attack for scale PBFT and only decouples the communication and consensus process and at the same time reduces the consensus overhead by introducing a Validated and Provable Consensus protocol. However, Chainspace does not improve the high failure probability in intrashard consensus. Furthermore, the detail of randomness generator and leader selection is not provided.


#### 4.1.6. Ethereum 2.0: BFT-Based PoS

Since 2014, Ethereum, as the second largest decentralized blockchain platform after Bitcoin, is the first to develop smart contracts to conduct transactions automatically, which is considered to be a Turing complete programming language (Blockchain 2.0).With the gradually increasing transactions, the demand for high throughput increases. Shasper that sharding based on Casper FFG is proposed [67] to support Ethereum mainnet (Ethereum 1.0, the PoW-based single-chain architecture) to migrate to the new architecture (Ethereum 2.0, as shown in Figure 7) securely and stably. In particular, we mainly discuss Shasper on testnet and the intrashard consensus protocol, as well as the cross-shard transaction atomicity, because the other subprotocols have not yet been finalized.Figure 7
Ethereum 2.0.(1) Randomness Generation: Combination of RANDAO and VDF. For generating randomness, Shasper combines RANDAO [68] and verifiable delay function (VDF) [69]. RANDAO is implemented through smart contracts on the beacon chain, which mainly contains three functions:(i)
Commit(): if all participating validators have deposited at least 32ETH, they will select a seedℛ and run a VDF as follows:(4)VDFℛi=ℋℋℋ…ℋℛi,where the iteration number of Hash() exceeds10,000. As much, some malicious manipulation can be significantly prevented.(ii)
Reveal(): the local seedℛ of validators can be revealed through smart contract and be verified that whether it matches up with the commitment:(5)ℋ−1ℋ−1…ℋ−1VDFℛi.(iii)
Generate(): a randomness is generated by merging allℛi, and the validators that fail to reveal their own seeds in time will be punished.However,n times ℋ⋅ in VDF incurs a significant computation overhead of On. Furthermore, the overall security is reduced due to the gas limit and malicious seed.(2) Consensus Algorithm: Solving the Intrashard Consensus in a Global Way. To address 1% attack, Shasper applies the BFT-based algorithm to sharding, which decouples consensus process and node allocation. If a node wants to become a validator, it must deposit 32 ETH in an on-chain official contract. Having received the deposit, the beacon chain registers this node as a valid validator, which manages the validator pool. The validator needs to bet on the block in each round, while evaluating which block the other nodes will bet. If right, it can get the margin back plus the block bonus and gas fees for intrablock transactions. Otherwise, it can only get the margin back. Any malicious behaviors will be severely punished by the beacon chain. Due to the possible economic loss, the validator will choose to bet on the most favourable result. When the number of validators is enough, the betting algorithm ensures that the final result distribution tends to converge. Most of the validators will choose a high probability winning block as the eventual consistency result.Considering that the previous shift of ETH miner from PoW node to PoS verification node may be lower than expected, Shasper is a hybrid mining scheme that overlaying the existing PoW with PoS, providing more flexible allocation for intrashard consensus. In particular, it remains the PoW mining until the PoS protocol is formally stabilized, but verification of PoS nodes will be triggered when every 50 blocks are generated, which allows some members of the community to participate in the testing of the new PoS chain, until the community makes a smooth transition to a pure PoS mainnet.


#### 4.1.7. TEEChain: PBFT-Based in TEE

At present, most of the existing methods are to scale blockchain from the aspects of algorithms, protocols (software), etc. Later, some researchers improve the throughput and security from the perspective of hardware. The typical one is TEEChain [26] that is shown in Figure 8, which leverages the trusted execution environment (TEE) that combines with PBFT to eliminate equivocation.Figure 8
TEE-based PBFT in TEEChain.(1) Randomness Generation: Combination of TEE and VDF. TEEChain works in different epochs (e.g., an epoch of 24 h), and each committee is dynamically shuffled at the beginning of each epoch. For preventing the attacker from selectively discarding the TEE output, leading to bias in random number generation, the TEE enclave can only be called once in each epoch. At the beginning of each epoch e, TEEChain performs the following steps to generate a random seed ℛ that is uniform across the network:(i)
Generate two random numbersq and rnd(ii)
Ifq is zero, the node generates a signing certificate that contains e,rnd and broadcasts it to all other nodes(iii)
After waiting the time ofΔ, lock the smallest collected rnd(iv)
Use the minimumrnd as the random seed ℛ allocated by the committees for the current epochOnce each node has the samernd, it is possible to determine which committee a node belongs to. If the value of q that generated by all nodes is not equal to zero, that is, the certificate cannot be generated. Then, the epoch e is increased and the above steps are re-executed.To ensure security, it is possible to tolerate up tom−1/2 nonequivocating Byzantine failures. Without equivocation, existing BFT protocols can achieve higher fault tolerance with the same number of nodes. In particular, the log stored in TEE can help prevent the attacker from tampering. TEE provides the proof of operations containing the signatures, which are required to accompany all valid messages.In addition, there are two functions for processing in SGX (a TEE product): SGX_READ_RAND and SGX_GET_TRUSTED_TIME, which are used to generate unbiased random numbers and a timestamp, respectively, for realizing the assignment of committee members.However, TEEChain relies too much on TEE in the process of randomness generation and consensus. If TEE fails, the blow to the system will be devastating.


### 4.2. Cross-Shard Transaction Atomicity

It is necessary to support cross-shard transactions and verification for a sharding mechanism. Therefore, some solutions [27, 28] propose to apply an individual global root chain to perform transaction verification, but if some additional measures are missing, the root chain cannot natively support cross-shard transactions. Therefore, the demand for cross-shard transaction security outweighs a naive communication protocol without supporting cross-shard protocol to achieve a higher improving factor N. However, it is challenging to guarantee the data atomicity across multiple shards for supporting a cross-shard transaction protocol.This section focuses on discussing and comparing the cross-shard atomicity protocols in the considered sharding mechanisms.


#### 4.2.1. Monoxide-Relay Transactions

Monoxide proposes an asynchronous execution method, eventual atomicity, to bypass the overhead of state locking or unlocking, which decouples a single transaction into an initiated transaction and a relay transaction; the latter is added to the outbound transaction set. In this way, each consensus group can achieve efficient throughput without blocking each other. Eventual atomicity is not immediate atomicity, but a lock-free design. In particular, Chu-ko-nu mining algorithm is applied to maximize the global throughput in an asynchronous network.As shown in Figure9, a cross-shard payment transaction is generated that x tokens are transferred from user A to user B in different shards, which are decoupled into an initiate Tx and a relay Tx. In particular, the transaction that A transfers x tokens to B is successfully packaged, and then, relay Tx is used to transfer the tokens to shard b across shards.Figure 9
Monoxide atomicity.In addition, transfers and receipts are represented as withdrawal and deposit operations, respectively, to guarantee the atomicity. As long as the withdrawal operation is confirmed, the deposit operation will eventually be confirmed. Therefore, Monoxide can achieve an improving factor ofN=n/2.The uncertainty of cross-shard transactions in the originated shard and destination shard may result in additional transaction latency and replay.


#### 4.2.2. Elastico-No Cross-Shard Transactions

Elastico applies the traditional PBFT consensus algorithm to select the leader in a shard, who confirms and transfers an agreement on local transactions to the final committee. After reaching consensus, the leader generates the final global block and broadcasts it to all validators and then adds it to the chain. All other validators can retrieve and verify these transactions. On the other hand, Elastico does not consider cross-shard transaction and fails to ensure transaction atomicity.


#### 4.2.3. OmniLedger-Atomix Protocol

OmniLedger proposes a secure client-driven cross-shard transaction protocol (utilizing secure BFT shards) to ensure atomicity, which shifts the communication overhead outside the shards. As shown in Figure10, the clients act as a gateway to support intershard messages exchange without direct communication between shards. The procedures are as follows:(i)
Initialize: a client creates a UTXO-based cross-shard transaction with two inputs and one output, and gossips the transaction to all input shards.(ii)
Lock: the shard leaders receive the cross-shard transaction from the client and create a proof of acceptance or a proof of rejection attached with the corresponding signatures according to UTXOs, to show that the verification result is successful or failed, respectively. If successful, the UTXOs will be locked in all shards of inputs.(iii)
Unlock: the client issues an unlock to commit consisting of the attached proof of acceptance and the locked cross-shard transaction and then gossips it to output shards after receiving all proof of acceptance from all input shards. Output shards will verify the transaction and store it in the local ledger. If a proof of rejection is returned, the client issues the state from unlock to abort and helps those input shards issuing a proof of acceptance to unlock the account.Figure 10
Atomicity protocol of OmniLedger.Consequently, the Atomix protocol in OmniLedger can achieve an improving factor ofN=n/2. Besides, when the entire network is involved, it can achieve the worse improving factor of N=1.OmniLedger ensures the UTXO transaction security by relying on a coordinated client. However, if the client is malicious, the client driver protocol will be blocked indefinitely, and the payer’s funds may be locked forever. Furthermore, the extra overhead is inevitable for the client.


#### 4.2.4. RapidChain: Transaction Routing

OmniLedger guarantees the atomicity of transaction processing. Still, it also has the following apparent shortcomings: first, the client needs to broadcast the transactions to the entire network, and at least one proof is generated and submitted for each transaction, causing a lot of communication overhead. Another problem is that the system relies too much on the client and requires the client to understand the entire network structure, which violates the principle of light client.Differing from OmniLedger, RapidChain weakens the function of the client, who no longer needs to request asset proof from each input committee, nor does it need to understand the entire network. It only needs to send a transaction to any committee, and then, the transaction will be routed to the output committees through the intercommittee routing protocol.If a cross-shard transaction Tx is generated with two inputsIn1 and In2 and one output Out3, as shown in Figure 11, which belong to different shard committees Shard1, Shard2, and Shard3, then the leader of the output committee will create three new transactions Tx1, Tx2, and Tx3, as follows:(i)
Tx1 transforms the input In1 from Shard1 into the output Out1 of Shard3(ii)
Tx2 transforms the input In2 from Shard2 into the output Out2 of Shard3(iii)
Through the above two transactions, all inputs and outputs belong to the same shard and then create a transactionTx3 with the fact that the input is the output of Tx1 and Tx2 and the output is the same as the original transactionFigure 11
Atomicity protocol of RapidChain.The leader of the output committee will sendTx1 and Tx2 to Shard1 and Shard2, respectively, through the intercommittee routing protocol. The leaders of Shard1 and Shard2 will verify the validity of the corresponding transaction. If valid, they will add the transaction to the local ledger and reply to Shard3. The leader in Shard3 will add Tx3 to the local ledger after receiving all replies from the input committees.Consequently, there are two types of transactions involved in the throughput, as shown by theT at the bottom of Figure 11; thus, it can achieve an improving factor of N=n/2.The RapidChain routing protocol draws on the design ideas of the Kademlia routing algorithm. Simply put, each node stores the routing information of all nodes of the same committee member and only stores the information of thelog2log2n nodes in the log2n committees closest to the committee where it belongs, significantly reducing communication overhead. However, if the specific routing table is polluted, the eclipse attack [70] will be concerned.


#### 4.2.5. Chainspace: The Interpart of S-BAC

The Sharded Byzantine Atomic Commit (S-BAC) Protocol proposes an optimal PBFT algorithm to achieve intrashard consensus and ensure atomicity. In particular, the elected shard leader that works as a BFT initiator is responsible for ensuring the cross-shard transaction atomicity. In this way, Chainspace composes the interpart of S-BAC.Similar to OmniLedger, the key optimization in the BFT consensus process must be carried out, rather than reply on a simple client-oriented model. There are three same procedures involved in RapidChain, including initialize, lock, and unlock, with the same security problem. On one hand,T involves only one input and no output; thus, the improving factor is N=n. On the other hand, when T involves all objects, the improving factor can be N=1.


#### 4.2.6. Ethereum 2.0: Receipt-Based

Ethereum 2.0 applies the beacon chain to ensure cross-shard transaction atomicity. Differing from UTXO-based blockchain, only users with registered accounts can conduct transactions in Ethereum 2.0, while cross-shard transaction supported by smart contracts have not yet been implemented and released until now.According to the primary transaction in Ethereum 2.0, Shasper can achieve an improving factor ofN=n/3.Shasper applies accepted transaction receipts to verify and record the operation validity. In addition, involved validators can conduct cross-validation to obtain the operation results. According to the identities involved in receipts, the cross-shard transactions can be divided into many sub-transactions being executed in different shards, respectively. The idea of receipts is similar to the synchronous locking/unlocking scheme in OmniLedger and RapidChain, while the receipt plays the fundamental role of locking.


#### 4.2.7. TEEChain: 2PC and 2PL

After analyzing the shortcomings of OmniLedger and RapidChain, TEEChain proposes the two-phase commit (2PC) and two-phase locking (2PL) protocol to achieve the cross-shard transaction communication between committees, while satisfying isolation and atomicity. The communication between committees is divided into three steps, namely prepare, pre-commit, and commit. Ref represents the reference committee acting as a coordinator in the two-phase commit, which consists of a group of nodes and runs PBFT to reach a consensus on transactions.S1, S2, and S3 are the committees (shards) involved in this transaction.Concretely, the reference committee implements a simple state machine for 2PC, as shown in Figure12; when a transaction BeginTx is initialized by the client and sent to the reference committee, there are three procedures as follows:(i)
Prepare: once the Ref receives BeginTx, the state machine transitions to the started state. The nodes in the Ref send PrepareTx message to committees in different shards, and each shard committee executes PrepareTx and reaches a consensus on PrepareTx. If the consensus is reached and the transaction has been locked, the nodes in each shard committee will send a PrepareOK message to the Ref.(ii)
Precommit: after the state machine transitions to the started state, the reference committee Ref will create a counter to count the number of PrepareOK messages from different shards. Then, the state machine transitions to the preparing state during this process. Once it receives the PrepareNotOK message, the state machine transitions to the aborted state. Otherwise, when the counter reaches the counting threshold (count=0), the state machine transitions to the committed state.(iii)
Commit: if the state machine transitions to the committed state, the nodes in Ref can broadcast the CommitTx message to all shards. Otherwise, the transaction will be discarded.Figure 12
Atomicity protocol of TEEChain.From the above three procedures, it can be seen that a temporary agreement for transaction submission is reached in the first stage (prepare and pre-commit), and the transaction between shards is actually submitted in the second stage (commit). Similar to RapidChain, TEEChain can achieve an improving factor ofN=n/2. Furthermore, based on the assumption of TEEChain, the BFT-based protocol running in Ref achieves liveness. However, the reference committee can be a bottleneck in cross-shard transaction processing.


### 4.3. General Improvements

This section has listed several general improvements in the considered sharding mechanisms for the critical technical challenges. These solutions can usually be implemented to solve the new problems caused by sharding to the entire system.


#### 4.3.1. Reducing Transaction Latency

Users are sensitive to the waiting latency in the final transaction confirmation. To solve the BFT-based1% attack, OmniLedger and Ethereum 2.0 implement a scalable BFT consensus. RapidChain increases the fault tolerance within a single shard, while remaining the issue of transaction latency.According to the evaluation shown in Ref. [28, 57], the transaction latency deteriorates because the scalable BFT consensus solves 1% attack by increasing the shard size. Thus, OmniLedger proposes a two-level trust-but-verify transaction validation scheme to get low latency and high throughput, providing the real-time transaction confirmation within each shard, which is the same as Ethereum 2.0, as shown in Figure 13. Concretely, the validators are split into two groups of optimistic validators and core validators. To verify transactions in parallel, the optimistic group is further divided into multiple subgroups with several validators. Subsequently, the core validators conduct the second verification and determine whether there are inconsistent and malicious transactions. If none, the transactions can be stored in the shard ledger. However, optimistic validators may still suffer 1% attack after being grouped, and the real-time transaction is achieved at the expense of security, similar to IOTA [11], which can be applied in specific scenarios with lower security requirements.Figure 13
Two-level trust-but-verify validation scheme.Since the nonscalable50% BFT-based consensus will incur more considerable communication overhead to increase the transaction latency, thus, under a 50% consensus, only the block summary is agreed. RapidChain implements a gossip protocol based on an information dispersal algorithm (IDA) [71, 72] to reduce transaction latency. In particular, the initial message sent by the sender is split into n fragments. An α,β erasure coding scheme is proposed to encode the β fragments to α fragments. By querying neighbors for β fragments, other nodes can reconstruct the initial message, thereby significantly reducing the communication latency.


#### 4.3.2. Intershard Communication Protocol

The intershard communication protocol is different from the atomicity protocol that focuses on cross-shard transactions atomicity. It aims to reduce the data transmission overhead among shards. The first type of sharding mechanism, including Monoxide, Elastico, and Ethereum 2.0, implements a global root chain to transfer messages, where each validator needs to store the entire chain. The second type of sharding mechanism, including OmniLedger and Chainspace, applies the full-mesh connection mechanism to improve the communication efficiency by simplifying the communication process.Inspired by the Kademlia-based routing algorithm [73], RapidChain establishes a routing table and proposes a novel intershard communication protocol to decrease communication overhead caused by the full-mesh connection, where each validator only stores the routing information of the closest log2log2n nodes in the log2n committees, instead of all nodes in the network.


#### 4.3.3. Shard Ledger Pruning

Most existing blockchain systems support a single-chain structure [1, 5, 74]. To improve communication efficiency and reduce the computational overhead of data audition and verification, they tend to require validators to store a full version of the ledger. However, for a sharding system, this will bring an unacceptable storage overhead to the validators. Therefore, OmniLedger prunes the shard ledger by applying state blocks (SBs) similar to the fixed checkpoint in PBFT [50] to aggregate all the states of the sharding ledger. To create a state block SBj,e in shard j at the epoch e, the validator performs the following steps:(i)
The leader of the shardj saves the UTXO to a sorted Merkle tree at the end of epoch e and stores the root hash in the header of the state block SBj,e.(ii)
The shard validator runs a consensus on the header (note that each validator can construct the same sorted Merkle tree for validation).(iii)
If the consensus is successful, the leader will pass the block header and save it into the ledger, so thatSBj,e becomes the genesis block of epoch e+1.(iv)
Finally, UTXO inSBj,e can be safely discarded. To create a proof of transaction, we retain the normal blocks of epoch e until the end of epoch e+1.Furthermore, to avoid downtime, all validators in the epoche+1 shard need to include an empty state block as a substitute at the beginning of each epoch. However, such state block design can face the same client security problem like that in OmniLedger and Ethereum 1.0.


#### 4.3.4. Decentralized Bootstrapping

The randomness generator involved in sharding is responsible for randomly generating an initial set of nodes that can participate in intrashard consensus, while ensuring that honest nodes account for the majority in the initial set.Therefore, RapidChain uses a random seed to establish a sampler graph election network for supporting decentralized bootstrapping, where validators are uniformly assigned to several groups. Each member calculates the PoW-based result and its identity ID according to the random number generated by the DRG protocol based on VSS [27]. As shown in Figure 14, a subgroup can be obtained from each group. When this process is iterated, a unique root group can be made up of more than 50% honest validators. Therefore, the communication overhead can be reduced from Ot2 to Ott, where t represents the total number of validators.Figure 14
Election network.


#### 4.3.5. Epoch Reconfiguration

Shards in blockchain are vulnerable to partition attacks; that is, within a single shard, offline or malicious nodes exceed the tolerable ratio, or the protocol cannot be performed normally. In severe cases, wrong information may be recorded on the ledger. Therefore, new validators must be reallocated to other shards in each epoch to prevent attacks from slowly adaptive adversaries.The committee reconfiguration method of Elastico is to dismantle all committee nodes and reelect all committees, but this method has two fatal disadvantages: first, the reelection of all committees incurs more overhead and takes a longer time, resulting in the failure to significantly improve the performance of the sharding system; second, if the nodes are constantly disrupted, it is difficult to maintain an independent ledger for each committee. Since the original intention of state sharding is to store the ledger separately in the shards to reduce storage space, however, it is obvious that the method of all disruption and reconfiguration cannot achieve the desired effect.Ethereum 2.0 frequently updates the intrashard consensus members and requires each validator to track the status for speeding up the reconfiguration phase. A random arrangement scheme is implemented by OmniLedger to replace the validators in each shard to ensure that the number of validators exchanged at a given time is limited byk=logt/n. New registered validators in the global blockchain are randomly allocated to different shards. The number of honest validators is enough to reach a consensus, and the throughput is improved. However, such solution incurs a larger latency, which makes the 24-hour epoch not suitable for highly adaptive adversaries.On the other hand, RapidChain integrates cuckoo rule [75, 76] to propose a lightweight reconfiguration protocol, named bounded cuckoo rule, which only allows a certain number of validators to exchange among committees after each epoch. In particular, the reference committee divides committees into two categories: active committees with a majority of active members and inactive committees with a majority of inactive members. When a new node joins, the reference committee randomly adds the node to an active committee and allocates a fixed number of nodes in the current committee to different inactive committees. This scheme incurs less overhead and supports a more frequent committee reconfiguration to suit more highly adaptive adversaries.


## 4.1. Intrashard Consensus Protocol Security

Sharding technology improves throughput at the expense of security, making blockchain systems more vulnerable to attacks.In the traditional PoW consensus mechanism, due to the total mining powerP, it is difficult for a single entity to control the whole network by dominating more than 50% network mining power. After sharding the network (assuming n shards), although throughput increases, the network mining power is thus distributed into the different shards. A single shard is more vulnerable to be attacked than the entire network, because ideally a malicious node would only need to control about P/n×50% mining power to manipulate the entire shard. As the scale of sharding increases, the situation will continue to deteriorate, which is why the PoW consensus mechanism is not suitable for the intrashard consensus.Different from PoW-based consensus mechanisms, the BFT-based consensus mechanism is considered to be more effective in dealing with the abovementioned attacks. However, such design also introduces other problems as follows:(i)
Randomness generation: generating an unpredictable and unbiasable randomness is important for the sharding scheme independently in permissionless blockchains, which can be used for (1) validator allocation and (2) leader selection at the beginning of each epoch, meanwhile (3) determining the transmission route of a cross-shard transaction, etc. In this way, a strictly selected randomness is effectively used to prevent attackers from biasing the node allocation and controlling the leader election in a shard.(ii)
Shard size: the shard size is proportional to the strength of attack resistance for the BFT-based consensus algorithms. To improve security, the shard size should be increased as much as possible. However, an excessively high shard size will seriously affect the transaction throughput, resulting in greater overhead due to complex communication. We use the binomial distribution function to describe as follows:(1)Fx;m,p=PX≤x=∑i=0xmipi1−pm−i,F^x;m,p=1−Fx;m,p,whereX represents an event that a malicious miner is randomly picked; m denotes the shard size; x indicates the number of malicious members in a shard; and p denotes the global fault tolerance. Note that Fx;m,p is suggested to be larger than 99% [57], while it requires m>143, which will significantly reduce the efficiency of traditional BFT-based consensus algorithm.Next, we discuss and compare the considered intrashard consensus mechanisms, including Monoxide, Elastico, OmniLedger, RapidChain, Chainspace, Ethereum 2.0, and TEEChain.


### 4.1.1. Monoxide: PoW-Based Chu-Ko-Nu Mining

Monoxide is the first to combine Chu-ko-nu mining with PoW-based algorithm for achieving intrashard consensus and solving the problem of computing power being diluted after partitioning, which makes attacking a single shard as difficult as attacking the entire system, where a Merkle Patricia tree (MPT) [5] is used to store all proposed blocks from multiple shards.Chu-ko-nu mining is inspired by merged mining [58], which applies the PoW-based consensus and adopts a parent-child chain to share mining power. The parent chain with total mining power can protect these child chains with relatively smaller mining power from being attacked. Furthermore, an MPT root is involved to store all proposed blocks from different shards. Furthermore, the factor of k can be used to amplify the mining power; when k⟶n, the effective mining power that contributed by shards can achieve Pk/n≃P to address 1% attack.In particular, the consensus algorithm in Monoxide is described as follows:(2)ℋφ‖ℋH‖MPTM≤ϵ,where ℋ represents the hash function; φ indicates the random nonce; H denotes the block header content; MPTM represents the MPT root that aggregated by ℬ0,ℬ1,…,ℬn−1 of each involved shard; and ϵ denotes the PoW target difficulty. φ, identities, and relay transactions are involved in each block.Chu-ko-nu mining algorithm allows miners in any shard to generate multiple blocks when successfully solving the hash puzzle, but at most one block in each shard. In this way, the computing power of miners in each shard is amplified, so that the same level of computing power is required to attack a single shard as attacking the entire system.Monoxide requires most miners in each shard to conduct Chu-ko-nu mining (i.e.,k=n) to meet Pk/n≃P. Because scattered mining power may not guarantee the security of a single shard, on the other hand, it could result in overconcentration of mining power and generate additional overhead.


### 4.1.2. Elastico: BFT-Based

As shown in Figure4, Elastico is the first to implement an intrashard BFT-based consensus protocol. In particular, Elastico allocates validators to different shards according to the least significant bits generated by the random solutions at the beginning of each epoch and then runs a classical Byzantine agreement protocol for intrashard consensus. Members agree and sign on one valid data block, and valid blocks have 2m/3+1 signatures.Figure 4
Node allocation of Elastico.(1) Randomness Generation: A Decentralized Commit-And-Xor Scheme. This scheme is proposed to generate the randomness used in the mining process, which allows different random numbers picked by nodes to achieve unbiased and verifiably random. Each final committee member picks a random seed Ri and broadcasts the hash value ℋRi to other committee members, and these members reach an agreement on a single set of hash values S and broadcast it to the entire network. Note that S must contain at least 2m/3 signatures (m denotes the size of the final committee). Each final member broadcasts the selected Ri, and other nodes in the network will receive at least 2m/3 and at most 3m/2Ri−ℋRi pairs from the final committee members and discard the unmatched Ri−ℋRi pairs. The final randomness can be finalized by randomly picking m/2+1 pairs from the remaining matched Ri−ℋRi pairs for an XOR operation.(2) Consensus Algorithm: Restrictions of PBFT in Sharding. According to the experimental results in Ref. [59], the transaction failure probability of Elastico is close to 8% with Fx;m,p=F6;16,0.25. When the network scale is expanded to 100 shards m=100, it still incurs a 2.76% failure probability, which may be the bottleneck [28] to hinder Elastico from being practically applied. On the other hand, OmniLedger and RapidChain claim greatly improve this problem.


### 4.1.3. OmniLedger: BFT-Based

As shown in Figure5, to resolve the bottleneck of Elastico, OmniLedger combines verifiable random function (VRF) [60] and RandHound [61] to generate an unbiased and unpredictable randomness, which is used to allocate members and select the leader. On the basis of ByzCoin [57], OmniLedger proposes ByzCoinX with larger shard size to resolve the BFT-based 1% attack in sharding.Figure 5
Shard validator assignment of OmniLedger.(1) Randomness Generation: Combination of VRF and RandHound. OmniLedger combines RandHound [61] to propose a scalable bias-resistant distributed randomness generator to maintain the system availability and robustness, in which the publicly VSS (PVSS) [62] is applied to share the secret offline in advance. Furthermore, ByzCoinX introduces the Schnorr Signature [63] to reduce the communication complexity.In particular, a VRF-based algorithm [60] is used for leader selection among participating validators randomly as follows:(3)ℛe,view,i,proofe,view,i=VRFconfige‖view,ski,where confige denotes the predefined settings of the genesis block; view denotes a view in Δ; ℛe,view,i represents the decided randomness; and proofe,view,i represents the specific proof with epoch e and view for validator i.(2) Consensus Algorithm: ByzCoinX. ByzCoin [57] proposes a hybrid scalable consensus protocol based on PoW and BFT, which implements a tree structure with signature collection to improve scalability. Compared with ByzCoin, ByzCoinX has lower latency and more robust fault tolerance for sharding. In particular, ByzCoinX implements a fixed three-depth shallow tree with an increased branching factor, generates the randomness at the beginning of current epoch and uses it to select the group leader, and then allocates the remaining validators to each group. Each group leader is responsible for managing a fixed number of members and forming a subtree according to the members. In addition, the group leader will maintain their roles until the next view occurs, thereby eliminating the shifting window and the difference between key blocks and micro-blocks. After aggregating more than 2/3 signatures from subtrees or leaves, the leader sends the signatures to the root node. Similarly, if at least 2/3 signatures are received, the decision in the root node can be finalized.However, as the number of validators increases and exceeds the threshold, the tree branching keeps increasing, and ByzCoin will outperform ByzCoinX in terms of latency. Furthermore, ByzCoinX improves the scalability by achieving an approximate1.5% failure probability with Fx;m,p=F50;145,0.25 and 1% communication overhead with F340;1000,0.3 by sacrificing transaction efficiency in large-scale networks. In addition, the combination of VRF and RandHound relies on the randomness initiated by the third party in the genesis block. There will be a fallback to inefficient solutions in an asynchronous network, which limits the scalability that RandHound can guarantee.


### 4.1.4. RapidChain: BFT-Based

To minimize the failure probability without sacrificing transaction efficiency, RapidChain [27] generates unbiased randomness by implementing the distributed random generation (DRG) protocol based on VSS [64]. RapidChain introduces a random graph to eliminate the third-party randomness limitation problem, which can guarantee a certain proportion (around 50%) of malicious validators [27].(1) Randomness Generation: VSS-Based DRG Protocol. For fairness, RapidChain only introduces a basic VSS that shares scheme into DRG protocol to (re)allocate the participating validators to different shards.(2) Consensus Algorithm:50% BFT with Pipelining. In addition, RapidChain claims to increase the fault tolerance of the intrashard consensus up to 50% with a smaller shard size [65].In particular, in each round of the consensus phase, each committee uses the epoch randomness to select a leader who collects transactions from the clients and packs them into blocksℬi. The leader uses the information dispersal algorithm gossip (IDA-Gossip) protocol to broadcast ℬi and creates a block header Hi containing the Merkle tree and the number of rounds. The committee members initiate a consensus protocol for the header Hi. In particular, the leader adds a proposed tag to the header Hi and broadcasts Hi through the gossip network. After receiving Hi, each node responds to and adds an echo tag to Hi, which is also broadcasted through the gossip network. If nodes see a different version of Hi, it means that the leader is malicious and they can reject it by gossiping a message with tag pending. On the contrary, if nodes receive more than m/2+1 echoes and there is only one version of Hi, it means that the committee has reached a consensus on block ℬi, and they accept the header gossiping and add an accept tag and a proof to Hi.In addition, RapidChain proposes the pipeline processing to re-propose the pending blocks along with the new block for improving throughput. As shown in Figure6, Hi is proposed in the iteration i, and if a new proposed block is replied with m/2+1 votes, it can be considered secure.Figure 6
A synchronous BFT-based consensus protocol implemented by RapidChain.According to (1), the50% BFT in RapidChain achieves a 1.5% failure probability with Fx;m,p=F18;35,0.33 and 1% communication overhead with F50;100,0.40.RapidChain prevents the BFT-based1% attack and achieves 50% fault tolerance in intrashard consensus, differing from ByzCoinX in OmniLedger, which is suitable for small-sized shards. However, it is conceivable that the scheduled scheme that defines the timeout has not been proven to be sufficiently synchronized to run the 50% BFT of the pipeline.


### 4.1.5. Chainspace: BFT-Based

Chainspace implements the optimal PBFT in the proposed S-BAC protocol, called ModSMaRt [66]. However, it ignores the issue of 1% attack for scale PBFT and only decouples the communication and consensus process and at the same time reduces the consensus overhead by introducing a Validated and Provable Consensus protocol. However, Chainspace does not improve the high failure probability in intrashard consensus. Furthermore, the detail of randomness generator and leader selection is not provided.


### 4.1.6. Ethereum 2.0: BFT-Based PoS

Since 2014, Ethereum, as the second largest decentralized blockchain platform after Bitcoin, is the first to develop smart contracts to conduct transactions automatically, which is considered to be a Turing complete programming language (Blockchain 2.0).With the gradually increasing transactions, the demand for high throughput increases. Shasper that sharding based on Casper FFG is proposed [67] to support Ethereum mainnet (Ethereum 1.0, the PoW-based single-chain architecture) to migrate to the new architecture (Ethereum 2.0, as shown in Figure 7) securely and stably. In particular, we mainly discuss Shasper on testnet and the intrashard consensus protocol, as well as the cross-shard transaction atomicity, because the other subprotocols have not yet been finalized.Figure 7
Ethereum 2.0.(1) Randomness Generation: Combination of RANDAO and VDF. For generating randomness, Shasper combines RANDAO [68] and verifiable delay function (VDF) [69]. RANDAO is implemented through smart contracts on the beacon chain, which mainly contains three functions:(i)
Commit(): if all participating validators have deposited at least 32ETH, they will select a seedℛ and run a VDF as follows:(4)VDFℛi=ℋℋℋ…ℋℛi,where the iteration number of Hash() exceeds10,000. As much, some malicious manipulation can be significantly prevented.(ii)
Reveal(): the local seedℛ of validators can be revealed through smart contract and be verified that whether it matches up with the commitment:(5)ℋ−1ℋ−1…ℋ−1VDFℛi.(iii)
Generate(): a randomness is generated by merging allℛi, and the validators that fail to reveal their own seeds in time will be punished.However,n times ℋ⋅ in VDF incurs a significant computation overhead of On. Furthermore, the overall security is reduced due to the gas limit and malicious seed.(2) Consensus Algorithm: Solving the Intrashard Consensus in a Global Way. To address 1% attack, Shasper applies the BFT-based algorithm to sharding, which decouples consensus process and node allocation. If a node wants to become a validator, it must deposit 32 ETH in an on-chain official contract. Having received the deposit, the beacon chain registers this node as a valid validator, which manages the validator pool. The validator needs to bet on the block in each round, while evaluating which block the other nodes will bet. If right, it can get the margin back plus the block bonus and gas fees for intrablock transactions. Otherwise, it can only get the margin back. Any malicious behaviors will be severely punished by the beacon chain. Due to the possible economic loss, the validator will choose to bet on the most favourable result. When the number of validators is enough, the betting algorithm ensures that the final result distribution tends to converge. Most of the validators will choose a high probability winning block as the eventual consistency result.Considering that the previous shift of ETH miner from PoW node to PoS verification node may be lower than expected, Shasper is a hybrid mining scheme that overlaying the existing PoW with PoS, providing more flexible allocation for intrashard consensus. In particular, it remains the PoW mining until the PoS protocol is formally stabilized, but verification of PoS nodes will be triggered when every 50 blocks are generated, which allows some members of the community to participate in the testing of the new PoS chain, until the community makes a smooth transition to a pure PoS mainnet.


### 4.1.7. TEEChain: PBFT-Based in TEE

At present, most of the existing methods are to scale blockchain from the aspects of algorithms, protocols (software), etc. Later, some researchers improve the throughput and security from the perspective of hardware. The typical one is TEEChain [26] that is shown in Figure 8, which leverages the trusted execution environment (TEE) that combines with PBFT to eliminate equivocation.Figure 8
TEE-based PBFT in TEEChain.(1) Randomness Generation: Combination of TEE and VDF. TEEChain works in different epochs (e.g., an epoch of 24 h), and each committee is dynamically shuffled at the beginning of each epoch. For preventing the attacker from selectively discarding the TEE output, leading to bias in random number generation, the TEE enclave can only be called once in each epoch. At the beginning of each epoch e, TEEChain performs the following steps to generate a random seed ℛ that is uniform across the network:(i)
Generate two random numbersq and rnd(ii)
Ifq is zero, the node generates a signing certificate that contains e,rnd and broadcasts it to all other nodes(iii)
After waiting the time ofΔ, lock the smallest collected rnd(iv)
Use the minimumrnd as the random seed ℛ allocated by the committees for the current epochOnce each node has the samernd, it is possible to determine which committee a node belongs to. If the value of q that generated by all nodes is not equal to zero, that is, the certificate cannot be generated. Then, the epoch e is increased and the above steps are re-executed.To ensure security, it is possible to tolerate up tom−1/2 nonequivocating Byzantine failures. Without equivocation, existing BFT protocols can achieve higher fault tolerance with the same number of nodes. In particular, the log stored in TEE can help prevent the attacker from tampering. TEE provides the proof of operations containing the signatures, which are required to accompany all valid messages.In addition, there are two functions for processing in SGX (a TEE product): SGX_READ_RAND and SGX_GET_TRUSTED_TIME, which are used to generate unbiased random numbers and a timestamp, respectively, for realizing the assignment of committee members.However, TEEChain relies too much on TEE in the process of randomness generation and consensus. If TEE fails, the blow to the system will be devastating.


## 4.1.1. Monoxide: PoW-Based Chu-Ko-Nu Mining

Monoxide is the first to combine Chu-ko-nu mining with PoW-based algorithm for achieving intrashard consensus and solving the problem of computing power being diluted after partitioning, which makes attacking a single shard as difficult as attacking the entire system, where a Merkle Patricia tree (MPT) [5] is used to store all proposed blocks from multiple shards.Chu-ko-nu mining is inspired by merged mining [58], which applies the PoW-based consensus and adopts a parent-child chain to share mining power. The parent chain with total mining power can protect these child chains with relatively smaller mining power from being attacked. Furthermore, an MPT root is involved to store all proposed blocks from different shards. Furthermore, the factor of k can be used to amplify the mining power; when k⟶n, the effective mining power that contributed by shards can achieve Pk/n≃P to address 1% attack.In particular, the consensus algorithm in Monoxide is described as follows:(2)ℋφ‖ℋH‖MPTM≤ϵ,where ℋ represents the hash function; φ indicates the random nonce; H denotes the block header content; MPTM represents the MPT root that aggregated by ℬ0,ℬ1,…,ℬn−1 of each involved shard; and ϵ denotes the PoW target difficulty. φ, identities, and relay transactions are involved in each block.Chu-ko-nu mining algorithm allows miners in any shard to generate multiple blocks when successfully solving the hash puzzle, but at most one block in each shard. In this way, the computing power of miners in each shard is amplified, so that the same level of computing power is required to attack a single shard as attacking the entire system.Monoxide requires most miners in each shard to conduct Chu-ko-nu mining (i.e.,k=n) to meet Pk/n≃P. Because scattered mining power may not guarantee the security of a single shard, on the other hand, it could result in overconcentration of mining power and generate additional overhead.


## 4.1.2. Elastico: BFT-Based

As shown in Figure4, Elastico is the first to implement an intrashard BFT-based consensus protocol. In particular, Elastico allocates validators to different shards according to the least significant bits generated by the random solutions at the beginning of each epoch and then runs a classical Byzantine agreement protocol for intrashard consensus. Members agree and sign on one valid data block, and valid blocks have 2m/3+1 signatures.Figure 4
Node allocation of Elastico.(1) Randomness Generation: A Decentralized Commit-And-Xor Scheme. This scheme is proposed to generate the randomness used in the mining process, which allows different random numbers picked by nodes to achieve unbiased and verifiably random. Each final committee member picks a random seed Ri and broadcasts the hash value ℋRi to other committee members, and these members reach an agreement on a single set of hash values S and broadcast it to the entire network. Note that S must contain at least 2m/3 signatures (m denotes the size of the final committee). Each final member broadcasts the selected Ri, and other nodes in the network will receive at least 2m/3 and at most 3m/2Ri−ℋRi pairs from the final committee members and discard the unmatched Ri−ℋRi pairs. The final randomness can be finalized by randomly picking m/2+1 pairs from the remaining matched Ri−ℋRi pairs for an XOR operation.(2) Consensus Algorithm: Restrictions of PBFT in Sharding. According to the experimental results in Ref. [59], the transaction failure probability of Elastico is close to 8% with Fx;m,p=F6;16,0.25. When the network scale is expanded to 100 shards m=100, it still incurs a 2.76% failure probability, which may be the bottleneck [28] to hinder Elastico from being practically applied. On the other hand, OmniLedger and RapidChain claim greatly improve this problem.


## 4.1.3. OmniLedger: BFT-Based

As shown in Figure5, to resolve the bottleneck of Elastico, OmniLedger combines verifiable random function (VRF) [60] and RandHound [61] to generate an unbiased and unpredictable randomness, which is used to allocate members and select the leader. On the basis of ByzCoin [57], OmniLedger proposes ByzCoinX with larger shard size to resolve the BFT-based 1% attack in sharding.Figure 5
Shard validator assignment of OmniLedger.(1) Randomness Generation: Combination of VRF and RandHound. OmniLedger combines RandHound [61] to propose a scalable bias-resistant distributed randomness generator to maintain the system availability and robustness, in which the publicly VSS (PVSS) [62] is applied to share the secret offline in advance. Furthermore, ByzCoinX introduces the Schnorr Signature [63] to reduce the communication complexity.In particular, a VRF-based algorithm [60] is used for leader selection among participating validators randomly as follows:(3)ℛe,view,i,proofe,view,i=VRFconfige‖view,ski,where confige denotes the predefined settings of the genesis block; view denotes a view in Δ; ℛe,view,i represents the decided randomness; and proofe,view,i represents the specific proof with epoch e and view for validator i.(2) Consensus Algorithm: ByzCoinX. ByzCoin [57] proposes a hybrid scalable consensus protocol based on PoW and BFT, which implements a tree structure with signature collection to improve scalability. Compared with ByzCoin, ByzCoinX has lower latency and more robust fault tolerance for sharding. In particular, ByzCoinX implements a fixed three-depth shallow tree with an increased branching factor, generates the randomness at the beginning of current epoch and uses it to select the group leader, and then allocates the remaining validators to each group. Each group leader is responsible for managing a fixed number of members and forming a subtree according to the members. In addition, the group leader will maintain their roles until the next view occurs, thereby eliminating the shifting window and the difference between key blocks and micro-blocks. After aggregating more than 2/3 signatures from subtrees or leaves, the leader sends the signatures to the root node. Similarly, if at least 2/3 signatures are received, the decision in the root node can be finalized.However, as the number of validators increases and exceeds the threshold, the tree branching keeps increasing, and ByzCoin will outperform ByzCoinX in terms of latency. Furthermore, ByzCoinX improves the scalability by achieving an approximate1.5% failure probability with Fx;m,p=F50;145,0.25 and 1% communication overhead with F340;1000,0.3 by sacrificing transaction efficiency in large-scale networks. In addition, the combination of VRF and RandHound relies on the randomness initiated by the third party in the genesis block. There will be a fallback to inefficient solutions in an asynchronous network, which limits the scalability that RandHound can guarantee.


## 4.1.4. RapidChain: BFT-Based

To minimize the failure probability without sacrificing transaction efficiency, RapidChain [27] generates unbiased randomness by implementing the distributed random generation (DRG) protocol based on VSS [64]. RapidChain introduces a random graph to eliminate the third-party randomness limitation problem, which can guarantee a certain proportion (around 50%) of malicious validators [27].(1) Randomness Generation: VSS-Based DRG Protocol. For fairness, RapidChain only introduces a basic VSS that shares scheme into DRG protocol to (re)allocate the participating validators to different shards.(2) Consensus Algorithm:50% BFT with Pipelining. In addition, RapidChain claims to increase the fault tolerance of the intrashard consensus up to 50% with a smaller shard size [65].In particular, in each round of the consensus phase, each committee uses the epoch randomness to select a leader who collects transactions from the clients and packs them into blocksℬi. The leader uses the information dispersal algorithm gossip (IDA-Gossip) protocol to broadcast ℬi and creates a block header Hi containing the Merkle tree and the number of rounds. The committee members initiate a consensus protocol for the header Hi. In particular, the leader adds a proposed tag to the header Hi and broadcasts Hi through the gossip network. After receiving Hi, each node responds to and adds an echo tag to Hi, which is also broadcasted through the gossip network. If nodes see a different version of Hi, it means that the leader is malicious and they can reject it by gossiping a message with tag pending. On the contrary, if nodes receive more than m/2+1 echoes and there is only one version of Hi, it means that the committee has reached a consensus on block ℬi, and they accept the header gossiping and add an accept tag and a proof to Hi.In addition, RapidChain proposes the pipeline processing to re-propose the pending blocks along with the new block for improving throughput. As shown in Figure6, Hi is proposed in the iteration i, and if a new proposed block is replied with m/2+1 votes, it can be considered secure.Figure 6
A synchronous BFT-based consensus protocol implemented by RapidChain.According to (1), the50% BFT in RapidChain achieves a 1.5% failure probability with Fx;m,p=F18;35,0.33 and 1% communication overhead with F50;100,0.40.RapidChain prevents the BFT-based1% attack and achieves 50% fault tolerance in intrashard consensus, differing from ByzCoinX in OmniLedger, which is suitable for small-sized shards. However, it is conceivable that the scheduled scheme that defines the timeout has not been proven to be sufficiently synchronized to run the 50% BFT of the pipeline.


## 4.1.5. Chainspace: BFT-Based

Chainspace implements the optimal PBFT in the proposed S-BAC protocol, called ModSMaRt [66]. However, it ignores the issue of 1% attack for scale PBFT and only decouples the communication and consensus process and at the same time reduces the consensus overhead by introducing a Validated and Provable Consensus protocol. However, Chainspace does not improve the high failure probability in intrashard consensus. Furthermore, the detail of randomness generator and leader selection is not provided.


## 4.1.6. Ethereum 2.0: BFT-Based PoS

Since 2014, Ethereum, as the second largest decentralized blockchain platform after Bitcoin, is the first to develop smart contracts to conduct transactions automatically, which is considered to be a Turing complete programming language (Blockchain 2.0).With the gradually increasing transactions, the demand for high throughput increases. Shasper that sharding based on Casper FFG is proposed [67] to support Ethereum mainnet (Ethereum 1.0, the PoW-based single-chain architecture) to migrate to the new architecture (Ethereum 2.0, as shown in Figure 7) securely and stably. In particular, we mainly discuss Shasper on testnet and the intrashard consensus protocol, as well as the cross-shard transaction atomicity, because the other subprotocols have not yet been finalized.Figure 7
Ethereum 2.0.(1) Randomness Generation: Combination of RANDAO and VDF. For generating randomness, Shasper combines RANDAO [68] and verifiable delay function (VDF) [69]. RANDAO is implemented through smart contracts on the beacon chain, which mainly contains three functions:(i)
Commit(): if all participating validators have deposited at least 32ETH, they will select a seedℛ and run a VDF as follows:(4)VDFℛi=ℋℋℋ…ℋℛi,where the iteration number of Hash() exceeds10,000. As much, some malicious manipulation can be significantly prevented.(ii)
Reveal(): the local seedℛ of validators can be revealed through smart contract and be verified that whether it matches up with the commitment:(5)ℋ−1ℋ−1…ℋ−1VDFℛi.(iii)
Generate(): a randomness is generated by merging allℛi, and the validators that fail to reveal their own seeds in time will be punished.However,n times ℋ⋅ in VDF incurs a significant computation overhead of On. Furthermore, the overall security is reduced due to the gas limit and malicious seed.(2) Consensus Algorithm: Solving the Intrashard Consensus in a Global Way. To address 1% attack, Shasper applies the BFT-based algorithm to sharding, which decouples consensus process and node allocation. If a node wants to become a validator, it must deposit 32 ETH in an on-chain official contract. Having received the deposit, the beacon chain registers this node as a valid validator, which manages the validator pool. The validator needs to bet on the block in each round, while evaluating which block the other nodes will bet. If right, it can get the margin back plus the block bonus and gas fees for intrablock transactions. Otherwise, it can only get the margin back. Any malicious behaviors will be severely punished by the beacon chain. Due to the possible economic loss, the validator will choose to bet on the most favourable result. When the number of validators is enough, the betting algorithm ensures that the final result distribution tends to converge. Most of the validators will choose a high probability winning block as the eventual consistency result.Considering that the previous shift of ETH miner from PoW node to PoS verification node may be lower than expected, Shasper is a hybrid mining scheme that overlaying the existing PoW with PoS, providing more flexible allocation for intrashard consensus. In particular, it remains the PoW mining until the PoS protocol is formally stabilized, but verification of PoS nodes will be triggered when every 50 blocks are generated, which allows some members of the community to participate in the testing of the new PoS chain, until the community makes a smooth transition to a pure PoS mainnet.


## 4.1.7. TEEChain: PBFT-Based in TEE

At present, most of the existing methods are to scale blockchain from the aspects of algorithms, protocols (software), etc. Later, some researchers improve the throughput and security from the perspective of hardware. The typical one is TEEChain [26] that is shown in Figure 8, which leverages the trusted execution environment (TEE) that combines with PBFT to eliminate equivocation.Figure 8
TEE-based PBFT in TEEChain.(1) Randomness Generation: Combination of TEE and VDF. TEEChain works in different epochs (e.g., an epoch of 24 h), and each committee is dynamically shuffled at the beginning of each epoch. For preventing the attacker from selectively discarding the TEE output, leading to bias in random number generation, the TEE enclave can only be called once in each epoch. At the beginning of each epoch e, TEEChain performs the following steps to generate a random seed ℛ that is uniform across the network:(i)
Generate two random numbersq and rnd(ii)
Ifq is zero, the node generates a signing certificate that contains e,rnd and broadcasts it to all other nodes(iii)
After waiting the time ofΔ, lock the smallest collected rnd(iv)
Use the minimumrnd as the random seed ℛ allocated by the committees for the current epochOnce each node has the samernd, it is possible to determine which committee a node belongs to. If the value of q that generated by all nodes is not equal to zero, that is, the certificate cannot be generated. Then, the epoch e is increased and the above steps are re-executed.To ensure security, it is possible to tolerate up tom−1/2 nonequivocating Byzantine failures. Without equivocation, existing BFT protocols can achieve higher fault tolerance with the same number of nodes. In particular, the log stored in TEE can help prevent the attacker from tampering. TEE provides the proof of operations containing the signatures, which are required to accompany all valid messages.In addition, there are two functions for processing in SGX (a TEE product): SGX_READ_RAND and SGX_GET_TRUSTED_TIME, which are used to generate unbiased random numbers and a timestamp, respectively, for realizing the assignment of committee members.However, TEEChain relies too much on TEE in the process of randomness generation and consensus. If TEE fails, the blow to the system will be devastating.


## 4.2. Cross-Shard Transaction Atomicity

It is necessary to support cross-shard transactions and verification for a sharding mechanism. Therefore, some solutions [27, 28] propose to apply an individual global root chain to perform transaction verification, but if some additional measures are missing, the root chain cannot natively support cross-shard transactions. Therefore, the demand for cross-shard transaction security outweighs a naive communication protocol without supporting cross-shard protocol to achieve a higher improving factor N. However, it is challenging to guarantee the data atomicity across multiple shards for supporting a cross-shard transaction protocol.This section focuses on discussing and comparing the cross-shard atomicity protocols in the considered sharding mechanisms.


### 4.2.1. Monoxide-Relay Transactions

Monoxide proposes an asynchronous execution method, eventual atomicity, to bypass the overhead of state locking or unlocking, which decouples a single transaction into an initiated transaction and a relay transaction; the latter is added to the outbound transaction set. In this way, each consensus group can achieve efficient throughput without blocking each other. Eventual atomicity is not immediate atomicity, but a lock-free design. In particular, Chu-ko-nu mining algorithm is applied to maximize the global throughput in an asynchronous network.As shown in Figure9, a cross-shard payment transaction is generated that x tokens are transferred from user A to user B in different shards, which are decoupled into an initiate Tx and a relay Tx. In particular, the transaction that A transfers x tokens to B is successfully packaged, and then, relay Tx is used to transfer the tokens to shard b across shards.Figure 9
Monoxide atomicity.In addition, transfers and receipts are represented as withdrawal and deposit operations, respectively, to guarantee the atomicity. As long as the withdrawal operation is confirmed, the deposit operation will eventually be confirmed. Therefore, Monoxide can achieve an improving factor ofN=n/2.The uncertainty of cross-shard transactions in the originated shard and destination shard may result in additional transaction latency and replay.


### 4.2.2. Elastico-No Cross-Shard Transactions

Elastico applies the traditional PBFT consensus algorithm to select the leader in a shard, who confirms and transfers an agreement on local transactions to the final committee. After reaching consensus, the leader generates the final global block and broadcasts it to all validators and then adds it to the chain. All other validators can retrieve and verify these transactions. On the other hand, Elastico does not consider cross-shard transaction and fails to ensure transaction atomicity.


### 4.2.3. OmniLedger-Atomix Protocol

OmniLedger proposes a secure client-driven cross-shard transaction protocol (utilizing secure BFT shards) to ensure atomicity, which shifts the communication overhead outside the shards. As shown in Figure10, the clients act as a gateway to support intershard messages exchange without direct communication between shards. The procedures are as follows:(i)
Initialize: a client creates a UTXO-based cross-shard transaction with two inputs and one output, and gossips the transaction to all input shards.(ii)
Lock: the shard leaders receive the cross-shard transaction from the client and create a proof of acceptance or a proof of rejection attached with the corresponding signatures according to UTXOs, to show that the verification result is successful or failed, respectively. If successful, the UTXOs will be locked in all shards of inputs.(iii)
Unlock: the client issues an unlock to commit consisting of the attached proof of acceptance and the locked cross-shard transaction and then gossips it to output shards after receiving all proof of acceptance from all input shards. Output shards will verify the transaction and store it in the local ledger. If a proof of rejection is returned, the client issues the state from unlock to abort and helps those input shards issuing a proof of acceptance to unlock the account.Figure 10
Atomicity protocol of OmniLedger.Consequently, the Atomix protocol in OmniLedger can achieve an improving factor ofN=n/2. Besides, when the entire network is involved, it can achieve the worse improving factor of N=1.OmniLedger ensures the UTXO transaction security by relying on a coordinated client. However, if the client is malicious, the client driver protocol will be blocked indefinitely, and the payer’s funds may be locked forever. Furthermore, the extra overhead is inevitable for the client.


### 4.2.4. RapidChain: Transaction Routing

OmniLedger guarantees the atomicity of transaction processing. Still, it also has the following apparent shortcomings: first, the client needs to broadcast the transactions to the entire network, and at least one proof is generated and submitted for each transaction, causing a lot of communication overhead. Another problem is that the system relies too much on the client and requires the client to understand the entire network structure, which violates the principle of light client.Differing from OmniLedger, RapidChain weakens the function of the client, who no longer needs to request asset proof from each input committee, nor does it need to understand the entire network. It only needs to send a transaction to any committee, and then, the transaction will be routed to the output committees through the intercommittee routing protocol.If a cross-shard transaction Tx is generated with two inputsIn1 and In2 and one output Out3, as shown in Figure 11, which belong to different shard committees Shard1, Shard2, and Shard3, then the leader of the output committee will create three new transactions Tx1, Tx2, and Tx3, as follows:(i)
Tx1 transforms the input In1 from Shard1 into the output Out1 of Shard3(ii)
Tx2 transforms the input In2 from Shard2 into the output Out2 of Shard3(iii)
Through the above two transactions, all inputs and outputs belong to the same shard and then create a transactionTx3 with the fact that the input is the output of Tx1 and Tx2 and the output is the same as the original transactionFigure 11
Atomicity protocol of RapidChain.The leader of the output committee will sendTx1 and Tx2 to Shard1 and Shard2, respectively, through the intercommittee routing protocol. The leaders of Shard1 and Shard2 will verify the validity of the corresponding transaction. If valid, they will add the transaction to the local ledger and reply to Shard3. The leader in Shard3 will add Tx3 to the local ledger after receiving all replies from the input committees.Consequently, there are two types of transactions involved in the throughput, as shown by theT at the bottom of Figure 11; thus, it can achieve an improving factor of N=n/2.The RapidChain routing protocol draws on the design ideas of the Kademlia routing algorithm. Simply put, each node stores the routing information of all nodes of the same committee member and only stores the information of thelog2log2n nodes in the log2n committees closest to the committee where it belongs, significantly reducing communication overhead. However, if the specific routing table is polluted, the eclipse attack [70] will be concerned.


### 4.2.5. Chainspace: The Interpart of S-BAC

The Sharded Byzantine Atomic Commit (S-BAC) Protocol proposes an optimal PBFT algorithm to achieve intrashard consensus and ensure atomicity. In particular, the elected shard leader that works as a BFT initiator is responsible for ensuring the cross-shard transaction atomicity. In this way, Chainspace composes the interpart of S-BAC.Similar to OmniLedger, the key optimization in the BFT consensus process must be carried out, rather than reply on a simple client-oriented model. There are three same procedures involved in RapidChain, including initialize, lock, and unlock, with the same security problem. On one hand,T involves only one input and no output; thus, the improving factor is N=n. On the other hand, when T involves all objects, the improving factor can be N=1.


### 4.2.6. Ethereum 2.0: Receipt-Based

Ethereum 2.0 applies the beacon chain to ensure cross-shard transaction atomicity. Differing from UTXO-based blockchain, only users with registered accounts can conduct transactions in Ethereum 2.0, while cross-shard transaction supported by smart contracts have not yet been implemented and released until now.According to the primary transaction in Ethereum 2.0, Shasper can achieve an improving factor ofN=n/3.Shasper applies accepted transaction receipts to verify and record the operation validity. In addition, involved validators can conduct cross-validation to obtain the operation results. According to the identities involved in receipts, the cross-shard transactions can be divided into many sub-transactions being executed in different shards, respectively. The idea of receipts is similar to the synchronous locking/unlocking scheme in OmniLedger and RapidChain, while the receipt plays the fundamental role of locking.


### 4.2.7. TEEChain: 2PC and 2PL

After analyzing the shortcomings of OmniLedger and RapidChain, TEEChain proposes the two-phase commit (2PC) and two-phase locking (2PL) protocol to achieve the cross-shard transaction communication between committees, while satisfying isolation and atomicity. The communication between committees is divided into three steps, namely prepare, pre-commit, and commit. Ref represents the reference committee acting as a coordinator in the two-phase commit, which consists of a group of nodes and runs PBFT to reach a consensus on transactions.S1, S2, and S3 are the committees (shards) involved in this transaction.Concretely, the reference committee implements a simple state machine for 2PC, as shown in Figure12; when a transaction BeginTx is initialized by the client and sent to the reference committee, there are three procedures as follows:(i)
Prepare: once the Ref receives BeginTx, the state machine transitions to the started state. The nodes in the Ref send PrepareTx message to committees in different shards, and each shard committee executes PrepareTx and reaches a consensus on PrepareTx. If the consensus is reached and the transaction has been locked, the nodes in each shard committee will send a PrepareOK message to the Ref.(ii)
Precommit: after the state machine transitions to the started state, the reference committee Ref will create a counter to count the number of PrepareOK messages from different shards. Then, the state machine transitions to the preparing state during this process. Once it receives the PrepareNotOK message, the state machine transitions to the aborted state. Otherwise, when the counter reaches the counting threshold (count=0), the state machine transitions to the committed state.(iii)
Commit: if the state machine transitions to the committed state, the nodes in Ref can broadcast the CommitTx message to all shards. Otherwise, the transaction will be discarded.Figure 12
Atomicity protocol of TEEChain.From the above three procedures, it can be seen that a temporary agreement for transaction submission is reached in the first stage (prepare and pre-commit), and the transaction between shards is actually submitted in the second stage (commit). Similar to RapidChain, TEEChain can achieve an improving factor ofN=n/2. Furthermore, based on the assumption of TEEChain, the BFT-based protocol running in Ref achieves liveness. However, the reference committee can be a bottleneck in cross-shard transaction processing.


## 4.2.1. Monoxide-Relay Transactions

Monoxide proposes an asynchronous execution method, eventual atomicity, to bypass the overhead of state locking or unlocking, which decouples a single transaction into an initiated transaction and a relay transaction; the latter is added to the outbound transaction set. In this way, each consensus group can achieve efficient throughput without blocking each other. Eventual atomicity is not immediate atomicity, but a lock-free design. In particular, Chu-ko-nu mining algorithm is applied to maximize the global throughput in an asynchronous network.As shown in Figure9, a cross-shard payment transaction is generated that x tokens are transferred from user A to user B in different shards, which are decoupled into an initiate Tx and a relay Tx. In particular, the transaction that A transfers x tokens to B is successfully packaged, and then, relay Tx is used to transfer the tokens to shard b across shards.Figure 9
Monoxide atomicity.In addition, transfers and receipts are represented as withdrawal and deposit operations, respectively, to guarantee the atomicity. As long as the withdrawal operation is confirmed, the deposit operation will eventually be confirmed. Therefore, Monoxide can achieve an improving factor ofN=n/2.The uncertainty of cross-shard transactions in the originated shard and destination shard may result in additional transaction latency and replay.


## 4.2.2. Elastico-No Cross-Shard Transactions

Elastico applies the traditional PBFT consensus algorithm to select the leader in a shard, who confirms and transfers an agreement on local transactions to the final committee. After reaching consensus, the leader generates the final global block and broadcasts it to all validators and then adds it to the chain. All other validators can retrieve and verify these transactions. On the other hand, Elastico does not consider cross-shard transaction and fails to ensure transaction atomicity.


## 4.2.3. OmniLedger-Atomix Protocol

OmniLedger proposes a secure client-driven cross-shard transaction protocol (utilizing secure BFT shards) to ensure atomicity, which shifts the communication overhead outside the shards. As shown in Figure10, the clients act as a gateway to support intershard messages exchange without direct communication between shards. The procedures are as follows:(i)
Initialize: a client creates a UTXO-based cross-shard transaction with two inputs and one output, and gossips the transaction to all input shards.(ii)
Lock: the shard leaders receive the cross-shard transaction from the client and create a proof of acceptance or a proof of rejection attached with the corresponding signatures according to UTXOs, to show that the verification result is successful or failed, respectively. If successful, the UTXOs will be locked in all shards of inputs.(iii)
Unlock: the client issues an unlock to commit consisting of the attached proof of acceptance and the locked cross-shard transaction and then gossips it to output shards after receiving all proof of acceptance from all input shards. Output shards will verify the transaction and store it in the local ledger. If a proof of rejection is returned, the client issues the state from unlock to abort and helps those input shards issuing a proof of acceptance to unlock the account.Figure 10
Atomicity protocol of OmniLedger.Consequently, the Atomix protocol in OmniLedger can achieve an improving factor ofN=n/2. Besides, when the entire network is involved, it can achieve the worse improving factor of N=1.OmniLedger ensures the UTXO transaction security by relying on a coordinated client. However, if the client is malicious, the client driver protocol will be blocked indefinitely, and the payer’s funds may be locked forever. Furthermore, the extra overhead is inevitable for the client.


## 4.2.4. RapidChain: Transaction Routing

OmniLedger guarantees the atomicity of transaction processing. Still, it also has the following apparent shortcomings: first, the client needs to broadcast the transactions to the entire network, and at least one proof is generated and submitted for each transaction, causing a lot of communication overhead. Another problem is that the system relies too much on the client and requires the client to understand the entire network structure, which violates the principle of light client.Differing from OmniLedger, RapidChain weakens the function of the client, who no longer needs to request asset proof from each input committee, nor does it need to understand the entire network. It only needs to send a transaction to any committee, and then, the transaction will be routed to the output committees through the intercommittee routing protocol.If a cross-shard transaction Tx is generated with two inputsIn1 and In2 and one output Out3, as shown in Figure 11, which belong to different shard committees Shard1, Shard2, and Shard3, then the leader of the output committee will create three new transactions Tx1, Tx2, and Tx3, as follows:(i)
Tx1 transforms the input In1 from Shard1 into the output Out1 of Shard3(ii)
Tx2 transforms the input In2 from Shard2 into the output Out2 of Shard3(iii)
Through the above two transactions, all inputs and outputs belong to the same shard and then create a transactionTx3 with the fact that the input is the output of Tx1 and Tx2 and the output is the same as the original transactionFigure 11
Atomicity protocol of RapidChain.The leader of the output committee will sendTx1 and Tx2 to Shard1 and Shard2, respectively, through the intercommittee routing protocol. The leaders of Shard1 and Shard2 will verify the validity of the corresponding transaction. If valid, they will add the transaction to the local ledger and reply to Shard3. The leader in Shard3 will add Tx3 to the local ledger after receiving all replies from the input committees.Consequently, there are two types of transactions involved in the throughput, as shown by theT at the bottom of Figure 11; thus, it can achieve an improving factor of N=n/2.The RapidChain routing protocol draws on the design ideas of the Kademlia routing algorithm. Simply put, each node stores the routing information of all nodes of the same committee member and only stores the information of thelog2log2n nodes in the log2n committees closest to the committee where it belongs, significantly reducing communication overhead. However, if the specific routing table is polluted, the eclipse attack [70] will be concerned.


## 4.2.5. Chainspace: The Interpart of S-BAC

The Sharded Byzantine Atomic Commit (S-BAC) Protocol proposes an optimal PBFT algorithm to achieve intrashard consensus and ensure atomicity. In particular, the elected shard leader that works as a BFT initiator is responsible for ensuring the cross-shard transaction atomicity. In this way, Chainspace composes the interpart of S-BAC.Similar to OmniLedger, the key optimization in the BFT consensus process must be carried out, rather than reply on a simple client-oriented model. There are three same procedures involved in RapidChain, including initialize, lock, and unlock, with the same security problem. On one hand,T involves only one input and no output; thus, the improving factor is N=n. On the other hand, when T involves all objects, the improving factor can be N=1.


## 4.2.6. Ethereum 2.0: Receipt-Based

Ethereum 2.0 applies the beacon chain to ensure cross-shard transaction atomicity. Differing from UTXO-based blockchain, only users with registered accounts can conduct transactions in Ethereum 2.0, while cross-shard transaction supported by smart contracts have not yet been implemented and released until now.According to the primary transaction in Ethereum 2.0, Shasper can achieve an improving factor ofN=n/3.Shasper applies accepted transaction receipts to verify and record the operation validity. In addition, involved validators can conduct cross-validation to obtain the operation results. According to the identities involved in receipts, the cross-shard transactions can be divided into many sub-transactions being executed in different shards, respectively. The idea of receipts is similar to the synchronous locking/unlocking scheme in OmniLedger and RapidChain, while the receipt plays the fundamental role of locking.


## 4.2.7. TEEChain: 2PC and 2PL

After analyzing the shortcomings of OmniLedger and RapidChain, TEEChain proposes the two-phase commit (2PC) and two-phase locking (2PL) protocol to achieve the cross-shard transaction communication between committees, while satisfying isolation and atomicity. The communication between committees is divided into three steps, namely prepare, pre-commit, and commit. Ref represents the reference committee acting as a coordinator in the two-phase commit, which consists of a group of nodes and runs PBFT to reach a consensus on transactions.S1, S2, and S3 are the committees (shards) involved in this transaction.Concretely, the reference committee implements a simple state machine for 2PC, as shown in Figure12; when a transaction BeginTx is initialized by the client and sent to the reference committee, there are three procedures as follows:(i)
Prepare: once the Ref receives BeginTx, the state machine transitions to the started state. The nodes in the Ref send PrepareTx message to committees in different shards, and each shard committee executes PrepareTx and reaches a consensus on PrepareTx. If the consensus is reached and the transaction has been locked, the nodes in each shard committee will send a PrepareOK message to the Ref.(ii)
Precommit: after the state machine transitions to the started state, the reference committee Ref will create a counter to count the number of PrepareOK messages from different shards. Then, the state machine transitions to the preparing state during this process. Once it receives the PrepareNotOK message, the state machine transitions to the aborted state. Otherwise, when the counter reaches the counting threshold (count=0), the state machine transitions to the committed state.(iii)
Commit: if the state machine transitions to the committed state, the nodes in Ref can broadcast the CommitTx message to all shards. Otherwise, the transaction will be discarded.Figure 12
Atomicity protocol of TEEChain.From the above three procedures, it can be seen that a temporary agreement for transaction submission is reached in the first stage (prepare and pre-commit), and the transaction between shards is actually submitted in the second stage (commit). Similar to RapidChain, TEEChain can achieve an improving factor ofN=n/2. Furthermore, based on the assumption of TEEChain, the BFT-based protocol running in Ref achieves liveness. However, the reference committee can be a bottleneck in cross-shard transaction processing.


## 4.3. General Improvements

This section has listed several general improvements in the considered sharding mechanisms for the critical technical challenges. These solutions can usually be implemented to solve the new problems caused by sharding to the entire system.


### 4.3.1. Reducing Transaction Latency

Users are sensitive to the waiting latency in the final transaction confirmation. To solve the BFT-based1% attack, OmniLedger and Ethereum 2.0 implement a scalable BFT consensus. RapidChain increases the fault tolerance within a single shard, while remaining the issue of transaction latency.According to the evaluation shown in Ref. [28, 57], the transaction latency deteriorates because the scalable BFT consensus solves 1% attack by increasing the shard size. Thus, OmniLedger proposes a two-level trust-but-verify transaction validation scheme to get low latency and high throughput, providing the real-time transaction confirmation within each shard, which is the same as Ethereum 2.0, as shown in Figure 13. Concretely, the validators are split into two groups of optimistic validators and core validators. To verify transactions in parallel, the optimistic group is further divided into multiple subgroups with several validators. Subsequently, the core validators conduct the second verification and determine whether there are inconsistent and malicious transactions. If none, the transactions can be stored in the shard ledger. However, optimistic validators may still suffer 1% attack after being grouped, and the real-time transaction is achieved at the expense of security, similar to IOTA [11], which can be applied in specific scenarios with lower security requirements.Figure 13
Two-level trust-but-verify validation scheme.Since the nonscalable50% BFT-based consensus will incur more considerable communication overhead to increase the transaction latency, thus, under a 50% consensus, only the block summary is agreed. RapidChain implements a gossip protocol based on an information dispersal algorithm (IDA) [71, 72] to reduce transaction latency. In particular, the initial message sent by the sender is split into n fragments. An α,β erasure coding scheme is proposed to encode the β fragments to α fragments. By querying neighbors for β fragments, other nodes can reconstruct the initial message, thereby significantly reducing the communication latency.


### 4.3.2. Intershard Communication Protocol

The intershard communication protocol is different from the atomicity protocol that focuses on cross-shard transactions atomicity. It aims to reduce the data transmission overhead among shards. The first type of sharding mechanism, including Monoxide, Elastico, and Ethereum 2.0, implements a global root chain to transfer messages, where each validator needs to store the entire chain. The second type of sharding mechanism, including OmniLedger and Chainspace, applies the full-mesh connection mechanism to improve the communication efficiency by simplifying the communication process.Inspired by the Kademlia-based routing algorithm [73], RapidChain establishes a routing table and proposes a novel intershard communication protocol to decrease communication overhead caused by the full-mesh connection, where each validator only stores the routing information of the closest log2log2n nodes in the log2n committees, instead of all nodes in the network.


### 4.3.3. Shard Ledger Pruning

Most existing blockchain systems support a single-chain structure [1, 5, 74]. To improve communication efficiency and reduce the computational overhead of data audition and verification, they tend to require validators to store a full version of the ledger. However, for a sharding system, this will bring an unacceptable storage overhead to the validators. Therefore, OmniLedger prunes the shard ledger by applying state blocks (SBs) similar to the fixed checkpoint in PBFT [50] to aggregate all the states of the sharding ledger. To create a state block SBj,e in shard j at the epoch e, the validator performs the following steps:(i)
The leader of the shardj saves the UTXO to a sorted Merkle tree at the end of epoch e and stores the root hash in the header of the state block SBj,e.(ii)
The shard validator runs a consensus on the header (note that each validator can construct the same sorted Merkle tree for validation).(iii)
If the consensus is successful, the leader will pass the block header and save it into the ledger, so thatSBj,e becomes the genesis block of epoch e+1.(iv)
Finally, UTXO inSBj,e can be safely discarded. To create a proof of transaction, we retain the normal blocks of epoch e until the end of epoch e+1.Furthermore, to avoid downtime, all validators in the epoche+1 shard need to include an empty state block as a substitute at the beginning of each epoch. However, such state block design can face the same client security problem like that in OmniLedger and Ethereum 1.0.


### 4.3.4. Decentralized Bootstrapping

The randomness generator involved in sharding is responsible for randomly generating an initial set of nodes that can participate in intrashard consensus, while ensuring that honest nodes account for the majority in the initial set.Therefore, RapidChain uses a random seed to establish a sampler graph election network for supporting decentralized bootstrapping, where validators are uniformly assigned to several groups. Each member calculates the PoW-based result and its identity ID according to the random number generated by the DRG protocol based on VSS [27]. As shown in Figure 14, a subgroup can be obtained from each group. When this process is iterated, a unique root group can be made up of more than 50% honest validators. Therefore, the communication overhead can be reduced from Ot2 to Ott, where t represents the total number of validators.Figure 14
Election network.


### 4.3.5. Epoch Reconfiguration

Shards in blockchain are vulnerable to partition attacks; that is, within a single shard, offline or malicious nodes exceed the tolerable ratio, or the protocol cannot be performed normally. In severe cases, wrong information may be recorded on the ledger. Therefore, new validators must be reallocated to other shards in each epoch to prevent attacks from slowly adaptive adversaries.The committee reconfiguration method of Elastico is to dismantle all committee nodes and reelect all committees, but this method has two fatal disadvantages: first, the reelection of all committees incurs more overhead and takes a longer time, resulting in the failure to significantly improve the performance of the sharding system; second, if the nodes are constantly disrupted, it is difficult to maintain an independent ledger for each committee. Since the original intention of state sharding is to store the ledger separately in the shards to reduce storage space, however, it is obvious that the method of all disruption and reconfiguration cannot achieve the desired effect.Ethereum 2.0 frequently updates the intrashard consensus members and requires each validator to track the status for speeding up the reconfiguration phase. A random arrangement scheme is implemented by OmniLedger to replace the validators in each shard to ensure that the number of validators exchanged at a given time is limited byk=logt/n. New registered validators in the global blockchain are randomly allocated to different shards. The number of honest validators is enough to reach a consensus, and the throughput is improved. However, such solution incurs a larger latency, which makes the 24-hour epoch not suitable for highly adaptive adversaries.On the other hand, RapidChain integrates cuckoo rule [75, 76] to propose a lightweight reconfiguration protocol, named bounded cuckoo rule, which only allows a certain number of validators to exchange among committees after each epoch. In particular, the reference committee divides committees into two categories: active committees with a majority of active members and inactive committees with a majority of inactive members. When a new node joins, the reference committee randomly adds the node to an active committee and allocates a fixed number of nodes in the current committee to different inactive committees. This scheme incurs less overhead and supports a more frequent committee reconfiguration to suit more highly adaptive adversaries.


## 4.3.1. Reducing Transaction Latency

Users are sensitive to the waiting latency in the final transaction confirmation. To solve the BFT-based1% attack, OmniLedger and Ethereum 2.0 implement a scalable BFT consensus. RapidChain increases the fault tolerance within a single shard, while remaining the issue of transaction latency.According to the evaluation shown in Ref. [28, 57], the transaction latency deteriorates because the scalable BFT consensus solves 1% attack by increasing the shard size. Thus, OmniLedger proposes a two-level trust-but-verify transaction validation scheme to get low latency and high throughput, providing the real-time transaction confirmation within each shard, which is the same as Ethereum 2.0, as shown in Figure 13. Concretely, the validators are split into two groups of optimistic validators and core validators. To verify transactions in parallel, the optimistic group is further divided into multiple subgroups with several validators. Subsequently, the core validators conduct the second verification and determine whether there are inconsistent and malicious transactions. If none, the transactions can be stored in the shard ledger. However, optimistic validators may still suffer 1% attack after being grouped, and the real-time transaction is achieved at the expense of security, similar to IOTA [11], which can be applied in specific scenarios with lower security requirements.Figure 13
Two-level trust-but-verify validation scheme.Since the nonscalable50% BFT-based consensus will incur more considerable communication overhead to increase the transaction latency, thus, under a 50% consensus, only the block summary is agreed. RapidChain implements a gossip protocol based on an information dispersal algorithm (IDA) [71, 72] to reduce transaction latency. In particular, the initial message sent by the sender is split into n fragments. An α,β erasure coding scheme is proposed to encode the β fragments to α fragments. By querying neighbors for β fragments, other nodes can reconstruct the initial message, thereby significantly reducing the communication latency.


## 4.3.2. Intershard Communication Protocol

The intershard communication protocol is different from the atomicity protocol that focuses on cross-shard transactions atomicity. It aims to reduce the data transmission overhead among shards. The first type of sharding mechanism, including Monoxide, Elastico, and Ethereum 2.0, implements a global root chain to transfer messages, where each validator needs to store the entire chain. The second type of sharding mechanism, including OmniLedger and Chainspace, applies the full-mesh connection mechanism to improve the communication efficiency by simplifying the communication process.Inspired by the Kademlia-based routing algorithm [73], RapidChain establishes a routing table and proposes a novel intershard communication protocol to decrease communication overhead caused by the full-mesh connection, where each validator only stores the routing information of the closest log2log2n nodes in the log2n committees, instead of all nodes in the network.


## 4.3.3. Shard Ledger Pruning

Most existing blockchain systems support a single-chain structure [1, 5, 74]. To improve communication efficiency and reduce the computational overhead of data audition and verification, they tend to require validators to store a full version of the ledger. However, for a sharding system, this will bring an unacceptable storage overhead to the validators. Therefore, OmniLedger prunes the shard ledger by applying state blocks (SBs) similar to the fixed checkpoint in PBFT [50] to aggregate all the states of the sharding ledger. To create a state block SBj,e in shard j at the epoch e, the validator performs the following steps:(i)
The leader of the shardj saves the UTXO to a sorted Merkle tree at the end of epoch e and stores the root hash in the header of the state block SBj,e.(ii)
The shard validator runs a consensus on the header (note that each validator can construct the same sorted Merkle tree for validation).(iii)
If the consensus is successful, the leader will pass the block header and save it into the ledger, so thatSBj,e becomes the genesis block of epoch e+1.(iv)
Finally, UTXO inSBj,e can be safely discarded. To create a proof of transaction, we retain the normal blocks of epoch e until the end of epoch e+1.Furthermore, to avoid downtime, all validators in the epoche+1 shard need to include an empty state block as a substitute at the beginning of each epoch. However, such state block design can face the same client security problem like that in OmniLedger and Ethereum 1.0.


## 4.3.4. Decentralized Bootstrapping

The randomness generator involved in sharding is responsible for randomly generating an initial set of nodes that can participate in intrashard consensus, while ensuring that honest nodes account for the majority in the initial set.Therefore, RapidChain uses a random seed to establish a sampler graph election network for supporting decentralized bootstrapping, where validators are uniformly assigned to several groups. Each member calculates the PoW-based result and its identity ID according to the random number generated by the DRG protocol based on VSS [27]. As shown in Figure 14, a subgroup can be obtained from each group. When this process is iterated, a unique root group can be made up of more than 50% honest validators. Therefore, the communication overhead can be reduced from Ot2 to Ott, where t represents the total number of validators.Figure 14
Election network.


## 4.3.5. Epoch Reconfiguration

Shards in blockchain are vulnerable to partition attacks; that is, within a single shard, offline or malicious nodes exceed the tolerable ratio, or the protocol cannot be performed normally. In severe cases, wrong information may be recorded on the ledger. Therefore, new validators must be reallocated to other shards in each epoch to prevent attacks from slowly adaptive adversaries.The committee reconfiguration method of Elastico is to dismantle all committee nodes and reelect all committees, but this method has two fatal disadvantages: first, the reelection of all committees incurs more overhead and takes a longer time, resulting in the failure to significantly improve the performance of the sharding system; second, if the nodes are constantly disrupted, it is difficult to maintain an independent ledger for each committee. Since the original intention of state sharding is to store the ledger separately in the shards to reduce storage space, however, it is obvious that the method of all disruption and reconfiguration cannot achieve the desired effect.Ethereum 2.0 frequently updates the intrashard consensus members and requires each validator to track the status for speeding up the reconfiguration phase. A random arrangement scheme is implemented by OmniLedger to replace the validators in each shard to ensure that the number of validators exchanged at a given time is limited byk=logt/n. New registered validators in the global blockchain are randomly allocated to different shards. The number of honest validators is enough to reach a consensus, and the throughput is improved. However, such solution incurs a larger latency, which makes the 24-hour epoch not suitable for highly adaptive adversaries.On the other hand, RapidChain integrates cuckoo rule [75, 76] to propose a lightweight reconfiguration protocol, named bounded cuckoo rule, which only allows a certain number of validators to exchange among committees after each epoch. In particular, the reference committee divides committees into two categories: active committees with a majority of active members and inactive committees with a majority of inactive members. When a new node joins, the reference committee randomly adds the node to an active committee and allocates a fixed number of nodes in the current committee to different inactive committees. This scheme incurs less overhead and supports a more frequent committee reconfiguration to suit more highly adaptive adversaries.


## 5. Comprehensive Comparison of State-of-the-Art Sharding Protocols

### 5.1. The Upper Bound of Throughput

In this section, we discuss and provide a comprehensive comparison regarding the above considered sharding mechanisms, ranging from the intrashard consensus protocol security to the cross-shard transaction atomicity, as well as the corresponding overhead. The result is shown in Table2. Due to the poor performance of achieving sharding with smart contracts, Chainspace is not discussed in this section. Instead of considering the individual protocols, we map out the landscape by extracting and evaluating the high-level design themes in the considered blockchain sharding solutions.Referring to Ref. [77, 78], we use local calculate-optimized servers with 200 Mbps bandwidth, 8vCPU of Intel Xeon, and 2 TB disk storage. To fill the bandwidth and conduct comparisons, we select bandwidth as the upper bound and define some parameters and initial values, such as H=500B, Tx=250B, and Sig=65B. Then, we take the size of a single identity by ID=32B.In particular, the calculations of throughput and disk storage are presented as follows.


#### 5.1.1. Monoxide

Monoxide is the sole sharding mechanism that supports PoW algorithm for intrashard consensus. We refer to Ethereum [5] and set ℬ=20KB, T=10s, n=218=262,144, m=128, and h=1,000,000.(i)
Throughput: the intrashard throughput can be calculated byℬ/TxT=8.192tps. By multiplying the intrashard throughput and the improving factor of n/2, the entire network throughput of Monoxide can be calculated. Considering the different mixed/identical targets, the former is calculated by z with n=262,144. The latter is calculated by 8.192n/2=2.048Mtps with n=524,288. Therefore, the throughput of Monoxide is nearly from 1.024Mtps to 2.048Mtps.(ii)
Storage:H, Txs, and Sigs are involved in ℬ; thus, the storage space of ℬ can be calculated by hℬ=Sh=19GB. Furthermore, all participating miners are required by the Chu-ko-nu mining to store all received block headers to ensure security; therefore, much more storage space is needed in Monoxide.


#### 5.1.2. Elastico

Similar to Monoxide, Elastico also requires validators to store all block data globally. In this way, we simply take the intrashard throughput as800tps and set ℬ=800tps×Tx×T+2mSig/3≃1.9MB, where T=10s, n=48, m=26=64, h=1,000,000, and e=10min.(i)
Throughput: by multiplying the intrashard through put and the improving factor ofn, the entire network throughput of Elastico can be calculated by 800n=38.4ktps.(ii)
Storage: Elastico does not consider the ledger pruning scheme. All validators are required to store the global ledger, which involves all blocks from different shards and consumes a huge amount of storage space. The storage can be calculated bynhℬ≃87TB.


#### 5.1.3. OmniLedger

Referring to Ref. [28], we simply take the intrashard throughput in OmniLedger as 1000tps and set ℬ=32MB, n=48, m=1024, h=1,000,000, and e=24hours. Thus, T=ℬ/1000Tx=134s.(i)
Throughput: by multiplying the intrashard throughput and the improving factor ofn/2, the entire network throughput of OmniLedger can be calculated by 1000n/2=24ktps.(ii)
Storage: the identity chain and local pruned chain in each shard cover the storage space in OmniLedger. For the identity chain, the block height is calculated byhT/e=1551; thus, ℬID,1551=1551nmID=2.27GB. On the other hand, an MPT with the aggregated ℬs at the epoch of ek can be constructed to achieve the ledger pruning, and the state block ek+1 is finalized at the end of ek. Validators only need to store the header of each state block, along with ℬs at each epoch. The storage can be calculated by hH+ℬe/T≃20.6GB.


#### 5.1.4. RapidChain

Referring to Ref. [27], we simply take the intrashard throughput in RapidChain as 1000tps and set ℬ=8MB, n=256, m=256, h=1,000,000, and e=24hour. Thus, T=ℬ/1000Tx=33.6s.(i)
Throughput: by multiplying the intrashard throughput and the improving factor ofn/2, the entire network throughput of RapidChain can be calculated by 1000n/2=128ktps.(ii)
Storage: the identity chain in the local routing table and local pruned chain in each shard cover the storage space in RapidChain. The routing table records the identities of all other members in the current committee, as well aslog2log2n validators of other log2n committees, i.e., IDm+IDlog2log2nlog2n=9KB.


#### 5.1.5. Ethereum 2.0

Referring to Ref. [5], we take the number of validators selected in each round (one epoch e contains several rounds) as 10 and set ℬ=1.2MB, T=10s, n=512, m=8, h=1,000,000, and e=1week. In addition, the total number of validators in Shasper is 400 and the interval for checkpoint is 100s.(i)
Throughput: the intrashard throughput can be calculated byℬ/TxT=503tps. By multiplying the intrashard throughput and the improving factor of n/3, the entire network throughput of Ethereum 2.0 can be calculated by 787n/3=86ktps.(ii)
Storage: the PoW-based main chain, the beacon chain, and the local shard chain cover the storage space in Ethereum 2.0. For the main chain, the data involved in Txs will be gradually transferred to the beacon chain for security and storage. The storage space of the current main chain has reached TB level. For the beacon chain,Hcs needs to be stored in each ℬ for all involved shards, and it can be calculated by nhHc=238GB. On the other hand, the identity storage space of all active validators in the beacon chain can be calculated by IDnm=128KB. Furthermore, validators are required to store the current shard ledger, and the storage can be calculated by hℬc=1.14TB.


#### 5.1.6. TEEChain

TEE is applied to design fault-tolerant, scalable consensus protocol and an effective sharding protocol in TEEChain. Refer to Ref. [26], and we simply take the intrashard throughput in TEEChain as 2000tps and set ℬ=2MB, n=16, m=32, h=1,000,000, and e=24hour. Thus, T=ℬ/2000Tx=4.2s.(i)
Throughput: by multiplying the intrashard throughput and the improving factor ofn/2, the entire network throughput of TEEChain can be calculated by 2000n/2=16ktps.(ii)
Storage: TEEChain does not consider the disk storage.


### 5.2. Comparison and Discussion

According to the above calculation, this study provides a comprehensive comparison and the results are shown in Table3.In summary, Monoxide finds a new way of Nakamoto-based consensus and significantly improves the throughput. On the other hand, RapidChain and Ethereum 2.0 outperform Elastico and OmniLedger in transaction throughput and overhead. Furthermore, there is still much room for improvement in the performance of sharding contracts in Chainspace. TEEChain creatively introduces TEE to trade-off security and performance.Concretely, we focus on four aspects: protocol settings, intrashard consensus, cross-shard transaction atomicity, and security and performance. The protocol settings show how the protocols are set up in an overall perspective, such as network model, randomness generation, participant allocation and reconfiguration, and transaction structure. The intrashard consensus and cross-shard transaction have already been described in the previous sections. Finally, we compare their security aspects and the achieved performance, such as communication and storage overhead.


#### 5.2.1. Protocol Settings

The network model shows the synchrony of the underlying communication network. Except for RapidChain, all the other considered sharding mechanisms adopt the partial sync network model. For most solutions, a randomness is generated at different epochs, which is used to complete different stages of work, such as PoW puzzle for next epoch, shard formation, leader selection, decentralized bootstrapping, and epoch reconfiguration. In addition, there are two main transaction structures: UTXO-based and account-based models. In particular, TEEChain implements a general transaction structure.


#### 5.2.2. Intrashard Consensus

The intrashard consensus protocols have been presented in detail in the previous sections. Considering the waste of resources generated by the PoW consensus, most sharding mechanisms use the BFT protocol to achieve intrashard consensus. Through algorithm optimization, RapidChain improves the fault tolerance from1/3 to 50%. Chainspace and Ethereum 2.0 combine the BFT-type protocols with the Nakamoto-type protocols to improve scalability. In particular, TEEChain introduces the trusted execution environment (TEE) to enhance the security of PBFT protocol.


#### 5.2.3. Cross-Shard Transaction Atomicity

Cross-shard transaction is supported in all the considered sharding mechanisms except for Elastico. To ensure the atomicity of blockchain data, most solutions adopt a synchronized lock/unlock scheme to achieve either success or failure of transaction results for all transactions. In particular, TEEChain proposes a two-phase lock and two-phase commit atomicity scheme, which outperforms other schemes.


#### 5.2.4. Security and Performance

For security, we focus on the security model, including the threat model and fault tolerance (FT). The threat model represents the likelihood that the system will be suppressed by a malicious node. The attacker behaves arbitrarily, and most attackers are not cooperating with the system. In addition, the attacker is considered slowly adaptive so that the system is not affected in an epoch. Due to the BFT-type consensus algorithm during the intrashard consensus, the FT generally controls at33%, through the optimization of security algorithms, and the introduction of a TEE can improve FT to a certain extent.


### 5.3. Different from Other Surveys

As far as we know, the current review literature [15, 30, 37] on blockchain sharding does not cover the same issues as we do.Kim et al. [30] discussed the blockchain scalability solutions from four dimensions, including on-chain, off-chain, side chain/child chain, and interchain. However, strictly speaking, these solutions can be divided into on-chain and off-chain solutions. Neither the side chain/child chain nor the interchain solutions have changed the main chain. Furthermore, in view of different solutions, the paper did not propose a more profound theoretical analysis and ignores the more important sharding-based scalability solution. Our work considers the most promising shard-based blockchain scalability solution and provides a three-layer taxonomy and a more detailed comparison of the solutions.Wang et al. [15] emphasized the scalability issues of the current blockchain and put forward the challenges of introducing sharding to blockchain. In view of these challenges, the existing blockchain solutions were analyzed. In particular, they compared five sharding-based blockchain mechanisms. However, they did not provide enough details about security analysis and comparison. On the basis of Ref. [15], we classify existing solutions, focus on several of the most distinctive sharding solutions, and provide a more comprehensive comparison based on detailed theoretical analysis and calculations.Zhou et al. [37] proposed a three-layer architecture to systematically outline the scalability solutions of the blockchain. However, they elaborated on these solutions from a higher level, without showing the details about the specific mechanisms, and there were no analysis and comparison of security and performance among different solutions. In addition, they did not detail shard-based solutions. Instead, we focus on sharding solutions and present seven well-known shard-based blockchain mechanisms. Furthermore, we provide a comprehensive analysis (i.e., latency and throughput) of considered sharding mechanisms.


## 5.1. The Upper Bound of Throughput

In this section, we discuss and provide a comprehensive comparison regarding the above considered sharding mechanisms, ranging from the intrashard consensus protocol security to the cross-shard transaction atomicity, as well as the corresponding overhead. The result is shown in Table2. Due to the poor performance of achieving sharding with smart contracts, Chainspace is not discussed in this section. Instead of considering the individual protocols, we map out the landscape by extracting and evaluating the high-level design themes in the considered blockchain sharding solutions.Referring to Ref. [77, 78], we use local calculate-optimized servers with 200 Mbps bandwidth, 8vCPU of Intel Xeon, and 2 TB disk storage. To fill the bandwidth and conduct comparisons, we select bandwidth as the upper bound and define some parameters and initial values, such as H=500B, Tx=250B, and Sig=65B. Then, we take the size of a single identity by ID=32B.In particular, the calculations of throughput and disk storage are presented as follows.


### 5.1.1. Monoxide

Monoxide is the sole sharding mechanism that supports PoW algorithm for intrashard consensus. We refer to Ethereum [5] and set ℬ=20KB, T=10s, n=218=262,144, m=128, and h=1,000,000.(i)
Throughput: the intrashard throughput can be calculated byℬ/TxT=8.192tps. By multiplying the intrashard throughput and the improving factor of n/2, the entire network throughput of Monoxide can be calculated. Considering the different mixed/identical targets, the former is calculated by z with n=262,144. The latter is calculated by 8.192n/2=2.048Mtps with n=524,288. Therefore, the throughput of Monoxide is nearly from 1.024Mtps to 2.048Mtps.(ii)
Storage:H, Txs, and Sigs are involved in ℬ; thus, the storage space of ℬ can be calculated by hℬ=Sh=19GB. Furthermore, all participating miners are required by the Chu-ko-nu mining to store all received block headers to ensure security; therefore, much more storage space is needed in Monoxide.


### 5.1.2. Elastico

Similar to Monoxide, Elastico also requires validators to store all block data globally. In this way, we simply take the intrashard throughput as800tps and set ℬ=800tps×Tx×T+2mSig/3≃1.9MB, where T=10s, n=48, m=26=64, h=1,000,000, and e=10min.(i)
Throughput: by multiplying the intrashard through put and the improving factor ofn, the entire network throughput of Elastico can be calculated by 800n=38.4ktps.(ii)
Storage: Elastico does not consider the ledger pruning scheme. All validators are required to store the global ledger, which involves all blocks from different shards and consumes a huge amount of storage space. The storage can be calculated bynhℬ≃87TB.


### 5.1.3. OmniLedger

Referring to Ref. [28], we simply take the intrashard throughput in OmniLedger as 1000tps and set ℬ=32MB, n=48, m=1024, h=1,000,000, and e=24hours. Thus, T=ℬ/1000Tx=134s.(i)
Throughput: by multiplying the intrashard throughput and the improving factor ofn/2, the entire network throughput of OmniLedger can be calculated by 1000n/2=24ktps.(ii)
Storage: the identity chain and local pruned chain in each shard cover the storage space in OmniLedger. For the identity chain, the block height is calculated byhT/e=1551; thus, ℬID,1551=1551nmID=2.27GB. On the other hand, an MPT with the aggregated ℬs at the epoch of ek can be constructed to achieve the ledger pruning, and the state block ek+1 is finalized at the end of ek. Validators only need to store the header of each state block, along with ℬs at each epoch. The storage can be calculated by hH+ℬe/T≃20.6GB.


### 5.1.4. RapidChain

Referring to Ref. [27], we simply take the intrashard throughput in RapidChain as 1000tps and set ℬ=8MB, n=256, m=256, h=1,000,000, and e=24hour. Thus, T=ℬ/1000Tx=33.6s.(i)
Throughput: by multiplying the intrashard throughput and the improving factor ofn/2, the entire network throughput of RapidChain can be calculated by 1000n/2=128ktps.(ii)
Storage: the identity chain in the local routing table and local pruned chain in each shard cover the storage space in RapidChain. The routing table records the identities of all other members in the current committee, as well aslog2log2n validators of other log2n committees, i.e., IDm+IDlog2log2nlog2n=9KB.


### 5.1.5. Ethereum 2.0

Referring to Ref. [5], we take the number of validators selected in each round (one epoch e contains several rounds) as 10 and set ℬ=1.2MB, T=10s, n=512, m=8, h=1,000,000, and e=1week. In addition, the total number of validators in Shasper is 400 and the interval for checkpoint is 100s.(i)
Throughput: the intrashard throughput can be calculated byℬ/TxT=503tps. By multiplying the intrashard throughput and the improving factor of n/3, the entire network throughput of Ethereum 2.0 can be calculated by 787n/3=86ktps.(ii)
Storage: the PoW-based main chain, the beacon chain, and the local shard chain cover the storage space in Ethereum 2.0. For the main chain, the data involved in Txs will be gradually transferred to the beacon chain for security and storage. The storage space of the current main chain has reached TB level. For the beacon chain,Hcs needs to be stored in each ℬ for all involved shards, and it can be calculated by nhHc=238GB. On the other hand, the identity storage space of all active validators in the beacon chain can be calculated by IDnm=128KB. Furthermore, validators are required to store the current shard ledger, and the storage can be calculated by hℬc=1.14TB.


### 5.1.6. TEEChain

TEE is applied to design fault-tolerant, scalable consensus protocol and an effective sharding protocol in TEEChain. Refer to Ref. [26], and we simply take the intrashard throughput in TEEChain as 2000tps and set ℬ=2MB, n=16, m=32, h=1,000,000, and e=24hour. Thus, T=ℬ/2000Tx=4.2s.(i)
Throughput: by multiplying the intrashard throughput and the improving factor ofn/2, the entire network throughput of TEEChain can be calculated by 2000n/2=16ktps.(ii)
Storage: TEEChain does not consider the disk storage.


## 5.1.1. Monoxide

Monoxide is the sole sharding mechanism that supports PoW algorithm for intrashard consensus. We refer to Ethereum [5] and set ℬ=20KB, T=10s, n=218=262,144, m=128, and h=1,000,000.(i)
Throughput: the intrashard throughput can be calculated byℬ/TxT=8.192tps. By multiplying the intrashard throughput and the improving factor of n/2, the entire network throughput of Monoxide can be calculated. Considering the different mixed/identical targets, the former is calculated by z with n=262,144. The latter is calculated by 8.192n/2=2.048Mtps with n=524,288. Therefore, the throughput of Monoxide is nearly from 1.024Mtps to 2.048Mtps.(ii)
Storage:H, Txs, and Sigs are involved in ℬ; thus, the storage space of ℬ can be calculated by hℬ=Sh=19GB. Furthermore, all participating miners are required by the Chu-ko-nu mining to store all received block headers to ensure security; therefore, much more storage space is needed in Monoxide.


## 5.1.2. Elastico

Similar to Monoxide, Elastico also requires validators to store all block data globally. In this way, we simply take the intrashard throughput as800tps and set ℬ=800tps×Tx×T+2mSig/3≃1.9MB, where T=10s, n=48, m=26=64, h=1,000,000, and e=10min.(i)
Throughput: by multiplying the intrashard through put and the improving factor ofn, the entire network throughput of Elastico can be calculated by 800n=38.4ktps.(ii)
Storage: Elastico does not consider the ledger pruning scheme. All validators are required to store the global ledger, which involves all blocks from different shards and consumes a huge amount of storage space. The storage can be calculated bynhℬ≃87TB.


## 5.1.3. OmniLedger

Referring to Ref. [28], we simply take the intrashard throughput in OmniLedger as 1000tps and set ℬ=32MB, n=48, m=1024, h=1,000,000, and e=24hours. Thus, T=ℬ/1000Tx=134s.(i)
Throughput: by multiplying the intrashard throughput and the improving factor ofn/2, the entire network throughput of OmniLedger can be calculated by 1000n/2=24ktps.(ii)
Storage: the identity chain and local pruned chain in each shard cover the storage space in OmniLedger. For the identity chain, the block height is calculated byhT/e=1551; thus, ℬID,1551=1551nmID=2.27GB. On the other hand, an MPT with the aggregated ℬs at the epoch of ek can be constructed to achieve the ledger pruning, and the state block ek+1 is finalized at the end of ek. Validators only need to store the header of each state block, along with ℬs at each epoch. The storage can be calculated by hH+ℬe/T≃20.6GB.


## 5.1.4. RapidChain

Referring to Ref. [27], we simply take the intrashard throughput in RapidChain as 1000tps and set ℬ=8MB, n=256, m=256, h=1,000,000, and e=24hour. Thus, T=ℬ/1000Tx=33.6s.(i)
Throughput: by multiplying the intrashard throughput and the improving factor ofn/2, the entire network throughput of RapidChain can be calculated by 1000n/2=128ktps.(ii)
Storage: the identity chain in the local routing table and local pruned chain in each shard cover the storage space in RapidChain. The routing table records the identities of all other members in the current committee, as well aslog2log2n validators of other log2n committees, i.e., IDm+IDlog2log2nlog2n=9KB.


## 5.1.5. Ethereum 2.0

Referring to Ref. [5], we take the number of validators selected in each round (one epoch e contains several rounds) as 10 and set ℬ=1.2MB, T=10s, n=512, m=8, h=1,000,000, and e=1week. In addition, the total number of validators in Shasper is 400 and the interval for checkpoint is 100s.(i)
Throughput: the intrashard throughput can be calculated byℬ/TxT=503tps. By multiplying the intrashard throughput and the improving factor of n/3, the entire network throughput of Ethereum 2.0 can be calculated by 787n/3=86ktps.(ii)
Storage: the PoW-based main chain, the beacon chain, and the local shard chain cover the storage space in Ethereum 2.0. For the main chain, the data involved in Txs will be gradually transferred to the beacon chain for security and storage. The storage space of the current main chain has reached TB level. For the beacon chain,Hcs needs to be stored in each ℬ for all involved shards, and it can be calculated by nhHc=238GB. On the other hand, the identity storage space of all active validators in the beacon chain can be calculated by IDnm=128KB. Furthermore, validators are required to store the current shard ledger, and the storage can be calculated by hℬc=1.14TB.


## 5.1.6. TEEChain

TEE is applied to design fault-tolerant, scalable consensus protocol and an effective sharding protocol in TEEChain. Refer to Ref. [26], and we simply take the intrashard throughput in TEEChain as 2000tps and set ℬ=2MB, n=16, m=32, h=1,000,000, and e=24hour. Thus, T=ℬ/2000Tx=4.2s.(i)
Throughput: by multiplying the intrashard throughput and the improving factor ofn/2, the entire network throughput of TEEChain can be calculated by 2000n/2=16ktps.(ii)
Storage: TEEChain does not consider the disk storage.


## 5.2. Comparison and Discussion

According to the above calculation, this study provides a comprehensive comparison and the results are shown in Table3.In summary, Monoxide finds a new way of Nakamoto-based consensus and significantly improves the throughput. On the other hand, RapidChain and Ethereum 2.0 outperform Elastico and OmniLedger in transaction throughput and overhead. Furthermore, there is still much room for improvement in the performance of sharding contracts in Chainspace. TEEChain creatively introduces TEE to trade-off security and performance.Concretely, we focus on four aspects: protocol settings, intrashard consensus, cross-shard transaction atomicity, and security and performance. The protocol settings show how the protocols are set up in an overall perspective, such as network model, randomness generation, participant allocation and reconfiguration, and transaction structure. The intrashard consensus and cross-shard transaction have already been described in the previous sections. Finally, we compare their security aspects and the achieved performance, such as communication and storage overhead.


### 5.2.1. Protocol Settings

The network model shows the synchrony of the underlying communication network. Except for RapidChain, all the other considered sharding mechanisms adopt the partial sync network model. For most solutions, a randomness is generated at different epochs, which is used to complete different stages of work, such as PoW puzzle for next epoch, shard formation, leader selection, decentralized bootstrapping, and epoch reconfiguration. In addition, there are two main transaction structures: UTXO-based and account-based models. In particular, TEEChain implements a general transaction structure.


### 5.2.2. Intrashard Consensus

The intrashard consensus protocols have been presented in detail in the previous sections. Considering the waste of resources generated by the PoW consensus, most sharding mechanisms use the BFT protocol to achieve intrashard consensus. Through algorithm optimization, RapidChain improves the fault tolerance from1/3 to 50%. Chainspace and Ethereum 2.0 combine the BFT-type protocols with the Nakamoto-type protocols to improve scalability. In particular, TEEChain introduces the trusted execution environment (TEE) to enhance the security of PBFT protocol.


### 5.2.3. Cross-Shard Transaction Atomicity

Cross-shard transaction is supported in all the considered sharding mechanisms except for Elastico. To ensure the atomicity of blockchain data, most solutions adopt a synchronized lock/unlock scheme to achieve either success or failure of transaction results for all transactions. In particular, TEEChain proposes a two-phase lock and two-phase commit atomicity scheme, which outperforms other schemes.


### 5.2.4. Security and Performance

For security, we focus on the security model, including the threat model and fault tolerance (FT). The threat model represents the likelihood that the system will be suppressed by a malicious node. The attacker behaves arbitrarily, and most attackers are not cooperating with the system. In addition, the attacker is considered slowly adaptive so that the system is not affected in an epoch. Due to the BFT-type consensus algorithm during the intrashard consensus, the FT generally controls at33%, through the optimization of security algorithms, and the introduction of a TEE can improve FT to a certain extent.


## 5.2.1. Protocol Settings

The network model shows the synchrony of the underlying communication network. Except for RapidChain, all the other considered sharding mechanisms adopt the partial sync network model. For most solutions, a randomness is generated at different epochs, which is used to complete different stages of work, such as PoW puzzle for next epoch, shard formation, leader selection, decentralized bootstrapping, and epoch reconfiguration. In addition, there are two main transaction structures: UTXO-based and account-based models. In particular, TEEChain implements a general transaction structure.


## 5.2.2. Intrashard Consensus

The intrashard consensus protocols have been presented in detail in the previous sections. Considering the waste of resources generated by the PoW consensus, most sharding mechanisms use the BFT protocol to achieve intrashard consensus. Through algorithm optimization, RapidChain improves the fault tolerance from1/3 to 50%. Chainspace and Ethereum 2.0 combine the BFT-type protocols with the Nakamoto-type protocols to improve scalability. In particular, TEEChain introduces the trusted execution environment (TEE) to enhance the security of PBFT protocol.


## 5.2.3. Cross-Shard Transaction Atomicity

Cross-shard transaction is supported in all the considered sharding mechanisms except for Elastico. To ensure the atomicity of blockchain data, most solutions adopt a synchronized lock/unlock scheme to achieve either success or failure of transaction results for all transactions. In particular, TEEChain proposes a two-phase lock and two-phase commit atomicity scheme, which outperforms other schemes.


## 5.2.4. Security and Performance

For security, we focus on the security model, including the threat model and fault tolerance (FT). The threat model represents the likelihood that the system will be suppressed by a malicious node. The attacker behaves arbitrarily, and most attackers are not cooperating with the system. In addition, the attacker is considered slowly adaptive so that the system is not affected in an epoch. Due to the BFT-type consensus algorithm during the intrashard consensus, the FT generally controls at33%, through the optimization of security algorithms, and the introduction of a TEE can improve FT to a certain extent.


## 5.3. Different from Other Surveys

As far as we know, the current review literature [15, 30, 37] on blockchain sharding does not cover the same issues as we do.Kim et al. [30] discussed the blockchain scalability solutions from four dimensions, including on-chain, off-chain, side chain/child chain, and interchain. However, strictly speaking, these solutions can be divided into on-chain and off-chain solutions. Neither the side chain/child chain nor the interchain solutions have changed the main chain. Furthermore, in view of different solutions, the paper did not propose a more profound theoretical analysis and ignores the more important sharding-based scalability solution. Our work considers the most promising shard-based blockchain scalability solution and provides a three-layer taxonomy and a more detailed comparison of the solutions.Wang et al. [15] emphasized the scalability issues of the current blockchain and put forward the challenges of introducing sharding to blockchain. In view of these challenges, the existing blockchain solutions were analyzed. In particular, they compared five sharding-based blockchain mechanisms. However, they did not provide enough details about security analysis and comparison. On the basis of Ref. [15], we classify existing solutions, focus on several of the most distinctive sharding solutions, and provide a more comprehensive comparison based on detailed theoretical analysis and calculations.Zhou et al. [37] proposed a three-layer architecture to systematically outline the scalability solutions of the blockchain. However, they elaborated on these solutions from a higher level, without showing the details about the specific mechanisms, and there were no analysis and comparison of security and performance among different solutions. In addition, they did not detail shard-based solutions. Instead, we focus on sharding solutions and present seven well-known shard-based blockchain mechanisms. Furthermore, we provide a comprehensive analysis (i.e., latency and throughput) of considered sharding mechanisms.


## 6. Conclusions

This study introduces the blockchain logical architecture and trilemma, outlines the knowledge of sharding, emphasizes the importance of sharding for scalable blockchain design, and systematizes the existing state-of-the-art sharding mechanisms, involving intrashard consensus protocol, cross-shard transaction atomicity, and general improvements. On this basis, we also propose the detailed calculations and unique insights analyzing the features and restrictions of the considered sharding mechanisms from multidimensions and make a comprehensive comparison and evaluation [19, 20].



---

*Source: 5483243-2021-12-18.xml*