HAMTs and non-cryptographic hash functions

[Stebalien]

Context: https://github.com/ipld/specs/pull/109#discussion_r271081859. I'm putting this here as I'm seeing optimization work on HAMTs and I don't want this to get lost (or us to waste a bunch of time by, e.g., trying to choose a faster hash function when we have to use sha256 anyways).

Using non-cryptographic hash functions (e.g., murmur3) in a HAMT is fine in some cases but please be careful. I've brought this up before but I want to make sure this doesn't fall through the cracks.

Specifically, if (a) multiple mutually distrusting parties can update the same HAMT and (b) these parties can can chose their keys, an attacker can choose a set of keys such that a target key can't be inserted into the HAMT. They can do this by finding BUCKET_SIZE keys that collide with the target key and filling up that HAMT bucket.

This may not be an issue if end-users can't chose their keys, the non-chosen keys are uniformly random, and the non-cryptographic hash function has a uniformly random output given a uniformly random input. The non-cryptographic hash applied by the HAMT should effectively be a no-op. is effectively a no-op. But I'm not sure if murmur3 has this property. I'm also not sure if this is correct as this statement requires a proof.

If possible, please just use sha256 in HAMTs.

[Stebalien]

cc @anorth, @acruikshank, @hannahhoward

(and @whyrusleeping)

[whyrusleeping]

Thanks for bringing this up. Users have a choice over the keys as they can generate their own cryptographic keypairs, and the hash of the public keys end up being the HAMT key. Users can grind keys until they find collisions.