[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] minor tweaks throughout
Update of /home/freehaven/cvsroot/doc/sync-batching
In directory moria.mit.edu:/home2/arma/work/freehaven/doc/sync-batching
Modified Files:
model-app.tex model.tex sync-batching.tex
Log Message:
minor tweaks throughout
Index: model-app.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/model-app.tex,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -d -r1.1 -r1.2
--- model-app.tex 23 Jan 2004 19:57:26 -0000 1.1
+++ model-app.tex 23 Jan 2004 22:52:22 -0000 1.2
@@ -113,7 +113,7 @@
Probability distribution is computed in exactly the same way for a
free-route network as for a stratified array, except that the entire set
of mixes is treated as a layer. Consider a 4x2 free-route network as in
-fig.~\ref{free-4x2}. With 128 messages per batch, the buffer for each
+fig.~\ref{fig:free-4x2}. With 128 messages per batch, the buffer for each
mix is 32 messages. If $A$ is the first mix selected (and is hostile
with probability $\frac{1}{4}$), the probability distribution after the
message passes through $A$ is
Index: model.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/model.tex,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -d -r1.2 -r1.3
--- model.tex 23 Jan 2004 19:57:26 -0000 1.2
+++ model.tex 23 Jan 2004 22:52:22 -0000 1.3
@@ -166,6 +166,6 @@
of the actual random distribution of a given batch through the network.
Appendix \ref{sec:walk-through} provides a walk-through of calculating
-entropy for each topology, to help build intuition about our assumptions
-and results.
+entropy for each topology, to help the unfamiliar reader build intuition
+about our assumptions and results.
Index: sync-batching.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/sync-batching.tex,v
retrieving revision 1.29
retrieving revision 1.30
diff -u -d -r1.29 -r1.30
--- sync-batching.tex 23 Jan 2004 21:33:01 -0000 1.29
+++ sync-batching.tex 23 Jan 2004 22:52:22 -0000 1.30
@@ -336,8 +336,8 @@
\section{Threat model and Mixnet Topologies}
\label{sec:scenarios}
-The threat model we consider is a slight variant of the standard one,
-for example as given in \cite{disad-free-routes}. Senders of messages
+We consider a slight variant on the traditional powerful
+adversary~\cite{disad-free-routes}. Senders of messages
input to the mixnet and receivers of messages output from the mixnet
can be observed. It is assumed that selective forwarding will be
discovered and prevented, or the misfunctioning node will be removed
@@ -354,24 +354,23 @@
more than an adversary that observes its network connections. In this
sense our model subsumes such a threat provided the adversary is not
global. Adversaries are also assumed to compromise nodes at random
-rather than in a targeted fashion. See Section~\ref{?} for more
-discussion on this point. We have only described a passive attacks,
-active attacks are discribed in Section~\ref{subsec:anonymity-robustness}.
+rather than in a targeted fashion. See Section~\ref{subsec:random-adversary} for more
+discussion on this point. We have only described passive attacks,
+active attacks are described in Section~\ref{subsec:anonymity-robustness}.
For all of our analyses, we assume a 16 node mixnet with all messages
following a four node path. (We do say a few things about a 16 node
-path free route.) We use the the same number for all mixnets so as to
+path free route.) We use the same number for all mixnets to
have a reasonably fair comparison of available resources. Besides
being a tractable size for analysis, this is also a fairly good
-approximation of actually deployed mixnets. (Mixmaster typically has
+approximation of actually deployed mixnets. (Mixminion currently has
between 20 and 30 active nodes.)
Messages proceed through all of our networks in \emph{layers}; all of the
nodes in a layer process messages of one mxinet batch at the same time.
-In general we describe networks as $n$x$\ell$, where $n$ is the number
+In general we describe networks as $n$x$\ell$, where $n$ is the number
of nodes at each layer and $\ell$ is the number of nodes in a path.
-
We consider three basic topologies: a 4x4 cascade mixnet in which all
messages pass through four cascades of length four; a 4x4
\emph{stratified} mixnet, in which all messages pass through four
@@ -408,21 +407,6 @@
\input{model}
-
-
-\subsection{further Assumptions}
-[Safe to cut now? Anything in this subsec not covered elsewhere? -PS]
-
-also discuss how scenario 3 makes a different assumption about the
-adversary, since watching all the nodes requires more power than just
-watching the entry and exit columns.
-
-also, notice that since the batch period is large and the hop period is
-short, most of the nodes will be idle nearly all the time in scenarios
-1 and 2, whereas they get used at every hop in scenarios 3 and 4. so
-scenario 4 is not so farfetched, if we can convince ourselves that
-the reliability issues aren't bad.
-
\section{Graphs and Analysis}
\label{sec:graphs}
@@ -466,6 +450,7 @@
\label{sec:other}
\subsection{Is the adversary really randomly distributed?}
+\label{subsec:random-adversary}
To keep our model tractable, we have assumed that each node has an
equal chance of being controlled by the adversary. A real adversary
@@ -513,8 +498,8 @@
more negligible. This is also true as the network size grows.
For example, for a 32x4 mixnet with half bad nodes, the difference
is 5.7\% vs.\ 6.3\% . At what point this difference can safely
-be ignored is a question that can only be answered in context, but
-we will ignore it for the present.
+be ignored is a question that can only be answered in context.
+% but we will ignore it for the present.
% Mention that we have that entropy different for each of \ell hops.
% But it's just \ell times the above negligible difference, right? -RD
@@ -525,11 +510,12 @@
% knows she doesn't exit from her entry node. Hm. -RD
\subsection{Average Entropy vs Actual Entropy}
+\label{subsec:average-actual}
The graphs and analysis above are for average entropy---the network's
-expected behavior for very large batches. But in reality the batch size
+behavior for very large batches. But in reality the batch size
may be quite small, and each sender chooses paths independently from the
-others. We must consider the variance we might get in entropy depending
+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
@@ -597,29 +583,33 @@
\section{Other metrics for comparison}
\label{sec:metrics}
-\subsection{Capacity and throughput}
+\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
+$\ell=4$, that users deliver 128 messages every 3 hours, and that users
+will tolerate a latency of 3-6 hours.
-An important constraint on the network structure is 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.
+One approach is to choose $t_\mathrm{batch} = t_\mathrm{hop}$.
+We let 32 messages in every 45 minutes.
-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 were used optimally (this is a big if),
-the bandwidth required through each node in this simplified case
-will be $\frac{T_{batch}}{wt_{hop}} = \frac{nT_{batch}}{wt_{batch}}$.
+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}}$.
[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.]
-\subsection{Mixing with previous and future batches}
-% not really a metric, but fits nicely after 'capacity' discussion. -RD
+Mixing with previous and future batches
The free-route topology can add a new batch at every hop,
increasing the anonymity everybody gets. maybe.
@@ -885,7 +875,7 @@
hop or in each cascade, respectively) will be more uniform.
-%\section*{Acknowledgements}
+\section*{Acknowledgements}
David Hopwood for the initial impetus and ideas; Camilla Fox, Rachel
Greenstadt, LiWu Chang, Chris Laas, Ira Moskowitz,
and Itamar Shtull-Trauring for probability discussions;
***********************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe freehaven-cvs in the body. http://freehaven.net/