Trust - Peer-to-Peer Computing: Applications, Architecture, Protocols, and Challenges - page 132

t i = (C T ) n c i and it can be shown that [Kamvar et al., 2003] t i will converge
to the same vector for all i. Specifically, t i will converge to the left principal
eigenvector of C.
Kamvar et al. suggested a probabilistic interpretation of EigenTrust: if an
agent searches for reputable peers, it can crawl to peer j with probability c ij .
After crawling for a while in this manner, the agent is more likely to be at
reputable peers than unreputable peers.
In a practical P2P system, there are always a set of enthusiastic peers (i.e.,
the peers that initiate the system) that warrant unconditional a priori trust.
To incorporate this feature in the EigenTrust model, Kamvar et al. modeled
such a set P of pre-trusted peers by a vector p i , where each element p ik = 1/|P|
if k∈P and p ik = 0 otherwise. Thus, each peer i can use this vector to
bootstrap the initial trust aggregation: t i (0)

= C T p i and t i (k+1) = C T t i (k) for

all k≥0.
To combat collusion where a set of malicious peers give each other high
reputation values, Kamvar et al. suggested a weighted approach:

t (k+1)

= (1−a)C T t (k) + ap (6.5)

where a is some constant less than 1. Kamvar et al. offered a probabilistic
justification for this approach: when a peer is crawling the network, it is less
likely to get stuck crawling a malicious member of a collusion because there is
a non-zero probability that it ends up at a pre-trusted peer. Another merit of
this weighted approach is that the matrix C becomes irreducible and aperiodic,
thereby forcing the computation to converge.
Simulation results indicated that using EigenTrust to guide files download-
ing in a Gnutella-like network can reduce the number of bogus files downloaded
under a wide variety of threat scenarios.
However, as shown by Abrams et al. [Abrams et al., 2005], the EigenTrust
algorithm can also potentially facilitate a selfish peer to lie about its recom-
mendation to gain a higher trust value. Specifically, to maximize its trust, a
peer must always recommend a peer that recommended it. Consider the down-
load graph of Figure 6.3(a), and assume a uniform distribution for pre-trusted
peers over all n peers: if the middle peer reports a download from the right
peer, it will have trust (2−ǫ)ǫ

n . If, on the other hand, it reports a download
from the left peer, it will only have a trust value of 1/n.
Abrams et al. [Abrams et al., 2005] suggested a modified EigenTrust algo-
rithm which works by first creating a query topology and then making each
peer's trust independent of his/her reporting of downloads. Specifically, the
EigenTrust algorithm is modified as follows:

Initialization At the initialization of the modified algorithm, peers are
partitioned into groups evenly (depicted by different colors), where
C ={c 1 , c 2 , . . . , c m }is the set of partitions. Each color has either⌊ m ⌋
or⌈ m ⌉peers. The colors are arranged into a directed cycle chosen uni-
formly at random. Then,∀c∈C, let pred(c) be the color which is the