Gossip-Based Aggregation of Trust in Decentralized Reputation Systems

1 Introduction

In open multiagent environments, self-interested agents are often tempted to employ deceit as they interact with others. Fortunately, dishonest agents can expect their victims to retaliate in future encounters. This "shadow of the future" motivates cooperation and trustworthiness.

However, as the size of the system grows, agents have an increasingly small chance of dealing with another agent they already know; as a consequence, building trust in domains teeming with numerous agents becomes much harder. Reputation systems address this problem by collecting and spreading reports among agents, so that agents may learn from others' experience. To put it differently, agents are intimidated by the "shadow of the future" today, even though tomorrow they are most likely to meet total strangers.

Reputation systems can be decomposed into two major components: 1) the trust model, which describes whether an agent is trustworthy, and 2) the data management scheme. The latter component poses some interesting questions, since it is imperative to efficiently aggregate trust-related information in the system. A simple solution is maintaining a central database that contains the feedback gathered from past transactions. Unfortunately, this solution is inappropriate in distributed environments where scalability is a major concern, as the database soon becomes a bottleneck of the system. Moreover, this approach is not robust to failures. Previous work on decentralized reputation schemes suffered from their own major problems: agents have to maintain complex data structures, evaluation of trust is based only on local information, or there are restrictive assumptions on the trust model. 1

We approach this hornets' nest by designing a novel method of trust aggregation (i.e., a reputation system's data management scheme). The method is demonstrated in this paper for a simple trust model, but it can be extended to more complex models.

The roots of our gossip-based approach can be traced to a seminal paper by Frieze and Grimmett [1985]: a rumor starts with one agent; at each stage, each agent that knows the rumor spreads it to another agent chosen uniformly at random. The authors show that the rumor reaches all agents quickly (a result that coincides with real life). We directly rely on more recent results, surveyed in the next section. It has been shown that aggregate information, such as averages and sums of agents' inputs, can be calculated using similar methods of uniform gossip in a way that scales gracefully as the number of agents increases. Furthermore, the approach is robust to failures, and the results hold even when one cannot assume a point-to-point connection between any two agents (as is the case in peer-to-peer [P2P] networks).

In our setting, each agent merely keeps its private evaluation of the trustworthiness of other agents, based on its own interactions. 2 When an agent wishes to perform a transaction with another, it obtains the average evaluation of the other's reputation from all agents in the system, using a gossip-based technique. Although the presented algorithms estimate the average reputation, they can be easily adapted to estimating whether a certain agent has a high reputation in the eyes of the majority of the agents, or certain other similar metrics. Thus, the framework we advocate for aggregating reputation information accommodates more sophisticated trust models.

Some advantages are immediately self-evident. Each agent stores very little information, which can be simply and efficiently organized, and evaluation of trust is based on global information. Additionally, this framework inherits the advantages of gossip-based algorithms: scalability, robustness to failure, decentralization, and as a consequence, applicability in peer-to-peer networks.

1 The "or" is not exclusive.

2 The question of how agents set this valuation is outside the scope of this paper.

We show that our scheme has two other major advantages. An important desideratum one would like a reputation system to satisfy is motivating agents to maintain an untarnished reputation, i.e., to be absolutely trustworthy (as opposed to, say, being generally trustworthy but occasionally cheating). We show that our data management scheme, together with an extremely simple trust model, satisfies this property. We also demonstrate that our scheme is inherently resistant to some attacks (with no assumptions on the trust model). This is a positive side effect of the exponential convergence rates of the algorithms we use.

In this paper we do not address the problem of designing a trust model. Rather, we suggest an approach for agents to aggregate distributed trust information so as to decide with whom to carry out transactions.

2 Gossip-Based Information Aggregation

In this section, we survey the relevant results of Kempe, Dobra and Gehrke [Kempe et al., 2003]. These algorithms allow us to estimate the average of values held at network nodes (in our case, these values will be the reputation values concerning a particular agent). [Kempe et al., 2003] also shows how to calculate other functions over these values, such as the majority function and sum. Thus our algorithms can be adapted for other, more sophisticated models of trust.

