Mixnets

I was forwarded a great little re-cap paper on mixnets. While I wasn’t very familiar with mixnets, the paper introduce me to many ideas to think about when working on systems attempting to preserve privacy. And those reveal some pretty large shortcomings of my simple Nostr NIP-4A proposal.

But first, what is a mixnet? The concept was introduced by David Chaum back in 1981, same guy behind ecash. Mixnets were originally focused on an email use case, attempting to make sending message more private. Cryptography is used to hide contents, but also servers in the network perform batching and re-ordering to help break timing correlations. Messages are also padded so they are all the same size.

Timing and size are two side-channel leaks not addressed at all in NIP-4A. NIP-4A is simple as hell, so it still might be helpful in its current state, but could at least learn from the shortcomings.

First up, timing. If a global adversary can see the bits between all the nostr relays, a message which moves quickly from one server to another is easier to track than if it takes some pauses in between hops. The more latency, the noise the adversary has to piece through. Sadly, adding latency is usually at odds with communication, but its important to know the leak.

Size is the other. NIP-4A uses a very simple wrapper technique so that routers are kept in the dark. But each wrapper is a very real wrapper of bytes, so as a message bounces from router to router it shrinks. For our global adversary, they have another vector of information, the connected output message is smaller than the input.

Mixnets have experimented with all sorts of strategies to try and distort these timing and size side-channel leaks. They generally involve adding latency (e.g. delaying when a packet is relayed) or noise (e.g. sending dummy packets). It’s a tough tradeoff because these are at odds with the goals of communication which are low latency and low bandwidth. There have been some advancements however which maintain privacy and don’t have quite as much of a time or size cost. I think the coolest example are sphinx packet headers which use some very nifty encryption to onion encrypt a packet’s route, but the header stays the same size across during transit. Compare that to the simple NIP-4A proposal which sheds bytes after each stop. I am totally gonna have to dig into how sphinx does that, but just taking it at face value, could it be helpful for the NIP-4A proposal?

Maybe what can help shed some light on that is our old friend, the lightning network. As described in BOLT-4, it uses sphinx headers for its routing messages! Again it feels like the lightning network is just oh so close to what I am searching for in this series. I’d like an extremely private communication channel for cooperative bitcoin transaction construction. And if you squint, that is technically what the lightning network is doing. A transaction across the network is just updating off-chain bitcoin transactions. The lightning network is designed for scalable, trust-less, low-fee payments, with privacy as secondary goal. Adding latency to this is a complete no go for the product, so there is a time leak. But lightning uses sphinx headers along with fixed packet sizes so there is no size leaks.

But there are practical requirements of the network which don’t make it a great mixnet and limits the type of transaction construction. For a lightning payment, each hop on a route is actually a lot of work. Transactions are updated at every stop, not just the endpoints. And each node is taking a small risk with its staked bitcoin. This complexity and risk puts pressure on the rest of the protocol to be very simple. Everything else needs to be optimized for predictability, reliability, and speed. Allowing any sort of general purpose communication, or even just transaction construction, is probably too big of an undefined attack surface.

OK, but the sphinx packet is cool! But it does require fixed packet sizes to hide size connections, which are not standard on nostr. Nostr has all sorts of traffic on it, which is actually great for an anonymity set, but fixed packet sizes stick out like sore thumb. Without a fixed packet size, a sphinx header may allow a NIP-4A message to not shed bytes, but it would stay the exact same size which is…worse?

There could be some other stuff to throw in though.

• Router timing delays. Allows a sender to tune if they care more about privacy or latency.
• Router batching. Maybe messages can “grow” (concatenated) if sent to the same relay?
• Split apart a message and have the router rebuild it. Allows a sender to tune if they care more about privacy or bandwidth.