Understanding and Implementing Merkle Trees in Bitcoin

In this article, we'll dive deep into Merkle trees - a fundamental data structure that ensures transaction integrity on the Bitcoin blockchain. We'll implement a practical TypeScript solution for working with Merkle trees and validate our code by testing it against real Bitcoin block data. The complete source code is available here.

What are Merkle Trees?

Merkle trees are a hash-based data structure used to efficiently summarize and verify large sets of data. In Bitcoin, each block's transactions are organized into a Merkle tree, where individual transaction hashes are repeatedly paired and hashed until a single "Merkle root" remains, ensuring that any alteration to a transaction invalidates the entire tree. This allows Bitcoin nodes to verify transactions without storing the entire blockchain, improving security and performance.

Practical Implementation

Let's put this knowledge into practice by examining a real Bitcoin block. We'll fetch its transaction data, compute the Merkle root from scratch, and verify it matches the blockchain's record. To demonstrate the power of Merkle proofs, we'll also randomly select a transaction and verify its inclusion in the block.

import { getMerkleRoot } from "./core/getMerkleRoot"
import { getMerkleProof } from "./core/getMerkleProof"
import { verifyMerkleProof } from "./core/verifyMerkleProof"
import { queryUrl } from "../../lib/utils/query/queryUrl"
import { toBitcoinMerkleNode } from "./core/toBitcoinMerkleNode"

interface BlockData {
  merkle_root: string
  height: number
}

const verifyBlock = async (blockHash: string) => {
  const blockData = await queryUrl<BlockData>(
    `https://blockstream.info/api/block/${blockHash}`,
  )
  const transactions = await queryUrl<string[]>(
    `https://blockstream.info/api/block/${blockHash}/txids`,
  )

  console.log(`Block Merkle Root from blockchain: ${blockData.merkle_root}`)
  console.log(`Number of transactions: ${transactions.length}`)

  const computedMerkleRoot = getMerkleRoot(transactions, toBitcoinMerkleNode)

  console.log(`Computed Merkle Root: ${computedMerkleRoot}`)
  const isRootValid = computedMerkleRoot === blockData.merkle_root
  console.log(
    `Merkle Root Validation: ${isRootValid ? "Valid ✅" : "Invalid ❌"}`,
  )

  // Pick a random transaction to verify
  const randomIndex = Math.floor(Math.random() * transactions.length)
  const targetTx = transactions[randomIndex]
  console.log(`\nVerifying random transaction:`)
  console.log(`Transaction Hash: ${targetTx}`)
  console.log(`Transaction Index: ${randomIndex}`)

  const proof = getMerkleProof({
    nodes: transactions,
    targetNode: targetTx,
    toNode: toBitcoinMerkleNode,
  })

  const isProofValid = verifyMerkleProof({
    leaf: targetTx,
    merkleRoot: blockData.merkle_root,
    proof,
    toNode: toBitcoinMerkleNode,
    index: randomIndex,
  })

  console.log(`Proof length: ${proof.length} elements`)
  console.log(
    `Transaction Proof Validation: ${isProofValid ? "Valid ✅" : "Invalid ❌"}`,
  )
}

const blockHash =
  "0000000000000000000266819fe415c51f9c025e1059b4c1332c1033236166f0"

verifyBlock(blockHash)

Fetching Block Data

To fetch the block data and transaction hashes, we'll use the Blockstream API. We'll make HTTP requests using a helper function called queryUrl that handles the API calls and response parsing. The block data contains the Merkle root we want to verify, while the transaction hashes will be used to reconstruct the Merkle tree.

import { assertFetchResponse } from "../fetch/assertFetchResponse"

export const queryUrl = async <T>(url: string): Promise<T> => {
  const response = await fetch(url)

  await assertFetchResponse(response)

  return response.json()
}

Computing the Merkle Root

The getMerkleRoot function calculates the Merkle root of a tree by recursively combining pairs of nodes. It takes two parameters:

1. An array of nodes (in this case, transaction hashes) that form the leaves of the tree
2. A function that specifies how to combine two nodes into their parent node by hashing them together

import { toPairs } from "@lib/utils/array/toPairs"
import { getLastItem } from "@lib/utils/array/getLastItem"

export const getMerkleRoot = (
  nodes: string[],
  toNode: (pair: [string, string]) => string,
): string => {
  if (nodes.length === 0) {
    throw new Error("Cannot create a Merkle tree with no leaves")
  }

  if (nodes.length === 1) {
    return nodes[0]
  }

  const pairs = toPairs(
    nodes.length % 2 === 0 ? nodes : [...nodes, getLastItem(nodes)],
  )

  const level = pairs.map(toNode)

  return getMerkleRoot(level, toNode)
}

Building the Tree Structure

The getMerkleRoot function implements the core logic for building a Merkle tree and computing its root hash. When given an array of transaction hashes, it first handles edge cases: throwing an error for empty arrays or returning the single hash for arrays of length one. For arrays with multiple elements, it ensures an even number of nodes by duplicating the last element if necessary (a standard practice in Merkle trees). It then pairs up the nodes, hashes each pair using the provided toNode function, and recursively processes the resulting level until only one hash remains - the Merkle root. This approach creates a balanced binary tree structure where each non-leaf node is the hash of its two children.

