Web of Trust - Mean Shortest Distance

Mean Shortest Distance

In statistical analysis of the PGP/GnuPG/OpenPGP Web of trust the mean shortest distance (MSD) is one measurement of how "trusted" a given PGP key is within the "strongly connected" set of PGP keys that make up the Web of trust.

Drew Streib wrote the following in his explanation of keyring analysis:

There are a variety of metrics one could apply to this set, but I've chosen initially to measure the "mean shortest distance" (MSD) to each key. Since every key is reachable from every other in the strong set, it is possible to find out the shortest distance (number of hops) to any given key from any other key. Averaging these distances gives the MSD to that key from every other key in the strong set.

It is desirable to have as short as possible an MSD to your key, as that means that on average, people can reach your key quickly through signatures, and thus your key is relatively more trusted than a key with a higher MSD.

NOTE: This does not mean that you should universally trust keys with a low MSD. This is merely a relative measurement for statistical purposes.

The MSD has the property of being no more than 1 higher than your lowest signature. In the worst case, every key in the strong set could reach you by getting to that key, plus 1 hop to get to you. It also encourages the joining of keys that are separated by great distances in the graph, as it will make you a highway of sorts for shortest paths between keys in those groups. In the end, it encourages an overall tightening of the world graph, shortening distances between key owners.

MSD has become a common metric for analysis of sets of PGP keys. Very often you will see the MSD being calculated for a given subset of keys and compared with the global MSD which generally refers to the keys ranking within one of the larger key analyses of the global Web of trust.