Transitive trust and MLM

-----BEGIN PGP SIGNED MESSAGE-----

I have a few thoughts relating to the "web of trust" versus
hierarchical key certificate systems.  This description is pretty
elementary and is intended more for people who have not been familiar
with the issues before.  First some background.

The problem to be solved is how to know that a particular public key
is actually associated with a particular person.  This actually gets
into some fuzzy philosophical areas in terms of what we mean by a
person and what this association involves, but let's avoid those and
just consider the specific question of binding a key to a particular
email address and/or user name.

Most of the "corporate" systems being advanced today use a
hierarchical approach.  One or a small number of trusted key
certification authorities (CAs) are at the root of a tree.  The root
CA issues key signatures binding keys to ID's.  However usually these
are not the ID's of end users, but rather of other lower-level CA's
who will be associated with some smaller domain.  These may sign yet
other CA's keys, until the whole world is partitioned into small
enough pieces that the lowest level CA's actually sign user keys.

This is often mapped onto a corporate model where a company has a
master CA key which gets signed by the root CA (or perhaps by a lower
level CA between the root and corporate level), and which then,
depending on the company size, may directly sign the keys of
employees, or at the other extreme will sign keys for a division,
which will sign them for a department, which will sign them for a
group, which will then sign the employee's keys.  Similar structures
can be used for educational institutions as well.

The idea behind this is that at each level only a relatively small
number of keys are needed, and the signatures are on entities closely
related to the key doing the signing.  So the key signer is in a
position to verify the accuracy of the signatures he is making.

PGP uses a completely different system which Phil Zimmermann calls the
"web of trust".  It also uses the idea of key signatures, but there is
no hierarchy.  Instead, each person individually decides which other
signers he will trust.  A key which has a signature from a trusted
signer is accepted as validated.  PGP also allows people to specify
other signers as partially trusted.  A key will be accepted if it has
multiple signatures by partially trusted signers.

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.

I had many discussions with Phil during the time when he was
developing this concept, and he was adamant about the importance of
this point.  The phrase he used was "trust is not transitive".
Transitivity is a mathematical property where if A has some relation
to B, and B has the same relation to C, then A has that relation to C.
For example, "greater than" is transitive with respect to numbers.
But trust in general cannot be considered to be transitive in this
sense, as Phil saw it.  Asking Alice to trust Bob to sign keys is one
thing.  But asking her to trust everyone that Bob trusts as a key
signer is something else.  That requires a lot more insight into the
mind of the other person, to judge not only whether he is careful
about his key signatures, but whether he is careful about judging how
careful other people are about key signatures.

The situation reminds me of a maxim of multi-level marketing (MLM)
companies like Amway.  These businesses typically sell a product, but
they use a pyramid scheme for distribution where people not only sell
the product, but try to recruit others to sell for them.  Each person
not only gets profit for the sales he makes, but he gets a share of
the profit for sales made by the people he recruited, and a further
smaller share of the profits from the people they recruit, and so on.
If he gets a large enough "downline" of people selling below him then
he can actually retire and just live off the profits they are
producing.  At least, that is part of the sales pitch for these
outfits.

To achieve success, though, the saying goes like this: You not only
have to sell; you not only have to teach your people to sell; but you
have to teach your people to teach people to sell.  Only once you have
developed this skill do you have a chance of having really big success
in MLM.  The idea is that being a good salesman is not enough.  You
have to recruit people and teach them to be good sellers, but that is
not enough either.  You also have to take your recruits and teach them
not only to be good sellers, but also teach them how to pass this
knowledge on down the line so that the whole downline thrives.

(It does seem strange that the saying stops where it does.  Don't you
also have to teach your people to teach people to teach people to
sell, etc.?  I think though the human mind starts to lose track of
what these increasingly abstract goals would mean.  Stopping where
they do conveys the idea that the teaching must be carried on
indefinately at each level.)

The analogy to transitivity of trust is this.  If you want to have
transitive trust, you have to be sure the other person knows how to
securely sign keys.  But you also have to make sure he knows how to
make sure that the next person knows how to securely sign keys.  And
further you have to make sure he knows how to make sure the next guy
knows how to make sure, and so on.

