Building Merkle Proofs for Inventory Events

When a DEA inspector or a diversion investigator questions a single dispense, you need to prove that one event was part of an anchored audit batch — without handing over the hundreds of unrelated events in the same window. A Merkle inclusion proof is exactly that instrument: the minimal set of sibling hashes that lets anyone recompute the batch’s root from one leaf, confirming the event belongs to the anchored record while disclosing nothing else. This recipe implements proof generation and verification for a batch of inventory-event hashes using only Python’s standard library. It sits within Merkle-Tree Audit Anchoring, which defines how the root is computed and why it is tamper-evident; here the focus is the narrow, high-value operation of proving membership in that root.

The proof is small — logarithmic in the batch size — and self-contained. Given a leaf and its sibling path, the verifier walks up the tree hashing pairs until it reaches a candidate root, then compares that root to the one bound in the RFC 3161 token. If they match, the event provably existed inside the anchored batch; if a single byte of the event was altered, the recomputed root diverges and verification fails. That binary outcome is what makes an inclusion proof usable as evidence.

Problem framing

The parent reference establishes that a batch of controlled-substance events is reduced to a single Merkle root and anchored with an RFC 3161 token. That root proves the batch as a whole is intact, but audit questions are almost always about one event: “show me that this Schedule II dispense at 14:07 was in the record you anchored.” Reproducing the whole batch to answer that is both wasteful and a HIPAA problem — it would disclose every other patient’s event in the window. The inclusion proof solves this by extracting only the sibling hashes on the path from the target leaf to the root, so the verifier needs the one event plus a short list of opaque hashes and nothing more.

Correctness here is unforgiving. The proof must use the identical hashing rules — domain separation and odd-node handling — that produced the anchored root, or a valid event will appear fraudulent. The two operations that follow, build_tree and verify_proof, are therefore written as an exact pair, and the test block proves both that a genuine event verifies and that a tampered one fails.

Prerequisites & environment

• Python 3.11+ — the code uses dataclasses(frozen=True) and modern typing syntax.
• Standard library only: hashlib, dataclasses, logging, datetime. Add pytest only for the test block.
• Regulatory context to hold: 45 CFR § 164.312(c)(1) (integrity — the proof is an integrity check), 45 CFR § 164.312(a)(1) (minimum necessary — the proof discloses only the target event), and 21 CFR § 1304.04 (retrievable records — a proof makes a single retained event verifiable). The domain-separation and canonical-ordering rules must match the tree builder in Merkle-Tree Audit Anchoring.

Implementation: build the tree, generate and verify a proof

The module keeps every level of the tree so a proof can read sibling hashes directly. LEAF_PREFIX and NODE_PREFIX provide domain separation; odd levels duplicate their last node. A proof is an ordered list of (sibling_hash, is_left) steps, where is_left records whether the sibling sits on the left so the verifier concatenates in the correct order.

from __future__ import annotations

import hashlib
import logging
from dataclasses import dataclass
from datetime import datetime, timezone

logger = logging.getLogger("pharmacy.audit.merkle.proof")

LEAF_PREFIX = b"\x00"   # leaves hashed with 0x00, internal nodes with 0x01:
NODE_PREFIX = b"\x01"   # domain separation blocks second-preimage forgery.


def _sha(*parts: bytes) -> bytes:
    h = hashlib.sha256()
    for p in parts:
        h.update(p)
    return h.digest()


def leaf_hash(entry_hash: bytes) -> bytes:
    return _sha(LEAF_PREFIX, entry_hash)


def node_hash(left: bytes, right: bytes) -> bytes:
    return _sha(NODE_PREFIX, left, right)


@dataclass(frozen=True)
class ProofStep:
    sibling: bytes
    is_left: bool          # True if the sibling is the LEFT node at this level


def build_tree(entry_hashes: list[bytes]) -> list[list[bytes]]:
    """Return every level, leaves-first, so proofs can index siblings directly.

    Ordering follows the ledger sequence number (canonical). Odd levels duplicate
    the last node, matching the anchored root's construction exactly.
    """
    if not entry_hashes:
        raise ValueError("Cannot build a tree over an empty batch.")
    levels = [[leaf_hash(e) for e in entry_hashes]]
    while len(levels[-1]) > 1:
        cur = levels[-1]
        if len(cur) % 2 == 1:
            cur = cur + [cur[-1]]         # duplicate odd tail; do not mutate in place
        levels.append([node_hash(cur[i], cur[i + 1]) for i in range(0, len(cur), 2)])
    return levels


def merkle_root(entry_hashes: list[bytes]) -> bytes:
    return build_tree(entry_hashes)[-1][0]


def build_proof(entry_hashes: list[bytes], index: int) -> list[ProofStep]:
    """Sibling path from leaf `index` up to the root — the inclusion proof."""
    if not 0 <= index < len(entry_hashes):
        raise IndexError("Leaf index outside the batch.")
    levels = build_tree(entry_hashes)
    proof: list[ProofStep] = []
    idx = index
    for level in levels[:-1]:              # every level except the root
        padded = level + [level[-1]] if len(level) % 2 == 1 else level
        pair = idx ^ 1                     # sibling is the other node in the pair
        proof.append(ProofStep(sibling=padded[pair], is_left=(pair < idx)))
        idx //= 2
    return proof


