The conversion from plain Key to Cid introduced an extra layer of indirection that can likely be avoided.

Currently Cid takes up the width of 5*64 bits. With it's current definition of:

type Cid struct {
    version uint64
    codec   uint64
    hash    mh.Multihash
}

May I suggest

type Cid struct {
    version uint32
    codec   uint32
    hash    mh.Multihash
}

As 32 bits should be more than enough for version and codec which I don't think will ever get very large (even 16 bits should be enough). If combined with multiformats/go-multihash#29 the size will now be 3*64 bits, which is the same size an array slice.

As the same size of a slice it becomes practical to pass it around by value which avoids an extra layer of indirection. Even though it is passed by value, the internals can still be kept hidden, as is done with many other go datatypes.

Just a suggestion. It might make a difference when you have an array of 1000's of Cids (which I might in some of my maintenance commands for the filestore, ipfs/kubo#2634).