homepgpnotes [Henk Penning]

computing shortest paths in WOTs

author Henk P. Penning
date Thu Aug 26 15:18:35 MEST 2004
regards PGP pathfinder

abstract

We often want to find shortest paths in a Web of Trust (WOT). Because a (strongly connected component of a) WOT often has the small world property, the number of points at distance k, increases rapidly with k. When searching a shortest path from A to B, it is cheaper to use a modified BreadthFirstSearch algorithm. Instead of only searching from A to B, a combined search from A to B and B to A is given.

introduction

Skip this if you know what PGP is.
In the Pretty Good Privacy (PGP) public key system, users generate (one or more) keys, and label them with a name and email address. When Alice has a key A, and Bob has a key B, Alice can sign the key of Bob: key B then has signature A.

It is the rule that before Alice signs a key of Bob, Alice must establish (by photo id) that

Other users, who observe that Alice signed key B of Bob, may (sceptically) accept that Alice trusts that key B realy belongs to someone named Bob.

A trust path from (the key of) Dave to (the key of) Eve is a list of keys

Dave -> X -> Y -> Z -> Eve
where Dave signed X, X signed Y, etc. Dave may trust that the key labeled 'Eve' actually belongs to Eve, if there is a trust path from Dave to Eve. A priori, shorter paths are better than longer paths, and having multiple, disjunct paths is better than having a single path, or no path at all.

shortest paths in WOTs

A Web Of Trust (WOT) is a labeled, directed graph where Assume that the datastructure for the WOT allows, for each point v, to find the points connected to v and the points v connects to.
  in  ( v ) = { x | x -> v }     [ all signatures of v  ]
  out ( v ) = { x | v -> x }     [ all keys signed by v ]
Finding a shortest path from A to B is straightforward. Use BreadthFirstSearch (BFS):

Note that finding a path from A to B, could also start at B, if we switch the roles of (A, B) and (in, out) in the algorithm.

We will use this symmetry to modify BreadthFirstSearch.

Improvement I

A WOT usually has the small world property: the shortest path length (degrees of separation) is small in view of the size of the graph. This means that the number of points at distance 1, 2, 3, etc grows fast. The cost of computing the points at distance 2k, is much higher than twice the cost of computing the points at distance k. It is much cheaper to find a middle man M: a point on the the shortest path from A to B. The path from A to B is
A -> ... -> M -> ... -> B
As it turns out, finding a middle man is easy.

Instead of searching from A to B, we can alternate: compute the next ring around A, then the next ring around B, then A etc. Stop when a point in an 'opposite' ring is found (middle man!), or one of the rings becomes empty (no path exists).

Adapting the algorithm is simple:

Because my PGP pathfinder is written in an interpreted language (Perl) and runs on a rather slow server, this improvement was quite noticable.

Improvement II

Instead of simply alternating between A and B : the program should proceed with the smallest ring, be it around A or B. The adaptation of the algorithm is trivial.

finding multiple, disjunct paths

If we want to show multiple, disjunct paths, we must succesively Suppose we start with a graph that is one strongly connected component (for every A and B, there is a path from A to B). When we delete points from the graph, it may become unconnected. Using straightforward BFS can be costly when there is no path. When A is very well connected, and B isn't, we have to search almost the entire graph to find out that B isn't reachable from A.

BFS-I and BFS-II generally terminate much more quickly when there is no path.


Valid HTML 4.01!
Henk P. Penninghomepgppathfinder and key statistics