Introduce Crystal::Hasher for computing a `hash` value #4946

asterite · 2017-09-10T22:16:24Z

This PR is a preparation to better implement the hash method for Crystal objects.

Instead of asking types to implement hash, we now provide a default implementation and ask subclasses to implement hash(hasher). A hasher provides a safe way to compute a hash, and can also compute a different value for the same program at different runs to prevent DoS attacks. So this fixes #2817

The current implementation lives in Crystal::Hasher and it's not public. The idea is not to leak this information. For example in Ruby you can't pass a hasher to methods, and you can't choose a hasher. This is all decided by Ruby's runtime, and hidden, and this is good because it removes the burden from the user.

The implementation here is safe(r) because it randomizes the initial hash value. However, I'm sure we could use SipHash or FNV or some other algorithm. But this is just a start. Next PRs should just touch Crystal::Hasher (and probably BigInt and others because the hash is not correct there).

Fixes #2817
Fixes #4578

asterite · 2017-09-10T22:18:03Z

This implements the code organization part of #4675 but not the actual "good" implementation. But this PR is simpler to review.

asterite · 2017-09-10T22:18:17Z

Also fixes #4578

RX14 · 2017-09-10T22:52:31Z

@asterite I don't think "fixes #foo" outside the main PR body actually gets github to close the issues (you can actually see on the issue page if a PR will close it now, which is cool)

asterite · 2017-09-10T22:55:24Z

@RX14 Thanks, updated!

RX14 · 2017-09-10T23:18:46Z

src/crystal/hasher.cr

+  end
+
+  def float(value)
+    @value = @value * 31 + value.to_f64.unsafe_as(UInt64)


I think we should use this on the floats.

We can leave it for a next PR

There's a big todo at the top of the struct. On fact in this PR I could have used zero as a seed, but I wanted to see that it worked with it.

I know what you are asking is not exactly covered by the above TODO. Still, I'd like to tackle these issues one at a time. After we merge this, I'll probably wait for someone (you? :-)) to use float normalization, though I'll require a test to see why it's needed. Then another PR can tackle another (better) hash algorithm, etc.

canonicalize is OK, but implementation proposed by @funny-falcon (PyHash inspired) is more robust and generic normalization that takes in care canonicalization too. Will propose it as separate PR.

bcardiff

I like how the pattern take advantage of the struct and chain the results. 💙

It's a pity that all the methods in the hasher have a value argument that hide the getter of the sole ivar @value. 🤷‍♂️

ysbaddaden

Looks great, and it avoids pointers. Now I'd love to see halfsiphash and siphash hashing!

straight-shoota

I'd suggest to add add a simple explanatory doc string to each hash(hasher) implementation, similar to the one in the example for def_hash: Define a `hash(hasher)` method based on @name and @age.
At least all the obsolete documentation should be updated or removed.

straight-shoota · 2017-09-11T09:05:03Z

src/enum.cr

-  # Returns a hash value. This is the hash of the underlying value.
-  def hash
-    value.hash
+  def hash(hasher)


Missing doc

I'll add a "See Object#hash(hasher) to all of these

straight-shoota · 2017-09-11T09:05:12Z

src/float.cr

@@ -86,6 +86,10 @@ struct Float
    end
  end

+  def hash(hasher)


Missing doc

straight-shoota · 2017-09-11T09:09:16Z

src/hash.cr

-  # ```
-  def hash
-    hash = size
+  def hash(hasher)


Missing doc

straight-shoota · 2017-09-11T09:10:19Z

src/bool.cr

@@ -42,8 +42,8 @@ struct Bool
  end

  # Returns a hash value for this boolean: 0 for `false`, 1 for `true`.


These fixed hash value should be removed.

straight-shoota · 2017-09-11T09:10:56Z

src/char.cr

@@ -415,8 +415,8 @@ struct Char
  end

  # Returns this char's codepoint.


This doc string is no longer correct.

straight-shoota · 2017-09-11T09:17:10Z

src/xml/namespace.cr

-  def hash
-    object_id
-  end
+  def_hash object_id


Missing doc

straight-shoota · 2017-09-11T09:17:18Z

src/xml/node.cr

