OptiMix: Scalable and Distributed Approaches for Latency Optimization in Modern Mixnets

Mixnets, on the other hand, are deployed in various configurations, with two widely adopted topologies being the cascade and stratified designs. In the cascade topology, mixnodes are organized into predefined chains (cascades), each consisting of h mixnodes. Clients select one of these cascades for message delivery [42] , [7] , [41] , [21] . In contrast, the stratified topology arranges mixnodes into W layers (or sets), where clients form a path by selecting one mixnode from each layer [25], [13] . To generalize across both designs, OptiMix adopts a mixnet model based on the butterfly topology [9], as illustrated in Fig. 1 . The butterfly structure consists of W wings, each with depth d (i.e., the number of chains), where each chain contains h intermediary mixnodes (hops), resulting in a total of N = W • d • h mixnodes. Notably, when W = 1, the structure reduces to a cascade mixnet, and when h = 1, it becomes stratified, with each wing corresponding to a layer. This generality allows our framework to remain topologyagnostic while capturing the essential characteristics of both configurations. Similarly, the mixing process performed by mixnodes can be implemented in various ways. However, the most widely adopted scheme (which we also consider in OptiMix) is stop-and-go mixing [18], as deployed in the Nym mixnet. In this scheme, each message is delayed independently before being forwarded, with the delay drawn from an exponential distribution, Exp(λ). Problem Statement. Mixnets, regardless of their structure or internal mixing processes, provide anonymity at the cost of high end-to-end communication latency. While such latency is tolerable for applications like email or crypto-wallets, it becomes a critical barrier for latency-sensitive use cases such as instant messaging or web browsing. As a result, clients may be discouraged from adopting mixnets in these scenarios, inadvertently shrinking the anonymity set that mixnets can offer. To explore the sources of high latency, note that the overall delay experienced by a message in a mixnet arises from three main components: (1) mixing delay, denoted by ℓ Mix , which is imposed by the mixing operations, delaying messages for reordering or shuffling purposes, performed by all mixnodes along a message route; (2) propagation delay, denoted by ℓ P , which results from network link latency when messages are forwarded between consecutive mixnodes; (3) δ 0 , which accounts for additional delays due to cryptographic Abstract-Mixnets provide network-level anonymity, traded off with increased communication latency, which consequently limits their applicability to only latency-tolerant applications, shrinking the anonymity set to clients engaged in such use cases. Addressing this issue requires optimizing latency, as recently explored in LARMix (NDSS'24) and LAMP (NDSS'25) through node arrangement and strategic routing. However, these approaches are tailored to specific m ixnet d esigns, rely o n s implified mo dels and trust assumptions, or suffer from limited practical efficiency. In contrast, OptiMix bridges these gaps by introducing a general low-latency mixnet model adaptable to all well-established designs. To this end, we first propose an efficient distributed protocol for arranging nodes in mixnets that achieves low-latency properties while maintaining unbiasability against adversaries. Second, we introduce novel strategic routing schemes that optimize communication latency. Third, we design a load-balancing algorithm that evenly distributes traffic without undermining the latency-optimized characteristics of the routing strategies. Fourth, we conduct extensive evaluations using data from the deployed Nym mixnet, demonstrating substantial latency reductions with minimal anonymity loss across various mixnet designs-achieving up to 4× performance gains over state-ofthe-art solutions. Finally, considering that latency reduction incurs either anonymity degradation or increased bandwidth overhead-as stated by the anonymity trilemma-we propose a cover-routing mechanism that enables clients to benefit from lowlatency mixnets without compromising anonymity, at the modest cost of generating additional cover traffic.