\documentclass[runningheads]{llncs}
\usepackage{epsfig}
\usepackage{latexsym}
\usepackage{psfrag}
\usepackage{amsfonts}

%%\newenvironment{algorithm}
%%{%
%%\begin{figure}[hptb]
%%%\renewcommand{\baselinestretch}{1}
%%\small
%%}
%%{\end{figure}
%%\renewcommand{\baselinestretch}{2}
%%}
% replace bullets by dashes in itemize
\renewcommand\labelitemi{\normalfont\bfseries --}
\renewcommand\labelitemii{$\m@th\bullet$}

\newenvironment{revpar}{%
\begin{list}%
{}{\setlength{\labelwidth}{0in}%
\setlength{\itemsep}{0in}%
\setlength{\topsep}{0in}%
\setlength{\leftmargin}{4em}%
\setlength{\itemindent}{-2em}}}{\end{list}}

\newenvironment{algorithm}{%
\medbreak%
\begin{list}%
{}{\setlength{\labelwidth}{0in}%
\setlength{\listparindent}{0in}%
\setlength{\rightmargin}{0in}} \small \item}{\end{list}}


\title{Echolot and Leuchtfeuer: Measuring the Reliability of Unreliable Mixes}

% Blinded for submission

%\author {Klaus Kursawe\inst{1} and Peter Palfrader\inst{2} and Len Sassaman\inst{1}


%foo
%\institute{Katholieke Universiteit Leuven\\
%Kasteelpark Arenberg 10, B-3001 Leuven-Heverlee, Belgium\\
%\email{\{len.sassaman,klaus.kursawe\}@esat.kuleuven.be}
%\and
%Paris Lodron Universit\"at Salzburg\\
%Salzburg, Austria\\
%\email{ppalfrad@cosy.sbg.ac.at}
%}
%foo


\date{}

\begin{document}

\maketitle

\begin{abstract}

In a mix-net, information regarding the network health and operational
behavior of the individual nodes must be made available to the client
applications so they may select reliable nodes to use in each message's
path through the mix-net.

We evaluate the security concerns regarding an information service,
including the issues regarding anonymity set preservation, information
disclosure, and node cheating.

We present our software \emph{Echolot}, the most comprehensive and widely
adopted solution for mix-net reliability monitoring.

We present \emph{Leuchtfeuer}, a protocol enhancement for mix-nets which
eliminates the active and passive intersection attacks that are possible
when different users obtain conflicting reliability statistics about the
mix-net.

\end{abstract}


\section{Introduction}

Chaum\cite{chaum81} introduced the concept of mixes as a method of
providing secure anonymous network communication. The publicly accessible
mix networks, such as the ``Type I'' Cypherpunk remailers, the ``Type II''
Mixmaster network, and the ``Type III'' Mixminion network\cite{mixminion}, as well
as the low-latency network anonymity service Tor\cite{tor}, are operated on a
volunteer basis and are prone to intermittent failure of individual nodes.
It is therefore necessary for mix client software to have an accurate view
of the health of the nodes in the mix network. This information is
gathered by sending test messages through each node and observing the
success or failure of the mix to successfully transmit the message. In a
similar fashion, links between mixes are examined by sending messages
through every combination of two consecutive mixes. Since the overhead and
operational complexity involved in monitoring an entire network of mixes
is too great for the average user, reliability testing servers, or
\emph{pingers}, perform this function and publish their results in a
machine-parsable format. The results are downloaded and interpreted by
the mix clients. Pingers track additional information as well, such as the
average latency provided by each mix, changes in the key information and
capabilities of the mixes, and so forth.

In this paper we give an overview of the different pinger systems that
have been developed for the Mixmaster network, and describe the problems
they attempt to address, as well as their relative success at doing so. We
present Echolot, our pinger implementation which more adequately addresses
the problem of reliability monitoring than the other pingers. Finally, we
explain the problem of pinger inconsistency, an issue which poses
significant security implications and is shared by all existing pingers
and mix clients. To solve this, we present the pinger agreement protocol
Leuchtfeuer.

\section{Related work}
\label{pingers}

\subsection{rlist}

Raph Levien first introduced the concept of monitoring service for anonymous
remailers.  His software ``rlist'' was at first designed to work with the
Cypherpunk remailer network, support for the Mixmaster network was added later.

Once started, rlist would run indefinitely, regularly sending simple test
messages through remailers and building statistic files.

% I haven't the slightest clue how rlist comes up with its reliability number.
% it's certainly black magic.  -- weasel

\subsection{pingstats}

% - cmeclax, Dec 2000 - 2003
% - written in C and shell
% - run out of cron, uses procmail to filter mails into folders
% - pings weight decreases exponentioally with age
% - pings come back in plain text but contain a random token
%   so a remailer can't just make up pings if me missed a fewcontain a random token
%   so a remailer can't just make up pings if me missed a few

Pingstats\cite{pingstats}, developed by cmeclax between 2000 and 2003 is a
pinger for Cypherpunk as well as Mixmaster remailers.  It is made up of a C
program that actually compiles the statistics and a collection of shell scripts
that manage the creation, sending, and receiving aspect of pinging, as well
as help with collecting keys of known remailers and making a list of their
capabilities. These programs are called from Cron, a Unix daemon that
executes programs at previously specified times.

Pingstats introduced random tokens in message payloads to prevent cheating by
mixes (see section \ref{section:gaming} below).
It also uses weighted pings for its reliability calculation, giving older
pings less weight than more recent data.  


\subsection{remlist}

% - Christian Mock, 2001
% - uses a RDBMS as storage backend
% - run out of Cron
% - pings come back in plain text but contain a random token
%   so a remailer can't just make up pings if me missed a fewcontain a random token
%   so a remailer can't just make up pings if me missed a few

Christian Mock wrote remlist\cite{remlist} at about the same time as cmeclax
developed pingstats.  Mock's pinger also generated non-deterministic ping
payloads but did not do any weighting of data.  Remlist's main feature
was the use of a database like MySQL as its storage backend.

% XXX: Maybe Reliable deserves being mentioned

\subsection{Mixminion directory server}

Mixminion\cite{mixminion} generalized the concept of pingers, defining a
directory server component of the Mixminion system, responsible for the
distribution of all information about remailer availability, performance,
and key material. The designers of the Mixminion system considered the
attacks on the independent pinger model, and specified that directory
servers be synchronized as well as redundant.

%FIXME [Does Mixminion have any details on calculation stategy? Not sure,
%but I should check the source.]
%
% Apparently, Mixminion doesn't do any actual pinging. Scratch that.
%

Mixminion publishes signed \emph{capability blocks} in the directory
server, consisting of the supported mix protocol versions, mix's address,
long-term (signing) public key, short-term (message decryption) public
key, remixing capability, and batching strategy.


\section{Veracity attacks}
\label{section:gaming}

A mix which is otherwise honest (in that it correctly performs mixing
duties without breaking the anonymity of the messages transmitted through
it) may attempt to convince a pinger to provide false information
regarding the performance of the mix, by identifying the source address of
pings, and treating the pinger messages differently than normal messages.
While this manipulation will not change basical results such as the
operational status of a defunct mix, it could allow a mix to alter the
latency statistics reported for its operation.

We experimented in Echolot 1.x with a technique intended to discourage such
cheating by creating ping messages which originate and terminate at a local mix
that also mixes normal messages, so that the target mix cannot distinguish
between user messages and pinger messages. Unfortunately, systems such as
Mixmaster have a minimum distance between hops which is considered when
creating a mix chain, and thus messages which consist of the mix chain
A,B,A will still be distinguishable as pinger messages, since no properly
functioning mix client would generate this chain. If a pinger were to
create a chain of A,B,C,A, neither mixes B or C would be able to tell that
the message contained pinger information, but the results would only
indicate the combined latency of the mixes B and C, as well as the health
of both B and C and the link between those mixes. It would not provide any
useful information about B or C alone.

The pinger message data (or \emph{pings}) itself should not be
deterministic, lest a mix attempt to "back-fill" the results for pings
sent during a period when the mix was offline.


%%%% ECHOLOT SECTION


\section{Echolot}

The first version Echolot \cite{echolot} was written in 2001.  Its
distinguishing property was that it sent pings through a local Mixmaster node
in order to prevent the nodes being tested from learning that a message
was a ping.  Other than that it was fairly similar to other pinger software
in existence at the time.

It was followed by a complete rewrite in 2002, Echolot 2.x, that ran as a
single daemon instead of a handful of programs that all needed to be called in
the correct order.  In addition to the normal single hop pings, this version
also featured automated node discovery.  The following year with Echolot 2.1
chain pinging was added.

Echolot is the most widely used pinger for the Types 1 and 2 remailer networks.
As of this writing, there are over a dozen Echolot pingers operating
publicly\cite{allpingers}.

\subsection{Reliability measurement aspects}

Echolot tests multiple areas of failure in the remailer networks and
collates this data in a format the Mixmaster software can process,
allowing the mix clients to make as much use of the available network
resources as possible, without preventable packet loss.

The most basic test of reliability is the ``single ping'' test, wherein
the known nodes of the mix-net are each periodically sent individual
messages encrypted using the network-specific packet format, and the
response times and success rates are tallied. These results allow the mix
client to make general assumptions about the overall behavior of the node
being tested.

When performing a ``chain ping'' test, Echolot creates a message of path
length equal to two, for all combinations of any two remailers in the
network, and tests each of these pairings. If both remailers consistently
return single pings, but fail to return chained pings, one can deduce that
the failure is occurring at the link between the two nodes. Thus, either
remailer can be reliably used, as long as they are not selected to be
adjacent nodes in the message path.
%Likewise, the latency value calculated
%from the transmission of a chain ping until its return at the pinger
%measures the combined latency of the two nodes. If this is significantly
%different than the sum of the single-ping latencies for each node, the
%mix-net client can make determinations about the suitability of that
%pairing of nodes in a chain.
% XXX: nothing reports or cares about latencies of chain pings -- weasel

\subsection{Node discovery}

Distributed mix-nets consisting of independent operators often do not
allow for a guaranteed means for nodes to communicate join and exit events
to the other nodes in the network. In the case of Mixmaster, there is no
central control structure for tracking the existence of functional nodes,
and the components in the system must devise a way of obtaining this
information. Often, the human operator of a node joining or exiting the
network will announce the status change to other node operators and users
via the ``remops'' mailing list or by posting to USENET. Just as often,
nodes will come into existence or cease operation without any warning or
notification at all.

% unfinished -- Len's working on this, leave notes, but leave until last to write it up.
%
%
% Remailers publish nodes they know about in their remailer-* data.
% Echolot collects that data, and once a sufficient number of nodes list
% a new remailer an Echolot pinger starts to ping it too.
%
% Therefore only a few remops have to manually add a new node and it spreads
% to everyone from there.  Similarly, remailers that have not been answering any
% requests for about a week get delisted automatically.  This allows echolot
% to be zero to low maintenance, an important feature for widespread adaption.
%
%  - weasel
% let's add some text for this:
Echolot regularly sends requests to remailers to learn their current keys,
their capabilities, and a list of remailers that a certain node knows about.
If a threshold of remailers know about a new server, previously unknown to this
Echolot pinger, it will automatically add the new address to the list of
remailers, request information about keys and capabilities and start pinging
the address.

Remailers that have not responded to any requests for a long time are also removed
automatically.  This automation allows most Echolot pingers to run with zero
or close to zero maintenance work, an important incentive for prospective operators
of pingers.


\subsection{Echolot algorithm}

Echolot's approach for determining remailer reliability is simple.
Distributed over the course of a day Echolot sends several pings through
each remailer, keeping track of the time when they were sent.  For pings
already received the time it took for it to return is recorded as well.

The ``reliability'' of a remailer is basically the quotient of pings
received and pings sent, with some skewing in place to put more emphasis
on more recent data while still being fair to remailers with higher
latencies: $rel := \frac{w_i \cdot rcvd_i }{w_i}$, where $rcvd_i$ is $1$
if a ping was received and $0$ otherwise.

The weight $w_i$ of a ping is made up of two factors: $w1_i \cdot w2_i$.
The first of them, $w1_i$ is strictly a function of the ping's age:
Pings younger than 24 hours have a weight of $0.5$, for older pings
$w1$ is $1.0$ for a while until the weight decreases to zero for pings
older than 12 days.  See table \ref{table:pingweight1} for the exact
numbers used in the Echolot software.

\begin{table}[h]
\centering
\begin{tabular}{r||c|c|c|c|c|c|c|c|c|c|c|c}
 age [days]:  ~ &   1 &   2 &   3 &   4 &   5 &   6 &   7 &   8 &   9 &  10 & 11  & 12\\
 \hline
 weight $w1$: ~ & 0.5 & 1.0 & 1.0 & 1.0 & 1.0 & 0.9 & 0.8 & 0.5 & 0.3 & 0.2 & 0.2 & 0.1\\
\end{tabular}
\caption{Weight of pings based on their age}
\label{table:pingweight1}
\end{table}


The second part of a ping's weight also considers this node's latency
behavior over the last 12 days.  If a ping already has returned its
$w2$ is $1.0$.  However, should it still be outstanding Echolot computes
the ping's age, with some constant skewing factors again:
$ age_{skewed} := (now - send - 15 min) \cdot 0.8$.  The weight $w2$ is
now the percentage of pings returned with a latency lower than
$age_{skewed}$ within the past 12 days.

To illustrate this assume a ping was sent two hours ago, which
makes $age_{skewed}$ be 84 minutes.  If all pings returned from
this node were faster than 84 minutes then $w2$ is $1.0$.  If only
a third of pings were received within that time frame then $w2$ is
$0.33$.  If no ping was ever faster than 84 minutes, then $w2$ is
zero.

This weighting based on past behavior was introduced to accurately
report reliability of remailers that have vastly different latencies.
There exist Mixmaster nodes which return pings within minutes of sending
while others often take days to forward a message.

In addition to reliability Echolot also reports a node's latency.  The
latency is simply the median of latencies of all pings received within
the last 12 days.


\paragraph{Chain-Pinging:}  In addition to single-hop pings Echolot also
does chain pinging to uncover cases where two remailers A and B perform
well in most cases but for obscure reasons messages sent through A to B
never arrive.

Since pinging every two-hop chain often would put an unnecessary load on
the network Echolot contents itself with only testing each chain once a
week.  Chains that warrant closer attention (so called ``interesting
chains'') are pinged more often---daily.

Echolot reports a chain to be broken if
\begin{itemize}
\item at least 3 pings were sent to test the chain, and
\item the resulting chain reliability is far smaller than could be
	expected from the nodes' individual performance:
	$\frac{\mbox{received pings}}{\mbox{sent pings}} <= rel_A \cdot rel_B \cdot 0.3$.
\end{itemize}

Chains are considered interesting by Echolot when
\begin{itemize}
\item less than 3 pings have been sent without any returning, or
\item the chain is currently reported broken.
\end{itemize}

Because Echolot pings chains which it considers working only once a
week it may take a while before it realizes that a previously working
chain is now broken.  Fortunately experience with the currently deployed
Mixmaster network shows that broken chains do not change very often.

%%%% END ECHOLOT



%EXPAND AND CLEAN UP THE ABOVE

\section{Anonymity set attacks based on pinger data}

A mix network in which users obtain their view of the network's heath and
status from multiple independent sources opens the system to partitioning
% FIXME
attacks\cite{} against the users, based on differences in the mix
selection based on the results of the different pingers. In a system of
entirely honest pingers, this attack is feasible for an adversary
operating in the passive observer model. 

Suppose Alice retrieved her network health information from pinger 1, and
Bob retrieved his information from pinger 2. An observer watching the
network local to Alice or Bob would know which pinger the user under
observation chose. If the information provided by both pingers different in
some manner, the delta would contain mixes that, if chosen by Alice or
Bob, would betray which pinger had been used to obtain this information. A
message processed by a mix contained only in the results provided by
pinger 1 could not have been sent by Bob, who obtains his results from a
pinger lacking that information.

Additionally, differences in pinger results for mix latency could lead to
more subtle variations in mix path selection, which may aid an attacker.

If a pinger is operated by an attacker, it becomes possible to
specifically target individual users by providing them with unique
information about the network, in order to partition them into an
anonymity set of size 1. Users can attempt to prevent against this attack
by obtaining their pinger results from a widely-published location, such
as Usenet, though this does not completely solve the partitioning attack
problem, and introduces additional reliability constraints on the quality
of the pinger information.

% More attacks?  FIXME
% - most users also fetch keys with the stats
%   -> an attacker could not just give Alice a different list of nodes, but
%      could give her the same list only with a different key for his
%      remailers, so he can easily distinguish her messages when he seems them
%      at his node

\section{Leuchtfeuer: a unified directory view}

The solution to the partitioning attacks mentioned in the previous section
involves providing all clients with the same view of the network. Each
pinger should calculate its results for the status of the network, and
compare these results with those of the other pingers. The pingers then
must agree on a compromise result which reflects an accurate view of mix
availability, and provides every client with a consistent information with
which to calculate message paths.


Since the infamous FLP impossibility proof\cite{filypa85}, it is known
that a simple problem such as reaching consensus in the presence of faulty
parties -- even if the worst they can do is to crash -- is rather hard,
and a significant amount of research has been put into securing a
distributed systems against faulty parties\cite{schnei90,deblfa91}.  In the
Mixes scenario, the main parties for the agreement protocols are the {\em
pingers}, i.e., the parties that maintain a database on the active mixes,
their authentication keys and some of their properties.  They need to
agree on a consistent status of the {\em mixes} and then deliver it on
request to the {\em clients}. As the clients should not be forced to
contact more pingers than needed, each honest mix should be able to prove
that the result it forwards to the client is in fact the genuine outcome
of the agreement.

Depending on the attack model, the solutions can be rather complex, and in
many implementations weaker attack models are chosen to allow for simpler
protocols . In the Mixminion protocol, for example, the agreement protocol
can easily be circumvented by one (or several) parties stopping the
communication after a while -- a condition that may be constructed even if
none of the involved pingers is actually corrupt. The honest parties may
recognize they are in a bad condition and alert the administrator, but it is
left to human interference to actually recreate consensus; as the
disagreement may be created without any party behaving obviously
dishonest, this may place quite some burden on the administration.

The protocol suite presented here will guarantee consensus independent of
timing assumptions, as long as less than a third of all pingers behave
actively malicious. For additional security, one can still add tests along
the lines of the Mixminion protocol to detect inconsistencies and alert
the administrators; however, if more than a third of the pingers are
actively corrupt, the system is in a sufficiently bad state that its
survival is questionable.
 
\subsection{The Tools}

In this section, we introduce the basic building blocks needed for our
protocol. Due to lack of space, we do not give a formal model here. The
protocols we choose where mostly developed within the MAFTIA
project\cite{MAFTIA}; using new randomization techniques, these protocols
are the first practical protocols that can deal with the maximum possible
number of corruptions, and do not require any timing assumptions.
 
\subsubsection{Binary Byzantine Agreement}

The basic protocol behind our consensus protocols is a binary Byzantine
agreement protocol\cite{lashpe82,cakush00}, which allows parties to
agree on a simple binary value. In addition to agreement, the output
value also must depend on the input values; in our case, this means it
must be proposed by at least one non-corrupted pinger. We also want to
obtain a proof of the outcome, so one single pinger can prove an
external party what the outcome of a particular protocol instance was.


\subsubsection{Verifiable Multivalued Byzantine Agreement}

A multivalued Byzantine agreement protocol\cite{ckps01} allows the pingers
to agree on any bitstring, rather than only a binary value.  As there is a
(potentially) infinite universe of possible values, a multivalued
Byzantine agreement protocol can no longer guarantee that the output of
the protocol is the input of some honest party -- this would only be
possible if all honest parties propose the same value. It is, however,
possible to enforce that all honest parties verify the value prior to
agreement, and thus guarantee that it satisfies some properties, e.g.,
that it has the expected format, or contains proper signatures that
certify its validity.

\subsubsection{Broadcast protocols}

Broadcast protocols\cite{ckps01} are used to send messages from one
sender to a number of receivers. In the simplest version, the sender
simply sends the message to every other party (Note that in the Mixminion
protocol, the receivers poll the messages, rather than the sender pushing
them; for our purpose, this does not pose a significant difference). This
simple protocol does not give any guarantees to the receivers, however;
some may receive different messages, or no message at all.

A {\em consistent broadcast}, or {c-broadcast}, guarantees that all
parties that do receive a particular broadcast receive the same
value\cite{malrei98a}. It does not, however, guarantee that all parties
on the group receive anything in the first place.

A {\em reliable broadcast}, or {\em r-broadcast}, additionally guarantees
that all parties receive the broadcast\cite{bracha84}. Our model being
asynchronous, there is no guarantee about the time; the only guarantee is
that if one honest party receives the broadcast, eventually all other ones
will.

An {\em Atomic broadcast} \cite{caslis99a,reiter94} primitive additionally
guarantees that all honest parties receive all messages in the same order.
This is a rather powerful synchronization mechanism, that deals with many
uncertainties of the asynchronous network and the attackers. In principal,
it is possible to build the entire database on top of such a protocol; for
this paper, however, we have chosen dedicated protocols.
 
\subsubsection{Threshold signatures}

Threshold signatures\cite{shoup00a} allow parties to issue shares of a
signature, which then -- given enough shares are available -- can be
combine to one single signature. The nice property is that a threshold
signature outputs the same constant length signature, independent of the
actual number of parties or the subset of parties that did the actual
signing. This not only preserves space and bandwidth, but also solves the
key distribution system. A client does not need to know the public key of
any individual pinger, nor the identity of the set of pingers, but can
verify that a certain message was signed by a certain number of pingers by
verifying against one, static, public key. The disadvantage is that the
internal management of the group of pingers becomes more complex. If an
old pinger is disabled, its key share must be invalidated. Similarly, a
new pinger needs to get a new keyshare, and all thresholds need to adapt.



\subsection{The database update functions}

Due to the different character of the data in the database, 
the pingers need four different protocols to maintain
their database in a consistent state.

\subsubsection{Update set of mixes.}

The main functionality of our protocols is to maintain a consistent
set of mixes. Furthermore, a client should easily be able to obtain
that set, i.e., each pinger can prove that he gives out the correct
set. This is where the threshold signatures are used; there is only
one signature for all pingers, but a minimum of two thirds are needed
to generate the signature. Thus, a client only needs one public key
to verify she got a correct set of mixes, without needing to know
which parties are in the actual set of pingers.


\begin{algorithm}
{\bf Protocol UpdateMixes}

\begin{revpar}
 \item r-broadcast new list ${\cal L}$ of mixes
 \item wait for $n-t$ r-broadcasts.
 \item {\bf receive} a set ${\cal L}'$ of mixes
\end{revpar}
\begin{revpar}
  \item run multivalued BA protocol, using  ${\cal L}'$ as an input
  \item {\bf receive} a set ${\cal L}''$ of n-t lists
  \item let ${\cal L}'''$ be the set of mixes that have been proposed by $t+1$
  parties in the set.
  \item threshold-sign  (\em date, ${\cal L}'''$) using a threshold signature
   scheme, getting the signature share$\sigma_i$
