Merkle Tree Provenance for Binary Transparency Receipts

I got tired of the same old provenance story: “we stored a hash on a ledger, so trust is solved.” In practice, that’s often incomplete—especially when the thing you’re proving is a set of artifacts and you need a verifiable receipt that a particular binary build included particular upstream files.

So I built a tiny “binary transparency receipt” system: given a build’s inputs (multiple files), it computes a Merkle tree (a hash tree where each internal node is the hash of its children). Then it produces a JSON receipt containing:

• the Merkle root (a single fingerprint for the whole input set),
• the per-file Merkle inclusion proofs (“here’s why file X is in the set”),
• and a signature over the receipt (using Ed25519).

This post walks through what I implemented and what actually happens when you run it.

---

What the receipt proves (and what it doesn’t)

• Proves: “This exact set of input file bytes was used, and each file’s inclusion is verifiable against the Merkle root.”
• Does not prove: “Those bytes correspond to some real-world license or that someone followed policy.” That policy needs additional processes. The cryptography here only covers integrity of the referenced bytes and inclusion in the set.

---

The niche part: a “file receipt” Merkle tree keyed by chunk hashes

A simple Merkle tree over whole files is common. The niche choice I made (and stuck with) is:

1. For each file, split it into fixed-size chunks (e.g., 1024 bytes).
2. Hash each chunk.
3. Build a per-file chunk Merkle tree, and use its root as the file hash.
4. Build a global Merkle tree over the list of file roots.
5. Produce inclusion proofs at the file level (not chunk level) because receipts are usually consumed by build systems and auditors who care which files were included, not every chunk boundary.

This makes the receipt resilient to re-chunking and avoids storing full file contents in the receipt—only hashes and proofs.

---

Working code: build a receipt, verify it, and check inclusion proofs

Below is a complete Python implementation using:

• hashlib for SHA-256,
• cryptography for Ed25519 signatures,
• canonical JSON for stable receipts (so signatures remain stable).

1) Receipt builder + verifier

import hashlib
import json
from dataclasses import dataclass
from typing import List, Tuple, Dict, Any

from cryptography.hazmat.primitives.asymmetric.ed25519 import (
    Ed25519PrivateKey, Ed25519PublicKey
)
from cryptography.hazmat.primitives import serialization


CHUNK_SIZE = 1024  # bytes


def sha256(b: bytes) -> bytes:
    return hashlib.sha256(b).digest()


def canonical_json(obj: Any) -> bytes:
    # Stable, signature-friendly JSON encoding.
    return json.dumps(obj, sort_keys=True, separators=(",", ":"), ensure_ascii=False).encode("utf-8")


def chunk_bytes(data: bytes, chunk_size: int) -> List[bytes]:
    return [data[i:i + chunk_size] for i in range(0, len(data), chunk_size)]


def merkle_parent(left: bytes, right: bytes) -> bytes:
    # Domain-separated node hashing to avoid accidental collisions with leaf hashing.
    return sha256(b"\x01" + left + right)


def merkle_leaf(hash_of_chunk: bytes) -> bytes:
    # Leaves are hashed with a domain separator too.
    return sha256(b"\x00" + hash_of_chunk)


def build_merkle_root(leaves: List[bytes]) -> bytes:
    """
    Builds a Merkle root from already-hashed leaves (bytes).
    If there's an odd number at a level, I duplicate the last node.
    """
    if not leaves:
        # Deterministic root for empty set.
        return sha256(b"\x02" + b"")  # domain: empty

    level = leaves[:]
    while len(level) > 1:
        if len(level) % 2 == 1:
            level.append(level[-1])
        next_level = []
        for i in range(0, len(level), 2):
            next_level.append(merkle_parent(level[i], level[i + 1]))
        level = next_level
    return level[0]


def merkle_proof(leaves: List[bytes], index: int) -> List[Tuple[bytes, str]]:
    """
    Returns a proof for leaves[index] as a list of (sibling_hash, direction),
    where direction indicates whether sibling is on the left or right.
    """
    if index < 0 or index >= len(leaves):
        raise IndexError("proof index out of range")

    proof = []
    level = leaves[:]
    idx = index

    while len(level) > 1:
        if len(level) % 2 == 1:
            level.append(level[-1])

        # Determine sibling index
        if idx % 2 == 0:
            sibling_idx = idx + 1
            direction = "right"
        else:
            sibling_idx = idx - 1
            direction = "left"

        sibling_hash = level[sibling_idx]
        proof.append((sibling_hash, direction))

        # Move up
        next_level = []
        for i in range(0, len(level), 2):
            next_level.append(merkle_parent(level[i], level[i + 1]))
        idx //= 2
        level = next_level

    return proof


