Owner:  @Alexander Mozeika

Reviewer: 🟢@Marvin Jones 🟢@Álvaro Castro-Castilla

Introduction

We consider queuing system of a mix node where coin-flipping algorithm is used to remove messages. We show that the amount of time message spends in a queue is governed by the Geometric distribution. The consequence of the latter is memorylessness property, i.e. the amount of time a message will spend in the queue is independent on how long it is already been in the queue, which is important for anonymity of communication.

Overview

This document analyses how a mix node—a privacy tool that hides message origins—manages delays using randomised queues. Key points:

1. Queue Design:
   • Each connection has an in-queue (FIFO order) and out-queue with randomised removal.
   • A "Relayer" forwards real messages to all out-queues except the sender’s, dropping dummies.
2. Randomised Delays:
   • Messages in the out-queue are shuffled, then each has probability $q$ (e.g., 50%) of being sent per round.
   • This follows a Geometric distribution: ~50% sent in Round 1, ~25% in Round 2, etc.
3. Anonymity Guarantee:
   • The system’s memorylessness ensures delays are independent of past wait times, preventing timing attacks.

Methods used:

• Geometric distribution models rounds until a message is sent.
• Simulations (e.g., sending 10,000 messages) validate the theory.
• Binomial distribution tracks messages removed per round.

Why It Matters:

• Balances privacy (unpredictable delays) with efficiency (tunable via $q$).
• Foundations for Tor-like systems and anonymous networks.

Analysis

Assumptions

We assume that node $i$ has $c_i$ connections to other nodes, labelled by the set $[c_i]$, and two queues (”in-queue” and “out-queue”), associated with each connection (see Node internals). Messages which arrive via the connection $\ell\in [c_i]$ are stored in the in-queue $Q_\ell^{in}$. Messages which are sent via the connection $\ell\in [c_i]$ are stored in the out-queue $Q_\ell^{out}$. Messages are added to the back and removed from the front of $Q_\ell^{in}$, i.e. the latter is the FIFO queue

Representation of a FIFO (first in, first out) queue.