I’ve been experimenting with a modified Dandelion protocol intended to increase chances of stem-phase aggregation. I called it Kademlion, because it is inspired by Kademlia, but now think that Objective-Dandelion is a better name, both as a play on Dandelion++/C++/Objective-C, and because it introduces an “objective” routing metric that nodes agree on.
I want to note that I have no clue if this is a good idea or not!
All grin nodes pick a random 256-bit node id which is broadcast to their peers. A node’s ID need only stay the same for short periods of time, on the order of a few block heights, so it could rotate frequently enough to avoid allowing node tracking and identification.
Upon receiving a block, a new epoch begins if
block_height % 10 == 0 . The epoch id is the hash of the block that started the epoch.
At the start of each epoch, every node:
- Calculates the relay weight of itself and all peers using the formula:
relay_weight = blake2b(node_id || epoch_id). Relay weight is interpreted as a 256 bit unsigned integer.
- Selects the node among itself and all peers with the highest relay weight as the relay target .
- Determines that it is in stem mode if the relay target is a peer, and in fluff mode if the relay target is itself.
Then, for every stem transaction received, each node:
- If it is in stem mode, it immediately relays it to its relay target.
- If it is in fluff mode, it aggregates transactions until its next patience timer expires, then broadcast them.
“Heavy” peers will naturally be chosen for relay targets, creating agreed-upon stem paths and fluff sinks, and leading to more opportunities for transaction aggregation.
- In a well-connected network, one node may be the sink for all transactions during a given epoch, and thus see all unaggregated transactions during the epoch. It may thus be desirable to stick to random mode selection as in Dandelion++, so as to break up stem paths with randomly selected fluff sinks.
- Since the epoch ID is known by all, a node could pick node IDs that had high relay weight during that epoch. To provent this, if a node connects to a new peer it should use a randomly assigned peer ID for the current epoch.
- I wrote a crappy aggregation and routing simulation, and the results were encouraging. Objective routing led to around 2x more aggregation in the toy network. Also, as would be expected, increasing the number of connections between nodes increased aggregation.
- Potentially, some of the benefits of dandelion are lost, since a node can to some degree predict routing between neighbors. However, since nodes cannot observe connections between other nodes, they still don’t have a complete picture.
- I had previously used an xor-based relay metric, but I think using a hash-based metric is better. Kademlia uses an xor metric, but Grin doesn’t require it, so better to use something more resistant to gaming.
Grey nodes are in stem mode, aquamarine nodes are in fluff mode. Connections between nodes are invisible, since they clutter the graph too much. Each node has one outgoing edge if it is in stem mode, showing the node that it is routing to in the current epoch.
100 nodes w/8 connections each
All transactions will be forwarded to and aggregated by one of the 7 aquamarine nodes during the current epoch.
100 nodes w/64 connections each
As you would expect, higher connectivity leads to fewer fluff-mode nodes, in this case only one.
1000 nodes w/8 outgoing connections
1000 nodes w/8 outgoing connections, alternate layout
This somewhat nicer layout shows more clearly the groups of nodes that all share the same sink during the current epoch.