elixir-mst

An Elixir implementation of AT Protocol-flavoured Merkle Search Trees (MST).

Overview

A Merkle Search Tree is a content-addressed, ordered key/value structure. Every unique set of key/value pairs produces a unique root CID, making it suitable for Merkle proofs, efficient diffs, and repository synchronisation. This library implements the AT Protocol flavour: nodes are encoded as DRISL, keys are arbitrary byte strings, values are DASL.CID links, and tree depth is derived from the SHA-256 hash of each key.

Installation

Get elixir-mst from hex.pm by adding it to your mix.exs:

# mix.exs
def deps do
  [
    {:mst, "~> 0.1"}
  ]
end

Documentation can be found on HexDocs at https://hexdocs.pm/mst.

Quick start

# Build a tree
tree = MST.new()

val = DASL.CID.compute("my record data")
{:ok, tree} = MST.put(tree, "app.bsky.feed.post/3jqfcqzm3ft2j", val)
{:ok, ^val} = MST.get(tree, "app.bsky.feed.post/3jqfcqzm3ft2j")

# Mutate (persistent — the original tree is unchanged)
{:ok, tree2} = MST.put(tree, "app.bsky.feed.post/3jqfcqzm3fz2j", val)
{:ok, tree2} = MST.delete(tree2, "app.bsky.feed.post/3jqfcqzm3ft2j")

# Enumerate in sorted order
{:ok, pairs} = MST.to_list(tree2)
# => [{"app.bsky.feed.post/3jqfcqzm3fz2j", val}]

# Or stream lazily
tree2 |> MST.stream() |> Enum.each(fn {key, cid} -> ... end)

CAR import / export

# Export to a CARv1 binary
{:ok, car_bytes} = MST.to_car(tree)
File.write!("repo.car", car_bytes)

# Import from a CARv1 binary
{:ok, tree} = MST.from_car(File.read!("repo.car"))

Diffing two trees

{:ok, diff} = MST.diff(tree_a, tree_b)

diff.created_nodes  # MapSet of node CIDs added in tree_b
diff.deleted_nodes  # MapSet of node CIDs removed from tree_a

for %MST.Diff.Op{key: key, old_value: old, new_value: new} <- diff.record_ops do
  case {old, new} do
    {nil, cid} -> IO.puts("create  #{key} → #{cid}")
    {cid, nil} -> IO.puts("delete  #{key} (was #{cid})")
    {old, new} -> IO.puts("update  #{key}: #{old} → #{new}")
  end
end

This project is licensed under the MIT License