Bucketed Broadcast Routing

The routing problem

In a metadata-private system the network must deliver a message to a recipient without learning who the recipient is. Any per-message routing decision — “send this proof to node R” — is itself metadata an adversary can observe. The core design question is: how do you route without routing decisions?

The mixnet approach

Mixnets (Chaum 1981; Vuvuzela, Nym) answer this by sending each message through a cascade of mix servers that re-encrypt and permute batches, breaking the link between a message that enters the cascade and the one that leaves. The anonymity set is the batch size of the cascade. The cost is latency (round-based batching waits for a batch to fill) and a trust assumption: at least one mix in the cascade must be honest. If all mixes collude, the anonymity collapses.

Tessera’s approach: bucketed broadcast

Tessera avoids per-message routing entirely. Every proof is broadcast to a small number of buckets; every recipient subscribes to the bucket it expects its deliveries to land in. The relay network simply forwards proofs by bucket — it never learns, for a given proof, which subscriber will claim it. The anonymity set for a delivery is the occupancy of its bucket.

The routing fields are derived deterministically from a per-delivery commitment:

commit       = H(Y′ ‖ ephemeral_key ‖ session_id)
bucket       = int(SHA256(commit)[:2]) mod 64
fingerprint = SHA256(commit ‖ window_start)[:8]

• commit is fresh per delivery — it binds the blinded pseudonym, the ephemeral delivery key, and the session id.
• bucket is the first byte of SHA256(commit) mod 64 — a deterministic mapping into 64 buckets.
• fingerprint is an 8-byte Bloom key the recipient uses to match incoming proofs against its subscription filter.

Commitment, bucket, and fingerprint

Because commit is a hash of the blinded pseudonym and a fresh ephemeral key and session id, it is uniformly distributed and unpredictable to anyone who cannot decrypt the envelope — including the relays. The bucket assignment is therefore pseudorandom: deliveries to a given recipient are spread across the 64 buckets according to the hash, and the recipient must subscribe to its expected buckets for the current time window.

The window_start is the start of the current time window; including it in the fingerprint means a fingerprint is only valid for one window, which bounds replay and keeps the Bloom filters fresh.

Bloom-filter subscription

Each recipient registers a Bloom filter against each relay, encoding the set of fingerprints it expects to receive in the current window. The relay tests every incoming proof’s fingerprint against every registered filter and forwards matches. Bloom filters have a small false-positive rate (tunable; Tessera targets <1%), which means a relay occasionally forwards a proof that the recipient did not actually request — this is harmless (the recipient simply discards it) and adds a small amount of cover noise.

The Bloom filter never reveals which fingerprints the recipient is waiting for, only a probabilistic membership structure — so the relay cannot trivially learn the recipient’s contact list. Combined with DP cover traffic on the broadcast side, the subscription layer is also padded.

Gossip over a WebSocket P2P mesh

Relays are peers: each relay gossips proofs it has seen to its neighbours over a persistent WebSocket connection. Tessera supports two topologies:

• Mesh — every relay talks to every other. Higher bandwidth, maximum resilience to churn.
• Ring — each relay talks to two neighbours. Lower bandwidth, simpler, but less resilient to partitions.

Gossip is idempotent: each relay deduplicates by commitment, so a proof is forwarded at most once per relay per window. The combination of deterministic bucketing and P2P gossip means a proof will reach any recipient that is subscribed to the right bucket on any reachable relay.

DP cover traffic fills the buckets

Broadcast alone is not private: an adversary counting proofs per bucket sees the real delivery pattern. Tessera pads each bucket with dummy proofs drawn from the (ε,δ)-differentially-private shifted-Laplace mechanism (see DP for Messaging). The dummies are indistinguishable from real proofs on the wire — they have valid-looking commitments, fingerprints, and ciphertexts — so the per-bucket count is (ε,δ)-DP in the real load.

Advantages over mixnets

• Lower latency. No cascade: a proof reaches its bucket in one gossip hop, not k sequential mixes.
• Simpler implementation. A relay is a peer with a WebSocket listener and a SQLite store — no re-encryption cascade, no threshold mix crypto.
• No trusted mix servers. Any peer can relay; there is no per-cascade honesty assumption. Security comes from DP cover traffic and bucket occupancy, not from a cascade.

Tradeoffs

Bucketed broadcast pays for its simplicity with bandwidth: every proof is sent to an entire bucket (all subscribers in that bucket receive it), not to a single recipient. The anonymity set is therefore thebucket occupancy, not the whole network. Spreading deliveries across 64 buckets keeps any single bucket from becoming a_singleton (which would collapse the anonymity set), and DP cover traffic guarantees a minimum bucket load regardless of real traffic.

Performance

Measured on the Tessera benchmark harnesses:

• Routing throughput: ~440 ops/s per relay with ~75 subscribers per bucket.
• Subscribe throughput: ~326 ops/s (4.5× the naive baseline).
• Delivery under churn: 100% message delivery at 50% node-offline churn in a mesh topology; ring degrades more under the same churn.

The single-writer SQLite design (one persistent connection with a lock,synchronous=NORMAL) is the verified bottleneck mitigation for the persistent path — see the research notes for the throughput analysis.

Comparison: Tessera vs mixnet vs Tor

Tessera trades bandwidth for lower latency and a simpler trust model. For one-to-one authenticated delivery — where the recipient is known in advance and can subscribe — bucketed broadcast is the simpler, faster choice.

Frequently asked questions