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.

@en

Routing based on greedy network embeddings enables efficient and privacypreserving routing in overlays where connectivity is restricted to mutually trusted nodes. In previous works, we proposed security enhancements to the embedding and routing procedures to protect against denial-of-service attacks by malicious overlay participants. In this work, we propose an improved timeout scheme to reduce the stabilization overhead of secure tree maintenance in response to node failures and malicious behavior. Furthermore, we present an attack-resistant packet replication scheme that leverages alternative paths discovered during routing

@en

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.@en

Current leader election algorithms fail in the presence of Sybil attacks, i.e., one malicious entity inserting many nodes, network dynamics, and restricted knowledge about the graph. However, social overlay networks, i.e., peer-to-peer networks with links corresponding to social relationships, face all of the above challenges. Social overlay networks naturally offer privacy, as they avoid connections with strangers, and furthermore prevent a Sybil attacker from controlling a large number of links in the graph. As recent ideas for scalable communication in such overlays rely heavily on attack resistant leader election, solving leader election for such overlays opens the door for decentralized, privacy-preserving, and secure communication at a large scale. In this work, we propose a novel leader election algorithm based on three-majority voting that utilizes timestamps and cryptographic signatures to detect leader faults in an attack resistant manner. We evaluate our algorithm with simulations on real-world as well as synthetic network topologies. Our results indicate that in networks whose degree sequence follows a power law, our leader election algorithm quickly achieves consensus for more than $80\%$ of all nodes. Furthermore, attackers are unlikely to become leaders as long as the number of connections they establish with honest nodes is low. @en

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@en