Optimization of Merkle Tree Structures: A Focus on Subtree Implementation
Prasad Ayyalasomayajula, Mahalingam Ramkumar · 2023
A Merkle hash tree is an efficient data structure for generating a cryptographic commitment to a dynamic repository of records. For a database with N entries, the Merkle tree includes $2N-1$ cryptographic hashes as the nodes of the tree. With the rising prominence of such structures in contemporary applications, especially blockchain ledgers, optimal strategies for storage and retrieval of Merkle tree nodes become pivotal. This paper juxtaposes two primary mechanisms - the linear tree and the subtree - emphasizing databases potentially containing billions of records. Our discourse underscores the compelling advantages of the subtree method.