The Leaf of Trust
One of the most interesting and controversial aspects of Phil Zimmerman’s PGP was that it avoided any central repositories of information, relying instead on what Phil labeled the “web of trust.” The idea was that Alice “trusts” Bob, and Bob “trusts” Charlie, there’s some transitive trust that you can establish.[1] (I’m going to stop putting trust in quotes, but keep using it in the sense of this web of trust.) These trust relationships are one way and publicly expressed in the form of signatures. That is, Alice indicates her with Bob by means of signing Bob’s key. Bob may choose to sign Alice’s key, but doesn’t have to.
Setting aside all of the security properties of the idea, it creates a fascinating set of published data around social networks. In “Wotsap: Dissecting the Leaf of Trust,” Jörgen Cederlöf writes:
After implementing the group matrices I figured it would be nice to see the group matrix of a much larger group. (If you are a mathematician, the Web of Trust is a large directed graph where the vertices are called “keys” and the edges “signatures”. There are four different types of signatures, just think of them as four colors of the edges. The group matrix is the adjacency matrix of this graph. You probably want to take a look at the FAQ, especially the part about MSD.) I generated a PNG image with the keys sorted in MSD order and expected little more than random noise. When I first saw the result I thought I had done something wrong, but a little bit of thinking revealed that the resulting leaf-like shape was perfectly natural, almost unavoidable.
Thanks to Nicko for pointing out the emergent properties of the web of trust.
[1] I attempted to quantify that in a message to the cypherpunks list, “reputation credts.” Rafe pointed out that the system could be made to oscillate, and I abandoned it. In retrospect, I’m pretty pleased with what I wrote, even if the system wouldn’t have worked–there’s a lot that’s still applicable to reputation and social networking and identity projects.
That’s absolutely fascinating, and I look forward to looking at this data more, maybe even playing with it.
The structure is fairly intuitive: the rows and columns are the same list of keys, sorted by Mean Social Distance, or the average number of hops you have to make to get to that key from all other keys. The lowest social distance keys (up and left) can be thought of as at the “center” of the network. A dot is made at [X, Y] when key X signs key Y.
Why the leaf structure? It has to do with how the are sorted: any highly connected key is going to have a low social distance. In order to produce a dot in the lower left quadrant, a well-connected key [low x] would have to sign an high MSD key [high y]. But now anyone trying to reach Y could just go through X, reducing its MSD and bringing it up in the order.
The line that forms the boundary of the leaf shape is an emergent property, since the MSD of many keys is defined by being one greater than one highly connected neighbor.