Authenticated stratified k-buckets

[infinity0]

I propose that the kademlia implementation should provide more structure in the k-buckets so that "more trusted nodes" (as configured by the higher layer) are guaranteed available resources in the k-buckets and cannot be evicted in favour of less trusted nodes. This would help to greatly raise the cost and lower the effectiveness of an eclipse attack (paritytech/substrate#332) and indirectly and automatically avoid wasting resources storing light clients in the DHT (paritytech/substrate#3303).

Proposal is as follows, the full text is being worked on as part of w3f/research#61:

1. The kademlia implementation should offer an API for the higher-layer application to define different "authenticated roles" for peers that can potentially be inserted into k-buckets, along with the maximum fraction of the whole k-bucket that peers belonging to that role are allowed to occupy. Roles must be sortable. So for example a typical configuration might look like:

   • { role 2: 0.5, role 1: 0.3 }

   The sum of the fractions should <= 1, with the remainder being allocated to the default unauthenticated role ("role 0"). So in the above example, role 0 would be left with a fraction of 0.2.

   This should be called sporadically e.g. at the start of the process run.

2. The kademlia implementation should offer an API for the higher-layer application to define which cryptographic identities belong to which roles. This should come with an expiry time and be refreshed continually. For example a typical API call might look like:

   • { role 2: member_of { some set }, role 1: some predicate, expires: 1 hour }

When the k-bucket is not full, these configurations have no effect and the behaviour is the same as ordinary Kademlia. That is, a new node is simply added to the k-bucket, and an existing node has their timestamp refreshed.

When the k-bucket is full however, this configuration serves to affect which other node is potentially evicted in favour of the new node. In ordinary Kademlia it is the node with the oldest timestamp that is nominated for eviction - a PING is sent and if they don't reply then they are evicted in favour of the new node. In our new proposal, the node to maybe-evict is instead selected as follows:

1. from lowest to highest role (starting with the unauthenticated role 0):
   a. if the k-bucket contains more than k*fraction entries for that role, then
   i. select the oldest node in that role for eviction
2. if the above loop did not select any node, then
   a. select the oldest node in the same role as the new node for eviction

This should serve to guarantee the following security properties:

1. If resources are available (i.e. the k-bucket is not full) then everyone is added, without prejudice.

2. If resources are constrained then higher-priority roles are added with greater priority than lower-priority roles, but without starving lower-priority roles of the guarantees they are given according to the fractional resource limits configuration.

[thomaseizinger]

I think this should be done as an addition to the kad spec and not just in rust-libp2p. Closing here for now.