Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Merkle trees: verify an indexed scan record

Last updated: 7 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A binary hash tree summarizes an ordered batch in one root digest. This implementation hashes each record with a leaf prefix and each pair of child digests with a different branch prefix. Those prefixes keep a record byte string separate from a serialized branch. For an odd node count, the last node advances unchanged to the next level. A third prefix commits the batch size together with the tree digest in the final root. A proof carries only sibling digests on the record's path and marks whether each sibling is left or right. Verification reconstructs the path using the claimed index and size, rejects a missing or extra sibling, and compares the size-bound result with a trusted root. The root must arrive through a trusted channel; a proof cannot authenticate itself.

Operational case

A scan batch contains five byte records, including D-61:19 at index three. Its inclusion proof has three siblings under the chosen odd-node rule. With the batch's trusted root and size, the original record verifies true; changing it to D-61:20 verifies false. The record order, index, tree shape, byte encoding, and hash prefix rules are all part of the protocol. Two identical payloads at different positions are distinct occurrences for this proof. A caller who accepts an attacker-supplied root alongside an attacker-supplied proof learns only that they agree with each other, not that the scan belongs to an approved batch.

Working Python program

python
"""Ordered binary hash tree with index- and size-bound inclusion proofs."""

import hashlib


def leaf_digest(payload: bytes) -> bytes:
    return hashlib.sha256(b"\x00" + payload).digest()


def branch_digest(left: bytes, right: bytes) -> bytes:
    return hashlib.sha256(b"\x01" + left + right).digest()


def committed_root(size: int, tree_digest: bytes) -> bytes:
    return hashlib.sha256(b"\x02" + size.to_bytes(8, "big") + tree_digest).digest()


class ScanBatchTree:
    def __init__(self, scan_records: list[bytes]):
        if not 0 < len(scan_records) < 1 << 64:
            raise ValueError("batch size must fit the root commitment")
        self.size = len(scan_records)
        self.levels = [[leaf_digest(record) for record in scan_records]]
        while len(self.levels[-1]) > 1:
            level = self.levels[-1]
            parents = [branch_digest(level[position], level[position + 1])
                       if position + 1 < len(level) else level[position]
                       for position in range(0, len(level), 2)]
            self.levels.append(parents)
        self.root = committed_root(self.size, self.levels[-1][0])

    def proof(self, position: int) -> list[tuple[str, bytes]]:
        if not 0 <= position < self.size:
            raise IndexError(position)
        siblings = []
        for level in self.levels[:-1]:
            peer = position ^ 1
            if peer < len(level):
                siblings.append(("left" if position & 1 else "right", level[peer]))
            position //= 2
        return siblings


def verify_scan(payload: bytes, position: int, size: int,
                proof: list[tuple[str, bytes]], trusted_root: bytes) -> bool:
    if not 0 <= position < size < 1 << 64 or not isinstance(trusted_root, bytes) or len(trusted_root) != 32:
        return False
    batch_size = size
    current = leaf_digest(payload)
    proof_position = 0
    while size > 1:
        peer = position ^ 1
        if peer < size:
            if proof_position >= len(proof):
                return False
            side, sibling = proof[proof_position]
            if side != ("left" if position & 1 else "right") or not isinstance(sibling, bytes) or len(sibling) != 32:
                return False
            current = branch_digest(sibling, current) if side == "left" else branch_digest(current, sibling)
            proof_position += 1
        position //= 2
        size = (size + 1) // 2
    return proof_position == len(proof) and committed_root(batch_size, current) == trusted_root


scans = [b"D-19:47", b"D-26:31", b"D-47:61", b"D-61:19", b"D-83:52"]
batch = ScanBatchTree(scans)
inclusion = batch.proof(3)
print(verify_scan(scans[3], 3, batch.size, inclusion, batch.root))
print(verify_scan(b"D-61:20", 3, batch.size, inclusion, batch.root))
print(len(inclusion))

Output

Output
True
False
3

Time, space, and tradeoff

For N records containing B total input bytes, building all levels hashes O(B + N) bytes at fixed digest length and stores O(N) digests. A proof has O(log N) siblings and takes O(log N) time to extract from the stored levels. Verification hashes the submitted record, O(log N) fixed-size pairs, and one size-bound root, using O(log N) proof space and O(1) extra working space. This immutable batch rebuilds after any record change; it does not provide append consistency proofs, signatures, timestamps, or collision resistance beyond the chosen digest algorithm's assumptions. The root encoding here is this lesson's protocol, and its trusted delivery matters more than the short path's speed.

Common Mistakes

  • Do not accept an untrusted root and call the proof authenticated.
  • Do not swap sibling order when recomputing a parent digest.
  • Do not omit index and batch-size checks for an odd-shaped tree.
  • Do not hash leaves and branches under the same undifferentiated byte format.

Connected lessons

Apply the invariant in the scan batch audit project, then check the operations quiz.

Invertible Bloom tables: peel differences between replica ID sets examines a related structure with a different operation boundary.

data structures
range-query-structures
Storage details