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

Martin Byrenheid, Thorsten Strufe, Stefanie Roos

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

1 Citation (Scopus)


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 publicationProceedings - 2020 International Symposium on Reliable Distributed Systems, SRDS 2020
Subtitle of host publicationProceedings
EditorsC. Ceballos
Place of PublicationPiscataway
Number of pages10
ISBN (Electronic)978-1-7281-7626-0
ISBN (Print)978-1-7281-7627-7
Publication statusPublished - 2020
Event2020 International Symposium on Reliable Distributed Systems (SRDS) - Shanghai, China
Duration: 21 Sep 202024 Sep 2020

Publication series

NameProceedings of the IEEE Symposium on Reliable Distributed Systems
ISSN (Print)1060-9857


Conference2020 International Symposium on Reliable Distributed Systems (SRDS)
Abbreviated titleSRDS 2020


Dive into the research topics of 'Secure Embedding of Rooted Spanning Trees for Scalable Routing in Topology-Restricted Networks'. Together they form a unique fingerprint.

Cite this