Secure Embedding of Rooted Spanning Trees for Scalable Routing in Topology-Restricted Networks

Research output: Contribution to book/conference proceedings/anthology/reportConference contributionContributedpeer-review



Greedy embeddings on rooted spanning trees are the most promising solution to provide sufficiently scalable routing in dynamic networks with restricted topologies, for instance friend-to-friend overlays such as the Dark Freenet and payment channel networks such as Lightning. Yet, they are not deployed in practice, as electing a root and configuring addresses remains an unsolved problem in adverse environments. Indeed, faulty or malicious nodes might provide incorrect coordinates, prevent the network from stabilizing by simulating dynamics, or not start the assignment of coordinates in their subtree at all. All of the above attacks may result in an inability to route. To mitigate the above attacks, we design a novel embedding algorithm with an adapted distance metric that only relies on interconnections between benign subtrees for successful delivery. In other words, even if roots of (sub-)trees are malicious or faulty, the remaining nodes still receive coordinates and can communicate with nodes in their tree branch as well as other branches reachable via the neighborhood of their benign ancestors. Extensive simulations demonstrate that we thus facilitate efficient routing even when seemingly decisive parts of the network are under adversarial control.


Original languageEnglish
Title of host publication2020 International Symposium on Reliable Distributed Systems (SRDS)
PublisherWiley-IEEE Press
Number of pages10
ISBN (print)978-1-7281-7627-7
Publication statusPublished - 24 Sept 2020


Title2020 International Symposium on Reliable Distributed Systems
Abbreviated titleSRDS 2020
Conference number39
Duration21 - 24 September 2020

External IDs

Scopus 85097759201



  • Network topology, Lightning, Routing, Reliability engineering, Routing protocols, Topology, Resilience