A Tractable Probabilistic Approach to Analyze Sybil Attacks in Sharding-Based Blockchain Protocols

Table I shows the list of symbols and variables that are used to describe the proposed PGFA as well as JHDA.

Definition 1. Ordinary Generating Function. The ordinary generating function for the sequence $(u_{z})_{z\geq 0}$ is the power series, which can be expressed as follows:

Definition 2. Committee Resiliency. The maximum percentage of Sybil IDs that the committee can contain/support whereas still being secure.

Definition 3. Total Resiliency. The maximum percentage of malicious nodes that the whole network can contain whereas still being secure. It is the maximum percentage of malicious nodes that the entire network can tolerate/support without compromising its security.

Definition 4. ID Pool. ID Pool contains IDs (Sybil and honest IDs) generated by the nodes (honest or malicious nodes); each node generates its own ID, save the ones, which can generate many Sybil IDs.

Definition 5. Adversary’s hash-rate. The percentage of adversary’s hash-power in participating in the ID Selection Pool (e.g., if an adversary controls $30$ Sybil IDs in an ID Selection Pool that contains 100 IDs, thus the adversary’s hash-rate will be $30\%$).

Definition 6. ID Selection Pool. ID Selection Pool is constructed in each epoch using a consensus mechanism (e.g. PoW) and contains the total number of required and valid/qualified IDs; it contains the number of IDs that is necessary in participating in this epoch; this number depends of the security of the network.

Remark. It is worth noting that a honest node can participate with many honest IDs.

In this section, we compute the probability of selecting Sybil IDs from the ID Pool during the construction of the ID Selection Pool.

Figure 2 shows a worst-case scenario of a sharding-based blockchain protocol. In this scenario, we assume that each honest node is able to generate its own ID and one strong (in terms of hash rate) malicious node (aka one adversary) generates numerous Sybil IDs. The sharding process consists of $3$ steps. In the first step, each node participates by its own ID, save a malicious node, it participates with $\mathcal{M}$ IDs. In the second, we construct the ID Selection Pool from the ID Pool. More specifically, using a consensus mechanism (e.g. PoW and PoS), each node competes to generate a valid/qualified ID to join the ID Selection Pool, save the malicious, it adds $\mathcal{M^{{}^{\prime}}}$ Sybil IDs ($\mathcal{M^{{}^{\prime}}}\leq\mathcal{M}$) thanks to its high hash power. In the third step, we randomly distribute (i.e., random assignment) IDs from from the ID Selection Pool to shards.

A few sharding-based Blockchain protocols (e.g. Ethereum sharding [33]) adopt the PoS-based node/ID selection method to select shard members to defend against Sybil attacks. However, in most sharding-based blockchain protocols (e.g., Elastico [10], OmniLedger [9] and RapidChain [8]), Proof-of-Work (PoW) consensus is typically used to establish the committee/shard members (committee formation) and generate the corresponding IDs; Byzantine Fault Tolerant (BFT) is used for the intra-committee consensus, which is used within a committee to create and append the blocks [8], [5]. More specifically, nodes who want to join/stay in the protocol use PoW consensus to generate valid IDs (i.e., public keys). Only the nodes that can solve the ID generation PoW puzzle (e.g. RapidChain uses a fresh fixed PoW puzzle [8]) can generate valid IDs. It turns out that the nodes that have a higher hash-rate have a higher probability to solve the ID generation PoW puzzle compared to those of lower hash-rate. The security of the network will not be compromised as long as the malicious node’s computational power is limited.

Now, let $\mathcal{X}$ be a random variable that counts the number of Sybil IDs selected from the ID Pool. In the following, we compute the probability of selecting exactly $m$ Sybil IDs from the ID pool (Lemma 1) and then the probability of selecting at least $m$ Sybil IDs from the ID pool (Lemma 2).

Lemma 1: In a sharding-based blockchain protocol, the probability of selecting exactly $m$ Sybil IDs from the ID pool is given by:

