Merkle Tree — Definition and Proof of Inclusion

A Merkle tree commits to many records with a single root hash and lets a verifier prove inclusion of any record in O(log N) hashes.

Definition

A Merkle tree, introduced by Ralph Merkle in 1979, is a binary tree in which every non-leaf node is the cryptographic hash of the concatenation of its two child nodes. Leaves hold hashes of individual records. The single hash at the top of the tree, the Merkle root, is a fixed-length commitment to the entire dataset. Two datasets with the same root contain the same leaves in the same order; any change to any leaf forces the root to change.

Why log-N proof of inclusion matters

To prove that a specific leaf belongs to a Merkle tree of N leaves, a verifier needs only the leaf, the root, and the chain of sibling hashes along the path from the leaf to the root. That is `ceil(log2(N))` extra hashes, not N. For a tree of one million leaves, a proof of inclusion is roughly 20 SHA-256 digests, about 640 bytes. This is what makes Merkle trees the standard primitive for batch attestation: thousands of records can be committed to a single root, and any one record can be verified cheaply.

How NakedPnL uses it

Every day, NakedPnL collects the current chainHead of every trader account and uses them as leaves in a deterministic SHA-256 Merkle tree (`lib/ots/merkle.ts`). The resulting root is submitted to OpenTimestamps calendar servers (`lib/ots/anchor.ts`), which eventually return a Bitcoin block-anchored proof. Anyone who later wants to prove that a specific trader's chainHead was committed on a specific day downloads the leaf, the sibling path, and the root, and then re-hashes pairwise up to the root. Verification of one trader does not require downloading every other trader's data.

Worked example

import { createHash } from "node:crypto";

const h = (s: string) => createHash("sha256").update(s).digest("hex");

// Four trader chain heads on a given day:
const leaves = [h("trader-A-head"), h("trader-B-head"), h("trader-C-head"), h("trader-D-head")];

// Layer 1: pair and hash
const ab = h(leaves[0] + leaves[1]);
const cd = h(leaves[2] + leaves[3]);

// Layer 2: root
const root = h(ab + cd);

// To prove trader B is in the tree, share: leaves[1], leaves[0] (sibling), cd (sibling), root.
// Verifier reconstructs: h(leaves[0] + leaves[1]) -> ab, h(ab + cd) -> root.

Related terms

• Hash chain — per-trader history that feeds its head into the daily Merkle leaf set.
• OpenTimestamps — receives the daily root and returns a Bitcoin-anchored proof.
• Proof of inclusion — the sibling-hash path that demonstrates a leaf is in a tree.
• SHA-256 — the hash function used for both leaves and internal nodes.