From: Hal <hfinney@shell.portal.com>
Date: Wed, 8 May 1996 10:36:18 +0800
To: cypherpunks@toad.com
Subject: Transitive trust and MLM
Message-ID: <199605071750.KAA03884@jobe.shell.portal.com>
MIME-Version: 1.0
Content-Type: text/plain


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