Show HN: Tifuhash - Tiny Fast Universal Hash, using 64-bit continued fractions(npmjs.com)
npmjs.com
Show HN: Tifuhash - Tiny Fast Universal Hash, using 64-bit continued fractions
https://www.npmjs.com/package/tifuhash
55 コメント
Edit: Update. I pushed a new version that addresses the collisions presented by dchest. I invite you to take a look. Thanks!
--
Thanks for the feedback. I really appreciate it. Well done finding all those collisions. This is serious! Here's an issue: https://github.com/dosaygo-coder-0/tifuhash/issues/3
Tho it's already valuable enough you pointing this out -- if you have any ideas on how to improve for these cases, please let me know!
Note to self: This community is so good. If something technical gets a bit of traction, you can count on people to find some holes in it. Very valuable. Just wanna say words can't express my gratitude at people's efforts at this. It's very helpful.
--
Thanks for the feedback. I really appreciate it. Well done finding all those collisions. This is serious! Here's an issue: https://github.com/dosaygo-coder-0/tifuhash/issues/3
Tho it's already valuable enough you pointing this out -- if you have any ideas on how to improve for these cases, please let me know!
Note to self: This community is so good. If something technical gets a bit of traction, you can count on people to find some holes in it. Very valuable. Just wanna say words can't express my gratitude at people's efforts at this. It's very helpful.
Update: I have completed testing of a slightly modified version in c++ with SMHasher, details below.
I posted the results in the repo: https://github.com/dosaygo-coder-0/tifuhash/blob/master/tifu...
And my SMHasher fork testing tifuhash is here: https://github.com/dosaygo-coder-0/smhasher
I posted the results in the repo: https://github.com/dosaygo-coder-0/tifuhash/blob/master/tifu...
And my SMHasher fork testing tifuhash is here: https://github.com/dosaygo-coder-0/smhasher
Dumb questions, why is this a problem?
t.hash(0.00000000000000002) == t.hash(0.00000000000000003)
If you use it for a hash table, every collision has to be "resolved" in a way that takes time: https://en.wikipedia.org/wiki/Hash_table#Collision_resolutio... .
So if a hash function has lots of collisions it will use the memory of the hash table less efficiently and cause inserts and lookups to be slower. I think collisions are undesirable for other reasons too, none of which are coming to me right now.
So if a hash function has lots of collisions it will use the memory of the hash table less efficiently and cause inserts and lookups to be slower. I think collisions are undesirable for other reasons too, none of which are coming to me right now.
But doesn't every hash function have some collisions? Why would this particular example be very bad?
I'm of the same mindset. I mean -- surely there are some collisions always. And I actually liked the property of the original version that a zero value hashed to all zeroes. While the rest of the pre-image was shuffled. But I suppose that being able to compute collisions is not a great thing. You may think that if it is not intended to be used in a cryptographic sense it does not matter. However, if you can easily compute collisions you could, theoretically of course, launch a denial-of-service attacks on a service (cache denial) by sending lots of values to the same hash slot. I mean, with probing and so on there are ways around this and in the end maybe the conventional wisdom ought to be revised, maybe there isn't so much to worry about from a few collisions, even easy to compute ones. But, as it stands, right now, the market demands collision resistance. So I damn well gave it to them.
[keep in mind I'm far from an expert on this]
The thing that bothers me personally about these examples is that there are a lot that end in 0x000000 or 0xffffff, i.e. all bits set or all bits unset in many of the trailing bits.
If you use this for a hash table, a common way that you get your index into the table is:
You can use a non-power-of-two table size to compensate for this (prime sizes are typically the most robust choice I think) at the cost of a more expensive modulo operation. See more here in the first section: https://en.wikipedia.org/wiki/Hash_table#Hashing
The thing that bothers me personally about these examples is that there are a lot that end in 0x000000 or 0xffffff, i.e. all bits set or all bits unset in many of the trailing bits.
If you use this for a hash table, a common way that you get your index into the table is:
index = hash_result % table_size
You can use a non-power-of-two table size to compensate for this (prime sizes are typically the most robust choice I think) at the cost of a more expensive modulo operation. See more here in the first section: https://en.wikipedia.org/wiki/Hash_table#Hashing
[deleted]
I was going to ask if he'd run it through SMHasher, but... yeah, clearly not.
-Austin (author of murmurhash/smhasher)
-Austin (author of murmurhash/smhasher)
Thank you, Austin. I'll look into SMHasher. Really appreciate you pointing me in that direction.
Austin, I've done a first test of a slightly modified CPP version. Thanks very much for this library. It really is so useful.
SMHasher fork testing tifuhash is here: https://github.com/dosaygo-coder-0/smhasher
And I posted the results in the repo: https://github.com/dosaygo-coder-0/tifuhash/blob/master/tifu...
SMHasher fork testing tifuhash is here: https://github.com/dosaygo-coder-0/smhasher
And I posted the results in the repo: https://github.com/dosaygo-coder-0/tifuhash/blob/master/tifu...
Sorry I'd changed the file name : https://github.com/dosaygo-coder-0/tifuhash/blob/master/tifu...
So your point is that the name of the hash is appropriate? Today I fucked up a hash function...?
Haha. Well the name is good then. Since it will work everyday.
[deleted]
In addition to the things others have pointed out, note that "universality" is a well-defined concept w.r.t. hash functions: https://en.wikipedia.org/wiki/Universal_hashing - you should probably not use it to describe your hash function if you can't show universality.
I realize my other comment might have come across as: "i called it universal because it hashes both strings and numbers, then someone pointed out the technical term universal and i decided i would just turn it into a 'universal hash' as well, because that would be easy."
From that point of view it makes sense to point out what universal hashing means, and how showing universality is non trivial, and not something i can just trivially track on.
However, i didn't communicate this following point before, but the genesis of tifuhash was: yesterday i read the paper i linked in the other comment and wanted to write a universal hash family. There's an open problem at the end of the paper that directly motivated me to try to come up with this.
* from that paper:*
> "Major Open Problem: Can we get something simple and fast like multiply-shift to work directly for strings, so that we do not need to compute polynomials over prime fields?"
Actually i wrote tifuhash to be universal and work on strings, in other words to be a family of parameterized hash functions with the 2^-64 collision probability. I imposed a bunch of other constraints I myself as well, such as only using arithmetic operations ( no bitwise ops ), making it as simple as possible, and trying to avoid opaque magic constants. I tried a bunch of things related to traditional multiply shift but nothing really clicked for me. Then I had the idea of using ratios of successive message values and from there just went into continued fractions. I was blown away with something so simple and using only arithmetic passed practrand. One reason i think passing practrand is important to universality is reflected in this quote from the wiki page on universal hashing:
> "This is exactly the probability of collision we would expect if the hash function assigned truly random hash codes to every key. "
Anyway, tl;dr is I designed it from the start to be universal.
From that point of view it makes sense to point out what universal hashing means, and how showing universality is non trivial, and not something i can just trivially track on.
However, i didn't communicate this following point before, but the genesis of tifuhash was: yesterday i read the paper i linked in the other comment and wanted to write a universal hash family. There's an open problem at the end of the paper that directly motivated me to try to come up with this.
* from that paper:*
> "Major Open Problem: Can we get something simple and fast like multiply-shift to work directly for strings, so that we do not need to compute polynomials over prime fields?"
Actually i wrote tifuhash to be universal and work on strings, in other words to be a family of parameterized hash functions with the 2^-64 collision probability. I imposed a bunch of other constraints I myself as well, such as only using arithmetic operations ( no bitwise ops ), making it as simple as possible, and trying to avoid opaque magic constants. I tried a bunch of things related to traditional multiply shift but nothing really clicked for me. Then I had the idea of using ratios of successive message values and from there just went into continued fractions. I was blown away with something so simple and using only arithmetic passed practrand. One reason i think passing practrand is important to universality is reflected in this quote from the wiki page on universal hashing:
> "This is exactly the probability of collision we would expect if the hash function assigned truly random hash codes to every key. "
Anyway, tl;dr is I designed it from the start to be universal.
I think it is probably universal, but I have to show it to know for sure. I'm going to keep calling it universal until I know more.
I think I note it in the README, but some reasons I think it is probably universal are because tifuhash can be parameterized, and it has good independence properties ( passes PractRand ).
Showing it is universal or not is another step. I suppose I could experiment, to see if the collision probabilities match the criteria for universal or k-universal. Or maybe I could show it. For showing it, my next step is to read over this paper[1] to see if I can use its methods to show universality. I think it is using properties of the bits under multiplication. And I believe one avenue would be to show it using properties of the bits under division. I don't know how to approach the bits under division right now.
[1]: https://arxiv.org/abs/1504.06804
I think I note it in the README, but some reasons I think it is probably universal are because tifuhash can be parameterized, and it has good independence properties ( passes PractRand ).
Showing it is universal or not is another step. I suppose I could experiment, to see if the collision probabilities match the criteria for universal or k-universal. Or maybe I could show it. For showing it, my next step is to read over this paper[1] to see if I can use its methods to show universality. I think it is using properties of the bits under multiplication. And I believe one avenue would be to show it using properties of the bits under division. I don't know how to approach the bits under division right now.
[1]: https://arxiv.org/abs/1504.06804
I admire your confidence but I don't share it - showing universality for a complex construct like yours is rather nontrivial. You should really start by testing with SMHasher, though. Best of luck.
Thanks for encouraging me to use SMHahser.
I posted the SMHasher results here: https://github.com/dosaygo-coder-0/smhasher/blob/master/tifu...
And my SMHasher fork testing tifuhash is here: https://github.com/dosaygo-coder-0/smhasher
I posted the SMHasher results here: https://github.com/dosaygo-coder-0/smhasher/blob/master/tifu...
And my SMHasher fork testing tifuhash is here: https://github.com/dosaygo-coder-0/smhasher
Maybe i ought to have just said that the title includes the qualifier, " - that's the aim anyway," reinforcing the notion that even if we don't know if tifuhash is universal, it aims to be.
So work is ongoing in that area, and you're welcome to contribute code or work on an approach to prove it is universal at some point. If you have more you'd like to contribute, you could become co author potentially.
Please try to see it like that. That's the idea I'm going for here. Thanks
So work is ongoing in that area, and you're welcome to contribute code or work on an approach to prove it is universal at some point. If you have more you'd like to contribute, you could become co author potentially.
Please try to see it like that. That's the idea I'm going for here. Thanks
Okay, I'll start with that next time, thanks
Sorry, I can only read this as "Today I Fucked Up hash"
It probably is. So what is wrong with say MurmurHash that you have to hack your own?
Yeah, it's one thing to create it for fun, but why publish it as a library for general consumption?
I strongly disagree with this idea - code should always be released! If it's good, we can avoid rewriting code and have more options for hashing, and if some people point out problems with the code, the author can learn from their mistakes and fix them if possible - they wouldn't want to use it in their private code with the mistakes.
I think this thread is more negative than the author deserves. The method of hashing is novel and could possibly lead to exploration in the area, and if not that, where else could the author post to get feedback from the author of murmurhash??
I think the only problem here is that they advertise it as production ready/universal without evidence or rigorous testing, rather than "hey, here's a cool hash I came up with."
I think this thread is more negative than the author deserves. The method of hashing is novel and could possibly lead to exploration in the area, and if not that, where else could the author post to get feedback from the author of murmurhash??
I think the only problem here is that they advertise it as production ready/universal without evidence or rigorous testing, rather than "hey, here's a cool hash I came up with."
> I strongly disagree with this idea - code should always be released!
There is a difference between releasing code, say on github, and putting it out there like it's ready for use in a production system, like in a package manager. I only said the later shouldn't be done, not the former.
Rereading, I guess that wasn't exactly what I said. I can't seem to edit now, though.
There is a difference between releasing code, say on github, and putting it out there like it's ready for use in a production system, like in a package manager. I only said the later shouldn't be done, not the former.
Rereading, I guess that wasn't exactly what I said. I can't seem to edit now, though.
Thanks for sticking up for me, rjeli, I really appreciate that!
Indeed. That claim requires hard statistics on performance on multiple platforms and statistics of the hash function itself.
The floating point hash might be useful on a CPU for example.
The floating point hash might be useful on a CPU for example.
I like making things. I want to have an impact. I want to do something new. I want people to try and use my stuff and tell me about it. So I'm achieving that today.
Make your own hash function. It's not that hard. Most non crypto hash functions are just something similar to ax + b mod p. And then there's plenty of room left for exotic ones. There's room for yours, too.
Personally I've for a long time really liked making RNGs. Many people like making them actually. For me, I always liked the feeling of getting something simple that i made create so much uncompressible apparent entropy out of so little. And i enjoy the challenge of passing the test suites for randomness. And i enjoy the feeling of making tiny mixing functions. I like the diagrams of mixing functions and ciphers. I like the aesthetics of writing that code, both that which is similar to the main habits of many ciphers, the xors, the shifts, as well as coming up with something new.
A lot of people like making hashes, and RNGs, and there are a lot of them, and a lot of good, useful and interesting ones. All made by people no smarter than me. I'm fine to get up in front of you all here and try and do something i like, and fall and succeed, and learn. I just enjoy what I'm doing. I'm creative and can come up with new things. I like doing it. Coding is one way i can express that creativity in a way that satisfies me. And i feel more satisfied when i share what i make it with others, and i have more fun when i take it more seriously.
I like a challenge. And i think i can do something good with this space. And i want to. And I'm fine to fail too. I like to succeed. And I'm fine to fail. I just like doing it.
I like doing more than i like sitting on the sidelines and commenting on other people doing, and secretly wishing i was on the field doing something too, instead of in the stands just having opinions. That always felt fake to me... Because if i secretly wanted to do what someone else was doing, I wouldn't get jealous, I'd just say to myself, how do I get that, too? Because, why not? So other peoples achievements inspired me to do, too, if i liked the same thing. If didn't like it, I wouldn't do it, but i could still enjoy it vicariously.
So that's why I do stuff and share it with others and take it seriously. Hope that answers your question.
Make your own hash function. It's not that hard. Most non crypto hash functions are just something similar to ax + b mod p. And then there's plenty of room left for exotic ones. There's room for yours, too.
Personally I've for a long time really liked making RNGs. Many people like making them actually. For me, I always liked the feeling of getting something simple that i made create so much uncompressible apparent entropy out of so little. And i enjoy the challenge of passing the test suites for randomness. And i enjoy the feeling of making tiny mixing functions. I like the diagrams of mixing functions and ciphers. I like the aesthetics of writing that code, both that which is similar to the main habits of many ciphers, the xors, the shifts, as well as coming up with something new.
A lot of people like making hashes, and RNGs, and there are a lot of them, and a lot of good, useful and interesting ones. All made by people no smarter than me. I'm fine to get up in front of you all here and try and do something i like, and fall and succeed, and learn. I just enjoy what I'm doing. I'm creative and can come up with new things. I like doing it. Coding is one way i can express that creativity in a way that satisfies me. And i feel more satisfied when i share what i make it with others, and i have more fun when i take it more seriously.
I like a challenge. And i think i can do something good with this space. And i want to. And I'm fine to fail too. I like to succeed. And I'm fine to fail. I just like doing it.
I like doing more than i like sitting on the sidelines and commenting on other people doing, and secretly wishing i was on the field doing something too, instead of in the stands just having opinions. That always felt fake to me... Because if i secretly wanted to do what someone else was doing, I wouldn't get jealous, I'd just say to myself, how do I get that, too? Because, why not? So other peoples achievements inspired me to do, too, if i liked the same thing. If didn't like it, I wouldn't do it, but i could still enjoy it vicariously.
So that's why I do stuff and share it with others and take it seriously. Hope that answers your question.
I answered the why below. Also, i didn't feel there was anything really "wrong" with others.
One motivation i had specifically apart from that paper i linked asking for a different way, was i was bored of seeing the same hash and type of code in hashes and ciphers again and again. And i had made a successful RNG, using a very simple construction, in a similar genre to this same regular genre, using the traditional operations like shifts and xors, and i felt i pretty much had nailed that type of construction to my satisfaction. So i wanted to do something different. A hash with a different aesthetic. A hash that, when you look at the code, it looks different to others.
I didn't like that i just had success in this one genre of hash or rng code, and i wanted to do something just using arithmetic operations. It annoyed me that i had never really been able to find, or make, a good hash or rng without using shifts or xors or the same boring multiply stuff. When you see enough of them, it's all just derivative... Changing constants and so on...And the choices, this xor instead of that plus, are basically arbitrary because the space of possible algorithms using similar constructions is so huge, they're really not so different to each other, just more points in the same hyperplane, and there exist still so many other algorithms to find that way, a computer could basically fill in the rest of the dots. So instead of trying to discover a new point in parameter space of constructions like that, i wanted to get back to something more pure, that was more about the essence of a different construction, rather than a few more tweaks to the same type.
Also, not just pure, but short. So many lines of shifts and xors are unnecessary...i know from deep and long experience, you don't need that much code to make so much good apparent entropy. I proved that by making a good rng, with a very simple construction. And I've written code like the sea of hashes and mixing functions hundreds of times... And really... It is like, change this shift, change this constant, change the construction, tweak until it works... But it's ask basically the same structure... It's just so boring after a while.
I'm trying to convey to you the feeling that motivated me to do it, since that is what you asked. Hope it comes across clearly.
Finally, i don't want this to come across as only a condemnation. I draw a lot of inspiration, ideas and information reading other people's ciphers, hashes, and papers. It's just, I don't want to copy the same style always. I want to diversify. I have a good mixing function in the traditional genre ( dosy, also on npm ), and I wanted to see if i could construct a good mixing function in a new aesthetic. And i have. Hooray!
Tl;dr - aesthetics. I felt bored with what i had seen and done. I wanted to discover, make and see something new.
One motivation i had specifically apart from that paper i linked asking for a different way, was i was bored of seeing the same hash and type of code in hashes and ciphers again and again. And i had made a successful RNG, using a very simple construction, in a similar genre to this same regular genre, using the traditional operations like shifts and xors, and i felt i pretty much had nailed that type of construction to my satisfaction. So i wanted to do something different. A hash with a different aesthetic. A hash that, when you look at the code, it looks different to others.
I didn't like that i just had success in this one genre of hash or rng code, and i wanted to do something just using arithmetic operations. It annoyed me that i had never really been able to find, or make, a good hash or rng without using shifts or xors or the same boring multiply stuff. When you see enough of them, it's all just derivative... Changing constants and so on...And the choices, this xor instead of that plus, are basically arbitrary because the space of possible algorithms using similar constructions is so huge, they're really not so different to each other, just more points in the same hyperplane, and there exist still so many other algorithms to find that way, a computer could basically fill in the rest of the dots. So instead of trying to discover a new point in parameter space of constructions like that, i wanted to get back to something more pure, that was more about the essence of a different construction, rather than a few more tweaks to the same type.
Also, not just pure, but short. So many lines of shifts and xors are unnecessary...i know from deep and long experience, you don't need that much code to make so much good apparent entropy. I proved that by making a good rng, with a very simple construction. And I've written code like the sea of hashes and mixing functions hundreds of times... And really... It is like, change this shift, change this constant, change the construction, tweak until it works... But it's ask basically the same structure... It's just so boring after a while.
I'm trying to convey to you the feeling that motivated me to do it, since that is what you asked. Hope it comes across clearly.
Finally, i don't want this to come across as only a condemnation. I draw a lot of inspiration, ideas and information reading other people's ciphers, hashes, and papers. It's just, I don't want to copy the same style always. I want to diversify. I have a good mixing function in the traditional genre ( dosy, also on npm ), and I wanted to see if i could construct a good mixing function in a new aesthetic. And i have. Hooray!
Tl;dr - aesthetics. I felt bored with what i had seen and done. I wanted to discover, make and see something new.
You aren't alone at all, that's exactly what I thought it was too.
You got me. There are some pretty serious issues with this.
Oh, sorry, I only understood what this comment meant after I read the child comment. Yeah, I got "Today I fucked up" from reddit's TIFU, not as a commentary on your abilities.
I think they're only saying it because TIFU is a colloquial acronym for "Today I Fucked Up" (this is how I read it too), not intending to insult your abilities.
definitely not a commentary on the work itself!
Actually "the today i ffff up hash" is a pretty cool name for tifuhash, like a backronym.
It's probably more memorable / mimetic than "tiny fast universal". And memorable wad one of my original goals, but i was referring to the source code!
As well as so many people naming it "today i ..." hash, there's the other comment saying i ought not use the technical term universal.... Maybe it works for me to take the hint and just change the name to today i fucked up hash. Somebody open a PR!
I guess future versions can be named like "Wednesday i fucked up hash"... Or maybe now I'm just getting distracted by this name.
It's probably more memorable / mimetic than "tiny fast universal". And memorable wad one of my original goals, but i was referring to the source code!
As well as so many people naming it "today i ..." hash, there's the other comment saying i ought not use the technical term universal.... Maybe it works for me to take the hint and just change the name to today i fucked up hash. Somebody open a PR!
I guess future versions can be named like "Wednesday i fucked up hash"... Or maybe now I'm just getting distracted by this name.
Thanks for saying so :)
Came here to say exactly this.
> Novel: using division, or using floating point division, and discarding the high-order-bits ( as we do here ) is not used nor studied so much, if at all, in hash construction
Is that because division is slow compared to bit operations?
Is that because division is slow compared to bit operations?
I think it's something like that, that division is slower than multiplication in the chip.
Also, a lot of hashing had to do with prime fields, and polynomials in them, and people seem to be able to do most of the maths without division. Or when they do divide, then are using powers of two, so thru can just use bit shifts, which are faster.
So there's a lot of "discrete" type math in hashing...i don't see why we couldn't have more continuous or factional math.
Afterall, Huffman coding is good, but arithmetic coding, which i believe uses fractional math, is better. Probably more hashing can be done the way that I'm doing here. So happy to find this new thing.
I'm thinking FPGA... They do floating point right? GPU? Same right? I think continued Egyptian fraction hashing could be on the up.
Also, a lot of hashing had to do with prime fields, and polynomials in them, and people seem to be able to do most of the maths without division. Or when they do divide, then are using powers of two, so thru can just use bit shifts, which are faster.
So there's a lot of "discrete" type math in hashing...i don't see why we couldn't have more continuous or factional math.
Afterall, Huffman coding is good, but arithmetic coding, which i believe uses fractional math, is better. Probably more hashing can be done the way that I'm doing here. So happy to find this new thing.
I'm thinking FPGA... They do floating point right? GPU? Same right? I think continued Egyptian fraction hashing could be on the up.
"Uses two 64 bit floating point integers for calculation"? Floating point integers?
My snarky self woke up and said "That's an appropriate name for the integer simulation of JavaScript".
I read it as "JS has no ints"
I'll correct it, thank you.
This is connected with a truly amazing website that does not make my eyes bleed in any way.
https://dosaygo.com/
https://dosaygo.com/
I'll say this though - the site is absolutely 1000% more usable than the single-page-app-that's-actually-a-document style du jour. Just tone down the colours and remove the horizontal scrollbar (put the two things one below the other). Other than that, this is definitely a motherfucking website :) ( http://motherfuckingwebsite.com/ )
Thank you for saying this. I am fond of my robust as nails site. I like that it can work on lynx. I shall take your improvement ideas under advisement.
I just grabbed the horizontal scrollbar (ThinkPad X61, no trackpad) to see what it was hiding, and slowly scrolled that part of the page over.
It felt like I'd just hand cranked a CSS animation. Kinda steampunk.
Note that I'm not dissing the author here. They appreciate the feedback they've gotten, which means they're receptive, and that's honestly a very large percentage of "this'll work out okay," which in this case means that this project will iterate until it nails something new, or the author will go join one of the other hashing efforts out there.
It felt like I'd just hand cranked a CSS animation. Kinda steampunk.
Note that I'm not dissing the author here. They appreciate the feedback they've gotten, which means they're receptive, and that's honestly a very large percentage of "this'll work out okay," which in this case means that this project will iterate until it nails something new, or the author will go join one of the other hashing efforts out there.
Thank you. Steampunk. I'm not gonna forget that!
Sort of like those elaborate pop up books where you move the paper slider to move the figure across some background. :)
Sort of like those elaborate pop up books where you move the paper slider to move the figure across some background. :)
That could definitely be improved, too. Thanks
[deleted]