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