Proof: In a sharding-based blockchain protocol, the process of assigning IDs to shards can be modeled as a random sampling without replacement, because the shards can not overlap. In this case, the hypergeometric distribution yields a better probability approximation compared to any other probability distribution, including that of Binomial’s [20]. Thus, the proof of Lemma 1 is a direct result from the fact that $X$ follows a hypergeometric distribution [20], [4].

Lemma 2: In a sharding-based blockchain protocol, the probability of selecting at least $m$ Sybil IDs from the ID pool can be computed as follows:

Proof: Given the fact that $\mathcal{X}$ follows a hypergeometric distribution, the proof of Lemma 2 can be extracted directly from the cumulative hypergeometric distribution [20].

The following subsection will be devoted to compute and calculate the probability that at least one shard fails.

In this section, we compute the probability that at least one shard fails in a sharding-based blockchain protocol using the proposed approach (i.e., PGFA). First, we briefly describe how JHDA [4] computes such a probability. Then, we present the details of the proposed PGFA.

In sharding-based blockchain protocols, the process of assigning IDs to committees (or partition of the network into committees/shards) can be defined as a sampling without replacement, because the committees do not overlap [6]. When the sample is done without replacement, we make use of the hypergeometric distribution instead of binomial’s [6], [20]. Note that to model this sampling using the hypergeometric distribution, we need to make use of joint hypergeometric distribution to cover the failure probabilities of all committees, which is a complex/difficult to compute; it is a closed-form expression. This is the reason why we choose generating function. Generating function is fundamentally devoted to such complicated problems.

The generating function corresponding to select distinct items from a finite set (as sampling without replacement) can be expressed as follows:

where $\binom{n}{k}$ is the number of ways/possibilities to choose/select $k$ distinct items from a set of size $n$; it can be expressed as follows:

The main aim of our analysis is how to divide $m$ malicious nodes between $\lambda$ committees without exceeding the resiliency of each committee. Let $m=m_{1}+m_{2}+\dots+m_{\lambda}$ where $m_{1}$ is the number of Sybil IDs in the first committee, $m_{2}$ is the number of Sybil IDs in the second committee, and so on. We need to divide $m$ Sybil IDs, whereas for all $i\in\{1,2,\cdots,\lambda\}$, $m_{i}$ is smaller than the resiliency of the committee (e.g., $r=\frac{1}{2}$ for RapidChain [8]).

Now, based on (7), the generating function that represents one committee can be expressed as follows:

Precisely, if we assume (9) refers to shard 1, thus $m_{1}$ can take 0 , 1 , 2 , …, or $\lfloor nr\rfloor$ Sybil IDs. And if (9) refers to shard 2, $m_{2}$ also can take 0 , 1 , 2 , …, or $\lfloor nr\rfloor$ malicious nodes, and so on for the other shards. Based on (9), the number of possibilities for shard 1 to receive $m_{1}$ = 0 malicious nodes (i.e., shard 1 does not contain any malicious node) is $\binom{n}{0}$, the number of possibilities for shard 1 to receive $m_{1}$ = 1 malicious nodes (i.e., shard 1 contains one malicious node) is $\binom{n}{1}$; thus, the number of possibilities for shard 1 to get $m_{1}$ = $\lfloor nr\rfloor$ Sybil IDs is $\binom{n}{\lfloor nr\rfloor}$. Our first objective is to calculate the number of possibilities we can split $m$ malicious nodes between $\lambda$ committees without exceeding the committee resiliency (i.e., without exceeding the maximum number of Sybil IDs that the committee can tolerate; this number is $\lfloor nr\rfloor$ in (9)). Then, we can compute the failure probability, which represents the probability that at least one committee exceeds the committee resiliency.

Generally, the generating function for choosing elements from a union of disjoint sets is the product of the generating functions from choosing from each set [21]. In our case, we have $\lambda$ committees which do not overlap (the sampling is done without replacement). Indeed, the entire network is the union of disjoint committees; it can be modeled as follows:

