Attack-resistant Spanning Tree Construction in Route-Restricted Overlay Networks

Martin Byrenheid, Stefanie Roos, Thorsten Strufe

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

2 Citations (Scopus)
25 Downloads (Pure)


Nodes in route-restricted overlays have an im-mutable set of neighbors, explicitly specified by their users. Pop-ular examples include payment networks such as the Lightningnetwork as well as social overlays such as the Dark Freenet.Routing algorithms are central to such overlays as they enablecommunication between nodes that are not directly connected.Recent results show that algorithms based on spanning treesare the most promising provably efficient choice. However, allsuggested solutions fail to address how distributed spanning treealgorithms can deal with active denial of service attacks bymalicious nodes.In this work, we design a novel self-stabilizing spanning treeconstruction algorithm that utilizes cryptographic signatures andprove that it reduces the set of nodes affected by active attacks.Our simulations substantiate this theoretical result withconcretevalues based on real-world data sets. In particular, our resultsindicate that our algorithm reduces the number of affectednodes by up to 74% compared to state-of-the-art attack-resistantspanning tree constructions
Original languageEnglish
Title of host publicationProceedings - 2019 IEEE 38th International Symposium on Reliable Distributed Systems, SRDS 2019
Number of pages10
ISBN (Electronic)0769567118, 9781728142227
Publication statusPublished - Oct 2019
Event38th Symposium on Reliable Distributed Systems - Lyon, France
Duration: 1 Oct 20194 Oct 2019
Conference number: 38

Publication series

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


Conference38th Symposium on Reliable Distributed Systems
Abbreviated titleSRDS 2019


  • Attack resistance
  • Availability
  • Route restricted overlays
  • Spanning tree construction
  • Sybil attacks


Dive into the research topics of 'Attack-resistant Spanning Tree Construction in Route-Restricted Overlay Networks'. Together they form a unique fingerprint.

Cite this