\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.