Knowledge Base

Overview

A Merkle tree reduces a whole set of entries down to a single fingerprint, called the root, in a way that lets anyone later prove that one particular entry was part of the set without revealing or re-hashing the rest. An entry is a key plus a SHA-256 digest already computed over whatever that key names, so a single tree can hold entries of more than one kind: a Truestamp block’s tree holds both submitted items and the external entropy observations captured for that block. Every entry’s digest becomes a leaf, pairs of hashes are combined into node hashes level by level, and the single hash left at the top is the root. Truestamp’s implementation is pure Elixir with no dependencies beyond the standard cryptographic and hex-encoding libraries, which makes it small enough to audit line by line and straightforward to reimplement in any other language.

Leaf, node, and root

Three words describe the whole structure.

• A leaf is the bottom of the tree: one input entry, represented by its pre-computed SHA-256 hash. Truestamp does not hash your original document. You (or Truestamp) compute a SHA-256 hash of the data first, and that 32-byte hash is what enters the tree as a leaf.
• A node (also called an internal node) sits above the leaves. Each node is the hash of the two hashes directly beneath it, its left child and its right child. Nodes combine two hashes into one, so each level up the tree has half as many hashes as the level below.
• The root is the single hash at the very top, the one value that summarizes every leaf. Change any leaf, add a leaf, remove a leaf, or reorder the leaves, and the root changes. In Truestamp the root of a block’s tree is recorded as that block’s Merkle root and folds into the block’s overall fingerprint.

The tree is a binary tree: every node has exactly two children. Reading it top to bottom, the root splits into two nodes, each of those into two more, and so on down to the leaves.

How the root is computed

Building the tree is a repeated pairing-and-hashing process that starts at the leaves and works upward.

1. Order the entries. By default the input entries are sorted by their key, comparing raw key bytes ascending, so the same set of entries always produces the same root regardless of the order they were supplied in. Sorting can be turned off to preserve the supplied order, but a different order produces a different root. Each entry’s key must also be unique within one tree, because the key is how a proof is later looked up. Two entries carrying the same key are refused rather than quietly collapsed into one leaf, so a tree either holds every entry it was handed or does not build at all. The single exception is an exact re-submission, the same key with the same hash, which the incremental input path treats as the one entry it is.
2. Pad to a power of two. If the number of entries is not a power of two (2, 4, 8, 16, and so on), the tree is filled out to the next power of two with padding leaves. This keeps the tree balanced. Every padding leaf holds the same fixed, reserved constant as its input hash, 96a296d224f285c67bee93c30f8a309157f0daa35dc5b87e410b78630a09cfc7, and is then hashed exactly like any other leaf. That constant is closed to callers in both directions: an entry may not be submitted under it, and a proof presented for it is refused rather than checked, because such a proof would prove a padding slot rather than an entry. The __PAD__ key prefix is reserved the same way.
3. Hash each leaf. Each leaf hash is prefixed with a single 0x00 byte and run through SHA-256. In shorthand: leaf = SHA-256(0x00 || entry_hash).
4. Hash pairs up the levels. Adjacent leaf hashes are paired left and right, joined with a 0x01 prefix, and hashed: node = SHA-256(0x01 || left || right). This produces the next level up. The same pairing repeats on each new level until a single hash remains.
5. That last hash is the root.

An empty tree (no entries at all) has a special defined root: the SHA-256 hash of the empty input, e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855. That root is not the leaf hash of anything, so no inclusion proof can ever check out against it. A tree with a single entry has that one entry’s leaf hash (SHA-256(0x00 || entry_hash)) as its root; there are no siblings to pair, so no further hashing happens.

The tree refuses to build past 40 levels, which already allows for roughly a trillion leaves. This is an arithmetic guard against a nonsensical depth, not a load limit: no real tree comes close.

Domain separation: the 0x00 and 0x01 prefixes

The 0x00 byte in front of every leaf and the 0x01 byte in front of every node are not decoration. They are domain separation, and they are what make the tree secure against a class of forgery called a second preimage attack.

Without a prefix, a leaf hash and a node hash would be computed the same way, so an attacker could take an internal node’s hash and pass it off as if it were a leaf, presenting a fake but valid-looking proof. By hashing leaves with a 0x00 prefix and nodes with a 0x01 prefix, a leaf can never be mistaken for a node or vice versa: the two are drawn from separate, non-overlapping input spaces. It is worth being clear about what does not do this: Bitcoin’s original Merkle tree hashes leaves and internal nodes identically, which is exactly the confusion described above, and it separately duplicates the final hash on an odd level, a rule with its own documented root-collision weakness (CVE-2012-2459). Ethereum’s Merkle Patricia trie and its SSZ trees are different constructions again, and neither is this one. Truestamp applies this same single-byte-prefix discipline across all of its hashing, which is covered in hashing and domain separation.

Reproducing a root

Because the implementation is small and self-contained, it is easy to audit and easy to port. A verifier written in any language can reproduce a Truestamp root and confirm a proof by following five rules:

• 0x00 in front of every leaf input.
• 0x01 in front of every joined pair of child hashes.
• SHA-256 throughout.
• Leaves ordered by raw key bytes ascending, never a locale-aware comparison.
• Padding out to the next power of two with leaves whose input hash is the reserved constant 96a296d224f285c67bee93c30f8a309157f0daa35dc5b87e410b78630a09cfc7, which is itself SHA-256 over the two bytes 0x00 0x00.

Every leaf input must also be exactly 64 lowercase hex characters, a 32-byte digest. Uppercase input, a short or long string, or anything that is not a hex digest is rejected rather than coerced.

What this tree does not do

The tree proves that a leaf belonged to a specific root. It is not an append-only transparency log, and it deliberately leaves out the machinery that would make it one: there are no consistency proofs, no signed tree heads, and no third-party log monitoring. Tamper evidence over time comes from somewhere else entirely, namely the block hash chain, the signatures over each block, and the external commitments to public blockchains.

What the tree is used for

Reducing a set of entries to one root hash is only useful if you can later prove a single entry belonged to that set. That is the job of an inclusion proof: a short list of sibling hashes that lets anyone recompute the path from one leaf back up to the root, confirming the entry was in the tree, without needing every other entry. Truestamp uses this to prove that a specific submitted item was part of a specific block. The inclusion proof walk, and how it is verified, are covered in the inclusion proofs concept.

The root is also compact and stable, which is what lets Truestamp fold an entire block’s worth of entries, the submitted items and the block’s external entropy observations alike, into a single value that can be committed onward. This concept covers the tree and its root only; the proof mechanics and the commitment steps that build on it live in their own concepts.

Citations

1. RFC 6962: Certificate Transparency. The inspiration for the leaf and node hashing above: the 0x00 and 0x01 domain-separation prefixes over SHA-256, the empty-tree root as the hash of the empty input, and the single-leaf root all follow it. The tree shape does not. Truestamp sorts by key and pads to a power of two, where the standard splits an uneven leaf set and adds no filler, so a verifier written strictly to RFC 6962 reproduces a Truestamp root only when the leaf count is 0, 1, or an exact power of two.
2. CVE-2012-2459. The Bitcoin Merkle root collision named above, which comes from duplicating the last hash on an odd level rather than from the missing leaf and node prefixes.