
\section{Entropy examples for each topology}
\label{sec:walk-through}

\subsection{Cascade.}

Consider a 2x2 cascade network as in Figure~\ref{fig:casc-2x2}.  Assume
there are 128 messages in a batch, and that any node has $\frac{1}{4}$
chance of having been compromised.  Let $m$ be the targeted message,
and suppose the adversary observed that the sender of $m$ chose $A$
as the first mix.  Under the equal loading assumption, there are 63
other messages in addition to $m$ that chose $A$ as the first mix.
Without loss of generality, we may assume that $m$ occupies the first
position in $A$'s input buffer of length 64.

With probability $\frac{1}{4}$, mix $A$ is hostile.  In this case,
$m$ remains in the first position after passing through the mix.
With probability $\frac{3}{4}$, mix $A$ is honest.  In this case, $m$
appears in any of the 64 output positions of this mix with probability
$\frac{1}{64}$ (note that $m$ may not appear in the output buffer of
mix $B$).  The resulting probability distribution for $m$'s position
after passing through $A$ is
\begin{equation}
\label{eq:cascfirst}
\begin{array}{c@{\hspace{1em}}c@{\hspace{1em}}c}
\underbrace{\frac{67}{256}}_{\frac{1}{4} \cdot 1 + 
                             \frac{3}{4}\cdot\frac{1}{64}}
&
\underbrace{\frac{3}{256}}_{\frac{3}{4}\cdot\frac{1}{64}}\
\ldots 
& 
0\ 0\ \ldots\ 0
\\
\mbox{position}\ 1 &
\mbox{positions}\ 2..64 &
\mbox{positions}\ 65..128
\end{array}
\end{equation}

Next mix $C$ is pre-determined by network topology, and the distribution
it produces on its messages is the same as~(\ref{eq:cascfirst}).
Combining two distributions, we obtain that $m$ appears in the cascade's
output buffer with following probabilities:
\begin{equation}
\label{eq:cascsecond}
\begin{array}{c@{\hspace{1em}}c@{\hspace{1em}}c}
\underbrace{\frac{5056}{65536}}_{
            \frac{67}{256}\cdot\frac{67}{256} + 
            \frac{3}{256}\cdot(63\cdot\frac{3}{256})}
&
\underbrace{\frac{960}{65536}}_{
            \frac{67}{256}\cdot\frac{3}{256} + 
            \frac{3}{256}\cdot(\frac{67}{256}+62\cdot\frac{3}{256})}\
\ldots
& 
0\ 0\ \ldots\ 0
\\
\mbox{position}\ 1 &
\mbox{positions}\ 2..64 &
\mbox{positions}\ 65..128
\end{array}
\end{equation}

Entropy of this distribution is approximately $5.9082$.  Effective
anonymity set provided by a 2x2 cascade with 25\% density of hostile
nodes and 128 messages per batch is 60 messages.


\subsection{Stratified array.}

The procedure for calculating mixing distribution for a stratified array
is essentially the same as for a cascade, but there is an additional
probabilistic choice.  After the message passes through a mix, the next
mix is selected randomly among all mixes in the next layer.

Consider a 2x2 stratified array as in fig.~\ref{fig:sa-2x2}.  Again,
assume there are 128 messages in a batch, $\frac{1}{4}$ chance that
a node is hostile, and that $A$ was selected (in a manner visible
to the adversary) as the first mix.  The mixing performed by any
single mix is exactly the same as in the cascade case, thus mixing
distribution~(\ref{eq:cascfirst}) after the first hop is the same in a
stratified array as in a cascade.  

After the first hop, however, mix $C$ is selected only with probability
$\frac{1}{2}$, while $D$ may also be selected with probability
$\frac{1}{2}$ (by contrast, in a cascade $C$ is selected with probability
$1$).  Distribution~(\ref{eq:cascsecond}) has to be adjusted to take into
account the fact that mix $D$, selected with probability $\frac{1}{2}$,
has a $\frac{1}{4}$ chance of being hostile and thus leaving each 
received message in the same position.
\[
\begin{array}{c@{\hspace{1em}}c@{\hspace{1em}}c}
\underbrace{\frac{4672}{65536}}_{
            \frac{1}{2}\cdot\frac{5056}{65536} +
            \frac{1}{2}\cdot\frac{1}{4}\cdot\frac{67}{256}}
&
\underbrace{\frac{576}{65536}}_{
            \frac{1}{2}\cdot\frac{960}{65536} +
            \frac{1}{2}\cdot\frac{1}{4}\cdot\frac{3}{256}}\
\ldots
& 
\underbrace{\frac{3}{512}}_{
            \frac{1}{2}\cdot\frac{3}{4}\cdot\frac{1}{64}}\
\ldots
\\
\mbox{position}\ 1 &
\mbox{positions}\ 2..64 &
\mbox{positions}\ 65..128
\end{array}
\]

Entropy of this distribution is approximately $6.8342$.  Effective
anonymity set provided by a 2x2 stratified array with 25\% density of
hostile nodes and 128 messages per batch is 114 messages.


\subsection{Free-route network.}

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{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
\[
\begin{array}{c@{\hspace{1em}}c@{\hspace{1em}}c}
\underbrace{\frac{35}{128}}_{\frac{1}{4} \cdot 1 + 
                             \frac{3}{4}\cdot\frac{1}{32}}
&
\underbrace{\frac{3}{128}}_{\frac{3}{4}\cdot\frac{1}{32}}\
\ldots 
& 
0\ 0\ \ldots\ 0
\\
\mbox{position}\ 1 &
\mbox{positions}\ 2..32 &
\mbox{positions}\ 33..128
\end{array}
\]

The next mix is selected from among all four mixes with equal probability.
A mix other than $A$ is selected with probability $\frac{3}{4}$, and
has $\frac{1}{4}$ chance of being hostile, producing the following
probability distribution:
\[
\begin{array}{c@{\hspace{1em}}c@{\hspace{1em}}c}
\underbrace{\frac{1216}{16384}}_{
            \begin{array}{rl}
            \frac{1}{4}\cdot( &
            \frac{35}{128}\cdot\frac{35}{128} + \\ [1ex] &
            \frac{3}{128}\cdot(31\cdot\frac{3}{128})) + \\ [1ex]
            \multicolumn{2}{l}{
            \frac{3}{4}\cdot\frac{1}{4}\cdot\frac{35}{128}}
            \end{array}}
&
\underbrace{\frac{192}{16384}}_{
            \begin{array}{rl}
            \frac{1}{4}\cdot( &
            \frac{35}{128}\cdot\frac{3}{128} + \\ [1ex] &
            \frac{3}{128}\cdot(\frac{35}{128}+30\cdot\frac{3}{128})) + \\ [1ex]
            \multicolumn{2}{l}{
            \frac{3}{4}\cdot\frac{1}{4}\cdot\frac{3}{128}}
            \end{array}}\
\ldots
& 
\underbrace{\frac{3}{512}}_{
            \begin{array}{l}
            \frac{1}{4}\cdot\frac{3}{4}\cdot\frac{1}{32}
            \end{array}}\
\ldots
\\
\mbox{position}\ 1 &
\mbox{positions}\ 2..32 &
\mbox{positions}\ 33..128
\end{array}
\]
Entropy of this distribution is approximately $6.7799$ and effective
anonymity set is 110 messages~--- slightly lower than in a stratified
2x2 array.

