5 ms·

Show HN: Rain hashes – well designed, simple and fast variable sized hashes

79 points by keepamovin 2y ago

keepamovin 2y ago
This is my hash included in the best hash testing library out there "SMHasher3" maintained by Frank T Wojcik: https://gitlab.com/fwojcik/smhasher3 https://gitlab.com/fwojcik/smhasher3 This test lib has many improvements over SMHasher 1 & 2, listed on the previous link. Results are: https://gitlab.com/fwojcik/smhasher3/-/blob/main/results/README.md https://gitlab.com/fwojcik/smhasher3/-/blob/main/results/REA... Rainbow is the fastest 128-bit hash, and the fastest 256-bit hash (non-crypto). The 8th fastest 64-bit hash (by family, or 9th fastest overall, and 13-th fatest overall if you include 32-bit hashes). The advantage of rainbow is its easily scalable output size (64, 128 and 256), its high quality (passes all the tests), and its utter simplicity: it is under 140 source lines of code, easily readable The random constants are primes that were selected based on their avalanche quality under a multiply modulo operation. This part of the development was interesting different primes had very distinctly different avalanche qualities. The highest quality primes caused good avalanche (~ 50% bit flip probability) across the widest possible set of bits, on average. These are quite rare. A lot of large primes only avalanche across a narrow range of bits, even in a 128-bit space. The search program took a couple of days to discover all these primes running on a 2020s era MBP. Primes are chosen because they give a complete residue set under the modulus, ensuring a long cycle length at least regarding the nominal test operation. The rest of the hash was developed by trial and error using my intuition on developing hashes arising from long experience of doing so, and using SMHasher3 to evaluate the results, by iterating to improve and re-testing, over a period of a couple of weeks in the holidays a few years ago. I started making hash functions in my teens as a fun hobby. There's also a fun little wasm powered dashboard you can play with, here: https://dosaygo-research.github.io/rain/ https://dosaygo-research.github.io/rain/
- mulle_nat 2y ago
  I am using fnv-1a to hash Objective-C method selectors, which are generally just identifier characters and zero or multiple ':'. At the time of my research, fnv-1a had the least collisions over my set of "real life" selectors. I think, it could be worthwhile some time, to try out other constants for maybe even less collisions. Is your list of good primes available ? (And maybe also those that are not quite perfect)
  - keepamovin 2y ago
    Everything is in the source code. I highly doubt any of the good hash functions listed in smhasher3 (ie all tests passed) would collide over identifiers. So they should all have zero collisions, meaning there’s no ‘least’ among the good quality ones - they’re all equally collissionless (they differ in other tests). Sounds like an interesting project. What’s its purpose?
    - mulle_nat 2y ago
      Cool. I forgot to mention, that I am truncating the hash down to 32 bits to hopefully generate tighter CPU instructions. At these few bits, collisions are still rare enough, but they are a concern. Now my understanding of the choice of prime is that, you are "weighing" the input bits and the computed bits, that will form the hash. So in case of identifiers its very likely that bit 7 of the input is always 0 and say maybe bit 4 is statistically more likely to be 1 by some margin. The other input bits would have some entropy as well. I would expect that certain (imperfect) primes would then aid me to get a better use of the 32 bit space and therefore less risk of a collision for my Objective-C runtime. You can check out the project here: https://github.com/mulle-objc https://github.com/mulle-objc.
      - keepamovin 2y ago
        Ah, that's interesting. 32-bits yes you would get some collisions even from good hashes just statistically. Also now I understand your constraints. Very interesting, so you are designing a custom hash function to use in this specific domain of keys with specific probabilistic properties, and you are thinking that there would be some way you could multiply by a certain prime that would ideally fan out these keys to be evenly distributed over the space? mulle-objc looks fascinating: fast, portable Objective-C runtime written 100% in C11. I encourage you to post a Show HN I'm sure people here would like it.
        mulle_nat 2y ago
        Actually I already did, a few years ago: https://news.ycombinator.com/item?id=13030568 https://news.ycombinator.com/item?id=13030568
