Sybil Resistance for DHTs

s-kademlia proposes requiring that the hash of a node's public key should have a certain number of trailing (or leading) zeros. This is intended to make it difficult for nodes to generate many NodeIds and sybil attack the network, but, as discussed in the #3 and #7 , this isn't effective.

A static puzzle might look like:

    pub fn hard_generate(difficulty: usize) -> NodeId {
        loop {
            let new_id = NodeId::generate();
            let mut success = true;
            // default leading zeros
            for i in 0..difficulty {
                if new_id.discohash.get(i).unwrap() != &0u8 {
                    success = false;
                }
            }
            if success {
                return new_id;
            }
        }
    }

I've discussed what I don't like about this at length in the open pr(7); here are some of the main points

If we're just hashing public keys, then I can have a few machines doing that all the time to generate a set of public keys for which the respective hash maintains the requisite number of trailing zeros. Then, I can just sybil attack the network with the pre-generated set of public keys whenever I want.

Let's assume that it is provably difficult via benchmarking or hardware testing. This just means that normal nodes won't be able to generate a new NodeId in a reasonable amount of time and, if the puzzle is hard enough, it will restrict the network to the nodes that have the compute power to generate sets of keys and whoever they want to share their pre-generated keys with.

The proposed solution encourages hashing shared state that changes over time. This would require consensus, but that consensus need not be built on this DHT. If we treat the blockchain as primitive, then we can use it to limit NodeId generation -- it is possible to set rules on-chain to enforce a limited number of new members within a certain number of blocks. One method for issuing new membership could bias these decisions to existing members, see next comment (but this is not the only approach I have in mind)

I'm leaning towards using the blockchain to limit the number of nodes joining. The existing membership set might be tracked on-chain. Each member might be endowed with the ability to sponsor a quota number of new members every JoinPeriod: BlockNumber.

@troublescooter thoughts?

rust-p2p / s-kademlia

Sybil Resistance for DHTs #9