Show HN: Discohash – Fast Hash • Hacker News Board

Re: Show HN: Discohash – Fast Hash

#21

Post by antirez » Sat, May 23, 2020, 6:08 PM UTC

fantastisch wrote: post #18

aappleby wrote: post #16

Earlier quoted context omitted.

Predeclared aliased pointers, STATEM/HSTATEM constants, len/Len, that kind of stuff.

Thank you, Austin! BTW, not sure exactly what you mean by cross-half mixing, but I'm assuming it means mixing both halves of the 128 bit state with each other. There is that, on 3 lines 91[0], 100 and 108. The 128 bit mix, stirs two adjacent blocks of 64 bits. Those 3 lines can mix blocks 1 & 2. Subsequent mixes on either half then propagate that cross mix. So it does use the full 256 bit state. Is that what you mean…

Looks like a solid hash function indeed, with a very simple round.

Q: Is there any reason you don't use the same mixing function for the residue of the string (the final tail that is not a full 8 bytes block)? You could copy the bytes you have into a 8 byte array that is pre-padded with some pattern, and call the same mixing function again. Is this in order to save the distribution / avalanche properties in case the string is very short? In general would be nice to read some design note, if P and Q were obtained experimentally by checking for distribution or alike, if a different rotation length changes significantly the distribution properties and so forth.

Re: Show HN: Discohash – Fast Hash

#22

Post by zokier » Sat, May 23, 2020, 6:24 PM UTC

It is fast hash sure, but it still only sits in the middle of the pack in smhasher results, which is not very impressive. The code is maybe bit simpler than some of its competition, but to my non-expert eyes its still not trivial, and the compiled code still seems as big as some of its competitors. Although I'm bit curious why there is no "size" result in the smhasher table for this hash?

http://rurban.github.io/smhasher/doc/table.html

The ecrypt result is completely irrelevant when this can not be in any way be considered cryptographically secure at this point.

Re: Show HN: Discohash – Fast Hash

#23

Post by fantastisch » Sat, May 23, 2020, 6:31 PM UTC

antirez wrote: post #21

fantastisch wrote: post #18

Earlier quoted context omitted.

Thank you, Austin! BTW, not sure exactly what you mean by cross-half mixing, but I'm assuming it means mixing both halves of the 128 bit state with each other. There is that, on 3 lines 91[0], 100 and 108. The 128 bit mix, stirs two adjacent blocks of 64 bits. Those 3 lines can mix blocks 1 & 2. Subsequent mixes on either half then propagate that cross mix. So it does use the full 256 bit state. Is that what you mean…

Looks like a solid hash function indeed, with a very simple round. Q: Is there any reason you don't use the same mixing function for the residue of the string (the final tail that is not a full 8 bytes block)? You could copy the bytes you have into a 8 byte array that is pre-padded with some pattern, and call the same mixing function again. Is this in order to save the distribution / avalanche properties in case the…

Great question, and thank you, Salvatore!

Some reasons for that are: different hashes for s and s\0 (without explicitly using length) to make it harder to create collisions, related to as you say better distribution/avalanche for short strings, also design-wise I like the asymmetry that strings not perfectly divisible by 8 will be treated a little differently. I just think that makes it better overall.

Re: Show HN: Discohash – Fast Hash

#24

Post by [deleted] » Sat, May 23, 2020, 6:36 PM UTC

zokier wrote: post #22

It is fast hash sure, but it still only sits in the middle of the pack in smhasher results, which is not very impressive. The code is maybe bit simpler than some of its competition, but to my non-expert eyes its still not trivial, and the compiled code still seems as big as some of its competitors. Although I'm bit curious why there is no "size" result in the smhasher table for this hash? http://rurban.github.io/smha…

[deleted]

Re: Show HN: Discohash – Fast Hash

#25

Post by [deleted] » Sat, May 23, 2020, 7:12 PM UTC

remcob wrote: post #15

niftich wrote: post #7

This is a hash designed for non-cryptographic use, like in hash tables or bloom filters. You can tell by their small output size, which greatly reduces the cost of a brute-force collision search. It's also in the linked readme. Hash function families with a similar target usecase include: cityhash, falkhash, farmhash, FNV, meowhash, metrohash, murmur, t1ha, wyhash, xxh. The SMHasher suite tests hash functions for spe…

> This is a hash designed for non-cryptographic use The Readme specifically says "you can modify it to yield 128-bits or more if you want a cryptographically secure hash." Which is a problematic statement, because it is not designed for cryptography even if you extended the output to 256 bit. It's not the output length that makes it cryptographicaly secure. (Rather it's the difference between "you won't find collisio…

[deleted]

Re: Show HN: Discohash – Fast Hash

#26

Post by [deleted] » Sat, May 23, 2020, 7:13 PM UTC

zokier wrote: post #22

It is fast hash sure, but it still only sits in the middle of the pack in smhasher results, which is not very impressive. The code is maybe bit simpler than some of its competition, but to my non-expert eyes its still not trivial, and the compiled code still seems as big as some of its competitors. Although I'm bit curious why there is no "size" result in the smhasher table for this hash? http://rurban.github.io/smha…

[deleted]

Re: Show HN: Discohash – Fast Hash

#27

Post by ComputerGuru » Sat, May 23, 2020, 7:34 PM UTC

Stay away. The author can't tell the difference between a cryptographically secure hash and a regular one, claims that simply going from 64 to 128 bits will make magically make this cryptographically secure, and then benchmarks it against actually cryptographically secure hash functions (blake3), which are almost necessarily slower than generic hash functions.

Look at meowhash and wyhash instead for the latest and greatest in that field.

Re: Show HN: Discohash – Fast Hash

#28

Post by antirez » Sat, May 23, 2020, 8:27 PM UTC

fantastisch wrote: post #23

antirez wrote: post #21

Earlier quoted context omitted.

Looks like a solid hash function indeed, with a very simple round. Q: Is there any reason you don't use the same mixing function for the residue of the string (the final tail that is not a full 8 bytes block)? You could copy the bytes you have into a 8 byte array that is pre-padded with some pattern, and call the same mixing function again. Is this in order to save the distribution / avalanche properties in case the…

Great question, and thank you, Salvatore! Some reasons for that are: different hashes for s and s\0 (without explicitly using length) to make it harder to create collisions, related to as you say better distribution/avalanche for short strings, also design-wise I like the asymmetry that strings not perfectly divisible by 8 will be treated a little differently. I just think that makes it better overall.

Thanks for the replies!

Re: Show HN: Discohash – Fast Hash

#29

Post by bufferoverflow » Sat, May 23, 2020, 11:19 PM UTC

xxHash64 has demonstrated 14 GB/s a while ago

https://aras-p.info/img/blog/2016-08/hash2-pc.png

And FarmHash64 with SSE4.2 did almost 18 GB/s:

https://aras-p.info/img/blog/2016-08/hash2-farmhashoptions.p...

Full article: https://aras-p.info/blog/2016/08/09/More-Hash-Function-Tests...

Re: Show HN: Discohash – Fast Hash

#30

Post by remcob » Sun, May 24, 2020, 12:34 AM UTC

halayli wrote: post #5

wyhash is very impressive for those interested. Not sure why it doesn't get a lot of attention. https://github.com/wangyi-fudan/wyhash

It's odd to have the documentation in a .docx file in the repo. The code itself is not very readable. The core of it is something like (simplified):

    function mix(uint64 a, uint64 b) {
        a ^= secret
        b ^= seed
        hi, lo = mul128(a, b)
        seed = hi ^ lo
    }

It's elegantly simple, but depends critically on 'secret' not appearing in the data.