We begin by describing a simple algorithm, PUSH-SUM, to compute the average of values at nodes in a network. There are n nodes in the system, and each node i holds an input xi ≥ 0. At time t, each node i maintains a sum st,i and a weight wt,i. The values are initialized as follows: s0,i = xi, w0,i = 1. At time 0, each node i sends the pair s0,i,w0,i to itself; at every time t > 0, the nodes follow the protocol given as Algorithm 1.

Algorithm 1

• 1: procedure PUSH-SUM
• 2: Let {(ˆ sl, ˆwl)}l be all the pairs sent to i at time t - 1
• 3: st,i ← ∑l ˆ sl
• 4: wt,i ← ∑l ˆwl
• 5: Choose a target ft(i) uniformly at random
• 6: Send the pair ( 12 st,i, 12 wt,i) to i and to ft(i)
• 7: st,i wt,i is the estimate of the average at time t
• 8: end procedure

Let U(n, δ, ϵ) (the diffusion speed of uniform gossip) be an upper bound on the number of turns PUSH-SUM requires so that for all t ≥ U(n, δ, ϵ) and all nodes i,

(the relative error is at most ϵ) with probability at least 1 - δ. Theorem 1 ([Kempe et al., 2003]).

1. The size of all messages sent at time t by PUSH-SUM is O(t + maxi bits(xi)), where bits(xi) is the number of bits in the binary representation of xi.

A major advantage of gossip-based algorithms is their robustness to failures: the aggregation persists in the face of failed nodes, permanent communication failures, and other unfortunate events. Further, no recovery action is required. The assumption is that nodes can detect whether their message has reached its destination; PUSH-SUM is modified so that if a node detects its target failed, it sends its message to itself.

Theorem 2 ([Kempe et al., 2003]). Let μ < 1 be an upper bound on the probability of message loss at each time step, and let U ′ be the diffusion speed of uniform gossip with faults. Then:

In several types of decentralized networks, such as P2P networks, point-to-point communicationmay not be possible. In these networks, it is assumed that at each stage nodes send messages to all their neighbors (flooding). When the underlying graph is an expander, or at least expected to have good expansion, results similar to the above can be obtained. Fortunately, it is known that several peer-to-peer topologies induce expander graphs [Pandurangan et al., 2001].

In the rest of the paper, we have xi ≤ 1, and in particular ∑i xi ≤ n. Therefore, it is possible to redefine U to be an upper bound on the number of turns required so that for all t ≥ U and all nodes i, the absolute error ∣∣∣ st,i wt,i - 1n ∑k xk ∣∣∣ is at most ϵ with confidence 1 - δ, and it still holds that U(n, δ, ϵ) = O(log n + log 1δ + log 1ϵ ). Hereinafter, when we refer to U we have this definition in mind.

Remark 1. The protocol PUSH-SUM is presented in terms of a synchronized starting point, but this assumption is not necessary. A node that poses the query may use the underlying communication mechanism to inform all other nodes of the query; convergence times are asymptotically identical.

3 Our Framework

Let the set of agents be N = {1, . . . , n}. Each agent i ∈ N holds a number rj i ∈ [0, 1] for each agent j ∈ N (including itself). This number represents j's reputation with respect to i, or to put it differently, the degree to which i is willing to trust j. As agents interact, these assessments are repeatedly updated. We do not in general concern ourselves with how agents set these values.

When an agent i is deliberating whether to deal with another agent j, i wishes to make an informed evaluation of the other's reputation. Let ¯ rj = Pk rjk n be the average of j's reputation with respect to all agents. Knowledge of ¯ rj would give i a good idea of how trustworthy j is (this is, of course, a simple model of trust).

We show that in this scenario, agents can use gossip-based algorithms to decide with whom to carry out transactions. Also, in such a setting, agents are encouraged to keep a completely untarnished reputation. Similar results can be obtained for more complex trust models.

