Abstract
Nodes in route-restricted overlays have an immutable set of neighbors, explicitly specified by their users. Popular examples include payment networks such as the Lightning network as well as social overlays such as the Dark Freenet. Routing algorithms are central to such overlays as they enable communication between nodes that are not directly connected. Recent results show that algorithms based on spanning trees are the most promising provably efficient choice. However, all suggested solutions fail to address how distributed spanning tree algorithms can deal with active denial of service attacks by malicious nodes. In this work, we design a novel self-stabilizing spanning tree construction algorithm that utilizes cryptographic signatures and prove that it reduces the set of nodes affected by active attacks. Our simulations substantiate this theoretical result with concrete values based on real-world data sets. In particular, our results indicate that our algorithm reduces the number of affected nodes by up to 74% compared to state-of-the-art attack-resistant spanning tree constructions.
Introduction
In route-restricted overlay networks, such as the Lightning Network or the Dark Freenet, the network topology is determined by explicit user-defined connections. Unlike traditional overlays where nodes can connect to any peer, these networks have an immutable set of neighbors. Efficient communication in such large-scale decentralized systems typically relies on constructing a spanning tree—specifically a Breadth-First Search (BFS) tree—to facilitate shortest-path routing between participants.
However, these systems are highly susceptible to Byzantine behavior. A single malicious node can disrupt the entire routing layer by lying about its distance to the root node. In self-stabilizing systems, which are designed to recover from arbitrary initial states or transient faults, such attacks can prevent the network from ever reaching a stable, legitimate state. This results in a persistent Denial-of-Service (DoS) attack. Existing solutions often assume computationally unbounded attackers and avoid cryptography, leading to large "containment areas" where many honest nodes are misled by a few adversaries.
The Signature-based BFS Spanning Tree
To address these vulnerabilities, this research proposes a novel Signature-based BFS Spanning Tree algorithm. By shifting from an information-theoretic model to one that assumes a computationally bounded adversary, the protocol can leverage cryptographic primitives to verify distance claims.
Level Attestation and Link Signatures
The core of the algorithm lies in two mechanisms:
- Level Attestation: Each node maintains a chain of signatures that serves as a proof of its distance from the root. To claim a distance $d$, a node must present a sequence of $d$ signatures from its honest ancestors in the tree.
- Link Signatures: To prevent an attacker from simply "shortening" a valid attestation received from an honest neighbor, the protocol employs neighbor-specific signatures. This ensures that an attacker can, at best, claim to be at the same distance as its honest neighbor, but never closer.
Self-Stabilization and Convergence
The algorithm is designed to be self-stabilizing, meaning it will eventually reach a legitimate state regardless of the starting configuration, provided the root remains honest. To ensure convergence in the presence of multiple valid paths, nodes use a deterministic but adaptive strategy for parent selection, which prevents cycles and oscillation.
Datasets and Evaluation
The resilience of the algorithm was evaluated using four distinct graph topologies. These datasets represent a range of real-world and synthetic network structures, allowing researchers to observe how clustering and degree distribution impact attack containment.
The evaluation included:
- Facebook: A real-world social network graph with 63,392 nodes and high clustering.
- Ripple: A real-world payment network graph with 67,149 nodes and a highly skewed degree distribution (presence of "hubs").
- Randomized Facebook: A synthetic graph maintaining the Facebook degree distribution but with randomized edges to remove clustering.
- Erdös-Renyi (ER): A standard random graph model with normally distributed node degrees.
Key Results and Insights
Simulations demonstrate that the signature-based approach significantly outperforms existing non-cryptographic protocols across all tested topologies.
Resilience Gains
The primary finding is a dramatic reduction in the "containment area"—the set of nodes unable to reach a stable, correct state due to attacker interference. Compared to previous state-of-the-art protocols, this algorithm reduces the number of "lost nodes" by up to 74%. This improvement stems from the "limit of one" principle: while signatures cannot stop an attacker from copying a neighbor's attestation, they prevent the attacker from claiming to be closer to the root than any of its neighbors.
Attacker Effort and Topology
The study also reveals that to achieve the same level of disruption as the non-cryptographic baseline, an adversary would need to establish up to 200 times more connections to honest nodes. Furthermore, network topology plays a critical role. The skewed nature of payment networks like Ripple makes them more vulnerable to hub-based attacks, whereas the high clustering in social networks like Facebook provides honest nodes with more alternative paths, enhancing resilience.
Conclusion and Future Work
This work demonstrates that incorporating cryptographic signatures into self-stabilizing spanning tree algorithms provides a robust defense against Byzantine DoS attacks in route-restricted overlays. While the current model assumes an honest root node with a known public key, it highlights the critical need for secure leader election protocols. Future research will focus on developing decentralized methods to elect reliable, high-degree nodes as roots without subversion by malicious actors, as well as optimizing the computational overhead introduced by cryptographic verification.
Summary updated