Hash map without collision check

Question

A few days ago I found a fun fact, that finding a collision of 256-bit hash using brute-force is physically impossible in solar system.

That made me think, what would happen if we used a good (uniform) 256-bit hash in a hash map. I guess, we could consider, that there are never false key hash matches, so we could get rid of the actual value of key in favor of storing only its hash.

1. Would be space efficient? (No value of key, just hash)
2. Would it be fast? (No collision check, but bigger hash than usual)
3. Would it be safe? (Statistically)
4. Has anybody done this?

Yes, there could be way fewer buckets than 2^256. The goal is to calculate the hash, find bucket and then find the actual value inside the bucket using ONLY the full 256-bit hash and without actual value check. For example in hash map where keys are strings, there could be no equality confirmation, so no actual bytes comparison and no potentially big key storage.

There seems to be a lot of disregard towards 2^256 combinations. To give you the scale, the estimated number of atoms in the known universe is between 10^78 and 10^82, roughly 2^260 and 2^270. Humankind will probably never produce all possible 256-bit numbers.

Yes, the quantum computers will be able to find collisions in split seconds. But future cryptographic safety is not the point, the point is simplification of in-memory, std-lib grade collections for internal use in applications.

Answer 1

Yes, it is possible to do this. Look up the details of ZFS for a deployed, production-quality system that uses this idea. In ZFS, any data that is to be stored is hashed with a cryptographic, 256-bit hash, and if it matches any existing data that is known to exist in the system it is assumed to be the same data, and the two blocks on disk are considered to be candidates for merging. This means that, as long as you have enough RAM (or, more realistically, fast SSD space) to keep a hashtable of a large proportion of the recently accessed blocks, you can store duplicated copies of files without needing extra space for the duplicates. The same facility is also used to provide snapshots for the system.

While it's handy for file systems, it's probably not that useful for in-memory storage, however, due to the fact that it's only really a good approach for very large objects that are expensive to access (i.e. due to disk access latency). For smaller objects with fast access, it's easier to compute a small hash and check them in detail when a hash collision occurs, because the hash functions for such an operation run much faster and the results need less memory to store than the large cryptographic hashes that are required to make ZFS reliable.

Answer 2

You are right, a hash function which such a large hash space will see very few collisions. But a hash table uses a hash function for a specific purpose: mapping hash table entries into a specific bin. This is usually done by using a modulo operation, i.e. bucket = hash(key) % n_buckets. For a power-of-two sized table, this can be done very efficiently by masking off the high bits of the hash.

So a hash table isn't so much concerned about hash collisions as it is about bucket collisions. Or viewed differently, it doesn't directly use some hash function but that hash function modulo the number of buckets.

Because of this, a hash function with a big hash space is pointless, nearly all bits will be masked off. For a hash table with 256 buckets I only need 8 bits, any more would be a waste.

How can hash tables be secure if they only have so few bits? Especially for fast (non-cryptographic) hash functions, it is possible to pre-compute collisions. If an attacker feeds these colliding elements into a hash table (e.g. query string parameters into a web application) they will be mapped to the same bucket, thus degrading the O(1) lookup of a hash table to that of a linked list: O(n). This is usually prevented by parametrizing the hash function with a per-process or even per-table salt. As the salt is unknown to the attacker, they cannot precompute any collusions.

Answer 3

With the right hashing algorithm, your idea might work, at least in some scenarios. For specialized applications, it could have a valuable performance advantage. But the quality of the hashing algorithm is crucial. Other answers and comments have mentioned software like Git and ZFS that assume equal hashes imply equal objects. They can get away with this because they do their own hashing with a known algorithm.

This is not the case for a general purpose collection. In Java, for example, every class supplies its own hashing method, and HashMap delegates hashing to the objects it stores. It's perfectly legal for a class to use a bad hashing algorithm that is likely to produce collisions. In fact, it's perfectly legal to return the same hash code for every object. The performance of hash based collections will suffer, but they will still produce correct results. Your map would not.

Answer 4

The image you reference is an example of why I firmly believe that most cryptocurrency enthusiasts really don't understand the underlying technology. One huge flaw in it's claim is that if a 256-bit quantum computer were built (something that a lot of people think can be done in the near future), such a machine could crack the crypto 'protecting' bitcoin in a matter of seconds. In other words, the main claim in the image is bogus.

The other factor that this factoid fails to mention is that it's not simply the integer space (2^256) that is relevant here, it's also how well distributed the hashes are across that space. Here's an example of a 256 bit hash function:

byte[] hash(Object... data){
   byte[] hash = new byte[32];

   for (int i = 0; i < 32; i++) hash[i] = (byte)0xFF;

   return hash;
}

Now, ask yourself, is it really 'impossible' for a 256 bit hash to collide with another? Obviously, that hash function sucks. But history has shown us that over time, the hash functions that were thought to be secure turn out not to be so. It's important to understand that it's not just that the spaces of these hash functions weren't big enough, it's that the algorithms were weak.

In theory, this scheme is possible but it can only be guaranteed to work if you are using a perfect hash function and your inputs to that function never exceed 256 bits.