Here's what I discussed with @Stebalien:

Let's call the permanent ID <private id> and the ephemeral ID <public id>.

We want the DHT to store the <private id> -> <public id> mapping, while also making it difficult for an adversary to follow a given <private id> around the network.

• Option 1: Using <public id> as our node ID, call Put(Hash(<private id>), <public id>)

This makes it easy to find a <public id>, and hence public PeerInfo, given a <private id>. As an extension, we could also sign <public id> with itself, allowing DHT nodes to easily verify these records are valid, which would be nice. The main downside of this design is that any attacker running a DHT node that sees Hash(<private id>) on the wire, in a Put or Get RPC, can later issue Get(Hash(<private id>)) to find that peer's <public id> as it changes.

To avoid this, we have:

• Option 2: Using <public id> as our node ID, call Put(Hash(<private id>), Encrypt(DeriveSymmetricKey(<private id>), <public id>)))

This has the advantage that seeing messages that contain Hash(<private id>) don't let us follow that <private id> around the network, since we don't know the actual <private id> to decrypt the <public id>. The main downside relative to option 1 is that it is no longer possible for nodes that don't know the actual <private id> to validate these records.

Finally, both of these approaches still have the issue that a Sybil DHT node that receives the Put message could just look at the physical address (e.g. ip and port) that sent that Put, revealing where the <private id> is located. Only a relay network like TOR or something equivalent can fix this issue.

Ref. libp2p/specs#139
Tor rend spec v3 allows anonymous service discovery by encrypting <private id> before publishing to the DHT