didbot_data/mst/
mod.rs

1//! The Merkle search tree a repository is keyed by.
2//!
3//! atproto does not store a repository as a map. It stores it as a tree whose
4//! shape is decided by the keys themselves, so that two servers holding the
5//! same records build the same tree, root it at the same CID, and can each
6//! verify the other's commit. Nothing about the shape is an implementation's
7//! choice: not the layering, not the node encoding, not which node a key
8//! lands in.
9//!
10//! Three pieces, in the order they depend on each other:
11//!
12//! * [`key_height`] and [`common_prefix_len`] are the two pure functions the
13//!   shape comes from. They are checked against upstream's `mst/` vectors
14//!   without a tree, which is the stronger test.
15//! * [`Tree`] is the tree: nodes, layering, the DAG-CBOR node encoding, and
16//!   the root CID that a commit signs.
17//! * [`Tree::path`] is the walk from the root to one key, which is what an
18//!   inclusion — or exclusion — proof is made of.
19//! * [`Store`] is a tree that arrived from somewhere else: blocks, a claimed
20//!   root, and no trust. [`Node::decode`] reads one of those blocks and
21//!   [`diff`] says what changed between two roots.
22//!
23//! # Two ways to arrive at a root
24//!
25//! [`Tree::build`] takes the whole leaf set at once and is a pure function of
26//! it. [`Tree::insert`] and [`Tree::remove`] change one key of a tree already
27//! built, rewriting only the nodes whose key range holds it, and answer which
28//! nodes that created and removed. The shape is a function of the key set, so
29//! both ways must land on the same nodes. The tests in `edit.rs` hold them to
30//! that after every step of random edit sequences, and the corpus in
31//! `crates/didbot/tests/conformance/mst_edit.rs` does it for every pair of
32//! upstream's exhaustive trees.
33//!
34//! # The layering rule, which is the part that is easy to get wrong
35//!
36//! A key's height says which layer it sits on. Every key below a node's layer
37//! goes into a subtree, and the subtree's node is at **exactly one layer
38//! below**, whether or not any key sits there. A run of keys at layer 0
39//! hanging under a layer-3 node is therefore three nodes deep, two of which
40//! hold no entries at all and exist only to carry a left pointer.
41//!
42//! Collapsing those — putting the subtree at the layer of its own tallest key
43//! — gives a tree that is smaller, holds every record, answers every lookup,
44//! and roots at a CID no other implementation will ever agree with. Both
45//! rules were written and run against real repositories; see
46//! `tests/reference_repository.rs`, which is where the answer came from.
47//!
48//! The root is the exception: it sits at the height of the tallest key in the
49//! repository, with nothing above it.
50
51mod edit;
52mod read;
53mod shape;
54mod store;
55mod tree;
56
57pub use edit::Rewritten;
58pub use read::{NodeError, Parts};
59pub use shape::{common_prefix_len, key_height};
60pub use store::{diff, Diff, Found, RecordOp, Store, StoreError};
61pub use tree::{Entry, Node, Path, Tree};
didbot_data/mst/mod.rs

didbot_data/mst/
mod.rs
