In the last post, we constructed a Merkle Tree with a predefined set of transactions in
txs array. The merkle root was calculated successfully and all the nodes in each branch were displayed. But, the branches did not have a tree structure.
In this post, we aim at constructing a Merkle Tree in the form of a visual tree with merkle root at the top and leaf nodes at the bottom.
We will also be taking the total number of transactions and the list of transaction IDs which have to be summarized as input from the user.
A merkle tree is a data structure used for efficiently summarizing and verifying the integrity of large sets of data. The nodes of a merkle tree contain cryptographic hashes. A merkle tree is represented upside down with the “root” at the top and the “leaves” at the bottom.
Merkle trees are used in bitcoin to summarize all the transactions in a block, producing an overall digital fingerprint of the entire set of transactions, providing a very efficient process to verify whether a transaction is included in a block.
A merkle tree is constructed by recursively concatenating and hashing pairs of nodes until the merkle root is reached
A merkle tree is constructed bottom-up, placing the leaf nodes at the bottom, and the merkle root at the top. The number of leaf nodes that have to be summarized is counted. Let’s call this number n.
If n is an even number, then we start by concatenating the first node and the second node, and hash the result using double-SHA256 cryptographic hashing algorithm. The hash is called the parent node. Similarly, parent nodes of all the leaf nodes are computed.
If n is an odd number, then the last element is duplicated to achieve an even number of elements. Then, the nth node is concatenated with the n+1 node and the result is hashed using double-SHA256 cryptographic hashing algorithm. The parent nodes of all the leaf nodes are computed in this way.
The concatenating and hashing steps are repeated for the parent nodes, and repeated again for the next set of parent nodes and this process of recursively concatenating, hashing, and duplicating the last element for odd number of nodes, is continued till there is only one hash left in the tree. This hash is known as a root, or a merkle root.
The merkle root is a 32 byte hash summarizing all the transactions.