zokier 2y ago
The benchmarks are bogus at the least, you are essentially just measuring the startup time of the executable/runtime and not your hash function.
- keepamovin 2y ago
  Right, how to improve that? That nodejs bench script is meant to compare between cpp and wasm. For hash speed consult the smasher3 results.
tptacek 2y ago
Broadly: I don't understand the design space of "cryptographic-ish" hashes. There's an intensely competitive design space of cryptographic hashes. What does it mean to be "more secure" than an insecure hash function? When would it ever be appropriate to use such a hash?
- dan_manges 2y ago
  Checksums are a good use case, where you’re not worried about any sort of forged collisions and you want to calculate the checksum as fast as possible. Although cryptographic hashes are fast enough that there likely aren’t too many use cases where the difference in speed is meaningful.
  - loeg 2y ago
    If you don't care about forged collisions, what makes a secure-ish checksum bette than a faster insecure checksum? Both are likely to result in a different value for bit-flipped input, which is the point.
    - nepthar 2y ago
      That’s a good question. A cryptographic hash must not leak any information other than “yes” or “no”. A checksum-type hash might have an additional property where data that only has a single bit flipped might hash to something close to the original hash, allowing you to refine your collision attack by knowing if you’re hot or cold. For a checksum, this isnt a bad thing and actually could be good.
    - cstrahan 2y ago
      Note that you said “likely” and not “equally likely”. Therein lies your answer. There are applications where hashes are used as identifiers, where it would be impossible to use the original data to resolve possible collisions. One example would be in RTTI (Run Time Type Information), when you want to check if two objects (of unknown-at-compile-time type) are instances of the same type. The only performant way to achieve this is if the compiler emits each type’s RTTI with a unique integer key to efficiently compare against, and this key must be unique across all object files and shared objects. In practice, this is done using hashing. If there is a collision, then the program behavior is undefined, so it is ideal to minimize probability of collision. You can see this issue in the Rust compiler project where there is ongoing discussion about how to handle this hashing, trying to balance compiler speed and collision likeliness: https://github.com/rust-lang/rust/issues/129014 https://github.com/rust-lang/rust/issues/129014 Another scenario would be like what Backtrace does: a hash is used to identify certain classes of errors in application code. The cost of analyzing each error is quite high (you have to load objects into memory, source maps (if available), perform symbolification, etc), so comparing any two errors every time you want to perform any metrics or retrieve associated data (like issue tracker identifiers) would reduce the performance to a point that any such application would be too slow to be useful. So a lot of thought was given to producing fast, non-cryptographic hashes (these hashes aren’t shared across tenants, and no customer is going to go out of their way to work out initialization parameters so they can be their own adversary) with a known likely hood of collision. You can read about the hash (UMASH) here: https://engineering.backtrace.io/2020-08-24-umash-fast-enough-almost-universal-fingerprinting/ https://engineering.backtrace.io/2020-08-24-umash-fast-enoug...
thadt 2y ago
So, questions for people that know more than I: What's up with the 'passing' and 'failing' hashes in SMHasher3? Specifically, what happened to xxHash[1] to kick it down to the 'failing' category? I'm not certain about SMHasher's testing criteria, but comparing the benchmark numbers posed in Rain vs xxHash show xxH3 rather faster? Not that a have a personally vested intersted in xxHash, but it seems to be a rather widely used (e.g. RocksDB [2]) with a number of implementations - it would be useful to understand the criteria that make it no longer a passing SMHasher3 entry. [1] https://github.com/Cyan4973/xxHash https://github.com/Cyan4973/xxHash [2] https://rocksdb.org/blog/2022/07/18/per-key-value-checksum.html https://rocksdb.org/blog/2022/07/18/per-key-value-checksum.h...
- deleted 2y ago
  [deleted]
- zimpenfish 2y ago
  > Specifically, what happened to xxHash to kick it down to the 'failing' category? Looking at [1], it seems to collisions (search for "!!!!!") [1] https://gitlab.com/fwojcik/smhasher3/-/blob/main/results/raw/XXH-64.txt https://gitlab.com/fwojcik/smhasher3/-/blob/main/results/raw...
