EigenTrust
Encyclopedia
EigenTrust algorithm
is a reputation management
algorithm for peer-to-peer
networks, developed by Sep Kamvar, Mario Schlosser, and Hector Garcia-Molina. The algorithm provides each peer in the network a unique global trust value based on the peer's history of uploads and thus aims to reduce the number of inauthentic files in a P2P
network.
systems available today (like Gnutella
) are open, often anonymous and lack accountability. Hence a user with malicious intent can introduce into the peer-to-peer network resources that may be inauthentic, corrupted or malicious (Virus
). This reflects poorly on the credibility of current peer-to-peer systems. A research team from Stanford provides a reputation management system, where each peer in the system has a unique global trust value based on the peer's history of uploads. Any peer requesting resources will be able to access the trust value of a peer and avoid downloading files from untrusted peers.
where sat (i, j) refers to the number of satisfactory responses that peer i has received from peer j,
and unsat(i, j) refers to the number of unsatisfactory responses that peer i has received from peer j.
The local value is normalized, to prevent malicious peers from assigning arbitrarily high local trust values to colluding malicious peers and arbitrarily low local trust values to good peers. The normalized local trust value cij is then
The local trust values are aggregated at a central location or in a distributed manner to create a trust vector for the whole network. Based on the idea of transitive trust, a peer i would ask other peers it knows to report the trust value of a peer k and weigh responses of these peers by the trust peer i places in them.
If we assume that a user knew the cij values for the whole network in the form of a matrix
C, then trust vector
that defines the trust value for 
is given by
In the equation shown above, if C is assumed to be aperiodic and strongly connected, powers of the matrix C will converge to a stable value at some point.
It seems that for a large value of x, the trust vector
will converge to the same vector for every peer in the network. The vector 
is known as the left principal eigenvector of the matrix C. We also note that since 
is same for all nodes in the network, it represents the global trust value.
Based on the results above a simple centralized trust value computing algorithm can be written. Note that we assume that all the local trust values for the whole network are available and present in the matrix C. We also note that, if the equation shown above converges, we can replace the initial vector
by a vector 
that is an m-vector representing uniform probability distribution over all m peers. The basic EigenTrust algorithm is shown below:
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
is a reputation management
Reputation management
Reputation management , also known as directory management, is the process of tracking an entity's actions and other entities' opinions about those actions; reporting on those actions and opinions; and reacting to that report creating a feedback loop. All entities involved are generally people, but...
algorithm for peer-to-peer
Peer-to-peer
Peer-to-peer computing or networking is a distributed application architecture that partitions tasks or workloads among peers. Peers are equally privileged, equipotent participants in the application...
networks, developed by Sep Kamvar, Mario Schlosser, and Hector Garcia-Molina. The algorithm provides each peer in the network a unique global trust value based on the peer's history of uploads and thus aims to reduce the number of inauthentic files in a P2P
Peer-to-peer file sharing
P2P or Peer-to-peer file sharing allows users to download files such as music, movies, and games using a P2P software client that searches for other connected computers. The "peers" are computer systems connected to each other through internet. Thus, the only requirements for a computer to join...
network.
Overview
Peer-to-peerPeer-to-peer
Peer-to-peer computing or networking is a distributed application architecture that partitions tasks or workloads among peers. Peers are equally privileged, equipotent participants in the application...
systems available today (like Gnutella
Gnutella
Gnutella is a large peer-to-peer network which, at the time of its creation, was the first decentralized peer-to-peer network of its kind, leading to other, later networks adopting the model...
) are open, often anonymous and lack accountability. Hence a user with malicious intent can introduce into the peer-to-peer network resources that may be inauthentic, corrupted or malicious (Virus
Virus
A virus is a small infectious agent that can replicate only inside the living cells of organisms. Viruses infect all types of organisms, from animals and plants to bacteria and archaea...
). This reflects poorly on the credibility of current peer-to-peer systems. A research team from Stanford provides a reputation management system, where each peer in the system has a unique global trust value based on the peer's history of uploads. Any peer requesting resources will be able to access the trust value of a peer and avoid downloading files from untrusted peers.
Algorithm
The Eigentrust algorithm is based on the notion of transitive trust: If a peer i trusts any peer j, it would also trust the peers trusted by j. Each peer i calculates the local trust value sij for all peers that have provided it with authentic or fake downloads based on the satisfactory or unsatisfactory transactions that it has had.where sat (i, j) refers to the number of satisfactory responses that peer i has received from peer j,
and unsat(i, j) refers to the number of unsatisfactory responses that peer i has received from peer j.
The local value is normalized, to prevent malicious peers from assigning arbitrarily high local trust values to colluding malicious peers and arbitrarily low local trust values to good peers. The normalized local trust value cij is then
The local trust values are aggregated at a central location or in a distributed manner to create a trust vector for the whole network. Based on the idea of transitive trust, a peer i would ask other peers it knows to report the trust value of a peer k and weigh responses of these peers by the trust peer i places in them.
If we assume that a user knew the cij values for the whole network in the form of a matrix
Matrix (mathematics)
In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...
C, then trust vector
that defines the trust value for is given byIn the equation shown above, if C is assumed to be aperiodic and strongly connected, powers of the matrix C will converge to a stable value at some point.
It seems that for a large value of x, the trust vector
will converge to the same vector for every peer in the network. The vector is known as the left principal eigenvector of the matrix C. We also note that since is same for all nodes in the network, it represents the global trust value.Based on the results above a simple centralized trust value computing algorithm can be written. Note that we assume that all the local trust values for the whole network are available and present in the matrix C. We also note that, if the equation shown above converges, we can replace the initial vector
by a vector that is an m-vector representing uniform probability distribution over all m peers. The basic EigenTrust algorithm is shown below:- repeat
- until