Note too that the hierarchical structure of the MLM is similar to that
used in traditional hierarchical key CA's.  So this points out one of
the big problems with these systems, which is the requirement to have
transitive trust.  Just trusting the root CA is not enough.  You have
to trust that it makes sure that all the CA's whose keys it signs will
be careful, as well.  And further it has to make sure that each
lower-level CA will pass on the need for care to all the CA's below
it.

At the time this concept was created, several years ago, users of the
net largely consisted of students and employees of national labs and
large corporations.  The hierarchical idea mapped pretty well into the
large bureaucracies which ran these places.  But today things are
different.  It's hard to see how a hierarchy would work for the
subscribers to AOL or MSN.

So instead one idea is to flatten the hierarchy.  Instead of a CA
giving out perhaps a few dozen key signatures, it might give out
hundreds of thousands.  Obviously this is a totally different concept
in terms of the checking possible and the security of the resulting
signatures.  At least there is less delegation and transfers of trust.
But the logistical problems can be very large.

PGP takes care to avoid transitive trust.  When you mark various key
signers as trusted, it is very careful to strip out that information
when you extract a key for sending to someone else.  Phil had another
reason for this beyond the general difficulties mentioned above.  The
basic problem is the social implication of trusting or not trusting
another person as a key signer.  Revealing that information could
cause difficulties.  People might be offended to learn that someone
else doesn't trust them.  Worse, people might feel pressure to trust
someone else if this were public knowledge.  Maybe the other person is
in a position of power where publically offering trust would be
valuable.  These kinds of social interactions could ruin the meaning
of the trust markings.  So PGP doesn't allow it at all.

However the problem is then that with PGP it is hard to find someone
you trust who can reliably sign the keys of people you want to
communicate with.  In a small group with many social interactions it
can work OK, but if you see a random posting by someone who sounds
interesting, the chances that you know someone who has signed his key
are very small.  So I don't think that the web of trust in practice
works very well, at least for a lot of the communication that people
do.

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.

Hal Finney

-----BEGIN PGP SIGNATURE-----
Version: 2.6

iQBVAwUBMY+NZxnMLJtOy9MBAQEE6gIAro4leHAsPn6OaqDreXY9/zhhOgQjLKTB
YzESC3lmIDEo1TnSGeibh2pM4N+VfO6ReqB5GQP0vxss2Rb3Ud2yug==
=KFDL
-----END PGP SIGNATURE-----

HF:

a very brilliant and thoughtful essay that sparks many ideas for
me. I am sure you will be flamed, or someone will want to,
for your analogy of hierarchical CA's to MLM, but imho you are right
on there!! a beautiful analogy to help the public see why hierchical
CA's are not very pretty.

what amazed me is that you didn't introduce the concept of a graph.
clearly, the web of trust and the hierarchical CA are actually just
different kinds of graphs. (for the uninitiated, a graph is a network
consisting of nodes and edges.) the hierarchical CA is a tree. PRZ's
"web of trust" is a graph that is not treelike. the point you make
about his trust being "non transitive" is actually saying (as I
understand it) that trust only propagates to adjacent edges 
in the trust graph, but not further.  that is,  say A trusts B,
and B trusts C. a "trust link" exists between A and B and B and C.
but a trust link does not exist between A and C. 

interestingly, beginning CS students learn to create a "transitive
closure" of a graph by drawing all the missing links. this is
effectively what is going on in a Hierarchical CA. a path of links implies
a link between all the nodes in that path.

your point that the "trust graph" is the most problematic area
of cryptography at this point is really right on the nail. we
all have to realize that Public Key Cryptography solved one
vexing problem, the requirement of the preexistence of a secret
channel. but it does not solve another problem-- ensuring that
keys are associated with the individuals one communicates with.

what I was thinking as I read your essay was that perhaps some
new metrics are called for. it seems to me that people are hitting
a brick wall in thinking, "trust is something that is either there
or it isn't". I think in the graph situation what we really have
is information about the "strength" of a trust link between nodes.

