http://www.usenix.org/events/nsdi10/ Abstract Wh¯ nau is a novel routing protocol for distributed a hash tables (DHTs) that is efficient and strongly resis- tant to the Sybil attack. Wh¯ nau uses the social connec- a tions between users to build routing tables that enable Sybil-resistant lookups. The number of Sybils in the so- cial network does not affect the protocol's performance, but links between honest users and Sybils do. When there are n well-connected honest nodes, Wh¯ nau can tolerate a up to O(n/ log n) such "attack edges". This means that an adversary must convince a large fraction of the honest users to make a social connection with the adversary's Sybils before any lookups will fail. Wh¯ nau uses ideas from a structured DHTs to build routing tables that contain O( n log n) entries per node. It introduces the idea of layered identifiers to counter clustering attacks, a class of Sybil attacks challenging for previous DHTs to handle. Using the constructed tables, lookups provably take constant time. Simulation results, using social network graphs from LiveJournal, Flickr, YouTube, and DBLP, confirm the analytic results. Ex- perimental results on PlanetLab confirm that the protocol can handle modest churn.