|
A Sybil-proof one-hop DHT
Chris Lesniewski-Laas
Abstract
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.
Socialnets 2008 slides:
PPTX
PPT
|
|
