Knowledge Base

Browse the concepts behind Truestamp. Follow the links between concepts, or search across everything.

Merkle Proof Encodings

The two encodings of a Truestamp Merkle inclusion proof - the JSON object {leaf_index, path, tree_size} that proofs and the APIs carry, and the fixed-width binary form Truestamp stores, 16 + 32 x d bytes - with their limits and a worked example.

Overview

A Truestamp Merkle inclusion proof has exactly two encodings. Its JSON form is the object {"leaf_index", "path", "tree_size"} of RFC 9162: it is what every proof document carries as inclusion_proof, and what the JSON:API and GraphQL APIs show for a commitment’s inclusion proof. Its binary form is a fixed-width layout of 16 + 32 x d bytes, for a path of d hashes, in which Truestamp stores each proof. The two carry the same information and convert losslessly, and each proof has exactly one spelling in each. There is no other wire form: no direction markers, no bitfield and no base64 text form. For what an inclusion proof is and how it is checked against a root, see Merkle inclusion proofs; for how the tree and its hashes are built, see Truestamp’s Merkle tree.

The JSON form

The JSON form is a closed object with exactly these three members:

Member Value
leaf_index the leaf’s position in the tree, counted from 0; an integer below tree_size
path the sibling hashes from the leaf up to the root, each 64 lowercase hex characters
tree_size the number of leaves in the tree

The path holds exactly as many hashes as the index and the size require, and no more than 32. A one-leaf tree’s proof has an empty path:

{"leaf_index": 0, "path": [], "tree_size": 1}

A proof Truestamp takes as input (an API filter, an internal job) is held to the same rules: exactly these members, integers for the two numbers, a tree_size of at most 2^32, a path of at most 32 hashes, and a path of the length the index and the size fix. Anything else is refused, never coerced.

The binary form

The binary form has three parts, in order:

bytes 0-7 leaf_index, unsigned 64-bit big-endian
bytes 8-15 tree_size, unsigned 64-bit big-endian
the rest each path hash's 32 raw bytes, bottom to top

So a proof with a path of d hashes is exactly 16 + 32 x d bytes, and the one-leaf proof above is 16 bytes: 0000000000000000 followed by 0000000000000001. The fields are fixed-width and the path’s length follows from the index and the size, so each proof has exactly one binary form, and comparing two binary forms byte for byte compares the proofs.

Decoding takes untrusted bytes and never guesses. It refuses, in this order:

  1. anything that is not a byte string;
  2. fewer than the 16 bytes of the two fields;
  3. a leaf_index that is not below tree_size (so a tree_size of 0 always fails);
  4. remaining bytes that are not exactly the 32-byte hashes the index and the size require.

Encoding refuses a proof that the walk would refuse, rather than writing bytes a decoder would reject.

Worked example: a two-leaf proof

The proof of the first leaf of a two-leaf tree is:

{"leaf_index": 0, "path": ["5e5caeafc27155c368b6f201107d6f8b270747ce636ac5174a56c6e12ef89ad1"], "tree_size": 2}

Its binary form is 16 + 32 = 48 bytes:

bytes 0-7 00 00 00 00 00 00 00 00 leaf_index = 0
bytes 8-15 00 00 00 00 00 00 00 02 tree_size = 2
bytes 16-47 5e 5c ae af c2 71 55 c3 ... 2e f8 9a d1 the one path hash

Decoding reverses this: read the two fields, check that index 0 is below size 2, check that a tree of 2 needs one path hash at index 0, read its 32 bytes, and spell them back as lowercase hex.

Limitations

  • An inclusion proof in either form carries only the leaf’s position, the tree’s size and the path. It does not carry the leaf’s own hash, the expected root, or the tree’s committed leaf_count; those come from the records a proof document carries, and a verifier must take the leaf from a hash it recomputed.
  • The binary form holds a tree_size up to 2^64 - 1, but Truestamp never commits a tree of more than 2^32 leaves, and every proof it accepts or serves keeps to that limit and to 32 path hashes.
  • Each path entry is exactly a 32-byte SHA-256 digest. Neither form is a general container for hashes of other lengths.

Citations

  1. RFC 9162: Certificate Transparency Version 2.0. Section 2.1.3 defines the inclusion proof, its leaf index, tree size and path, that both encodings hold.