def verify_proof(entry_hash: bytes, proof: list[ProofStep], expected_root: bytes) -> bool:
    """Recompute the root from one leaf and its sibling path; compare to anchor."""
    computed = leaf_hash(entry_hash)
    for step in proof:
        computed = (
            node_hash(step.sibling, computed)
            if step.is_left
            else node_hash(computed, step.sibling)
        )
    ok = computed == expected_root
    logger.info(
        "merkle_proof_verified result=%s root=%s steps=%d",
        "PASS" if ok else "FAIL", expected_root.hex(), len(proof),
    )
    return ok

The proof is derived from the retained leaves on demand; it is never stored, because it is fully determined by the batch. The is_left flag is the load-bearing detail — concatenating a sibling on the wrong side yields a different, wrong root, so the flag must be captured from the tree, not assumed.

Verification & testing

Two properties must be proven: a genuine event verifies against the anchored root, and any tampering — to the event or to a proof hash — makes verification fail. The pytest block below covers both, plus the odd-leaf-count case that exercises node duplication.

import hashlib
import pytest
from merkle_proof import build_proof, merkle_root, verify_proof


def _entries(n: int) -> list[bytes]:
    return [hashlib.sha256(f"inventory-event-{i}".encode()).digest() for i in range(n)]


def test_valid_proof_verifies():
    entries = _entries(4)
    root = merkle_root(entries)
    proof = build_proof(entries, index=1)
    assert verify_proof(entries[1], proof, root) is True


def test_tampered_event_fails():
    entries = _entries(4)
    root = merkle_root(entries)
    proof = build_proof(entries, index=1)
    forged = hashlib.sha256(b"back-dated-dispense").digest()
    assert verify_proof(forged, proof, root) is False       # altered event -> wrong root


def test_tampered_proof_hash_fails():
    entries = _entries(4)
    root = merkle_root(entries)
    proof = build_proof(entries, index=2)
    proof[0] = proof[0].__class__(sibling=b"\x00" * 32, is_left=proof[0].is_left)
    assert verify_proof(entries[2], proof, root) is False


def test_odd_leaf_count_duplicates_tail():
    entries = _entries(5)                                    # forces odd-node handling
    root = merkle_root(entries)
    for i in range(5):
        assert verify_proof(entries[i], build_proof(entries, i), root) is True

The emitted audit line records only the outcome and the root, never the event body or any patient identifier:

INFO pharmacy.audit.merkle.proof merkle_proof_verified result=PASS \
     root=b8f1c2...9a3e steps=2

Re-running verify_proof for a stored event against the anchored root is the inspection check: a PASS proves that exact event was in the anchored batch, and a FAIL on an entry that should verify is the tamper signal an integrity control under 45 CFR § 164.312(c)(1) exists to surface. The root itself is proven to have existed at a point in time by the RFC 3161 timestamp anchor, so a passing proof plus a valid token together establish both membership and existence-at-time.

Gotchas & compliance pitfalls

• Odd-node duplication must match the builder. If the tree that produced the anchored root duplicated the last node on odd levels but your proof code pairs it with a neighbor instead, valid events fail verification. The builder and the proof generator must share one implementation — never two copies that can drift.
• Second-preimage attacks without domain separation. Hashing leaves and internal nodes the same way lets an attacker present an internal node’s preimage as a two-leaf “event,” forging a proof. The 0x00/0x01 prefixes are not optional decoration; they are the defense, and they must be applied identically on both paths.
• Canonical leaf ordering. Leaves must be ordered by ledger sequence number, not by arrival time or by any map iteration order. A batch hashed in a different order yields a different root, so a proof built against the “wrong” ordering silently fails — quarantine any batch whose ordering cannot be reproduced.
• Concatenation direction. The is_left flag decides whether the sibling is prepended or appended before hashing. Assuming a fixed side “because index 1 is on the right” breaks the moment the path turns; always read the side from the tree.
• Byte hashes, not hex strings. Hash and concatenate raw 32-byte digests. Mixing hex-encoded strings into the tree produces a structurally different root that will not match an anchor built from bytes, and the mismatch is easy to miss because both look like valid hashes.
• Proofs are derived, never trusted from the wire. A proof supplied by an untrusted party is only meaningful once verified against a root you already trust — the anchored, timestamped root. Verifying a proof against a root that itself came from the same untrusted source proves nothing.

Frequently Asked Questions

Related

• Merkle-Tree Audit Anchoring — parent reference: how the root is built and anchored.
• Anchoring Audit Logs to RFC 3161 Timestamps — proving the root existed at a point in time.
• Audit Boundary Definition & Scope — how events enter the log the proof draws from.
• Core Architecture & DEA Compliance Frameworks — the immutable-ledger foundation this recipe supports.