\chapter{Introduction}
\label{intro}

In today's world of open, decentralized networks, the question of
\emph{trust} is becoming increasingly relevant. Most existing Internet
protocols implement a naive policy of providing a relatively limited
set of services, but trusting all users with them. Given that a
significant fraction of Internet users are not trustworthy, the
inevitable result is spam, denial of service attacks, cracking, and a
host of other ills far too familiar to legitimate Internet users.

A number of approaches have been developed and deployed over the
years, with varying degrees of success. The most basic is the model of
password-protected accounts. This mechanism is almost universally
deployed, but suffers from serious limitations, including the need for
servers to manage the accounts, the need for users to keep track of a
large number of passwords, and the relative lack of security provided
by this model. Thus, there has been a sustained interest in more
sophisticated models.

One such approach is the \emph{Public Key Infrastructure}, or PKI
\cite{Bra97}. Briefly, a PKI consists of various \emph{Certification
Authorities} (or CA's) that issue \emph{certificates} asserting a
binding between a name and a public key. PKI's suffer from two
fundamental problems: the lack of useful meaning in the PKI's
underlying namespace, and the question of which CA to trust. Actual
implementations of CA's have proved themselves not worthy of absolute
trust. Further, as the number of CA's deployed scales up, the risk of
any one of them being compromised scales accordingly. In part because
of these two problems, PKI's have met with limited success at best.

Spurred on by these limitations, much recent attention has been
focussed on the explicit encoding and evaluation of trust
relationships. A pioneering work in this area is the PolicyMaker
framework of Matt Blaze\cite{BFL96}. A particularly interesting branch
of this work is the concept of \emph{trust metrics,} which are the
primary focus of this thesis.

Trust metrics are based on the principle of \emph{local} encoding of
trust relationships, but granting trust on a global scale. These
assumptions closely parallel the philosophy of peer to peer
networks\cite{P2P}.

While the literature is rich with design proposals for trust metrics,
there has been relatively little analysis of how well they work in
practice. In Chapter~\ref{tmetrics}, we show that, under assumptions
similar to the Internet, the entire category of ``scalar'' trust
metrics fails to resist easily-mounted attacks. Attacks against these
poor trust metrics dot the literature\cite{RS97b}, and have been used
to argue (incorrectly) that a centralized identity service is
needed\cite{douceur-sybil}.

While the outlook for scalar trust metrics is indeed bleak, we propose
a new class, which we call \emph{group} trust metrics, so called both
because the trust metric is very well suited to evaluating membership
in a group, and because this evaluation is done over the entire group
of nodes, rather than individually for each node. While the group
trust metric cannot prevent individual hostile nodes from being
accepted as group members, it can place strict bounds on the
\emph{number} of hostile nodes so accepted.

I built a community website for free software developers, called
Advogato, that uses this group trust metric to determine who belongs
to the community. Acceptance by the trust metric confers privileges to
post articles and comments, and to edit project information. At the
time of this writing, the site has been in operation for about 18
months, and has built a trust graph of over 1000 active nodes.
Advogato is notable for the extremely low level of trolls, spam, and
other forms of abuse common to bulletin board type systems, thus
providing strong anecdotal evidence that the trust metric is
effective. Advogato is described in more detail in
Chapter~\ref{advogato}.

One interesting application of trust metrics is secure registration
and lookup of public keys bound to names, essentially the same problem
addressed by Public Key Infrastructures (PKI). The attack resistant
properties of the trust metric avoid the single point of vulnerability
common to most PKI designs. We present a detailed design for such an
attack-resistant name service in Chapter~\ref{nameservice}. The desire
to build a ``better PKI'' was the original motivation behind the work
of this thesis.

Because the group trust metric is effective in resisting attack, it
has many other interesting applications. One such is an
attack-resistant system for distributing metadata, for example
opinions about songs. Attack resistance can be useful for ensuring
high quality of the metadata, but becomes particularly important when
there are financial implications to the metadata system, for example
to identify recipients of voluntary donations to artists who post
their music to the Net. We propose a design for an attack resistant
metadata system in Chapter~\ref{metadata}. This design combines ideas
from both the Advogato group trust metric and the PageRank algorithm
used in Google.

Another intriguing application for group trust metrics is to provide a
spam resistant infrastructure for e-mail. Spam is a huge problem,
causing lots of wasted time for many, and most e-mail users feel
hopeless in the face of it. We present a partial design for a
communications infrastructure resistant to spam, yet highly permeable
to legitimate email. This design uses a capacity constrained flow
network where ``stamps'' are the commodity of flow. Rather than
explicitly computing a flow in the network, the flow results from
local activity. When capacity is exhausted, e-mail is no longer
deliverable. This design has many appealing properties, but several
aspects remain as open problems, particularly scaling.
Chapter~\ref{stamptrading} presents this design and discusses some
open issues.