Keywords

1 Introduction

Scalability is a prominent issue in the blockchain. While Mastercard processes 50,000 transactions per second, Bitcoin processes 7 and Ethereum processes 15 transactions per second. Offline channel [1] is a useful tool to improve the scalability of blockchains. A pair of peers only need to broadcast two transactions to open and close a channel between them. A channel (theoretically) supports an infinite number of transactions between them. Channels offer offline Path-Based fund Transfer (PBT) service [2]. A PBT uses a path in the offline channel network for fund transfer between two parties who do not have a channel. Examples of offline channel networks are Lightning Network for Bitcoin, the Raiden Network [3] for Ethereum and SilentWhispers [2] for credit networks.

Peers allow PBT execution through their channels in exchange for small transfer fee. Hence PBT can be a source of revenue. While ordinary peers with limited funds cannot establish a great number of channels for the purpose of generating revenue, there are financial entities (with access to significant funding) who can establish offline channels for the sole purpose of collecting the PBT transfer fees. In Bitcoin Lightning network we witnessed this phenomenon. There are only 10 nodes with control of more than 50% funds available in the Lightning network. These nodes have a very high degree. We refer to these high degree nodes as the hubs.

Hubs can improve the performance of the offline channels by reducing the PBT completion time and improving the success rate of PBT execution. But it brings a new form of collusion attack on the channel network. In a collusion attack, a collusion (a group of hubs) can make few channels non-operational to prevent PBTs among a set of targeted hubs. The targeted hubs are the victim of the collusion attack. The objective of this paper is to investigate how such a collusion attack can be executed in the channel network and develop a mechanism that can lower the possibility of such anattack. We have the following results in this paper:

  1. 1.

    We present a mathematical model of collusion attack on the channel network. We use cooperative game theory and coalitional power index (Banzhaf index) [4, 5] to model collusion attacks. We model a collusion as a coalition and Banzhaf index gives the estimation on the importance of a hub’s participation in a collusion attack.

  2. 2.

    We present a model of the likelihood of collusion attack among the hubs in a channel network using Banzhaf indices.

  3. 3.

    We analyze the possibility collusion attack in the Bitcoin’s Lightning network. We found that there are 62 nodes who can execute collusion attacks against 90% of their neighbors in the Lightning network.

The paper is organized as follows: In Sect. 2 we discuss related literature, in Sect. 3 we present the collusion attack problem, in Sect. 4 we present a method to evaluate the possibility of collusion attack in a channel network, in Sect. 5 we present a method to lower the possibility of collusion attack, in Sect. 6 we evaluate Bitcoin’s Lightning network to evaluate possibility of collusion attacks and we conclude the paper in Sect. 7.

2 Related Literature

In this paper, we study an attack model in the offline channel network. Offline channels are designed to improve the scalability of blockchains. Examples of such developments are as follows: Bitcoin Lightning network was proposed in [1] which allows peers to create and transfer funds among them without frequently updating the blockchain. Similar networks are proposed for Ethereum [3] and credit networks [2]. A privacy-preserving payment method in the credit network was proposed in [6]. Recent advances on the offline channel network are focused on the development of routing protocols for offline channels. Examples of such routing protocols are as follows: A method for anonymous payment to improve privacy in PBT was developed in [7]. Grunspan and Pérez-Marco [8] proposed a decentralised routing algorithm for the channel network.

Current research in the offline channel network for blockchains is focused on developing better routing protocols for balancing the channels, privacy preserving routing and fast routing protocols. But there is a lack of analysis on the collusion attack that hubs in a channel network can orchestrate. In this paper we analyze collusion attacks among the hubdds in a blockchain peer to peer network. The collusion attack is similar to eclipse attack. Heilman et al. [9] analysed eclipse attack [10, 11] on Bitcoin network and it proposed appropriate countermeasures. Nayak et al. [12] analyzed a combination of selfish mining and eclipse attack on blockchain peer to peer network. In this paper, we analyze collusion attack among hubs in the blockchain network instead of analyzing eclipse attack on the entire peer to peer network. We perform such analysis as we observed centralization of the channel network. Our results can characterize the effect of centralisation in the channel network. We will use the Banzhaf index to characterize collusion attacks. Bachrach and Rosenschein [5] analyzed Banzhaf podddwer indices for network flow games and [4] analyzed Banzhaf power indices for network connectivity games. These research have proved that it is NP-hard to compute the Banzhaf index.

