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 = 
            |> 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] 
            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()

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

    Console.ReadLine() |> ignore

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.