DHT provider records: adopt sloppiness, rejection and backtracking from Coral

Context

Provider records in our Kad DHT implementation are equivalent to the concept of pointers as proposed in the Coral DHT [0].

Unfortunately they are implemented half-way in go-libp2p, and probably in other languages too. That makes them scale poorly.

Problem statement

Nodes close to a popular hash H get swamped with provider records. Every time a new provider appears for the same hash H, it advertises on exactly the same nodes. We currently advertise at the KValue=20 nodes closest to the hash H. Nodes that download hash H become providers in turn of that hash, therefore compounding the problem when hashes become very popular.

There is no concept of backpressure or spill over for provider records. No limits, throttling policies or validations are enforced. Peers swallow any provider record they receive. This ends up causing all kinds of local negative effects.

• https://github.com/ipfs/go-ipfs/issues/5613#issuecomment-471284697
• https://github.com/libp2p/go-libp2p-kad-dht/issues/316

Proposal

Adopt these features of Coral:

1. rejection/throttling,
2. sloppy hashing / spill over,
3. backtracking.

Rejection/throttling: nodes restrict the amount of provider records stored per hash, and the rate of registration. The limit can be locally enforced and need not be synchronised across the network. Attacks by injecting uncollaborative nodes (with low or zero local limits) are nullified by spill-over.

Sloppy hashing/spill over: on a rejection, the requester backtracks along the traversal path and tries to store the record in earlier nodes.

This has the effect of expanding the radius of advertisement of popular hashes, such that subsequent lookups for that content will result in faster resolutions.

However, depending on how lookups are implemented, this could end up overloading new providers, and weaning traffic off elder providers. I feel this is an oversight in Coral.

Backtracking: the process by which we walk back our traversal trail hitting earlier nodes along the way, attempting to register our record further from the desired target, thus expanding the radius where the hash is advertised.

Coral's approach is insecure, insofar a single adversary along the path rejecting your record will derail you and cause you to backtrack, even if closer peers to the key had spare capacity.

To resist such attacks, we can continue traversing forward a few more steps to confirm the rejection, or we can traverse disjoint paths.

Additionally it does not play well with TTLs and disappearing content. If a hash has spilled over several layers, and early registrants fail to reprovide (if they're offline or they pruned the hash), farther nodes holding recent registrations who happen to be over-capacity could preclude us from finding closer nodes that now have vacancies due to expired and unrenewed earlier records. This could result in progressive expansion of the radius, with a hollow centre.

---

See these instructional videos for reference:

• https://www.youtube.com/watch?v=2FE8PrGATo4
• https://www.youtube.com/watch?v=zWzW6o55hHw

---

[0] Freedman, Michael & Mazieres, David. (2003). Sloppy Hashing and Self-Organizing Clusters. Lecture Notes in Computer Science. 2735. 10.1007/978-3-540-45172-3_4.