Analysis of collision probability in Merkle trees in the random oracle model

This work analyzes the probability of collisions in Merkle graphs, with a focus on a specific class of attacks in balanced Merkle trees. To provide a tractable model, each hash function is modeled as an independent random oracle with finite input space. We provided a general methodology for computing collision probabilities in arbitrary Merkle graphs, when an arbitrary amount of leaves is modified. The main finding of this study is the fact that an attack carried out modifying multiple leaves is not necessarily more powerful than the one carried out modifying only one leaf. Specifically, the collision probability depends on the height of the attacked Merkle tree, increasing for higher trees, and on the position of the modified nodes in the tree.