What is Merkle Tree? (With images, examples and code)

With the use case of Blockchain technology and Bitcoin’s inception, Merkle Trees have touched the lives of billions worldwide. Merkle Trees are an integral part of blockchain technology, and they play a crucial role in ensuring data integrity.

In this article, we’ll explore what Merkle Trees are, how they work, and provide code examples to help you understand them better. Let’s dive right in since they have piqued your interest.

Prerequisites

To understand Merkle Trees, it’s important to have a basic understanding of Hashes and Trees. Here’s a brief explanation since they are not our main focus here:

• A hash (referring to its use in cryptography) is a function that takes an input of arbitrary length, encrypts it, and produces an output of fixed length. A hashing function maps inputs to encrypted outputs. They are deterministic, meaning that for a given input, they always provide the same output. For example, Sha-256.

• A tree is a directed acyclic graph where nodes are connected hierarchically, forming parent-child relationships. At the top is the root node, and all other nodes are organized into layers below it. Nodes in a tree may have zero or more child nodes, and those with no children are termed leaf nodes. Trees are fundamental data structures used to represent and manage hierarchical relationships in computer science and algorithms. They play a crucial role in applications such as database indexing, file system organization, and parsing in compilers and interpreters.

Tree

What is a Merkle Tree, really?

Merkle Tree, named after Ralph Merkle, is a data structure used to verify the integrity of data. A Merkle Tree is constructed by recursively hashing pairs of data until all the data is hashed into a singular root hash. It is a generalization of a hash list and hash chain.

How does it work?

Let’s visualize a scenario using the knowledge we’ve gained. Suppose you have four sets of data that you need to store while preserving their integrity. Merkle Tree is your chosen data structure. You hash pairs of data and then hash them again.

But what if there is an odd number of data sets?

Then the last hash is duplicated and hashed with itself.

Code

// Importing library that contains hash functions
import { SHA256 } from "crypto-js/sha256";

//Function to generate Merkle Tree
function generateMerkleTree(data) {
  //Base Case
  if (data.length == 1) {
    return SHA256(data[0]);
  }
  // Recursive Code
  const Tree = [];
  for (i = 0; i < data.length; i += 2) {
    //Step is 2 because pairs of data sets are taken
    const block1 = data[i];
    const block2 = i + 1 < data.length ? data[i + 1] : block1;
    //If the last block is the only one remaining(ODD no of blocks)
    // the last block is duplicated
    const combinedHash = SHA256(block1 + block2);
    Tree.push(combinedHash);
  }

  return generateMerkleTree(Tree);
}

// Function to verify integrity by providing Merkle Proof
function MerkleProof(data, merkleProof, BlocktoCheck, rootHash) {
  let PROOF = SHA256(BlocktoCheck);
  for (const Proof of merkleProof) {
    if (Proof.position === left) {
      PROOF = SHA256(PROOF + Proof.hash);
    } else {
      PROOF = SHA256(Proof.hash + PROOF);
    }
  }

  return PROOF === rootHash;
}

Use Cases

Some places where you might’ve already interacted with a Merkle tree could be:

1. Blockchain (Cryptocurrency): In the blockchain, Merkle Trees are used to ensure the integrity of transaction data.
2. Distributed File Systems: Merkle Trees are used to verify the consistency of distributed file systems.
3. Version Control (Git): In version control systems like Git, Merkle Trees help track changes and ensure data consistency.
4. Cloud Storage
5. Data Verification Systems

Any system where data integrity is critical can benefit from the use of Merkle Trees.