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

Corsi A, Almenhali A, Laurenti N (2026)

Publication Type: Journal article

Publication year: 2026

Journal

Journal of Mathematical Cryptology Walter de Gruyter GmbH & Co. KG

Book Volume: 20

Article Number: 20250050

Journal Issue: 1

DOI: 10.1515/jmc-2025-0050

Abstract

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.

Authors with CRIS profile

Alessandro Corsi Graduiertenkolleg 2475/2 - Cyberkriminalität und Forensische Informatik

Involved external institutions

University of Padua / Universita degli Studi di Padova IT Italy (IT)

How to cite

APA:

Corsi, A., Almenhali, A., & Laurenti, N. (2026). Analysis of collision probability in Merkle trees in the random oracle model. Journal of Mathematical Cryptology, 20(1). https://doi.org/10.1515/jmc-2025-0050

MLA:

Corsi, Alessandro, Abdulla Almenhali, and Nicola Laurenti. "Analysis of collision probability in Merkle trees in the random oracle model." Journal of Mathematical Cryptology 20.1 (2026).

BibTeX: Download