[minion-cvs] resolved the batching section

[arma@seul.org (Roger Dingledine)]

Update of /home/minion/cvsroot/doc
In directory moria.seul.org:/home/arma/work/minion/doc

Modified Files:
	minion-design.tex 
Log Message:
resolved the batching section


Index: minion-design.tex
===================================================================
RCS file: /home/minion/cvsroot/doc/minion-design.tex,v
retrieving revision 1.84
retrieving revision 1.85
diff -u -d -r1.84 -r1.85
--- minion-design.tex	6 Nov 2002 04:10:07 -0000	1.84
+++ minion-design.tex	6 Nov 2002 04:18:24 -0000	1.85
@@ -1348,23 +1348,29 @@
 \cite{batching-taxonomy}. By repeatedly
 attacking each mix in the path, the adversary will link Alice and Bob.
 
-%XXXX
 Mixminion nodes use a \emph{timed dynamic-pool} batching strategy
-\cite{batching-taxonomy} adapted from Mixmaster. A
-mix fires every... [insert Cottrell mix description here. Perhaps put
-the algorithm itself from the spec into a side box, or an appendix?]
+\cite{batching-taxonomy} adapted from Mixmaster. Rather than simply
+processing each message as soon as it arrives, each mix keeps a pool of
+messages. New messages arrive, are decrypted, and enter the pool. The
+mix fires every $t$ seconds, but only if the pool contains at least a
+threshold of messages. If the mix fires, it randomly chooses a constant
+fraction of the pool messages (say, 60\%) to deliver.
 
-Timed dynamic-pool mixes increase
-the cost of the blending attack: because the number of messages coming
-out at each flush is always a fraction of the number waiting, it is
-impossible to arrange to completely flush the mix with high probability
-in one flush. Thus an adversary is forced to spend multiple intervals
-(and thus delay other messages for considerable time) first to flush
-the original honest messages from the mix, and again to flush the
-target message from the mix. This delay will be noticed by the other
-mixes, because they communicate over TLS with a heartbeat to detect
-delays.
+Since the number of messages delivered each round is based on the rate of
+incoming messages, an attacker cannot overflow the pool with sustained
+flooding. These mixes also increase the cost of the blending attack:
+while the \emph{number} of messages coming out increases as the rate
+of incoming messages increases, the chance that any given message will
+leave the pool remains constant. Thus it is impossible to arrange to
+completely flush the mix with high probability in one flush. An adversary
+is forced to spend multiple intervals (and thus delay other messages
+for considerable time) first to flush the original honest messages from
+the mix, and again to flush the target message from the mix. This delay
+will be noticed by the other mixes, because they communicate over TLS
+with a heartbeat to detect delays.
 % XXXX Huh? Heartbeat? -NM
+% spoke to you about this on the phone. feel free to add clarifying
+% text if you like. there's another place we say heartbeat too. -RD
 
 This batching strategy also increases the cost of intersection attacks by
 providing large anonymity sets for each message in the network. Because
@@ -1394,8 +1400,9 @@
 honest messages remain. In the second phase of the attack, he again
 needs to flush until the target message comes out; but once it does, he
 can be certain of recognizing it. Thus Mixminion employs the following
-dummy policy, as suggested in \cite{batching-taxonomy} and analyzed in 
-\cite{andrei-claudia}: each time the mix
+dummy policy, as suggested in \cite{batching-taxonomy}:
+%and analyzed in \cite{andrei-claudia}:
+each time the mix
 fires, it also sends out a number of dummies chosen from a geometric
 distribution. These dummies travel a number of hops chosen uniformly
 between $1$ and $4$. The blending attack is now harder --- the adversary