BIP 98 Fast Merkle Trees: Draft Proof Construction Guide

This guide explains BIP 98 Fast Merkle Trees in plain English. It covers the problem behind the BIP, why it matters and whether the proposal is part of Bitcoin today.

Why a different tree was proposed

Bitcoin’s historical transaction tree duplicates a final hash at some odd-width levels. That construction has created duplicate-entry hazards commonly associated with CVE-2012-2459 and performs more SHA-256 compression work than a purpose-built fixed-input inner-node hash. BIP 98 targets new applications so they need not inherit those properties. It is not permission to reinterpret existing block headers.

Leaf and inner-node separation

Leaves are 32-byte double-SHA256 hashes of application-defined data. Inner nodes combine exactly two 32-byte labels with fast-SHA256, using a custom initialisation vector and no padding. The changed domain prevents a leaf label being interpreted casually as an inner commitment. Applications still need their own unambiguous leaf serialisation and domain separation before hashing.

Nothing-up-my-sleeve initialisation vector

The custom initialisation value is derived from fixed fractional bits related to the square root of 23 and then a standard SHA-256 midstate. The published derivation must be reproduced byte-for-byte. Substituting an implementation-defined digest state, byte order or padding rule creates another algorithm even if sample outputs happen to resemble the specification.

Tree shape and edge cases

The proposal permits unbalanced binary trees but forbids nodes with a single child. An empty tree has no defined root, while a one-leaf tree passes through that leaf label without another hash. These rules affect proof composition and must be tested explicitly. A generic library that silently pads, duplicates or sorts children will calculate incompatible roots.

Proof encoding

A proof records the internal-node count, packed three-bit branch instructions and the omitted branch hashes. DESCEND, SKIP and VERIFY describe how the verifier reconstructs the committed root. Counts are deliberately redundant and must agree with the inferred structure. Reject non-zero padding bits, truncated hashes, extra hashes, impossible trees and trailing bytes rather than normalising them.

Malleability and resource limits

A node with two SKIP branches is disallowed because replacing it with one skipped parent is equivalent and otherwise creates proof malleability. Proof work is tied to internal-node count, but parsers still need strict byte, depth, allocation and hash-operation ceilings before recursion. Adversarial inputs should fail without unbounded memory, stack growth or partially accepted state.

How specialists test it

Developers test the proposal with made-up data on an isolated test network. They check normal cases and deliberately invalid cases. Different implementations should reach the same result before anyone relies on the proposal.

Conclusion

BIP 98 specifies a promising tree for new proof systems, not a retrofit of Bitcoin block commitments. Safe evaluation requires exact hashing domains, canonical proof parsing, bounded resources and explicit Draft labelling.