Risks of hash collisions due to Int encoding

[artwyman]

Context:

This is a spin-off of #426 for a deeper discussion of a related issue. #426 is mostly about the specific constants chosen in value hashing, and could be fixed by changing that constants. In this issue I want to prompt a broader discussion about the encoding of Ints direclty in a RawValue without hashing. I think that might have security implications which are worth exploring. I have 2 risks in mind which I'll document below. I welcome input on whether each of them is real and worth worrying about.

I'm coming at this largely from the direction that any ability to construct hash collisions is dangerous, and we need to ensure doing so is hard within some number of bits of security. I don't have specific vulnerabilities in mind, but could try to come up with some if it would be helpful. I'm also not sure of the specific security level we assume from our Poseidon hash against specific attacks - I'd appreciate input there.

Int Encoding:

I'll restate the details as I understand them, mostly based on documentation, so please correct any mistakes here:

• Raw values are represented as 4 Goldilocks field elements containing ~256 bits (~64 bits each). I'll write these little-endian as (h0, h1, h2, h3)
• In most cases there are the result of a Poseidon hash which we assume to be strong, with some number of effective bits of security N<256
• Integers of 64 bits are not hashed, but are instead embedded directly in a raw value as (i0, i1, 0, 0) where i0 and i1 are the lowest and highest 32 bits of the integer, and the two constant 0s could be any other arbitrary constant.

This encoding of ints has obvious efficiency benefits of not requiring circuits to take extra inputs or verify hashes in order to prove statements like SumOf and Lt

Risk 1:

Since int-encoding is known, and 2 of the 4 elements are known, it becomes easier to construct a hash collision between an Int and some other type. For instance, if I can somehow find a String whose hash is (s0, s1, 0, 0) I immediately know how to construct a colliding Int. Thus if we think our Poseidon hash is collision-resistant with N bits of effective security, this approach to integer encoding reduces that to N/2, at least for any attack involving colliding an Int against some other type.

Is N/2 good enough? That's where I'd like to have more input or pointers from people who understand the math and security of Poseidon better. My surface-level logic is that if N/2 were good enough, we'd have picked a RawValue type with 2 field elements instead of 4, and saved a lot of circuit space.

Risk 2:

This risk isn't about direct hash collisions, but about the related collisions of key in a Merkle Tree.

The int encoding above interacts further with the encoding of Sparse Merkle Trees for containers (Dict/Set/Array), documented here. The path through the tree is fixed by the bits of the raw value in little-endian order, up to some max (usually 32 in our use cases). Note that leaves of the Merkle tree are always hashed in full, so a collision of the 32 key bits doesn't allow construction of false proofs. But it means that 2 values which share the same lowest 32 bits cannot be contained in the same Merkle tree.

For Int values, that means the lowest 32-bit bits of the integer directly determine its path in the tree. Since they're in reverse order, this gives the nice property that sequential integers (such as the indexes into an array) result in a perfectly balanced tree. However it also means that certain integer values can never be present as keys in the same container (Dict/Set). E.g. a Set of Ints cannot contain 0x0 and 0x100000000.

This can happen by accident, and be quite unexpected in a POD-based system. Integers aren't randomly distributed, so the likelihood of this happening will depend on the specifics of a given use case.

Furthermore, as an attacker, if I know the value of one element in a Set, it's easy for me to construct another value which cannot be inserted into the same Set without causing all future proofs to fail. This could result in a denial-of-service effect in some scenarios. E.g. imagine a PODB service which cannot accept a proven-valid request to insert data.

This is the kind of "sharp edge" which would cause me to avoid using Ints as keys when designing a system, which would eliminate certain possible designs. That may be sufficient to avoid problems if everyone does the same, but it means a part of the system's expressiveness isn't really usable.

[tideofwords]

We have to worry about two kinds: hash-hash collisions and hash-int collisions.

Hash-hash collisions: there are 2^256 possible hash values, but since a birthday attack runs in square-root time, it takes ~2^128 time to find a hash-hash collision. This is the standard 128 bits of security.

By the way, the reason it's 2^128 is basically this: you store all the hashes you've come across already. So once you've stored 2^128 hashes, at each step, there is a 1 in 2^128 chance you will hit a hash you've already seen. The more hashes you have stored, the higher this probability gets...

Hash-int collisions: There are 2^64 possible ints. If you ever find a hash that is equal to one of them, you have a problem. But the list of 2^64 ints never grows. So every hash has a 1 in 2^192 chance of colliding with an int. So you expect to have to try 2^192 hashes before you find a hash-int collision.

So it's actually harder to find a hash-int collision than a collision between two hashes. And this is why we weren't worried about ints.