\end{revpar}

\begin{revpar}
 \item r-broadcast the signature share $\sigma_i$
 \item wait for $n-t$ such shares
 \item combine the shares to retrieve $\sigma$
\end{revpar}
\end{algorithm}

\subsubsection{Update set of pingers.}

The protocol that updates the set of pingers is similar to the one that
updates the set of mixes. However, for this protocol it is important to
also update the shared keys, so that the old parties can not participate
in any signing process anymore, while the new parties get shares that
allow them to participate. An appropriate resharing protocol is described
in~\cite{CachinKLS02} ;

\subsubsection{Update database (externally.}

With this function, the pingers can update information about a mix, most
prominently its performance data. In the simplest case, this data is
binary; in this case, a simple binary Byzantine agreement can be performed
to determine a common value that has been proposed by at least one honest
party. To avoid communication overhead, the agreements needed for all data
on all mixes can be bundled; this leads to a protocol with message size
linear in the total number of data items, and a running time logarithmic
in the number of pingers.


Update database (internally)

This function is used to allow a mix to update database information about
himself. Most commonly, this will be used to install a new key pair once
the old one expires.  It is relatively straightforward to implement this
functionality, as the mix already has a key to authenticate itself.
Assuming this is implemented properly (i.e., the signed messages are
tagged properly), this can safely be used for database updates.

The update protocol would be a simple {\em r-broadcast} of the a signed
message requesting the update. This way, it is guaranteed that all pingers
receive the same request, and the database stays consistent. To avoid race
conditions, the mix also needs to maintain a serial number, so that all
parties can be assured to receive all updates in the same order. Note that
there exist protocols that can also enforce the all pingers receive all
update requests in the same order; however, implementing this here may be
overkill.

\subsection{Attack Model}

Since the infamous FLP impossibility proof\cite{FLP85}, it is known that
a simple problem such as agreement is quite hard in an asynchronous
environment if some parties crash or otherwise do not follow the protocol.
The only way around is to either rely on timing assumptions, or to use a
randomized algorithm.

Our choice is for randomization, for two reasons: Firstly, the randomized
model appears to be better adapted to the byzantine setting, where the
corrupted parties actively try to disrupt the protocol. Secondly, we can
expect realistic attacker in our scenario to launch denial of service
attacks on the network, which timing based protocols have difficulties
dealing with.

The price to pay for the fully asynchronous network model is a lower
tolerance. It can easily be shown that nothing useful can be done once a
third or more of all parties are corrupted. In the Mixes scenario, the
main parties for the agreement protocols are the {\em pingers}; they need
to agree on a consistent status of the {\em mixes} and then deliver it on
request to the {\em clients}. As the clients should not be forced to
contact more pingers than needed, each honest mix should be able to prove
that the result it forwards to the client is in fact the genuine outcome
of the agreement.


\subsection{The Functionality}
 Protocols Run by mixes:
  \paragraph{become\_mix:}
    With this protocol, a new server tells the pingers that he would like
    to become a mix

    Parameters: pub\_key
  \paragraph{renounce\_mix:}
    With this protocol, a mix announces he does not want to be a server 
    any more.
    
    Parameters: signature on the message 
  \paragraph{update\_pubkey}
    This protocol is used by a mix to define a new public key.

 Protocols run by clients
   \paragraph{get\_mix\_list}

 Protocols run by pingers
 \paragraph{suggest\_mix}
 \paragraph{output\_mix\_list}
 \paragraph{make\_pinger}
 
\subsection{The basic building blocks}

In this section, we introduce the basic building blocks needed for our
protocol. Due to lack of space, we do not give a formal model here.

\subsubsection{Binary Byzantine Agreement}
  
The basic Byzantine agreement protocol allows the parties to agree on a
binary value, with the property that at least one honest party must have
proposed this value initially\cite{Blah}.
 

\subsection{Verifiable Multivalued Byzantine Agreement}
 
As there is a (potentially) infinite universe of possible values, a
multivalued Byzantine agreement protocol can no longer guarantee that the
output of the protocol is the input of some honest party -- this would
only be possible if all honest parties propose the same value. It is,
however, possible to enforce that all honest parties verify the value
prior to agreement, and thus guarantee that it satisfies some properties,
e.g., that it is signed by someone.

\subsection{Broadcast protocols}

Broadcast protocols are used to send a message to a number of receivers.
If the sender and/or the network cannot be trusted, more complex
techniques have to be used to ensure properties required by higher level
protocols.

A {\em consistent broadcast}, or {c-broadcast}, guarantees that all
parties that do receive a particular broadcast receive the same value. It
does not, however, guarantee that all parties on the group receive
anything in the first place.

A {\em reliable broadcast}, or {\em r-broadcast}, additionally guarantees
that all parties receive the broadcast. Our model being asynchronous,
there is no guarantee about the time; the only guarantee is that if one
honest party receives the broadcast, eventually all other ones will.

An {\em atomic broadcast}, or {\em a-cast}, also ensures that all honest
parties receive all broadcasted messages in the same order. This is a
rather powerful primitive, as it deals with the worst effects of an
asynchronous network and allows for an easy implementation of a replicated
state machine, ensuring all replicas perform all updates in the same
order.
 

\subsection{Threshold signatures} 

A threshold signature scheme\cite{shoup00a} is a special signature scheme in
which individual parties issue shares of a signature, which then can be
combined to the full signature. The nice property is that a threshold
signature outputs the same constant length signature, independent of the
actual number of parties or the subset of parties that did the actual
signing. This not only preserves space and bandwidth, but also solves the
key distribution system - a client does not need to know the public key of
any individual pinger, nor the identity of the set of pingers, but still
can verify that a certain message was signed by the pingers. The
disadvantage is that the internal management of the group of pingers
becomes more complex. If an old pinger is disabled, its key share must be
invalidated. Similarly, a new pinger needs to get a new keyshare, and all
thresholds need to adapt.
  
\subsubsection{Key Update Protocols}

Both the agreement protocol and the threshold signatures require keys
shared between participants. Thus, modifying the set of participants is
relatively complex; old key shares need to be invalidated, and new ones
created. While the corresponding update protocols are relatively
expensive, they only need to be executed when the set of pingers changes.
Protocols suitable for this task have been described in~\cite{Proactive}.

 
\subsection{Protocol Implementation}

The following protocol, executed by the pingers, can be used to update the
mix list

%FIXME FIXME FIXME: TeXify me  (==> is not right)
 r-broadcast new list ${\cal L}$ of mixes \\
 wait for $n-t$ r-broadcasts. \\
 ==> a set ${\cal L}'$ of mixes \\
 run multivalued BA protocol, using  ${\cal L}'$ as an input\\
 ==> a set ${\cal L}''$ of n-t lists\\
 let ${\cal L}'''$ be the set of mixes that have been proposed by $t+1$ parties in the set.\\
 threshold-sign  (\em date, ${\cal L}'''$) using an (n,n-t) threshold signature scheme\\
 ==> $\sigma_i$\\
 r-broadcast the signature share $\sigma_i$\\
 wait for $n-t$ such shares\\
 combine the shares to retrieve $\sigma$\\


\section{Conclusions and future work}
\label{conclusions}

% WRITE ME

\subsection*{Acknowledgments}

The author of Echolot would like to thank Lucky Green and Colin Tuckley
for writing end user documentation and keeping it current, Orange admin
for work on the HTML templates that make up Echolot's output, and BiKiKii
Admin, noisebox Admin and many nameless testers for providing valuable
feedback during Echolot's development.

\bibliographystyle{plain}
\bibliography{pingers}

\end{document}