def verify_merkle_proof(leaf: bytes, proof: List[Tuple[bytes, str]], root: bytes) -> bool:
    """
    Recompute the path to the root using proof steps.
    """
    h = leaf
    for sibling_hash, direction in proof:
        if direction == "right":
            h = merkle_parent(h, sibling_hash)
        else:
            h = merkle_parent(sibling_hash, h)
    return h == root


def file_root_from_bytes(data: bytes, chunk_size: int = CHUNK_SIZE) -> bytes:
    """
    File root = Merkle root of per-chunk leaves.
    Leaves are hash(chunk bytes), then domain-wrapped as Merkle leaves.
    """
    chunks = chunk_bytes(data, chunk_size)
    chunk_hashes = [sha256(c) for c in chunks]
    leaves = [merkle_leaf(ch) for ch in chunk_hashes]
    return build_merkle_root(leaves)


@dataclass
class FileInclusionProof:
    filename: str
    file_root_hex: str
    file_index: int
    merkle_proof: List[Dict[str, str]]  # each: { "sibling": hex, "direction": "left|right" }


def build_global_tree(file_roots: List[bytes]) -> bytes:
    # Global leaves are file roots (already hash-like), domain-wrap them.
    leaves = [sha256(b"\x03" + r) for r in file_roots]
    return build_merkle_root(leaves)


def global_leaf(file_root: bytes) -> bytes:
    return sha256(b"\x03" + file_root)


def build_receipt(files: Dict[str, bytes], private_key: Ed25519PrivateKey) -> Dict[str, Any]:
    # Sort filenames to make receipt deterministic.
    filenames = sorted(files.keys())
    file_roots = [file_root_from_bytes(files[name]) for name in filenames]

    global_leaves = [global_leaf(r) for r in file_roots]
    global_root = build_merkle_root(global_leaves)

    proofs = []
    for idx, name in enumerate(filenames):
        leaf = global_leaves[idx]
        proof = merkle_proof(global_leaves, idx)
        proofs.append(
            FileInclusionProof(
                filename=name,
                file_root_hex=file_roots[idx].hex(),
                file_index=idx,
                merkle_proof=[{"sibling": s.hex(), "direction": d} for (s, d) in proof],
            )
        )

    # Receipt payload excludes signature (signature covers canonical payload).
    payload = {
        "version": 1,
        "scheme": {
            "chunk_size": CHUNK_SIZE,
            "hash": "sha256",
            "merkle": {
                "leaf_domain": "0x00 for chunk leaf wrapper",
                "node_domain": "0x01 for internal nodes",
                "global_leaf_domain": "0x03 for file roots wrapper",
                "empty_root_deterministic": True,
                "odd_duplication": True,
            },
            "sig": "ed25519",
        },
        "file_count": len(files),
        "global_root_hex": global_root.hex(),
        "inputs": [
            {
                "filename": p.filename,
                "file_root_hex": p.file_root_hex,
                "file_index": p.file_index,
                "inclusion_proof": p.merkle_proof,
            }
            for p in proofs
        ],
    }

    signature = private_key.sign(canonical_json(payload)).hex()

    receipt = {
        "payload": payload,
        "signature_hex": signature,
        "public_key_hex": private_key.public_key().public_bytes(
            encoding=serialization.Encoding.Raw,
            format=serialization.PublicFormat.Raw,
        ).hex(),
    }
    return receipt


def verify_receipt(receipt: Dict[str, Any]) -> bool:
    payload = receipt["payload"]
    signature_hex = receipt["signature_hex"]
    pub_hex = receipt["public_key_hex"]

    signature = bytes.fromhex(signature_hex)
    pub = Ed25519PublicKey.from_public_bytes(bytes.fromhex(pub_hex))

    # Verify signature first.
    pub.verify(signature, canonical_json(payload))
    # If it doesn't raise, it's valid.

    global_root = bytes.fromhex(payload["global_root_hex"])
    for inp in payload["inputs"]:
        filename = inp["filename"]
        file_root = bytes.fromhex(inp["file_root_hex"])

        # Recreate the global leaf used in the tree.
        leaf = global_leaf(file_root)

        # Verify inclusion proof for this file root against global_root.
        proof = [(bytes.fromhex(step["sibling"]), step["direction"]) for step in inp["inclusion_proof"]]
        ok = verify_merkle_proof(leaf, proof, global_root)
        if not ok:
            return False

    return True


