Premix Routing is a layer of "onion routing" at the beginning of a request, to protect against correlation attacks.
This will be difficult to implement, 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.
To prevent Sybil attacks (a node pretending to be many nodes) we need a trust metric.
See here for more:
Hopefully just starting with 1.0 and splitting it on each node as we go outwards would be a useful metric.
- n-cliques: every member can reach every other member in n hops.
- n-clans: every member can reach every other member in n hops, all of which are also members.
- 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?