Forks off #111 to focus on the backwards compatibility issue instead of the CID/PID design space.

Summary

Peer ID calculation has changed a couple of times over the past year.

1. Initially, peer IDs were always sha2-256 multihashes of the public key.
2. From go-ipfs 0.4.16-0.4.18, we used the identity multihash to "inline" small keys (specifically, ed25519 keys) into the peer ID under the assumption that nobody was using them.
3. We reverted (2) in 0.4.19 dev as OpenBazaar was using ed25519 keys before 0.4.16.
4. We are now planning on re-introducing (2) as:
   a. Textile is also using ed25519 keys and is relying on 0.4.18 behavior.
   b. OpenBazaar is using a forked go-ipfs network. We are adding a package-level flag so they can restore pre-0.4.16 behavior in their forked build.
5. Finally, we need to agree on a migration path such that all IPFS nodes use the same method to calculate peer IDs.

PR: libp2p/go-libp2p-peer#42

Goals

This all grew out of several requirements and wants:

Requirements

• We need to provide a way to for users to select a hash function other than sha256 when computing their peer ID.
• Given a public key, peer ID calculation must be deterministic.
• There must be a case-insensitive way to express peer IDs appearing in IPNS paths (for browsers). Currently, peer IDs are always base58 encoded which is not case-insensitive.

Wants

• We'd like a way to "inline" public keys into peer IDs (if the public key is small enough to fit comfortably). This will allow encrypting a message to a peer without needing to look up their key first.
• We'd like to be able to fetch keys with bitswap.

Definitions

1. Inlining peer ID (working title...): A peer ID from which the associated
   public key can be extracted.
2. sha256 peer ID: A peer ID created using the sha256 hash function.

Note: "inlining" peer IDs look like 1..., sha256 peer IDs look like Qm....

Events

Below is an exhaustive history of this issue:

1. In the beginning, peer IDs were sha256 multihashes of peer IDs.
2. At some point, we added support for ed25519 keys in go-libp2p. The plan was
   to embed them in peer IDs
   (implement ed25519 support go-libp2p-crypto#5). However, we punted on
   that. We never added support to go-ipfs
   (Allow option to use ed25519 ipfs/kubo#3625).
3. OpenBazaar started using ed25519 keys anyways.
4. We (go) added a separate function for calculating inlining peer IDs (in
   libp2p/go-libp2p-peer#15) that embedded ed25519 keys. Unfortunately, that
   wasn't usable because everyone needs to compute the same peer ID.
5. In libp2p/go-libp2p-peer#30, we removed this separate function and
   switched to automatically embedding keys shorter than 42 bytes into peer IDs.
   This way, everyone would deterministically calculate the same peer ID. We did
   this by using the "identity" hash function instead of sha256.
6. Textile started using go-libp2p and go-ipfs (using ed25519 keys).
7. OpenBazaar tried to rebase onto go-ipfs 0.4.18 and discovered that peer ID
   calculation had changed.
8. After discussing the issue in libp2p/specs#111 and on a
   call, we decided to revert 5. We were under the
   impression that nobody else was using ed25519 keys given that go-ipfs doesn't
   provide a way to generate ed25519 keys.
9. Textile reached out to @whyrusleeping about a weird bug they were seeing when
   trying to connect two nodes. @whyrusleeping tried reproducing it got the
   error dial attempt failed: <peer.ID Qm*yNGz7a> --> <peer.ID 12*FrJvar> dial
   attempt failed: connected to wrong peer". This is the inverse of the issue
   OpenBazaar was having.
10. At the moment, it doesn't actually look like this is the issue Textile was
    having, they're seeing timeouts: dial attempt failed: <peer.ID 12*xWYT4W> --> <peer.ID 12*YsNMRE> dial attempt failed: context deadline exceeded and
    dial attempt failed: <peer.ID 12*xWYT4W> --> <peer.ID 12*YsNMRE> dial attempt failed: dial tcp4 13.57.23.210:4001: i/o timeout. The latter looks
    like it comes from add a TCP connect timeout go-tcp-transport#24.

This issue covers the peer ID issue, not the timeout issues.

Current State

1. Most of the (go) network is using the inlining from libp2p/go-libp2p-peer#30.
2. The latest go-ipfs and go-libp2p masters are not inlining keys into peer IDs. They are now (again) inlining keys.
3. OpenBazaar is using a forked (separate) network so, for now at least, they
   don't actually need to interoperate with the rest of the network.
4. Textile is not using a forked network so they do need to interoperate. Textile is using peer IDs for identity but these could (potentially) be migrated. They are not using IPNS.
5. IPLD-DID (decentralized identity) is using the new inlined keys for IPNS. However, it's unclear if they have many/any users who would be affected.

Affected Subsystems

This covers the affected subsystems and some hacky fixes that I don't recommend.
They're only there to illustrate the issue.

Outbound Connection

When establishing an outbound connection, go-libp2p will:

1. Perform a secio handshake.
2. Derive the remote peer's ID from their public key.
3. Check if this derived peer ID is the target peer ID.

Textile is seeing this fail after updating go-libp2p because they're passing a
peer ID created using the identity hash function into go-libp2p while
go-libp2p-peer is calculating it using the sha256 multihash.

Example Fix: This could be fixed by a hack to convert a peer ID created using
the identity hash function to a sha256 one.

Inbound Connection

When receiving an inbound connection, we compute the peer's ID from their public key. That means:

1. If we're running a 0.4.18 go-ipfs node, we'll compute inlining peer IDs for ed25519 keys.
2. If we're running a 0.4.19-dev go-ipfs node, we'll compute sha256 peer IDs for ed25519 keys.

Example Fix: In practice, this "just works". That is, we use our version of the
peer's ID internally and don't really care what the other side thinks it's ID
is.

DHT

The DHT is the first place where we really care about calculating the same peer
IDs. If we don't, FindPeer breaks.

Let's say there's some peer A that wants to connect to a peer B. Let's assume
that peer A and B have this peer ID inlining enabled but the rest of the network
doesn't.

When peer A tries to connect to peer B, it'll walk the DHT looking asking nodes if they either:

1. Know of nodes closer to peer B.
2. Know how to connect to peer B. Currently (in go-ipfs), only nodes that are
   actually connected to peer B will respond.

In this case,

1. Peer A will be able to walk the DHT all the way to a node directly connected
   to peer B. That is, (1) will work.
2. That node will know peer B by a different name (ID) so it won't be able to do part (2).

Example Fix: So, if we have an inlining peer ID, we can extract the key and
compute the sha256 peer ID and try to look that up in the DHT. Unfortunately,
we can't go the other way. This fix would also be really hacky.

IPNS

I don't believe IPNS is affected but I haven't thought through it thoroughly. At
worst, we'd have to apply a fix similar to the outbound connection fix.

PubSub

Same as IPNS.

Multibase

Unfortunately, this whole issue also relates to the ask from IPFS In Web
Browsers to make IPNS (and peer IDs) use multibase. If we just have Qm...
IDs, we can avoid allocating Q as a multibase prefix and we'll be fine.
However, inlining peer IDs start with 12 and 1 is already a valid (albeit
useless) multibase prefix for unary.

The real worry is that if we allow arbitrary mulithash functions, we need to
tackle the multibase issue before we start running into collisions. That is,
hash codes such that Base58Encode([hash code]) maps to some useful multibase
prefix.