where $C$ is a set which contains all nodes in the entire network with $card(C)=N$, $C_{i}$ contains the number of nodes in committee $i$ with $card(C_{i})=n$ for all $i\in\{1,2,\cdots,\lambda\}$, and for all $i,j\in\{1,2,\cdots,\lambda\}$, $C_{i}\cap C_{j}=\emptyset$ for $i\neq j$. To compute the total number of ways we can distribute the $m$ Sybil IDs across all committees, we multiply this generating function with itself $\lambda$ times:

where

Now, we need to extract the coefficient of $x^{m}$ in (11), which corresponds to the number of possibilities we can split $m$ Sybil IDs across $\lambda$ committees without exceeding the resiliency of each committee (note that all the committees have the same resiliency). To compute the sequence of coefficients from this generating function, we need to compute the Taylor series for this generating function [21]. Therefore, the required coefficient can be expressed as follows:

where $\Psi^{m}(0)$ is the $m$th derivative of $\Psi(x)$ evaluated at $x=0$.

The required coefficient can be determined explicitly (analytically) by using (13); however, this process involves tedious and complex calculations. Instead, we can determine the coefficient computationally by using SymPy package [31]; it uses the symbolic math system making the process easier to execute.

The probability that at least one committee fails is the probability that at least one committee contains more than $nr$ Sybil IDs. This means that the number of Sybil IDs in the committee exceeds the committee resiliency. Therefore, the probability that at least one committee fails using PGFA is expressed in Theorem 2.

Theorem 2: In a sharding-based blockchain protocol, the failure probability that at least one committee fails using PGFA can be expressed as follows:

where $\binom{\mathcal{N}}{m}$ is the total number of possibilities to select $m$ Sybil IDs from $\mathcal{N}$ IDs.

In this section, we compute the probability of a successful attack (the failure probability of the entire network); this means that we take into consideration the probability of selecting Sybil IDs from the ID Pool as well as the probability of at least one shard takeover attack.

Theorem 3: Given a sharding-based blockchain protocol, the probability of a successful attack (assumed by an adversary) can be computed as follows:

Proof: By taking into consideration both probabilities (i.e., the probability of selecting Sybil IDs from the ID pool as well as the probability that at least one shard fails), and based on Lemma 2 and Theorem 2, the probability of a successful attack ($\mathcal{P^{{}^{\prime\prime}}}$) can be expressed as follows.

To measure the security of a given protocol, we propose to compute the average number of years to failure. To perform this computation, we need to determine the failure probability of epoch per sharding round, which refers to the failure probability that at least one committee fails. The average number of years to fail corresponding to PGFA is given by:

The average number of years to fail corresponding to JHDA ($\mathcal{P^{\prime}}$ must be calculated by Theorem 1) is given by:

where

Table II shows a comparison (in terms of complexity) between PGFA and JHDA.

Specifically, Table II shows that JHDA is very difficult and impractical to compute whereas PGFA shows a linear complexity. Thus, the feasibility of PGFA to analyze the security of sharding-based blockchain protocols.

To implement our approach, we use SymPy Python library, which makes the use of symbolic mathematics easier [31], (e.g., polynomial functions). Particularly, we use sympy.Symbol() and sympy.Poly() to declare the variable “x” explicitly and to explicitly express the polynomial in (9). To implement JHDA, we refer the readers to [4].

Table III shows the values of the parameters used in the simulations.

Figure 3 shows a comparison between JHDA and PGFA for different ID Selection Pool sizes ($\mathcal{K}$), values of resiliency ($r$ and $\mathcal{R}$), and numbers of trials ($t$) when varying the size of the committee from 25 to 250 by a step of 25.

More specifically, Figures 3(a), 3(b), and 3(c) show that the performance of FPGA is close to JHDA. Figure 3(d) shows a much closer match between the results achieved by PGFA and JHDA. This is expected since, for JHDA, when the number of trials ($t$) increases the estimated failure probability moves towards the exact failure probability [4]. We conclude that the proposed PGFA allows for an accurate computation of the failure probability.

