Bucketed Broadcast Routing: A Decentralized Alternative to Mixnets

Metadata-private messaging has historically meant mixnets: cascades of relays that shuffle and delay packets so an observer cannot link input to output. Mixnets work, but they impose two costs: high latency (each mix adds delay) and a trust assumption (each mix must not collude with the others). Tessera takes a different route —bucketed broadcast routing — that gives metadata-private delivery with low latency, no trusted mixes, and a much simpler protocol.

How mixnets work

A mixnet is a cascade of L mix servers. The sender wraps the payload in L layers of public-key encryption (one per mix), like layered envelopes. Each mix, in turn:

1. Collects a batch of incoming ciphertexts.
2. Decrypts its layer (peels one envelope).
3. Shuffles the batch and retransmits in a randomized order.

After L mixes, the payload emerges at the recipient. An observer who watches all links cannot link the input at mix 1 to the output at mix L, because the shuffle at each step permutes the batch and hides the correspondence.

The problems with mixnets

• Latency. Each mix waits to collect a batch before shuffling, adding delay at every hop. With L = 3 mixes and batch windows of a few seconds, end-to-end latency is seconds to tens of seconds. Real-time messaging becomes painful.
• Trust. If all mixes in a cascade collude, the anonymity set collapses to one. Mixnets need a non-collusion assumption across independent operators — an assumption that is hard to verify and has historically been broken.
• Replay / tagging attacks. A malicious mix can tag a packet (mutate a bit) and recognise it downstream, breaking the shuffle unless defences (fixed-format ciphertexts, drop-on-malformed) are enforced.
• Throughput. Each mix is a bottleneck; the cascade runs at the speed of the slowest mix.

Tessera's bucketed broadcast approach

Tessera replaces the cascade with a flat bucketed broadcastnetwork. There are no mix servers and no cascade. Every node:

1. Subscribes to a small number of buckets.
2. Broadcasts every received delivery to its peers via P2P gossip.
3. Stores deliveries in a local cache (in-memory + persistent SQLite).

A delivery is addressed not to a recipient identity but to abucket derived from a recipient fingerprint. Every node in the same bucket receives a copy; the recipient is among them but is not singled out.

Commitments and buckets

Before delivery, the sender publishes a commitment that fixes the delivery's identity without revealing it. The bucket is computed from a cryptographic fingerprint of the recipient:

fingerprint = H(Y' ‖ session_id ‖ nonce)
bucket = fingerprint mod N_buckets
commitment = H(fingerprint ‖ payload_hash)

The commitment gives the recipient something to search for: every node checks each cached delivery against the commitments it expects for its buckets.

Bloom filter matching

To avoid scanning every cached delivery against every commitment, each node maintains a Bloom filter over the fingerprints it expects in its buckets. A delivery is checked against the filter in constant time; only on a Bloom hit (with calibrated false-positive rate) does the node attempt full verification. Theanonymity_sim.py harness (experiment E2) measures the k-anonymity of the bucketing scheme and the Bloom FPR; at typical parameters the FPR is below 1%.

Gossip protocol

Nodes peer with a small set of neighbours (mesh or ring topology) and gossip every delivery they see. A delivery propagates across the network in a few hops; every node in the destination bucket ends up with a copy. There is no "last hop" that knows the recipient — every bucket member looks identical from the outside. The recipient identifies itself only byrecovering the sender's public key from the blinded pseudonym and verifying the Schnorr proof — which it does locally, without telling the network it was the intended recipient.

Advantages

Tradeoffs

Bucketed broadcast is not free. The cost is bandwidth: every delivery is replicated to every node in the recipient's bucket, and DP cover traffic pads every bucket regardless of real load. At ε=0.1 the overhead is roughly 4–6× the real traffic. Mixnets, by contrast, forward each packet once per hop. The trade is bandwidth for latency and trust:

• Mixnet: low bandwidth, high latency, trust in mixes.
• Bucketed broadcast: higher bandwidth, low latency, no trusted mixes.

For messaging workloads where bandwidth is cheap and latency matters, bucketed broadcast wins. For bulk anonymous transfer where latency is irrelevant, mixnets remain competitive.

Performance numbers

From experiments E4 and E5 (bench_throughput.py andchurn_sim.py):

• Subscribe throughput: 326 ops/s (4.5× naive baseline).
• Route throughput (~75 subscribers/bucket): 440 ops/s.
• Mesh delivery at 50% nodes offline: 100%.
• Ring delivery at 50% nodes offline: ~85%.
• Persistent SQLite single-writer: verified bottleneck mitigation; synchronous=NORMAL.

Mesh topology is more resilient than ring under churn because there are multiple paths between any two nodes; a ring breaks if a single node disappears. Tessera defaults to mesh.

Reproducing

uv run python -m tessera.network.ws_server --port 8100          # single node
uv run python -m tessera.deploy.cluster --nodes 5 --topology ring  # cluster
uv run python scripts/bench_throughput.py                            # E4
uv run python scripts/analysis/churn_sim.py --nodes 8               # E5

Takeaways

Bucketed broadcast trades bandwidth for the two things mixnets cannot easily give: low latency and no trusted mixes. Combined with(ε,δ)-DP cover traffic to hide bucket counts andper-recipient blinded pseudonyms to hide the sender, the routing layer closes the metadata side of the authentication / metadata-privacy gap without a cascade of trusted intermediaries.