Traversal of the Merkle Search Tree inside a repository checkout.

A com.atproto.sync.getRepo CAR (see ProtoRune.Atproto.Sync.get_repo/2) contains the repository's MST as DAG-CBOR node blocks. Each node holds a nullable left subtree link l and an ordered list of entries e, where every entry maps a collection/rkey key to the CID of a record block:

%{
  "l" => left_cid | nil,
  "e" => [
    %{"p" => prefix_len, "k" => key_suffix, "v" => record_cid, "t" => subtree_cid | nil}
  ]
}

Keys are prefix-compressed: an entry's full key is the first p bytes of the previous key in traversal order concatenated with k. Traversal is depth-first in-order (left subtree, then each entry followed by its right subtree t), which yields entries in sorted key order.

The MST root CID is the data field of the commit block, itself found under the CAR header's root CID (see ProtoRune.CAR.read/1).

Trust model

This module performs no verification: no key hashing, no inclusion proofs, no diffing. The blocks are trusted as delivered by the source PDS, matching the trust model of ProtoRune.Atproto.Sync.