merkle_search_trees.md

Awesome Merkle Search Trees

Various MST implementations. Paper: https://inria.hal.science/hal-02303490/document

atproto docs: https://atproto.com/specs/repository

atproto-flavour

https://github.com/bluesky-social/atproto/tree/main/packages/repo/src/mst typescript "reference implementation"

https://gitlab.com/bnewbold/adenosine/-/blob/main/adenosine/src/mst.rs?ref_type=heads rust

https://github.com/blacksky-algorithms/rsky/tree/main/rsky-pds/src/repo/mst rust - afaik it intends to mirror the logic of the reference impl

https://github.com/snarfed/arroba/blob/main/arroba/mst.py python - likewise

https://github.com/DavidBuchanan314/atmst/tree/main/src/atmst/mst python - written "from first principles" but should behave identically to the other spec-compliant impls. diffing is a little half-baked at time of writing.

https://github.com/PassiveModding/atompds/tree/main/src/projects/Repo/MST - C#

https://github.com/DavidBuchanan314/picopds/blob/main/mst.py likewise, but it stores the whole MST in memory (no "block store" backing). prototype quality, no diffing.

https://github.com/mekaem/hexpds/tree/main/lib/hexpds/mst elixir, still WIP afaik

generic or non-atproto:

https://github.com/davidBuchanan314/merkle-search-tree python. no diffing. (includes some graphviz code, might aid understanding)

https://github.com/domodwyer/merkle-search-tree rust, looks to have been highly perf-optimised

misc

Test cases for validating atproto MST impls (wip): https://github.com/DavidBuchanan314/mst-test-suite