Merkle Proof Format

TrackForge uses a binary Merkle tree to commit all certified tracks in a batch to a single root hash. This root hash is then anchored to the blockchain via OpenTimestamps. Any individual track can prove its inclusion in the batch using a compact Merkle proof, without revealing any other track's data.

Merkle proof JSON structure

Each track's inclusion proof is represented as a MerkleProof object:

{
  "leaf_hash": "a1b2c3d4e5f6a1b2c3d4e5f6a1b2c3d4e5f6a1b2c3d4e5f6a1b2c3d4e5f6a1b2",
  "proof_hashes": [
    "b2c3d4e5f6a1b2c3d4e5f6a1b2c3d4e5f6a1b2c3d4e5f6a1b2c3d4e5f6a1b2c3",
    "c3d4e5f6a1b2c3d4e5f6a1b2c3d4e5f6a1b2c3d4e5f6a1b2c3d4e5f6a1b2c3d4"
  ],
  "proof_directions": ["right", "left"],
  "root_hash": "d4e5f6a1b2c3d4e5f6a1b2c3d4e5f6a1b2c3d4e5f6a1b2c3d4e5f6a1b2c3d4e5",
  "leaf_index": 0,
  "total_leaves": 4
}

Field	Type	Description
leaf_hash	string	SHA-256 hex digest of the track's canonical JSON. 64 characters.
proof_hashes	array[string]	Sibling hashes from leaf to root. Each is a 64-character hex string.
proof_directions	array[string]	Direction of each sibling: "left" or "right". Same length as proof_hashes.
root_hash	string	Merkle root hash. 64 characters. This is the value anchored to the blockchain.
leaf_index	integer	Zero-based position of this leaf in the sorted leaf array.
total_leaves	integer	Total number of leaves in the tree.

Tree construction rules

1. Leaf ordering

Before building the tree, all leaf hashes are sorted lexicographically (standard string sort on 64-character hex strings). This ensures that the tree structure is deterministic regardless of the order in which tracks were processed.

leaves = sorted(leaf_hashes)

2. Odd-number duplication

If a layer has an odd number of nodes, the last node is duplicated to form a complete pair:

for i in range(0, len(current_layer), 2):
    left = current_layer[i]
    right = current_layer[i + 1] if i + 1 < len(current_layer) else left
    parent = combine_hashes(left, right)

3. Hash combination function

Two sibling hashes are combined by concatenating their hex string representations and hashing the result with SHA-256:

import hashlib

def combine_hashes(left: str, right: str) -> str:
    combined = (left + right).encode("utf-8")
    return hashlib.sha256(combined).hexdigest()

The input to SHA-256 is the UTF-8 encoding of the concatenated hex strings (128 ASCII characters for two 64-character hashes), not raw binary. This is a deliberate design choice for simplicity and reproducibility across languages.

4. Bottom-up construction

The tree is built layer by layer from the leaves upward. Each layer is produced by pairing adjacent nodes and combining them. The process continues until a single root hash remains.

Verification algorithm

To verify that a leaf belongs to a tree with a given root hash:

INPUT:  leaf_hash, proof_hashes[], proof_directions[], root_hash
OUTPUT: boolean (valid or invalid)

1. Set current = leaf_hash
2. For each i from 0 to len(proof_hashes) - 1:
   a. sibling = proof_hashes[i]
   b. direction = proof_directions[i]
   c. If direction == "right":
        current = SHA-256(current + sibling)
      Else (direction == "left"):
        current = SHA-256(sibling + current)
3. Return current == root_hash

The direction indicates where the sibling sits relative to the current node. If the sibling is on the "right", the current node is the left child, so we hash current + sibling. If the sibling is on the "left", the current node is the right child, so we hash sibling + current.

Python implementation

import hashlib

def verify_merkle_proof(proof: dict) -> bool:
    current = proof["leaf_hash"]

    for sibling, direction in zip(proof["proof_hashes"], proof["proof_directions"]):
        if direction == "right":
            combined = (current + sibling).encode("utf-8")
        else:
            combined = (sibling + current).encode("utf-8")
        current = hashlib.sha256(combined).hexdigest()

    return current == proof["root_hash"]

JavaScript implementation

async function verifyMerkleProof(proof) {
  let current = proof.leaf_hash;

  for (let i = 0; i < proof.proof_hashes.length; i++) {
    const sibling = proof.proof_hashes[i];
    const direction = proof.proof_directions[i];

    const combined = direction === "right"
      ? current + sibling
      : sibling + current;

    const encoded = new TextEncoder().encode(combined);
    const hashBuffer = await crypto.subtle.digest("SHA-256", encoded);
    const hashArray = Array.from(new Uint8Array(hashBuffer));
    current = hashArray.map(b => b.toString(16).padStart(2, "0")).join("");
  }

  return current === proof.root_hash;
}

Worked example: 4-leaf tree

Consider four tracks with the following record hashes (already sorted lexicographically):

Leaf 0: 1111111111111111111111111111111111111111111111111111111111111111
Leaf 1: 2222222222222222222222222222222222222222222222222222222222222222
Leaf 2: 3333333333333333333333333333333333333333333333333333333333333333
Leaf 3: 4444444444444444444444444444444444444444444444444444444444444444

Tree structure

                        Root
                       /    \
                    H01      H23
                   /   \    /   \
                Leaf0 Leaf1 Leaf2 Leaf3

Step-by-step construction

Layer 0 (leaves): [Leaf0, Leaf1, Leaf2, Leaf3]

Layer 1 (parents):

• H01 = SHA-256("1111...1111" + "2222...2222")
• H23 = SHA-256("3333...3333" + "4444...4444")

Layer 2 (root):

• Root = SHA-256(H01 + H23)

Proof for Leaf 2

To prove that Leaf 2 is in the tree, the proof contains:

{
  "leaf_hash": "3333333333333333333333333333333333333333333333333333333333333333",
  "proof_hashes": [
    "4444444444444444444444444444444444444444444444444444444444444444",
    "<H01 hash>"
  ],
  "proof_directions": ["right", "left"],
  "root_hash": "<Root hash>",
  "leaf_index": 2,
  "total_leaves": 4
}

Verification steps:

1. Start with current = Leaf2 (3333...3333)
2. Sibling Leaf3 is on the right: current = SHA-256(current + "4444...4444") = H23
3. Sibling H01 is on the left: current = SHA-256(H01 + current) = Root
4. Compare current with root_hash — they match. The proof is valid.

Proof size

For a tree with n leaves, the proof contains ceil(log2(n)) sibling hashes. For a catalogue of 1,000 tracks, each proof is only 10 hashes (640 hex characters). This logarithmic scaling means proof size remains practical even for very large catalogues.

Catalogue size	Proof depth	Proof data
10 tracks	4 hashes	256 bytes
100 tracks	7 hashes	448 bytes
1,000 tracks	10 hashes	640 bytes
10,000 tracks	14 hashes	896 bytes
100,000 tracks	17 hashes	1,088 bytes