Criteria for trust metrics

From TrustLet, a free, collaborative project for collecting and analyzing information about trust metrics.

Here we try to find some criteria for trust metrics. We're inspired by Bram Cohen on trust metric criteria. Bram Cohen is the creator of BitTorrent.

Contents 1 Relation to Bram's criteria 2 The criteria 3 Note on normalization 4 How much information is needed to determine a trust metric? 5 General schematic for a trust metric algorithm 5.1 Upper bounding algorithm 6 So what will we probably end up with? 7 More on the metricness of trust metrics 8 Discussion

[edit] Relation to Bram's criteria

We started this page by copying those down and rephrasing them, but in the end, we found that we reformulated some of them:

• I rolled "adding nodes" and "adding certifications" into "monotonicity", because it's similar to the way that in a monotonic logical inference system you can add new facts to the database without making old conclusions invalid
• I renamed "total strangers" "independence of disconnected components" -- although note that by "disconnected" I just mean disconnected in one direction, I don't know if there is another word for that.
• I renamed "extending chain" "decreasing chain" and changed the less than to a less than or equal to
• I replaced "terminators" with something stronger and renamed the result "composition"
• I replaced "redundant backlinks" with "self-confidence"; "self-confidence" combined with "composition" implies "redundant backlinks"
• I left out "full attestation" because I don't understand it. Does that mean that the label of any edge which goes into a "leaf node" (or "statement node") must be 1?
• I left out "sideshow" because it is implied by composition and self-confidence (the conditions in "sideshow" mean that all paths from me to the statement through B must involve loops from A to A; but by self-confidence, the last link of the loop can't influence A's trust ratings, and by composition, since we have to go through A to get to B, B doesn't matter except insofar as it affects A)
• I added "composition (multi node)", which is a stronger version/generalization of composition
• I added "nonincreasing bottleneck", which is a much stronger version/generalization of nonincreasing chain

In general, I have eliminated the notion of attestation -- if you want attestation, you could say that some of the leaf nodes represent not trusted people but rather trusted statements. Of course, you may want the trust metric to treat people and statements differently, in which case you really need to include the notion in the formalization. But it seems to me that the problems are separable; first consider the subgraph of people, and define a trust metric for that, and then define a separate "attestation trust metric" which is a function of the trusts of the people attesting. And it seems to me simpler to work that way, because then you only have to work with graphs with one kind of node, mathematically.

The new set of statements presented on this page don't have the property that none implies the other, especially since many of them are slightly stronger versions of other ones. I believe that the obvious subsets of these statements would have the property that none implies the other, but I haven't checked.

[edit] The criteria

We will consider a finite, directed, labeled, weighted graph, possibly with a distinguished node (the root node) or group of nodes. The nodes represent something like users (although leaf nodes could also represent statements that users attest to), the edges represent something like certifications, the edge weights represent something like the strength or certainty of the certification, with higher edge weights better.

A constraint on graphs is a set of graphs (that is, only graphs which satisfy the constraint are in the set).

A trust metric is a pair (graph constraint, function from f(graph, node, node) --> real number). We will often refer to the function as simply the "trust metric" when there will be no confusion. Often we'll refer to "the trust of a node", which means that we are assuming that a node "A" refers to user calculating trust, and that they are asking for f(graph, A, NODE). Unless otherwise specified, all of the properties are universally quantified for A, that is, you could prepend the phrase statement "for any node A, ..."

(Why does the metric include a constraint? Because we are going to have properties like "increasing the weight of an edge can't decrease trust". But what if you want to weight the value of a certification from user A to user B inversely to the total number of certifications given out by user A, like TrustFlow? In this formulation, you would do that by constraining the outedges from any node to sum to 1)

We will write A->B as shorthand for "there is an edge from A to B".

monotonicity

adding new certifications, or adding new nodes, or increasing the weights of any set of edges, can never decrease the trust metric for any node

independence of disconnected components

If there are two graphs G and G' and the nodes and edges and node and edge labels on all paths from A are the same in both G and G', then for any B, f(G,A,B) = f(G',A,B). In other words, you don't care what happens in parts of the graph that you can't reach.

nonincreasing chain

If there is only one edge from A, and that edge goes to B, then for any node C, f(graph,A,C) <= f(graph,A,B)

decreasing chain

If there is only one edge from A, and that edge goes to B, then for any node C, f(graph,A,C) < f(graph,A,B)

skepticism

If there is no edge from A to B, then f(graph,A,B) < 1

composition (one node)

Let graphs G and G' both contain no path from A to C except paths through B. If f(G,A,B) = f(G',A,B) and f(G,B,C) = f(G',B,C) then f(G,A,C) = f(G',A,C).

composition (multi node)

Let graphs G and G' both contain no path from A to C except paths through some set of nodes B. If f(G,A,b) = f(G',A,b) for all nodes b in B, and f(G,b,C) = f(G',b,C) for all nodes b in B, then f(G,A,C) = f(G',A,C).

