Security Issues - Peer-to-Peer Computing: Applications, Architecture, Protocols, and Challenges - page 164

ing the puzzle is the major barrier in obtaining the admission. The puzzle is
cryptographically safe in the sense that it is based on public key cryptogra-
phy and one-way hash function. Using such an approach, Sybil attack is not
eliminated but just becomes much more resource consuming to launch. Thus,
if a malicious user is equipped with powerful machines or plenty of resources,
a large scale Sybil attack is still possible.
Bazzi and Konjevod [Bazzi and Konjevod, 2005] suggested the use of net-
work coordinates (mentioned in Chapter 4) for honest peers to decide whether
new peers are indeed representing distinct physical users (i.e., having very dif-
ferent network coordinates). However, again if a malicious user can manage
to spoof multiple physical addresses which are then translated into different
network coordinates, the defense is broken.
Yu et al. [Yu et al., 2008] proposed a scheme called SybilGuard, relying
on topological properties of the social network connecting the physical users.
Specifically, based on the social network graph, peers can be logically parti-
tioned into two sets: honest peers and Sybil peers, as shown in Figure 7.3.
Here, the links connecting different nodes representing the declared human
trust relationships. This topology is independent of and could be entirely dif-
ferent from the P2P network topology. Yu et al.'s key insight is that if the
malicious user, controlling a large number of peers, can manifest as a very
strange structure in the social network graph. Specifically, the graph would
have a small quotient cut, i.e., a small set of edges (the attack edges) whose
removal would partition the graph. As observed empirically, a real-life social
network comprising of honest users does not exhibit such a strange property.
Thus, a straightforward method to detect Sybil attack is to search for a quo-
tient cut, or to solve the Minimum Quotient Cut problem. Unfortunately this
problem is known to be NP-hard.

Honest Nodes Sybil Nodes

Attack Edges

FIGURE 7.3: Based on the social network graph, peers can be classified into
honest nodes and Sybil nodes [Yu et al., 2008].

To get around the intractability of the Minimum Quotient Cut problem,
Yu et al. proposed to use verifiable random walk in the social network graph
and the intersections between such walks. Specifically, these random walks
are designed so that the small quotient cut (i.e., the set of attack edges) are
exploited to defend against the malicious user. Consequently, the number of