the problem then can be generalized: suppose I have a graph
of edges, and numerical weights that represent the trust between
entities represented by the nodes of the graph. the question is,
suppose A wishes to know the strength of his trust from himself
to some other entity C.

it should be clear that this is in fact a variation of the 
"shortest path" problem. it suggests a straightforward depth-
or breadth-first search. the code could tell you the "strongest
trust path" between you and some entity using some heuristic,
such that the trust between you and this person is the
average of the trust of all the traversed links, or something
like that. I am not saying this is the correct formula: it would
be interesting to try to find other formulas that are "correct"
in the sense that they truly model trust. (another obvious formula
would decrease the trust strength dramatically if any link in
the chain were weak.)

I would be interested to hear what people
think a correct "trust formula" should be. in fact what you
have delineated HF, are two extreme trust formulas at different
ends of the spectrum. (hope I get this right)

1. the HCA (hierarchical certification authority scheme). 
all trust links are 0 or 1. (0 is the same as no link). the
trust between entity A and entity B is 1 if a path exists
between them, 0 otherwise.

2. the PRZ scheme. all links are 0 or 1. a trust exists
between A and B if B is adjacent to A, 0 otherwise.

it seems to me that possibly neither is "correct", and that
perhaps a "correct" formula may not even exist. there are
clearly other variations. I'm being a bit sloppy, and I'd
be happy for anyone to hammer out these ideas with more
rigor.  what might be ideal is if every person could choose
to use whatever trust algorithm they desired. (that is,
a system that supported *both* HCA and PRZ is easily 
conceivable, with the consumer determining how he wishes
to use the "trust data", although PRZ complicates this
by insisting that some trust data must be secret)

and as I wrote, other possible algorithms, with 
some obvious defects:

3. trust is measured as 0 to 1, or perhaps -1 to 1. the 
trust between A and B is the highest average possible in
the path between A and B. ("optimistic")

4. or, trust is measured as the worst average possible. 
("pessimistic")

5. trust is the product of trust values.

etc.

what we have is a graph in which some links are explicitly
given, and we have to "derive" some of the implied links
based on our knowledge of "trust properties" and the given
trust values.

it is quite interesting that in fact the problem of "secrecy"
is replaced by that of "trust" by PKC, and that to adequately
solve the "trust" problem, we must try to figure out what its
actual properties are. how does human trust work? how should
it work? are there ways to formalize or optimize the
informal "algorithms" that people use to deal with trust issues?
we are getting into some deep psychological issues. can
trust be quantified?

also, there are some other obvious computational problems
that immediately ensue. how can we efficiently store all
this graph information? is there a way to distribute it
over a network? how can we efficiently respond to "trust
queries"? etc.

it seems to me that both PRZ's scheme and the HCA scheme
are only the very first, most basic ideas of how to tackle
these complex issues and that we are likely to see new
variations by others. it is quite possible that some cpunks
may help immensely in refining the field.

here is another idea: it appears what we have is a trust
graph in which some people may want to selectively reveal
or conceal their trust. this complicates things because
now the algorithms may or may not run on the "open trust"
values, or the "secret/hidden values", etc.  ugh!!! the trust
network itself is subject to the kind of secrecy and
hiding that is associated with the original problem it
tries to solve (i.e. conveying secret information).

hence it seems to me a good "trust network system" would support
some things:

1. allow efficient trust queries, without severe problems associated
with "nearness" of the participants. 

2. allow individual users to decide how they wish to use
the system, possibly supporting *both* HCA and PRZ etc.
(we all seem to be working from the assumption they are
mutually exclusive. but do they really have to be? is there
really a "best" algorithm, or is the best situation to
actually allow different algorithms for different situations?)

3. allow people to selectively reveal or conceal their 
trust values.

4. be distributed.

5. not rely on a central authority.

etc.-- additions, anyone?

it appears there is a rich vein of memes in all this beyond
the basic territory explored by PRZ and HCA for someone to mine.
in fact I'm surprised their aren't more academic papers out on
this subject that tackle some of the things I am referring to 
above (alternate trust algorithms, trust as a network, etc.)

maybe someone would like to work up some alternative prototypes
ala the way remailers were developed in this "community".