Algorithm 2

1: procedure EVAL-TRUST(i, j, δ, ϵ) ▷ i evaluates ¯ rj with accuracy ϵ, confidence 1 - δ 2: for all k ∈ N do 3: xk ← rjk ▷ Inputs to PUSH-SUM are j's reputation w.r.t. agents 4: end for 5: run PUSH-SUM for U = U(n, δ, ϵ) stages 6: return sU,i wU,i 7: end procedure

A simple way to compute the average trust is via PUSH-SUM.

The protocol EVAL-TRUST is given as Algorithm 2. PUSH-SUM is executed for U = U(n, δ, ϵ) stages. At time U, it holds for all k ∈ N, and in particular for agent i, that ∣∣∣ st,i wt,i - ¯ rj ∣∣∣ ≤ ϵ, with probability 1 - δ. In other words, the algorithm returns a very good approximation of j's average reputation.

In practice, when two agents i and j interact, i may evaluate j's reputation (and vice versa) by calling EVAL-TRUST. The protocol quickly returns the approximation of ¯ rj , based on the values rjk at the time EVAL-TRUST was called. Each agent i keeps different values st,i and wt,i for every different query that was issued by some other agent in the system, and updates these values repeatedly according to PUSH-SUM. Thus, at any stage every agent participates in many parallel executions of PUSH-SUM.

A possible cause for concern is the amount of communication each agent has to handle at every turn. However, the quick convergence of PUSH-SUM guarantees that the burden will not be too great. Indeed, it is plausible to assume that the number of new interactions at each turn is bounded by a constant c (or at worst is very small compared to n). Each such new interaction results in at most two new executions of EVAL-TRUST, but the execution lasts at most U turns. To conclude the point, each agent sends at most c ·U = O(log n) messages per turn.

Remark 2. The size of messages depends on how the rj i are calculated, and as mentioned above, this issue is outside the scope of this paper. Nevertheless, there would usually be a constant number of reputation levels (say, for instance, rij ∈ {0, 0.1, 0.2, . . . , 1}), so the message size would normally be constant.

As the above method of aggregating an agent's average reputation relies on the gossip-based algorithm PUSH-SUM, it inherits all the latter's benefits, in particular robustness to failure and applicability in peer-to-peer networks.

4 The Benefit of an Unstained Reputation

It is very desirable (indeed, crucial) that a reputation system be able to induce truthfulness in agents. Naturally, an agent with a stained reputation would be shunned by its peers, while an agent with a good reputation would easily solicit deals and transactions. A further step in this direction is motivating agents never to cheat. Indeed, an agent with a generally good reputation, that only occasionally cheats, would probably be able to win the confidence of peers; there is seemingly no reason why an agent should not play false now and again. Nevertheless, we consider in this section an extremely simple and general trust model, and show that with the data management scheme that we have presented, there is a social benefit to having a very high reputation: the higher the agent's reputation, the shorter the time required to close deals.

We consider a model in which each agent i has a reputation threshold rthr i (similar to [Xiong and Liu, 2003]) and a confidence level δi: agent i is willing to deal with an agent j iff i knows that j's average reputation is at least rthr i , with confidence 1 - δi. i evaluates j's reputation as above, using EVAL-TRUST. Recall that when the algorithm terminates, agent i only has an ϵ-close approximation of ¯ rj . If st,i wt,i is very close to rthr i , i would have to increase the accuracy.

Remark 3. We still do not commit to the way the values rij are determined and updated, so the above trust model is quite general.

Algorithm 3

1: procedure DECIDE-TRUST(i, j) ▷ i decides if it wants to deal with j 2: ϵ ← 1/2 ▷ Initialization 3: k1 ← 0 4: loop 5: k2 ← U(n, δi, ϵ) 6: run EVAL-TRUST(j) for another k2 -k1 stages ▷ A total of k2 stages 7: if st,i/wt,i < rthr i - ϵ then 8: return false 9: else if st,i/wt,i > rthr i + ϵ then 10: return true 11: end if 12: k1 ← k2 13: ϵ ← ϵ/2 14: end loop 15: end procedure

