patternMinor
Merkle tree collision probability
Viewed 0 times
probabilitycollisiontreemerkle
Problem
Say I use a perfect 128-bit hash function to construct a merkle tree.
By perfect I mean that any of the values in the $0$–$2^{128}$ range has an equal probability to be an outcome of the function, over a large enough domain of hashed entities.
Does the root have a higher collision probability than any of the leafs?
To elaborate, say that I have 1000 entities, each of which has a $p_1=1/2^{128}$ probability of colliding.
I construct the tree so that the lowest level spans the range of $2^8$ values, and upper levels span the range of two lower levels.
What is the probability of a single collision in such a tree?
What is the probability of two collisions in a single tree? $n$ collisions?
By perfect I mean that any of the values in the $0$–$2^{128}$ range has an equal probability to be an outcome of the function, over a large enough domain of hashed entities.
Does the root have a higher collision probability than any of the leafs?
To elaborate, say that I have 1000 entities, each of which has a $p_1=1/2^{128}$ probability of colliding.
I construct the tree so that the lowest level spans the range of $2^8$ values, and upper levels span the range of two lower levels.
What is the probability of a single collision in such a tree?
What is the probability of two collisions in a single tree? $n$ collisions?
Solution
Yes, the root has a higher probability of collision.
Take, for example, simple trees with two leaves. Label tree 1's leaves $A$ and $B$, and tree 2's leaves $X$ and $Y$.
The probability that the tree hashes collide at the root is the probability that $\langle h(A),h(B) \rangle \neq \langle h(X),h(Y)\rangle \land h(h(A)||h(B)) = h(h(X)||h(Y))$ plus the probability that $\langle h(A),h(B) \rangle = \langle h(X),h(Y)\rangle$. The probability of the second part is $p^{-2}$ and the probability of the first is $p^{-1}(1-p^{-2})$, for a total of $p^{-1} + p^{-2} - p^{-3}$, which is slightly greater than $p^{-1}$, the probability of a single collision.
That assumes all of your leaves have different values. If the leaves are all the same but one, the probability of collision at the root is proportional to the logarithm (base 2) of the number of leaves times the collision probability of the underlying hash function.
Take, for example, simple trees with two leaves. Label tree 1's leaves $A$ and $B$, and tree 2's leaves $X$ and $Y$.
The probability that the tree hashes collide at the root is the probability that $\langle h(A),h(B) \rangle \neq \langle h(X),h(Y)\rangle \land h(h(A)||h(B)) = h(h(X)||h(Y))$ plus the probability that $\langle h(A),h(B) \rangle = \langle h(X),h(Y)\rangle$. The probability of the second part is $p^{-2}$ and the probability of the first is $p^{-1}(1-p^{-2})$, for a total of $p^{-1} + p^{-2} - p^{-3}$, which is slightly greater than $p^{-1}$, the probability of a single collision.
That assumes all of your leaves have different values. If the leaves are all the same but one, the probability of collision at the root is proportional to the logarithm (base 2) of the number of leaves times the collision probability of the underlying hash function.
Context
StackExchange Computer Science Q#55087, answer score: 4
Revisions (0)
No revisions yet.