  Many distributed systems are subject to the Sybil attack, where an adversary
subverts system operation by emulating behavior of multiple distinct nodes.
Most recent work to address this problem leverages social networks to establish
trust relationships between users. However, the use of social networks is not
appropriate in all systems, as they can be subverted by social engineering
techniques, require nodes in a P2P network to maintain and be aware of social
network information, and may require overly optimistic assumptions about the
fast-mixing nature of social links.
  This paper explores an alternate approach. We present SybilControl, a novel,
decentralized scheme for controlling the extent of Sybil attacks. SybilControl
is an admission control mechanism for nodes in a distributed system that
requires them to periodically solve computational puzzles. SybilControl
consists of a distributed protocol to allow nodes to collectively verify the
computational work of other nodes, and mechanisms to prevent the malicious
influence of misbehaving nodes that do not perform the computational work. We
investigate the practical issues involved with deploying SybilControl into
existing DHTs, particularly with resilient lookup protocols. We evaluate
SybilControl through simulations and find that SybilControl retains low
overhead and latency. Additionally, even when the adversary controls 20% of the
system's computational resources, SybilControl-enabled DHTs can be configured
to maintain lookup performance at over 99% success rate using low communication
overhead.
