Premix routing
A layer of "onion routing" at the beginning of a request, to protect against correlation attacks.
This will be difficult; the best option is probably to divide the darknet into cells, groups of say 50 nodes within which the topology is published, and choose 2 random nodes from within the cell (with each node in the cell equally likely to be picked), to tunnel through. Then your anonymity set is the cell. We cannot just choose a node and then a node connected to it, because if the first node is evil, the second node may be fake. Choosing two nodes at random from the cell prevents predecessor-probability attacks; to prevent fraction-of-a-splitfile attacks and node downtime attacks, we need the cellular structure. To prevent Sybil attacks (node pretending to be many nodes) we need a trust metric: see this blog post, a mailing list post, TrustRank, trust metrics etc; hopefully just starting with 1.0 and splitting it on each node as we go outwards would be a useful metric.
Clusters in the network would be a natural basis for cells. There are various ways to define clusters. For example:
1) n-cliques: every member can reach every other member in n hops.
2) n-clans: every member can reach every other member in n hops, all of which are also members.
3) k-plexes: each of the n members is connected to at least n-k others (a fully connected subgraph is a 1-plex).
However we define cells, a node must be able to work out which cell(s) it belongs to using only its local view of the network. It's not clear how to do this with the definitions above. In the k-plex case, what if the cell is larger than the node's local view? In the n-clique case, if a node can reach two other nodes in n hops but they aren't within n hops of each other, which does it eliminate from its cell?
Note that the above is for darknet. It's likely that we will need a completely different mechanism more like what I2P or Tor does for peer selection on opennet.
An alternative proposal is PreTunneling.
