Pedersen Hash Collision Resistance

The Pederson hash function Pederson(D,M) is defined on a personalization input, D, and a the message, M, that we want to hash. According to the zcash protocol document the Pedersen hash has the following collision properties:

I would like to first confirm my understanding of the the above statement:

  1. There is no way to cause a collision between Pedersen(D,M) and Pedersen(D’,N) where D not equal D’ for all M,N
  2. If someone knew the personalization input D he can use use a message N with a different length than M to cause a collision (i.e Pedersen(D,M) = Pedersen(D,N)

Suppose we had a commitment scheme where the Pedersen hash is used to hash the note into a commitment. In this scheme, a user would prove ownership of the commitment on the Merkle tree by proving that he has a note that hashes to the commitment. Would it not be possible in such a scheme for an attacker to falsely prove that he has a note that hashes to a commitment on the Merkle tree. He would need to create a fake note with a different length than the real note and by #2 he can cause a collision.

If the above is possible how does the zcash protocol protect against such an attack?

1 Like

1 and 2 are correct. 1 is a stronger property than the spec claims. The spec claims nothing about collisions across different personalisations. If the hash were allowed to take zero-length inputs, then those would have the same hash for different personalisations, but actually it’s only defined on nonzero-length inputs. It is possible to prove --although it isn’t proven in the spec-- that for such inputs, property 1 holds based on hardness of discrete log in the random oracle model (for BLAKE2b as the random oracle).

The Zcash protocol never uses the hash with a variable-length input.

2 Likes

Note that if you want to use this hash for variable-length inputs, it is sufficient to prefix (not suffix) the input with a fixed-length encoding of the length.

2 Likes

Thank you for your reply Daira,

You say, “The Zcash protocol never uses the hash with a variable-length input” but would it be possible for an attacker to somehow modify his input to the Pedersen hash to change its length. Is there a length check in the proof protocol to prevent this?

2 Likes

No that would not be possible. There doesn’t need to be an explicit check, because all inputs to the Pedersen hash and to the Pedersen commitments are constructed from fixed-length field encodings.