[artwyman]

Thanks for recalling that analysis. I think that makes me think Risk #1 isn't an issue, though Risk #2 remains unaddressed. A few additions from direct conversations which are worth capturing for group understanding:

• My surface analysis missed the fact that the two 32-bit limbs of ints don't fully fill the last 2 field elements. There are only 2^64 ints, so to find one you need to find a hash with 2^192 bits of zeroes, not 2^128 as I stated above.
• The birthday attack means our benchmark for security is 128 bits already. Importantly the attacks on the two types of collisions don't combine in a dangerous way. You can check for both after each hash/guess but the chance of finding a hash-int collision at 2^-192 is smaller than 2^-128 by a large enough margin to not meaningfully change the probabilities. Your list of stored hashes never makes the chance of a hash-int collision larger.

For future reference, the argument above would change if we started to use more space for non-hashed raw types, such that the total became meaningful compared to 2^128 (sqrt(total_bits) if we changed that). E.g. we probably shouldn't try to encode a 128-bit integer or quad-precision floating-point in a similar way.

I'd still like to discuss the fallout of Risk #2 above (Merkle container collisions) if anyone has thoughts.

[ed255]

About Risk 2:

I think in some initial design we thought it'd be great to hash the keys in Dicts and Sets (to derive the merkle path) so that they are uniformly distributed and collisions become less common. At the same time we found it very interesting to use integers in little endian to derive paths to get perfectly balanced trees. In the circuit implementation we don't distinguish Dicts, Sets and Arrays, so we ended up never hashing keys.

I would like to break Risk 2 into two categories:

Risk 2 with honest user

This would be the case of a user picking values that become keys of the container Merkle Tree in a non-malicious way.

As @artwyman points out, choosing depth=32 will cause a set with values 0x0 and 0x100000000 to not be provable in the circuit. I think this is a severe issue. Using hashed integers should solve this; and there would be two ways to approach it: either hash an integer to construct the RawValue, or hash it in the Merkle Tree operation. Nevertheless by hashing these integers we lose the property of balanced trees when using integers... I wonder if we could have both at the same time without complicating too much the design / implementation.

Risk 2 with malicious user

In this case the user is actively trying to find collision of the 32 first bits of the RawValue of the key in order to make a merkle tree that can't be proved with depth=32. It's trivial to find collisions with integer keys in our current implementation, but even with hashing, this is just a 32 bit attack for depth=32. So hashing integers doesn't solve this, only increasing the depth solves this, and increasing the depth grows the circuit for a situation that doesn't happen most of the time. I think we considered the kinds of attacks that a malicious user that finds key collisions could do, and we concluded that it wasn't "too bad", but perhaps we should revisit that.

For example I can imagine the following scenario: an AD system has commitments to some operations, and from them we build an index. A user manages to send two operations that appear in the commitments, and they will cause a 32 bit collision when building the index; so the index suffers a DoS as it can't advance anymore once it goes through the second operation of this malicious user.

[artwyman]

Nevertheless by hashing these integers we lose the property of balanced trees when using integers... I wonder if we could have both at the same time without complicating too much the design / implementation.

1. Adding an extra layer of hashing to Merklization only for integers is an interesting idea. I think we'd need to think more about the edge cases of what a malicious prover could do when a single Merkle leaf could be interpreted in 2 different ways (as a raw value which is the hash of some other value, or as the hash of an integer). Hopefully a strong hash means such cases aren't attackable, but it feels iffy.

2. If the balanced property is primarily about Arrays (not arbitray Dicts/Sets with user-defined integer keys), we might define the desugaring of Array -> Container to use a different type of hashing for keys. This could be exposed in the TypedValue system. Imagine an Integer type which was hashed (for less likely collisions of arbitrary values) and a Counter type which is unhashed (for use with small sequential values). An Array would be a Container with Counter keys. Counter values would also be most efficient for use with SumOf, Lt, etc. I feel like having two full types adds a lot of complexity, though, so I don't fully support this suggestion. It's just a point to ponder for now.

For example I can imagine the following scenario: an AD system has commitments to some operations, and from them we build an index. A user manages to send two operations that appear in the commitments, and they will cause a 32 bit collision when building the index; so the index suffers a DoS as it can't advance anymore once it goes through the second operation of this malicious user.

That's a good point. In my thinking through ADs interacting with clients and with other ADs, I've tried to reason through what happens when a request is rejected. I think in the presence of race conditions you can't guarantee that any valid request will always be accepted, but it should generally be possible for an AD to prove either that it accepted a request (and updated state), or prove that the request was invalid when applied to the current state. That second option might not be available if there are value combinations which simply cannot be proven.