Figure 4 shows the failure probability of selecting Sybil IDs from the ID Pool ($\mathcal{P}$), the failure probability for at least one shard takeover attack ($\mathcal{P^{\prime}}$), and the probability of a successful attack ($\mathcal{P^{\prime\prime}}$) when varying the number of Sybil IDs (we assume that $\mathcal{M}$ = $\mathcal{M^{\prime}}$; the worst case that can happen) from 10 to 200 (by a step of 10 IDs) for different network sizes, values of committee resiliency, values of ID Selection Pool resiliency, ID Selection Pool sizes, and for different values of committee size (n). These results show that the failure probability increases with the number of Sybil IDs means a high hash-rate of the adversary; this increases the probability to compromise the security of the network. In particular, Figures 4 (a), 4 (b), and 4 (c) show the failure probability of selecting Sybil IDs from the ID Pool for different network size ($\mathcal{N}$ = 1000, $\mathcal{N}$ = 1200, and $\mathcal{N}$ = 1400), ID Selection Pool resiliency ($\mathcal{R}$ = 0.333, $\mathcal{R}$ = 0.25, and $\mathcal{R}$ = 0.20), and for different ID Selection Pool size ($\mathcal{K}$ = 400, $\mathcal{K}$ = 600, and $\mathcal{K}$ = 800), respectively. More specifically, Figure 4 (a) shows that as the network size increases (in this case, we set of the size of the ID Pool Selection to 800 IDs, and the resiliency of ID Selection Pool to 0.333) the failure probability ($\mathcal{P}$) delays to assume big values; this shows up the impact of the network size on the security of the network. Figure 4 (b) shows that when the committee resiliency gets larger the failure probability ($\mathcal{P}$) delays to assume values close to 1; this shows that a higher ID Selection Pool resiliency allows for higher security.

Figure 4 (c) shows the impact of the size of the ID Selection Pool on the failure probability ($\mathcal{P}$). We observe that as the size of ID selection pool gets larger the failure probability is slow to assume values closer to 1; thus, the larger the size of the ID Selection Pool the higher the security of the network.

In addition, Figures 4 (d), 4 (e), and 4 (f) show the failure probability that at least one shard takeover attack ($\mathcal{P^{\prime}}$) for different ID Selection Pool sizes, values of the committee resiliency, and committee sizes, respectively.

More specifically, Figure 4 (d) shows the impact of the size of the ID Selection Pool ($\mathcal{K}$ = 600 and $\mathcal{K}$ = 700; in this case, we set $\mathcal{N}$ to 1000, r to 0.333, and $n$ to 100) on the failure probability ($\mathcal{P^{\prime}}$). We observe that as the size of ID Selection Pool gets larger the failure probability is slow to assume values closer to 1; thus, the larger the size of the ID Selection Pool the higher the security of the network.

Figure 4 (e) shows the impact of the committee resiliency ($r$) on the failure probability ($\mathcal{P^{\prime}}$). We observe that as the committee resiliency gets larger the failure probability is slow to assume values closer to 1; thus, the larger committee resiliency the higher the security of the network.

Figure 4 (f) shows the impact of the committee size ($r$) on the failure probability ($\mathcal{P^{\prime}}$). We observe that as the committee size gets larger the failure probability is slow to assume large values (i.e., values closer to 1); thus, the larger the size of the committee the higher the security of the network.

Figures 4 (g), 4 (h), and 4 (i) show the probability of a successful attack ($\mathcal{P^{\prime\prime}}$) when varying the number of Sybil IDs ($\mathcal{M}$) from 10 to 200 by a step of 10. We observe that the failure probability ($\mathcal{P^{\prime\prime}}$) increases with the number of Sybil IDs (generated by an adversary). This is expected, since the increase in the number of Sybil IDs leads to an increase of the chance of an adversary to compromise the security of the network.

