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.
