Exosphere.ATProto.MST (Exosphere v0.2.0)

Merkle Search Tree (MST) for AT Protocol repositories.

A repository's records are stored in an MST: a deterministic, content-addressed key/value map from record paths (<collection>/<rkey>) to record CIDs. The structure depends only on the current set of keys (not insertion order), so the root CID is a stable fingerprint of the repository contents and is what a commit's data field points at.

This module can:

build/1 an MST from a set of path => CID entries, returning the root CID and the encoded node blocks (so you can verify a commit's data root or construct a repository).
read/2 an MST from a root CID and a block store back into a path => CID map (so you can verify and walk a repository checkout or the blocks of a firehose commit).
depth/1 compute the layer of a key, and valid_key?/1 validate a key.

Node format

Each node is DAG-CBOR with the shape:

%{
  "l" => CID | nil,   # left subtree (keys sorting before all entries)
  "e" => [            # entries, sorted by key
    %{
      "p" => integer, # bytes shared with the previous entry's key
      "k" => bytes,   # key suffix after the shared prefix
      "v" => CID,     # value (record CID)
      "t" => CID | nil # right subtree (keys between this and the next entry)
    }
  ]
}

Examples

iex> {:ok, root, _blocks} = Exosphere.ATProto.MST.build([])
iex> to_string(root)
"bafyreie5737gdxlw5i64vzichcalba3z2v5n6icifvx5xytvske7mr3hpm"

Summary

Types

blocks()

key()

Functions

build(entries)

Build an MST from path => CID entries.

depth(key)

Compute the MST layer (depth) of a key.

read(root, blocks)

Read an MST into a path => CID map, walking from root through blocks.

root_cid(entries)

Build an MST and return only the root CID.

valid_key?(key)

Validate an MST key (a repository record path <collection>/<rkey>).

Types

blocks()

@type blocks() :: %{required(Exosphere.ATProto.CID.t()) => binary()}

key()

@type key() :: String.t()

Functions

build(entries)

@spec build(Enumerable.t()) ::
  {:ok, Exosphere.ATProto.CID.t(), blocks()} | {:error, term()}

Build an MST from path => CID entries.

Accepts a map or an enumerable of {key, %CID{}} pairs. Returns {:ok, root_cid, blocks} where blocks maps each node CID to its encoded DAG-CBOR bytes.

Returns {:error, {:invalid_key, key}} or {:error, {:invalid_value, key}} for malformed input, {:error, {:duplicate_key, key}} if the same path appears with different CIDs, and {:error, {:invalid_entry, term}} for non-pair elements.

depth(key)

@spec depth(key()) :: non_neg_integer()

Compute the MST layer (depth) of a key.

The key is hashed with SHA-256 and the number of leading zero bits is counted in 2-bit chunks (fanout 4): every two leading zero bits increments the layer. Implemented to match the reference leadingZerosOnHash.

Examples

iex> Exosphere.ATProto.MST.depth("com.example.record/3jqfcqzm3fx2j")
2

read(root, blocks)

@spec read(Exosphere.ATProto.CID.t(), %{
  required(Exosphere.ATProto.CID.t()) => binary() | map()
}) ::
  {:ok, %{required(key()) => Exosphere.ATProto.CID.t()}} | {:error, term()}

Read an MST into a path => CID map, walking from root through blocks.

blocks may map CIDs to encoded DAG-CBOR bytes (e.g. a raw block store) or to already-decoded node maps (e.g. the output of Exosphere.ATProto.CAR.decode/1).

This walks the tree but does not validate its structure (entry ordering or key layering): use build/1 on the resulting entries and compare root CIDs (as Exosphere.ATProto.Repo.Commit.verify_data/2 does) to fully authenticate a tree.

Returns {:error, {:missing_block, cid}} if a referenced node is absent, {:error, {:invalid_node, cid}} if a node cannot be decoded, and {:error, {:cycle, cid}} if a node links to itself or an ancestor (possible with hostile block data).

root_cid(entries)

@spec root_cid(Enumerable.t()) :: {:ok, Exosphere.ATProto.CID.t()} | {:error, term()}

Build an MST and return only the root CID.

valid_key?(key)

@spec valid_key?(term()) :: boolean()

Validate an MST key (a repository record path <collection>/<rkey>).

The collection must be a valid NSID and the rkey a valid record key, so keys built here are accepted by reference implementations.