Re: An e-mail web of trust

On 2004-03-02 14:41:33 -0500, Alan DeKok wrote:
> Yakov Shafranovich <[email protected]> wrote:
> > However, the biggest problem in a web of trust system is scaling
>
>   Only if you have a centralized record of trust.  If you distribute
> the system, then the scaling is limited only by local limits on number
> of systems trusted.
>
>   e.g. Each domain maintains its own list of trusted systems.
>
>   When a sender wishes to send mail, they establish one or more paths
> of trust between sender and recipient.  The recipient can then check
> these paths very quickly.

There is still the problem of determining the path efficiently.
You have a few tens of millions nodes (if you are using domain names -
more if you are using individual mail addresses), each with dozens to
hundreds edges, and determining some path (prefererrably a rather short
path) in that graph should be possible in a few seconds to minutes to be
acceptable to users.

>   The only problem is that the web of trust now becomes more fragile.

Does it? I think by distributing the information it can be made more
robust on the whole.

> > The real question is would such system be really scalable? I don't know
> > if we can easily answer such question.
>
>   If the system is designed from the start to be a "scale-free" graph,
> then the maximum path between participants will be small.  The system
> will also be highly distributed, making it more robust.
>
>   e.g. AT&T has business relationships with many other companies.
> Those companies have business relationships with others, so the path
> between any two tiny businesses may be only 5 elements, and may often
> go through AT&T.
>
>   This solution does, however, require the designers of the system to
> understand and consciously choose a method of graph partitioning which
> has only been known for a few years, and which was coincidentally
> discovered by people analyzing the Internet.

Can provide a reference for the method? I'd like to look at it (I'm
afraid my knowledge of graph-theory is several years out of date, and
was never very thorough to begin with).

	hp

--
   _  | Peter J. Holzer    | I think we need two definitions:
|_|_) | Sysadmin WSR       | 1) The problem the *users* want us to solve
| |   | [email protected]         | 2) The problem our solution addresses.
__/   | http://www.hjp.at/ |    -- Phillip Hallam-Baker on spam

[demime 0.99d.1 removed an attachment of type application/pgp-signature]