self-confidence

If G and G' are identical except perhaps edges or the weights of edges which go towards "me", then the trust metric does not change for any node.

unreachability

the trust value of B is always 0 if there is no path from A to B.

nonincreasing bottleneck with Omega = ...

If there are no paths from A to C except paths through some set of nodes B, then the trust of C is <= some function Omega(trust(B)), where trust(B) is the list of trust values [f(graph,A,b_1), f(graph,A,b_2), ...] . For example, if Omega is the sum function, then the trust of C can never be more than the sum of the trusts of any cutset that separates A from C in the graph. A more conservative choice would be "max". Intuitively, Omega represents how you react to a situation where a bunch of people you trust all trust a third party -- how much can that boost the trust of the third party? To put it another way, how much does popularity count?

[edit] Note on normalization

If Omega is sum, and if the recipe for calculating trust is just to multiple previous node weight by the edge weight and sum if there are multiple incoming nodes, then the bottleneck property leads to a normalization constraint on the graph (if you want to accomodate all graph shapes, at least, which I think we do). That is, for any node N, sum(edge labels of all edges emanating from N) <= 1.

Proof sketch: Say G contains edges from A to k different nodes K_1, ... K_k, and that no other nodes go to the Ks, and say G contains edges from each K_i to a new node B. The trust of B is then the sum of the trusts of the K_is, and this is sum(edge labels of all edges emanating from A). But by the bottleneck property with Omega = sum, all paths from the root to B must go through the Ks, therefore they must all go through A, therefore the trust of B must be <= the trust of A

[edit] How much information is needed to determine a trust metric?

An important question is, do these properties (with the addition of a function Omega) give you enough information to completely determine a trust metric? If not, what else is needed?

I don't think these properties determine it yet.

[edit] General schematic for a trust metric algorithm

The best way to prove that some set of criteria determine a trust metric would be to find some an algorithm with some free parameters, and then to prove that any trust metric that meets the criteria can be calculated by that algorithm, and then to prove that the free parameters in the criteria determine the free parameters in the algorithm.

So, let's work on making that algorithm.

We'll consider only the subset of the graph that is connected to a root node.

Step 0: Formulate the graph structure in the way we are using it. Note that this may involve some computation based on the trust values that you are given; for instance, you may need to normalize the outgoing edges from each node. This is because the formalization we are using doesn't allow the addition of new outgoing edges from a node to reduce the effect of the other existing edges, so this sort of information must be incorporated into the graph with preprocessing.

Step 1: Start with a root node, A. Label it with "1".

Step 2: Let S_1 be the set of all nodes B with an edge A->B. We are going to label all of these nodes with their final trust values. We need a function g_1(e) that accept the trust of the node A, and the label of the edge from A to B, and tells us what label goes on node B. Most likely any trust metric can be rephrased so that g(e) = e, but I haven't proven that.

I feel that these will be the initial steps of the algorithm if we have a single root (I think that step 2 will be shown to be a special case of the later steps of whatever we come up with).

Now is where it gets more tricky.

To get a sense of the kinds of situations we have to deal with on the next step, consider a 2D lattice. The root node is one of the nodes of the lattice, let's call it "0". In step 1, the root node is labeled. In step 2, the 4 neighbors of the root node are labeled (call them (-1,0), (1,0), (0,-1), and (0,1)). What do we do next? It seems that, for some trust metrics, we can't assign the final value of the next node in one step. For example, consider node (0,2). Although the composition property tells us that we can ignore node (0,0) (because we have a cutset separating (0,0) from (0,2); the four neighbors of (0,0)), there are paths from each of the other 4 labeled nodes to (0,2) which don't cross each other. Therefore, it seems like we don't want to assign a final trust value to (0,2) until we have assigned final trust values to each of its four neighbors (of which 3 are currently unassigned). But the same situation exists with any of the currently open nodes. So how do we make progress?

So, I assume this means we need an iterative algorithm. I don't know too much about the theory of those, though -- is there one iterative algorithm which can be proved to be sufficient for any trust metric in this situation?

Note btw that if we allowed multiple roots then we'd have the same problem on step 2 that we have here. So, conceptually, it may be simpler to just consider that.

My intuition is that we can in fact find some general algorithm. I mean, trust always decreases as you get farther from the root(s), except when different streams of trust "merge", in which case you are bounded by Omega by the bottleneck property. So maybe we can draw the "isoclines" of the metric space, i.e. if you start on top of a mountain and want to map the space around you, first identify all the points that are 20 feet below you or higher, etc. Or to put it another way, they are trust metrics, right? So there is some notion of "distance" between any two nodes A and B, with "far" nodes getting less trust; so we can first identify all nodes that are distance 1 or less from us, then all nodes that are distance 2 or less from us, etc.

Other random notes about the algorithm:

Note that if you wanted to have the trust at each step depend not only the trust of the neighbors, but also on distance from the root node(s), you could generalize this by having the edge labels be not just real numbers, but rather pairs (distance, certification level). If you want to use the properties given above (with appropriate generalizations), all you really need is a partial ordering on edge labels, I think.

