New Mathematical Model to Analyze Security of Sharding-Based Blockchain Protocols

Abstract

In recent years, the scalability issue of blockchain protocols has received huge attention. Sharding is one of the most promising solutions to scale blockchain. The basic idea behind sharding is to divide the blockchain network into multiple committees where each committee processes a separate set of transactions. In this paper, we propose a mathematical model to analyze the security of sharding-based blockchain protocols. Moreover, we analyze well-known sharding protocols including RapidChain, OmniLedger, and Zilliga to validate our model. The key contribution of our paper is to bound the failure probability for one committee and so for each epoch using probability bounds for sums of upper-bounded hypergeometric and binomial distributions. In addition, this paper contribution answers the following fundamental question: “how to keep the failure probability, for a given sharding protocol, smaller than a predefined threshold?”. Three probability bounds are used: Chebyshev, Hoeffding, and Chvátal. To illustrate the effectiveness of our proposed model, we conduct a numerical and comparative analysis of the proposed bounds.

Keywords

• Blockchain
• failure probability
• hypergeometric distribution
• probability bounds
• sharding