Wire Format — Settled Documentation

Section 1

Hash Constructions

All hash functions use SHA-256 (32-byte output). Domain separation prefixes follow RFC 6962 Section 2.1 exactly.

1.1 Leaf Hash

leaf_hash(data) = SHA-256(0x00 || data)

0x00 is a single byte domain separation prefix.
data is the raw bytes of the submitted entry payload — not the key.
An empty payload (data = b"") is valid and produces a defined hash.

1.2 Interior Node Hash

node_hash(left, right) = SHA-256(0x01 || left || right)

0x01 is a single byte domain separation prefix.
left and right are each 32-byte SHA-256 hashes.
The operation is not commutative: node_hash(a, b) ≠ node_hash(b, a).

1.3 Why Domain Separation Matters

Without the 0x00/0x01 prefix, an interior node hash (64 bytes of input) could be confused with a leaf hash of a 64-byte payload. This is the second-preimage attack described in RFC 6962 Section 2.1. An attacker could craft a payload whose leaf hash equals a valid interior node, and construct a fraudulent inclusion proof using it. The prefixes eliminate this attack entirely.

Section 2

Merkle Tree Structure

The tree is a binary append-only Merkle tree as defined in RFC 6962. For a tree with n leaves:

MTH([])    = undefined  (empty tree has no root)

MTH([d(0)]) = leaf_hash(d(0))

MTH(D[n]) where n > 1:
  k = largest power of 2 strictly less than n
  MTH(D[n]) = node_hash(MTH(D[0:k]), MTH(D[k:n]))

Where D[a:b] denotes the slice of leaf data from index a (inclusive) to b (exclusive). k is the largest power of 2 strictly less than n.

n	k	Tree shape
1	—	`h0`
2	1	`node(h0, h1)`
3	2	`node(node(h0, h1), h2)`
4	2	`node(node(h0, h1), node(h2, h3))`
5	4	`node(node(node(h0,h1),node(h2,h3)), h4)`
6	4	`node(node(node(h0,h1),node(h2,h3)), node(h4,h5))`
7	4	`node(node(node(h0,h1),node(h2,h3)), node(node(h4,h5),h6))`
8	4	`node(node(node(h0,h1),node(h2,h3)), node(node(h4,h5),node(h6,h7)))`

Where hi = leaf_hash(entry_i_data).

Section 3

Inclusion Proof

An inclusion proof for leaf at index m in a tree of size n is a list of sibling hashes from leaf to root. The verifier recomputes the root from the leaf hash and this path, then compares against a Signed Tree Head.

Cross-SDK compatibility: Any SDK implementing this verification algorithm must produce the same result as any other for the same inputs. The algorithm is defined here, not per-SDK.

3.1 Generation (RFC 6962 §2.1.1)

PATH(m, D[n]):
  if n == 1: return []
  k = largest power of 2 strictly less than n
  if m < k:
    return PATH(m, D[0:k]) + [MTH(D[k:n])]
  else:
    return PATH(m - k, D[k:n]) + [MTH(D[0:k])]

3.2 Verification

verify_inclusion(leaf_hash, m, n, path, root):
  fn = m
  sn = n - 1
  r  = leaf_hash

  for each step in path:
    if sn == 0: return false          // proof too long
    if fn is odd OR fn == sn:
      r  = node_hash(step, r)
      while fn != 0 AND fn is even:
        fn = fn >> 1
        sn = sn >> 1
    else:
      r  = node_hash(r, step)
    fn = fn >> 1
    sn = sn >> 1

  return sn == 0 AND r == root

A true result confirms that the entry with leaf_hash exists at index m in the tree committed to by root, and that root is the root of a tree containing exactly n entries.

Section 4

Consistency Proof

A consistency proof from tree size m to tree size n proves that the first m entries of the size-n tree are identical to the size-m tree. A verifier holding STH(m) can confirm this using only the two STHs and O(log n) proof hashes — no log entries need to be read.

This proves integrity of existing entries: nothing logged before STH(m) was subsequently modified, deleted, or reordered. It does not prove completeness: the proof cannot detect whether entries that should have been appended between m and n were silently omitted. Completeness is a separate concern addressed at the application and audit-process level.

4.1 Generation (RFC 6962 §2.1.2)

PROOF(m, D[n]):
  if m == n: return []
  return SUBPROOF(m, D[n], true)

SUBPROOF(m, D[n], b):
  n = len(D)
  if m == n:
    if b:    return []
    else:    return [MTH(D)]
  k = largest power of 2 strictly less than n
  if m <= k:
    return SUBPROOF(m, D[0:k], b) + [MTH(D[k:n])]
  else:
    return SUBPROOF(m - k, D[k:n], false) + [MTH(D[0:k])]

4.2 Verification

verify_consistency(m, n, proof, old_root, new_root):
  if m == n AND proof is empty:
    return old_root == new_root

  fn = m - 1
  sn = n - 1
  if fn has a set bit:               // m is not a power of 2
    while fn is even:
      fn = fn >> 1
      sn = sn >> 1
    fr = proof[0]
    sr = proof[0]
    proof = proof[1:]
  else:
    fr = old_root
    sr = old_root

  for each step in proof:
    if sn == 0: return false
    if fn is odd OR fn == sn:
      fr = node_hash(step, fr)
      sr = node_hash(step, sr)
      while fn != 0 AND fn is even:
        fn = fn >> 1
        sn = sn >> 1
    else if fn is even:
      sr = node_hash(sr, step)
    else:
      return false
    fn = fn >> 1
    sn = sn >> 1

  return sn == 0 AND fr == old_root AND sr == new_root

