Potential hash collision by using v8::Module::GetIdentityHash()

[ry]

https://github.com/denoland/deno/blob/1e5e091cb074896c7550b1b6f802582f12629048/libdeno/binding.cc#L293

Seems very unlikely people will hit this issue - but creating something just to track it.

[harthur]

I came across this when searching for other projects having issues with GetIdentityHash. Circling back around just to say that I found out it's only 21 bits now, so we in another project were having issues with collisions in just hundreds of instances.

[ry]

Ok thanks - good to know.

[zbendefy]

Hi! Is there an estimate on this issue? We're using GetIdentityHash() to identify objects, and we would like to know if we can rely on it or not.

[ry]

@zbendefy I've had no problems with it.

[zbendefy]

@ry We'll use potentially thousands of objects, that we are identifying (for storage in a hashmap) using GetIdentityHash(). We didn't do thorough testing yet, but having a Stable way to identify JS objects would be nice.

I presume that we cannot use the underlying pointer values behind a Local<> or Persistent<> handle?

[lucacasonato]

@ry Is this still relevant?

[ry]

Yes

[kitsonk]

These bindings are now in rust_v8 so I moved it.

[bnoordhuis]

This is not for rusty_v8 to fix. The identity hash itself isn't buggy but it can be used in a way that introduces bugs.

To summarize:

1. An object's identity hash is a 21 or 22 bits random number (on 32 and 64 bits architectures respectively)

2. Per the Birthday Paradox, that means the chance of a collision is > 50% with approx. 1700 or 2400 objects.

You can use it to store objects in a hashmap but you need to additionally check with a.same_value(b) if the object already exists in the hashmap bucket.