13 ms·

SeaHash: A fast, portable hash function in Rust

186 points by pcwalton 10y ago

jedisct1 10y ago
Great. But keep in mind that this is not a keyed hash function.
- dsp1234 10y ago
  This is mentioned in the documentation: "Warning! This is not a cryptographic function, and it certainly should not be used as one. If you want a good cryptograhic hash function, you should use SHA-3 (Keccak) or BLAKE2."
  - Dylan16807 10y ago
    That's not the same thing. You don't usually key for crypto reasons, and a good cryptographic hash does not imply keying.
- pcwalton 10y ago
  You can use it as a keyed hash function by adjusting the IV. See: https://docs.rs/seahash/2.0.0/src/seahash/.cargo/registry/src/github.com-1ecc6299db9ec823/seahash-2.0.0/src/reference.rs.html#94 https://docs.rs/seahash/2.0.0/src/seahash/.cargo/registry/sr...
  - tveita 10y ago
    It seems to already be implemented in https://docs.rs/seahash/2.1.1/src/seahash/.cargo/registry/src/github.com-1ecc6299db9ec823/seahash-2.1.1/src/buffer.rs.html#102 https://docs.rs/seahash/2.1.1/src/seahash/.cargo/registry/sr... But it only seeds one of the lanes, so you can still make collisions trivially in one of the other lanes. I guess it could still be useful for namespacing.
eridius 10y ago
Very cool! BTW, the hyperlink for "reference" in the "Specification" section is broken.
sp332 10y ago
I was trying to figure out how this is so much faster than FNV https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function#FNV-1_hash https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo... Is it only because of the parallelism? Or are the operations really that much cheaper somehow?
- mastax 10y ago
  Presumably because SeaHash operates on 8-byte blocks while FNV acts on single bytes.
