Martin Byrenheid

Martin Byrenheid, Stefanie Roos, Thorsten Strufe

Due to its high efficiency, routing based on greedy embeddings of rooted spanning trees is a promising approach for dynamic, large-scale networks with restricted topologies. Friend-to-friend (F2F) overlays, one key application of embedding-based routing, aim to prevent disclosure of their participants to malicious members by restricting exchange of messages to mutually trusted nodes. Since embeddings assign a unique integer vector to each node that encodes its position in a spanning tree of the overlay, attackers can infer network structure from knowledge about assigned vectors. As this information can be used to identify participants, an evaluation of the scale of leakage is needed. In this work, we analyze in detail which information malicious participants can infer from knowledge about assigned vectors. Also, we show that by monitoring packet trajectories, malicious participants cannot unambiguously infer links between nodes of unidentified participants. Using simulation, we find that the vector assignment procedure has a strong impact on the feasibility of inference. In F2F overlay networks, using vectors of randomly chosen numbers for routing decreases the mean number of discovered individuals by one order of magnitude compared to the popular approach of using child enumeration indexes as vector elements.

Martin Byrenheid, Stefanie Roos, Thorsten Strufe

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.