This is part II of the multi part series on Merkle trees. To get an understanding of what merkle trees are and why they’re used, you can read the previous article.
Merkle Tree implementation basically consists of 3 main parts — calculating root, making a proof for an element and finally verifying the presence of that element in that list. We will implement these parts in both Typescript and Rust.
The root is a single hash that represents the entire dataset. To calculate it, you recursively hash pairs of nodes until only one hash remains. For simplicity we will use arrays or vectors for representing the dataset. It follows the following pseudocode.
WHILE length of leaves > 1:
// Ensure even number for pairing
IF length of leaves is ODD:
DUPLICATE the last element and APPEND it to leaves
SET next_level to an empty list
FOR index FROM 0 TO length of leaves - 1 STEP 2:
CONCATENATE leaves[index] and leaves[index + 1]
HASH the concatenated string
ADD result to next_level
SET leaves to next_level
RETURN leaves[0] (The Root)
A proof (or “Merkle path”) is the set of “sibling” hashes required to reconstruct the path from a specific leaf to the root. You don’t need the whole tree; you just need the hashes of the nodes you didn’t have.
FUNCTION build_proof(leaves, target_element):
FIND target_index of target_element in leaves
IF target_index not found, THROW error
MAP each leaf through hash_function()
SET proof to an empty list
WHILE length of leaves > 1:
IF length of leaves is ODD:
DUPLICATE the last element and APPEND it to leaves
// Identify sibling and its relative position
IF target_index is ODD:
ADD {sibling: leaves[target_index - 1], position: "left"} to proof
ELSE:
ADD {sibling: leaves[target_index + 1], position: "right"} to proof
// Move to next level
SET next_level to empty list
FOR index FROM 0 TO length of leaves - 1 STEP 2:
HASH(leaves[index] + leaves[index + 1]) and ADD to next_level
SET leaves to next_level
UPDATE target_index to (target_index / 2, rounded down)
RETURN proof
Verification is where the magic happens. A user provides a leaf and a proof. You hash them together repeatedly; if the final result matches the known Merkle Root, the leaf is valid.
FUNCTION verify_merkle_proof(merkle_root, leaf_value, proof):
SET current_hash to HASH(leaf_value)
FOR EACH element IN proof:
IF element.position is “left”:
SET current_hash to HASH(element.sibling + current_hash)
ELSE:
SET current_hash to HASH(current_hash + element.sibling)
IF current_hash EQUALS merkle_root:
RETURN true
ELSE:
RETURN false
By implementing a Merkle Tree in code, we’ve shifted from looking at data as a simple list to seeing it as a verifiable, cryptographic structure. We’ve explored how to condense large datasets into a single Merkle Root, generate Proofs that allow for efficient verification, and ensure data integrity without needing to share the entire tree.
Whether you are building a whitelist for an NFT drop, optimizing state sync in a blockchain client, or just curious about how Git handles file changes, the Merkle Tree is an indispensable tool in your engineering toolkit. Now that you have the core logic down, try experimenting with different hashing algorithms or scaling the tree to handle thousands of leaves to see how the performance holds up!
Implementing Merkle Trees in TypeScript — Part II was originally published in Coinmonks on Medium, where people are continuing the conversation by highlighting and responding to this story.