The procedure DECIDE-TRUST, given as Algorithm 3, is a straightforward method of determining whether ¯ rj ≥ rthr i . Agent i increases the accuracy of the evaluation by repeatedly halving ϵ, until it is certain of the result. In this context, a stage of EVAL-TRUST corresponds to a stage of PUSH-SUM.

Proposition 3. Let i, j ∈ N, and Δij = |¯ rj - rthr i |. With probability at least 1 - δi, DECIDE-TRUST correctly decides whether agent j ′ s reputation is at least rthr i after O(logn+ log 1 δi + log 1 Δij ) stages of EVAL-TRUST. 3

Proof. Assume w.l.o.g. that rthr i < ¯ rj , and that the algorithm reached a stage t0 where ϵ < Δij/2. At this stage, it holds that | st,i wt,i - ¯ rj | ≤ ϵ (with probability 1 - δi), and therefore:

3 The probability is the chance that the algorithm will answer incorrectly; the bound on the number of stages is always true.

Hence, the algorithm surely terminates when ϵ < Δij/2. Now the proposition follows directly from the fact that U (n, δi, Δij ) = O(log n + log 1 δi + log 1 Δij ).

To conclude, Proposition 3 implies that there is a benefit for agent j in maintaining a high reputation: for any agent i with a reasonable threshold, Δij is significant, and this directly affects the running time of DECIDE-TRUST.

Remark 4. The result is limited, though, when the number of agents n is large, as the time to evaluate an agent's reputation is also proportional to logn.

5 Resistance to Attacks

We have seen that information about an agent's reputation can be efficiently propagated, as long as all agents consistently follow EVAL-TRUST. However, with reputation systems we are usually dealing with self-interested agents. In our context, a manipulative agent may artificially increase or decrease the overall evaluation of some agent's reputation by deviating from the protocol.

In the framework we have presented, trust is evaluated on the basis of global knowledge, i.e., the average of all reputation values in the system. Therefore, any small coalition cannot significantly change the average reputation of some agent j by setting their own valuations rj i to legal values in [0, 1], and then following the protocol EVAL-TRUST. 4

This is, of course, not the case when a manipulator is allowed to set its reputation value arbitrarily. As a simple motivating example, consider a setting where agents propagate agent j's average reputation (xi = rj i for all i), and a manipulator im wants to ensure that for all i, st,i wt,i converges to a high value as the time t increases. At some stage t0, the manipulator updates st0,im to be n, but except for this harsh deviation follows the protocol to the letter. In particular, the manipulator might initially set rj im = xim = n. We refer to this strategy as Strategy 1. Clearly, for all i, st,i wt,i eventually converges to a value that is at least 1.

Despite the apparent effectiveness of Strategy 1, it is easily detected. Indeed, unless for all i ̸= im it holds that st0,i = 0 at the time t0 when the manipulator deviated by assigning st0,im = n, the expressions st,i wt,i would eventually converge to a value that is strictly greater than 1; this would clearly unmask the deceit. It is of course possible to update st0,im to be less than n, but it is difficult to determine a priori which value to set without pushing the average reputation above 1.

We now consider a more subtle way to increase the values st,i wt,i , a deceit that is indeed difficult to detect; we call this strategy Strategy 2. For the first T stages of the algorithm, the manipulator im follows PUSH-SUM as usual, with the exception of the updates of st,im: after updating wt,im = ∑l ˆwl (as usual), im updates: st,im = wt,im. In other words, the manipulator sets its personal evaluation of the average st,im wt,im to be 1 at every stage t = 1, . . . , T . For time t > T , the manipulator abides by the protocol. Using this strategy, it always holds that st,i wt,i ≤ 1 for all i. In addition, for all t, it still holds that ∑i wt,i = n. Therefore, without augmenting the system with additional security measures, this manipulation is difficult to detect. We shall presently demonstrate formally that the manipulation is effective in the long run: st,i wt,i converges to 1 for all i.

