comet.sh
An Elixir implementation of AT Protocol-flavoured Merkle Search Trees (MST)
ovyerus.com
1defmodule MST.Height do
2 @moduledoc """
3 Key-depth computation for the AT Protocol Merkle Search Tree.
4
5 Each key's depth (also called "layer" or "height") is derived by SHA-256
6 hashing the key and counting the number of leading zero bits, divided by two
7 (rounding down). This gives a theoretical fanout of 4: each additional level
8 of depth is four times rarer than the previous.
9
10 Spec: https://atproto.com/specs/repository#mst-structure
11 """
12
13 @doc """
14 Computes the MST depth for a given key.
15
16 SHA-256 hashes `key` and counts the number of leading zero bits in the
17 binary output, then divides by 2 (floor). Returns a non-negative integer;
18 depth 0 is the most common (probability ~75% per key), each higher depth
19 is four times rarer.
20
21 ## Examples
22
23 iex> MST.Height.for_key("2653ae71")
24 0
25
26 iex> MST.Height.for_key("blue")
27 1
28
29 iex> MST.Height.for_key("app.bsky.feed.post/454397e440ec")
30 4
31
32 iex> MST.Height.for_key("app.bsky.feed.post/9adeb165882c")
33 8
34
35 """
36 @spec for_key(binary()) :: non_neg_integer()
37 def for_key(key) when is_binary(key) do
38 :crypto.hash(:sha256, key)
39 |> leading_zero_bits()
40 |> div(2)
41 end
42
43 # ---------------------------------------------------------------------------
44 # Private helpers
45 # ---------------------------------------------------------------------------
46
47 @spec leading_zero_bits(binary()) :: non_neg_integer()
48 defp leading_zero_bits(<<>>), do: 0
49
50 defp leading_zero_bits(<<byte, rest::binary>>) do
51 lz = leading_zeros_in_byte(byte)
52
53 if lz == 8 do
54 8 + leading_zero_bits(rest)
55 else
56 lz
57 end
58 end
59
60 # Returns the count of leading zero bits in a single byte (0–8).
61 @spec leading_zeros_in_byte(byte()) :: 0..8
62 defp leading_zeros_in_byte(0), do: 8
63 defp leading_zeros_in_byte(b) when b >= 128, do: 0
64 defp leading_zeros_in_byte(b) when b >= 64, do: 1
65 defp leading_zeros_in_byte(b) when b >= 32, do: 2
66 defp leading_zeros_in_byte(b) when b >= 16, do: 3
67 defp leading_zeros_in_byte(b) when b >= 8, do: 4
68 defp leading_zeros_in_byte(b) when b >= 4, do: 5
69 defp leading_zeros_in_byte(b) when b >= 2, do: 6
70 defp leading_zeros_in_byte(_), do: 7
71end