Katzenpost Echomix: Quantum-Secure Mix Networks

ZKNetwork implements the Echomix protocol — a state-of-the-art mix network based on Katzenpost — providing metadata privacy with post-quantum security guarantees.

The Katzenpost Echomix architecture combines three subsystems: the Sphinx routing layer (onion-encrypted packets traversing a three-hop mix topology), Pigeonhole storage (BACAP-derived Box-IDs with k-of-n replication for asynchronous message delivery), and echo cover traffic (continuous indistinguishable loop packets). SURBs enable unlinkable reply paths without exposing sender identity. The mix topology provides sender-receiver unlinkability, input-output unlinkability, and unobservability against global passive adversaries.

Sphinx & SURBs (Routing Layer)

Every message that enters the mixnet is a constant-length Sphinx packet: an onion-encrypted header plus an encrypted payload. A sender chooses a k-hop route, wraps the packet in k layers of public-key encryption, and attaches a Single-Use Reply Block (SURB) — another onion header that encodes a return path, encrypted such that neither the recipient nor any intermediate hop can link it back to the sender.

Sphinx Packet Format

• Constant-length packets — All messages padded to identical size, preventing size-based correlation
• Onion encryption — Each hop decrypts one layer, revealing only the next destination
• SURB support — Enables unlinkable return paths for response messages

Three-Layer Topology

Layer	Purpose	Latency
Entry Mix	Initial anonymization	~100ms
Middle Mix	Traffic mixing	~200ms
Exit Mix	Delivery & timing	~100ms

Each layer operates independently with its own next-hop selection, making it impossible for adversaries to correlate traffic patterns across layers.

Pigeonhole Storage & BACAP Protocol

On top of Sphinx transport, Echomix provides Pigeonhole — a stateless courier API where clients deposit and fetch opaque data blobs through echoes. Combined with BACAP (Blinding-And-Capability) scheme, this creates cryptographic storage where only authorized parties can write or read, with unlinkable Box-IDs.

Pigeonhole Storage (Service Layer)

Each blob sits in a "Pigeonhole" identified by a pseudorandom 32-byte string, its Box-ID. Uploads, downloads, and replica-to-replica gossip are all ordinary Sphinx packets, so a global passive adversary sees nothing but cover traffic.

BACAP Vanilla (Cryptographic Core)

BACAP (Blinding-And-Capability) deterministically turns one 256-bit seed into an infinite one-way chain of storage locations and keys. Each piece of data that lands in a Pigeonhole is the signed triple: Box-ID, ciphertext, and signature — produced using Ed25519 elliptic curves.

Key Features:

• Box-ID Unlinkability — Each storage location is the product of a public point and pseudorandom scalar — computationally indistinguishable from fresh Ed25519 public keys
• Write/Read Capabilities — Separate cryptographic capabilities for creating boxes (Write) and enumerating boxes (Read)
• Consistent Hashing Replication — Each Box-ID maps to k-of-n storage replicas via consistent hashing
• Echo Traffic (Cover Traffic) — Clients emit continuous loop packets indistinguishable from application traffic

Memoryless Mixing & Exponential Delay

Each message delay is independently sampled from the exponential distribution: f(x) = λe^{-λx}. This memoryless property means that at any point in time, each message has the same probability distribution of remaining delay, regardless of how long it has already been waiting.

Mathematical Guarantees

The memoryless property provides:

• No timing correlation — Past waiting time gives no information about future delay
• Traffic analysis resistance — Statistical timing attacks become mathematically infeasible
• Decoy traffic integration — Cover traffic and real messages share identical delay distributions

Post-Quantum Security

Echomix on Katzenpost provides provable security against sophisticated adversaries:

• Built on Ed25519 — Elliptic curve cryptography with cryptographic agility for seamless upgrades
• Information-theoretic unlinkability — Resistant to quantum adversaries through mixing properties
• Cryptographic agility — Protocol designed for seamless algorithm upgrades as post-quantum standards evolve

Security Objectives

• Sender-Receiver Third-Party Unlinkability (SRTU) — Global passive adversaries cannot distinguish communication patterns. Mathematically bounded advantage ≤ 4ε + δ (negligible for 256-bit security).
• Input-Output Unlinkability (IO-U) — Even storage boxes containing inputs and outputs cannot be linked by their identifiers or timing patterns.
• Sender/Receiver Unobservability — Adversaries cannot determine whether any participant is communicating. Echo cover traffic hides application usage.
• Computation-Time Unlinkability — Latency-bucket release policy quantizes timing into public grid (e.g., 0.2s buckets). Prevents side-channel attacks.

Layer 0 Privacy for ZK Stack

Every component of the ZKNetwork stack inherits Layer 0's metadata privacy guarantees:

ZK-PKI over Mixnets

Privacy-preserving public key infrastructure routes through Katzenpost. Anonymous node identity verification without exposing which nodes you're querying or trusting.

ZK-Firewall (Access Control)

Zero-knowledge access control proofs travel via mixnet routing. Verify credentials, age, residency — without revealing identity or creating access logs.

ZK-BOM (Provenance Tracking)

Recursive Noir proofs for supply chain integrity traverse mixnets. Verify hardware authenticity, software bills of materials — without exposing your supply chain relationships.

WalletShield RPC Privacy

Blockchain interactions route through Katzenpost mixnets. MetaMask, Coinbase Wallet, and other wallets can shield transaction metadata — sender-receiver unlinkability for DeFi.

Integration with Aztec

Mix networks integrate with Aztec Protocol:

• Transactions from mixnet-routed wallets can enter Aztec's privacy pool
• Enables metadata-private DeFi operations
• ZK proofs verify the mixnet path without revealing details

---

See also: Architecture | Noir Circuits