Merkle trees

A Merkle tree squeezes a whole list of items into one hash, in a way that still lets you prove any single item is on the list.

Every Pearl block uses one. Its transactions are hashed into a tree, and the single hash at the top, the Merkle root, goes into the block header. Change one byte of any transaction and the root changes, so the header vouches for every transaction in the block.

Try it

Add or edit transactions and watch the tree recompute. Click a leaf to see its proof path.

How is the tree built?

Start with the transaction IDs at the bottom. Then repeat one step until one hash is left:

1. Pair them up

   Take the hashes two at a time, left to right.

2. Hash each pair

   Join the two 32-byte hashes (64 bytes, in internal byte order) and take SHA256d. That’s the parent.

3. Odd one out? Pair it with itself

   If a level has an odd number of hashes, the last one is hashed together with a copy of itself.

The tree is the same as Bitcoin’s, built by the same code inherited from btcd.

What does a real Pearl tree look like?

Block 130,825 has 115 transactions. Here is how its tree shrinks, level by level:

The one hash left at the top is ab5f7fee74ac4fc304186ab08b556fd03e408576753b1f9ae4574d48251d052a, and that’s exactly what the header stores at bytes 36 to 67 (byte-reversed, as hashes always are):

How do you prove one transaction is in the block?

With a Merkle proof: the sibling hash at every level on the way up. Given those, anyone can recompute the root and compare it with the header.

Take the payment at position 17 in block 130,825, d919e02a4adfd739ceef31d98803f0ddd24e1b1fa67b0fe572cdec42c1b384c9. Its proof is seven hashes, computed from the block’s real transaction list:

The first step hashes transaction 16 and the payment together: SHA256d of the pair gives dce385157c7be73e…2d936174. Six more steps and you land on ab5f7fee…251d052a, the root in the header. The check passes.

That’s 7 × 32 = 224 bytes of proof, instead of downloading all 115 transaction IDs (3,680 bytes) or the whole block.

Why not hash all the transactions in one go?

You could. A single SHA256d over every transaction ID in a row would commit to the whole list just as firmly, and the header would still hold one 32-byte hash.

The difference shows up when you want to prove something about one transaction. With a flat hash, the proof is every other transaction ID. With a tree, it’s one sibling per level: 7 hashes for 115 transactions, 12 for 4,000. The header stays 108 bytes no matter how big the block is, and anyone holding it can check a single transaction cheaply.

Pearl’s mining leans on the same advantage, at a much bigger scale: a pool can check two rows of a gigabyte-sized matrix against a 32-byte fingerprint.

Why is pairing with itself a problem?

Because two different lists can then give the same root. A block with transactions [a, b, c] and a block with [a, b, c, c] build identical trees: the lone c is paired with a copy of itself either way.

This was a real Bitcoin bug, CVE-2012-2459. The fix, which Pearl inherits, is simple: a block with a duplicate transaction is invalid. So the trick can’t be used to make a valid block look invalid, or the other way round.

Where else does Pearl use Merkle trees?

The same shape turns up across Pearl, with different hash functions inside:

• Witness tree. A second tree over the witness transaction IDs (with the coinbase’s set to zero) is committed in the coinbase, exactly as in Bitcoin’s segwit.
• Script trees. Taproot and P2MR outputs commit to a tree of spending scripts, built with the TapLeaf and TapBranch tagged hashes. A P2MR address carries that tree’s root directly.
• XMSS keys. A post-quantum XMSS public key contains the root of a tree of 32 one-time keys.
• Mining matrices. A miner fingerprints each matrix with keyed BLAKE3, which is itself a Merkle tree over 1 KiB chunks. When a ticket wins, the pool receives just the needed rows and columns plus their Merkle paths, and checks them against the fingerprints. See noise seeds.

func HashMerkleBranches(left, right *chainhash.Hash) chainhash.Hash {
	// Concatenate the left and right nodes.
	var hash [chainhash.HashSize * 2]byte
	copy(hash[:chainhash.HashSize], left[:])
	copy(hash[chainhash.HashSize:], right[:])

	return chainhash.DoubleHashRaw(func(w io.Writer) error {
		_, err := w.Write(hash[:])
		return err
	})
}

function merkleRoot(level) {
  while (level.length > 1) {
    const next = [];
    for (let i = 0; i < level.length; i += 2) {
      const right = level[i + 1] ?? level[i];          // odd: pair with itself
      next.push(sha256(sha256(new Uint8Array([...level[i], ...right]))));
    }
    level = next;
  }
  return level[0];
}