Proposal

1. Use an updated Record interface that supports:
   a. Merge(rec1, rec2) so that we can support record types that are mergeable (e.g. provider records) and not just sortable (e.g. IPNS records)
   b. Verify(key, rec) which we already have
   c. We could optionally make both of these functions take some external "state" if we wanted to insist that the above were pure functions, which is not the case with the existing Record interface
2. Pass record validators into the DHT with a few extra properties for efficiency (especially helpful given the below changes):
   a. CustomKadID(key string) kad.ID, so that if it makes sense that /a/QmABC would be near QmABC in Kad space that we can represent that
   b. RecordID int we should allow representing record namespaces on the wire using a (var)int instead of a string to save some bytes. There's no reason to expect contention over the slots since they should be defined per DHT prefix (e.g. /ipfs), and that spec would be where the standardization of the record IDs happen
3. Rework some of the record processing internals to handle "merged" records instead of just "best" records (there's likely to be some coding complexity here that will fine tune exactly what information we need from a validator)
4. Remove the ADD_PROVIDER and GET_PROVIDERS Message Types and instead perform those operations via the /provider namespace of PUT/GET VALUE
5. Use the /p2p namespace of PUT/GET VALUE for finding and advertising peers. Use a CustomKadID for peer records that puts /p2p/QmABC near SHA256(QmABC) (this will make it behave similarly to how it does today)

Background

We currently have a few message types that do approximately the same thing:

Generic Puts + Gets

PutValue(key, value): puts an arbitrary piece of data that must follow the rules defined by the key's prefix
Get/SearchValue(key): gets an arbitrary piece of data returning the "best" version of the data found using the rules defined by the key's prefix

Message Types Used: FIND_NODE and PUT_VALUE for PutValue and GET_VALUE for Get/SearchValue

What can you do with the records? The Record interface allows for user defined types that verify and order records (e.g. the /ipns prefix is associated with a particular record format, a way to verify that an IPNS record is valid and a way to determine which of two records is better).

Provider Records

Provide(cid): Puts a provider record (a piece of data signifying that a peer cares about some information)
FindProviders(cid): Gets a set of provider record corresponding to the cid (or really multihash #422 )

Message Types Used: FIND_NODE and ADD_PROVIDER for Provide and GET_PROVIDERS for FindProviders

What can you do with the records? Everything here is implicit, we learn about peer's the have expressed interest in some topic (e.g. having the data identified by a multihash) and then decide what to do about it (e.g. connect to them and start using some other protocol). Despite provider records not being signed we'd still like the network to only advertise that someone is interested in being contacted if they have expressed interest, therefore DHT servers only accept provider records coming directly from the source (as can be verified by their crypto handshake).

Peer Records

This one is a little funky and still needs a specification libp2p/go-libp2p#784. The main reason it's strange is because there are a number of optimizations that can be done for peers that are members of the DHT (whether clients or servers) that cannot be performed for others.

FindPeer(peerID): Get a peer's multiaddresses from the DHT
PutPeer(peerID): This function does not exist, but rather is implicitly done by forming connections to other peers

Message Types Used: FIND_NODE and implicitly the Identify protocol

What can you do with the records? These operate similarly to provider records, you find out about the addresses for a peer that you have an interest in. Like provider records servers are supposed to ensure that only real addresses that they have received from the peers are conveyed in queries.

Why Now?

Well a few of the "quirks" of our DHT message types have finally caught up with us. In particular, we want to:

1. Make peer records signed (means breaking the message format) Signed Peer records for the DHT #558 - which helps us
   a. Dial peers more reliably, especially peers that are not DHT servers, but are advertising their addresses in the DHT
   b. Trust DHT servers a little less (attack omitted, but you can guess 😁)
   c. Enable third parties to advertise peer records in the DHT
   d. Give less trust to third parties that fetch peer records from the DHT
2. Make provider records signed (and actual records) Signed Provider records for the DHT #559 - which helps us
   a. Find content more reliably, since we can prioritize which providers to utilize first
   b. Enable third parties to advertise provider records in the DHT
   c. Give less trust to third parties that fetch provider records from the DHT
   d. Enable record rebalancing Correctly Implement Kademlia Rebalancing #354 (more important for provider records then peer records, but useful there too)
   e. Having an actual record format will also enable embedding extra information in the record going forward (e.g. in the case of IPFS, do I have all of a DAG under some CID or just some of it)
   f. Trust DHT servers a little less
3. Allow refreshing our routing tables beyond 15 buckets Fix Routing Table Refresh after we have a SearchByKadId RPC #556
4. We want to remove the IPFS-ness from this libp2p component IpfsDHT -> KadDHT #568

Given that 1,2 and 3 will require rewriting our message types anyway this seems like an opportune time to tackle this as well. As an added bonus this will give us an opportunity to take another stab at what the ContentRouting and PeerRouting interfaces could look like in a very low stakes environment (since we'll end up wrapping the DHT in something that exports the existing Routing interface)

@jacobheun @Stebalien @aarshkshah1992