introduction

introduction

The peer-to-peer (p2p) computing paradigm has many advantages over other traditional paradigms. For example, resources such as bandwidth, memory, and data are available to all other participating users [1]. Broadly speaking, this paradigm includes both structured and unstructured systems. Structured overlays (such as Kademlia [2] and Chord [3]) provide deterministic mechanisms for data and peer discovery, while unstructured overlays (such as Gnutella [4]) organize peers in a random graph and use pan Hung algorithm for peer and data discovery. Most popular peer-to-peer systems lack a "central authority", which makes this paradigm resistant to fault attacks. On the other hand, the lack of such a centralized authority leads to many challenging security issues: most of the security services required to protect networked systems require one or another centralized authority, making these services unusable by peer-to-peer systems [5]]. Worse, the fully decentralized and open nature of many of these systems has led to a wide range of unknown security threats in other distributed systems, including Sybil attacks [6].

Sybil attacks are well known in peer-to-peer, wired and wireless network environments. In its basic form, a peer representing an attacker generates as many identities as possible and behaves as if she is multiple peers in the system [6], designed to interfere with the normal behavior of the system. The number of identities an attacker can generate depends only on the attacker's ability, which is limited by the bandwidth required to respond to concurrent requests from other peers in the system, storing the routing information of the node corresponding to each generated Sybil identity. memory required, and the computing resources required to process concurrent requests without noticeable delay. With the dramatic growth of hardware (e.g., in terms of storage capacity and processing) and the widespread spread of broadband Internet with high bandwidth rates, even attackers running on general-purpose hardware can cause significant damage to large systems.

Sybil attacks occur in many contexts, as are common on peer-to-peer systems and other general distributed systems and paradigms that are essential to mine services. Such environments include voting systems, reputation systems, routing, distributed storage, and more. To illustrate how this attack works in a real-world system, imagine a recommender system built on peer-to-peer overlays [7]. In such systems, the goal of the system is to filter out information that may be of interest to the user based on recommendations from others. In this case, an attacker who can impersonate multiple users by forging multiple identities (Sybil) can easily vote on legitimate objects that legitimate users voted for.

In any realistic recommender system, it is almost guaranteed that the number of legitimate users who usually vote on an object is always no more than 1% of the total users of the system [7]. Given this, this attack is attractive to attackers, who are potential users of the system trying to attack systems that provide high incentives. The online marketplace eBay, for example, uses customer testimonials to determine the reputation of its sellers, those who use its platform to sell goods, so it is tempting for such sellers to engage in misconduct to gain a higher reputation. The same happens in many other situations, such as peer-to-peer file sharing where content is rated by users, bandwidth allocation based on reputation, and in this case, even reputation being used to determine the quality of content distributed by users. bad. In all such examples, there is an incentive for users to misbehave, and the Sybil attack has proven to be a powerful tool for such attackers to achieve their goals.

To defend against attacks, several forms of defense or mitigation have been attempted to defend against or limit the impact of attacks. Such attacks can be broadly divided into two schools of thought: centralized and decentralized (i.e. distributed) defenses. In centralized defenses [6, 8, 9, 10], a central authority is responsible for verifying the identity of each user in the system. While this defense is somewhat effective in defending against attacks, it makes certain assumptions about the system, some of which are not easily implemented in a peer-to-peer decentralized system. First, as the name and operational description suggest, such systems require a centralized authority, which may not be affordable for many for security and functionality reasons. Furthermore, even in the presence of such a centralized authority, some credentials related to users in the system are needed in order to match those credentials of a user with their digital identities: obtaining such credentials is very challenging in many cases.

On the other hand, decentralized defenses include but are not limited to the work in [11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 7, 21, 22, 23], which do not require Centralized authority and carefully designed for decentralized peer-to-peer systems. At the core of their operation, such defenses weigh collaboration among users in the system to admit or reject users who might be attackers. Admission or rejection of users is based on credentials associated with the user, as in the case of encrypted distributed defenses, or network attributes of legitimate honest users, as in the case of Sybil defenses using social graphs. In either solution, the ultimate goal of the defense is to simulate the power of a central authority in a decentralized manner, and use this power to detect witches and honest nodes.

Another classification of a defense might be based on how that defense works. Therefore, in previous work, Sybil defenses can be divided into defenses using trusted certificates - where certificates are usually generated for honest users and verified against public keys of trusted authorities, incurring costs - where users are subject to some cost punishment, thereby limiting the amount of resources available to them, reducing their misbehavior, and social network-based Sybil defense.

first level title

2. Sybil attack model and goals

In this section, the attacker model commonly assumed in most Sybil attack research and defenses is elaborated, further exploring the attacker's goals and defense goals.

2.1 Problem statement and model

The problem is formulated as a single user in the system having an ability in the system that allows her to act as if she has multiple copies. This is problematic for so many applications, since the correctness of such applications depends on the behavior of peers, their number, and willingness to participate honestly in collaboration in the system. However, the sybil identity of a single attacker trying to bias the behavior of the system as a whole cannot satisfy such system goals.

An attacker is formally characterized by the number of false identities she can inject into the system. The motivation of the attacker is to maximize the number of false identities. The value and significance of the number of identities an attacker generates and injects into a system depends on the application itself and varies from application to application. For example, to attack a recommender system, it is enough to have the sum of matches from 1% of honest users in the system as fake identities. Since it is commonly observed that even for very popular objects in this system, only 1% of honest nodes vote for it, this in particular is a strong enough factor to bias the behavior of the system and outrank honest nodes in the system. That is, by having more single identities than the exact number of honest nodes voting for an object in the system, Sybil attackers will be able to overtake the votes of honest nodes.

On the other hand, in other systems, such as hybrid networks used to anonymize communications (such as the Tor network), even a small amount of sybil identity can seriously undermine the promises in the system. Theoretically, the compromise of two nodes on a circuit is sufficient to identify the sender and receiver of a communication on such a hybrid network [24]. On the other hand, the compromise of enough identities in the network will enable an attacker to monitor any number of circuits. Other applications where the number of identities itself is important include attacks on file-sharing systems [25], to name a few.

Figure 1 Several different ways of Sybil defense in a P2P superimposed environment

C/CA stands for Centralized Certification Authority

D/C stands for Decentralized Cryptographic Primitives

T/D stands for Trusted Device Authentication

IP/T stands for IP detection

R/C stands for cost cycle based detection

S/G stands for social graph based defense

2.2 Objectives and success criteria of Sybil Defense

The ultimate goal of sybil defense is to eliminate sybil attacks by detecting and isolating sybil identities in the overlay network, or those peers capable of generating those sybil identities. However, this ultimate goal cannot always be achieved, because most defenses, except those based on centralized trusted authentication, have the possibility of false positives and false negatives in their detection mechanisms, which may Some sybil nodes are tolerated while falsely reporting other honest nodes, as we have seen with false positive and false negative reporting. A false positive report is when a Sybil node is reported as an honest node. On the other hand, false negative honest nodes are reported as Sybil nodes. A realistic and practically achievable goal of defense mechanisms is to reduce the false negative rate as much as possible.

2.3 Depth of Witch Defense

first level title

3. Use trusted certificates

The trusted authentication method is arguably one of the most popular methods nowadays, as Douceur [6] has demonstrated its potential to eliminate Sybil attacks [26]. In the traditional form of this approach, a centralized authority (CA) is used to ensure that the identities assigned to each peer are unique and legitimate by matching these identities with pre-assigned credentials. These credentials may include encryption keys, synchronous random strings typically generated by a one-time password generator (OTP), or digital certificates issued by a centralized authority.

While the traditional forms of centralized certificate authorities described above are well defined in the literature, distributed certificate schemes have been defined by applying cryptographic primitives suitable for distributed multi-party models that enable Collaborate to attest to other peers joining the overlay.

3.1 Centralized Certification Authority

Centralized trusted authentication may be the only way to eliminate Sybil attacks [6]. In the context of P2P coverage, there has been some work on using centralized certificate authorities for credential generation, distribution, and verification. For example, studies using the social graph explained in Section 5 and utilizing public-key cryptography as a building block assume that the authenticity of a user's public key is passed through a certificate assigned to the user through a centralized authority in the offline phase [19]. Examples of other schemes utilizing CCA-based methods include the work in [8], [9], [6], and [10].

3.2 Cryptographic primitives

Recently, several works on cryptographic primitives have emerged [11, 12, 13, 14, 15]. These primitives are intended to provide the infrastructure for validating peers in order to make it harder for Sybil attacks to occur by only having legitimate peers participate in the overlay. Typically, these efforts attempt to leverage public key infrastructure (PKI) in a decentralized manner and use threshold cryptographic components (e.g., secret sharing and threshold signatures) to ensure collaboration among so-called honest users to authenticate joins overlaid on The operation time of the peer. Interestingly, explicitly stated motivations go beyond some of these primitives (e.g., [11, 12, 13, 14]), since many non-cryptographic protocols in the literature assume the existence of an authentication system to cover legitimate users ( such as SybilGuard and SybilLimit). Therefore, encryption methods are designed to ensure the successful operation of such protocols.

3.3 Trusted Devices

first level title

4. Resource testing

In addition to the resource testing method used to defend against Sybil attacks, the basic idea is to check whether a set of identities associated with supposedly different users has enough resources to match the number of identities. These resources may include computing power, bandwidth, memory, IP addresses, and even trust credentials. Although Douceur proved the resource testing idea to be invalid [6], some researchers consider it a minimal defense. That is, this method does not completely eliminate the attack, but it makes it harder for Sybil attacks to occur.

In theory, most schemes in such defenses limit the number of witch identities to a smaller number than would be the case without the defense. In practice, however, even a smaller number of witch identities is enough to threaten the usability and security of many systems. For example, as mentioned earlier, anonymity in an anonymous system such as Tor depends on two nodes per circuit. Additionally, 1% of fake identities in an online reputation system are enough to vote for legitimate nodes.

4.1 IP test

A common testing scenario involves testing the IP addresses of peers in an attempt to determine their location and match this to their activity. In particular, if a significant amount of activity emanates from the same specific geographic area, some of that activity is likely due to witchhood. Also, the assumption in such works is to obtain IP addresses for different geographical regions, which is not cheap. For example, Friedman et al. [29] introduce Tarzan, where a node's IP address is tested based on its geographic location within a particular autonomous system. Similar results were presented by Cornelli et al. in [30] and [30].

The main assumption of these works is that IP addresses are difficult to obtain in a wide geographic area. However, with recent indications of the existence of gigantic botnets [31] with infected hosts controlled by a single administrative entity and residing in different autonomous systems, it is certain that this defense mechanism is useless.

4.2 Cost cycle

Several studies and practices suggest recurring costs as a defense against Sybil attacks. In particular, computational puzzles [16, 32] and Turing tests (e.g. CAPTCHA [33]) are suggested as solutions. However, by the same token that IP testing will not work against attackers controlling botnets, neither will these cost-based schemes. Additionally, for CAPTCHA-like solutions, it has been shown that Sybil attackers may publish CAPTCHA tests on controlled sites for users to test access to attacker-provided services.

first level title

5. Defense based on social graph

While most of the previously proposed solutions to the problem of sybil attacks in distributed systems have limitations and shortcomings, social network-based sybil defense attempts to overcome these problems in an elegant manner. First, social network-based Sybil defenses are mostly decentralized solutions to the Sybil attack problem, meaning that these designs operate without any central authority—an important property in most distributed systems. This decentralized model of operation is made easier thanks to random walk theory, the most commonly used ingredient in these defenses. Second, these defenses leverage the trust of social links between social nodes to make collaboration among honest nodes possible and easy. Third and finally, these defenses have been proven in several studies to be practical and effective against Sybil attacks at low cost, and they are now further developed as components of many services, including Distributed Hash Tables (DHT) , anti-Sybil voting, and for mobile network routing.

Although they differ greatly in design details and operations, all social network-based Sybil defenses share two common assumptions: algorithmic properties, i.e., fast-mixing properties, and trust. First, these defenses are based on the "rapid mixing" property of social graphs. Informally, the fast-mixing property of social graphs means that "honest" nodes in such graphs mesh well, and that honest regions do not contain sparse cuts - a method that connects two large subsets of honest nodes with some social network cut up. For simplicity, the fast-mixing nature of the social graph means that a random walk from any node in the social graph will closely approximate the stationary distribution of the Markov chain (MC) defined on the graph after a few steps. In a network of millions of nodes, the recommended number of such steps is 10 to 15 steps.

The second common assumption in this defensive vein is trust. In particular, all of these defenses assume good trust values ​​in the underlying social graph, e.g., as evidenced by face-to-face interactions between nodes. This particular assumption is necessary in order to infer the difficulty of penetrating a social network with an arbitrary number of attackers' social links. While the operation of the Sybil defense for correctly identifying "honest" nodes in a social graph is guaranteed by the fast-mixing assumption, and the construction of corresponding schemes using this algorithmic property, the ability to identify Sybil nodes is only guaranteed under the assumption that An attacker, or a collective of attackers, controls some links between itself and other honest nodes in the social graph (such links are called attack edges).

Below we sort out some of the widely cited and concerned approaches to Sybil defense based on social networks.

5.1 Sybil Guard

The design of SybilGuard, attributed to Yu et al. [19, 20], uses the fast-mixing properties of trust-owned social networks to detect Sybil nodes. Technically, SybilGuard consists of two phases: an initialization phase and an online detection phase. During the initialization phase, each node builds its routing table as a random permutation of its neighbors for input and output edge pairs. Next, each node starts a random walk of length w = O(root n log n) and propagates it to its neighbors according to the routing table built using random permutations. Every node on the random walk path will register as a witness of the initiator of the random walk, and then act as the witness of the node when the node becomes a suspect node. In addition, taking advantage of the retrospective nature of the random walk, each initiator of the random walk will receive a list of "witnesses" (that is, nodes that register the initiator's public key and are located on the path constructed by the initiator's random walk).

In the online phase, the verifier determines whether the suspect is honest, as follows. First, the suspect sends the address of a "witness" on its random route to the verifier. Therefore, the validator compares the witness list with its validator routing list. If there is no intersection between the two sets (a very likely event), the verifier will abort and reject the suspect. Otherwise, the verifier will continue, asking to compare nodes on the intersection between the two sets to verify that the suspect registered with their public key. If the suspect is verified by cross nodes, the validator accepts the suspect or marks it as a Sybil node.

5.2 Sybil Limit

Unlike SybilGuard, which uses a single long random walk, SybilLimit suggests multiple shorter random walks. Furthermore, unlike SybilGuard (where the public keys of verifiers and suspects are registered on nodes in the social graph), SybilLimit [18] proposes to register such keys on edges in the social graph. SybilLimit consists of an initialization phase and an online verification phase .In the initialization phase, each node builds its routing table using the same method described in SybilGuard, and performs random walks of r = O(root n), each time of length w = O(log n) where O(log n) is 10 to 15 social graphs of mixed temporal social graphs, theoretically assumed to be sufficient to sample nodes from a distribution very close to the statistical distribution. Unlike SybilGuard, all nodes on a random routing path are used to register random walk initiators , the last edge of each of the r random walks is used to register the public key of the originator node (each such edge is called a tail). In particular, the public key of the originator of the walk registers At the last node under the last edge reached by the random walk. Also using the retrospective nature of random routing, witnesses who register the public key of the initiator node (which can be a suspect or verifier) ​​return their identity to the node .Each node in the social graph performs the same process, and each node that initiates a registered random walk gathers a set of witnesses (or validators).

In the online phase, SybilLimit is also the same as SybilGuard, the suspect sends the identifier and address of the witness to the verifier node, which will compare the witnesses in the list of suspects, trying to find a conflict. If a conflict occurs in the two sets on the verifier's side, the verifier asks witnesses with a common identity in both sets to verify the suspect's identity, and decides whether to accept or reject the suspect based on the outcome of this process. If there is no intersection between the two (which is very unlikely to happen) the validator aborts and rejects the suspect by marking it as an attacker.

The principal components of the provable guarantees used to reason about SybilLimit are the same as in Sybil Guard. In particular, assuming that the random walk length w is the mixing time of the social graph, then the last node selected in such a random walk is according to a stationary distribution.

Furthermore, the last edge in the random walk is chosen "almost" uniformly randomly from among the edges in the social graph. Furthermore, assuming r = O(root n), if the hidden constant r0 (where r = r0 × root n) is chosen correctly, the intersection between the sampled edges of the verifier and suspect will exist with overwhelming probability . The authors refer to this condition as the "intersection" condition, which is used to guarantee high-probability intersection of random walks of nodes in the honest region. Like SybilGuard, assuming there are g attacker edges, the attacker is allowed to register the public key of his Sybil identity on at most gwr = O(g × root n × log n) tails (called taint tails). In this case, each additional edge introduces an additional O(log n) Sybil identities (assuming the attacker uses an optimal attack strategy by registering different public keys of different Sybil identities with each possible tainted tail).

The safety of SybilLimit also relies heavily on w. Since there is no mechanism for estimating the exact value of parameters, underestimating or overestimating these parameters is problematic, as shown above. SybilLimit also provides a "benchmarking technique" for estimating this parameter, which also does not provide any provable guarantees about the quality of the parameter estimate. Finally, Sybil Limit guarantees the number of sybil identities introduced per attack edge as long as g = o (n / log n). Note that neither SybilGuard nor SybilLimit require any global knowledge of the social network it operates on, and can be implemented in a fully decentralized fashion.

5.3 Sybil Infer

SybilInfer uses a probabilistic model defined on random walks (called trajectories) to infer how realistic a set of nodes X is that generates such trajectories. The basic assumption in SybilInfer is that each node has a global view and knowledge of the social network, the network is rapidly mixed, and the node that initiates SybilInfer is an honest node. Technically, SybilInfer tries to eventually label different nodes in the graph as honest nodes or sybil nodes. In SybilInfer, each node in a network of n nodes performs s walks, so the total number of walks in the general trace is s × n. Each of these traces consists of the first node (the initiator of the random walk) and the last node in the random walk (the tail). Unlike the uniform (exceeding node degree) transition probabilities used in SybilGuard and SybilLimit, SybilInfer defines a uniform transition matrix on nodes, penalizing nodes with higher degrees. The ultimate goal of the SybilInfer operation is to compute the probability P (X = Honest | T); that is, to compute the probability that a set of nodes X given a trajectory T is honest. This probability is calculated using Bayes' theorem.

SybilInfer samples the honest configuration by technical means, which was originally used to determine the honesty of a set of nodes from the trace. This sampling is performed using the Metropolis-Hasting algorithm, which first considers a set X0 and modifies the set one at a time by removing or adding nodes to the set: at each time, with probability a new node x is added from X¯0 to X0 so that X ′ = X0 [x or nodes in X0 are deleted with probability premove. The procedure performs n × log n rounds to obtain good samples independent of X0.

5.4 Sum Up

Unlike SybilGuard and SybilLimit which are generic node admission problems and decentralized in the sense that individual nodes are not required to carry global information about the social graph, and Sybil-Infer for inferring node honesty, SumUp [35] attempts to address Solving Sybil Attacks in the Context of Vote Aggregation. In this case, a node called a vote collector wishes to collect votes from other nodes in the network in a Sybil-resistant manner. That is, for a given number of object votes, vote collectors wish to increase the proportion of votes accepted by honest nodes, reduce the number of accept votes cast by attackers through their attack edges, and identify attackers when they repeatedly misbehave . At the core of SumUp, the link capacity allocation mechanism is used to adaptively allocate capacity to links in the trust-owned social graph and limit the number of votes propagated from the voter's side to the vote collector. SumUp's adaptive voting streaming mechanism uses two observations of traditional online voting systems: a small number of users in the system vote on a single object, and - if such a voting system is implemented on top of a social graph - congestion only Appears on the chain close to the vote collector. Therefore, SumUp proposes to distribute a large number of tickets over different links in the social graph according to their distance from the voting collector (according to some level calculated using a breadth-first search algorithm).

An obvious appeal of the technique lies in its high computational requirements: the running time of a typical algorithm (such as the Ford-fulkerson algorithm) will require an order of the number of edges to be manipulated to collect the votes of a single voter. Its authors further propose a heuristic using only the order of graph diameter steps, where each node greedily selects a higher-level node through which to connect using non-zero capacity and propagate votes until a vote is reached collector. At any time, each node is allowed to explore other nodes for paths of the same or lower rank, taking into account that the greedy step may not result in a non-zero capacity.

5.5 GateKeeper

GateKeeper [21] borrows tools from SumUp and SybilLimit to achieve efficient operation. In particular it attempts to improve the performance of SybilLimit by incorporating SumUp's ticket distribution component. Unlike in SumUp, where nodes are admitted via non-zero paths from voters to collectors, as mentioned earlier, GateKeeper only considers the "ticket allocation" phase of SumUp, where tickets are used by admission controllers to admit nodes. Such tickets are propagated from the controller to all nodes in the same way as in SumUp. However, to limit the attacker's chances of getting more tickets and reduce its overall advantage, the controller in GateKeeper randomly selects m different random nodes; these nodes are called "favorable nodes" if and only if It will only be allowed if the vantage point receives a fadmitm ticket (where fadmit is the fraction of a randomly selected vantage point; 0.2 is used in GateKeeper). Therefore, once a node is allowed by a fraction of this vantage point, it is allowed. To prevent double-spend attacks, Gate Keeper proposes to use the chain of cryptographic signatures of the ticket's path (propagated to the controller).

5.6 Other DHTs based on social networks

SPROUT [36] is another DHT routing protocol that uses social links with a trusted social graph to route information to users operating on social networks. SPROUT is actually built on top of Chord [3], and in Chord adds additional links (routing table entries) to other users in any given node's social network that are online at any time. By doing this, SPROUT claims to improve the reliability and load distribution of the Chord itself.

Whanau was originally proposed in [23], where the work in [22] includes further analysis and proofs of performance and security as well as implementation and demonstration of end-to-end guarantees.

In [1], the authors use bootstrap graphs - trees showing the relationships introduced in the DHT to defend against Sybil attacks. By modifying the operation of the DHT Chord of interest so that each node returns the addresses of all nodes it knows (including points of entry), the authors devise several strategies for reducing the impact of Sybil attacks. Unlike the original Chord which uses proximity on Chord as a routing (query) metric, this solution considers multiple routing strategies including diversity, hybrid and zig-zag. The authors show experimentally that such a strategy can be used to perform Sybil-resistant DHT lookups more efficiently when operating under a Sybil attack, and that it will require fewer queries than would be required for a vanilla Chord design.

6 Conclusion

6 Conclusion

Voting Progress: DAO Committee 4/7 passed

DAOrayaki DAO Research Bonus Pool:

Funding address: 0xCd7da526f5C943126fa9E6f63b7774fA89E88d71

Voting Progress: DAO Committee 4/7 passed

Total bounty: 170 USDC

Types of research: DAO, Social networks, Sybil defenses, Survey

Original Author: Aziz Mohaisen, Joongheon Kim

Contributors: Natalie, DAOctor @DAOrayaki

references:

references:

[1] George Danezis, Chris Lesniewski-laas, M. Frans Kaashoek, and Ross Anderson. Sybil-resistant dht

routing. In In ESORICS, Lecture Notes in Computer Science, pages 305–318, Berlin, Heidelberg, 2005. Springer.

[2] Petar Maymounkov and David Mazi`eres. Kademlia: A peer-to-peer information system based on the xor metric. In Peter Druschel, M. Frans Kaashoek, and Antony I. T. Rowstron, editors, IPTPS, Lecture Notes in Computer Science, pages 53–65, Berlin, Heidelberg, 2002. Springer.

[3] Ion Stoica, Robert Morris, David R. Karger, M. Frans Kaashoek, and Hari Balakrishnan. Chord: A scalable peer-to-peer lookup service for internet applications. In SIGCOMM, pages 149–160, New York, NY, USA, 2001. ACM.

[4] Yong Wang, Xiao chun Yun, and Yifei Li. Analyzing the characteristics of gnutella overlays. In ITNG, pages 1095–1100, Washington, DC, USA, 2007. IEEE Computer Society.

[5] Vivek Pathak and Liviu Iftode. Byzantine fault tolerant public key authentication in peer-to-peer

systems. Computer Networks, 50(4):579–596, 2006.

[6] John Douceur and Judith S. Donath. The sybil attack. In IPDPS, pages 251–260, Washington, DC, USA, 2002. IEEE.

[7] Haifeng Yu, Chenwei Shi, Michael Kaminsky, Phillip B. Gibbons, and Feng Xiao. Dsybil: Optimal sybil-resistance for recommendation systems. In IEEE Symposium on Security and Privacy, pages 283–298, Washington, DC, USA, May 2009. IEEE Computer Society.

[8] Miguel Castro, Peter Druschel, Ayalvadi J. Ganesh, Antony I. T. Rowstron, and Dan S. Wallach. Secure routing for structured peer-to-peer overlay networks. In OSDI, Berkeley, CA, USA, 2002. USENIX Association.

[9] Atul Adya, William J. Bolosky, Miguel Castro, Gerald Cermak, Ronnie Chaiken, John R. Douceur, Jon Howell, Jacob R. Lorch, Marvin Theimer, and Roger Wattenhofer. Farsite: Federated, available, and reliable storage for an incompletely trusted environment. In OSDI, New York, NY, USA, 2002. USENIX Association.

[10] Jonathan Ledlie and Margo I. Seltzer. Distributed, secure load balancing with skew, heterogeneity and churn. In INFOCOM, pages 1419–1430, Washington, DC, USA, 2005. IEEE.

[11] Fran¸cois Lesueur, Ludovic M´e, and Val´erie Viet Triem Tong. An efficient distributed pki for structured p2p networks. In Proceeding of P2P, pages 1–10, Washington, DC, USA, 2009. IEEE

Computer Society.

[12] Fran¸cois Lesueur, Ludovic M´e, and Val´erie Viet Triem Tong. A distributed certification system for structured p2p networks. In David Hausheer and J¨urgen Sch¨onw¨alder, editors, AIMS, volume 5127 of Lecture Notes in Computer Science, pages 40–52, Berlin, Heidelberg, 2008. Springer.

[13] Fran¸cois Lesueur, Ludovic M´e, and Val´erie Viet Triem Tong. A sybil-resistant admission control coupling sybilguard with distributed certification. In WETICE, pages 105–110, Washington, DC, USA, 2008. IEEE Computer Society.

[14] Fran¸cois Lesueur, Ludovic M´e, and Val´erie Viet Triem Tong. A sybilproof distributed identity

management for p2p networks. In ISCC, pages 246–253, Washington, DC, USA, 2008. IEEE.

[15] Agapios Avramidis, Panayiotis Kotzanikolaou, and Christos Douligeris. Chord-pki: Embedding a

public key infrastructure into the chord overlay network. In Javier Lopez, Pierangela Samarati,

and Josep L. Ferrer, editors, EuroPKI, volume 4582 of Lecture Notes in Computer Science, pages 354–361, Berlin, Heidelberg, 2007. Springer.

[16] Nikita Borisov. Computational puzzles as sybil defenses. In Alberto Montresor, Adam Wierzbicki,

and Nahid Shahmehri, editors, Peer-to-Peer Computing, pages 171–176, Washington, DC,

USA, 2006. IEEE Computer Society.

[17] Haifeng Yu, Phillip B. Gibbons, and Michael Kaminsky. Toward an optimal social network

defense against sybil attacks. In Indranil Gupta and Roger Wattenhofer, editors, PODC, pages

376–377. ACM, 2007.

[18] Haifeng Yu, Phillip B. Gibbons, Michael Kaminsky, and Feng Xiao. Sybillimit: A near-optimal social network defense against sybil attacks. In IEEE Symposium on Security and Privacy, pages 3–17, Washington, DC, USA, 2008. IEEE Computer Society.

[19] Haifeng Yu, Michael Kaminsky, Phillip B. Gibbons, and Abraham Flaxman. SybilGuard: defending against sybil attacks via social networks. In Luigi Rizzo, Thomas E. Anderson, and Nick McKeown, editors, SIGCOMM, pages 267–278, New York, NY, USA, 2006. ACM.

[20] Haifeng Yu, Michael Kaminsky, Phillip B. Gibbons, and Abraham D. Flaxman. Sybilguard: defending against sybil attacks via social networks. IEEE/ACM Trans. Netw., 16(3):576–589, 2008.

[21] Nguyen Tran, Jinyang Li, Lakshminarayanan Subramanian, and Sherman S.M. Chow. Optimal sybil-resilient node admission control. In The 30th IEEE International Conference on Computer Communications (INFOCOM 2011), Shanghai, P.R. China, 2011. IEEE.

[22] Chris Lesniewski-Lass and M. Frans Kaashoek. Wh¯anau: A sybil-proof distributed hash table. In

7th USENIX Symposium on Network Design andImplementation, pages 3–17, Berkeley, CA, USA,

2010. USENIX Association.

[23] C. Lesniewski-Laas. A Sybil-proof one-hop DHT. In Proceedings of the 1st workshop on Social network systems, pages 19–24, New York, NY, USA, 2008. ACM.

[24] Paul F. Syverson, David M. Goldschlag, and Michael G. Reed. Anonymous connections and

onion routing. In IEEE Symposium on Security and Privacy, pages 44–54, Washington, DC, USA,

1997. IEEE Computer Society.

[25] Peng Wang, James Tyra, Eric Chan-tin, Tyson Malchow, Denis Foo Kune, and Yongdae Kim.

Attacking the kad network, 2009.

[26] B.N. Levine, C. Shields, and N.B. Margolin. A survey of solutions to the sybil attack. Technical

report, University of Massachusetts Amherst, Amherst, MA, 2006.

[27] Rodrigo Rodrigues, Barbara Liskov, and Liuba Shrira. The design of a robust peer-to-peer system. In 10th ACM SIGOPS European Workshop, pages 1–10, New York, NY, USA, 2002. ACM.

[28] James Newsome, Elaine Shi, Dawn Song, and Adrian Perrig. The sybil attack in sensor networks: analysis & defenses. In IPSN ’04: Proceedings of the 3rd international symposium on Information processing in sensor networks, pages 259–268, New York, NY, USA, 2004. ACM.

[29] Michael J. Freedman and Robert Morris. Tarzan: a peer-to-peer anonymizing network layer. In

Vijayalakshmi Atluri, editor, ACM Conference on Computer and Communications Security, pages 193–206, Washington, DC, USA, 2002. ACM.

[30] Fabrizio Cornelli, Ernesto Damiani, Sabrina De Capitani di Vimercati, Stefano Paraboschi, and Pierangela Samarati. Choosing reputable servents in a p2p network. In WWW, pages 376–386, New York, NY, USA, 2002. ACM.

[31] Brent ByungHoon Kang, Eric Chan-Tin, Christopher P. Lee, James Tyra, Hun Jeong Kang, Chris Nunnery, Zachariah Wadler, Greg Sinclair, Nicholas Hopper, David Dagon, and Yongdae Kim. Towards complete node enumeration in a peer-to-peer botnet. In Wanqing Li, Willy Susilo, Udaya Kiran Tupakula, Reihaneh Safavi-Naini, and Vijay Varadharajan, editors, ASIACCS, pages 23–34, New York, NY, USA, 2009. ACM.

[32] Frank Li, Prateek Mittal, Matthew Caesar, and Nikita Borisov. Sybilcontrol: practical sybil

defense with computational puzzles. In Proceedings of the seventh ACM workshop on Scalable trusted computing, pages 67–78. ACM, 2012.

[33] Luis von Ahn, Manuel Blum, Nicholas J. Hopper and John Langford. Captcha: Using hard ai problems for security. In Eli Biham, editor, EUROCRYPT, volume 2656 of Lecture Notes in Computer Science, pages 294–311, Berlin, Heidelberg, 2003. Springer.

[34] Jeff Yan and Ahmad Salah El Ahmad. Breaking visual captchas with naive pattern recognition algorithms. In ACSAC, pages 279–291, Washington, DC, USA, 2007. IEEE Computer Society.

[35] N. Tran, B. Min, J. Li, and L. Subramanian. Sybil-resilient online content voting. In NSDI, Berkeley, CA, USA, 2009. USENIX.

[36] Sergio Marti, Prasanna Ganesan, and Hector Garcia-Molina. Dht routing using social links. In IPTPS, pages 100–111, Washington, DC, USA, 2004. IEEE.

[37] Daniele Quercia and Stephen Hailes. Sybil attacks against mobile users: friends and foes to the

rescue. In INFOCOM’10: Proceedings of the 29th conference on Information communications, pages

336–340, Piscataway, NJ, USA, 2010. IEEE Press.

[38] Abedelaziz Mohaisen, Aaram Yun, and Yongdae Kim. Measuring the mixing time of social graphs. In Proceedings of the 10th annual conference on Internet measurement, IMC ’10, pages 383–389,

New York, NY, USA, 2010. ACM.

[39] Bimal Viswanath, Ansley Post, Krishna P. Gummadi, and Alan Mislove. An analysis of social network-based sybil defenses. In SIGCOMM, New York, NY, USA, August 2010. ACM.

[40] George Danezis and Prateek Mittal. SybilInfer: Detecting sybil nodes using social networks. In

The 16th Annual Network & Distributed System Security Conference, Lecture Notes in Computer Science, Berlin, Heidelberg, 2009. Springer-Verlag.

[41] Abedelaziz Mohaisen, Huy Tran, Nicholas Hopper, and Yongdae Kim. Understanding social networks properties for trustworthy computing. In ICDCS Workshops, pages 154–159. IEEE, 2011.

[42] Abedelaziz Mohaisen and Scott Hollenbeck. Improving social network-based sybil defenses by augmenting social graphs. In WISA, 2013.

[43] Abedelaziz Mohaisen, Nicholas Hopper, and Yongdae Kim. Keep your friends close: Incorporating trust into social network-based sybil defenses. In INFOCOM, pages 1943–1951. IEEE, 2011.

[44] Haifeng Yu. Sybil defenses via social networks: a tutorial and survey. ACM SIGACT News, 42(3):80–101, 2011.