A peer-to-peer reputation algorithm

EigenTrust helps networked peers measure the level of trust placed on one another in a peer-to-peer network. The core idea behind EigenTrust is that a person’s reputation is defined recursively by the people who trust that person, weighted by those people’s reputations.

As a baseline, you can trust your friends. This gives you a good starting point, but because each person only has so many friends, it’s too limited to make a reliable system for millions of users/peers in a network. As a next step, you can expand that by asking your friends who they trust, and weighing their opinions by how much you trust your friends.

The linear algebra behind EigenTrust — you can initialize a trust vector with a set of seed peers that you trust. And then you can keep multiplying that vector by a matrix that represents the pairwise trust judgments of all the peers in the network. This is a power method algorithm, and it converges to the principal eigenvector of the matrix. Eventually you get complete coverage over everyone connected to you, directly or indirectly - in just a single eigenvector calculation.

Local Trust (Reputation Graphs)

EigenTrust helps map trust from peer A to peer B in a graph. The primary input to EigenTrust is how much each peer directly trusts each other peer. These direct trust levels are called local trust values (LTVs), a function P(A, B) which translates to how much the peer A trusts peer B. Local Trust is not necessarily symmetric. Over the same set of interactions, A may trust B more than B trusts A. Hence, there are two local trust values: how much direct trust A places in B, and how much direct trust B places in A.

Context of Local Trust is important

The pairwise trust levels of peers need a related context. For example:

  • Linear combination of engagement actions on a social network

  • Tipping on an app to reward quality content

  • Onchain token transfers

  • Graphical NFT activities and ownership

  • Peer attestations for being a reputable software developer

These contextual axes bear higher fidelity to specific activities than, say, a simple follower-based pairwise trust, and in general cater much better to users’ interests. We encourage developers to try to bring topical/fine-grained reputation graph data as well as more general/coarse-grained data.

Modeling Distrust

By default, EigenTrust revolves around degrees of trust above the neutral trust level: A local trust level of 0, for example, indicates a peer places the default amount of trust that they would in any other random peer in the network with which they have had no interaction at all. Trust levels cannot be negative; negative trusts are clipped at zero. This implements the untrusted-by-default model; the original EigenTrust research paper shows that this model is effective, for example, in detecting and thwarting Sybil attacks—a common use case for EigenTrust.

If an application does need a way of expressing/calculating the level of distrust below the neutral trust level, ex: where a somewhat-trusted-by-default model is needed, developers may want to experiment with the positive/negative karma model, where two EigenTrust scores are computed: One that revolves around trust above the neutral trust (zero is neutral trust, above zero is positive trust), and another below the neutral trust (zero is neutral trust, above zero is negative trust). Then the resulting scores may be combined to calculate the final trust score.

Seed Trust

EigenTrust lets applications or services calculate trust scores tailored for a specific peer. For example, the trust opinions of peer’s immediate network neighbors and vicinity may matter more to the peer. Also, services may place context-specific trust in certain peers, e.g. those who share a common and/or clandestine relationship with the service.

To accommodate these use cases, EigenTrust lets services boost the importance of these pre-trusted peers, so that the opinions of their own matter more (and those of their vicinity too, the closer the stronger boost). For this, in addition to the local trust values for all peers in the network, EigenTrust accepts two more inputs:

  • The seed trust that a peer and/or service places in certain other pre-trusted peers.

  • The seed confidence—the strength of the seed trust, expressed as a percentage.

The seed trust by a peer may be distinct from the local pairwise trust that the peer places in other peers. For example, although the local trust by a peer may be derived solely from the interactions that the peer had with other peers, the seed trust may include other peers that the peer had no experience with but nevertheless knew to be trustworthy.

Good selection of seed trust helps achieve better rankings. Without any seed trust, each peer is by default assigned an equal amount of trust level (1/n), which is less Sybil resistant. Seed trust boosts trust levels of peers directly or indirectly trusted by them, and the seed confidence decides the level of this boost. By choosing peers (and their vicinity) generally known to be prudent not to trust Sybils as seed trust, one can effectively limit the impact of the Sybils in the system.

For details about how we can achieve permissionless verifiability of EigenTrust, refer to the original OpenRank paper.

Last updated


Copyright 2024