Skip to main content

Merkle Trees

An ALX Merkle tree combines one or more Block hashes into a single deterministic Merkle root hash. The Merkle root acts as a compact commitment to the complete leaf collection and can be stored, transmitted, or anchored on a blockchain without exposing Block content.

Merkle trees are an optional ALX extension. Block creation, Block identity, and Graph verification do not use Merkle trees, and core conformance does not require the extension. The JavaScript SDK exposes the extension from @alx-protocol/sdk/merkle; extension vectors are in protocol/extensions/merkle/test-vectors/.

Merkle Tree Model​

A single Merkle root represents an entire leaf collection. Inclusion of one Block hash is checked with a Merkle proof, described in Merkle Proofs.

Tree Construction​

The Merkle extension constructs trees deterministically so every implementation that claims the extension produces the same Merkle root hash from the same leaf sequence after normalization and sorting. The construction process:

  1. Trim and lowercase each Block hash, and validate the 0x-prefixed 32-byte format.
  2. Sort the leaf hashes.
  3. Group adjacent leaves into pairs.
  4. Order each pair by raw 32-byte value, smaller value first.
  5. Hash the 64-byte concatenation with Keccak-256, without a prefix, length, or domain byte.
  6. Promote an unpaired value to the next level unchanged.
  7. Repeat until one Merkle root remains.

The same normalized and sorted leaf sequence, including the same duplicate occurrences, produces the same Merkle root. Tree construction preserves duplicate leaves. buildMerkleTree() rejects an empty leaf collection with ALX_EMPTY_LEAVES and a leaf that is not a 32-byte hash with ALX_INVALID_LEAF_HASH.

When to Use a Merkle Tree​

Use a Merkle tree when one commitment must represent multiple Block hashes or when a verifier needs compact inclusion proofs. If a commitment contains only one Block, use the Block's blockHash directly.