[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[freehaven-cvs] initial commit of "reputation in anonymity systems" ...
Update of /home/freehaven/cvsroot/doc/econp2p03
In directory moria.mit.edu:/home/arma/work/freehaven/doc/econp2p03
Added Files:
econp2p03.bib econp2p03.tex llncs.cls
Log Message:
initial commit of 'reputation in anonymity systems' paper
missing abstract, intro, conclusion, most of the bib entries
still needs more shaping and cohesion
--- NEW FILE: econp2p03.bib ---
@InProceedings{mix-acc,
author = {Roger Dingledine and Michael J. Freedman and David
Hopwood and David Molnar},
title = {{A Reputation System to Increase MIX-net
Reliability}},
booktitle = {Information Hiding (IH 2001)},
pages = {126--141},
year = 2001,
editor = {Ira S. Moskowitz},
publisher = {Springer-Verlag, LNCS 2137},
note = {\url{http://www.freehaven.net/papers.html}},
}
@InProceedings{casc-rep,
author = {Roger Dingledine and Paul Syverson},
title = {{Reliable MIX Cascade Networks through Reputation}},
booktitle = {Financial Cryptography (FC '02)},
year = 2002,
editor = {Matt Blaze},
publisher = {Springer-Verlag, LNCS (forthcoming)},
}
@InProceedings{freehaven-berk,
author = {Roger Dingledine and Michael J. Freedman and David Molnar},
title = {The Free Haven Project: Distributed Anonymous Storage Service},
booktitle = {Workshop on Design Issues in Anonymity and Unobservability},
year = {2000},
month = {July},
note = {\url{http://freehaven.net/papers.html}},
}
--- NEW FILE: econp2p03.tex ---
\documentclass{llncs}
% \documentclass{llncs}
\usepackage{fullpage}
\usepackage{url}
\usepackage{graphics}
\usepackage{amsmath}
\newcommand{\workingnote}[1]{} % The version that hides the note.
%\newcommand{\workingnote}[1]{(**#1)} % The version that makes the note visible.
\renewcommand\url{\begingroup \def\UrlLeft{<}\def\UrlRight{>}\urlstyle{tt}\Url}
\newcommand\emailaddr{\begingroup \def\UrlLeft{<}\def\UrlRight{>}\urlstyle{tt}\Url}
% If an URL ends up with '%'s in it, that's because the line *in the .bib/.tex
% file* is too long, so break it there (it doesn't matter if the next line is
% indented with spaces). -DH
%\newif\ifpdf
%\ifx\pdfoutput\undefined
% \pdffalse
%\else
% \pdfoutput=1
% \pdftrue
%\fi
\begin{document}
\title{Reputation in P2P Anonymity Systems}
\author{Roger Dingledine and Nick Mathewson \\ The Free Haven Project \\
\{arma,nickm\}@freehaven.net \and Paul Syverson \\ Naval Research Lab \\
syverson@itd.nrl.navy.mil}
\maketitle
\pagestyle{plain}
\begin{abstract}
\end{abstract}
%\begin{center}
%\textbf{Keywords:} foo, bar, baz
%\end{center}
\section{Intro}
\section{An Economics of Anonymity}
Unlike confidentiality (encryption), anonymity cannot be created by the
sender or receiver. Alice cannot decide by herself to send anonymous
messages --- she must trust the infrastructure to provide protection, and
others must use the same infrastructure. Anonymity systems use messages
to hide messages: senders are consumers of anonymity and also providers
of the cover traffic that creates anonymity for others. Thus users are
always better off on crowded systems because of the noise they provide.
High traffic is necessary for strong anonymity, which means that the
incentives of several agents must find a common equilibrium. High traffic
also enables better performance: a system that processes only light
traffic must delay messages to achieve adequately large anonymity sets.
But systems that process the most traffic do not necessarily provide the
best hiding: if trust is not well distributed, a high volume system is
vulnerable to insiders and attackers who target the trust bottlenecks.
Anonymity systems face a surprisingly wide variety of direct
anonymity-breaking attacks \cite{back01,raymond00}. Additionally,
adversaries can also attack the efficiency or reliability of nodes, or
try to increase the cost of running nodes. All of these factors combine
to threaten the \emph{anonymity} of the system. As Back et al.\ point
out, ``in anonymity systems usability, efficiency, reliability and cost
become \emph{security} objectives because they affect the size of the
user base which in turn affects the degree of anonymity it is possible
to achieve.'' \cite{back01}
Early work on the economics of anonymity \cite{econymics} focused on
the incentives for participants to act as senders and nodes, providing
three results:
\begin{itemize}
\item Systems must attract cover traffic (many low-sensitivity users)
before they can attract the high-sensitivity users. Weak security
parameters (e.g. smaller batches) may produce \emph{stronger} anonymity
by bringing more users. But to attract this cover traffic, they may well
have to address the fact that most users do not want (or do not realize
they want) anonymity protection.
\item High-sensitivity agents have incentive to run nodes, so they can
be certain their first hop is honest. There can be an optimal level of
free-riding: in some conditions these agents will opt to accept the cost
of offering service to others in order to gain cover traffic.
\item While there are economic reasons for distributed trust,
the deployment of a completely decentralized system might involve
coordination costs which make it unfeasible. A central coordination
authority to redistribute payments may be more practical.
\end{itemize}
lead in to why we focus on reputation here
\section{An Example: Remailer Networks}
Remailer networks allow people to send and receive mail while protecting
their identities. Today's remailer networks use a handful of long-lived,
static servers with fairly uniform reliability. Currently deployed
reputation systems \cite{echelot} send periodic test messages through
each remailer to determine which are currently working. This ``pinging''
approach works well enough for a small static list of servers. However,
a network that is made of a small static set of remailers is potentially
vulnerable to a well-funded adversary in a variety of ways, e.g.,
denial of service or remailer compromise. %Any solution based only on
%hardening the nodes runs contrary to the basic premise of remailers
%that trust is distributed rather than mutually assured.
Thus, to better
resist a well-funded adversary, the remailer network must grow so it has
enough nodes to properly distribute trust. Pinging for reputation breaks
down in an environment where the network is made up of many transient
volunteer nodes. On the other hand, an adversary might render a growing,
dynamic network useless by volunteering a flood of unreliable remailers,
or it might manipulate the reputation system to improve the standing of
remailers it owns.
The reputation system presented in \cite{mix-acc} aims to improve
remailer reliability. Remailer reputation is based on both positive and
negative performance. If it were based only on successes, an adversary
could pump up his reputation by sending his own messages through the
node while ignoring other messages. On the other hand, recording only
failures is also insufficient, because new unreliable remailers would be
rated the same or better than remailers that consistently perform well
\cite{cheap-pseudonyms}. In this design, each remailer in the message's
path passes back a receipt to the one behind it. Senders can successively
query for receipts to determine which remailer to blame for delivery
failure. However, a remailer might refuse to provide a receipt for a
particular message either because it didn't try to send the message, or
because it tried but was unable to obtain a receipt from the next hop. We
solve the problem of pinpointing failures by introducing a set of weakly
trusted global witnesses. These witnesses are contacted when the next
hop in the path refuses the message, allowing a remailer to prove that it
made a best-effort delivery attempt. Senders can also tell witnesses about
remailers that silently dropped messages (meaning they got a copy but did
not attempt to pass it on). These witnesses verify and tally failures, and
also send their own test messages to distinguish reliable remailers from
new ones that have not yet been tested. Reputations are %tabulated and
made available to client software, which can use them to choose reliable
remailers for sending anonymous mail.
This reputation system attempts to improve reliability in a long-term
sense, rather than giving provable delivery guarantees for each
message.
[cite all those provable mix papers]
On the other hand, it still relies both on proofs of correct
behavior to establish reputations, and trusted witnesses to determine
and keep track of them. The reputation system in \cite{casc-rep} does
away with trusted witnesses and proofs in favor of self-rating groups
of remailers. Remailers are arranged in cascades (fixed paths through the
network, so batches of messages go through in synchrony).
New cascades are formed at a regular interval (say, daily),
and the formation of cascades is based on a communally generated
random value so that no set of collaborating remailers can predict which
remailer will be in which cascade, as long as at least one remailer is
honest. Remailers send test messages through their own cascades and
can also receive evidence of failure from client senders. Rather than
depending on proofs of remailer performance, a cascade fails when and
only when some member of that cascade has declared it to have failed. All
members of cascades that do not fail during an interval increase in
reputation; all members of cascades that fail decrease. To make it
harder for the head remailer of a cascade to undetectably fail or fail
selectively, each of the cascade members is responsible for a portion of
the messages that go through a cascade in each batch. In effect, each
member is the head for some of the messages. Similarly, the tail of
the cascade sends each message in a batch to each of the other cascade
members rather than just directly to the recipient. All then attempt to
deliver the message to the recipient. (Efficiency of communication for
final delivery can be improved by using receipts when that is feasible.)
In both of these remailer reputation systems, it was necessary to redesign the
remailer protocol so we could track remailer behavior. In the first
case, we added receipts for each delivery to each remailer and to
the ultimate destination, and we added trusted witnesses to verify
delivery and record success or failure. In the second case, we used
the usual remailer cascade protocol for messages inside the cascade,
but we introduced a new protocol for sending messages into the cascade
and delivering messages from the cascade.
[needs more analysis here]
\section{An Example: Anonymous Publishing}
Free Haven \cite{freehaven-berk} describes a design for a publishing
system that can resist the attempts of powerful adversaries to find or
destroy any stored data. It provides anonymity for readers and publishers,
and also hides the locations of the servers that store and serve the
documents. Unlike related designs such as Freenet \cite{freenet},
the publisher of a document --- not the servers holding the document
--- determines its lifetime. To counter malicious or flaky servers,
publishers break documents up into shares, any adequately sized subset of
which is sufficient to reconstruct the document. Servers then trade these
shares around, allowing for servers to join and leave smoothly and also
providing a moving target for an adversary hunting a particular share.
To prevent selfish or malicious users from filling up the available disk
space, all who would publish must also provide servers, and servers form
contracts to store each other's material for a certain period of time.
Because servers can cheat and drop data early, Free Haven employs a
reputation system to limit the damage done by servers that misbehave.
Successfully fulfilling a contract increases a server's reputation and
thus its ability to store some of its own data on other servers. This
gives an incentive for each server to behave well --- that is, as long
as cheating servers can be identified.
In such a dynamic and anonymous environment, it is very difficult to
reliably notice if a server drops data early. We might give the original
publisher the task of monitoring the availability of his documents; he can
then broadcast a claim that a particular document has been dropped early.
If we don't want to rely on the original publisher, we can assign a
random server as a ``shepherd'' for a document. Or for a more dynamic
solution, we can use a ``buddy system'', where publishers put in two
copies of each share, and the copies watch each other and broadcast a
complaint if either disappears.
Anyone wishing to claim misbehavior can present a signed contract as
an indication the file should have been kept, but there are a number
of special cases where a signed contract is not sufficient proof to
pinpoint a particular server as the culprit, such as if the server traded
the share away before the contract expired. Because a claim cannot be
taken as absolute proof, servers are left with the grim task of trying
to determine the credibility of the claimer: if two or more servers
disagree, onlookers need a way to determine which to believe. Keeping
track of all claims ever made and tracking their results might give a
server enough information to make reasonable guesses about the validity
of each claim. This approach gets complex very quickly, and leaves lots
of holes for a smart adversary.
Providing a way to verify claims in Free Haven remains an open problem.
Given our experience designing the remailer reputation systems above,
it seems most promising to redesign the entire system from the ground up,
this time with verifiable claims in mind. Designing the original system
without a clear idea of the reputation requirements made Free Haven's
design complex and brittle.
It's tempting to scale down the reputation system instead. That is,
servers use only local information from their own transactions and
trades. In this scenario, a new server must separately convince each
server it encounters that it is reputable before that server will
allow it to publish any data. Because news about good and bad behavior
does not propagate, servers must be more conservative about offering
resources to unfamiliar nodes. To prevent stabilization into a static
network with a small number of nodes trading data among each other and
ignoring newcomers, many servers must explicitly risk resources on new
nodes. Rather than the global gossip system where the whole world learns
from a server's first interaction, now each new server has a chance to
waste the time and resources of every other server (the ``screw everyone
once'' attack).
Perhaps the most interesting point of Free Haven reputations is that
servers use their reputation capital to obtain proportional resources
from other servers. In order to build up to a reputation that allows
a server to store a certain amount in the system (think of it like a
credit limit), the server must previously have successfully stored that
same size of other documents. Each server is able to commit at most his
current credit limit in new contracts, and successfully completing a
contract raises his credit limit. Because a server can cheat on at most
the amount of useful work he has already done, each server is forced to
perform at least 50\% useful work. We will say more about this notion of
``spending'' reputation and quantifying risk below.
\section{Reputation and Anonymity}
Although the examples described above associate non-transferable
reputation with long-lived pseudonyms, there are many ways to vary this
formula. Entities may be anonymous or have only short-lived names;
reputations may be short-lived or transferable; and bindings between
pseudonyms, entities, and reputations may be varied.
nym, pseudonym
We have already noted that in Free Haven, a server can both acquire and
spend reputation. A central register or registers can keep track of each
server's current reputation credit level, or each server can maintain its
own view of the system. It is a small step from here to consider systems
in which reputation can be paid in the form of coins or tokens. With such
a system, the same entity can maintain reputation even while changing
pseudonyms. An entity that holds different pseudonyms in different
contexts can benefit from this feature -- either to preserve reputation
independent of private key compromise, or to maintain perfect forward
anonymity (future compromises linking a nym to an entity will not reveal
previous transactions by the entity bearing that nym, even if all past
behavior under all nyms is logged \cite{unlinkable-serial-transactions}).
Along with the advantages of fungible reputation come some potential
problems. For example, an entity can obtain reputation in one context
where it has functioned well and spend it in another context where
it has not. Or the entity can transfer reputation to another entity
entirely. This capability might be controlled by using cryptographic
techniques that, e.g., bind all the reputation to the same nym or the
same entity without revealing which nym (or entity) that is. But there
are other concerns for this approach. For example, how do you diminish
reputations for bad performance in such a model? (If it is possible
to bind reputation tokens to an entity in an anonymity preserving way,
it may also be possible to bind them to a duration so that the amount of
reputation can be evaluated with respect to the time that the reputation
bearer has existed. Thus we can distinguish longstanding, low-performing
entities from untested ones.)
On the other hand, in some contexts transferable reputation may not be a
problem. For example, in a system like Free Haven that ``pays'' you for
good performance with system services from others, as long as the amount
of service credit taken from the system is no more than the amount of
service provided to it, does it matter if that credit is transferred
to others?
\section{Conclusion: New Directions, Misdirections, and Other Questions}
\bibliographystyle{plain}
\bibliography{econp2p03}
\end{document}
--- NEW FILE: llncs.cls ---
% LLNCS DOCUMENT CLASS -- version 2.8
% for LaTeX2e
%
\NeedsTeXFormat{LaTeX2e}[1995/12/01]
\ProvidesClass{llncs}[2000/05/16 v2.8
^^JLaTeX document class for Lecture Notes in Computer Science]
% Options
\let\if@envcntreset\iffalse
\DeclareOption{envcountreset}{\let\if@envcntreset\iftrue}
\DeclareOption{citeauthoryear}{\let\citeauthoryear=Y}
\DeclareOption{oribibl}{\let\oribibl=Y}
\let\if@custvec\iftrue
\DeclareOption{orivec}{\let\if@custvec\iffalse}
\let\if@envcntsame\iffalse
\DeclareOption{envcountsame}{\let\if@envcntsame\iftrue}
\let\if@envcntsect\iffalse
\DeclareOption{envcountsect}{\let\if@envcntsect\iftrue}
\let\if@runhead\iffalse
\DeclareOption{runningheads}{\let\if@runhead\iftrue}
[...976 lines suppressed...]
\def\sectionmark##1{}%
\def\subsectionmark##1{}}
\def\ps@titlepage{\let\@mkboth\@gobbletwo
\let\@oddfoot\@empty\let\@evenfoot\@empty
\def\@evenhead{\normalfont\small\rlap{\thepage}\hspace{\headlineindent}%
\hfil}
\def\@oddhead{\normalfont\small\hfil\hspace{\headlineindent}%
\llap{\thepage}}
\def\chaptermark##1{}%
\def\sectionmark##1{}%
\def\subsectionmark##1{}}
\if@runhead\ps@headings\else
\ps@empty\fi
\setlength\arraycolsep{1.4\p@}
\setlength\tabcolsep{1.4\p@}
\endinput
***********************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe freehaven-cvs in the body. http://freehaven.net/