---
# System prepended metadata

title: Analysis of failures in the mix  network

---

# 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)$

![image](https://hackmd.io/_uploads/r1WPRB2Ta.png)

- “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)$

![image](https://hackmd.io/_uploads/BkjbRShpT.png)

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

![image](https://hackmd.io/_uploads/Bkg9RH36T.png)

## 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$.