# Application of Graph Theory for Blockchain Technologies
## 5 Graph Theory Application in Blockchain Systems
### Evaluating Security and Privacy
#### 5.2.2 Threat Modelling
A phishing attack targets a subset of nodes \(V_{p}\subseteq V\) where the attacker attempts to compromise the private keys of these nodes through deceptive communication. The success of phishing on each node depends on \(p(v)\), the phishing susceptibility of the node. Compromise Propagation. Once a node's key is compromised (\(k(v)=C\)), the attacker can utilize this node to further propagate the attack within the network, increasing the reach of the phishing campaign. Representation of the Attack's Impact  
* Initial Compromise Set \(V_{c0}\): The set of nodes initially targeted and successfully compromised by the phishing attack. * Propagation Function \(F\): A function that models how the attack propagates through the network from the initial set of compromised nodes. * Total Compromised Set \(V_{c}\): The set of nodes that are eventually compromised as a result of both the initial attack and subsequent propagation. \(V_{c}\) is derived by applying \(F\) to \(V_{c0}\) and the network \(G\). * Network Vulnerability Index (NVI): A metric to quantify the overall impact of the phishing attack on the network. It is given by: \[\text{NVI}(G) = \frac{|V_{c}|}{|V|}\times\left(1+\sum_{v\in V_{c}}\text{ centrality}(v)\right)\]  
Figure 8 represents a model of a blockchain network under the threat of phishing attacks. Nodes represent network participants, color-coded based on their key status: nodes in red have compromised keys (C), while nodes in green have secure keys (S). Edges represent potential communication channels through which phishing attacks can be propagated or through which information is exchanged among participants. The network includes both initially targeted nodes for phishing attacks (selected based on a higher susceptibility to phishing) and nodes that may potentially be compromised through network propagation. This graph-theory-based simulation illustrates the dynamics of phishing attacks within a network, highlighting the importance of understanding both the structural vulnerabilities and behavioral aspects that make nodes susceptible to phishing. By analyzing such models, network administrators and blockchain protocol designers can develop strategies to detect and mitigate the risk of key compromise through phishing attacks, thereby enhancing the overall security and resilience of the network. BGP hijacking affects the routing on the Internet by maliciously rerouting traffic through an attacker-controlled system. In blockchain networks, full nodes play a critical role in maintaining the network's integrity. If these are compromised, the reliability of the lightweight nodes that depend on them can also be compromised, leading to spatial partitioning within the network. **Assumption 8**. :
* _We assume a graph_ \(G=(V,E)\)_, where:_
* _V: Set of nodes, partitioned into full nodes_ \(V_{F}\) _and lightweight nodes_ \(V_{L}\)_, such that_ \(V~{}=~{}V_{F}\cup V_{L}\) _and_ \(V_{F}\cap V_{L}~{}=~{}\emptyset\)_._
* _E: Set of directed edges representing communication links, with_ \(E_{F}\) _representing links between full nodes and_ \(E_{L}\) _representing links from full nodes to lightweight nodes._
* _Node Status_ \(s(v)\)_: Indicates whether a node is secure (S) or compromised (C)._
* _Routing Path_ \(R(u,v)\)_: Ordered list of nodes a message traverses from_ \(u\) _to_ \(v\)_._  
**Application Statement 8**. :
* _In a blockchain network subject to BGP hijacks, if an attacker compromises a subset of full nodes_ \(V_{FC}\subseteq V_{F}\)_, it can induce a spatial partitioning where the associated lightweight nodes_ \(V_{LC}\subseteq V_{L}\)_, which rely on compromised full nodes, are also controlled by the attacker._  
Proof. :
* BGP hijacking Initiation: Attacker gains control of one or more full nodes \(V_{FC}\) by diverting their incoming and outgoing routing paths. For all \(v\in V_{FC}\), \(s(v)\) changes from S to C.
* Routing Path Alteration: The routing paths \(R(u,v)\) for \(u\in V_{F}\) and \(v\in V_{L}\) are altered to pass through \(V_{FC}\), if not already.