[freehaven-cvs] Tweaks throughout. Discussion of throughput, latency...

[syverson@seul.org]

Update of /home/freehaven/cvsroot/doc/sync-batching
In directory moria.mit.edu:/tmp/cvs-serv29671/sync-batching

Modified Files:
	sync-batching.pdf sync-batching.tex 
Log Message:
Tweaks throughout. Discussion of throughput, latency, etc.


Index: sync-batching.pdf
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/sync-batching.pdf,v
retrieving revision 1.9
retrieving revision 1.10
diff -u -d -r1.9 -r1.10
Binary files /tmp/cvsbh3T9G and /tmp/cvsGLogNp differ

Index: sync-batching.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/sync-batching.tex,v
retrieving revision 1.38
retrieving revision 1.39
diff -u -d -r1.38 -r1.39
--- sync-batching.tex	24 Jan 2004 08:32:42 -0000	1.38
+++ sync-batching.tex	24 Jan 2004 23:18:48 -0000	1.39
@@ -11,6 +11,7 @@
 \newcommand{\workingnote}[1]{}        % The version that hides the note.
 %\newcommand{\workingnote}[1]{(**#1)}   % The version that makes the note visible.
 
+\hyphenation{mix-net mix-nets}
 
 \newenvironment{tightlist}{\begin{list}{$\bullet$}{
   \setlength{\itemsep}{0mm}
@@ -27,7 +28,8 @@
 %  Free Routes
 %\title{Groove Mixing:\\Synchronous Batching from Cascade Networks to Free Routes
 %\title{Synchronous Batching:\\Beat Mixing from Cascade Networks to Free Routes
-\title{Heartbeat Mixing: Synchronous Batching from Cascade Networks to Free Routes
+%\title{Heartbeat Mixing: Synchronous Batching from Cascade Networks to Free Routes
+\title{Synchronous Mixnets: From Cascades to Free Routes
 \thanks{Portions of this paper were inspired by discussions with David
 Hopwood. We would consider him an author, but have been unable to contact
 him since beginning the paper. We'll keep trying.}}
@@ -41,7 +43,8 @@
 %======================================================================
 \begin{abstract}
 
-XXXneeds an intro sentence.
+Synchronous mixnets are vastly superior to asynchorous mixnets in
+many ways.
 In a synchronous batching design, each batch of messages enters the
 mix network together, and the messages proceed in lock step through
 the network. We show that a synchronous batching strategy can be used
@@ -527,9 +530,9 @@
 others. We must consider the variance we could get in entropy depending
 on how the path choices actually turn out.
 
-For $m$ messages to $u$ buckets, we find the chance that any bucket
-will have less than $p$ messages based on Maxwell-Boltzmann statistics
-and inclusion-exclusion:
+For $m$ messages to $u$ buckets (nodes in a layer), we find the chance
+that any bucket will have less than $p$ messages based on
+Maxwell-Boltzmann statistics and inclusion-exclusion:
 
 \begin{eqnarray*}
 {u \choose 1} \sum_{i=0}^p (\frac1{u})^i (1-\frac1{u})^{m-i} {m \choose i}
@@ -555,8 +558,10 @@
 Second, how bad is it when a link varies by half the expected volume? If
 we change our metric to require at least 2 messages on each link for
 $m=128$, then we find that only 1\% of the cases fall outside this value.
-
-XXXplus think about chance for all layers not just one.
+Another significant question is how the number of layers affect the
+results. The more layers, the greater the chance that some of them will
+well balanced. But, the exact relation and its effect on entropy are
+open questions.
 
 Danezis also considers this issue of variance from average entropy for his
 mixnet design based on sparse expander graphs~\cite{danezis:pet2003}. He
@@ -589,7 +594,7 @@
 that the fraction of adversary messages in the batch limits the maximum
 size of the flooding attack---honest messages will still be randomly
 distributed. In general, this flooding issue is an unsolved problem for
-all mix-net designs; more research remains.
+all mixnet designs; more research remains.
 
 \section{Other metrics for comparison}
 \label{sec:metrics}
@@ -597,33 +602,68 @@
 \subsection{Capacity, throughput, delay, reliability}
 
 One parameter we cannot control is the rate that messages arrive to the
-mix-net. Similarly, we cannot control the latency that users will be
-willing to accept. To make the analyze more concrete, assume we choose
+mixnet. Similarly, we cannot control the latency that users will be
+willing to accept. To make the analysis more concrete, assume we choose
 $\ell=4$, that users deliver 128 messages every 3 hours, and that users
-will tolerate a latency of 3-6 hours.
+will tolerate a latency of 3-6 hours (which is on par with the latency
+that is currently experienced by a typical Mixmaster message, though
+they could be much longer in theory).
 
-One approach is to choose $t_\mathrm{batch} = t_\mathrm{hop}$.
+One approach is to choose $t_\mathrm{batch} = t_\mathrm{hop}$, so that
+processing occurs in uniform systolic cycles.
 We let 32 messages in every 45 minutes.
 
 
-We can compute the maximum bandwidth (traffic in unit time) through any
-given node. Assume that sending a message over a single hop consumes a
-fixed amount of network traffic; we can then use that as the unit for
-traffic. Let $T_\mathrm{batch}$ be the expected throughput in a single
-batch period, i.e.~the number of messages that go through the network
-in a batch. If the available nodes are used optimally (see Section
-\ref{subsec:average-actual}), the bandwidth required through each node
-is $\frac{T_\mathrm{batch}}{wt_\mathrm{hop}} =
-\frac{\ell T_\mathrm{batch}}{wt_\mathrm{batch}}$.
+We can compute the maximum flow rate (traffic in unit time) through
+any given node. Assume that sending a message over a single hop
+consumes a fixed amount of network traffic; we can then use that as
+the unit for traffic. Let $T_\mathrm{batch}$ be the expected
+throughput in a single batch period, i.e.~the number of messages that
+go through the network in a batch. If the available nodes are used
+optimally (see Section \ref{subsec:average-actual}), the flow rate
+required through each node is $\frac{T_\mathrm{batch}}{w \cdot
+  t_\mathrm{hop}} = \frac{\ell \cdot T_\mathrm{batch}}{w \cdot
+  t_\mathrm{batch}}$.
 
-[Should note somewhere that stratified is like classic systolic arrays
-in that a layer can process a new batch as soon as it has sent the
-last with no additional overhead. That's not true of free routes.]
+For our example, this amounts to 42.7 messages/hour for a 4x4 mixnet,
+whether cascade or stratified.  In a 16x4 free-route mixnet the
+expected flow rate is the same because each node is processing a
+quarter as many messages per batch but processing four mixnet batches
+in the same period. This also means that multiple different mixnet
+batches are effectively being mixed together at one time.  That could
+be a factor for reducing the threat of internal observations, but it
+should not affect the anonymity in the face of an adversary watching
+only messages that enter and leave the mixnet as in this paper.
+Latency for a messages is between 2 hours 15 minutes and 3 hours.
+Maximum possible entropy is 5 (3 for the 4x4 cascade).
 
-Mixing with previous and future batches
+Alternatively, we can choose $t_\mathrm{batch} = \ell t_\mathrm{hop}$,
+so that all messages clear the mixnet before the next batch enters.
+We let 128 messages enter the network every 3 hours. Throughput per
+batch is increased, but throughput per unit time is the same as above.
+Latency is now between 2 hours 15 minutes and 5 hours 15 minutes. Note
+that flow rate per node is also the same as above. However, maximum
+entropy is raised to 7 (5 for the 4x4 cascade).  If it were desired to
+have the maximum latency the same, it would be necessary to reduce
+$t_\mathrm{hop}$ to 15 minutes. This would correspondingly raise the
+flow rate per node by a factor of three. Note that the longer
+$t_\mathrm{batch}$ means more smoothing of spikes and troughs in
+$T_\mathrm{batch}$. Also, while it is still possible to coordinate
+messages within a batch to arrive at the same free-route node in the
+same period by choosing the layer appropriately, it is not possible to
+coordinate messages from multiple batches to flood a given node at the
+same time (as would be possible in the uniform systolic case).
 
-The free-route topology can add a new batch at every hop,
-increasing the anonymity everybody gets. maybe.
+[Drop everything from here to end of the subsection? -PS]
+
+Note that synchronous batching does not necessarily mean a "one
+latency fits all" approach. People who want a larger anonymity set can
+agree to send their messages only at intervals of $k \cdot
+t_\mathrm{batch}$, so those batches will have more messages (but at
+the expense of the other batches). This implies a fair degree of coordination
+and the flip side is a freedom to flood the network to some extent.
+It may also attract attackers to such cabals so that the net anonymity
+does not increase.
 
 [like S-G mixes, the sender chooses to delay at certain nodes, which
 improves anonymity. no reason why we couldn't too, really.]
@@ -650,31 +690,25 @@
 the path. In this scheme, messages that ask to be delayed are inherently
 more interesting. -RD]
 
-Possible extension: Note that synchronous batching does not necessarily
-mean a "one latency fits all" approach. People who want a larger anonymity
-set can agree to send their messages only at intervals of $k*t_\mathrm{batch}$,
-so those batches will have more messages (but at the expense of the
-other batches).
 
 \subsection{Robustness of Message Delivery}
 
-XXXPut the graph of 1x16 vs 16x16 entropy, as motivation for robustness
-analysis.
-
-XXXpoint out that we could use 16x4 for a fair comparison, or we could
-use $16 \times \ell$ to get more or less anonymity.
-
 % somewhere, cite the 1990 paper about cascades that can skip nodes
 
-It might seem from Fig.~\ref{fig:?} that the best anonymity is
-achieved with a 16x16 free-route network. There is almost no falloff
-in entropy until each node has a ninety percent chance of being
-compromised. But this ignores robustness of message delivery. (Robustness of
-anonymity is discussed below.) With only a single node failure, for
-randomly chosen routes through this mixnet, nearly two thirds of
+Better anonymity is achieved by longer routes. For example, in a 1x16
+cascade or a 16x16 free-route, the entropy is virtually identical.
+There is almost no falloff in entropy until each node has a ninety
+percent chance of being compromised. But this ignores robustness of
+message delivery.  (Robustness of anonymity is discussed below.) For
+the free-route mixnet with only a single node failure (and for
+randomly chosen routes through this mixnet) nearly two thirds of
 messages will be undelivered (because they will need to pass through
-it at some point). Such a network is very brittle.
-This illustrates that robustness can be an important question.
+it at some point). Such a network is very brittle. For the cascade, it
+is even worse: a single node crash blocks all message delivery.
+Parallel cascades can be added to the network, however unlike the
+free-route, this will a priori reduce the entropy of an input message
+for the same size mixnet batch.  This illustrates that robustness can
+be an important question.
 
 
 \begin{table} \caption{Percent of messages delivered}

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