Dempster-Shafer Theory and Belief Networks (Re: Transitive trust)

[tcmay@got.net (Timothy C. May)]

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."