Nowadays the concept of trust in computer communications starts to get more and more popular. While the idea of trust in human interaction seems to be obvious and understandable it is very difficult to find adequate and precise definitions of the trust-term. Even more difficult is the attempt to find computable models of trust, particularly if one tries to keep all psycho-sociological morality from the real life out of the model. But, apart of all these problems, some approaches have been introduced with more or less success. In this paper our focus lies in the question, how far recommended trust-information can be the base of a trust-decision. We introduce trust-decisions as the final step of a randomly chosen path in a decision-tree where reliability and certainty plays a big part in the creation of the tree. One advantage of the procedure to induce the trust-decisions on the base of randomness lies in the higher resistance against false information from malicious entities because there is a chance that paths through the tree will be chosen which exclude information of these entities. Besides the new approach of trust-decisions on the base of recommended trust-information, we show how far (meaning with how many recommenders) it is reasonable to recommend trustinformation, we will give suggestions how to optimize the tree of reliability, certainty and trust, so that in an adequate time trustdecisions are possible and we show the influence of bad and malicious entities on the results of the trust-decision.
Nowadays the concept of trust in computer communications starts to get more and more popular. While the idea of trust in human interaction seems to be obvious and understandable it is very difficult to find adequate and precise definitions of the trust-term.
Several approaches to handle direct trust relations on the base of
reputation exist. Dewan [
The trust model of Pirzada and McDonald [
Later on several models for calculating trust on the base of
recommendations have been presented. Josang [
In our model of trust-relations and trust-decisions we try to keep trust-information untouched as long as possible until we need to make a trustworthy decision. But first, we have to make some definitions.
D
Y
First we need Entities do define the trustee and the trusted party of a direct-trust relation (def. 1 (1, 2)) If the number of individual experiences of the trustee is not worth to build a trust-relation the direct-trust is not defined (def. 1 (3)). No recommended experiences but only new individual experiences may lead to new direct-trust. This paper does not give a definition of the directtrust and how the individual experiences have influence in the trust-model. But we show how to come to a trust-decision, if no direct-trust exists, but only recommended direct-trust information. The trust decision in our case is always a yes/no decision which depends on the trust relation in combination with the concrete trust-question (def. 1 (4)).
To justify the recommended information we introduce reliability as the probability that the given trust-information was reliable (def. 2 (5)). If the past experiences have no statistically relevance or are outdated, the reliability is not defined (def. 2 (6)) 0.7 0.8
0.5 B 0.6 0.4 0.7
C E A X 0.9 0.4
To understand the process of a trust-decision let's start with the short example of figure 1, where X tries to make a trustworthy decision towards Y. For that reason, the figure shows only direct trust towards Y and the reliabilities, where no direct trust towards Y is defined. Only E and D have direct-trust-relations towards Y. But X has a set of reliable neighbours (def. 3 (7)).
With such a given network the next stage in the trust-decisionprocess is the building of a decision-tree out of the network (fig. 2, next page). First of all, the tree represents all possible paths in the network from the entity X to a direct-trust-relations regarding Y. The tree is extended by branches to undefined trust-relations (⊥). These braches are inserted after each entity and represent the possibility that the entity was not reliably.
D 0.5 0.5 0.6 0.4 0.7 0.3 0.4 0.6 0.9
0.1 0.7
0.3 0.8 0.7 0.3
0.5 txen ittyen ro ty
n ty i itan trae r c ce un If a trust decision has to be done the tree is used to choose the used trust-relation by a random selection of the path. Starting from the root of the tree the next edge is chosen randomly. This random selection must take the weight of the edges into account. One important criterion in this decision-tree is a new certaintyvalue C (def. 4 (8-11)), telling how probable (certain) it is if a trust-decision is started to reach a direct-trust-relation and not "⊥".
The uncertainty in that decision lies in the fact that recommended information may be not reliably and therefore no prediction of the given trust-information is possible.
Looking at definition 4 (11) shows that an absolute certainty is given if a direct-trust-value exists. In this case, the direct-trust is calculated using individual experiences and for these reasons defined as certain. On the other hand, absolute uncertainty exists if no direct-trust exists and no further entities with reliability that may recommend trust-information. The otherwise-alternative in definition 4 (11) will be specified later because different calculation-strategies are possible.
The transformation of a trust-value-network (fig. 1) to the decision-tree (fig. 2) is best understood if the algorithm of the trust-decision is clear.
The trust decision in def. 5 (12, 13) is always a decision which
depends on the trust relation in combination with the concrete
trust-question ϑ which tells if the trustee trusts the trusted. The
algorithm in def. 5 (14) start with the trustee entity (line [
To prevent loops, further choices may not take visited entities into
consideration (line [
But picking up always entities with the highest values has a big disadvantage. In identical trust-decisions always the same entities are involved. For that reasons this strategy would lead to a higher sensitivity against malicious entities. A better way for the choice would be to pick up entities by random, weighting them by the certainty of the sub-tree. This would increase the resistance against malicious entities because with a certain probability, ways are chosen which pass these entities, if such ways exist. Therefore, the calculations of the certainty in def 4 (11) will be adjusted with def 7 (17) using def 7 (16).
As the calculation of the certainty of an entity towards a targetentity depends on values of the certainties of the sub-tree (and therefore on each possible loop free path to the target-entity), the complexity of the calculation is obviously exponential. Since the calculations of the certainties are essential for the process of the decision-tree, the process itself has exponential complexity. Let's go back one step and reconsider the meaning of the certainty-value of an entity towards a target-entity (def 4). This value gives the probability not to make the trust-decision on the base of a undefined trust-relation, but on the base of a direct-trustrelation. If we call the opposite of certainty uncertainty, the uncertainty gives the lower bound of possibility to make the trustdecision with no secure information. The value is the lower bound because this probability is only reached, if all entities recommend in good faith but the probability may be higher with malicious entities. The higher the uncertainty the more useless is the start of the decision-algorithm. Therefore, high certainty-values are the aim of the decision-process. But with exponential complexity the calculation may be useless too.
In this section we try to reduce the complexity of calculation. For this, we call the certainty on the base of the calculations in def 7 the reference certainty-values. We try to reduce the complexity in two ways: The first solution limits the maximum number of hops to the target-entity. The second solution limits the minimum certainty of a sub-tree. With these limitations, the calculated certainties will be higher because sub-trees will be removed with additional unreliability. In the next-subsections we try to find out, how much the reductions lead to inaccurate certainty-values.
To limit the decision-tree to a maximal number of hops, some definitions of def 4 have to be adjusted with a depth-factor:
To see the influence of these new restrictions on the certaintyvalues several simulations have been run. Because of the exponential complexity of the calculation of the reference certainty values, the number of entities of a random network was restricted to 20 entities with pre-initialised reliability of 0.5 to 1. We assume that in real conditions most entities act fair and therefore gain this high reliability.
The simulations with random networks have been run 30 times and averages have been built. The results are displayed in figure 3 (next page). The values of "without limitation" represent the reference certainty. "Hops to target" gives the number of hops until an entity is reached with direct-trust regarding the target. Watching the certainty values of the simulation without restriction, one can see that even with the high initial reliability values of 0.5 to 1 the certainty passes the 0.2-line after 8 hops already. This gives a clear indication that recommendationinformation is not the base of the trust-decision after very few hop-distance (in the majority of the cases). A limitation to 8-hoprecommended information from this point of view seems to be rational at first sight.
Let's see how the max-hop-restriction has influence in the certainty. The certainty falls to zero, if the distance to the targetentity is higher than the maximal number of hops. Limiting to 8hop distance keeps the certainty-values in a 10%-region (absolute) from the reference value until this value passes the 0.2line. A restriction to 8-hops seems (from this point of view) rational likewise.
How has the complexity changed with the restriction to max-hopdistance? In worst case, if all entities are inside the max-hopdistance, the strategy has no effect. It is still exponential. But in random conditions the restriction has a positive effect. In our simulation with random trust-relation-networks the calculation was with a 6-hop-limit 107-time faster and with an 8-hop-limit 14-time faster.
To limit the minimum certainty, only def 4 (10) has to be adjusted in the following manner:
If the certainty of a branch falls below a given limit, its certainty is set to zero. One problem in this definition lies in the fact that the calculation of certainties of the sub-tree is still needed and therefore no benefit is given. But it is possible to cut down the tree with breadth-first-search from the root of the tree, calculating not with definite values but with "less-than" values. In best-case the certainty of a sub-sub-tree may be 1. This value gives an upper bound, which will be adjusted if the next level of the breadth-first-search is reached. At the end it is possible to remove a branch only on the base of the product of the recommendationvalues, if this "less-than"-certainty value falls below the limit. To choose minimum certainties which have a similar effect than the limitation of maximum hops one has to choose 0.4 to be comparable with 6-hop-limit and 0.3 to be similar to with an 8hop-limit (fig. 4).
But compared to the limitation of the maximum hops this limitation is slightly less effective concerning the reduction of the computational period: In the case of a minimum certainty of 0.4 the calculation is only speed up by 34 (compared to 107 with 6hop limitation) and at a minimum certainty of 0.3 by only 9 (compared to 14 with 8-hop limitation).
Similar to the max-hop-limitation, this approach of reducing the complexity has no effect in worst-case running time. In dense networks both methods will have nearly no effect.
One reason to make the trust-decision on the base of random choices using a decision-tree was the resistance against malicious entities. To prove this assumption another simulation series was started.
Out of the 20 entities in the network, a number of malicious (or bad) entities recommend false information. In one scenario, all malicious entities recommend better reliability-values than given. This enhances the chance to choose a fake sub-tree given by the malicious entity. In the second scenario, all malicious entities report worse reliability-values than given. This reduces the chance to choose this sub-tree and in worse case the only possible paths to a direct-trust-value. In figure 5 the results are reported. By the (statistically seen) small number of runs, some results can only be explained with the unfavourable distribution of the malicious entities in different simulation-scenarios. But some results can be identified.
Obviously the influence of better values is smaller in this simulation, because the initial reliability-values were already high.
The difference between the reference value and the manipulated value can be interpreted as the probability that a malicious entity was reached during the process of selecting a direct-trust-value. Therefore this difference represents the probability that the trustdecision was made on false information.
This difference seems to be independent of the number of hops to the target-entity but is related to the number of malicious nodes. But this is an expected behaviour: If more of the nodes are malicious, one might expect that in average more of the paths pass one malicious node. More important is the fact that in statistically paths are chosen, which do not pass these nodes.
In this paper we presented a strategy to make trust-decisions on the base of recommended direct-trust-information trying to minimise the influence of malicious entities. This is done by using all recommended direct-trust-information in a random selection process and use only the finally chosen direct-trust-value to evaluate the trust-decision.
Because of the randomness in this selection process, paths without the influence of malicious entities are chosen statistically. The new introduced certainty-value gives an indicator of the reasonability of trust-decisions on the base of the recommended trust-information. One can state that decisions on such a base are unreasonable after a very short hop-distance towards the target (68 hops), even under good conditions (very high recommendationtrust-values).
One problem with this certainty-value lies in the fact that its calculation has exponential complexity and therefore can only be declared as a reference value. Reducing the decision-tree by limiting the max-hop-distance or by restricting the minimum certainty have positive effects on the calculation-speed but have still exponential complexity in the worst case.