Substrate mixnet component

We’re working on a mixnet component for Substrate. I’m creating this topic to discuss the design of it.

The use case we’re focusing on initially is anonymous submission of transactions to the Polkadot relay chain.

The current plan (none of this is really set in stone):

  • Use the Sphinx message format.
  • Determine the set of mixnet nodes on-chain, so that there is consensus over them. For the Polkadot relay chain, use the validator set (or a subset of it).
  • Use a fully-connected mixnet node topology, possibly switching to a layered topology later if it can be shown this has better properties.
  • Mix messages at each node by delaying each one by a time sampled from an exponential distribution (see eg Loopix for an explanation of this).
  • Sample the random delays using a seed derived from the Sphinx shared secret, so they can be determined by the sender ahead of time.
  • Identify nodes in the Sphinx header using indices into the mixnet node set. At each hop, use the authority discovery component to map the index of the next hop to a libp2p peer ID (this may need changing depending on how the mixnet node set is chosen).
  • For SURBs, allow the final node to be identified in the Sphinx header by a libp2p peer ID (the node may not be in the mixnet set).
  • Automatically rotate the Diffie-Hellman keys used by Sphinx every session. Though for simplicity the initial implementation might not have automatic key rotation.
  • Have mixnet nodes generate “cover loops” to hide real traffic (see eg Loopix).
3 Likes

Is there any particular reason to use the validator set as opposed to having an alternative selection process for mixnet nodes?

When it comes to submitting transactions, the goal should be to prevent an observer from learning about how the transaction was introduced to the network. Once the transaction is being gossiped among most nodes of the network, that is success.

What can be said about guaranteeing a large enough anonymity set of transactions originating from the mixnet, so that any individual new transaction can’t be correlated with a particular mixnet user?

None. Sassafras wants nodes run by validators for its one hop, but that’s another matter, not related to the mixnet that protects users.

We’d ideally have no memepool eventually, just sassafras ticket queries, and transactions being sent directly to upcoming block producers. All these could employ a mixnet protocol, or tor protocol, even if users did not anonymize their end by adding hops.

Simplicity. The validators already form a well defined network topology that’s available on chain. W.r.t transaction delivery they are also the final destination for all messages. So for the initial release it seems like a logical choice. The additional bandwidth requirements are capped by the protocol and should be negligible.

The mixnet protocol for delivering transaction won’t be replacing the existing gossip protocol. When the user submits a transaction over the mixnet network, a few random validators will be selected as destination. Once the transaction reaches its destination, the validator would gossip it around using an existing protocol.

So here’s how I see it:

  1. Mixnet protocol for transaction delivery will be enabled by default on all validators and full nodes. Potentially for light clients as well.
  2. All nodes with the mixnet protocol enabled will send cover traffic. So even if the transaction volume (real traffic) is low, it won’t be possible to determine the origin as long as the number of nodes is high enough. Any full node can potentially be the originator of any transaction from the POV of an external observer.
  3. The traffic rate (cover + real) will be fixed to a low enough value, so that it does not create considerable strain on the validators.
  4. Users will have to opt-in sending individual transactions over the mixnet, at least with the initial rollout on polkadot. Most polkadot users don’t really care about network level anonymity and I expect 90% of transactions to be submitted over the regular gossip protocol. This will allow us to keep the mixnet bandwidth low, at least initially.