Skip to main content

Module mst

Module mst 

Source
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>).
NodeData
An MST node — the unit addressed by a CID.
NodeEntry
Proof
An MST inclusion proof for a single record.
TreeEntry
One entry in an MST node.

Enums§

ProofStep
One step of an MST inclusion proof.