Introduction to Sharding
Sharding is fundamentally a technique of divide conquer, dividing a large blockchain into multiple smaller shards with the goal of increasing the system's throughput (increasing the number of transactions per second) by attempting to process transactions in each shard in parallel. By dividing a blockchain into n shards, the speed can be increased significantly. Components in sharding include nodes, pending transactions, and the ledger. Each shard can use different consensus mechanisms such as PoS, PoW, BFT-based, etc.
When implementing sharding, there are two main issues to consider: Intra-consensus-safety and Cross-shard-atomicity. Deciding the number of shards to be divided is also crucial because the more shards there are, the less computational power is needed to control a shard, but it may compromise the system's scalability (a trade-off between security and scalability).
Scaling Solutions - Layer 1 Blockchain Scaling Strategies:
-
Reducing Overhead: Decreasing the amount of data exchanged between nodes and reducing computational tasks on that data.
-
Vertical Scaling: Adding resources to nodes. For example, increasing the number of transactions per block or reducing the block generation time.
-
Horizontal Scaling: Sharding.
Intra-Consensus-Safety
Intra-consensus-safety deals with handling transactions within a single shard. In this scenario, measures need to be taken to avoid a 1% attack. A 1% attack implies that more than 50% of computational power is required to control the system. When using sharding, dividing the blockchain into n shards means the computational power required to control the system is P > PT/n*(50%). In simpler terms, by dividing the blockchain into many shards, one only needs to control one shard instead of the entire system. Since the computational power in each shard is much less than the entire system, it becomes easier to attack. To minimize the risk of a 1% attack, methods such as randomizing node allocation to different shards at the beginning of each new block are used. Additionally, the selection of leaders relies on random methods. For example, the RandHound protocol in Omniledger.
Cross-Shard-Atomicity
Cross-shard transactions involve transactions where the source and destination do not belong to the same shard. Handling these transactions is complex and time-consuming. Moreover, these transactions make up a significant portion, so efficient processing methods are necessary. Cross-shard-atomicity is a requirement during processing: if a cross-shard transaction fails, the money must be returned to the sender's account to prevent double-spending. To address this issue, mechanisms like Locking/Unlocking are commonly used.
Locking/Unlocking Mechanism: First, the client sends cross-shard transactions to input shards to gather proof (sufficient funds, whether it's locked, etc.) from the input shards. The input shards will then lock the client's money while sending the proofs. If all proofs are valid (Accepted), the client sends the transaction to the output shard for processing, unlocking the money to transfer to the destination account. Conversely, if the proofs are invalid (Rejected), the money is unlocked and returned to the client, ensuring Atomicity. Locking/Unlocking mechanisms operate in blockchains like Omniledger, RapidChain, ChainSpace, etc. Apart from Locking/Unlocking, there are other mechanisms such as Eventual Atomicity or Junking, etc. Eventual Atomicity is used in the Monoxide blockchain along with the Chu-ko-nu mining mechanism.
Some Sharding-Based Blockchains
Academic: Elastico (BFT), Omniledger (BFT), Rapidchain (BFT), Monochain (Nakamoto), ChainSpace (BFT).
Industrial: Ethereum 2.0, Zilliqa, Harmony, Near Protocol.
References: G. Yu, X. Wang, K. Yu, W. Ni, J. A. Zhang, and R. P. Liu, "Survey: Sharding in Blockchains," in IEEE Access, vol. 8, pp. 14155-14181, 2020, doi: 10.1109/ACCESS.2020.2965147.
By Vo Truong Trung Hieu
For more detailed information, please visit: https://inseclab.uit.edu.vn/ky-thuat-sharding-trong-blockchain/?fbclid=IwAR3TkRrEkqpl6A0EwxSAI6rzHl2FeifRNLZaxwaXkptEgStJgCvWHOv1xTQ
Ha Bang - Communications Collaborator, University of Information Technology
English version: Phan Huy Hoang
