Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Hashing

samwho.dev

Post reply on HN
Print view View original

31–40 of 68 posts

Re: Hashing

#31

Post by samwho »

ComputerGuru wrote: post #29

Great intro to hashing but if the concept of mmhash3’s seed is going to be brought up I think it’s only natural to mention its design limitations and why you still need something actually ddos resistant like SIP hash (even if we don’t get into the details of the latter). Also, it’s important to distinguish between hashing, hashing, and hashing. That is, hashing to map input to buckets, hashing to obscure the original…

I did have the distinction between cryptographic and non-cryptographic in there originally but found when junior folks read it they’d get confused about which use-case was being discussed. So I decided to focus on just one. With more time, I would have liked to cover at least scrypt.

I’ll be honest, I don’t know what the design limitations of the seeding in murmur3 are. What I wanted to show is the concept of seeding and what it’s there to prevent. I’m hoping that comes across, even without any deeper exploration of seeding.

Re: Hashing

#32

Post by ComputerGuru »

aappleby wrote: post #30
ComputerGuru wrote: post #29

Great intro to hashing but if the concept of mmhash3’s seed is going to be brought up I think it’s only natural to mention its design limitations and why you still need something actually ddos resistant like SIP hash (even if we don’t get into the details of the latter). Also, it’s important to distinguish between hashing, hashing, and hashing. That is, hashing to map input to buckets, hashing to obscure the original…

If I ever write Murmur4 it's going to be the smallest function that I can prove (via sat solver) to have no seed-independent collisions :D

I approve of the use of relative metrics, Austin! Just be prepared for mmhash4 to be a few megabytes in size ;)

Re: Hashing

#33

Post by ComputerGuru »

samwho wrote: post #31
ComputerGuru wrote: post #29

Great intro to hashing but if the concept of mmhash3’s seed is going to be brought up I think it’s only natural to mention its design limitations and why you still need something actually ddos resistant like SIP hash (even if we don’t get into the details of the latter). Also, it’s important to distinguish between hashing, hashing, and hashing. That is, hashing to map input to buckets, hashing to obscure the original…

I did have the distinction between cryptographic and non-cryptographic in there originally but found when junior folks read it they’d get confused about which use-case was being discussed. So I decided to focus on just one. With more time, I would have liked to cover at least scrypt. I’ll be honest, I don’t know what the design limitations of the seeding in murmur3 are. What I wanted to show is the concept of seeding…

Seeding is kind of a hack. It doesn’t guarantee you’ll avoid a (or even the same) collision, and quite a few “popular” hashes only change the output (but don’t change whether or not there is a collision) when you change the seed.

Thanks for the article, though!

Re: Hashing

#34

Post by samwho »

ComputerGuru wrote: post #33
samwho wrote: post #31

Earlier quoted context omitted.

I did have the distinction between cryptographic and non-cryptographic in there originally but found when junior folks read it they’d get confused about which use-case was being discussed. So I decided to focus on just one. With more time, I would have liked to cover at least scrypt. I’ll be honest, I don’t know what the design limitations of the seeding in murmur3 are. What I wanted to show is the concept of seeding…

Seeding is kind of a hack. It doesn’t guarantee you’ll avoid a (or even the same) collision, and quite a few “popular” hashes only change the output (but don’t change whether or not there is a collision) when you change the seed. Thanks for the article, though!

Ahh I see, the limitation you’re talking about is that there isn’t any inherent guarantee that a different seed will mean two values no longer collide? It’s just likely (in the case of murmur3 at least).

Re: Hashing

#35

Post by ComputerGuru »

samwho wrote: post #34
ComputerGuru wrote: post #33

Earlier quoted context omitted.

Seeding is kind of a hack. It doesn’t guarantee you’ll avoid a (or even the same) collision, and quite a few “popular” hashes only change the output (but don’t change whether or not there is a collision) when you change the seed. Thanks for the article, though!

Ahh I see, the limitation you’re talking about is that there isn’t any inherent guarantee that a different seed will mean two values no longer collide? It’s just likely (in the case of murmur3 at least).

Yes, but it's not just that there's only "a chance" that the collision is avoided - that would be enough if it was actually just a random probability (after all, everything about hashing and collisions - in the best textbook case - is just chance). The problem is that there are methods for obtaining what we call "seed-independent collisions" where by analyzing the hashing algorithm itself you can actually determine a priori values that will collide regardless of the seed.

If you have half an hour to spare, I really recommend you take the time to read this: http://emboss.github.io/blog/2012/12/14/breaking-murmur-hash...

Re: Hashing

#36

Post by samwho »

ComputerGuru wrote: post #35
samwho wrote: post #34

Earlier quoted context omitted.

Ahh I see, the limitation you’re talking about is that there isn’t any inherent guarantee that a different seed will mean two values no longer collide? It’s just likely (in the case of murmur3 at least).

Yes, but it's not just that there's only "a chance" that the collision is avoided - that would be enough if it was actually just a random probability (after all, everything about hashing and collisions - in the best textbook case - is just chance). The problem is that there are methods for obtaining what we call "seed-independent collisions" where by analyzing the hashing algorithm itself you can actually determine a…

Oh damn, I didn’t know that. Have bookmarked that post, thank you so much for your comments. I’ve been very fortunate in my writing that the comment sections are always full of people with awesome insight that I missed during my own reading on the topic.

Re: Hashing

#37

Post by dahart »

Solvency wrote: post #24
dahart wrote: post #19

Earlier quoted context omitted.

> You can use LSHs […] to help with nearest neighbor searches. Yes! A good example of this in graphics is a spatial nearest neighbor search. Space filling curves like the Morton and Hilbert curves are often used as hash functions that can preserve some amount of locality for 2-D / 3-D / N-D points. A locally sensitive hash function can basically be used to provide a sort key for data that doesn’t otherwise have a key…

The OP mentioned murmur3 due to its speed and high avalanche effect. So what's the best LSH function for this use case?

Hi I’m not sure I understand the question. Avalanche and local sensitivity are opposing goals, so typically the more avalanche, the less locally sensitive, and vice versa. You could even state the avalanche goal as being locally insensitive - the whole idea of avalanche is one bit change in the input produces a maximally different and uniformly distributed output.

Re: Hashing

#38

Post by mpartel »

Excellent work, again! Your intros somehow elicit the best out of HN too: the comments are always full of interesting angles and variations.

Wanna do quaternions next? :) Many have tried..

Re: Hashing

#40

Post by samwho »

mpartel wrote: post #38

Excellent work, again! Your intros somehow elicit the best out of HN too: the comments are always full of interesting angles and variations. Wanna do quaternions next? :) Many have tried..

There’s a name I haven’t heard for a long time.

Thank you, sir! As soon as I can reliably spell “quaternions” I will think about trying it.

Funnily, one of the ideas I have cooking in my head is going to require a foray into 3D.

Post reply on HN