3 Collusion Attacks

First, we present an analysis of the Bitcoin’s Lightning network to illustrate the existence of hubs in the channel network. Next, we present the model of collusion attack on the channel network.

3.1 Hubs in Bitcoin Lightning Network

We use the Bitcoin Lightning network data [13] to explain the existence of hubs. The dataset has 2810 nodes and 22,596 edges. The average degree of nodes is 16 (shown in Fig. 1). If we consider nodes with a degree more than 50 as hubs then, there are 168 hubs. Collusion is a coalition among the hubs which can prevent PBTs for the remaining hubs. A collusion attack can be executed by creating a cut the channel network.

Fig. 1
figure 1

Degree distribution of bitcoin lightning network data. It shows the existence of very high degree nodes

Full size image

Collusion is a group of hubs in the channel network who aim to prevent PBTs between a pair of targeted hubs or victims of the collusion attack. We will describe the model of collusion using a neighbourhood of a chosen hub. The neighbourhood will be restricted by the maximum distance from the hub. This will allow us to evaluate the potential of a hub to orchestrate a collusion attack in its neighbourhood. In the next Section we will define such collusion and we will define the potential of a peer to organise collusion as it Banzhaf index. Banzhaf index measures the value of a hub in a coalition (collusion) as it evaluates if the coalition will remain successful (to execute a collusion attack) if this hub leaves the coalition.

3.2 Models of Collusion Attack

Let \(G=(V,E)\) be a directed graph with n nodes V representing the hubs of the channel network and m edges E representing the channels among the hubs. Let \(G^i\) be the subgraph induced by the vertices who are at most k edges apart from \(V_i\in V\) (including \(V_i\)) on the graph G where k is a positive integer less than diameter of G. \(V^i\) will denote the set of nodes at most k edges apart from \(V_i\) or the set of vertices of the subgraph \(G^i\).

We will define collusions w.r.t any specific node \(V_i\) to use the subgraph \(G^i\). A collusion is a subset of nodes \(V^i\) such that:

  1. 1.

    It can produce a cut between a pair of hubs (or more pairs of hubs) in \(G^i\). This pair of hubs is the victim of the collusion attack as PBTs between them will not be executed in \(G^i\).

  2. 2.

    The hubs in the collusion have additional channels to allow the flow of tokens through them.

Fig. 2
figure 2

Example of a collusion centred at \(V_i\) that includes \(V_i, V_1,V_2,V_3\) and \(V_4\). The collusion produces a cut between \(V_a\) and \(V_b\) in \(G^i\)

Full size image
Fig. 3
figure 3

The collusion is the set of hubs \(V_1,V_2,V_3,V_4, V_i\) and the victim of the collusion are the hubs \(V_a,V_b,V_c,V_d,V_e,V_f\). Weight of the collusion is 3 as it disconnects 3 pairs of hubs

Full size image

We formally define collusion (shown in Figs. 2, 3 and 4) as follows:

Definition 1

