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:
- anything that is not a byte string;
- fewer than the 16 bytes of the two fields;
- a
leaf_indexthat is not belowtree_size(so atree_sizeof 0 always fails); - 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_sizeup 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
- 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.