[freehaven-cvs] Added first-pass at the agreement protocol.

[rabbi@xxxxxxxx]

Update of /home2/freehaven/cvsroot/doc/pingers
In directory moria:/tmp/cvs-serv2537

Modified Files:
	pingers.tex 
Log Message:
Added first-pass at the agreement protocol.


Index: pingers.tex
===================================================================
RCS file: /home2/freehaven/cvsroot/doc/pingers/pingers.tex,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -d -r1.1 -r1.2
--- pingers.tex	27 Oct 2005 09:04:14 -0000	1.1
+++ pingers.tex	27 Oct 2005 15:45:59 -0000	1.2
@@ -148,8 +148,7 @@
 long-term (signing) public key, short-term (message decryption) public
 key, remixing capability, and batching strategy.
 
-%FIXME [Does Mixminion have any details on calculation stategy? Not sure,
-%but I should check the source.]
+FIXME [Does Mixminion have any details on calculation stategy? Not sure, but I should check the source.]
 
 \section{Gaming the data}
 
@@ -220,8 +219,144 @@
 availability, and provides every client with a consistent information with
 which to calculate message paths.
 
-%[FIXME Klaus's protocol goes here]
+[FIXME Klaus's protocol goes here]
+
+
+To recap:
+
+Remailer network monitoring problems:
+
+All users must have one view of the network.
+
+There's no fixed number of mixes or pingers.
+
+Anyone can announce themselves as a mix.
+
+Users should have to query no more than three pingers to get the network
+view.
+
+The pinger results (the directory contains:
+
+mix address (which should be the index for the directory)
+Latency (high/low)
+mix status (valid/invalid)
+mix status (confirmed/unconfirmed)
+mix pubkeys
+mix key expiration dates
+is a pinger (y/n)
+
+
+
+
+
+\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 teo reasons: Firstly, the randomised 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 usefull 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 Functionallity}
+ 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 anymore.
+    
+    Paramters: 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) invinite 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 vaule 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 
+
+  A {\em consistend broadcast}, or {c-broadcast}, guarantees that all parties that do receive a particular
+  broadcast recieve the same value. It does not, however, guarantee that all parties on the group reveive
+  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 guarantere is that
+  if one honest party receives the broadcast, eventually all other ones will.
+ 
+
+ \subsection{Threshold signatures}
+  A threshold signature scheme\cite[shoup] 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
+  actuall number of parties or the subset of parties that did the actuiall signing. This not only preserves 
+  space and bandwith, 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 disabeled, its key share must be invalidated. Similary, 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
+
+ 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}
 

***********************************************************************
To unsubscribe, send an e-mail to majordomo@xxxxxxxx with
unsubscribe freehaven-cvs       in the body. http://freehaven.net/