# Merkle tree collision probability

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?

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.

I used Infer.Net to calculate the answer. For anyone interested, here's the code.

open MicrosoftResearch.Infer;
open MicrosoftResearch.Infer.Models
open MicrosoftResearch.Infer.Distributions
open MicrosoftResearch.Infer.Factors
open MicrosoftResearch.Infer.FSharp;
open System

let treeCollisionProb() =
let hashSize = 128
let entityCount = 512
let subRangeCount = 32

let subRangeWidth = hashSize / subRangeCount
let upperLevelChildrenCount = 2

let avgEntitiesPerRange = entityCount / subRangeCount

let hashCollision() = Variable.Bernoulli(2. ** -128.)

let nodeCollision (children:Variable<bool>[]) =
let anyChildCollision =
children
|> Array.reduce (|||)

let childHashSequenceHashCollision = hashCollision()
let parentCollisionWithoutChildCollision = ~~~anyChildCollision &&& childHashSequenceHashCollision

anyChildCollision ||| parentCollisionWithoutChildCollision

let subRange() =
[| 1..avgEntitiesPerRange |]
|> Array.map (fun i -> hashCollision())

let subRanges =
[| 1..subRangeCount |]
|> Array.map (fun i -> subRange())

let subRangeParents = subRanges |> Array.map nodeCollision

let rec constructTree (rangeWidth:int) (children:Variable<bool>[]) =
if rangeWidth = 1 then children.[0]
else
let chunks = children |> Array.chunkBySize upperLevelChildrenCount
let parents = chunks |> Array.map nodeCollision
constructTree (rangeWidth / upperLevelChildrenCount) parents

let tree = constructTree subRangeWidth subRangeParents

let engine = InferenceEngine()

let result = (engine.Infer<Bernoulli> tree).GetProbTrue()
result

[<EntryPoint>]
let main argv =
let prob = treeCollisionProb()

printfn "tree collision probability: %g" prob

let treesTillCollision = 1./prob
printfn "trees till collision: %.3g" treesTillCollision

let timeTillCollisionSec (genIntervalSec:float) = genIntervalSec * treesTillCollision

let intervalSec = 5.
let secsInYear = 365 * 24 * 60 * 60
let yearsToCollision = (timeTillCollisionSec intervalSec) / (float secsInYear)
printfn "If we generate a single tree every %.0f seconds, we'll have to wait %.4g years in average to see a collision" intervalSec yearsToCollision