4 In fact, this holds for every coalition that does not constitute a sizable portion of the entire set of agents.

Proposition4. Under Strategy 2, for all i ∈ N, s2T,i w2T,i T→∞ -→ 1 in probability.

Proof. We first notice that ∑i st,i is monotonic increasing in stage t. Moreover, as noted above, it holds that at every stage, ∑i wt,i = n, as for all i ∈ N: st,i wt,i ≤ 1, and thus:

Let ϵ, δ > 0. We must show that it is possible to choose T large enough such that for all t ≥ 2T and all i ∈ N, Pr[ st,i wt,i ≥ 1 - ϵ] ≥ 1 - δ.

Assume that at time t it holds that:

Let It = {i ∈ N : st,i wt,i ≥ 1 - ϵ/4}, w(It) = ∑i∈It wt,it . It holds that:

It follows that w(It) ≤ n · 1-ϵ/2 1-ϵ/4 . The total weight of agents in N \ It is at least n-w(It). There must be an agent it ∈ N \ It with at least a 1/n-fraction of this weight:

In order for the choice of it to be well-defined, assume it is the minimal index that satisfies Equation (2).

Now, let s′t,im be the manipulator's sum had it updated it according to the protocol, i.e., s′t,im = ∑l ˆ sl for all messages l sent to im. With probability 1/n (and independently of other stages), ft(it) = im; if this happens, it holds that:

For all stages t it holds that ∑i st+1,i - ∑i st,i = st+1,im - s′t+1,im, as the manipulator is the only agent that might change ∑i st,i. Therefore, in the conditions of Equation (3),

So far, we have shown that for each stage t where Equation (1) holds and ft(it) = im, it is the case that ∑i st+1,i - ∑i st,i ≥ Δ(w). This can happen at most n(1-ϵ/2) Δ(w) times before Equation (1) no longer holds, or to put it differently, before Pi st,i n ≥ 1 - ϵ/2.

Let Xt be i.i.d. binary random variables, that are 1 iff ft(it) = im. It holds that for all t where Equation (1) is true, E[Xt] = 1/n. By Chernoff's inequality, it holds that:

It is possible to choose T1 to be large enough such that this expression is at most δ/2, and in addition 1 · T1 ≥ n(1-ϵ/2) .

n ≥ 1 - ϵ/2 with probability 1 - δ/2.

2n Δ(w) Therefore, at time T1, the average Pi ST1,i

Recall that after T stages (where im deviated from the protocol), it still holds that ∑i wT,i = n. Assume that indeed Pi ST1,i n ≥ 1 - ϵ/2. By modifying the proof of Theorem 3.1 from [Kempe et al., 2003], it is possible to show that after another T2 = T2(n, δ, ϵ) stages where all agents observe the protocol, it holds with probability 1 - δ/2 that for all i, ∣∣∣ sT1+T2,i wT1+T2,i - Pi ST1,i n ∣∣∣ < ϵ/2, and thus for all i and t ≥ T1 + T2, st,i wt,i > 1 - ϵ with probability 1 - δ.

The proof is completed by simply choosing T = max{T1, T2}.

Proposition 4 implies that Strategy 2 poses a provably acute problem, when PUSH-SUM is run a large number of turns. Fortunately, PUSH-SUM converges exponentially fast, and thus it is usually the case that the manipulator is not able to significantly affect the average reputation, as the following proposition demonstrates.

Proposition 5. Let T1 ≤ T . Under Strategy 2 it holds that E [Pi ST1,i n - ¯ rj ] ≤ T1 2n .

Proof. Let {ˆ sl, ˆwl} be the messages that the manipulator received at time t + 1. The manipulator sets st+1,im = wt+1,im = ∑l ˆwl. Essentially, this is equivalent to setting for all l ˆ sl = ˆwl, or in other words, raising each ˆ sl by ˆwl - ˆ sl. At turn t it was already true that st,im = wt,im (w.l.o.g. this is also true for t = 0), so it is enough to consider messages at time t from all i ̸= im.

