Evaluate Brahms

[jannikluhn]

At Devcon last week, @tomaka suggested to look into the Brahms paper for peer discovery: http://www.cs.technion.ac.il/~shralex/Brahms-PODC.pdf

It looks really cool, they perform a pretty extensive attack analysis. One thing I don't quite grasp yet is "limited push": They assume that an attacker can push globally only with a limited frequency. I don't know how strict this is, are simple network limitations sufficient or do they require something stronger like PoW for each message?

That said, I don't think this is viable for sharding (at least on its own): It's not possible to query specifically for metadata (e.g. shard id). Querying is necessary as the size of the peer table at each node is on the order of n**(1/3) which for a network size of n = 100000 would be 50, so it does not contain nodes from all shards. It also is not immediately obvious to me if it's possible to build something like a DHT on top of this. All it does is provide a random sample of all nodes in the network, so there is no structure as in Kademlia.

So my take right now is that it would not be a good idea to abandon Kademlia in favor of this. But I really like their security analysis, so I'd be happy if someone could convince me of the contrary. What do you all think about this?

[raulk]

Just for background information. This stemmed from the Peer Discovery workshop on Oct 29th where we discussed an alternative pubsub-based approach for passive discovery that would satisfy the requirement of not disclosing validators based on their behaviour towards the network (e.g. lookups or query gossip).

The line of thinking was to have all nodes broadcast periodic messages to the network with a frequency F stating their shard membership and their multiaddrs. F would be a target delay of 1-5 minutes, with a bounded degree of +/- fuzziness per iteration (seconds).

By default, nodes gossip these ADVERTISE messages, but they do not process or store them, i.e. nodes are stateless, they do not hold a routing table at all, nor any views of the network.

A view of the network is populated on-demand: when validators need to act and lookup for nodes in a shard, they consume advertisements for a period F, tracking only the peers that are a member of the shard they're interested in.

Essentially we take a time tradeoff in exchange for anonymity. Any node can find peers in a shard in a passive fashion, without conducting queries, or displaying behaviour that would reveal they're a validator.

Of course, this is an early-stage idea, and lots of attack vectors need to be considered to analyse if an approach like this would scale in a byzantine-tolerant context. Some ideas include:

• randomly challenging nodes before relaying their advertisements.
• police roles that post BLACKLIST messages for nodes that make false claims, or that are not reachable.
• and others.

[raulk]

That said, I don't think this is viable for sharding (at least on its own): It's not possible to query specifically for metadata (e.g. shard id).

@jannikluhn – I'm still 1/3 into the paper, but I was making the same conclusion in my head.