  Distributed Hash Tables (DHTs) such as Chord and Kademlia offer an efficient
solution for locating resources in peer-to-peer networks. Unfortunately,
malicious nodes along a lookup path can easily subvert such queries. Several
systems, including Halo (based on Chord) and Kad (based on Kademlia), mitigate
such attacks by using a combination of redundancy and diversity in the paths
taken by redundant lookup queries. Much greater assurance can be provided,
however. We describe Reputation for Directory Services (ReDS), a framework for
enhancing lookups in redundant DHTs by tracking how well other nodes service
lookup requests. We describe how the ReDS technique can be applied to virtually
any redundant DHT including Halo and Kad. We also study the collaborative
identification and removal of bad lookup paths in a way that does not rely on
the sharing of reputation scores --- we show that such sharing is vulnerable to
attacks that make it unsuitable for most applications of ReDS. Through
extensive simulations we demonstrate that ReDS improves lookup success rates
for Halo and Kad by 80% or more over a wide range of conditions, even against
strategic attackers attempting to game their reputation scores and in the
presence of node churn.
