Expand description
Merkle Search Tree (MST) — the atproto repo’s per-account record store.
The MST (Auvolat & Taïani, SRDS 2019) is a binary-tree-of-blocks keyed by
string record keys (<collection>/<rkey> paths — ONE tree per account repo
spans all of its collections). Its defining
property is that the shape of the tree is a deterministic function of the
key set — independent of insertion order — so two hosts with the same
records compute the same root CID. This is what makes the repo
consensus-free: any host can rebuild the tree and verify a peer’s root.
§Structure (matches the atproto reference)
Each MST node is a NodeData block encoded as DAG-CBOR:
NodeData {
l: Option<Cid>, // leftmost subtree (key space < first key)
e: [TreeEntry { // entries, in ascending key order
p: usize, // shared-prefix length with previous key
k: Vec<u8>, // remainder of this key (suffix after the prefix)
v: Cid, // the record this entry addresses
t: Option<Cid>, // right subtree (keys in (this_key, next_key))
}]
}A node lives at a level (height). The level of a key is the number of
trailing zero bits in sha256("<collection>/<rkey>") — so roughly 1/2 of
keys are level-0 leaves, 1/4 are level-1, etc. Insertion walks down the tree
by level, splitting subtrees when a key’s level matches the current node’s.
§CID
Each node’s CID is CIDv1 dag-cbor over its canonical DAG-CBOR bytes. The
MST root CID is the commit’s data field.
Structs§
- Node
- An in-memory MST over an account repo’s records (all collections, keyed by
<collection>/<rkey>). - Node
Data - An MST node — the unit addressed by a CID.
- Node
Entry - Proof
- An MST inclusion proof for a single record.
- Tree
Entry - One entry in an MST node.
Enums§
- Proof
Step - One step of an MST inclusion proof.