Domain Separation in Merkle Tree Hashing

A Merkle tree hashes leaves, then hashes pairs of children into parents, up to a single root. The natural implementation hashes a leaf as H(data) and an internal node as H(left || right), which uses one function for two structurally different things. If some byte string can be read both as a leaf and as a concatenation of two 32-byte digests, then the same hash output can arise from two different tree shapes, and a proof of inclusion for one is a proof for the other. The fix is cheap and nearly universal, and the cases where it is missing are instructive.

The collision that is not a hash collision

Suppose leaves are 64 bytes of arbitrary data and the digest is 32 bytes. Consider a two-leaf tree whose leaves are A and B, both 32 bytes. The root is H(H(A) || H(B)). Now consider a single-leaf tree whose leaf is the 64-byte string H(A) || H(B). Its root is H(H(A) || H(B)) as well. The two trees have the same root, but one has two leaves and the other has one, and the first leaf of the two-leaf tree is A while the only leaf of the other is a 64-byte blob that happens to contain two digests.

No collision in H was needed. The attacker supplied a leaf whose value is the concatenation that an internal node would have hashed, and the tree builder could not tell the difference because both cases reduce to the same byte string going into the same function.

This matters when the tree is used to prove membership. A verifier presented with a proof that A is in the tree at position 0 under root R accepts it, because the root genuinely is R. The tree’s owner, who committed to a single 64-byte leaf, never agreed to any such membership. The tree committed to one thing and the proof claims another.

The general statement is that the tree is a commitment to a hash only if the mapping from tree to root is injective at the level of encodings. Structural injectivity is a separate requirement from collision resistance, and a hash can be perfectly collision resistant while the tree built on it is not.

Two standard repairs

The first repair prefixes each node with a distinct tag byte. Bitcoin commits to transactions with a tree whose internal nodes are hashed as SHA256d(0x01 || left || right), and its witnesses use a prefixed leaf encoding as well. The two prefixes cannot be confused, so a leaf that begins with the bytes of a tag cannot produce the digest of an internal node over the same bytes.

The second repair is structural rather than tagged: RFC 6962 for Certificate Transparency encodes a leaf as H(0x00 || leaf_data) and an internal node as H(0x01 || left || right), which is the same idea with the tags assigned the other way. The distinction is that CT takes the leaf tag seriously as a security requirement and states it in the specification. The empty tree is defined as the hash of the empty string, and that value is distinct from every prefixed node because a node’s input is at least one byte longer.

RFC 9162 keeps the rule. Its Merkle tree hash section defines the leaf hash and node hash with the same one-byte prefixes, and the formal specification makes clear that the prefixes are part of the definition of the structure rather than an implementation choice. Two implementations that disagree about prefixes produce incompatible roots, which is a strong incentive to follow the text.

HASH_LEN = 32

def leaf_hash(data: bytes) -> bytes:
    # 0x00 prefix makes leaf inputs disjoint from node inputs
    return sha256(b'\x00' + data)

def node_hash(left: bytes, right: bytes) -> bytes:
    assert len(left) == HASH_LEN and len(right) == HASH_LEN
    return sha256(b'\x01' + left + right)

The assertion is not decoration. Without it, a caller can pass a variable-length pair and reintroduce the ambiguity that the prefix removed, because two different splits of the same byte string would hash identically.

What the prefix costs

One byte of input per node, plus the hash call. No change to proof size, no change to digest size, no change to the tree shape. The cost is so small that the absence of the prefix is almost always an oversight rather than a trade-off.

There is a subtler cost in the case of tagged leaves: the tag occupies input space that would otherwise be available to the leaf, so the effective leaf domain shrinks by one byte at the front. For leaves of fixed structure that is free. For leaves that are themselves hash outputs of a different function, the tag has to be length-prefixed or the outer and inner functions have to be disjoint by construction.

A different approach is to use two independent hash functions, one for leaves and one for nodes. That works, but it doubles the implementation surface and the review burden, and it costs a second set of constants and test vectors. The tag byte achieves the same separation with a single function.

Where the separation has to be more than a byte

Prefix tags separate the kinds of node. They do not separate positions or contexts, and there are attacks that exploit the omission.

If the same hash function and the same leaf encoding are used for two different trees, then a proof from one tree may verify against the other when the roots coincide. Protocols with multiple trees, such as a per-shard structure or an append-only log with epochs, need a context string in the leaf and node encodings so that a proof cannot be transplanted. The tag byte can carry this: assign disjoint tag ranges per tree, or hash a domain string before the tag.

The second gap is the length of the leaf. If leaves are structured records, and the tree hashes the serialised record without a length prefix, then two records whose serialisations differ but concatenate identically produce the same leaf hash. This is the same field-boundary problem described in prefix-free encoding, reappearing one level down.

The third gap is between the tree and the signature or transcript that commits to the root. If a signed root for tree A and a signed root for tree B are both 32 bytes with no type tag, then a signature over one is a signature over the other whenever the values coincide, and more importantly a protocol that accepts “a signed root” cannot tell which structure it is a root of. The root itself should carry a domain tag in the signed message, not only in the node inputs.

Trees that avoid the problem structurally

Sparse Merkle trees sidestep the leaf/node ambiguity by making the position part of the leaf’s definition: a leaf sits at an index, and the path to it is determined by the index bits. The tree still needs a tag or a rule that an empty subtree has a distinct default value, which is covered in sparse Merkle trees, but the shape is fixed by the key space rather than by the message content, so a leaf cannot impersonate an internal node without also occupying its index.

A second structural approach is length-distinguishing node encodings, where an internal node hashes a fixed-size value and a leaf hashes a value of a different fixed size. If the two sizes differ, no byte string can be both. This works when the leaf size is fixed and distinct from twice the digest size, and it fails as soon as the leaf size happens to equal it, which is a fragile parameter to depend on.

The third approach is to commit to the tree shape separately: hash a canonical serialisation of the entire tree including its depth and leaf count, and sign that. The root then cannot be reinterpreted because the shape is part of what was signed. This is more expensive for large trees and is usually reserved for cases where the tree is small or where the shape is stable.

Verifying that a tree is correctly separated

Three checks catch most implementation errors. Confirm that the leaf and node encodings are statically disjoint, meaning there is no input length at which the two functions can be called with the same bytes. Confirm that the inclusion proof verifier recomputes the root with the same tags and the same left-right convention as the builder, since a mirror-image convention gives a different root for the same tree and breaks every proof. And confirm that the empty tree and a tree with one leaf have distinct roots, because a single-leaf tree and an empty tree that hash to the same value make the append-only property fail at size one.

A test vector covering a two-leaf tree with a 32-byte leaf, whose bytes are chosen to look like two digests, is the cheapest regression test for the first check and is the case that a naive implementation fails.