SybilControl: Practical sybil defense with computational puzzles

Frank Li, Prateek Mittal, Matthew Caesar, Nikita Borisov

Research output: Chapter in Book/Report/Conference proceedingConference contribution

35 Scopus citations


Many distributed systems are subject to the Sybil attack, where an adversary subverts system operation by emulating the behavior of multiple distinct nodes. Most recent works addressing this problem leverage social networks to establish trust relationships between users. However, social networks are not appropriate in all systems. They can be subverted by social engineering techniques, require nodes 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 Sybil-Control, a novel decentralized scheme for controlling the extent of Sybil attacks. It is an admission and retainment control scheme 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 handling churn. SybilControl is shown to provide strict bounds on the size of Sybil attacks, given adversaries with finite resources. We also show through simulations that the performance overhead of enabling SybilControl is manageable using commonplace DHT churn-handling techniques. This provides strong evidence that Sybil-Control can be practically deployed.

Original languageEnglish (US)
Title of host publicationSTC'12 - Proceedings of the Workshop on Scalable Trusted Computing
Number of pages12
StatePublished - 2012
Externally publishedYes
Event7th ACM Workshop on Scalable Trusted Computing, STC 2012 - Raleigh, NC, United States
Duration: Oct 15 2012Oct 15 2012

Publication series

NameProceedings of the ACM Conference on Computer and Communications Security
ISSN (Print)1543-7221


Other7th ACM Workshop on Scalable Trusted Computing, STC 2012
Country/TerritoryUnited States
CityRaleigh, NC

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Networks and Communications


  • Computational puzzles
  • Distributed systems
  • Sybil attack


Dive into the research topics of 'SybilControl: Practical sybil defense with computational puzzles'. Together they form a unique fingerprint.

Cite this