X-Vine: Secure and Pseudonymous Routing Using Social Networks

Prateek Mittal, Matthew Caesar, Nikita Borisov

Research output: Contribution to conferencePaperpeer-review

25 Scopus citations


Distributed hash tables suffer from several security and privacy vulnerabilities, including the problem of Sybil attacks. Existing social network-based solutions to mitigate the Sybil attacks in DHT routing have a high state requirement and do not provide an adequate level of privacy. For instance, such techniques require a user to reveal their social network contacts. We design X-Vine, a protection mechanism for distributed hash tables that operates entirely by communicating over social network links. As with traditional peer-to-peer systems, X-Vine provides robustness, scalability, and a platform for innovation. The use of social network links for communication helps protect participant privacy and adds a new dimension of trust absent from previous designs. X-Vine is resilient to denial of service via Sybil attacks, and in fact is the first Sybil defense that requires only a logarithmic amount of state per node, making it suitable for large-scale and dynamic settings. X-Vine also helps protect the privacy of users social network contacts and keeps their IP addresses hidden from those outside of their social circle, providing a basis for pseudonymous communication. We first evaluate our design with analysis and simulations, using several real world large-scale social networking topologies. We show that the constraints of X-Vine allow the insertion of only a logarithmic number of Sybil identities per attack edge; we show this mitigates the impact of malicious attacks while not affecting the performance of honest nodes. Moreover, our algorithms are efficient, maintain low stretch, and avoid hot spots in the network. We validate our design with a PlanetLab implementation and a Facebook plugin.

Original languageEnglish (US)
StatePublished - 2012
Externally publishedYes
Event19th Annual Network and Distributed System Security Symposium, NDSS 2012 - San Diego, United States
Duration: Feb 5 2012Feb 8 2012


Conference19th Annual Network and Distributed System Security Symposium, NDSS 2012
Country/TerritoryUnited States
CitySan Diego

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Control and Systems Engineering
  • Safety, Risk, Reliability and Quality


Dive into the research topics of 'X-Vine: Secure and Pseudonymous Routing Using Social Networks'. Together they form a unique fingerprint.

Cite this