salma sultana

Logo

Former End User Consultant, Current Software Developer, and a Master's degree holder in Data Science and Engineering.

View My GitHub Profile

Implementing a Merkle Tree in Javascript

In this post, you will find the implementation of a Merkle Tree summarizing n transactions.

A Merkle Tree produces a root, aka merkle root, by recursively concatenating and hashing pairs of nodes until there is only one node left.

The hashes are obtained by applying a cryptographic hashing algorithm, known as SHA256, twice to each element. This is also known as double-SHA256 hashing algorithm.

Merkle Trees in Detail

Definition of a Merkle Tree

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 in Bitcoin

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.

Constructing a Merkle Tree

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.

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.

Example of a Merkle Tree Containing 16 leaf nodes


Merkle Tree summarizing many data elements


SHA256 in detail –>

back