# Analysis of failures in the mix network

## Assumptions

- To construct the mixnet we sample $n$ nodes (without replacement) from the population of $N$ nodes.
- At most $M$ , where $M<N$, nodes in the population are adversarial.
- The number of adversarial nodes $m$ in the mixnet is random number from the hypergeometric probability distribution $P\left(m\vert N,n,M\right)=\frac{{n\choose m}{N-n\choose M-m}}{{N\choose M}}$
- We have $L$ layers constructed from $n=\sum_{\mu=1}^L n_\mu$ nodes, where $n_\mu$ is the number of nodes in the layer $\mu$.
- The probability that the number of adversarial nodes in layer 1 is $m_1$, in layer 2 is $m_2$, etc., is given by the multivariate hypergeometric distribution $P\left(m_{1},\ldots, m_{L}\vert n_{1},\ldots,n_{L}; m\right)=\frac{\delta_{m;\sum_{\mu=1}^L m_{\mu}}\prod_{\mu=1}^L {n_\mu\choose m_\mu}}{{n\choose m}}$
- From above follows the joint probability distribution $P\left(m_{1},\ldots, m_{L}\vert n_{1},\ldots,n_{L}\right)=\sum_{m=0}^nP\left(m_{1},\ldots, m_{L}\vert n_{1},\ldots,n_{L}; m\right)P\left(m\vert N,n,M\right)$

## Failures

- “Anonymity failure” occurs in the mix network when at least one adversarial node is present in each layer thus allowing to form a path of compromised nodes.
- The probability of anonymity failure is given by $P\left(m_{1}\geq1,\ldots, m_{L}\geq1\vert n_{1},\ldots,n_{L}\right)$


- “Communication failure” occurs in the mix network when the number of adversarial nodes is greater than some fraction $A$ of nodes in at least one layer. A layer with all (or a large number) of adversarial (or honest but with limited resources) nodes could prevent (or considerably slow down) communication between users.
- The probability of communication failure is given by $P\left(\cup_{\mu=1}^L\{m_\mu\geq \lfloor An_\mu\rfloor\}\right)=1\!-\!P\left(m_1\!<\! \lfloor An_1\rfloor,\ldots,m_L\!<\! \lfloor An_L\rfloor\right)$


- In the mix network of a fixed width the probability of anonymity failure and communication failure is, respectively, decreasing and increasing as the number of layers $L$ is increasing.


## Fraction of compromised paths

- The fraction of compromised paths in the mix network of $n=\sum_{\mu=1}^L n_\mu$ nodes distributed into $L$ layers, where $n_\mu$ is the number of nodes in layer $\mu$, is given by $\alpha= \prod_{\mu=1}^L \frac{m_\mu}{n_\mu}$,
where $m_\mu$ is the number of adversarial nodes in layer $\mu$ and $m=\sum_{\mu=1}^L m_\mu$.