Efficient multi-hop sybil-resilient DHT

Abstract

DHTs (Distributed Hash Tables) are data structures over an overlay network, implement- ing e cient insert and lookup of key-value pairs in a decentralized manner. DHTs are subject to the well-known Sybil attack, where an adversary creates many fake identities (known as Sybil nodes) in order to increase its in uence and deny service to the honest participants. Defense against Sybil attack is hard due to the easy identity creation process, absence of admission control, and necessity of out-of-band information for proper clas- si cation. There are heuristic algorithms to detect Sybil nodes using trust relationships in the social networks. But a Sybil-resilient DHT with scalable routing and table size is still missing. In this thesis, we have proposed EMSR (E cient Multi-hop Sybil-resilient DHT), which exploits trust recommendations latent in a social network. Social networks exhibit various properties like densely-connected core, scale-free topol- ogy or community-like structure. Taking these properties into account, in EMSR, we have opted for a hierarchical architecture of regional networks and a global network. Regional networks, representing the clique-like communities, are separate DHTs with a logarithmic and XOR-based localized routing mechanism using linear binary codes as IDs. The global network, representing the densely connected core of the social network, is comprised of the trusted nodes from the regional networks and responsible for inter-community routing. Sybil-resilience is maintained through admission control, where a joiner node uses gossip algorithms to decide if a joining node is trusted enough to be accepted as a super-peer capable to route requests or it should just be a leaf-peer dependent on the joiner node. While existing Sybil-proof DHTs take grossly suboptimal paths in routing, or use large nger tables, our scheme does not su er from such shortcomings. Simulation results follow the theoretical ndings and show signi cant improvement over the existing protocols.