More specifically, Figure 4 (g) shows the impact of the network size ($\mathcal{N}$) on the probability of a successful attack ($\mathcal{P^{\prime\prime}}$); in this case, we set $r$ to 0.25, $\mathcal{R}$ to 0.10 , $\mathcal{K}$ to 800, and $n$ to 100. We observe that as the network size gets larger the probability of a successful attack is slow to assume values closer to 1; thus, the larger size of the network the higher the security of the network.

Figure 4 (h) shows the impact of the committee resiliency ($r$) on the probability of a successful attack ($\mathcal{P^{\prime\prime}}$); in this case, we set $\mathcal{N}$ to 1000, $\mathcal{R}$ to 0.10, $\mathcal{K}$ to 800, and $n$ to 100. We observe that as the committee resiliency gets larger the probability of a successful attack is slow to assume values closer to 1; thus, the larger committee resiliency the higher security of the network.

Finally, Figure 4 (i) shows the impact of the size of the committee ($n$) on the probability of a successful attack ($\mathcal{P^{\prime\prime}}$); in this case, we set $\mathcal{N}$ to 1000, $\mathcal{R}$ to 0.10, $\mathcal{K}$ to 800, and $r$ to 0.25. We observe that as the size of the committee gets larger the probability of a successful attack is slow to assume values closer to 1; thus, the larger size of the committee the higher security of the network.

To sum up, Figure 4 shows that by taking advantage of PGFA we get a promising results. In particular, we identify the parameters that impact the probability of a successful attack. This means $\mathcal{N}$, $\mathcal{K}$, $\mathcal{M}$, $\mathcal{M^{\prime}}$, $n$, $\lambda$, $r$, and $\mathcal{R}$.

Table IV shows the probability of a successful attack ($\mathcal{P^{{}^{\prime\prime}}}$) and the average number of years to fail ($\mathcal{A}$) for different parameters (i.e., $\mathcal{N}$, $\mathcal{K}$, $\mathcal{M}$, $\mathcal{M^{\prime}}$, $n$, $\lambda$, $r$, $\mathcal{R}$, and $N_{s}$). We observe that when we change the values of some parameters (even small changes), the network security can be considerably impacted. For example, Table IV shows that for $\mathcal{R}$ = 0.2, the number of years to fail is 8623.61 and for $\mathcal{R}$ = 0.15, the number of years to fail is 1.02e-02. Indeed, a network that fails 1000s years on average has a high acceptable level of security (i.e., secure) whereas a network that fails less than one year on average is not secure enough.

Now, to validate the feasibility of our approach, we perform a comparison with another existing approach called Break Consensus Protocol attack (BCP) [7]. Rajab et al. [7] computed (by using BCP) $\mathcal{P}$, but failed to accurately compute $\mathcal{P^{\prime}}$. Thus, they failed to accurately compute $\mathcal{P^{\prime\prime}}$. BCP proposed a similar model to that of Figure 2; for that reason, we compare the proposed PGFA with BCP.

Figure 5 shows the probability of a successful attack when varying the number of Sybil IDs from 10 to 200 (by a step of 10 IDs) for both PGFA and BCP approach. We observe that the probability of a successful attack computed by BCP exceeds 1. This means that BCP computes false probabilities and its formula (Theorem 1 in [7]) does not corresponds to a proper probability distribution. In particular, they computed the probability that at least one shard fails by assuming that the probability of the first shard is indicative to the probability of the other shards; more specifically, they multiply the failure probability of the first shard by the number of shards to get the probability that at least one shard fails.

Note that the proposed probabilistic model can be adopted to different scenarios by adjusting some parameters (e.g. $\mathcal{K}$, $\mathcal{M^{{}^{\prime}}}$). For instance, (1) A network with many malicious nodes where each generates numerous Sybil IDs; and (2) Honest node/nodes participate with many IDs.