Module radix 

RadixMap<V, KEY_BYTES> — a structurally-compressed sparse binary radix merkle key→value map (the “option b” content-addressed map).

Keys are fixed-width [u8; KEY_BYTES] bit strings (bit 0 = the MSB of byte 0, MSB-first / big-endian), values are any V: HashTreeRoot. The root is a canonical, binding, shallow commitment to the key→value set: a pure function of the set (insertion-order independent), and a commitment that no two distinct sets can share under collision resistance of the digest D alone.

This is distinct from crate::SparseList (the “option a” map): a SparseList is a fixed-depth sparse Merkle tree whose root is byte-identical to a dense List<T, N> (leaves are bare value roots, plus mix_in_length). A RadixMap is not byte-compatible with any SSZ List/Vector — it is a deliberately different structure (see “Dense ≠ Vector” below).

Structure (EIP-7864-aligned hybrid)

The recursion node(S, depth) over a set S of (key, value) entries:

• empty (|S| = 0) → EMPTY = [0u8; 32] (zero hash ops).
• leaf (|S| = 1) → leaf_hash of that entry’s (key, value_root). A lone key collapses to a single leaf wherever its subtree narrows to one element — so a lone key is shallow, independent of depth.
• branch (|S| ≥ 2) → branch_hash of the two children obtained by splitting S on bit(key, depth).

Only empty and singleton subtrees collapse; a multi-key shared prefix is materialized as a chain of branch nodes each with one EMPTY sibling (exactly like EIP-7864’s outer “minimal InternalNodes” tree, and like SparseList’s zero-padding). This is what keeps non-membership proofs complete: an absent key always lands on a materialized EMPTY sibling (or a diverging leaf) at a well-defined depth — there is no skipped unary run for it to fall into. (A fully unary-skip-compressed Patricia trie is shallower for adversarially-close keys but needs an explicit skip-prefix commitment in every node for non-membership completeness; we deliberately avoid that complexity.)

Depth is bounded by KEY_BITS = 8 * KEY_BYTES. It is shallow in practice: for well-spread keys (e.g. address-derived) the singleton collapse fires at depth ≈ log2(|S|); for the DataCap (group-index keys) KEY_BYTES is chosen small enough to bound the depth directly.

Domain separation (binding under collision resistance alone)

Leaf and branch nodes are tagged with distinct one-byte domain prefixes:

EMPTY  = [0u8; 32]
leaf   = D( LEAF_TAG(0x00)   || key || value_root )
branch = D( BRANCH_TAG(0x01) || left || right )

Tagging both node kinds (not just the leaf) is load-bearing. For KEY_BYTES ≤ 32, an SSZ merkleize(pack_bytes(key), 1) returns the raw key chunk un-hashed, so a bare hash_pair(key, value_root) leaf would be byte-identical to a branch hash_pair(left, right) — yielding a trivial, collision-free forgery: the one-entry map {(H_L, Missing(H_R))} would share a root with the two-entry branch branch(H_L, H_R). The distinct tag bytes make the leaf and branch preimages differ in a fixed position regardless of content, so a collision between the two domains is a collision of D itself. This binds the map under collision resistance alone (no second-preimage / preimage assumption) and ports cleanly to a future SNARK-friendly sponge (the tag is a structural domain element, not an artifact of byte-hash length padding) — a stronger footing than EIP-7864’s asymmetric stem || 0x00 || … stem commitment.

The leaf commits the full key (not just the bits consumed to reach its collapsed depth). This pins each leaf to one logical key — required for canonicality (the shallow placement is uniquely determined by the set) and for sound non-membership proofs (a diverging-leaf exclusion reveals k' ≠ key). The value is taken via MissingOr so an un-materialized leaf (Missing(h)) contributes value_root = h with no mix_in_selector — substitution-transparent, exactly like SparseList.

Because both node kinds are tagged, a RadixMap root also cannot be confused with a List/SparseList root (bare hash_pair + no tag) even absent an enclosing union selector. Note EMPTY == [0u8;32] does alias the zero summaries zero_hash(0) / PageSlot::Empty / MissingOr::Missing([0;32]); a RadixMap root must therefore only ever sit under a domain-separating parent (e.g. the Cap SSZ-union selector), never in a position that also admits a raw zero summary.

Canonicality

node(S, depth) branches only on set membership and bit(key, depth), both intrinsic to the set; the base cases depend only on the (≤ 1) element present and commit the full key. So the root is a pure function of the key→value-root set, independent of insertion order or MissingOr materialization pattern. Storage is a strictly-ascending sorted Vec, so there is exactly one in-memory and one wire form per set; duplicate keys are rejected on decode and overwritten on insert.

Dense ≠ Vector

Even a fully-dense RadixMap root does not coincide with an SSZ List/Vector root: radix leaves are tagged + key-committed (D(0x00 || key || value_root), not the bare value_root a Vector leaf carries), branches are tagged, and there is no mix_in_length. Standard SSZ merkleization appears only inside the leaf value — e.g. the DataCap leaf value is a dense FixedVector<Page, 512> merkleized the ordinary SSZ way; that value_root is then fed into leaf_hash.

Wire format

Like crate::SparseList minus the len field (a map has no logical length, only a key set): a single variable field holding a sorted SSZ list of (key: ByteVector[KEY_BYTES], value: MissingOr<V>) containers. Decode is strict (loud on any non-canonical encoding): top-level offset must be 4, per-entry value-offset must be KEY_BYTES + 4, keys must be strictly ascending (rejecting duplicates and bad order), no trailing bytes.

Structs

ArchivedRadixMapRepr

An archived RadixMapRepr

RadixMap

A structurally-compressed sparse binary radix merkle map (option “b”).

RadixMapRepr

RadixMapReprResolver

The resolver for an archived RadixMapRepr

RadixProof

A compact proof of (non-)membership of a single key in a RadixMap.

Enums

RadixTerminal

The node q’s walk terminates on.

RadixVerdict

Outcome of a verified proof.

Constants

BRANCH_TAG

Domain tag prepended to a branch-node (internal-node) preimage.

EMPTY

The empty-subtree hash: the all-zero 32-byte chunk (= zero_hash(0)).

LEAF_TAG

Domain tag prepended to a leaf-node preimage.

Functions

bit

Extract bit i of key, MSB-first: bit 0 is the most-significant bit of key[0]. Caller must ensure i < 8 * key.len().

branch_hash

Branch-node hash: D(BRANCH_TAG || left || right).

leaf_hash

Leaf-node hash: D(LEAF_TAG || key || value_root). Commits the full key (canonicality + non-membership) and the value root (via MissingOr).

verify

Verify a RadixProof for key against root. Returns the verdict, or None if the proof is malformed or does not reconstruct root.