Adversarial examples for fast hash functions
8 points by pkhuong
8 points by pkhuong
I have come around to a strong belief that the correct design direction for hash tables is perhaps a bit surprising: require an ordering in addition to a hash, and fall back to a b-tree when excessive collisions occur. Then use the weakest, cheapest, fastest hash you can get away with.
And we should have an UnsafeHashMap or some such which omits the ordering requirement.
All of the efforts to resist adversarial attacks against the scaling of hash tables seem to either fail to provide a durable defense or are too costly in practice. And we pay the price of these when we don't have adversarial keys. =/
The only way that seems to durably preserve fast hash table performance is to fall back on an ordered container.
What price level is too costly? But also, hashing is used in more data structures than hash tables.
If we're aiming for almost-universality like Ahle does, we have a few very reasonable classic solutions for small GPR-sized values https://arxiv.org/abs/1504.06804 (and universality with independent random keys composes fine on structs/products/bounded vectors).
For longer strings (input >>> random key), the article has a nice Pareto front of throughput/proven collision bounds.
That doesn't help with data structures that need k-universality. Schemes like Twisted tabulation hashing are close to practical, but not quite there imo (unless hashing is the main thing the program does, e.g., for a statistical sketching server). Four rounds of AES though, that's Probably Good Enough (and definitely almost-XOR-universal, so just pipes short inputs straight through)?