What Merkle Proofs Have to Do with Verifiable AI Memory

A million memories. You want proof that entry number 471,203 is in the log and has not been edited since it was written. The proof is 20 hashes, 640 bytes at SHA-256, and verifying it takes 20 hash computations on the client. The server never sends you another user's data, never sends you the database, and cannot forge the proof without finding a SHA-256 collision.

That ratio, log2(n) hashes to prove membership in an n-element set, is why Merkle trees keep showing up in systems that need auditability without disclosure. It is not new and it is not blockchain-specific. Certificate Transparency has been running exactly this construction over billions of TLS certificates since 2013.

Building the tree

Leaves are hashes of records. Internal nodes are hashes of their two children concatenated. The root, called the tree head, is a single 32-byte value that commits to every leaf and their order.

leaf_hash(record)   = H(0x00 || record)
node_hash(l, r)     = H(0x01 || l || r)

                    root = H(0x01 || H_ab || H_cd)
                          /                    \
              H_ab = H(01|a|b)           H_cd = H(01|c|d)
                /        \                  /        \
             a=L(m0)   b=L(m1)          c=L(m2)   d=L(m3)

The domain-separation prefixes are load-bearing. Without the leading 0x00 and 0x01bytes, an attacker can present an internal node's hash as if it were a leaf, and the verifier cannot distinguish a record from a subtree. That is the second-preimage attack on unprefixed Merkle trees, and it is the exact reason RFC 6962 specifies those prefixes in section 2.1. Copy the RFC, do not invent your own hashing rule.

Odd node counts do not get duplicated. Bitcoin duplicates the last hash when a level has an odd number of nodes, which introduces a known malleability quirk. RFC 6962 instead splits at the largest power of two less than n, which keeps the tree well-defined for any n and makes consistency proofs work cleanly as the log grows. Follow the RFC here too.

The inclusion proof

To prove leaf i is in a tree of size n, the server sends the sibling hash at each level on the path from that leaf to the root. The client recomputes upward and compares to a tree head it already trusts.

function verify_inclusion(leaf, index, tree_size, proof, expected_root):
    computed = leaf_hash(leaf)
    i = index
    n = tree_size

    for sibling in proof:
        if n == 1:
            return false                              # proof longer than the tree

        if (i mod 2 == 1) or (i + 1 == n):
            computed = node_hash(sibling, computed)   # we sit on the right
            while i mod 2 == 0:                       # skip padded levels
                i = i / 2
                n = n / 2
        else:
            computed = node_hash(computed, sibling)   # we sit on the left

        i = floor(i / 2)
        n = floor((n + 1) / 2)

    return n == 1 and computed == expected_root

The whole trick is that the position bit at each level tells you the concatenation order. Get the order wrong and you compute a different root, so the proof fails closed. The n == 1 check at the end matters: without it, a proof of the wrong length against a misreported tree size can be made to verify.

Proof size for realistic stores: 1,000 memories is 10 hashes (320 bytes). One million is 20 hashes (640 bytes). One billion is 30 hashes (960 bytes). The proof grows by 32 bytes every time the log doubles, which is why this scales to a log you never prune.

Consistency proofs are the part that actually matters

Inclusion alone is weak. It proves your record is in this tree, presented with this root. A dishonest server can maintain two divergent logs and hand each client a root consistent with the version it wants that client to believe. Inclusion proofs against a root you were just handed prove nothing you did not already assume.

A consistency proof closes that. Given an old tree head at size m and a new one at size n (with m < n), the proof is a set of subtree hashes demonstrating that the size-n tree contains the size-m tree unchanged as a prefix. It is also O(log n) hashes. If it verifies, then every one of the first m leaves is still exactly where and what it was. Records were appended, nothing was rewritten.

That is the append-only property, and it is what converts "your memory is stored" into "your memory cannot have been silently edited." The client keeps the most recent tree head it has verified, and on each new head it checks consistency with the old one. A server that edits leaf 471,203 must produce a new root, and there is no consistency proof from the old head to that new root. The tampering is not merely detectable, it is cryptographically impossible to hide from a client that keeps checking.

What this does not give you

This is where most writing on the topic stops, and stopping there is misleading. Be precise about the limits.

• It does not prove the content is true or correct. A Merkle log will happily commit to a memory that says the deployment succeeded when it failed. Integrity is not accuracy. All the tree guarantees is that whatever was written is what you read back.
• It does not prevent deletion by omission.Append-only means committed leaves cannot change. It does not mean the server committed the record you asked it to commit. If a write is dropped before it enters the tree, there is no leaf and nothing to detect. The mitigation is a signed receipt at write time (Certificate Transparency's signed certificate timestamp is exactly this): a promise, signed by the server, to include the record within some window. Then a missing leaf is provable misbehavior with the server's own signature attached.
• It does nothing unless the client verifies. A proof no one checks is a decorative byte string. Verification has to be in the client, running on every fetch, and failing loudly. Shipping proof generation without proof checking is theater.
• You still need a trustworthy source of tree heads.This is the hard, unglamorous problem: split-view. A server can show client A one log and client B another, and each client's local chain of consistency proofs is internally coherent. Nothing in the tree math detects it, because both logs are individually valid.

The only real answers to split-view are social and infrastructural. Gossip: clients exchange tree heads and compare. Witnesses: independent parties co-sign the head, so a client refuses any head lacking k witness signatures. Public mirrors, so heads are pinned somewhere the operator does not control. Certificate Transparency needed a decade of ecosystem work to make this stick, and the witness cosigning model is still evolving. Any single-vendor system publishing its own signed heads with no external witness has reduced trust in the operator, not eliminated it, and should say so plainly.

The realistic value proposition is narrower than the marketing version but still worth building: with signed write receipts, verified inclusion proofs, and consistency checks across heads, silent retroactive editing goes from undetectable to a provable breach the operator cannot deny. That is a meaningful downgrade in what you have to trust.

For a memory system this matters more than it does for most storage, because the stored data is what an AI treats as ground truth about you. An edited memory does not surface as a wrong file, it surfaces as a model confidently asserting something you never said. The integrity and encryption properties Unimatrix currently guarantees, and the boundaries of each, are written out on the security page.