Overview

A Merkle tree is a way to reduce a whole set of items down to a single fingerprint, called the root, in a way that lets anyone later prove that one particular item was part of the set without revealing or re-hashing the rest. Truestamp builds its Merkle trees to the RFC 6962 standard, the same tree design used by Certificate Transparency to hold web browsers accountable for the certificates they trust. Every item’s SHA-256 hash becomes a leaf, pairs of hashes are combined into node hashes level by level, and the final single hash at the top is the root. Truestamp’s implementation is pure Elixir with zero external dependencies, 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 item, 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 items. By default the input items are sorted by their key so the same set of items 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.
2. Pad to a power of two. If the number of items 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. Each padding leaf uses a fixed, reserved constant for its hash and a reserved key that ordinary items are forbidden from using, so a padding leaf can never be confused with a real item.
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 || item_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 items at all) has a special defined root: the SHA-256 hash of the empty input, e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855. A tree with a single item has that one item’s leaf hash (SHA-256(0x00 || item_hash)) as its root; there are no siblings to pair, so no further hashing happens.

The tree is bounded for safety: it will not build past 40 levels deep, which already allows for roughly a trillion leaves, far beyond any practical need.

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. This is exactly the construction specified by RFC 6962, and the same idea appears in Bitcoin and Ethereum. Truestamp applies this same single-byte-prefix discipline across all of its hashing, which is covered in hashing and domain separation.

Why RFC 6962

RFC 6962 is the Certificate Transparency standard. Certificate Transparency exists so that the certificate authorities that issue the HTTPS certificates behind every secure website cannot quietly mis-issue one without leaving a public, tamper-evident record. That system runs on Merkle trees, and it has been scrutinized and depended upon at internet scale for years.

Truestamp chose RFC 6962 rather than inventing a bespoke tree for concrete reasons.

• It is a published, reviewed standard. The leaf/node domain separation and empty-tree behavior are specified, not improvised, so an independent verifier can be written against the spec.
• It resists second preimage forgery through the 0x00/0x01 prefixes described above.
• It is widely implemented. The same tree shape is used in Certificate Transparency, Bitcoin, and Ethereum, so the design is well understood and interoperable.

Because Truestamp’s implementation is pure and dependency-free, it is easy to audit and easy to port. A verifier written in any language can reproduce a Truestamp root and confirm a proof as long as it follows the same RFC 6962 rules: 0x00 on leaves, 0x01 on nodes, SHA-256 throughout, byte-wise key ordering, and power-of-two padding.

What the tree is used for

Reducing a set of items to one root hash is only useful if you can later prove a single item 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 item was in the tree, without needing every other item. 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 submitted items 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. Defines the Merkle tree used here, including the 0x00 leaf and 0x01 internal-node domain-separation prefixes over SHA-256 and the empty-tree root as the hash of the empty input.