In a hub network \(G=(V,E)\), a collusion C centred at \(V_i\) is a subset of \(V^i\) such that the following holds:

  1. 1.

    \(V_i\in C\).

  2. 2.

    \(|C|\le \delta \) where \(\delta \) is a positive integer.

  3. 3.

    Let \(F\subset E\) be the set of edges originating from any \(V_x\in C\).

  4. 4.

    There exists a pair of nodes \((V_a,V_b)\in V^i - C\) such that there cut \(F'\subset F\) where the source is \(V_a\) and sink is \(V_b\).

  5. 5.

    There is a path in \(F-F'\) that connects every node in C to any node \(V_x\in V-V^i\).

The explanation of the above notion of collusion attack is as follows:

  1. 1.

    We define a collusion w.r.t a node \(V_i\). It helps us to define the set of collusions where \(V_i\) can have significant contributions.

  2. 2.

    We restrict the size of collusions using the parameter \(\delta \).

  3. 3.

    We restrict the size of a subgraph that collusion can control by the parameter k. If collusion can produce a cut between \(V_a\) and \(V_b\) in the subgraph \(G^i\) then it means there is no path in G with distance less than the distance between \(V_a\) and \(V_b\) in \(G^i\). It means if the collusion blocks the paths between \(V_a\) and \(V_b\) in \(G^i\) then cost of PBT transfer between \(V_a\) and \(V_b\) is increased by the PBT transfer fee of at least one more channel. Hence a collusion attack can at least increase the cost of PBTs between the victims even if the collusion could not completely prevent any PBTs among its victims.

  4. 4.

    Finally, collusion must have a path to the hubs outside the subgraph \(G^i\) despite closing certain channels to execute the collusion attack. It is needed for executing the set of PBTs that the collusion allows.

Definition 2

Weight of a collusion \(C\subset V^i\) is the number of pairs of nodes for which the collusion can produce cuts.

Fig. 4
figure 4

The collusion is the set of hubs \(V_1,V_2,V_3,V_4, V_i\) and the victim of the collusion are the hubs \(V_a,V_b\). \(V_i\) is a critical player as the collusion will fail if \(V_i\) leaves

Full size image

Now we define collusion formation game as a cooperative game.

Definition 3

A collusion formation game produces a set of collusions denoted as the set \(\{(C,V_i)\}\) where \(C\subset V^i\) is the collusion centred at \(V_i\) as the result of cooperation among the members of each collusion. The value of a collusion is defined by the function \(\theta \) as follows:

$$\begin{aligned} \theta (C) = {\left\{ \begin{array}{ll} 1 &{} \text { if }C\text { can produce a cut for a pair of hubs }(V_a,V_b) \in V^i - C \\ 0 &{} \text { Otherwise} \end{array}\right. } \end{aligned}$$
(1)

Now we define the importance of a hub in a collusion.

Definition 4

In a collusion \((C,V^i)\), a hub \(V_x \in C\) is a critical player if \(\theta (C) = 1\) and \(\theta (C-V_x) = 0\) indicating that the collusion becomes unsuccessful if \(V_x\) leaves the collusion. The number of collusions centred at \(V_i\) where \(V_i\) is a critical player is denoted by \(\nabla _i\).

Now we define the Banzhaf index of a hub for a collusion formation game as follows:

Definition 5

Banzhaf index of the player \(V_i\) in the collusion formation game is

$$\begin{aligned} \beta _i = \frac{\nabla _i}{\sum _{V_x\in V^i} \nabla _x} \end{aligned}$$
(2)

Note that we restrict the definition of the power of a hub within the subgraph in which it forms collusion. This is because the same subgraph is valid where the hub will be a victim of another collusion attack. Next, we will discuss the algorithm to compute the Banzhaf index.

4 Potential of Collusion Attacks

figure a

In this Section, we discuss a method to evaluate the possibility of executing collusion attack in a channel network. First, we will discuss the algorithm to compute Banzhaf index for collusion attack as defined in the previous Section. It should be noted that the computation complexity of computing Banzhaf index is NP-hard [14]. In this paper, we will use Algorithm 1 to estimate Banzhaf indices. The explanation of Algorithm 1 is as follows:

  1. 1.

    In a subgraph \(G^i\) centerd at \(V_i\), we compute the number of collusions (subsets of nodes in \(V_i\) with maximum cardinality k) where \(V_i\) is a critical player.

  2. 2.

    It should be noted that if the number of nodes in \(G^i\) is x then the number of collusions where \(V_i\) is a member is

    $$\begin{aligned} \frac{x!}{(x-k)! k!} - \frac{(x-1)!}{(x-1-k)! k!} \end{aligned}$$
    (3)
    $$\begin{aligned} \frac{(x-1)!}{(x-1-k)! k!} [ \frac{x}{x-k}- 1] \end{aligned}$$
    (4)

    The number of possible collusions which includes \(V_i\) is very large. It is computationally difficult to test all such collusions to check if \(V_i\) is a critical player. Hence instead of checking all collusions we only check the collusions created by a set of random walks from \(V_i\).

  3. 3.

    For each node \(V_i\) we create x random walks where x is the degree of \(V_i\) in the graph \(V^i\).

  4. 4.

    For the set of vertices in each such random walk,  

    Case 1:

    We compute the if the deletion of the edges from the set of vertices in each random walk (treated as collusion) to the remaining vertices of \(V^i\) (victims of the collusion attack) disconnects the graph \(G^i\).

    Case 2:

    Next, we compute if such disconnection of the graph is possible without \(V_i\).

     

  5. 5.

    \(V_i\) is a critical player if Case 1 is true and Case 2 is false. Using such information we compute the Banzhaf indices for all hubs.

Now we define the potential of collusion attack in the channel network as follows:

Definition 6

The potential of collusion attack in a channel network can be estimated by the standard deviation of Banzhaf indices of hubs. High standard deviation indicates that there are few hubs who can easily execute collusion attack while the remaining hubs are unlikely to execute collusion attack.

5 Method to Reduce Possibility of Collusion Attacks

Theorem 1

The probability that a hub can successfully execute a collusion attack increases as its degree increases.

Fig. 5
figure 5

Relation between degree of an attacker and probability of successful attack: it shows the worst case scenario for \(V_i\) as a critical player to execute a collusion attack against \(V_a\) and \(V_b\)

Full size image

Proof

Let the collusion C is the set \(V_i\cup (V_1,V_2,\dots ,V_x)\) and it wants to execute a collusion attack against the pair of hubs \((V_a, V_b)\) in the subgraph \(G^i\). The attack scenario is illustrated in Fig. 5. Let \(V_a\) is at a distance \(k-1\) from \(V_i\) and \(V_b\) is adjacent to \(V_i\). In this scenario, we will estimate the size of collusion needed to execute an attack against the pair of hubs \((V_a,V_b)\) by \(V_i\). As shown in Fig. 5 the set of collusion is \(V_1,\dots ,V_x\). In the worst case, the number of such collusion is the number of leaf nodes of a tree from \(V_a\) with depth \(k-2\). Hence the number of nodes is

$$\begin{aligned} X = 1+d+d^2+\dots +d^{k-2} = \frac{d^{k-2} -1}{d-1} \end{aligned}$$
(5)

where d is the average degree of the hub network. Hence in the worst case \(V_i\) needs cooperation from \(\frac{d^{k-2} -1}{d-1}\) hubs to attack the pair \((V_a,V_b)\). Note that, \(V_i\) can have \(d_i\) neighbours (degree of \(V_i\) in \(G^i\)). The relation between degree of \(V_i\) and the probability that \(V_i\) can attack on the pair \((V_a,V_b)\) is as follows:

  1. 1.

    \(V_i\) may execute the attack if \(d_i < \frac{d^{k-2} -1}{d-1}\). It means if \(V_i\) has sufficient number of neighbours to form collusion then it can orchestrate such an attack.

  2. 2.

    The probability that \(V_i\) has can execute the attack depends on the probability that each node \(V_1\) to \(V_x\) has \(V_i\) as its neighbour. The probability that the node \(V_1\) is a neighbour of \(V_i\) is \(d_i\frac{d-1}{d^k-1}\) where \(\frac{d^k-1}{d-1}\) is the estimated number of edges in \(G^i\).

  3. 3.

    Hence the probability that \(V_i\) can execute the attack is \([d_i\frac{d-1}{d^k-1}]^X\)

  4. 4.

    Thus the probability that \(V_i\) can successfully attack the pair of hubs \((V_a,V_b)\) increases with the degree of \(V_i\).

Theorem 2

If hubs of the hub network have a uniform degree then, Banzhaf indices are approximately equal.

Proof

Note that Banzhaf index of a hub depends on the number of collusions where it is a critical player. As proved in the previous theorem, higher the degree higher the probability that a hub can successfully execute a collusion attack. It proves that if the degree of nodes is equal then they will be equally likely to execute successful collusion attacks. Hence their Banzhaf indices will be approximately equal.

We propose that uniform Banzhaf indices may prevent collusion attacks in the hub network. This claim is based on the following observations:

  1. 1.

    In order to detect collusion attack, a hub must observe where its PBT requests are denied in the network. If the network is synchronous then it is a trivial problem. But in an asynchronous network, such detection problem is non-trivial. The collusion detection problem can be formulated as the problem of finding black holes in the network. Block holes are the nodes in a network who destroy mobile agent visiting the node. The collusion detection problem can be formulated as a block hole search problem where mobile agents are network probes. The complexity of this search problem is NP-hard [15, 16]. But several approximation algorithms exist for both synchronous and asynchronous networks [17].

  2. 2.

    If the Banzhaf indices are approximately equal then it means if hub \(V_a\) can attack hub \(V_b\) then \(V_b\) can also execute a collusion attack against \(V_a\).

  3. 3.

    Hence equal Banzhaf indices will bring an ‘equilibrium’ in the sense that if \(V_a\) attacks \(V_b\) then \(V_a\) can reciprocate such action. Hence it will prevent the hubs from orchestrating collusion attacks.

6 Evaluation with Bitcoin Lightning Network

In this paper, we discussed a model of collusion attack in the offline channels for blockchains. We proved that (a) hubs will have approximately equal Banzhaf indices if their degrees are the same and (b) if hubs have equal Banzhaf indices then they are less likely to initiate a collusion attack. We measure the uniformity of Banzhaf indices as its standard deviation. In this Section, we perform an experimental evaluation of Algorithm 1 and we measure the Banzhaf index of nodes in the Bitcoin Lighting network. We have the following objectives in this experimental evaluation:

  1. 1.

    Prove the correctness of Algorithm 1 which measures the Banzhaf index.

  2. 2.

    Measure the Banzhaf indices of hubs in the Lightning network.

  3. 3.

    Explore the correlation between the uniformity of Banzhaf indices and diameter of a channel network.

We use Bitcoin Lightning network data [13] to analyze collusion attacks. Bitcoin lightning network graph [13] provided an API to access the Lightning network data. The downloaded data is in JSON format and RJSONIO package was used to process the data. The data contains (a) information about each node, i.e., public key and (b) network structure as the edge list. The data was accessed on 1st March 2019. It should be noted that the current size of Lightning network is slightly larger. The data contains the network structure of the Lightning network and it has the following properties:

# Nodes

# Edges

Avg. degree

Min. degree

Max. degree

2810

22,596

16

1

961

In the experimental evaluation, we execute Algorithm 1 using the above data as the input. First, we will evaluate the accuracy of Algorithm 1. We have proved that a peer’s Banzhaf index depends on its degree. Greater the degree higher the Banzhaf index. We create a hub network by selecting nodes with a degree in the ranges (30, 100) from the Lightning network data. In this network, we execute Algorithm 1 to estimate the Banzhaf indices of the nodes. The result of such estimation is shown in Fig. 6. It shows that as degree of hubs decreases the Banzhaf index also decreases. Figure 6 provides empirical evidence for the accuracy of Algorithm 1.

Fig. 6
figure 6

The Figure shows the relationship between the Banzhaf index and degree of the nodes (normalized to the range [0, 1])

Full size image

Next, we explore the relation between the diameter of a channel network and the uniformity of Banzhaf indices. We generate 17 hub networks from the Lightning network by selecting nodes with minimum degree 30 and maximum degree \(50,55\dots 135\) respectively. We increase the maximum degree of hub network to increase the diameter of the network (a subgraph of the hub network) as we want to explore the relationship between the Banzhaf index and the network diameter. We use Algorithm 1 to compute Banzhaf indices of all nodes in each such hub network. We observe (shown in Fig. 7) that as we increase the maximum degree of the subgraph generated from the hubs, the diameter of the graph becomes low. As the diameter becomes low it indicates graph converges towards a complete graph. Hence it becomes difficult to generate cuts in such a graph. We keep k (diameter of the collusion graph) as 2 for all datasets. We want to analyze the possibility of collusion within a hub’s immediate neighborhood, hence we use diameter 2 because the average diameter of these graphs is 4.5. The computed Banzhaf indices show that power indices become more uniform as the graph evolves towards a complete graph. It means it difficult to execute collusion attacks in channel network if the diameter of the graph becomes small.

Fig. 7
figure 7

Relation between the Banzhaf index and diameter of the network. The uniformity of Banzhaf increases as the diameter of the network decreases

Full size image

Next, we analyze the vulnerability of Bitcoin Lightning network against collusion attack. We use the following metric to measure such vulnerability per node as:

(6)

We found that there are 62 nodes (shown in Fig. 8) with vulnerability metric at least .9. This means there are 62 nodes who can execute collusion attacks against 90% of their neighbors in the Lightning network.

Fig. 8
figure 8

Vulnerability metric for Lightning network. The left hand figure shows the vulnerability metric for each node in Lightning network and the right hand figure shows the number of neighbours with less Banzhaf index for each node in the Lightning network

Full size image

7 Conclusion

In this paper, we analyzed collision attacks among the hubs of offline channel networks. We have defined the potential for collusion attacks using Banzhaf indices. We have shown the correlation between uniformity of degree of the hub network and Banzhaf indices. Using experiments on Bitcoin’s Lightning network we have shown that as the hub network evolves towards a complete graph it becomes more difficult to create cuts in the graph with a fixed number of edges and hence it increases the uniformity of power indices.