Author: rabbi
Date: 2007-06-10 14:20:08 -0400 (Sun, 10 Jun 2007)
New Revision: 1784
Modified:
doc/trunk/pingers/echolot.tex
Log:
Added Klaus's changes.
Modified: doc/trunk/pingers/echolot.tex
===================================================================
--- doc/trunk/pingers/echolot.tex 2007-05-10 13:09:01 UTC (rev 1783)
+++ doc/trunk/pingers/echolot.tex 2007-06-10 18:20:08 UTC (rev 1784)
@@ -517,30 +517,36 @@
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.}
+\subsubsection{Asynchronous 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 to an
-external party what the outcome of a particular protocol instance was.
+The basic problem behind coordinating mutually untrusting parties is the
+problem of {\em Byzantine Agreement}~\cite{lashpe82}. Given a
+set of participants with different (binary) input values, a Byzantine
+agreement protocol allows parties to agree on one common output that has
+been proposed by an uncorrupted pinger~\cite{cakush00}, in spite of the presence
+of undetected traitors that try to disrupt the agreement and unpredictable
+network delays.
+For our application, we also require a transferable proof of the outcome, so one
+single pinger can prove to 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
+A multivalued Byzantine agreement protocol~\cite{ckps01} extends the
+binary protocol to allow the pingers
to agree on any bit-string, 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
+the protocol is the input of some uncorrupted pinger -- this would only be
+possible if all uncorrupted pingers propose the same value. It is, however,
+possible to enforce that all pingers 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.
+We will denote with $y= $ {\em mult\_BA($x$)} the invocation of a multivalued Byzantine
+Agreement protocol with input $x$, yielding the output $y$.
\subsubsection{Broadcast protocols.}
Broadcast protocols~\cite{ckps01} are used to send messages from one
@@ -552,39 +558,43 @@
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
+pingers that do receive a particular broadcast receive the same
+value~\cite{malrei98a}. It does not, however, guarantee that all pingers
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
+that all pingers 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
+that if one uncorrupted pinger 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.
+guarantees that all uncorrupted pingers 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 principle,
it is possible to build the entire database on top of such a protocol; for
-this paper, however, we have chosen dedicated protocols.
+this paper, however, we have chosen more efficient dedicated protocols.
\subsubsection{Threshold signatures.}
-Threshold signatures~\cite{shoup00a} allow parties to issue shares of a
+Threshold signatures~\cite{shoup00a} allow pingers to issue shares of a
signature, which then -- given enough shares are available -- can be
combined into 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
+signing. This not only preserves space and bandwidth, but also allows for
+easy key distribution.
+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
+verifying against one single, 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 key-share, and all thresholds need to adapt.
+We will denote with {\em tsign\_generate(x)} the generation of a signature share
+of a threshold signature scheme, while {\em tsign\_combine($x_1,...x_n$)}
+comnines $n$ such shares into the final signature.
\subsection{The database update functions}
@@ -604,32 +614,52 @@
to verify she got a correct set of mixes, without needing to know
which parties are in the actual set of pingers.
+As an input for the protocol, each pinger $P_i$ has its own set
+${\cal L}_i$ of mixes it considers valid. The protocol then has
+2 phases; in the amplicifaction phase, each party collects the
+signed input of $n-t$ of other parties, and thus --- as less than a third
+of all parties are corrupt --- of at least $t+1$ uncorrupted parties.
+
+In the agreement phase, each party proposes its collection of inputs for
+a multivalued Byzantine agreement protocol, agreeing on one such set. It
+is possible that this set was proposed by a malicious party; however, as
+the initial sets where signed by the sender, any acceptable outcome set must
+contain at least $t+1$ proper lists proposed by uncorrupted parties.
+
+In the final step, a set of valid mixes is generated. To that end,
+each mix in the set of lists proposed by only $t$ pingers is removed; thus,
+only pingers proposed by at least one honest pingers remain. As the final list
+contains the input of at least $t+1$ pingers, every mix that is in the list
+of all uncorrupted pingers will be in the final set.
+The final list is then signed by a combined signature, allowing a party to
+prove that it is the proper list resulting from the protocol.
+
+
% FIXME -- I can't seem to get the LaTeX to like a \framebox here.
% Let's put a rectangular frame around the Protocol UpdateMixes?
\begin{algorithm}
-{\bf Protocol UpdateMixes}
+{\bf Protocol UpdateMixes for pinger $P_i$}
\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
+ \item r-broadcast new (signed) list ${\cal L}_i$ of mixes
+ \item wait for ($n-t$) valid r-broadcasts
+ \item let ${\cal L}'= {\cal L}_{j_1}, .... {\cal L}_{j_{n-t}}$ be a set of received $n-t$ lists.
\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$
+ \item ${\cal L}''$ = {\em mult\_BA} (${\cal L}'$)
+ \item let ${\cal L}'''$ be the set of mixes in ${\cal L}''$ that have been proposed by $t+1$ pingers
+ \item $\sigma_i$ = {\em tsign\_generate}({\em date}, ${\cal L}'''$)
\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$
+ \item r-broadcast $\sigma_i$
+ \item wait for ($n-t$) such shares $\sigma_{j_1,}..., \sigma{j_{n-t}}$.
+ \item $\sigma$ = {\em tsign\_combine}($\sigma_{j_1},...,\sigma_{j_{n-t}}$).
\end{revpar}
+output (${\cal L}'''$, $\sigma$)
\end{algorithm}
+
\subsubsection{Update set of pingers.}
The protocol that updates the set of pingers is similar to the one that
@@ -664,9 +694,13 @@
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
+parties can be assured to receive all updates in the same order; due to the
+properties of the {\em r-broadcast} protocol, all pingers will eventually receive
+all update requests from the mix, so malicious manipulation of the serial numbers can
+only lead to a temporary inconsistency.Note that
there exist protocols that can also enforce that all pingers receive all
-update requests in the same order; however, implementing this here may be
+update requests in the same order; however, the those protocols
+are rather complex, so implementing this here may be
overkill.
%
% FIXME Klaus -- say something about why this is overkill?
@@ -679,7 +713,7 @@
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
+Our choice of implementation 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
@@ -687,8 +721,8 @@
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.~\cite{FIXME} {\em FIXME, Klaus!}
+tolerance. It has been shown that even binary agreement is impossible
+once a third or more of all parties are corrupted~\cite{lashpe82}.
In the mix-net scenario, the
main parties for the agreement protocols are the pingers; they need
to agree on a consistent status of the mixes and then deliver it on
***********************************************************************
To unsubscribe, send an e-mail to majordomo@xxxxxxxx with
unsubscribe freehaven-cvs in the body. http://freehaven.net/