Attack resistant Leader Election in Social Overlay Networks by Leveraging Local Voting

Attack resistant Leader Election in Social Overlay Networks by Leveraging Local Voting

Byrenheid, Martin (Technische Universität Dresden)
Strufe, Thorsten (Technische Universität Dresden)
Roos, S. (TU Delft Data-Intensive Systems)

2020

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.

dynamic networks
leader election
peer-to-peer networks
social overlay networks

http://resolver.tudelft.nl/uuid:8607136b-c782-46c2-b93d-91c73e083aa8

https://doi.org/10.1145/3369740.3369770

978-1-4503-7751-5

21st International Conference on Distributed Computing and Networking (ICDCN 2020)

Institutional Repository

conference paper

© 2020 Martin Byrenheid, Thorsten Strufe, S. Roos