-  def hash
-    object_id
-  end
+  def_hash object_id


Missing doc

straight-shoota · 2017-09-11T09:17:25Z

src/xml/node_set.cr

-  def hash
-    object_id
-  end
+  def_hash object_id


Missing doc

straight-shoota · 2017-09-11T09:17:33Z

src/yaml/any.cr

-  def hash
-    raw.hash
-  end
+  def_hash raw


Missing doc

straight-shoota · 2017-09-11T09:18:39Z

src/json/any.cr

-  def hash
-    raw.hash
-  end
+  def_hash raw


Missing doc

akzhan · 2017-09-11T09:57:11Z

spec/std/float_spec.cr

@@ -206,11 +206,13 @@ describe "Float" do

  describe "hash" do
    it "does for Float32" do
-      1.2_f32.hash.should_not eq(0)
+      1.2_f32.hash.should eq(1.2_f32.hash)
+      1.2_f32.hash.should_not eq(1.3_f32.hash)


this expectation is wrong in common case.

I'll remove this then. Thanks

akzhan · 2017-09-11T09:57:24Z

spec/std/float_spec.cr

    end

    it "does for Float64" do
-      1.2.hash.should_not eq(0)
+      1.2.hash.should eq(1.2.hash)
+      1.2.hash.should_not eq(1.3.hash)


akzhan · 2017-09-11T10:01:08Z

src/crystal/hasher.cr

+  end
+
+  def float(value)
+    @value = @value * 31 + value.to_f64.unsafe_as(UInt64)


canonicalize is OK, but implementation proposed by @funny-falcon (PyHash inspired) is more robust and generic normalization that takes in care canonicalization too. Will propose it as separate PR.

asterite · 2017-09-11T12:18:45Z

I forced pushed a few fixes (maybe next time I'll add more commits so it's simpler to review)

@bcardiff I changed the instance variable name of Hasher to result to avoid this confusion
@straight-shoota I added some basic docs, just "See Object#hash(hasher). Maybe these docs should actually be hidden, but it's not a big deal
@akzhan I removed those hash.should_not eq specs

I also changed one spec that would randomly fail. This is when a hash has the values, for example, 1 and 1.0 as keys. Their value are equal and their hash value, depending on the initial hasher's seed, could result equal, and so could result equal for Hash. This is wrong and should probably be improved. We will probably have to introduce an eql? or equal_for_hash method, similar to Ruby, where 1 == 1.0 is true but 1.eql?(1.0) is false. Another way would be to hardcode this logic in Hash, though it gets tricky when these values are nested inside other values. Maybe def_equals can also automatically define eql?. In any case, this discussion belongs to a different issue.

akzhan · 2017-09-11T12:24:42Z