mrbluecoat 2y ago
The fastest 128-bit and 256-bit non-crypto hash, passes all tests, and under 140 source lines of code Nice!
- keepamovin 2y ago
  Yes. Thank you :) It’s pretty good
rurban 2y ago
I failed to integrate it into my smhasher, the rain branch. Lots of collisions and wrong results all over. Pretty fragile for a workday
- keepamovin 2y ago
  Hey Reini, I'm no C++ expert, but yes your SMHasher2 is pretty fragile. I don't know for a workday or not, but it's fragile. But what you said is a pretty nasty thing to say given there’s lots of bugs in your SMHasher2 that have already been fixed in SMHasher3. You can’t blame a hash for what’s your fault. You could always just do fixes instead of saying toxic nasty stuff. If you want to put it in, take a look at the SMHasher3 library code, and the rain integrations there. I think you’ll have to port it as there’s some internal differences with your SMHasher2. Also, I'm sorry for the unclear and wrong default branch: it should be 'boss' branch. That's corrected now.
  - rurban 2y ago
    smhasher2 is not fragile at all. The rain test api functions are static in a .cpp. This will not work anywhere else than in smhasher3 with its special wrappers. You need to put them in headers if you want them static inline.
dgacmu 2y ago
Just to make sure I'm understanding correctly, I think that your intent is that rainbow is / should be treated as cryptographically weaker than SIPhash, right? (despite both of them not being something you would use in a high security context)
- keepamovin 2y ago
  Right: rainbow has not been evaluated for HMAC or PRF (Sip's main security objectives), but it's not designed to be secure, just to have good stats and be fast af. I wouldn't be surprised if it was a good PRF, but also wouldn't be surprised if it was broken (by the standards of cryptohashes or HMAC or even PRF). Some more about sip: https://docs.kernel.org/security/siphash.html https://docs.kernel.org/security/siphash.html
  - keepamovin 2y ago
    However there’s some chance it’s actually better and more secure than Rainstorm

79 points by keepamovin 2y ago

This is my hash included in the best hash testing library out there "SMHasher3" maintained by Frank T Wojcik: https://gitlab.com/fwojcik/smhasher3 https://gitlab.com/fwojcik/smhasher3 This test lib has many improvements over SMHasher 1 & 2, listed on the previous link. Results are: https://gitlab.com/fwojcik/smhasher3/-/blob/main/results/README.md https://gitlab.com/fwojcik/smhasher3/-/blob/main/results/REA... Rainbow is the fastest 128-bit hash, and the fastest 256-bit hash (non-crypto). The 8th fastest 64-bit hash (by family, or 9th fastest overall, and 13-th fatest overall if you include 32-bit hashes). The advantage of rainbow is its easily scalable output size (64, 128 and 256), its high quality (passes all the tests), and its utter simplicity: it is under 140 source lines of code, easily readable The random constants are primes that were selected based on their avalanche quality under a multiply modulo operation. This part of the development was interesting different primes had very distinctly different avalanche qualities. The highest quality primes caused good avalanche (~ 50% bit flip probability) across the widest possible set of bits, on average. These are quite rare. A lot of large primes only avalanche across a narrow range of bits, even in a 128-bit space. The search program took a couple of days to discover all these primes running on a 2020s era MBP. Primes are chosen because they give a complete residue set under the modulus, ensuring a long cycle length at least regarding the nominal test operation. The rest of the hash was developed by trial and error using my intuition on developing hashes arising from long experience of doing so, and using SMHasher3 to evaluate the results, by iterating to improve and re-testing, over a period of a couple of weeks in the holidays a few years ago. I started making hash functions in my teens as a fun hobby. There's also a fun little wasm powered dashboard you can play with, here: https://dosaygo-research.github.io/rain/ https://dosaygo-research.github.io/rain/

mulle_nat 2y ago
I am using fnv-1a to hash Objective-C method selectors, which are generally just identifier characters and zero or multiple ':'. At the time of my research, fnv-1a had the least collisions over my set of "real life" selectors. I think, it could be worthwhile some time, to try out other constants for maybe even less collisions. Is your list of good primes available ? (And maybe also those that are not quite perfect)
- keepamovin 2y ago
  Everything is in the source code. I highly doubt any of the good hash functions listed in smhasher3 (ie all tests passed) would collide over identifiers. So they should all have zero collisions, meaning there’s no ‘least’ among the good quality ones - they’re all equally collissionless (they differ in other tests). Sounds like an interesting project. What’s its purpose?
  - mulle_nat 2y ago
    Cool. I forgot to mention, that I am truncating the hash down to 32 bits to hopefully generate tighter CPU instructions. At these few bits, collisions are still rare enough, but they are a concern. Now my understanding of the choice of prime is that, you are "weighing" the input bits and the computed bits, that will form the hash. So in case of identifiers its very likely that bit 7 of the input is always 0 and say maybe bit 4 is statistically more likely to be 1 by some margin. The other input bits would have some entropy as well. I would expect that certain (imperfect) primes would then aid me to get a better use of the 32 bit space and therefore less risk of a collision for my Objective-C runtime. You can check out the project here: https://github.com/mulle-objc https://github.com/mulle-objc.
    - keepamovin 2y ago
      Ah, that's interesting. 32-bits yes you would get some collisions even from good hashes just statistically. Also now I understand your constraints. Very interesting, so you are designing a custom hash function to use in this specific domain of keys with specific probabilistic properties, and you are thinking that there would be some way you could multiply by a certain prime that would ideally fan out these keys to be evenly distributed over the space? mulle-objc looks fascinating: fast, portable Objective-C runtime written 100% in C11. I encourage you to post a Show HN I'm sure people here would like it.
      - mulle_nat 2y ago
        Actually I already did, a few years ago: https://news.ycombinator.com/item?id=13030568 https://news.ycombinator.com/item?id=13030568

zokier 2y ago

The benchmarks are bogus at the least, you are essentially just measuring the startup time of the executable/runtime and not your hash function.

keepamovin 2y ago
Right, how to improve that? That nodejs bench script is meant to compare between cpp and wasm. For hash speed consult the smasher3 results.

tptacek 2y ago

Broadly: I don't understand the design space of "cryptographic-ish" hashes. There's an intensely competitive design space of cryptographic hashes. What does it mean to be "more secure" than an insecure hash function? When would it ever be appropriate to use such a hash?

dan_manges 2y ago
Checksums are a good use case, where you’re not worried about any sort of forged collisions and you want to calculate the checksum as fast as possible. Although cryptographic hashes are fast enough that there likely aren’t too many use cases where the difference in speed is meaningful.
- loeg 2y ago
  If you don't care about forged collisions, what makes a secure-ish checksum bette than a faster insecure checksum? Both are likely to result in a different value for bit-flipped input, which is the point.
  - nepthar 2y ago
    That’s a good question. A cryptographic hash must not leak any information other than “yes” or “no”. A checksum-type hash might have an additional property where data that only has a single bit flipped might hash to something close to the original hash, allowing you to refine your collision attack by knowing if you’re hot or cold. For a checksum, this isnt a bad thing and actually could be good.
  - cstrahan 2y ago
    Note that you said “likely” and not “equally likely”. Therein lies your answer. There are applications where hashes are used as identifiers, where it would be impossible to use the original data to resolve possible collisions. One example would be in RTTI (Run Time Type Information), when you want to check if two objects (of unknown-at-compile-time type) are instances of the same type. The only performant way to achieve this is if the compiler emits each type’s RTTI with a unique integer key to efficiently compare against, and this key must be unique across all object files and shared objects. In practice, this is done using hashing. If there is a collision, then the program behavior is undefined, so it is ideal to minimize probability of collision. You can see this issue in the Rust compiler project where there is ongoing discussion about how to handle this hashing, trying to balance compiler speed and collision likeliness: https://github.com/rust-lang/rust/issues/129014 https://github.com/rust-lang/rust/issues/129014 Another scenario would be like what Backtrace does: a hash is used to identify certain classes of errors in application code. The cost of analyzing each error is quite high (you have to load objects into memory, source maps (if available), perform symbolification, etc), so comparing any two errors every time you want to perform any metrics or retrieve associated data (like issue tracker identifiers) would reduce the performance to a point that any such application would be too slow to be useful. So a lot of thought was given to producing fast, non-cryptographic hashes (these hashes aren’t shared across tenants, and no customer is going to go out of their way to work out initialization parameters so they can be their own adversary) with a known likely hood of collision. You can read about the hash (UMASH) here: https://engineering.backtrace.io/2020-08-24-umash-fast-enough-almost-universal-fingerprinting/ https://engineering.backtrace.io/2020-08-24-umash-fast-enoug...

thadt 2y ago

So, questions for people that know more than I: What's up with the 'passing' and 'failing' hashes in SMHasher3? Specifically, what happened to xxHash[1] to kick it down to the 'failing' category? I'm not certain about SMHasher's testing criteria, but comparing the benchmark numbers posed in Rain vs xxHash show xxH3 rather faster? Not that a have a personally vested intersted in xxHash, but it seems to be a rather widely used (e.g. RocksDB [2]) with a number of implementations - it would be useful to understand the criteria that make it no longer a passing SMHasher3 entry. [1] https://github.com/Cyan4973/xxHash https://github.com/Cyan4973/xxHash [2] https://rocksdb.org/blog/2022/07/18/per-key-value-checksum.html https://rocksdb.org/blog/2022/07/18/per-key-value-checksum.h...

deleted 2y ago
[deleted]
zimpenfish 2y ago
> Specifically, what happened to xxHash to kick it down to the 'failing' category? Looking at [1], it seems to collisions (search for "!!!!!") [1] https://gitlab.com/fwojcik/smhasher3/-/blob/main/results/raw/XXH-64.txt https://gitlab.com/fwojcik/smhasher3/-/blob/main/results/raw...

mrbluecoat 2y ago

The fastest 128-bit and 256-bit non-crypto hash, passes all tests, and under 140 source lines of code Nice!

keepamovin 2y ago
Yes. Thank you :) It’s pretty good

