A probabilistic security analysis of sharded blockchains
Motivation:
Nowadays, blockchain becomes revolutionary and has been used in almost all sectors including cryptocurrencies, healthcare, and the government sector. However, blockchain scalability is emerging as a critical issue [1]. Sharding is one of the most promising solutions of the blockchain scalability. Sharding consists of dividing or splitting the entire network into shards, each of which handles and processes in parallel a separate set of transactions leading to scale up the network (i.e., increases the throughput; the number of transactions per second). However, sharding suffers from security issues due to its 1% attack [1], [2], which means that the network can be compromised if only one shard is compromised. In this article, we briefly present a probabilistic model to analyze the security of sharding-based blockchain protocols.
Notations and Definitions:
Table below shows the list of symbols and variables that are used throughout this article to describe the proposed probabilistic model.
Definition 1 (Failure Probability). The probability that the number of malicious nodes exceeds the malicious nodes limit (i.e., the maximum percentage of nodes that can act in a malicious manner, e.g., in the case of Elastico and OmniLedger, this limit is 33% of nodes in a committee and 25% in the network) in the network/committee.
Probabilistic Model:
The process of assigning nodes to shards can be modeled as sampling without replacement since the committees do not overlap in sharding-based blockchain protocols. In this case, we make use of hypergeometric distribution instead of binomial distribution because the hypergeometric distribution gives a better approximation (i.e., more accurate) than the binomial distribution [2].
Computing failure probability:
The failure probability of one sharding round (i.e., one epoch) can be expressed as follows:
Computing Years to Fail:
To measure the security of a given sharding-based blockchain protocol, we propose to compute the average number of years to failure, which can be expressed as follows:
Factors that impact the security of sharding-based blockchain protocols:
There are many factors that can impact the security of sharding-based blockchain protocol including the size of the committee, the number of sharding rounds per year, the resiliency of the network/committee (i.e., the consensus threshold), and the size of the network [2].
Figure above shows the number of years to fail versus the size of the committee (n varying from 10 to 200) and the number of sharding rounds per year (N_sy varying from 45 to 730) by considering N_t = 100000 in a network of N = 1000 nodes (with R = 0.250 and r = 0.333). We observe that for n = 192.421 and N_sy = 22.589 we have the best combination that achieves the biggest number of years to fail, which is about 2.58026 years.
Conclusion:
The sharding technique is one of the best (leading and promising) solutions of the blockchain scalability. However, sharding suffers from its security-critical issue. This article, in part, mitigates this issue by computing the failure probability of one sharding round and then determine the factors that can impact the number of years to fail. In reality, sharding-based blockchain protocols still need more investigations and deep research, we address these challenges to future work.
This is a quick overview of how we can quantify the security of a given sharding-based blockchain protocol. For the complete version of this article, we refer the readers to [2].
References:
[1] https://medium.com/@abdelatif.hafid/blockchain-scalability 8fe7a40a9414
[2] https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=9209957
[3] https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=8936849