[edit] Upper bounding algorithm

Since most of the properties only give us upper bounds on trust, maybe the best we can do so far is to get an upper bounding algorithm.

A free parameter of this algorithm is function g. g() takes a list of pairs [t, e], where t is a trust value and e is an edge weight. If the list of nodes which have edges to node C is B_1, B_2, ..., then the output of g([(trust(B_1), edge weight of B_1->C), (trust(B_2), edge weight of B_2->C), ...]) tells you what the trust value of C is.

Steps 0,1 as above.

Step 2: for every unlabeled node, we'll assign it a temporary upper bound. For each unlabeled node D, we do these substeps:

Step 2a: Calculate the set of all nodes C which have an edge to D. For each node C, do the following substeps:

Step 2a.i: Make a list L of all paths from a root node A to C. Prune this list until we have a list of uncrossing paths (this step is not necessary but makes it more efficient and intuitive)

Step 2a.ii: Associate each path in the list with the trust value of the last labeled node in the path. Let S be the set of these nodes.

Step 2a.iii: Note that S forms a cutset separating C from A. Therefore, by the bottleneck property, an upper bound for the trust value of C is A.

Step 2b: The temporary upper bound assigned to D on this iteration is g(upper bound(c_1), edge from c_1 to D)

Step 3: iterate this, except that now instead of using the actual trust value of the last labeled node in the path for step 2a.ii, just use the upper bound from the previous step of the second to last node.

I haven't proven this but I bet this will eventually converge.

Hmmm, this looks suspiciously like network flows. I guess it is network flow if the g function is chosen to just be mutiplication of the node label of the previous node by the edge weight.

The algorithm could also keep track of lower bounds in a similar way at each step. In which case, in order to show that setting the free paramters of the algorithm determines a trust metric, we need to prove that upper and lower bounds calculated converge. Yuck!

[edit] So what will we probably end up with?

Maybe we'll end up saying that the algorithm has as free parameters only the function g(), although what I'm afraid of is that for some functions g(), convergence could go different ways, so we'll need some other parameter to decide what to converge to. Alternately, maybe we'll just have to impose some reasonable-sounding properties on g() in order to guarantee convergence.

If we do only have g(), the next step is to translate the properties we talked about earlier into constraints on g(). Then at the end we'll see how much freedom we have for g().

The final step would be to prove that every g() in that class is workable. At that point, we'll have characterized the entire class of trust metric algorithms in a simple form.

This would be nice because then we go through all of the proposed trust metrics, and figure out the g() that they correspond to (or for some we would realize that they don't fit all of the criteria, and then we could say why they suck). And make a nice table. Maybe we'd even figure out that some trust metrics which seem different are actually identical.

Assuming we can finish the analysis, I'm kind of interested in writing a paper on this if anyone is interested. cipergoth? Paolo? Bram?

[edit] More on the metricness of trust metrics

The metric space properties of a distance metric are:

• d(x, y) > 0 (non-negativity)
• d(x,y) = 0 <--> x = y
• d(x,y) = d(y,x) (symmetry)
• d(x,z) <= d(x,y) + d(y,z) (triangle inequality)

Given a "trust metric" (which isn't a distance metric), can we always induce a distance metric ("trust distance")?

Now, for trust metrics, we don't really have symmetry; but I suppose that, given any root node (or set of root nodes???), we only care about things from their perspective, so if we induce a "distance" on the graph it should correspond (inversely) to how much they trust people. So maybe we can have symmetry-abiding metric once we fix on a root node.

"d(x,y) = 0 <--> x = y" says that the (only) person with 0 "trust distance" from you is yourself.

Non-negativity is pretty obvious. If distance is inversely related to trust, you can't trust someone else more than you can trust yourself.

To say exactly what the triangle inequality means, we really have to pick an actual relationship between "trust distance" and the trust metric. But one thing it says regardless is something like the "monotonicity" property; if you have one path from the root node (X) to node Z, and that causes you to assign trust T to Z, then if you add another, alternate path from X to Z, that can't decrease the trust you place in Z.

So it's looking like we will probably be able to induce a distance metric for any trust metric and choice of root nodes. All we gotta do is choose a relationship that lets the effect of path composition in trust-metric land be bounded by the addition operation when we transform to distance-metric land.

-- BayleShanks

[edit] Discussion

This stuff reminds me of two mathematical formalisms.

• Category theory, which is like (multi)graph theory but with paths and path composition (well okay, most of "category theory" is a bunch of algebraic stuff, but categories themselves are multigraphs with paths and path composition)
• The notion of "d-separation" in Bayesian networks, although I suspect there will be no use for something as complicated as that since trust never flows "backwards" from a target of an edge to its source. But its function is similar; to let you know, in a Bayesian network, when two nodes are independent given full knowledge about some other set of nodes.

-- BayleShanksImage:Example.jpg