openvet-tree

Content-addressed tree used by OpenVet to index audits by subject. The shape is an MST (Merkle Search Tree, Auvolat & Taïani 2019), which is the same as a dense skip-tree in the G-trees family.

Why this shape

The audit log binds audit-blob hashes to (registry, package, version, artifact-hash) keys. Given the same set of bindings, every consumer must compute the same root hash — otherwise mirrors disagree, commit signatures over commit.tree lose meaning, and the log stops being a trustable commitment to its state.

Two properties make this work:

• History independence. The encoded tree (and its root hash) depends only on the set of bindings, never on the order in which they were inserted, deleted, or re-inserted.
• Content addressing. Each node's identity is the SHA-256 of its serialised bytes; subtrees are referenced by hash. Equal content → equal hash → trivial deduplication across mirrors.

MST-shaped trees give both: every key's rank is a deterministic function of the key alone (here: count of leading 6-bit zero groups in blake2b-256(key)), so the tree's shape is determined by its contents alone.

API

See the crate-level rustdoc for the full surface. The operations are insert, delete, get, and diff, all async over a NodeStore trait. An in-memory store ships in-crate for tests and self-hosting.

See Also

• G-trees paper — defines the family that contains MSTs, dense skip-trees, zip-trees, and the k-ary variants.
• Reference G-tree implementation — Meyer's pseudocode-faithful Rust implementation; our insert and delete are adapted from its insert_explicit and delete_explicit.
• atproto repository spec — uses a structurally similar MST-shaped data structure for the same reasons.