# Achieving Sender Anonymity in Tor against the Global Passive Adversary
## 5 Introducing Fault Tolerance into the System  
Even though fault tolerance is one of the aspects that is typically missed in anonymous communication networks, we sketch in this section how a certain degree of fault tolerance can be easily introduced in a system based on our protocol. To confirm the above claim, consider the current Tor itself has no fault tolerance at all. Indeed, if a Tor router stops working during a communication, the communication is lost, and there is no a protocol to recover the communication on the fly (indeed, to set a backup Tor circuit is not enough to obtain this goal). As we focus on the part of the proposal that plays the role of _add-on_, with respect to the existing Tor system, we do not consider in this section the Tor communication occurring outside the system, between the proxy node and the destination. Apart from the fact that the fault tolerance of Tor can be considered as an orthogonal problem, it is also true that Tor routers can be considered more stable than standard client nodes involved in the rings. The basic change we have to introduce to obtain fault tolerance is the notion of a _ring layer_. The ring manager, instead of building simply rings of \(k\) nodes, builds rings of \(k\) layers, each composed of \(j\) nodes. We can figure out that the value of \(j\), for good fault  
Figure 6: Process of emptying the tokens and destroying the Tor circuit. Figure 7: Communication phase. tolerance, should be very low (for example, 2 or 3), if we are in a network with a high level of activity. Anyway, higher values of \(j\) do not result in infeasible computation, as we will see next. The nodes of each layer know each other in the sense that they are aware of the reciprocal addresses. With the notation \(r_{1},\ldots r_{k}\), used earlier for the rings, now we indicate a sequence of layers, such that \(r_{i}=\{x_{1}^{i},\ldots x_{j}^{i}\}\) is a set of \(j\) nodes. Besides the individual public keys of the nodes, there is also a public key per layer, called the _public layer key_. This impacts both the set-up phase and the communication phase. Concerning the set-up phase, some changes occur for the key exchange task. Forward keys are exchanged for each pair \(x_{p}^{i},x_{q}^{i,p_{k}k+1}\), \((1\leq p,q\leq j)\). Thus, we have \(j^{2}\) forward key exchanges per pair of consecutive layers. Instead, by leveraging public layer keys, the pair of keys used as sender key and proxy key \(k_{st}\) and \(k_{ts}\) will be established between layers instead of individual nodes. To do this, the ring manager selects one _representative_ node alive per layer and informs each selected node about the other selected nodes (and then about their public keys). Then, the Diffie-Hellman process described in Section 4 happens among these representative nodes. At the end of this process, any representative node has a pair of sender key and proxy key between its layer and any other layer. These keys are exchanged with all the other nodes in the layer. Indeed, in the pre-set-up phase, the nodes of the same layer exchange a symmetric key per pair, by enacting the \(j(j-1)\) Diffie-Hellman processes. Concerning both the circulation of tokens and the communication task, the only change is that the function \(next\), associating to each node of the ring the next node to forward a message, becomes non-deterministic. Specifically, a node in layer \(s\) which has to forward a message, just has to choose one alive node in the layer \(next(s)\) and forwards the message to it. For the proxy node, essentially no change is required, because the encryption is done for the layer, so that any node in the layer is able to decrypt the message and then initiate the Tor circuit. Similar considerations can be made for the response. To conclude this section, we evaluate our fault-tolerance mechanism from a probabilistic perspective, to allow the correct setting of the parameter \(j\), once a given reliability probability is fixed. We denote by \(p\) the probability that, at a given instant, a node is alive.