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

We often want to find shortest paths in a Web of Trust (WOT). Because a (strongly connected component of a) WOT often has thesmall worldproperty, the number of points at distancek, increases rapidly withk. When searching a shortest path fromAtoB, it is cheaper to use a modified BreadthFirstSearch algorithm. Instead of only searching fromAtoB, a combined search fromAtoBandBtoAis given.

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 keyA, and Bob has a keyB, Alice can sign the key of Bob: keyBthen has signatureA.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

- Bob is who he says he is, and
- key
Breally belongs to Bob.Bof Bob, may (sceptically) accept that Alice trusts that keyBrealy belongs to someone named Bob.A

trust pathfrom (the key of) Dave to (the key of) Eve is a list of keyswhereDave->X->Y->Z->EveDavesignedX,XsignedY, etc. Dave may trust that the key labeled 'Eve' actually belongs to Eve, if there is a trust path fromDavetoEve. 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.

A Web Of Trust (WOT) is a labeled, directed graph whereAssume that the datastructure for the WOT allows, for each point

pointsrepresent PGP keyslinesrepresent signatures ;A->BifAhas signedB- the
distancefrom pointAto pointBis the length of a shortest path fromAtoB- the
around a pointk-ringAis the set of points at distancekfromA.v, to find the points connected tovand the pointsvconnects to.in (Finding a shortest path fromv) = {x|x->v} [ all signatures ofv] out (v) = {x|v->x} [ all keys signed byv]AtoBis straightforward. Use BreadthFirstSearch (BFS):

phase 1: start atA, and find (usingout) thek-rings for k=1,2,3,.. untilBis found at some distanced(success), or somek-ring is empty (no path found). Mark each visited point with it's distance toA.phase 2: walk (usingin) fromBtoA, visiting points with distanced-1,d-2, etc untilAis found,result: the reverse of the walk in phase 2.Note that finding a path from

AtoB, could also start atB, if we switch the roles of (A,B) and (in,out) in the algorithm.We will use this symmetry to modify BreadthFirstSearch.

phase 1: start atB, and find (usingin) thek-rings for k=1,2,3,.. untilAis found at some distanced(success), or somek-ring is empty (no path found). Mark each visited point with it's distance toB.phase 2: walk (usingout) fromAtoB, visiting points with distanced-1,d-2, etc untilBis found.result: the walk in phase 2.

A WOT usually has thesmall 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 distancek. It is much cheaper to find amiddle manM: a point on the the shortest path fromAtoB. The path fromAtoBisAs it turns out, finding a middle man is easy.A-> ... ->M-> ... ->BInstead of searching from

AtoB, we can alternate: compute the next ring aroundA, then the next ring aroundB, thenAetc. 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

- marking both
AandBinitially with '0' causes a problem in a special case :A<->M<->B. To avoid this, for marking usedepthinstead ofdistance, wheredepth=distance+1. This can be achieved by initially markingAas '+1' andBas '-1'.- mark points reached from
Aas 2, 3, 4 etc- mark points reached from
Bas -2, -3, -4 etc- when computing the next ring around
A,

- ignore points with a mark greater than 0,
- stop if a point is found with a mark smaller than 0 ; we found the middle man
- mark other points with the proper (positive) mark
- when computing the next ring around
B,

- ignore points with a mark smaller than 0,
- stop if a point is found with a mark greater than 0 ; we found the middle man
- mark other points with the proper (negative) mark
- to keep the algorithm simple, treat these cases as special :
A==BandA->B.PGP pathfinderis written in an interpreted language (Perl) and runs on a rather slow server, this improvement was quite noticable.

Instead of simply alternating betweenAandB:the program should proceed with the smallest ring, be it around

- next ring around
A- next ring around
B- next ring around
A- ....
AorB. The adaptation of the algorithm is trivial.

If we want to show multiple, disjunct paths, we must succesivelySuppose we start with a graph that is one strongly connected component (for every

- find a shortest path, and show it
- delete the (interior of) the path from the graph
- repeat until there are no more paths, or enough paths are shown
AandB, there is a path fromAtoB). When we delete points from the graph, it may become unconnected. Usingstraightforward BFScan be costly when there is no path. WhenAis very well connected, andBisn't, we have to search almost the entire graph to find out thatBisn't reachable fromA.

BFS-IandBFS-IIgenerally terminate much more quickly when there is no path.