the inversion algorithm#

how verifyCommitDiff proves a commit is a valid state transition.

the claim being verified#

given:

• a signed commit with MST root data_cid (the "after" state)
• a CAR containing the commit block + changed MST nodes + new records
• a list of operations (create/update/delete with paths and CIDs)
• a previous MST root prev_data (the "before" state, from the preceding commit)

prove: the operations, applied to prev_data, produce data_cid.

the trick: instead of applying ops forward (which would require the full previous tree), invert them on the new tree and check if you get back to the old root.

why inversion instead of forward application#

forward application would require:

1. the full previous MST (potentially millions of entries)
2. applying each op to produce the new tree
3. comparing the new root against data_cid

inversion requires:

1. only the partial MST from the CAR (changed nodes only)
2. reversing each op on the new tree
3. comparing the inverted root against prev_data

the CAR already contains the new partial tree. unchanged subtrees become stubs — their CIDs are known but their contents aren't loaded. this is the key insight: you only need blocks for the parts that changed.

step by step#

source: repo_verifier.zig:387-469

1. parse CAR, extract commit#

loadCommitFromCAR(blocks) → { commit, unsigned_bytes, repo_car }

the commit is CBOR with fields: did, version, data (MST root CID), rev, prev, sig. the unsigned bytes are re-encoded without sig for signature verification.

2. verify signature#

verify(unsigned_bytes, commit.sig, public_key) → ok | error

proves the commit came from the account's signing key. this is independent of MST — it proves authorship.

3. load partial MST from CAR#

Mst.loadFromBlocks(repo_car, commit.data_cid) → partial tree

source: mst.zig:459-480

walks from the root block, loading nodes whose blocks exist in the CAR. blocks not found become ChildRef.stub — a CID placeholder. the result is a tree where:

• changed paths have fully loaded nodes
• unchanged subtrees are stubs (just their hash)

4. copy tree for inversion#

tree.copy() → inverted

deep clone. stubs stay as stubs. the original tree is preserved.

5. normalize operations#

normalizeOps(msg_ops) → sorted_ops

source: mst.zig:773-800

• sort: deletions first, then by path lexicographically
• reject duplicates (same path twice → DuplicatePath)

deletions first matters: if you invert a create before a delete on related paths, you might touch a node that should already be gone. ordering ensures deterministic application.

6. invert each operation#

source: mst.zig:804-820

for each op in sorted order:

each step is self-checking. if any assertion fails → InversionMismatch.

7. compute inverted root#

inverted.rootCid() → cid

traverses the (now-inverted) tree bottom-up. loaded nodes are serialized as DAG-CBOR and SHA-256 hashed. stubs contribute their known CIDs directly — this is safe because we trust the previous state.

if inversion needs to descend into a stub (operation touches an unchanged subtree), it fails with PartialTree — the CAR didn't include enough context.

8. compare#

inverted_root == prev_data → valid transition

if they match, the operations fully explain the state change from the old root to the new root. no hidden mutations, no missing ops, no reordering.

what stubs mean for the proof#

stubs are the mechanism that makes partial verification possible:

ChildRef = union(enum) {
    none,           — no child (leaf boundary)
    node: *Node,    — loaded from CAR, fully traversable
    stub: cbor.Cid, — CID known, content trusted
}

when computing rootCid():

• node → serialize, hash, produce CID
• stub → use the CID as-is (it's trusted from previous verification)
• none → encoded as null in CBOR

the proof chain holds because each stub was once a verified node in a previous commit. by induction, every stub's CID is correct.

error taxonomy#

the first three are the interesting ones — they distinguish between identity fraud (signature), history fraud (prevData), and operation fraud (inversion).