import { createHash } from "crypto"

import { pipe } from "@lib/utils/pipe"

const sha256 = (data: Buffer): Buffer =>
  createHash("sha256").update(data).digest()

export const toBitcoinMerkleNode = (pair: [string, string]): string => {
  const concatenated = Buffer.concat(
    pair.map((hex) => Buffer.from(hex, "hex").reverse()),
  )

  return pipe(concatenated, sha256, sha256).reverse().toString("hex")
}

Bitcoin-Specific Hashing Implementation

The toBitcoinMerkleNode function implements Bitcoin's specific method for computing parent nodes in the Merkle tree. It takes a pair of transaction hashes and combines them according to Bitcoin's protocol: first reversing each hash (converting from little-endian to big-endian), concatenating them, then applying SHA-256 twice (known as double-SHA256), and finally reversing the result back. This process matches Bitcoin's internal hashing convention, ensuring our computed Merkle root will match the blockchain's value.

Merkle Proofs for Transaction Verification

With the Merkle root computed and validated, the next step is to verify that a single transaction truly belongs in this Merkle tree. This is done through a Merkle proof, which provides just enough intermediate hashes to trace a path from the specific transaction (the leaf) all the way up to the Merkle root. Using this proof, any node can confirm the transaction's presence in the block without having to download all other transactions. This concept is central to Bitcoin's Simplified Payment Verification (SPV), enabling lightweight clients to efficiently verify individual transactions by relying on Merkle proofs rather than the full blockchain.

import { toPairs } from "@lib/utils/array/toPairs"
import { getLastItem } from "@lib/utils/array/getLastItem"

type GetMerkleProofInput = {
  nodes: string[]
  targetNode: string
  toNode: (pair: [string, string]) => string
}

export const getMerkleProof = ({
  nodes,
  targetNode,
  toNode,
}: GetMerkleProofInput): string[] => {
  if (nodes.length === 0) {
    throw new Error("Cannot create a Merkle proof with no leaves")
  }

  if (nodes.length === 1) {
    return []
  }

  const pairs = toPairs(
    nodes.length % 2 === 0 ? nodes : [...nodes, getLastItem(nodes)],
  )

  const targetIndex = nodes.indexOf(targetNode)
  if (targetIndex === -1) {
    throw new Error("Target node not found in the tree")
  }

  const pairIndex = Math.floor(targetIndex / 2)

  const pair = pairs[pairIndex]

  const isLeftNode = targetIndex % 2 === 0
  const proofNode = pair[isLeftNode ? 1 : 0]

  const level = pairs.map(toNode)

  const nextTargetNode = toNode(pair)

  return [
    proofNode,
    ...getMerkleProof({ nodes: level, targetNode: nextTargetNode, toNode }),
  ]
}

Generating Merkle Proofs

The getMerkleProof function generates a Merkle proof for a specific transaction by collecting the necessary sibling hashes along the path from the leaf to the root. It works recursively, similar to getMerkleRoot, but focuses on tracking one specific path through the tree. At each level, it identifies whether our target node is a left or right child (isLeftNode), then adds its sibling (proofNode) to the proof. This process continues up the tree, with each recursive call working with the parent hash (nextTargetNode) until we reach the root. The resulting proof contains the minimum set of hashes needed to reconstruct the path to the root, typically log₂(n) elements for n transactions. This efficiency is what makes Merkle proofs so powerful for lightweight verification.

type VerifyMerkleProofInput = {
  leaf: string
  merkleRoot: string
  proof: string[]
  toNode: (pair: [string, string]) => string
  index: number
}

export const verifyMerkleProof = ({
  leaf,
  merkleRoot,
  proof,
  toNode,
  index,
}: VerifyMerkleProofInput): boolean => {
  let currentNode = leaf
  let currentIndex = index

  proof.forEach((proofNode) => {
    const isLeftNode = currentIndex % 2 === 0
    const pair: [string, string] = isLeftNode
      ? [currentNode, proofNode]
      : [proofNode, currentNode]

    currentNode = toNode(pair)
    currentIndex = Math.floor(currentIndex / 2)
  })

  return currentNode === merkleRoot
}

Verifying Merkle Proofs

The verifyMerkleProof function is where the magic of Merkle proofs comes together. This function verifies that a transaction is indeed part of the block by reconstructing the path to the Merkle root using only the proof hashes. Here's how it works:

1. It starts with our target transaction hash (leaf) and its position in the original transaction list (index).
2. For each hash in the proof array, it:
   • Determines if our current hash should be the left or right child based on its index
   • Pairs it with the proof hash in the correct order
   • Computes the parent hash using the same toNode function
   • Updates the index for the next level by integer dividing by 2
3. Finally, it checks if the computed root matches the known Merkle root

This process effectively "climbs" the Merkle tree from our transaction to the root, using only log₂(n) hashes instead of the full set of transactions.

Conclusion

By implementing and testing these Merkle tree functions against real Bitcoin block data, we've demonstrated how this elegant data structure enables efficient verification of blockchain transactions. The ability to prove transaction inclusion with just a handful of hashes, rather than the entire block's data, is crucial for Bitcoin's scalability and accessibility to lightweight clients. This practical example shows why Merkle trees remain a cornerstone of blockchain technology, enabling secure and efficient verification of transaction history.