A true result confirms that the tree of size n contains the tree of size m as a prefix — every entry present at STH(m) is still present and unchanged. It does not verify the content of the n − m entries added since STH(m).

Section 5

Signed Tree Head

The Signed Tree Head (STH) is the cryptographic anchor of the log. It commits to the entire state of the log at a point in time with a compact, independently verifiable signature.

5.1 Structure

Field	Type	Description
tree_size	uint64	Number of entries in the tree at signing time
root_hash	bytes[32]	SHA-256 Merkle root of all entries
timestamp	int64	Unix nanoseconds, server clock at signing time
signature	bytes[64]	Ed25519 signature over the canonical signing payload
public_key	bytes[32]	Ed25519 public key (raw, compressed Edwards point)

5.2 Canonical Signing Payload

The bytes signed by Ed25519 are the concatenation of exactly three fields, in this order:

signing_payload =
  tree_size  as u64, big-endian (8 bytes)   ||
  root_hash  as bytes[32]                   ||
  timestamp  as i64, big-endian (8 bytes)

Total: 48 bytes

No padding, no length prefixes, no version byte. Any deviation from this exact layout means cross-SDK signature verification will fail. All implementations must produce bit-for-bit identical signing_payload bytes for the same inputs.

5.3 Signing Algorithm

Ed25519 as defined in RFC 8032. Ed25519 signs the message directly — no pre-hashing. The signing_payload above is the complete message passed to the signing function.

Language	Recommended library
Rust	`ed25519-dalek`
Python	`cryptography.hazmat.primitives.asymmetric.ed25519`
Go	`golang.org/x/crypto/ed25519`
Java	`java.security.Signature` with algorithm `"Ed25519"`
TypeScript	`@noble/ed25519`

5.4 Key Encoding

Keys are stored and transmitted as raw bytes. No ASN.1, no PEM, no JWK in the hot path.

Private key: 32 raw bytes (the seed, not the expanded key).
Public key: 32 raw bytes (compressed Edwards curve point).

For human-readable contexts — configuration files, admin API responses — keys are encoded as base64url without padding.

Section 6

Key Versioning

Each signing key has an associated version number (u32, starting at 1). When verifying a historical STH, the verifier must use the key version that was active when that STH was produced.

Key Record

Field	Type	Description
version	uint32	Key version number (starts at 1, increments on each rotation)
public_key	bytes[32]	Ed25519 public key (raw)
activated_at_tree_size	uint64	Tree size of the first STH signed with this key
retired_at_tree_size	uint64	Tree size at retirement; `0` means still active

Key Rotation Procedure

Generate a new Ed25519 key pair.
Record the current tree_size as activated_at_tree_size for the new key.
Update the old key's retired_at_tree_size to the same tree_size.
Sign a rotation announcement with the old key containing the new public key. This creates an auditable chain.
All subsequent STHs include the new public_key.

Verifying Across a Key Rotation

A verifier with a cached old STH and key version V:

Fetches the key history from the server (or a trusted external archive).
Identifies which key signed the STH being verified by checking activated_at_tree_size and retired_at_tree_size against the STH's tree_size.
Verifies the signature with that key.

Historical proofs remain valid across key rotations. The countersignature on each rotation announcement provides a verifiable chain from the initial public key to the current one.

Section 7

Duplicate Key Semantics

The index maps a user-provided key to a sequence number. When the same key is submitted more than once:

Semantics: last-write-wins. The index stores the sequence number of the most recent append for that key.
The earlier entry is not deleted or modified — it remains in the log at its original sequence number and is fully provable via inclusion proof.
The index is a convenience lookup, not the canonical identifier. The sequence number is the canonical identifier.

Rationale: O(1) lookup, simple schema, consistent with the primary use case of "find the latest state of this entity." Clients needing all versions of a key must scan the log directly or maintain their own secondary index.

Section 8

AppendResponse Leaf Hash

The leaf_hash returned in an AppendResponse is:

leaf_hash = SHA-256(0x00 || data)

Where data is the raw bytes of the submitted entry payload. The key field is not included in the leaf hash. The key is stored for index lookups but does not affect the Merkle commitment.

Two entries with the same data but different key values produce the same leaf_hash. This is correct and intentional — the Merkle tree commits to content, not identity. The sequence number disambiguates entries with identical content.

What to store: Your application should retain the seq (sequence number) and leaf_hash from each AppendResponse. These are the two values required to request and verify an inclusion proof in the future.

Wire Format Specification

Hash Constructions

1.1 Leaf Hash

1.2 Interior Node Hash

1.3 Why Domain Separation Matters

Merkle Tree Structure

Inclusion Proof

3.1 Generation (RFC 6962 §2.1.1)

3.2 Verification

Consistency Proof

4.1 Generation (RFC 6962 §2.1.2)

4.2 Verification

Signed Tree Head

5.1 Structure

5.2 Canonical Signing Payload

5.3 Signing Algorithm

5.4 Key Encoding

Key Versioning

Key Record

Key Rotation Procedure

Verifying Across a Key Rotation

Duplicate Key Semantics

AppendResponse Leaf Hash