def prove_file_inclusion(receipt: Dict[str, Any], target_filename: str, target_bytes: bytes) -> bool:
    """
    Verifies a specific filename's inclusion using:
    - recomputed per-file root from the provided bytes,
    - the inclusion proof in the receipt.
    """
    payload = receipt["payload"]
    global_root = bytes.fromhex(payload["global_root_hex"])

    # Find the matching input entry.
    target_entry = None
    for inp in payload["inputs"]:
        if inp["filename"] == target_filename:
            target_entry = inp
            break
    if target_entry is None:
        return False

    # Compute file root from bytes and compare to receipt's file_root_hex.
    recomputed_file_root = file_root_from_bytes(target_bytes)
    if recomputed_file_root.hex() != target_entry["file_root_hex"]:
        return False

    leaf = global_leaf(recomputed_file_root)
    proof = [(bytes.fromhex(step["sibling"]), step["direction"]) for step in target_entry["inclusion_proof"]]
    return verify_merkle_proof(leaf, proof, global_root)


def demo():
    # Two "upstream artifacts" a build might depend on.
    files = {
        "vendor/zlib-1.2.13.tar.gz": b"hello-from-zlib" * 200,
        "toolchain/gcc-wrapper.sh": b"#!/bin/sh\necho build" * 50,
        "patches/fix-bug.diff": b"diff --git a b\n+new-line\n" * 80,
    }

    private_key = Ed25519PrivateKey.generate()
    receipt = build_receipt(files, private_key)

    print("Receipt verification:", verify_receipt(receipt))

    # Successful per-file check:
    ok = prove_file_inclusion(
        receipt,
        "vendor/zlib-1.2.13.tar.gz",
        files["vendor/zlib-1.2.13.tar.gz"],
    )
    print("Per-file inclusion check (correct bytes):", ok)

    # Failing per-file check (tamper bytes):
    tampered = files["vendor/zlib-1.2.13.tar.gz"] + b"EVIL"
    ok2 = prove_file_inclusion(
        receipt,
        "vendor/zlib-1.2.13.tar.gz",
        tampered,
    )
    print("Per-file inclusion check (tampered bytes):", ok2)


if __name__ == "__main__":
    demo()

2) Run it

pip install cryptography
python receipt_merkle_provenance.py

Expected output should look like:

• Receipt verification: True
• Per-file inclusion check (correct bytes): True
• Per-file inclusion check (tampered bytes): False

The key observation: the receipt stays the same, but when I append “EVIL” to the file bytes, the per-file root changes, and the inclusion proof no longer matches the signed global root.

---

What happens internally (a concrete walkthrough)

I’ll describe the exact sequence for one file, say vendor/zlib-1.2.13.tar.gz:

1. Chunking: I split the bytes into 1024-byte chunks.
2. Chunk hashing: each chunk becomes sha256(chunk_bytes).
3. Chunk leaf formation: each chunk hash is wrapped as a Merkle leaf: sha256(0x00 || chunk_hash).
4. Per-file Merkle root: I build a Merkle tree from the chunk leaves and take the top hash as file_root.
5. Global tree construction:
   • I sort all filenames and produce a list of file_roots.
   • Each file_root becomes a global leaf as sha256(0x03 || file_root).
   • I compute the Merkle root over all global leaves → global_root.
6. Inclusion proof: I record, for each file, the sibling hashes needed to recompute global_root from that file’s global leaf.
7. Signing: I canonicalize the payload JSON (stable key ordering and formatting) and sign it with Ed25519.
8. Verification:
   • I verify the Ed25519 signature over the payload.
   • For each input, I recompute the path hash from the inclusion proof and confirm it equals global_root.
9. Per-file validation:
   • I recompute the per-file Merkle root from provided bytes.
   • I confirm the recomputed file_root matches the file_root_hex embedded in the receipt.
   • I verify the file’s inclusion proof against the signed global_root.

---

Serialization format: a signed, audit-friendly JSON receipt

In this implementation, the receipt looks like:

• payload: versioned content with global root and inclusion proofs
• signature_hex: Ed25519 signature of the canonicalized payload
• public_key_hex: signer identity (raw Ed25519 public key)

This makes it easy for an auditor or CI system to store the receipt alongside build logs.

---

Conclusion

I learned that “provenance via a single ledger hash” often isn’t enough for real auditing workflows. By building a two-level Merkle model—chunk trees per file and a global tree across file roots—and then signing a receipt containing inclusion proofs, I ended up with a practical digital provenance artifact: a signed, verifiable statement that specific binary inputs were included, and a way to detect tampering with per-file checks that fail exactly as expected.