MST.Height (mst v0.1.0)

Key-depth computation for the AT Protocol Merkle Search Tree.

Each key's depth (also called "layer" or "height") is derived by SHA-256 hashing the key and counting the number of leading zero bits, divided by two (rounding down). This gives a theoretical fanout of 4: each additional level of depth is four times rarer than the previous.

Spec: https://atproto.com/specs/repository#mst-structure

Summary

Functions

for_key(key)

Computes the MST depth for a given key.

Functions

for_key(key)

@spec for_key(binary()) :: non_neg_integer()

Computes the MST depth for a given key.

SHA-256 hashes key and counts the number of leading zero bits in the binary output, then divides by 2 (floor). Returns a non-negative integer; depth 0 is the most common (probability ~75% per key), each higher depth is four times rarer.

Examples

iex> MST.Height.for_key("2653ae71")
0

iex> MST.Height.for_key("blue")
1

iex> MST.Height.for_key("app.bsky.feed.post/454397e440ec")
4

iex> MST.Height.for_key("app.bsky.feed.post/9adeb165882c")
8