rurban 2y ago

I failed to integrate it into my smhasher, the rain branch. Lots of collisions and wrong results all over. Pretty fragile for a workday

keepamovin 2y ago
Hey Reini, I'm no C++ expert, but yes your SMHasher2 is pretty fragile. I don't know for a workday or not, but it's fragile. But what you said is a pretty nasty thing to say given there’s lots of bugs in your SMHasher2 that have already been fixed in SMHasher3. You can’t blame a hash for what’s your fault. You could always just do fixes instead of saying toxic nasty stuff. If you want to put it in, take a look at the SMHasher3 library code, and the rain integrations there. I think you’ll have to port it as there’s some internal differences with your SMHasher2. Also, I'm sorry for the unclear and wrong default branch: it should be 'boss' branch. That's corrected now.
- rurban 2y ago
  smhasher2 is not fragile at all. The rain test api functions are static in a .cpp. This will not work anywhere else than in smhasher3 with its special wrappers. You need to put them in headers if you want them static inline.

dgacmu 2y ago

Just to make sure I'm understanding correctly, I think that your intent is that rainbow is / should be treated as cryptographically weaker than SIPhash, right? (despite both of them not being something you would use in a high security context)

keepamovin 2y ago
Right: rainbow has not been evaluated for HMAC or PRF (Sip's main security objectives), but it's not designed to be secure, just to have good stats and be fast af. I wouldn't be surprised if it was a good PRF, but also wouldn't be surprised if it was broken (by the standards of cryptohashes or HMAC or even PRF). Some more about sip: https://docs.kernel.org/security/siphash.html https://docs.kernel.org/security/siphash.html
- keepamovin 2y ago
  However there’s some chance it’s actually better and more secure than Rainstorm