Module mst 

The Merkle search tree a repository is keyed by.

atproto does not store a repository as a map. It stores it as a tree whose shape is decided by the keys themselves, so that two servers holding the same records build the same tree, root it at the same CID, and can each verify the other’s commit. Nothing about the shape is an implementation’s choice: not the layering, not the node encoding, not which node a key lands in.

Three pieces, in the order they depend on each other:

• key_height and common_prefix_len are the two pure functions the shape comes from. They are checked against upstream’s mst/ vectors without a tree, which is the stronger test.
• Tree is the tree: nodes, layering, the DAG-CBOR node encoding, and the root CID that a commit signs.
• Tree::path is the walk from the root to one key, which is what an inclusion — or exclusion — proof is made of.
• Store is a tree that arrived from somewhere else: blocks, a claimed root, and no trust. Node::decode reads one of those blocks and diff says what changed between two roots.

Two ways to arrive at a root

Tree::build takes the whole leaf set at once and is a pure function of it. Tree::insert and Tree::remove change one key of a tree already built, rewriting only the nodes whose key range holds it, and answer which nodes that created and removed. The shape is a function of the key set, so both ways must land on the same nodes. The tests in edit.rs hold them to that after every step of random edit sequences, and the corpus in crates/didbot/tests/conformance/mst_edit.rs does it for every pair of upstream’s exhaustive trees.

The layering rule, which is the part that is easy to get wrong

A key’s height says which layer it sits on. Every key below a node’s layer goes into a subtree, and the subtree’s node is at exactly one layer below, whether or not any key sits there. A run of keys at layer 0 hanging under a layer-3 node is therefore three nodes deep, two of which hold no entries at all and exist only to carry a left pointer.

Collapsing those — putting the subtree at the layer of its own tallest key — gives a tree that is smaller, holds every record, answers every lookup, and roots at a CID no other implementation will ever agree with. Both rules were written and run against real repositories; see tests/reference_repository.rs, which is where the answer came from.

The root is the exception: it sits at the height of the tallest key in the repository, with nothing above it.

Modules

edit 🔒

Changing one key of a built tree without building it again.

read 🔒

Reading a node back out of a block.

shape 🔒

The two pure functions a Merkle search tree’s shape comes from.

store 🔒

A tree somebody else built: nodes by CID, and the walks over them.

tree 🔒

The tree: nodes, the layering, and the blocks they encode to.

Structs

Diff

What changed between two roots.

Entry

One entry in a node: a key, the record it names, and what hangs to its right.

Found

What a walk to one path found, and what proves it.

Node

One node of the tree.

Parts

A node’s contents in the form the tree algorithms want them.

Path

Which blocks prove what a tree says about one key.

RecordOp

One record that changed between two trees.

Rewritten

The blocks an edit added and took away.

Store

Blocks that are claimed to be a Merkle search tree.

Tree

A built Merkle search tree: a root CID and every block under it.

Enums

NodeError

Why a block is not a Merkle search tree node.

StoreError

Why a tree could not be walked.

Functions

common_prefix_len

How many leading bytes two keys share.

diff

Diffs two trees held in one store.

key_height

Which layer of the tree a key belongs on.