Raw value collisions

[dgulotta]

There are some known collisions between the raw values of various typed values:

• 0, false, and an empty container
• 1 and true
• 56-byte strings and containers with 1 element (strings are hashed by appending the byte 1, packing groups of 7 bytes into a field element, and hashing; Merkle leaves are hashed by concatenating the key, value, and field element 1 and hashing)

At the very least, the 0 / empty container and string / container collisions should be fixed. It is worth considering whether we want to have types in the backend as well.

[artwyman]

Out of curiosity: does the hash of an empty-string collide with anything else?

The non-empty container vs. non-empty string collision Dan mentions is particularly worrying since it's most non-intuitive and abusable, since it's a collision between two things which contain actual data.

My personal view is that at the very least unrelated types shouldn't collide with each other. I.e. I'm okay with 0==false and {}==[], but not 0=={}. The design of POD1 reflected that, where all numeric types (bool/int/cryptographic) hashed the same, and string/bytes hashed the same, but they wouldn't collide with each other.. I'm not necessarily against fully-distinct types (probably with some form of tagging) but it adds some complexity which is worth discussing more deeply.

There might be relatively simple fixes here. It seems like there are changeable constants involved in most of the collisions here. Dan mentioned the string and container hashes have a prefix byte 1 - couldn't one of the types use a 2 instead? Similarly couldn't Ints be packed with non-zero values, and empty containers be represented as different nonzero values?

[dgulotta]

It should be simple to fix the collisions mentioned above. We can change the hash of the empty container to an arbitrary value and/or pad integers with something other than zeros. We compute the hash of a non-leaf Merkle tree node by appending a 2, but it should be fine to use 3 for strings.

I don't think the hash of the empty string collides with anything. All of the hash computations in containers hash 9 field elements, while the empty string would hash 1 field element.

[ed255]

In this PR #493 the handling of types for Value was changed via the exposed APIs:

• Raw is no longer a type, instead it's treated as "lack of type". All values can be casted to raw
• bool is treated like Int(0) or Int(1)
• Value now doesn't expose a type, instead it can be casted to a type, and for some values multiple casts will return Some (where some of the collisions exists). As a general rule a cast will succeed if we have the preimage information (for types that are encoded by hashing).

I believe this alleviates the issue, because now the type is not given by the Value, but instead it's a responsibility of the consumer to remember the type and cast to it.