At 5:50 PM 5/7/96, Hal wrote: ....

It is important to eliminate a common misconception about the web of trust. Suppose Alice signs Bob's key, and Bob signs Clara's, and Clara signs Don's key. Suppose further that Alice trusts Bob and Bob trusts Clara as key signers, but that Alice doesn't know Clara. In terms of PGP's web of trust, this does not give a chain from Alice to Don which lets her trust his key. Alice has to have a signature on Don's key by someone she trusts. In this case, since she doesn't know Clara she presumably can't trust her, and hence Clara's signature on Don's key is worthless to Alice. ... Unfortunately we are left with a choice between three not very good possibilities: accept transitive trust and hierarchical key CA structures; use very flat hierarchies where one signer validates huge numbers of keys; or accept that only a small number of keys can be validated by key signatures. I think all these are troublesome and in fact it makes me question the whole notion of key signatures.

An interesting and thought-provoking essay. I've never been comfortable with the term "trust," and tend to think in terms of a related but subtly different term, "belief." "Do I _believe_ this person is who he says he is?" "Do I _believe_ this applet I am downloading will not erase my hard disk?" "Do I _believe_ MacWarehouse will ship the product I ordered last week?" "Do I _believe_ the Russians when they say they are destroying warheads?" (and recall Reagan's very accurate "Trust, but verify). (and so on, for many examples where "believe" means something more than "trust") Obviously, in many cases belief and trust are closely related, and saying I believe Eric Hughes is the same as saying I trust Eric Hughes, at least in some context. But belief also invokes other mechanisms, including independent verification (as with multiply connected graphs), "commonsense and sanity" tests, etc. And beliefs are in some sense what we are really talking about. There is no simple scalar quantity called "trust" (at least not one I can imagine), but different agents will have different beliefs about different things. One set of beliefs about signatures on keys has a lot of similarities to the "web of trust." In fact, imagine this "diminishing wavefront of belief" example: "I believe that Eric Hughes is who he says he is, and that the key he signed for me represents his signature. Further, he told me he believes Peter Wayner to be who he says he is [many philosophical issues of identity elided here], and that he believes because of several cross-checks he has made that Peter's signature as stored at the MIT site is in fact that of the journalist Peter Wayner. Because Eric believes Peter, and I believe Eric, I tend to believe Peter's signature. Peter says he believes Joe Blow, but neither Eric nor I have checked this, nor have we talked to Peter about how confidant he is, or why he believes this, so I have to say I'm not ready to say I believe in Joe Blow's signature." Can this be more mechanized? Can numbers be attached, and perhaps propagated? (I mentioned "diminishing wavefront of belief," because implicit in this viewpoint, inevitably (and rightly, I think), is the notion that "distant relations" have low probabilities of belief, all other things being equal. (All other things are not equal, in many cases, and there may be multiple paths to a person. As supporting evidence mounts, so does the confidence level, or belief. I believe [no pun intended] that some of the work in classical AI on belief networks, aka Bayesian networks, is relevant. Reasoning in such networks, where different beliefs are held about events, causes of events, reasons for things happening, etc., seems quite similar to what we have in webs of trust. In particular, one form of belief representation seems especially relevant: Dempster-Shafer theory. A nice summary is contained in a wonderful book, "Artificial Intelligence: A Modern Approach," Stuart Russell and Peter Norvig, 1995. On p. 462 they write: "The Dempster-Shafer theory is designed to deal with the distinction between _uncertainty_ and _ignorance_. Rather than computing the probability of a proposition, it computes the probability that the evidence supports the proposition. This measure of belief is call a _belief function_, written Bel(X). "We return to coin flipping for an example of belief functions. Suppose a shady character comes up to you and offers to bet you $10 that his coin will come up on heads on the next flip. Given that the coin may or may not be fair, what belief should you ascribe to the event of it coming up heads? Dempster-Shafer theory says that because you have no evidence either way, you have to say that the Bel(Heads) = 0, and also that the Bel(Not-Heads) = 0. This makes Dempster-Shafer reasoning systems skeptical in a way that has some intuitive appeal. Now suppose you have an expert at your disposal who testifies with 90% certainty that the coin is fair (i.e., he is 90% sure that P(Heads) = 0.5). Then Dempster-Shafer theory gives Bel(Heads) = 0.9 x 0.5 = 0.45 and likewise Bel(Not-Heads) = 0.45. There is still a 0.1 "gap" that is not accounted for by the evidence. "Dempster's rule" (Dempster, 1968) shows how to combine evidence to give new values for Bel, and Shafer's work extends this into a complete computational model." See why it looks promising? If it isn't clear, imagine the above example rewritten slightly: "We return to key signing for an example of belief functions. Suppose a shady character comes up to you and claims that he has a list of signatures he believes in. Given that you may or may not believe him, what belief should you ascribe to the validity of his list? Dempster-Shafer theory says that because you have no evidence either way, you have to say that the Bel(List) = 0, and also that the Bel(Not-List) = 0. This makes Dempster-Shafer reasoning systems skeptical in a way that has some intuitive appeal. Now suppose you have an expert at your disposal who testifies with 90% certainty that the shady stranger is to be believed ("trusted"). Then Dempster-Shafer theory gives Bel(List) = 0.9 x 1.0 = 0.9 and likewise Bel(Not-List) = 0.10. "Dempster's rule" (Dempster, 1968) shows how to combine evidence to give new values for Bel, and Shafer's work extends this into a complete computational model." By converting the problem of "trust" to one of "belief," and accepting that there may be "gaps," Dempster-Shafer theory has been useful in many situations for analyzing changes of belief...seems to be similar to what we face in the "web of trust." (I believe the results will be similar to Phil's heuristic that "trust is not transitive" and my point about a "diminishing wavefront of belief." One way this may be mechanized is to ask people who sign keys to make an estimate of their "belief" in each key, so that we might get something like: Bel-sub-May(Hughes) = 0.98 Bel-sub-May(Finney) = 0.96 Bel-sub-May(Wayner) = 0.70 .... Bel-sub-May(tallpaul) = 0.05 ... and so on, where "Bel-sub-May" means the belief I (May) have in some signature being properly done...FOR WHATEVER REASONS I MAY HAVE! Likewise, Hal Finney may have pretty good confidence that I am a careful checker of such things, so maybe he ascribes Bel-sub-Finney(May) to be 0.80. (The careful reader will have noticed that I switch between talking about belief in signatures and belief in methodology. It may be possible to handle these differently, but I think in a real sense they are best handled as the same thing. Thus, I am saying to Hal, "I place these amounts of trust (belief, really) in these signatures," and Hal says to me, "Well, based on past experience, I tend to believe you, at least with 80% confidence, so I'll take your estimates and pass them on, normalized by my belief factor." Not perfect, but then how can it ever be, due to the semantics of probabalistic belief.) Hierarchical systems are not necessarily any better, in that a hierarchical system may just be Bill Gates saying: Bel-sub-any_employee(Gates) = 1.0 (Thus, every employee is told to believe any statement by Bill Gates, including passing on belief in the statements of his designated key authorities!) By the way, the work on back propagation in belief networks looks to be very promising vis-a-vis the "reputations" we so often talk about. In the example above, where "suppose you have an expert at your disposal who testifies with 90% certainty that the coin is fair," imagine the results of many coin tosses. If the coin tosses turn out to be 900 heads and 100 tails, then one might expect the "belief" in the "expert" will decline rapidly. Like a bad consultant, or bad advice. Dempster-Shafer theorists have done a lot of work on how to actually compute using these belief probabilities, how to propagate beliefs, and what the limits are. Seems pretty applicable to studying webs of trust (which are actually "belief networks"). Thanks, Hal, for stimulating this discussion. --Tim May Boycott "Big Brother Inside" software! We got computers, we're tapping phone lines, we know that that ain't allowed. ---------:---------:---------:---------:---------:---------:---------:---- Timothy C. May | Crypto Anarchy: encryption, digital money, tcmay@got.net 408-728-0152 | anonymous networks, digital pseudonyms, zero W.A.S.T.E.: Corralitos, CA | knowledge, reputations, information markets, Licensed Ontologist | black markets, collapse of governments. "National borders aren't even speed bumps on the information superhighway."