I wonder if storing the hashing parameters next to the hash is the right approach to take for systems. Your system isn't going to support all hashes (adds a lot of library bloat, you don't want to support weak hashes), so you'll probably want one specific algorithm/parameter set, with room for upgrades in case weaknesses get discovered (not likely to occur often). A single byte/varint, starting at 0 and incrementing for every new parameter set sounds reasonable. A downside would be interoperability, but if that's your main concern then perhaps a human-readable string representation of the hash algorithm/parameters would be preferable.

What are the benefits of using Multihash?