[freehaven-cvs] clean up 7.1

[arma@seul.org (Roger Dingledine)]

Update of /home/freehaven/cvsroot/doc/sync-batching
In directory moria.mit.edu:/home2/arma/work/freehaven/doc/sync-batching

Modified Files:
	sync-batching.tex 
Log Message:
clean up 7.1


Index: sync-batching.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/sync-batching.tex,v
retrieving revision 1.43
retrieving revision 1.44
diff -u -d -r1.43 -r1.44
--- sync-batching.tex	26 Jan 2004 13:55:14 -0000	1.43
+++ sync-batching.tex	26 Jan 2004 15:11:23 -0000	1.44
@@ -630,23 +630,16 @@
 \section{Other metrics for comparison}
 \label{sec:metrics}
 
-\subsection{Capacity, throughput, delay, reliability}
-
-[This section still draft -RD]
+\subsection{Throughput, delay, capacity, bandwidth}
 
 One parameter we cannot control is the rate that messages arrive to the
 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 (which is on par with the latency
-that is currently experienced by a typical Mixmaster message, though
+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}$, so that
-processing occurs in uniform systolic cycles.
-We let 32 messages in every 45 minutes.
-
-
 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
@@ -658,36 +651,65 @@
   t_\mathrm{hop}} = \frac{\ell \cdot T_\mathrm{batch}}{w \cdot
   t_\mathrm{batch}}$.
 
-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).
+%We could choose $t_\mathrm{batch} = t_\mathrm{hop}$, so that
+%processing occurs in uniform systolic cycles:
+%we let 32 messages in every 45 minutes.
+%This is 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.\footnote{On first sight it also looks like multiple
+%different batches are effectively being mixed together at each hop---
+%but an adversary watching messages that enter and leave the
+%mixnet can easily partition the batches.} Latency for Alice's message
+%is between 3 hours and 3 hours 45 minutes,
+%depending on when Alice's message arrives.
+%Maximum possible entropy is 5 (3 for the 4x4 cascade).
+%
+% I really don't like this option. The entropy is going to suck,
+% particularly wrt the free-route system, where you get an expected
+% *two* messages into each node per batch. Even Vitaly can't claim
+% the actual entropy will whp approximate the average entropy for that
+% situation. :)
+% I bring the issue up briefly below, but don't present the bad option
+% as the first one the reader sees.
 
-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).
+If we choose $t_\mathrm{batch} \simeq \ell t_\mathrm{hop}$, all messages
+clear the mixnet before the next batch enters: we introduce a batch
+of 128 messages every 3 hours. We get 42.7 messages/hour for all three
+topologies. Latency is between 3 hours and 6 hours, depending on when
+Alice's message arrives. By accepting messages over a large amount
+of time, we get better expected entropy; make the actual behavior
+of the network closer to the expected behavior of the network (as in
+Section~\ref{subsec:average-actual}); and smooth spikes and troughs
+in the rate of incoming messages.
 
-%[Drop everything from here to end of the subsection? -PS]
+In the free-route network, each node needs to process 8 messages at a
+time, and it's active at each layer. The cascade and stratified networks
+require a larger capacity from each node: they must be able to handle 32
+messages at once (128/$w$), but they are idle for all but one hop in the
+batch. One could imagine a \emph{systolic network} where $t_\mathrm{batch}
+= t_\mathrm{hop}$ and 32 messages are let in every 45 minutes---in this
+case the capacity of nodes in cascade and stratified networks would also
+be 8, and indeed the latency could be cut to between 3 hours and 3 hours
+45 minutes---but the expected entropy would be cut by a factor of $\ell$.
+
+Bandwidth is acceptable. Assuming a higher load of 1280 messages per
+batch, and 32KB per message (as in Mixminion), nodes in the free-route
+system spend less than 4KB/s on batch (nodes in the other
+topologies need 16KB/s but only 1/4 of the time). That's well within
+the capabilities of current Mixmaster nodes.
+
+%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).
 
 %Note that synchronous batching does not necessarily mean a "one
 %latency fits all" approach. People who want a larger anonymity set can
@@ -698,30 +720,18 @@
 %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.]
-
-%Possible extension: for the purpose of discussion, let's use
-%$t_\mathrm{batch}$ = 3 hours and $t_\mathrm{hop}$ = 1 hour / n. Then
-%the latency is between
-%1 and 4 hours, and the anonymity set is the set of messages sent in a
-%3 hour period.
-
-We can improve this by having a "delay until next batch" option in
-the message subheader; that would delay the message by $t_\mathrm{batch}$ and
-re-introduce it at the same point in the path. If each message is either
-delayed once or not delayed, that gives us a latency of 1 to 4 hours for
-non-delayed messages, 4 to 7 hours for delayed messages, and a 6-hour
-anonymity set (unless the attacker knows that someone never sends or
-receives delayed messages, in which case the anonymity set for those
-users is still 3 hours).
-
-%Can anyone attack the "delay until next batch" option? I don't think
-%the fact that those messages can be distinguished by the node is any
-%more harmful than Mixminion's "swap" operation, etc. [It seems a bit
-%more harmful: in Mixminion, all messages have a swap point somewhere in
-%the path. In this scheme, messages that ask to be delayed are inherently
-%more interesting. -RD]
+Like stop-and-go mixes \cite{stop-and-go}, we may be able to get improved
+anonymity by allowing Alice to choose to delay her message at a given
+hop until the next batch. That is, the node would delay her message by
+$t_\mathrm{batch}$ and re-introduce it at the same point in the path.
+If each message is either delayed once or not delayed, that gives us
+a latency of 3 to 6 hours for non-delayed messages, 6 to 9 hours for
+delayed messages, and a 6-hour anonymity set (unless the attacker knows
+that someone never sends or receives delayed messages, in which case the
+anonymity set for those users is still 3 hours; also, if the attacker
+owns the node Alice chooses, he may be able to speculate about which
+senders would choose to delay messages). We leave further investigation
+to future work.
 
 \subsection{Robustness of Message Delivery}
 

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