when values are equal, their hashes should be equal too (as documented in Crystal documentation, and it's implemented in Python).

This is number normalization that was introduced by #4675 pull request, and will be proposed again later (just grep for hash_normalize in that PR or see for https://github.com/crystal-lang/crystal/pull/4675/files#diff-7eb0dd478a501936778ce47c2e9cde49 and https://github.com/crystal-lang/crystal/pull/4675/files#diff-0de55713d46889d8ddd209fcf1f6f120R161).

RX14 · 2017-09-11T13:14:47Z

@asterite === and eql? are probably the wrong names for what I consider to be internal functions. equal_for_hash and equal_for_case are better names I think.

Although i think that @akzhan's recommendation is probably better.

asterite · 2017-09-11T13:35:48Z

@RX14 @akzhan I don't see how float normalization will solve that particular issue. Care to explain?

akzhan · 2017-09-11T14:39:19Z

Number::Normalize returns same hashes for same values. 1.hash, 1.0.hash, 1.to_big_f.hash etc. always be equal with number normalization пн, 11 сент. 2017 г. в 16:35, Ary Borenszweig <notifications@github.com>:

…

@RX14 <https://github.com/rx14> @akzhan <https://github.com/akzhan> I don't see how float normalization will solve that particular issue. Care to explain? — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#4946 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAG3hNPGgpVHChbYtKBW_mlJyFDJDy1wks5shTc2gaJpZM4PSeU3> .

RX14 · 2017-09-11T14:50:21Z

The distinction is between float normalization which transforms a float into an unambiguous bitpattern, and number hash normalization which generates a unique hash from a unique numerical value. I guess thats why LLVM uses canonicalization to refer to the former. We should do the same.

asterite · 2017-09-11T14:54:25Z

But hash normalization for numbers will make this problem worse, because 1 and 1.0 will have the same hash value and because 1 == 1.0 a Hash can't distinguish them. So this:

{1 => 'a', 1.0 => 'b'}

will end up being:

{1.0 => 'b'}

because the second key replaces the first one, they are indistinguishable.

One way for that to work is not to use == to compare them, but use .eql? or equals_for_hash.

RX14 · 2017-09-11T14:57:37Z

@asterite What we were suggesting is exactly that behaviour: you cannot insert two "ones" into a hash - regardless of their representation.

asterite · 2017-09-11T15:17:50Z

@RX14 Sounds good for now. I don't think it's consistent with union types, but we can delay this "issue" (if it is one) for later.

asterite · 2017-09-11T17:42:29Z

Merged!

Feel free to open issues regarding number normalization and using other hashing algorithms, or correct hash values for big numbers.

oprypin · 2017-09-11T19:17:27Z

@asterite, see #2818 for why normalization is so important

oprypin · 2017-09-11T19:23:23Z

In fact, as I understand it, now numbers of two different types like {1 => 'a', 1.0 => 'b'} can undeterministically with a very low probability have the same hash causing {1.0 => 'b'}

oprypin · 2017-09-11T19:32:04Z

src/crystal/hasher.cr

+  # TODO: the implementation is naive and should probably use
+  # another algorithm like SipHash or FNV.
+
+  @@seed = uninitialized UInt64


@@seed = Random::System.rand(UInt64::MIN..UInt64::MAX) with #4894

It breaks the compiler at all with compiler bug inside. I don't know why :)

But I'll pull request with Random::Secure.

oprypin · 2017-09-11T19:38:39Z

src/crystal/hasher.cr

+  end
+
+  def float(value)
+    @result *= @result * 31 + value.to_f64.unsafe_as(UInt64)


Is this *= intended?

oprypin · 2017-09-11T19:39:56Z

I really dislike that this got merged in only 19 hours. I didn't have the opportunity to see it.

asterite · 2017-09-11T19:48:07Z

@oprypin Don't worry, this is not the final code. This just introduces Hasher as a unified way to compute a hash. I think providing a hash(hasher) method that objects must implement to append a hash value is the way to go. But do you think there's a different way to do it?

oprypin · 2017-09-11T19:50:21Z

The general idea is fine, if not the most elegant. In this case it's more about the small things (please re-check that *=!)

akzhan · 2017-09-11T20:30:34Z

@asterite

@oprypin Don't worry, this is not the final code. This just introduces Hasher as a unified way to compute a hash. I think providing a hash(hasher) method that objects must implement to append a hash value is the way to go. But do you think there's a different way to do it?

I'm sorry, but @funny-falcon code was the same in terms of 'final', but a lot better. Your things are great, but now we should repeat all of its great proposals. Ok.

asterite · 2017-09-11T20:44:58Z

@akzhan Maybe, but I don't think so. That PR adds a hash_normalize methods to numbers, but I don't think that's correct. That will only be used to implement hash, so it should be in Hasher.

It also introduces Number::HashNormalize type. That belongs in Hasher too. unseeded is not useful either. It also changes StringPool, I don't know why.

Anyway, it had a lot more code than what was needed. And it was so big it received many comments until the author got tired. I think it's better to do this by little steps.

ysbaddaden · 2017-09-12T12:54:05Z

BTW: I ported SipHash and made a streaming version:
https://gist.github.com/ysbaddaden/d51c66bc8e07d193ecbb9f7620be8ef5

In terms of performance, computing the hash in one bulk was on par with the official C implementation. Streaming the input adds a ~20% overhead, because the state must be regularly updated.

key = uninitialized UInt8[16]
SecureRandom.random_bytes(key.to_slice)

hasher = SipHash64(1, 3).new(key)
hasher.update("some ")
hasher.update("incoming ")
hasher.update("data ")
hasher.final # => UInt64

ysbaddaden · 2017-10-10T13:47:03Z

BTW again: I published a shard for SipHash and HalfSipHash: https://github.com/ysbaddaden/siphash.cr

RX14 · 2017-10-10T20:38:30Z

@ysbaddaden any reason why this isn't a PR to replace the default implementation? I think SipHash13 should be the default (perhaps only) hasher.

akzhan · 2017-10-10T21:06:34Z

Yes, it may be good proposal (but @funny-falcon one is better for LLVM i suppose).

Anyway I don't try to propose any implementation until pushed number normalization.

akzhan · 2017-10-10T21:10:34Z

And please leave result instead of final, there are no reasons to change the naming.

asterite added kind:feature kind:refactor topic:stdlib labels Sep 10, 2017

asterite self-assigned this Sep 10, 2017

faustinoaq mentioned this pull request Sep 10, 2017

change computation of hash value. #4675

Closed

RX14 requested changes Sep 10, 2017

View reviewed changes

RX14 approved these changes Sep 11, 2017

View reviewed changes

bcardiff approved these changes Sep 11, 2017

View reviewed changes

ysbaddaden approved these changes Sep 11, 2017

View reviewed changes

straight-shoota requested changes Sep 11, 2017

View reviewed changes

akzhan reviewed Sep 11, 2017

View reviewed changes

Introduce Crystal::Hasher for computing a hash value

c4114db

asterite merged commit f9237fd into crystal-lang:master Sep 11, 2017

asterite deleted the refactor/hash branch September 11, 2017 17:43

oprypin reviewed Sep 11, 2017

View reviewed changes

akzhan mentioned this pull request Oct 10, 2017

Use Random::Secure with Crystal::Hasher. #5097

Merged

akzhan mentioned this pull request Oct 20, 2017

Reimplementation a Hash using open addressing #4557

Closed

		@@ -42,8 +42,8 @@ struct Bool
		end

		# Returns a hash value for this boolean: 0 for `false`, 1 for `true`.

		@@ -415,8 +415,8 @@ struct Char
		end

		# Returns this char's codepoint.

Introduce Crystal::Hasher for computing a hash value #4946

Introduce Crystal::Hasher for computing a hash value #4946

Conversation

asterite commented Sep 10, 2017 • edited

asterite commented Sep 10, 2017

asterite commented Sep 10, 2017

RX14 commented Sep 10, 2017

asterite commented Sep 10, 2017

RX14 Sep 10, 2017 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

bcardiff left a comment

Choose a reason for hiding this comment

ysbaddaden left a comment

Choose a reason for hiding this comment

straight-shoota left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

asterite commented Sep 11, 2017 • edited

akzhan commented Sep 11, 2017 • edited

RX14 commented Sep 11, 2017 • edited

asterite commented Sep 11, 2017

akzhan commented Sep 11, 2017 via email

RX14 commented Sep 11, 2017

asterite commented Sep 11, 2017

RX14 commented Sep 11, 2017

asterite commented Sep 11, 2017

asterite commented Sep 11, 2017

oprypin commented Sep 11, 2017

oprypin commented Sep 11, 2017

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

oprypin commented Sep 11, 2017 • edited

asterite commented Sep 11, 2017

oprypin commented Sep 11, 2017 • edited

akzhan commented Sep 11, 2017

asterite commented Sep 11, 2017

ysbaddaden commented Sep 12, 2017

ysbaddaden commented Oct 10, 2017

RX14 commented Oct 10, 2017

akzhan commented Oct 10, 2017

akzhan commented Oct 10, 2017 • edited

Introduce Crystal::Hasher for computing a `hash` value #4946

Introduce Crystal::Hasher for computing a `hash` value #4946

asterite commented Sep 10, 2017 •

edited

RX14 Sep 10, 2017 •

edited

asterite commented Sep 11, 2017 •

edited

akzhan commented Sep 11, 2017 •

edited

RX14 commented Sep 11, 2017 •

edited

oprypin commented Sep 11, 2017 •

edited

oprypin commented Sep 11, 2017 •

edited

akzhan commented Oct 10, 2017 •

edited