Follow-up: “A Sybil-proof one-hop DHT”
26 March 2008
The previous post, pointing fingers at papers making unreasonable assumptions about Distributed Hash Tables, created a bit of controversy in the Cambridge Security group mailing lists. One of the most valid comments (made by Steven Murdoch over and Indian meal) was that no one knows how to secure systems against Sybil attacks. A few years ago Chris Lesniewski-Laas, M. Frans Kaashoek, Ross Anderson and myself worked on using social links between peers to aleviate the sybil attack in DHTs. The proposed solution was cumbersome, but the idea was clearly worth pursuing.
I am most glad to see that Chris Lesniewski-Laas has worked further on these ideas, and will be presenting a paper on the topic very soon:
A Sybil-proof one-hop DHT.
Chris Lesniewski-Laas. To appear. In Proceedings of the Workshop on Social Network Systems, Glasgow, Scotland, April 2008.
“Decentralized systems, such as structured overlays, are subject to the Sybil attack, in which an adversary creates many false identities to increase its influence. This paper describes a one-hop distributed hash table which uses the social links between users to strongly resist the Sybil attack. The social network is assumed to be fast mixing, meaning that a random walk in the honest part of the network quickly approaches the uniform distribution. As in the related SybilLimit system, with a social network of n honest nodes and m honest edges, the protocol can tolerate up to o(n/log n) attack edges (social links from honest nodes to compromised nodes). The routing tables contain O(√m log m) entries per node and are constructed efficiently by a distributed protocol. This is the first sublinear solution to this problem. Preliminary simulation results are presented to demonstrate the approach’s effectiveness.”