Resisting sybil attack by social network and network clustering

Peer to peer (P2P) systems are extremely vulnerable to Sybil attacks, in which a malicious user controls a large number of Sybil peers to collude to break the system laws. This paper proposes a distributed algorithm, named Sybil Resisting Network Clustering (SRNC), to resist the Sybil attack by preventing honest peers from communicating with Sybil Peers. SRNC is based on a social network model. In this model, honest peers and Sybil peers can be largely classified into two clusters, connected by a small number of edges, called attack edges. SRNC tries to explicitly detect attack edges, and then prohibits the communication over the detected edges. The performance of SRNC is evaluated by theoretical analysis and simulations. In particular, SRNC ensures theoretically that honest peers totally accept O(|AE|) Sybil peers. This is a O(log(n)) times improvement over SybilLimit, one of the conventional representative Sybil resisting algorithms, where n is the number of peers and |AE| is the number of attack edges in the system. The performance is then evaluated by simulations on data sets of real world social networks.