Safeguarding against Sybil attacks via social networks and multipath routing

Peer-to-Peer (P2P) overlay networks are currently being used to build large scale distributed systems running various decentralized applications like distributed storage, content distribution, collaborative scheduling, and leader election. Although we have protocols like Byzantine agreement, voting schemes etc. for building resilient distributed applications; we have very few solutions available for safeguarding these distributed protocols from Sybil attacks. In a Sybil attack, an adversary can forge multiple identities and create multiple, distinct nodes in the system hence overthrowing any upper bound on number of malicious nodes in these protocols. In this paper, we present a multipath routing protocol using graph theoretic approach to group the Sybil nodes first and then to poll them using Host Identity Protocol (HIP) to decide upon whether they really belong to a Sybil group. HIP clearly separates participating users from overlay nodes. It overcomes P2P network challenges like stability over time and identity differentiation. We also use a social network where the attack edges are minimum. An attack edge between a malicious user and an honest user indicates that the malicious user is able to establish a trust relationship with the honest user by some means. We perform simulations to show the feasibility of our distributed protocol.