Applying Pebble-Rotating Game to Enhance the Robustness of DHTs

Distributed hash tables (DHTs) are usually used in the open networking environment, where they are vulnerable to Sybil attacks. Pebble-Rotating Game (PRG) mixes the nodes of the honest and the adversarial randomly, and can resist the Sybil attack efficiently. However, the adversary may have some tricks to corrupt the rule of PRG. This paper proposes a set of mechanisms to make the rule of PRG be obliged to obey. A new joining node must ask the Certificate Authority (CA) for its signature and certificate, which records the complete process on how a node joins the network and obtains the legitimacy of the node. Then, to prevent the adversary from accumulating identifiers, any node can make use of the latest certificate to judge whether one identifier is expired with the help of the replacement property of RPG. This paper analyzes in details the number of expired certificates which are needed to store in every node, and gives asymptotic solution of this problem. The analysis and simulations show that the mean number of the certificates stored in each node are [Image: see text], where n is the size of the network.