Therefore, for all stages t, it holds that:

2

The last equality follows from the fact that for all t, ∑i wt,i = n.

As ¯ rj = Pi s0,i n , and from the linearity of expectation, we obtain that

In particular, since U(n, δ, ϵ) = O(log n + log 1δ + log 1ϵ ), PUSH-SUM is executed O(logn) stages, and thus the difference in the average is at most O( log n n ), which is quite insubstantial.

Remark 5. It is not guaranteed at time T1 that each st,i wt,i is close to ¯ rj , because the inputs were dynamically changed during the execution of PUSH-SUM.

Remark 6. The above discussion focused on a setting where the manipulator attempts to increase the average reputation of an agent. It is likewise possible for a manipulator to decrease an agent's average reputation, or indeed set it eventually to any value it wants.

6 RelatedWork

P2PRep [Cornelli et al., 2002] and Xrep [Damiani et al., 2002] are P2P reputation systems that can be piggybacked onto existing P2P protocols (such as Gnutella). P2PRep allows peers to estimate trustworthiness of other peers by polling. No guarantees are given with respect to computational efficiency and scalability.

Aberer and Despotovic [2001] introduce a reputation system that consists of both a semantic model and a data management scheme. The latter relies on P-Grid [Aberer, 2001], and uses distributed data structures for storing trust information; the associated algorithms scale gracefully as the number of agents increases. This approach, however, suffers from several shortcomings compared to ours. Agents in this scheme assess others' reputation only on the basis of complaints filed in the past; the framework is generally limited to such binary trust information. In addition, trust is evaluated only according to referrals from neighbors, whereas in our approach the evaluation is based on all the information in the system.

Xiong and Liu [2003] presented a sophisticated framework specifically applicable in P2P networks, where the decision whether to trust a peer is based on five metrics: satisfaction, number of transactions, credibility of feedback, transaction context, and community context. [Srivatsa et al., 2005] extended this work. Both papers focus on the trust model, and generally do not elaborate on the data management scheme. Specifically, in [Xiong and Liu, 2003] a P-Grid [Aberer, 2001] is used. Thus, this work is in a sense orthogonal but complementary to ours. Dewan and Dasgupta [2004] propose self-certification and IP-Based safeguards as ways of inducing trust; this work also complements ours.

Finally, gossip-based algorithms 5 have many applications in other domains, for instance replicated database maintenance [Demers et al., 1987].

7 Conclusions

We have presented a data management scheme built on gossip-based algorithms, and have demonstrated that it possesses several interesting features. Our method is decentralized, and uses no central database. It is also applicable in networks where point-to-point communication cannot be assumed. It is scalable: the time to evaluate an agent's average reputation with confidence 1 - δ and accuracy ϵ is O(log n + log 1δ + log 1ϵ ). The evaluation of trust is global, and based on all relevant information in the system, rather than only local information. We have used simple data structures: each agent merely keeps an assessment of the agents with which it personally interacted. Our method motivates absolute truthfulness, as the time to close deals may decrease as reputation increases. It is also resistant to some attacks, such as carefully tampering with the updates performed by PUSH-SUM.

We have focused on the data management scheme, and have largely ignored the trust model. However, we believe that many existing trust models can be integrated with our framework. A simple example is the binary trust model of [Aberer and Despotovic, 2001], where agents can file complaints against other agents. In our framework, each agent i sets its value rj i to be 0 if it wishes to file a complaint against j; otherwise, the value is 1. More sophisticated models may, however, require modifications to the framework. For example, an agent may give higher credibility to agents that have a high reputation (in its opinion), and weight their estimations accordingly. An interesting direction for further work would be to use gossip techniques to take even such considerations into account.

5 Also called epidemic algorithms.

8 Acknowledgment

This work was partially supported by grant #039-7582 from the Israel Science Foundation.