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.”


3 Responses to “Follow-up: “A Sybil-proof one-hop DHT””

  1. Sounds like a very worthwhile paper to read. Social networks do sound like a promising approach to Sybil attack resistance. One tricky issue, however, with anonymity networks is that you might not want to leak information about your social networks.

    For example, suppose you’re running an anonymity network and want to stop the secret police taking over lots of nodes. If you require everyone to register their friend-links before joining, you might be able to stop a Sybil attack, but what about privacy?

    Someone snooping on the wire, or an active adversary can build a social network from a recently arrested dissident, the police can find lots more.

    Now, communicating with someone doesn’t indicate that you have probably related IP addresses, or public keys, but ideologies, which is far more dangerous information to leak.

  2. Believer said

    I’ve just check the paper and It just adopted the “unreasonable” assumptions from SibilLimit. Assuming that a system will have always (n/log n) attack edges.

    Everybody writes that, but no proofs.

  3. […] social networks of recsys websites, which aren’t that big and may well be not fast mixing (controversial assumptions made by […]

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: