the eigentrust algorithm for reputation management in p2p networks

1、The EigenTrust Algorithm for Reputation Management in P2P NetworksSepandar D. Kamvar Stanford Universitysdkamvar@stanford.eduMario T. Schlosser Stanford Universityschloss@db.stanford.eduHector Garcia-Molina Stanford Univ

2、ersityhector@db.stanford.eduABSTRACTPeer-to-peer file-sharing networks are currently receiving much at- tention as a means of sharing and distributing information. How- ever, as recent experience shows, the anonymous, op

3、en nature of these networks offers an almost ideal environment for the spread of self-replicating inauthentic files. We describe an algorithm to decrease the number of downloads of inauthentic files in a peer-to-peer fil

4、e-sharing network that as- signs each peer a unique global trust value, based on the peer’s history of uploads. We present a distributed and secure method to compute global trust values, based on Power iteration. By havi

5、ng peers use these global trust values to choose the peers from whom they download, the network effectively identifies malicious peers and isolates them from the network. In simulations, this reputation system, called Ei

6、genTrust, has been shown to significantly decrease the number of inauthentic files on the network, even under a variety of conditions where malicious peers cooperate in an attempt to deliberately subvert the system.Categ

7、ories and Subject DescriptorsC.2.4 [Computer-Communication Networks]: Distributed Sys- tems—Distributed applications; H.3.3 [Information Systems]: In- formation Storage and Retrieval—Selection; H.2.7 [Information Systems

8、]: Database Management—Security, integrity and protec- tionGeneral TermsAlgorithms,Performance,TheoryKeywordsPeer-to-Peer, reputation, distributed eigenvector computation1. INTRODUCTIONPeer-to-peer file-sharing networks

9、have many benefits over stan- dard client-server approaches to data distribution, including im- proved robustness, scalability, and diversity of available data. How- ever, the open and anonymous nature of these networks

10、leads to a complete lack of accountability for the content a peer puts on the network, opening the door to abuses of these networks by malicious peers. Attacks by anonymous malicious peers have been observed on today’s p

11、opular peer-to-peer networks. For example, malicious users have used these networks to introduce viruses such as theCopyright is held by the author/owner(s). WWW2003, May 20–24, 2003, Budapest, Hungary. ACM 1-58113-680-3

12、/03/0005.VBS.Gnutella worm, which spreads by making a copy of itself in a peer’s Gnutella program directory, then modifying the Gnutella.ini file to allow sharing of .vbs files [19]. Far more common have been inauthentic

13、 file attacks, wherein malicious peers respond to virtu- ally any query providing “decoy files” that are tampered with or do not work. It has been suggested that the future development of P2P systems will depend largely

14、on the availability of novel methods for ensur- ing that peers obtain reliable information on the quality of resources they are receiving [6]. In this context, attempting to identify mali- cious peers that provide inauth

15、entic files is superior to attempting to identify inauthentic files themselves, since malicious peers can eas- ily generate a virtually unlimited number of inauthentic files if they are not banned from participating in t

16、he network. We present such a method wherein each peer i is assigned a unique global trust value that reflects the experiences of all peers in the network with peer i. In our approach, all peers in the network participat

17、e in computing these values in a distributed and node-symmetric manner with min- imal overhead on the network. Furthermore, we describe how to ensure the security of the computations, minimizing the probabil- ity that ma

18、licious peers in the system can lie to their own benefit. And finally, we show how to use these values to identify peers that provide material deemed inappropriate by the users of a peer-to- peer network, and effectively

19、 isolate them from the network.2. DESIGN CONSIDERATIONSThere are five issues that are important to address in any P2P reputation system.1. The system should be self-policing. That is, the shared ethics of the user popula

20、tion are defined and enforced by the peers themselves and not by some central authority.2. The system should maintain anonymity. That is, a peer’s rep- utation should be associated with an opaque identifier (such as the

21、peer’s Gnutella username) rather than with an exter- nally associated identity (such as a peer’s IP address).3. The system should not assign any profit to newcomers. That is, reputation should be obtained by consistent g

22、ood behav- ior through several transactions, and it should not be advan- tageous for malicious peers with poor reputations to contin- uously change their opaque identifiers to obtain newcomers status.4. The system should

23、 have minimal overhead in terms of com- putation, infrastructure, storage, and message complexity.5. The system should be robust to malicious collectives of peers who know one another and attempt to collectively subvert

24、the system.? t(0) = ? e; repeat ? t(k+1) = CT? t(k); δ = ||t(k+1) ? tk||; until δ < ?;Algorithm 1: Simple non-distributed EigenTrust algorithmdefined by the normalized local trust matrix C is our global trust vector ?

25、 t.4.4 Basic EigenTrustIn this section, we describe the basic EigenTrust algorithm, ig- noring for now the distributed nature of the peer-to-peer network. That is, we assume that some central server knows all the cij val

26、ues and performs the computation. In Section 4.6, we describe how the computation may be performed in a distributed environment. We simply wish to compute ? t = (CT )n? e, for n =large, where we define ? e to be the m-ve

27、ctor representing a uniform probability distribution over all m peers, ei = 1/m. (In Section 4.2, we said we wish to compute ? t = (CT )n? ci, where ? ci is the normalized local trust vector of some peer i. However, sinc

28、e they both converge to the principal left eigenvector of C, we may use ? e instead.) At the most basic level, the algorithm would proceed as in Algo- rithm 1.4.5 Practical IssuesThere are three practical issues that are

29、 not addressed by this simple algorithm: a priori notions of trust, inactive peers, and ma- licious collectives. A priori notions of trust. Often, there are some peers in the network that are known to be trustworthy. For

30、 example, the first few peers to join a network are often known to be trustworthy, since the designers and early users of a P2P network are likely to have less motivation to destroy the network they built. It would be us

31、eful to incorporate such notions of trust in a natural and seamless manner. We do this by defining some distribution ? p over pre-trusted peers1. For example, if some set of peers P are known to be trusted, we may define

32、 pi = 1/|P| if i ∈ P, and pi = 0 otherwise.) We use this distribution ? p in three ways. First of all, in the presence of malicious peers, ? t = (CT )n? p will generally converge faster than ? t = (CT )n? e, so we use ?

33、p as our start vector. We describe the other two ways to use this distribution ? p below. Inactive Peers. If peer i doesn’t download from anybody else, or if it assigns a zero score to all other peers, cij from Equation

34、1 will be undefined. In this case, we set cij = pj. So we redefine cij as:cij =( max(sij ,0) Pj max(sij) if Pj max(sij, 0) ?= 0;pj otherwise (4)That is, if peer i doesn’t know anybody, or doesn’t trust anybody, he will c

35、hoose to trust the pre-trusted peers. Malicious Collectives. In peer-to-peer networks, there is poten- tial for malicious collectives to form [8]. A malicious collective is a group of malicious peers who know each other,

36、 who give each other high local trust values and give all other peers low local trust values in an attempt to subvert the system and gain high global trust1The idea of pre-trusted peers is also used in [2], where the com

37、pu- tation of the trust metric is performed relative to a “seed” of trusted accounts.? t(0) = ? p; repeat? t(k+1) = CT? t(k); ? t(k+1) = (1 ? a)? t(k+1) + a? p; δ = ||t(k+1) ? t(k)||;until δ < ?;Algorithm 2: Basic Eig

38、enTrust algorithmvalues. We address this issue by taking? t(k+1) = (1 ? a)CT? t(k) + a? p (5)where a is some constant less than 1. This is equivalent to setting the opinion vector for all peers to be ? ci = (1 ? a)? ci +

39、 a? p, break- ing collectives by having each peer place at least some trust in the peers P that are not part of a collective. Probabilistically, this is equivalent to saying that the agent that is crawling the network by

40、 the probabilistic model given in Section 4 is less likely to get stuck crawling a malicious collective, because at each step, he has a cer- tain probability of crawling to a pre-trusted peer. Notice that this also makes

41、 the matrix C is irreducible and aperiodic, guaranteeing that the computation will converge. The modified algorithm is given in Algorithm 2. It should be emphasized that the pre-trusted peers are essential to this algori

42、thm, as they guarantee convergence and break up ma- licious collectives. Therefore, the choice of pre-trusted peers is important. In particular, it is important that no pre-trusted peer be a member of a malicious collect

43、ive. This would compromise the quality of the algorithm. To avoid this, the system may choose a very few number of pre-trusted peers (for example, the designers of the network). A thorough investigation of different meth

44、ods of choosing pre-trusted peers is an interesting research area, but it is outside of the scope of this paper.4.6 Distributed EigenTrustHere, we present an algorithm where all peers in the network co- operate to comput

45、e and store the global trust vector, and the com- putation, storage, and message overhead for each peer are minimal. In a distributed environment, the first challenge that arises is how to store C and ? t. In previous se

46、ctions, we suggested that each peer could store its local trust vector ? ci. Here, we also suggest that each peer store its own global trust value ti. (For presentation purposes, we ignore issues of security for the mome

47、nt and allow peers to store their own trust values. We address issues of security in Section 5.) In fact, each peer can compute its own global trust value:t(k+1) i = (1 ? a)(c1it(k) 1 + . . . + cnit(k) n ) + api (6)Inspe

48、ction will show that this is the component-wise version of ? t(k+1) = (1?a)CT? t(k)+a? p. Notice that, since peer i has had lim- ited interaction with other peers, many of the components in equa- tion 6 will be zero. Thi

49、s lends itself to the simple distributed algo- rithm shown in Algorithm 3. It is interesting to note two things here. First of all, only the pre-trusted peers need to know their pi. This means that pre-trusted peers may

50、remain anonymous; nobody else needs to know that they are pre-trusted2. Therefore, the pre- trusted peers maintain anonymity as pre-trusted peers. (One may imagine that pre-trusted peers may be identified because they ha

51、ve high global trust values. However, simulations show that, while the2Recall that, for the moment, we assume that peers are honest and may report their own trust values, including whether or not they are a pre-trusted p