Module shape 

The two pure functions a Merkle search tree’s shape comes from.

These sit below Tree and are checked without one, which is the whole argument: a tree built on a wrong height function is not merely self-consistent, it is correct — every lookup succeeds and every proof it makes verifies against itself — and the only symptom is a root CID no other implementation reproduces.

• key_height decides which layer a key sits on. It is derived from the key’s own hash, so every implementation puts a key on the same layer without coordinating.
• common_prefix_len decides how much of a key a node has to store. A node’s entries are sorted, so each one is written as the number of bytes it shares with its predecessor plus the rest.

Constants

FANOUT_BITS 🔒

atproto’s Merkle search tree has a fanout of four, so two zero bits of the key’s hash buy one layer.

Functions

common_prefix_len

How many leading bytes two keys share.

key_height

Which layer of the tree a key belongs on.