On the Limits of Byzantine-tolerant Spanning Tree Construction in Route-Restricted Overlay Networks.
Martin Byrenheid, Stefanie Roos, Thorsten Strufe · arXiv (Cornell University) · 2019
All 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 BFS spanning trees are the most promising provably efficient choice. All suggested solutions, however, fail to address whether and how distributed spanning tree algorithms can deal with Byzantine nodes. Our contribution is twofold. We first show that there is no protocol for route-restricted networks that achieves global consensus on a root node and is tolerant to Byzantine nodes at the same time. Second, we design a novel spanning tree construction algorithm based on cryptographic signatures that provably reduces the set of nodes affected by Byzantine 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 impact of an attack to affect as much as 90% less honest nodes.