- LeifCarrotson 10y ago
  Both. The pseudocode for FNV looks like this: hash = FNV_offset_value for each byte_of_data to be hashed { hash = hash XOR byte_of_data hash = hash × FNV_prime } return hash The pseudocode for seahash looks like this (with '×' as the wrapping multplier operator, and some simplification for padding if the data length in bytes is not a multiple of 8 bytes per word × 4 words in the hash state): hash = {offset_1, offset_2, offset_3, offset_4} for (int data_index = 0; data_index < data.length_in_64_bit_words; data_index = data_index + 4_words_in_hash) { for (int hash_index = 0; hash_index < 4; hash_index++) { // Mix in data hash[hash_index] = hash[hash_index] XOR data[data_index + hash_index] // Diffuse hash[hash_index] = hash[hash_index] XOR (hash[hash_index] RSHIFT 32) hash[hash_index] = hash[hash_index] × seahash_prime hash[hash_index] = hash[hash_index] XOR (hash[hash_index] RSHIFT 32) hash[hash_index] = hash[hash_index] × seahash_prime hash[hash_index] = hash[hash_index] XOR (hash[hash_index] RSHIFT 32) } } result = hash[0] XOR hash[1] XOR hash[2] XOR hash[3] XOR data.length_in_bytes result = result XOR (result RSHIFT 32) result = result × seahash_prime result = result XOR (result RSHIFT 32) result = result × seahash_prime result = result XOR (result RSHIFT 32) return result FNV is operating on bytes of data, while seahash is operating on 64-bit words. A modern processor will be able to handle 64 bits at once. True, it can probably handle 8 bits independently in one instruction without having to create a temporary value, but it still needs to do more operations. FNV is completely sequential. Until the first byte is hashed, no work can be done on the second byte. In seahash, as you observed, parallelism can be exploited. The second, third, and fourth bytes are all completely independent of the first byte, as bytes 6, 7, and 8 are independent of byte 5, and so on. You can have four independent threads each do a quarter of the work, and then put the result back together at the end.
nullnilvoid 10y ago
Great to see another piece of code written in Rust. That said, how do you make claims of something being blazingly fast without any comparisons to implementations in other languages such as C or C++?
- tupshin 10y ago
  The claim is that it is a blazingly fast hash function compared with other hash functions, and it is also written in Rust. Rust is an enabling technology, but not able to be dramatically faster than a comparable C/C++ implementation, as a general rule.
  - nullnilvoid 10y ago
    The title is confusing. If it tries to compete with other hash functions, why does the title have to bear "in Rust"?
    - pcwalton 10y ago
      Because it's probably the most notable/unusual part of this hash function. Virtually all other hash functions for at least a decade have had their reference implementations written in C or C++.
    - echelon 10y ago
      The Rust ecosystem is growing rapidly, and I personally think it's awesome that we're telling the world about it. Rust is production-ready and presents several advantages over C and C++. The more people that jump on board, the faster we get more libraries, and the more companies will take a look at using Rust in their own production environments. I predict Rust will also begin to find use as a backend server language, and begin to eat into Java, Go, Python, and Ruby mindshare. Though there's a learning curve with Rust, it doesn't take too long to become productive. I'm also excited to see how Rust makes inroads in game development. I think we're all going to start seeing more Rust in our headlines. It's a great language, and the people I know that use it are in love with it (myself included).
- deleted 10y ago
aleyan 10y ago
This is is not a knock against SeaHash, but I was looking at buffer.rs [0] and noticed pretty much all the code is wrapped in unsafe {} blocks. How much advantage is there to rust implementation vs c++ if unsafe is used so liberally? I ask this in ernest. [0] https://docs.rs/crate/seahash/2.0.0/source/src/buffer.rs https://docs.rs/crate/seahash/2.0.0/source/src/buffer.rs
- fnord123 10y ago
  None. But once you're out of the buffer code, it's safe.
  - michaelmior 10y ago
    It's safe as long as the unsafe code didn't mess with pointers in unexpected ways. Your unsafe code still needs to behave in a sane way for any safety guarantees to hold.
    - fnord123 10y ago
      Sure. And if there's a problem, the search for the bug should be limited to the unsafe blocks. Which is the promised benefit over C++.
      - Animats 10y ago
        No. As soon as there's unsafe code, there's the possibility of safe code misusing the unsafe code to create unsafe behavior. One would like to have un-abusable unsafe code, but the language does nothing to guarantee that.
        pcwalton 10y ago
        The parent post is correct. Unsafe code must uphold the invariants of safe Rust. If unsafe code is safe only if the caller upholds some invariants not enforced by the compiler, then by definition it's the unsafe code that is wrong.
Dylan16807 10y ago
I was unsure how to read the diffusion function's description, so I went to the source. The first line, "x ← x ≫ 32", might have a typo? It's actually assigning (x XOR (x >> 32)). With "x ← px", p is a fixed prime number being multiplied by x.
aappleby 10y ago
Looks like a pretty straightforward 64-bit block hash unrolled 4 times. I'd prefer a bit more assymetry in the diffuse() method, but since it passes SMHasher it's probably OK. I wonder how the Rust version compares with plain-jane C. -Austin (murmurhash guy).
- aappleby 10y ago
  Actually, just noticed a minor issue - since there's no intermixing between the four lanes and the diffuse() function is the same for all of them, if any of the IVs match then I can swap all the blocks in those lanes and get the same hash out. For example, if IV1 and IV2 match and the block pattern is ABCDABCDABCD, then BACDBACDBACD will produce the same hash value. A minor finalizer change would fix it for any IV (pseudocode as I don't actually know Rust) - vec[0] ^= diffuse(vec[1]); vec[1] ^= diffuse(vec[0]); vec[2] ^= diffuse(vec[3]); vec[3] ^= diffuse(vec[2]); u64 result = diffuse(vec[1] ^ diffuse(vec[3])); that's probably overkill but should work.
  - alekratz 10y ago
    I'm not a "hash guy" by any means - what impact would that have on its performance?
    - loeg 10y ago
      None for large strings and you'd have to benchmark small strings.
    - aappleby 10y ago
      Negligible, a few tens of cycles of extra overhead.
  - pbsd 10y ago
    That won't help much; you can zero the entire final state easily, e.g., with the message IV0 IV1 IV2 IV3 (or by xoring the latest diffuse() output back into the state), in which case you get diffuse(0) = 0 and with your finalization function you still get easy collisions. The operating mode of this hash is broken by default. The author calls it Merkle-Damgard, but that is not what it is. Merkle-Damgard uses a compression function, whereas what we have here is more like a sponge with full state absorption (you can pretend F(IV ^ m) is a compression function, but it is trivially susceptible to collisions F(IV ^ m) = F(m ^ IV)). Meaning, without a secret IV and some sort of truncation there's no way this mode can be secure, even with an ideal diffuse() function.
tibbe 10y ago
How does it perform on short strings (e.g. <= 16 bytes)? We've seen several new hash functions lately with great throughput numbers, but unfortunately they often end up being slower than FNV when used e.g. on keys in hash maps, which are often short strings.
crtc 10y ago
What's the matter with this stupid word "blazingly" in the Rust community?

186 points by pcwalton 10y ago

jedisct1 10y ago

Great. But keep in mind that this is not a keyed hash function.

dsp1234 10y ago
This is mentioned in the documentation: "Warning! This is not a cryptographic function, and it certainly should not be used as one. If you want a good cryptograhic hash function, you should use SHA-3 (Keccak) or BLAKE2."
- Dylan16807 10y ago
  That's not the same thing. You don't usually key for crypto reasons, and a good cryptographic hash does not imply keying.
pcwalton 10y ago
You can use it as a keyed hash function by adjusting the IV. See: https://docs.rs/seahash/2.0.0/src/seahash/.cargo/registry/src/github.com-1ecc6299db9ec823/seahash-2.0.0/src/reference.rs.html#94 https://docs.rs/seahash/2.0.0/src/seahash/.cargo/registry/sr...
- tveita 10y ago
  It seems to already be implemented in https://docs.rs/seahash/2.1.1/src/seahash/.cargo/registry/src/github.com-1ecc6299db9ec823/seahash-2.1.1/src/buffer.rs.html#102 https://docs.rs/seahash/2.1.1/src/seahash/.cargo/registry/sr... But it only seeds one of the lanes, so you can still make collisions trivially in one of the other lanes. I guess it could still be useful for namespacing.

eridius 10y ago

Very cool! BTW, the hyperlink for "reference" in the "Specification" section is broken.

sp332 10y ago

I was trying to figure out how this is so much faster than FNV https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function#FNV-1_hash https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo... Is it only because of the parallelism? Or are the operations really that much cheaper somehow?

mastax 10y ago
Presumably because SeaHash operates on 8-byte blocks while FNV acts on single bytes.
LeifCarrotson 10y ago
Both. The pseudocode for FNV looks like this: hash = FNV_offset_value for each byte_of_data to be hashed { hash = hash XOR byte_of_data hash = hash × FNV_prime } return hash The pseudocode for seahash looks like this (with '×' as the wrapping multplier operator, and some simplification for padding if the data length in bytes is not a multiple of 8 bytes per word × 4 words in the hash state): hash = {offset_1, offset_2, offset_3, offset_4} for (int data_index = 0; data_index < data.length_in_64_bit_words; data_index = data_index + 4_words_in_hash) { for (int hash_index = 0; hash_index < 4; hash_index++) { // Mix in data hash[hash_index] = hash[hash_index] XOR data[data_index + hash_index] // Diffuse hash[hash_index] = hash[hash_index] XOR (hash[hash_index] RSHIFT 32) hash[hash_index] = hash[hash_index] × seahash_prime hash[hash_index] = hash[hash_index] XOR (hash[hash_index] RSHIFT 32) hash[hash_index] = hash[hash_index] × seahash_prime hash[hash_index] = hash[hash_index] XOR (hash[hash_index] RSHIFT 32) } } result = hash[0] XOR hash[1] XOR hash[2] XOR hash[3] XOR data.length_in_bytes result = result XOR (result RSHIFT 32) result = result × seahash_prime result = result XOR (result RSHIFT 32) result = result × seahash_prime result = result XOR (result RSHIFT 32) return result FNV is operating on bytes of data, while seahash is operating on 64-bit words. A modern processor will be able to handle 64 bits at once. True, it can probably handle 8 bits independently in one instruction without having to create a temporary value, but it still needs to do more operations. FNV is completely sequential. Until the first byte is hashed, no work can be done on the second byte. In seahash, as you observed, parallelism can be exploited. The second, third, and fourth bytes are all completely independent of the first byte, as bytes 6, 7, and 8 are independent of byte 5, and so on. You can have four independent threads each do a quarter of the work, and then put the result back together at the end.

nullnilvoid 10y ago

Great to see another piece of code written in Rust. That said, how do you make claims of something being blazingly fast without any comparisons to implementations in other languages such as C or C++?

tupshin 10y ago
The claim is that it is a blazingly fast hash function compared with other hash functions, and it is also written in Rust. Rust is an enabling technology, but not able to be dramatically faster than a comparable C/C++ implementation, as a general rule.
- nullnilvoid 10y ago
  The title is confusing. If it tries to compete with other hash functions, why does the title have to bear "in Rust"?
  - pcwalton 10y ago
    Because it's probably the most notable/unusual part of this hash function. Virtually all other hash functions for at least a decade have had their reference implementations written in C or C++.
  - echelon 10y ago
    The Rust ecosystem is growing rapidly, and I personally think it's awesome that we're telling the world about it. Rust is production-ready and presents several advantages over C and C++. The more people that jump on board, the faster we get more libraries, and the more companies will take a look at using Rust in their own production environments. I predict Rust will also begin to find use as a backend server language, and begin to eat into Java, Go, Python, and Ruby mindshare. Though there's a learning curve with Rust, it doesn't take too long to become productive. I'm also excited to see how Rust makes inroads in game development. I think we're all going to start seeing more Rust in our headlines. It's a great language, and the people I know that use it are in love with it (myself included).
deleted 10y ago

aleyan 10y ago

This is is not a knock against SeaHash, but I was looking at buffer.rs [0] and noticed pretty much all the code is wrapped in unsafe {} blocks. How much advantage is there to rust implementation vs c++ if unsafe is used so liberally? I ask this in ernest. [0] https://docs.rs/crate/seahash/2.0.0/source/src/buffer.rs https://docs.rs/crate/seahash/2.0.0/source/src/buffer.rs

fnord123 10y ago
None. But once you're out of the buffer code, it's safe.
- michaelmior 10y ago
  It's safe as long as the unsafe code didn't mess with pointers in unexpected ways. Your unsafe code still needs to behave in a sane way for any safety guarantees to hold.
  - fnord123 10y ago
    Sure. And if there's a problem, the search for the bug should be limited to the unsafe blocks. Which is the promised benefit over C++.
    - Animats 10y ago
      No. As soon as there's unsafe code, there's the possibility of safe code misusing the unsafe code to create unsafe behavior. One would like to have un-abusable unsafe code, but the language does nothing to guarantee that.
      - pcwalton 10y ago
        The parent post is correct. Unsafe code must uphold the invariants of safe Rust. If unsafe code is safe only if the caller upholds some invariants not enforced by the compiler, then by definition it's the unsafe code that is wrong.

Dylan16807 10y ago

I was unsure how to read the diffusion function's description, so I went to the source. The first line, "x ← x ≫ 32", might have a typo? It's actually assigning (x XOR (x >> 32)). With "x ← px", p is a fixed prime number being multiplied by x.

aappleby 10y ago

Looks like a pretty straightforward 64-bit block hash unrolled 4 times. I'd prefer a bit more assymetry in the diffuse() method, but since it passes SMHasher it's probably OK. I wonder how the Rust version compares with plain-jane C. -Austin (murmurhash guy).

aappleby 10y ago
Actually, just noticed a minor issue - since there's no intermixing between the four lanes and the diffuse() function is the same for all of them, if any of the IVs match then I can swap all the blocks in those lanes and get the same hash out. For example, if IV1 and IV2 match and the block pattern is ABCDABCDABCD, then BACDBACDBACD will produce the same hash value. A minor finalizer change would fix it for any IV (pseudocode as I don't actually know Rust) - vec[0] ^= diffuse(vec[1]); vec[1] ^= diffuse(vec[0]); vec[2] ^= diffuse(vec[3]); vec[3] ^= diffuse(vec[2]); u64 result = diffuse(vec[1] ^ diffuse(vec[3])); that's probably overkill but should work.
- alekratz 10y ago
  I'm not a "hash guy" by any means - what impact would that have on its performance?
  - loeg 10y ago
    None for large strings and you'd have to benchmark small strings.
  - aappleby 10y ago
    Negligible, a few tens of cycles of extra overhead.
- pbsd 10y ago
  That won't help much; you can zero the entire final state easily, e.g., with the message IV0 IV1 IV2 IV3 (or by xoring the latest diffuse() output back into the state), in which case you get diffuse(0) = 0 and with your finalization function you still get easy collisions. The operating mode of this hash is broken by default. The author calls it Merkle-Damgard, but that is not what it is. Merkle-Damgard uses a compression function, whereas what we have here is more like a sponge with full state absorption (you can pretend F(IV ^ m) is a compression function, but it is trivially susceptible to collisions F(IV ^ m) = F(m ^ IV)). Meaning, without a secret IV and some sort of truncation there's no way this mode can be secure, even with an ideal diffuse() function.

tibbe 10y ago

How does it perform on short strings (e.g. <= 16 bytes)? We've seen several new hash functions lately with great throughput numbers, but unfortunately they often end up being slower than FNV when used e.g. on keys in hash maps, which are often short strings.

crtc 10y ago

What's the matter with this stupid word "blazingly" in the Rust community?