burin.coverage

The equal-area coverage engine: an aperture-9 rHEALPix SpatialMerkleTree with a canonical Poseidon (BN254) commitment, plus membership / non-membership proofs, space-time and value-bearing variants, signed attestations with fraud proofs, and the polygon → fingerprint pipeline.

Everything below is the public surface (burin.coverage.__all__).

burin.coverage: the equal-area coverage engine.

An aperture-9 rHEALPix coverage tree with a canonical Poseidon (BN254) commitment. The same set of equal-area cells always produces the same 32-byte root, regardless of insertion order or roll-up (deterministic, MOC-invariant). Dual EMPTY/FULL default-hash ladders give the roll-up, and the tree carries membership, non-membership, and uniform-coverage proofs. A canonicalizing SUID encoding for rHEALPix cell sets turns a polygon into a compact fingerprint.

See docs/coverage/SYNTHESIS.md for architecture, theory, and proof semantics.

AllenProof dataclass

Authenticated: a temporal cell (order,index) proven covered in a temporal coverage root stands in Allen relation relation to the public query interval [query_lo, query_hi). Verifiable from proof + root alone.

Source code in burin/coverage/allen.py

@dataclass
class AllenProof:
    """Authenticated: a temporal cell ``(order,index)`` proven covered in a temporal
    coverage root stands in Allen relation ``relation`` to the public query interval
    ``[query_lo, query_hi)``. Verifiable from proof + root alone."""

    order: int
    index: int
    query_lo: int
    query_hi: int
    relation: AllenRelation
    membership: CoverageProof
    temporal_depth: int

    def verify(self, temporal_root: bytes, hasher: HashFn | str = POSEIDON) -> bool:
        if self.query_hi <= self.query_lo:
            return False
        if not self.membership.present:
            return False
        if not self.membership.verify(temporal_root, self.temporal_depth, hasher):
            return False
        # the membership proof must be for exactly this cell
        base, kids = cell_to_path(self.order, self.index)
        if self.membership.base_idx != base or tuple(self.membership.children) != tuple(kids):
            return False
        start, end = cell_interval(self.order, self.index, self.temporal_depth)
        return allen_classify(start, end, self.query_lo, self.query_hi) == self.relation

HierarchicalCoverageTree

Sparse aperture-N Merkle tree over a canonical hierarchical cell set.

Node := _FULL | dict[int, node] (a missing child => EMPTY subtree). Root is a pure function of the set (order-independent) and MOC-invariant.

Source code in burin/coverage/coverage_tree.py

class HierarchicalCoverageTree:
    """Sparse aperture-N Merkle tree over a canonical hierarchical cell set.

    Node := ``_FULL`` | ``dict[int, node]`` (a missing child => EMPTY subtree).
    Root is a pure function of the set (order-independent) and MOC-invariant.
    """

    def __init__(self, aperture: int, n_base: int, max_depth: int, hasher: HashFn | str = POSEIDON):
        self.aperture = aperture
        self.n_base = n_base
        self.H = _Hashing(aperture, n_base, max_depth, hasher)
        self._bases: dict[int, object] = {}

    # -- construction (generic) --
    def add(self, base_index: int, children: Sequence[int]) -> None:
        if not (0 <= base_index < self.n_base):
            raise ValueError(f"base_index {base_index} out of range [0,{self.n_base})")
        children = [int(c) for c in children]
        for c in children:
            if not (0 <= c < self.aperture):
                raise ValueError(f"child {c} out of range [0,{self.aperture})")
        if len(children) > self.H.R:
            raise ValueError(f"path length {len(children)} exceeds max_depth {self.H.R}")
        if not children:
            self._bases[base_index] = _FULL
            return
        node = self._bases.get(base_index)
        if node is _FULL:
            return  # already covered by a rolled-up ancestor
        if not isinstance(node, dict):
            node = {}
            self._bases[base_index] = node
        cur: dict = node
        for c in children[:-1]:
            nxt = cur.get(c)
            if nxt is _FULL:
                return
            if not isinstance(nxt, dict):
                nxt = {}
                cur[c] = nxt
            cur = nxt
        cur[children[-1]] = _FULL

    @classmethod
    def from_paths(cls, aperture: int, n_base: int, paths, max_depth: int,
                   hasher: HashFn | str = POSEIDON) -> HierarchicalCoverageTree:
        t = cls(aperture, n_base, max_depth, hasher)
        for base, children in paths:
            t.add(base, children)
        return t

    # -- spatial adapter (aperture 9, n_base 6) --
    def add_suid(self, suid) -> None:
        base, children = suid_to_path(suid)
        self.add(base, children)

    @classmethod
    def from_suids(cls, suids, max_depth: int, hasher: HashFn | str = POSEIDON) -> HierarchicalCoverageTree:
        t = cls(9, 6, max_depth, hasher)
        for s in suids:
            t.add_suid(s)
        return t

    # -- temporal adapter (aperture 2, n_base 1) --
    def add_cell(self, order: int, index: int) -> None:
        base, children = cell_to_path(order, index)
        self.add(base, children)

    @classmethod
    def from_cells(cls, cells, max_depth: int, hasher: HashFn | str = POSEIDON) -> HierarchicalCoverageTree:
        t = cls(2, 1, max_depth, hasher)
        for order, index in cells:
            t.add_cell(order, index)
        return t

    def add_interval(self, lo: int, hi: int) -> list[tuple[int, int]]:
        """Cover a half-open time interval [lo, hi) (dyadic tree only). Returns the
        canonical cell set added. Domain is [0, 2**max_depth)."""
        if not (self.aperture == 2 and self.n_base == 1):
            raise ValueError("add_interval requires the dyadic temporal tree (aperture=2, n_base=1)")
        cells = interval_to_cells(lo, hi, self.H.R)
        for order, index in cells:
            self.add_cell(order, index)
        return cells

    @classmethod
    def from_intervals(cls, intervals, max_depth: int, hasher: HashFn | str = POSEIDON) -> HierarchicalCoverageTree:
        t = cls(2, 1, max_depth, hasher)
        for lo, hi in intervals:
            t.add_interval(lo, hi)
        return t

    # -- hashing --
    def _node_hash(self, node, d: int) -> bytes:
        if node is None:
            return self.H.EMPTY[d]
        if node is _FULL:
            return self.H.FULL[d]
        assert isinstance(node, dict)
        return self.H.internal([self._node_hash(node.get(i), d - 1) for i in range(self.aperture)])

    @property
    def root_hash(self) -> bytes:
        return self.H.root([self._node_hash(self._bases.get(b), self.H.R) for b in range(self.n_base)])

    @property
    def root_hash_hex(self) -> str:
        return self.root_hash.hex()

    # -- proofs --
    def _collect(self, base_index: int, children: list[int]):
        """Descend ``(base_index, children)``; return (root_sibs, internal_sibs,
        terminal_node) where terminal_node in {_FULL, None, dict}."""
        R, A = self.H.R, self.aperture
        base_h = [self._node_hash(self._bases.get(b), R) for b in range(self.n_base)]
        root_sibs = [base_h[b] for b in range(self.n_base) if b != base_index]
        internal_sibs: list[tuple[int, list[bytes]]] = []
        cur = self._bases.get(base_index)
        d = R
        for c in children:
            if isinstance(cur, dict):
                sibs = [self._node_hash(cur.get(i), d - 1) for i in range(A) if i != c]
                nxt = cur.get(c)
            elif cur is _FULL:
                sibs = [self.H.FULL[d - 1]] * (A - 1)
                nxt = _FULL
            else:  # None / empty
                sibs = [self.H.EMPTY[d - 1]] * (A - 1)
                nxt = None
            internal_sibs.append((c, sibs))
            cur = nxt
            d -= 1
        return root_sibs, internal_sibs, cur

    def membership_proof(self, base_index: int, children: Sequence[int]) -> CoverageProof | None:
        children = [int(c) for c in children]
        if len(children) > self.H.R:
            return None
        root_sibs, internal_sibs, term = self._collect(base_index, children)
        if term is not _FULL:  # not covered at this granularity
            return None
        return CoverageProof(base_index, tuple(children), True, root_sibs, internal_sibs,
                             self.aperture, self.n_base)

    def non_membership_proof(self, base_index: int, children: Sequence[int]) -> CoverageProof | None:
        children = [int(c) for c in children]
        if len(children) > self.H.R:
            return None
        root_sibs, internal_sibs, term = self._collect(base_index, children)
        if term is not None:  # covered (FULL) or partially covered (dict) -> can't prove absence
            return None
        return CoverageProof(base_index, tuple(children), False, root_sibs, internal_sibs,
                             self.aperture, self.n_base)

    # -- proof adapters --
    def membership_proof_suid(self, suid) -> CoverageProof | None:
        base, children = suid_to_path(suid)
        return self.membership_proof(base, children)

    def non_membership_proof_suid(self, suid) -> CoverageProof | None:
        base, children = suid_to_path(suid)
        return self.non_membership_proof(base, children)

    def membership_proof_cell(self, order: int, index: int) -> CoverageProof | None:
        base, children = cell_to_path(order, index)
        return self.membership_proof(base, children)

    def non_membership_proof_cell(self, order: int, index: int) -> CoverageProof | None:
        base, children = cell_to_path(order, index)
        return self.non_membership_proof(base, children)

add_interval

add_interval(lo: int, hi: int) -> list[tuple[int, int]]

Cover a half-open time interval [lo, hi) (dyadic tree only). Returns the canonical cell set added. Domain is [0, 2**max_depth).

Source code in burin/coverage/coverage_tree.py

def add_interval(self, lo: int, hi: int) -> list[tuple[int, int]]:
    """Cover a half-open time interval [lo, hi) (dyadic tree only). Returns the
    canonical cell set added. Domain is [0, 2**max_depth)."""
    if not (self.aperture == 2 and self.n_base == 1):
        raise ValueError("add_interval requires the dyadic temporal tree (aperture=2, n_base=1)")
    cells = interval_to_cells(lo, hi, self.H.R)
    for order, index in cells:
        self.add_cell(order, index)
    return cells

Attestation dataclass

One entry in a witness's append-only attestation log (ATTESTATION_MODEL §2).

Source code in burin/coverage/fraud.py

@dataclass
class Attestation:
    """One entry in a witness's append-only attestation log (ATTESTATION_MODEL §2)."""

    witness_pk: bytes
    epoch: int
    prev_hash: bytes
    root: bytes
    issued_at: int | None              # 'when' — optional; None = a time-agnostic attestation
    subject: tuple[int, int] | None
    policy: int
    sig: bytes

    def message(self) -> bytes:
        return attestation_message(self.witness_pk, self.epoch, self.prev_hash, self.root,
                                   self.issued_at, self.subject, self.policy)

    def valid(self, verify_sig: VerifySig) -> bool:
        return verify_sig(self.witness_pk, self.message(), self.sig)

BackdatingFraud dataclass

A later epoch carries an earlier issuance time. The witness's own epoch order says later came after earlier; its own clock says before — self-contradiction, no trusted clock needed. (Absorbs Roughtime: the epoch sequence is the ordering proof.) Requires both attestations to carry a time: a time-agnostic witness (issued_at is None) binds no when, so Rule 3 does not apply and no backdating proof can exist.

Source code in burin/coverage/fraud.py

@dataclass
class BackdatingFraud:
    """A later epoch carries an earlier issuance time. The witness's own epoch order
    says ``later`` came after ``earlier``; its own clock says before — self-contradiction,
    no trusted clock needed. (Absorbs Roughtime: the epoch sequence is the ordering proof.)
    Requires **both** attestations to carry a time: a time-agnostic witness (``issued_at is
    None``) binds no ``when``, so Rule 3 does not apply and no backdating proof can exist."""

    earlier: Attestation   # lower epoch, LATER issued_at
    later: Attestation     # higher epoch, EARLIER issued_at

    def verify(self, verify_sig: VerifySig) -> bool:
        return (self.earlier.witness_pk == self.later.witness_pk
                and self.earlier.issued_at is not None and self.later.issued_at is not None
                and self.later.epoch > self.earlier.epoch
                and self.later.issued_at < self.earlier.issued_at
                and self.earlier.valid(verify_sig)
                and self.later.valid(verify_sig))

CoverageMonotonicityFraud dataclass

Under a declared APPEND_ONLY_COVERAGE policy, a later epoch un-covers a (region, time) an earlier epoch covered. covered proves region R covered at temporal cell T; uncovered (a later epoch) proves R′ ⊆ R absent at the SAME T. Since R covered at T implies every descendant covered at T (ST inheritance), R′ absent later means coverage shrank — the bird demo's 'claimed the whole valley, denied this nest.'

Source code in burin/coverage/fraud.py

@dataclass
class CoverageMonotonicityFraud:
    """Under a declared APPEND_ONLY_COVERAGE policy, a later epoch un-covers a
    (region, time) an earlier epoch covered. ``covered`` proves region R covered at
    temporal cell T; ``uncovered`` (a later epoch) proves R′ ⊆ R absent at the SAME T.
    Since R covered at T implies every descendant covered at T (ST inheritance), R′
    absent later means coverage shrank — the bird demo's 'claimed the whole valley,
    denied this nest.'"""

    covered: Attestation
    uncovered: Attestation
    membership: STUniformProof             # ALL of R @ T  vs covered.root (coarse claim, any granularity)
    non_membership: STNonMembershipProof   # R′ ⊆ R @ T    vs uncovered.root

    def verify(self, verify_sig: VerifySig, hasher: HashFn | str = POSEIDON) -> bool:
        c, u = self.covered, self.uncovered
        if c.witness_pk != u.witness_pk:
            return False
        if not (c.policy & APPEND_ONLY_COVERAGE and u.policy & APPEND_ONLY_COVERAGE):
            return False
        if u.epoch <= c.epoch:                                   # must un-cover in a LATER epoch
            return False
        if not (c.valid(verify_sig) and u.valid(verify_sig)):
            return False
        m, n = self.membership, self.non_membership
        if n.kind != "temporal_absent" or n.temporal_proof is None:
            return False
        if m.base_idx != n.base_idx:                             # same spatial base
            return False
        ml = len(m.children)                                     # R′ = R or a descendant of R
        if len(n.children) < ml or tuple(n.children[:ml]) != tuple(m.children):
            return False
        _, mt_kids = cell_to_path(m.order, m.index)              # same temporal cell T on both sides
        if tuple(n.temporal_proof.children) != tuple(mt_kids):
            return False
        return m.verify(c.root, hasher) and n.verify(u.root, hasher)

EquivocationFraud dataclass

Same witness, same epoch, two DISTINCT signed attestations — a provable fork. Rule 1 is one attestation per epoch, so any divergence in the signed message (root, issued_at, subject, policy, prev_hash) at a shared (witness_pk, epoch) is a fork — not only a divergent root.

The comparison is on the signed message, never the signature, so a re-broadcast of the identical attestation is NOT a fork even under a randomized scheme (SM2/ECDSA give two distinct signatures for one message). Sound because the epoch is the context: different epochs are legitimate evolution, never flagged; one attestation per epoch ⇒ no false positive on any honest witness. Catching the whole message (not just the root) closes two cross-rule evasions — an issued_at fork that would otherwise let a witness escape backdating detection (Rule 3), and a policy fork that would let it selectively disclaim the APPEND_ONLY_COVERAGE behind Rule 4.

Source code in burin/coverage/fraud.py

@dataclass
class EquivocationFraud:
    """Same witness, same epoch, two DISTINCT signed attestations — a provable fork. Rule 1 is
    *one attestation per epoch*, so any divergence in the signed message (root, issued_at, subject,
    policy, prev_hash) at a shared ``(witness_pk, epoch)`` is a fork — not only a divergent root.

    The comparison is on the signed *message*, never the signature, so a re-broadcast of the
    identical attestation is NOT a fork even under a randomized scheme (SM2/ECDSA give two distinct
    signatures for one message). Sound because the epoch is the context: different epochs are
    legitimate evolution, never flagged; one attestation per epoch ⇒ no false positive on any honest
    witness. Catching the whole message (not just the root) closes two cross-rule evasions — an
    ``issued_at`` fork that would otherwise let a witness escape backdating detection (Rule 3), and a
    ``policy`` fork that would let it selectively disclaim the APPEND_ONLY_COVERAGE behind Rule 4."""

    a: Attestation
    b: Attestation

    def verify(self, verify_sig: VerifySig) -> bool:
        return (self.a.witness_pk == self.b.witness_pk
                and self.a.epoch == self.b.epoch
                and self.a.message() != self.b.message()
                and self.a.valid(verify_sig)
                and self.b.valid(verify_sig))

CoverageProof dataclass

Membership (present=True) or non-membership (present=False) proof for a cell at (base_idx, children). Self-verifying against a root.

Source code in burin/coverage/spatial_merkle.py

@dataclass
class CoverageProof:
    """Membership (`present=True`) or non-membership (`present=False`) proof
    for a cell at `(base_idx, children)`. Self-verifying against a root."""

    base_idx: int
    children: tuple[int, ...]
    present: bool
    root_sibs: list[bytes]                    # the 5 sibling base hashes
    internal_sibs: list[tuple[int, list[bytes]]]  # root->leaf: (child_pos, 8 sib hashes)

    def verify(self, root_hash: bytes, max_depth: int, hasher: HashFn | str = POSEIDON) -> bool:
        H = _Hashing(max_depth, hasher)
        level = len(self.children)
        if not (0 <= level <= max_depth) or not (0 <= self.base_idx < N_BASE):
            return False
        if len(self.internal_sibs) != level or len(self.root_sibs) != N_BASE - 1:
            return False
        # leaf value: FULL (covered) or EMPTY (absent) subtree of remaining depth
        h = (H.FULL if self.present else H.EMPTY)[max_depth - level]
        for pos, sibs in reversed(self.internal_sibs):
            if not (0 <= pos < N_CHILD) or len(sibs) != N_CHILD - 1:
                return False
            it = iter(sibs)
            h = H.internal9([h if i == pos else next(it) for i in range(N_CHILD)])
        it = iter(self.root_sibs)
        six = [h if b == self.base_idx else next(it) for b in range(N_BASE)]
        return H.root(six) == root_hash

SpatialMerkleTree

Sparse aperture-9 Merkle tree over a canonical rHEALPix cell set.

Build from canonical SUIDs (mixed levels, MOC-rolled). Root is a pure function of the set (order-independent) and MOC-invariant. Cells deeper than max_depth are rejected.

Source code in burin/coverage/spatial_merkle.py

class SpatialMerkleTree:
    """Sparse aperture-9 Merkle tree over a canonical rHEALPix cell set.

    Build from canonical SUIDs (mixed levels, MOC-rolled). Root is a pure
    function of the set (order-independent) and MOC-invariant. Cells deeper
    than `max_depth` are rejected.
    """

    def __init__(self, max_depth: int, hasher: HashFn | str = POSEIDON):
        self.H = _Hashing(max_depth, hasher)
        # node := _FULL | dict[int, node]   (missing child => EMPTY subtree)
        self._bases: dict[int, object] = {}

    # -- construction --
    def add(self, suid) -> None:
        suid = tuple(suid)
        base = _base_index(suid)
        children = [int(c) for c in suid[1:]]
        if len(children) > self.H.R:
            raise ValueError(f"cell level {len(children)} exceeds max_depth {self.H.R}")
        if not children:
            self._bases[base] = _FULL
            return
        node = self._bases.get(base)
        if node is _FULL:
            return  # already covered by a rolled-up ancestor
        if not isinstance(node, dict):
            node = {}
            self._bases[base] = node
        cur: dict = node
        for c in children[:-1]:
            nxt = cur.get(c)
            if nxt is _FULL:
                return
            if not isinstance(nxt, dict):
                nxt = {}
                cur[c] = nxt
            cur = nxt
        cur[children[-1]] = _FULL

    @classmethod
    def from_suids(cls, suids, max_depth: int, hasher: HashFn | str = POSEIDON) -> SpatialMerkleTree:
        t = cls(max_depth, hasher)
        for s in suids:
            t.add(s)
        return t

    # -- hashing --
    def _node_hash(self, node, d: int) -> bytes:
        if node is None:
            return self.H.EMPTY[d]
        if node is _FULL:
            return self.H.FULL[d]
        assert isinstance(node, dict)
        return self.H.internal9([self._node_hash(node.get(i), d - 1) for i in range(N_CHILD)])

    @property
    def root_hash(self) -> bytes:
        return self.H.root([self._node_hash(self._bases.get(b), self.H.R) for b in range(N_BASE)])

    @property
    def root_hash_hex(self) -> str:
        return self.root_hash.hex()

    # -- proofs --
    def _collect(self, base_idx: int, children: list[int]):
        """Descend `(base_idx, children)`; return (root_sibs, internal_sibs,
        terminal_node) where terminal_node in {_FULL, None, dict}."""
        R = self.H.R
        base_h = [self._node_hash(self._bases.get(b), R) for b in range(N_BASE)]
        root_sibs = [base_h[b] for b in range(N_BASE) if b != base_idx]
        internal_sibs: list[tuple[int, list[bytes]]] = []
        cur = self._bases.get(base_idx)
        d = R
        for c in children:
            if isinstance(cur, dict):
                sibs = [self._node_hash(cur.get(i), d - 1) for i in range(N_CHILD) if i != c]
                nxt = cur.get(c)
            elif cur is _FULL:
                sibs = [self.H.FULL[d - 1]] * (N_CHILD - 1)
                nxt = _FULL
            else:  # None / empty
                sibs = [self.H.EMPTY[d - 1]] * (N_CHILD - 1)
                nxt = None
            internal_sibs.append((c, sibs))
            cur = nxt
            d -= 1
        return root_sibs, internal_sibs, cur

    def membership_proof(self, suid) -> CoverageProof | None:
        suid = tuple(suid)
        base, children = _base_index(suid), [int(c) for c in suid[1:]]
        if len(children) > self.H.R:
            return None
        root_sibs, internal_sibs, term = self._collect(base, children)
        if term is not _FULL:  # not covered at this granularity
            return None
        return CoverageProof(base, tuple(children), True, root_sibs, internal_sibs)

    def non_membership_proof(self, suid) -> CoverageProof | None:
        suid = tuple(suid)
        base, children = _base_index(suid), [int(c) for c in suid[1:]]
        if len(children) > self.H.R:
            return None
        root_sibs, internal_sibs, term = self._collect(base, children)
        if term is not None:  # covered (FULL) or partially covered (dict) -> can't prove absence
            return None
        return CoverageProof(base, tuple(children), False, root_sibs, internal_sibs)

SpatioTemporalCoverageTree

Nested STMOC commitment. Space = aperture-9/n_base-6; each covered spatial leaf carries a dyadic (aperture-2) temporal coverage tree of depth temporal_depth.

Overlapping nested facts merge by push-down union (see module docstring).

Source code in burin/coverage/st_coverage.py

class SpatioTemporalCoverageTree:
    """Nested STMOC commitment. Space = aperture-9/n_base-6; each covered spatial
    leaf carries a dyadic (aperture-2) temporal coverage tree of depth ``temporal_depth``.

    Overlapping nested facts merge by push-down union (see module docstring)."""

    def __init__(self, spatial_depth: int, temporal_depth: int, hasher: HashFn | str = POSEIDON):
        self.sd = spatial_depth
        self.td = temporal_depth
        self.h = hasher
        self.SH = _Hashing(9, 6, spatial_depth, hasher)
        # node := None (EMPTY) | HierarchicalCoverageTree (covered leaf) | dict[int, node]
        self._bases: dict[int, object] = {}

    # -- temporal-leaf helpers --
    def _new_leaf(self, lo: int, hi: int) -> HierarchicalCoverageTree:
        leaf = HierarchicalCoverageTree(2, 1, self.td, self.h)
        leaf.add_interval(lo, hi)
        return leaf

    def _clone_temporal(self, leaf: HierarchicalCoverageTree) -> HierarchicalCoverageTree:
        c = copy.copy(leaf)                       # shares the read-only _Hashing
        c._bases = copy.deepcopy(leaf._bases)     # independent coverage
        return c

    def _expand_leaf(self, leaf: HierarchicalCoverageTree) -> dict:
        """A covered coarse leaf -> a dict of 9 children each carrying a clone of
        its temporal coverage (so a finer fact can specialize one child)."""
        return {i: self._clone_temporal(leaf) for i in range(9)}

    # -- construction (push-down union) --
    def add(self, suid, lo: int, hi: int) -> None:
        if hi <= lo:
            raise ValueError(f"interval must have positive duration: [{lo},{hi})")
        base, children = suid_to_path(suid)
        if not (0 <= base < 6):
            raise ValueError(f"base {base} out of range")
        if len(children) > self.sd:
            raise ValueError(f"spatial level {len(children)} exceeds spatial_depth {self.sd}")

        if not children:                          # fact covers the whole base cell
            self._bases[base] = self._apply(self._bases.get(base), lo, hi)
            return

        chain: list[tuple[dict, int]] = [(self._bases, base)]
        node = self._bases.get(base)
        if isinstance(node, HierarchicalCoverageTree):
            node = self._expand_leaf(node)
        elif not isinstance(node, dict):
            node = {}
        self._bases[base] = node
        cur: dict = node
        for c in children[:-1]:
            chain.append((cur, c))
            nxt = cur.get(c)
            if isinstance(nxt, HierarchicalCoverageTree):
                nxt = self._expand_leaf(nxt)
            elif not isinstance(nxt, dict):
                nxt = {}
            cur[c] = nxt
            cur = nxt
        key = children[-1]
        chain.append((cur, key))
        cur[key] = self._apply(cur.get(key), lo, hi)
        self._rollup_chain(chain)

    def _apply(self, node, lo: int, hi: int):
        """Apply interval (lo,hi) at a node: create / union / inherit. Returns node."""
        if node is None:
            return self._new_leaf(lo, hi)
        if isinstance(node, HierarchicalCoverageTree):
            node.add_interval(lo, hi)             # same cell, multiple intervals -> union
            return node
        return self._inherit(node, lo, hi)        # dict -> push down into the whole subtree

    def _inherit(self, node: dict, lo: int, hi: int):
        """A coarse fact over a partially-resolved subtree: every descendant leaf
        (present or implied) inherits (lo,hi). Re-rolls homogeneous subtrees."""
        for i in range(9):
            node[i] = self._apply(node.get(i), lo, hi)
        return self._maybe_rollup(node)

    def _maybe_rollup(self, node):
        """Collapse a dict of 9 leaves with identical temporal coverage to one leaf
        (canonical coarsest form). Otherwise return node unchanged."""
        if not isinstance(node, dict) or len(node) != 9:
            return node
        leaves: list[HierarchicalCoverageTree] = []
        for i in range(9):
            child = node.get(i)
            if not isinstance(child, HierarchicalCoverageTree):
                return node
            leaves.append(child)
        r0 = leaves[0].root_hash
        if all(leaf.root_hash == r0 for leaf in leaves[1:]):
            return leaves[0]
        return node

    def _rollup_chain(self, chain: list[tuple[dict, int]]) -> None:
        for container, key in reversed(chain):
            node = container.get(key)
            if not isinstance(node, dict):
                continue                          # the target leaf
            rolled = self._maybe_rollup(node)
            if rolled is node:
                break                             # didn't collapse -> ancestors won't either
            container[key] = rolled

    # -- hashing --
    def _node_hash(self, node, d: int) -> bytes:
        if node is None:
            return self.SH.EMPTY[d]
        if isinstance(node, HierarchicalCoverageTree):
            return _st_full(node.root_hash, d, self.SH, self.h)
        assert isinstance(node, dict)
        return self.SH.internal([self._node_hash(node.get(i), d - 1) for i in range(9)])

    @property
    def root_hash(self) -> bytes:
        return self.SH.root([self._node_hash(self._bases.get(b), self.sd) for b in range(6)])

    @property
    def root_hash_hex(self) -> str:
        return self.root_hash.hex()

    # -- query + proof --
    def _collect(self, base: int, children: list[int]):
        sd = self.sd
        base_h = [self._node_hash(self._bases.get(b), sd) for b in range(6)]
        root_sibs = [base_h[b] for b in range(6) if b != base]
        internal_sibs: list[tuple[int, list[bytes]]] = []
        cur = self._bases.get(base)
        d = sd
        for c in children:
            if not isinstance(cur, dict):
                return None  # path hits absent (None) or a covered ancestor leaf
            sibs = [self._node_hash(cur.get(i), d - 1) for i in range(9) if i != c]
            internal_sibs.append((c, sibs))
            cur = cur.get(c)
            d -= 1
        return root_sibs, internal_sibs, cur

    def _collect_nm(self, base: int, children: list[int]):
        """Descend for non-membership: pass THROUGH absent (None) nodes building
        EMPTY sibs. Returns (root_sibs, internal_sibs, terminal, blocked); blocked
        is True if the path hit a covered ANCESTOR leaf (cell covered by a coarser one)."""
        sd = self.sd
        base_h = [self._node_hash(self._bases.get(b), sd) for b in range(6)]
        root_sibs = [base_h[b] for b in range(6) if b != base]
        internal_sibs: list[tuple[int, list[bytes]]] = []
        cur = self._bases.get(base)
        d = sd
        for c in children:
            if isinstance(cur, dict):
                sibs = [self._node_hash(cur.get(i), d - 1) for i in range(9) if i != c]
                nxt = cur.get(c)
            elif cur is None:
                sibs = [self.SH.EMPTY[d - 1]] * 8
                nxt = None
            else:  # covered ancestor leaf
                return root_sibs, internal_sibs, cur, True
            internal_sibs.append((c, sibs))
            cur = nxt
            d -= 1
        return root_sibs, internal_sibs, cur, False

    def temporal_tree(self, suid) -> HierarchicalCoverageTree | None:
        """The temporal coverage tree at an exactly-covered spatial cell, else None."""
        base, children = suid_to_path(suid)
        collected = self._collect(base, children)
        if collected is None:
            return None
        _, _, term = collected
        return term if isinstance(term, HierarchicalCoverageTree) else None

    def st_membership_proof(self, suid, order: int, index: int) -> STMembershipProof | None:
        base, children = suid_to_path(suid)
        collected = self._collect(base, children)
        if collected is None:
            return None
        root_sibs, internal_sibs, term = collected
        if not isinstance(term, HierarchicalCoverageTree):
            return None
        tp = term.membership_proof_cell(order, index)
        if tp is None:
            return None
        return STMembershipProof(base, tuple(children), term.root_hash, root_sibs,
                                 internal_sibs, tp, self.sd, self.td)

    def st_non_membership_proof(self, suid, order: int, index: int) -> STNonMembershipProof | None:
        base, children = suid_to_path(suid)
        if len(children) > self.sd:
            return None
        root_sibs, internal_sibs, term, blocked = self._collect_nm(base, children)
        if blocked:
            return None  # covered by a coarser ancestor -> query at that granularity
        if term is None:
            return STNonMembershipProof("spatial_absent", base, tuple(children), root_sibs,
                                        internal_sibs, self.sd)
        if isinstance(term, HierarchicalCoverageTree):
            tp = term.non_membership_proof_cell(order, index)
            if tp is None:
                return None  # temporal cell IS covered -> it's a member
            return STNonMembershipProof("temporal_absent", base, tuple(children), root_sibs,
                                        internal_sibs, self.sd, term.root_hash, tp, self.td)
        return None  # dict -> partially covered; not provable at this granularity

    def _build_uniform(self, node, d: int, order: int, index: int) -> _UniformNode | None:
        if node is None:
            return None                                   # absent -> R not fully covered
        if isinstance(node, HierarchicalCoverageTree):
            tp = node.membership_proof_cell(order, index)
            if tp is None:
                return None                               # this leaf not covered at T
            return _UniformNode(node.root_hash, tp, None)
        kids: list[_UniformNode] = []                     # dict -> all 9 must be covered at T
        for i in range(9):
            child = self._build_uniform(node.get(i), d - 1, order, index)
            if child is None:
                return None
            kids.append(child)
        return _UniformNode(None, None, kids)

    def st_uniform_membership_proof(self, suid, order: int, index: int) -> STUniformProof | None:
        """Prove ALL of spatial cell ``suid`` is covered at temporal cell (order, index)."""
        base, children = suid_to_path(suid)
        collected = self._collect(base, children)
        if collected is None:
            return None
        root_sibs, internal_sibs, term = collected
        sub = self._build_uniform(term, self.sd - len(children), order, index)
        if sub is None:
            return None
        return STUniformProof(base, tuple(children), order, index, root_sibs,
                              internal_sibs, sub, self.sd, self.td)

temporal_tree

temporal_tree(suid) -> HierarchicalCoverageTree | None

The temporal coverage tree at an exactly-covered spatial cell, else None.

Source code in burin/coverage/st_coverage.py

def temporal_tree(self, suid) -> HierarchicalCoverageTree | None:
    """The temporal coverage tree at an exactly-covered spatial cell, else None."""
    base, children = suid_to_path(suid)
    collected = self._collect(base, children)
    if collected is None:
        return None
    _, _, term = collected
    return term if isinstance(term, HierarchicalCoverageTree) else None

st_uniform_membership_proof

st_uniform_membership_proof(
    suid, order: int, index: int
) -> STUniformProof | None

Prove ALL of spatial cell suid is covered at temporal cell (order, index).

Source code in burin/coverage/st_coverage.py

def st_uniform_membership_proof(self, suid, order: int, index: int) -> STUniformProof | None:
    """Prove ALL of spatial cell ``suid`` is covered at temporal cell (order, index)."""
    base, children = suid_to_path(suid)
    collected = self._collect(base, children)
    if collected is None:
        return None
    root_sibs, internal_sibs, term = collected
    sub = self._build_uniform(term, self.sd - len(children), order, index)
    if sub is None:
        return None
    return STUniformProof(base, tuple(children), order, index, root_sibs,
                          internal_sibs, sub, self.sd, self.td)

STMembershipProof dataclass

A chain of proofs: (spatial path to a covered cell) ∘ (temporal proof that the queried temporal cell is covered in that cell's sub-tree).

Source code in burin/coverage/st_coverage.py

@dataclass
class STMembershipProof:
    """A *chain of proofs*: (spatial path to a covered cell) ∘ (temporal proof
    that the queried temporal cell is covered in that cell's sub-tree)."""

    base_idx: int
    children: tuple[int, ...]
    temporal_root: bytes
    root_sibs: list[bytes]
    internal_sibs: list[tuple[int, list[bytes]]]
    temporal_proof: CoverageProof
    spatial_depth: int
    temporal_depth: int

    def verify(self, root_hash: bytes, hasher: HashFn | str = POSEIDON) -> bool:
        # link 1 — the temporal cell really is covered in this cell's tree
        if not self.temporal_proof.present:
            return False
        if not self.temporal_proof.verify(self.temporal_root, self.temporal_depth, hasher):
            return False
        # link 2 — this cell, carrying that temporal root, is in the spatial root
        SH = _Hashing(9, 6, self.spatial_depth, hasher)
        level = len(self.children)
        if not (0 <= level <= self.spatial_depth) or len(self.root_sibs) != 5:
            return False
        # bind the claimed spatial cell to the authenticated path (see CoverageProof.verify)
        if tuple(pos for pos, _ in self.internal_sibs) != tuple(self.children):
            return False
        h = _st_full(self.temporal_root, self.spatial_depth - level, SH, hasher)
        for pos, sibs in reversed(self.internal_sibs):
            if not (0 <= pos < 9) or len(sibs) != 8:
                return False
            it = iter(sibs)
            h = SH.internal([h if i == pos else next(it) for i in range(9)])
        it = iter(self.root_sibs)
        bvec = [h if b == self.base_idx else next(it) for b in range(6)]
        return SH.root(bvec) == root_hash

STNonMembershipProof dataclass

Proof that (suid, temporal cell) is NOT covered. Two kinds: spatial_absent — the spatial cell's subtree is EMPTY (no coverage at any time); temporal_absent — the cell is covered (carries temporal_root) but the queried temporal cell is absent in that sub-tree.

Source code in burin/coverage/st_coverage.py

@dataclass
class STNonMembershipProof:
    """Proof that ``(suid, temporal cell)`` is NOT covered. Two kinds:
    ``spatial_absent`` — the spatial cell's subtree is EMPTY (no coverage at any
    time); ``temporal_absent`` — the cell is covered (carries ``temporal_root``)
    but the queried temporal cell is absent in that sub-tree."""

    kind: str  # "spatial_absent" | "temporal_absent"
    base_idx: int
    children: tuple[int, ...]
    root_sibs: list[bytes]
    internal_sibs: list[tuple[int, list[bytes]]]
    spatial_depth: int
    temporal_root: bytes | None = None
    temporal_proof: CoverageProof | None = None
    temporal_depth: int | None = None

    def verify(self, root_hash: bytes, hasher: HashFn | str = POSEIDON) -> bool:
        SH = _Hashing(9, 6, self.spatial_depth, hasher)
        level = len(self.children)
        if not (0 <= level <= self.spatial_depth) or len(self.root_sibs) != 5:
            return False
        # bind the claimed spatial cell to the authenticated path (see CoverageProof.verify)
        if tuple(pos for pos, _ in self.internal_sibs) != tuple(self.children):
            return False
        if self.kind == "spatial_absent":
            h = SH.EMPTY[self.spatial_depth - level]
        elif self.kind == "temporal_absent":
            if self.temporal_proof is None or self.temporal_root is None or self.temporal_depth is None:
                return False
            if self.temporal_proof.present:  # must be a NON-membership temporal proof
                return False
            if not self.temporal_proof.verify(self.temporal_root, self.temporal_depth, hasher):
                return False
            h = _st_full(self.temporal_root, self.spatial_depth - level, SH, hasher)
        else:
            return False
        for pos, sibs in reversed(self.internal_sibs):
            if not (0 <= pos < 9) or len(sibs) != 8:
                return False
            it = iter(sibs)
            h = SH.internal([h if i == pos else next(it) for i in range(9)])
        it = iter(self.root_sibs)
        bvec = [h if b == self.base_idx else next(it) for b in range(6)]
        return SH.root(bvec) == root_hash

STUniformProof dataclass

Proves EVERY leaf of spatial cell (base_idx, children) is covered at temporal cell (order, index) — i.e. 'all of region R covered at T'. Sound against the existing root (no commitment change); size = O(distinct leaves under R), reducing to a single temporal proof when R is a uniform leaf. (If R is covered only via a coarser ancestor leaf, prove that ancestor — the natural coarsest claim.)

Source code in burin/coverage/st_coverage.py

@dataclass
class STUniformProof:
    """Proves EVERY leaf of spatial cell ``(base_idx, children)`` is covered at temporal
    cell ``(order, index)`` — i.e. 'all of region R covered at T'. Sound against the
    existing root (no commitment change); size = O(distinct leaves under R), reducing to
    a single temporal proof when R is a uniform leaf. (If R is covered only via a
    *coarser* ancestor leaf, prove that ancestor — the natural coarsest claim.)"""

    base_idx: int
    children: tuple[int, ...]
    order: int
    index: int
    root_sibs: list[bytes]
    internal_sibs: list[tuple[int, list[bytes]]]
    subtree: _UniformNode
    spatial_depth: int
    temporal_depth: int

    def verify(self, root_hash: bytes, hasher: HashFn | str = POSEIDON) -> bool:
        SH = _Hashing(9, 6, self.spatial_depth, hasher)
        level = len(self.children)
        if not (0 <= level <= self.spatial_depth) or len(self.root_sibs) != 5:
            return False
        # bind the claimed spatial cell to the authenticated path (see CoverageProof.verify)
        if tuple(pos for pos, _ in self.internal_sibs) != tuple(self.children):
            return False
        h = _verify_uniform_node(self.subtree, self.spatial_depth - level,
                                 self.order, self.index, self.temporal_depth, SH, hasher)
        if h is None:
            return False
        for pos, sibs in reversed(self.internal_sibs):
            if not (0 <= pos < 9) or len(sibs) != 8:
                return False
            it = iter(sibs)
            h = SH.internal([h if i == pos else next(it) for i in range(9)])
        it = iter(self.root_sibs)
        bvec = [h if b == self.base_idx else next(it) for b in range(6)]
        return SH.root(bvec) == root_hash

ValuedCoverageTree

Aperture-9 / n_base-6 spatial commitment whose covered leaves carry an opaque VALUE (a field element) instead of a FULL bit. node := None (EMPTY) | int (value_fe) | dict[int, node].

Roll-up is gated on value-equality: nine children with the identical value collapse to one valued leaf (canonical coarsest form); mixed values do not. A finer value fact inside a coarser valued cell expands that cell (children inherit its value) then sets the finer child (last-write-wins on a single cell). For a slide the cells are at one resolution, so it is just place + uniform roll-up.

Source code in burin/coverage/value_coverage.py

class ValuedCoverageTree:
    """Aperture-9 / n_base-6 spatial commitment whose covered leaves carry an opaque VALUE (a field
    element) instead of a FULL bit. ``node := None (EMPTY) | int (value_fe) | dict[int, node]``.

    Roll-up is gated on value-equality: nine children with the identical value collapse to one valued
    leaf (canonical coarsest form); mixed values do not. A finer value fact inside a coarser valued
    cell expands that cell (children inherit its value) then sets the finer child (last-write-wins on
    a single cell). For a slide the cells are at one resolution, so it is just place + uniform roll-up."""

    def __init__(self, spatial_depth: int, hasher: HashFn | str = POSEIDON):
        self.sd = spatial_depth
        self.h = hasher
        self.SH = _Hashing(9, 6, spatial_depth, hasher)
        # node := None (EMPTY) | int (value_fe; a covered VALUE leaf) | dict[int, node]
        self._bases: dict[int, object] = {}

    @classmethod
    def from_cells(cls, cells_values, spatial_depth: int, hasher: HashFn | str = POSEIDON):
        """Build from an iterable of ``(suid, value)``. Later values overwrite earlier at the same cell."""
        t = cls(spatial_depth, hasher)
        for suid, value in cells_values:
            t.add(suid, value)
        return t

    # -- construction --
    def add(self, suid, value) -> None:
        v = encode_value(value, self.h)
        base, children = suid_to_path(suid)
        if not (0 <= base < 6):
            raise ValueError(f"base {base} out of range")
        if len(children) > self.sd:
            raise ValueError(f"spatial level {len(children)} exceeds spatial_depth {self.sd}")

        if not children:                               # the whole base cell carries v
            self._bases[base] = self._apply(self._bases.get(base), v)
            return

        chain: list[tuple[dict, int]] = [(self._bases, base)]
        node = self._descend(self._bases.get(base))
        self._bases[base] = node
        cur: dict = node
        for c in children[:-1]:
            chain.append((cur, c))
            nxt = self._descend(cur.get(c))
            cur[c] = nxt
            cur = nxt
        key = children[-1]
        chain.append((cur, key))
        cur[key] = self._apply(cur.get(key), v)
        self._rollup_chain(chain)

    def _descend(self, node):
        """Make ``node`` a dict so a child can be set: a valued leaf expands into 9 children carrying
        its value (a finer fact specializes one; the rest inherit); an empty becomes ``{}``."""
        if isinstance(node, int):
            return {i: node for i in range(9)}
        if isinstance(node, dict):
            return node
        return {}

    def _apply(self, node, v: int):
        """Set value ``v`` at a node: empty/leaf -> v (overwrite); dict -> push v into every
        descendant, then re-roll."""
        if node is None or isinstance(node, int):
            return v
        return self._inherit(node, v)

    def _inherit(self, node: dict, v: int):
        for i in range(9):
            node[i] = self._apply(node.get(i), v)
        return self._maybe_rollup(node)

    def _maybe_rollup(self, node):
        """Collapse a dict of 9 leaves carrying the identical value to that one valued leaf."""
        if not isinstance(node, dict) or len(node) != 9:
            return node
        vals = []
        for i in range(9):
            child = node.get(i)
            if not isinstance(child, int):
                return node
            vals.append(child)
        return vals[0] if all(x == vals[0] for x in vals[1:]) else node

    def _rollup_chain(self, chain: list[tuple[dict, int]]) -> None:
        for container, key in reversed(chain):
            node = container.get(key)
            if not isinstance(node, dict):
                continue
            rolled = self._maybe_rollup(node)
            if rolled is node:
                break                                  # didn't collapse -> ancestors won't either
            container[key] = rolled

    # -- hashing --
    def _node_hash(self, node, d: int) -> bytes:
        if node is None:
            return self.SH.EMPTY[d]
        if isinstance(node, int):
            return _val_full(node, d, self.SH, self.h)
        assert isinstance(node, dict)
        return self.SH.internal([self._node_hash(node.get(i), d - 1) for i in range(9)])

    @property
    def root_hash(self) -> bytes:
        return self.SH.root([self._node_hash(self._bases.get(b), self.sd) for b in range(6)])

    @property
    def root_hash_hex(self) -> str:
        return self.root_hash.hex()

    # -- query + proof --
    def value_at(self, suid) -> int | None:
        """The value field element at an exactly-valued cell, else None (absent, partial, or valued
        only via a coarser ancestor — query at that granularity)."""
        base, children = suid_to_path(suid)
        collected = self._collect(base, children)
        if collected is None:
            return None
        _, _, term = collected
        return term if isinstance(term, int) else None

    def _collect(self, base: int, children: list[int]):
        sd = self.sd
        base_h = [self._node_hash(self._bases.get(b), sd) for b in range(6)]
        root_sibs = [base_h[b] for b in range(6) if b != base]
        internal_sibs: list[tuple[int, list[bytes]]] = []
        cur = self._bases.get(base)
        d = sd
        for c in children:
            if not isinstance(cur, dict):
                return None                            # absent (None) or a coarser valued ancestor
            sibs = [self._node_hash(cur.get(i), d - 1) for i in range(9) if i != c]
            internal_sibs.append((c, sibs))
            cur = cur.get(c)
            d -= 1
        return root_sibs, internal_sibs, cur

    def _collect_nm(self, base: int, children: list[int]):
        """Descend for non-membership: pass THROUGH absent (None) nodes building EMPTY sibs. Returns
        (root_sibs, internal_sibs, terminal, blocked); blocked = path hit a coarser valued leaf."""
        sd = self.sd
        base_h = [self._node_hash(self._bases.get(b), sd) for b in range(6)]
        root_sibs = [base_h[b] for b in range(6) if b != base]
        internal_sibs: list[tuple[int, list[bytes]]] = []
        cur = self._bases.get(base)
        d = sd
        for c in children:
            if isinstance(cur, dict):
                sibs = [self._node_hash(cur.get(i), d - 1) for i in range(9) if i != c]
                nxt = cur.get(c)
            elif cur is None:
                sibs = [self.SH.EMPTY[d - 1]] * 8
                nxt = None
            else:                                      # valued ancestor leaf
                return root_sibs, internal_sibs, cur, True
            internal_sibs.append((c, sibs))
            cur = nxt
            d -= 1
        return root_sibs, internal_sibs, cur, False

    def value_proof(self, suid) -> ValueProof | None:
        """Open the value at an exactly-valued cell (None if absent/partial/coarser-valued)."""
        base, children = suid_to_path(suid)
        collected = self._collect(base, children)
        if collected is None:
            return None
        root_sibs, internal_sibs, term = collected
        if not isinstance(term, int):
            return None
        return ValueProof(base, tuple(children), term, root_sibs, internal_sibs, self.sd)

    def non_membership_proof(self, suid) -> ValueNonMembershipProof | None:
        """Prove a cell carries no value (None if it is valued, or valued via a coarser ancestor)."""
        base, children = suid_to_path(suid)
        if len(children) > self.sd:
            return None
        root_sibs, internal_sibs, term, blocked = self._collect_nm(base, children)
        if blocked or term is not None:
            return None                                # member, or covered by a coarser ancestor
        return ValueNonMembershipProof(base, tuple(children), root_sibs, internal_sibs, self.sd)

from_cells classmethod

from_cells(
    cells_values,
    spatial_depth: int,
    hasher: HashFn | str = POSEIDON,
)

Build from an iterable of (suid, value). Later values overwrite earlier at the same cell.

Source code in burin/coverage/value_coverage.py

@classmethod
def from_cells(cls, cells_values, spatial_depth: int, hasher: HashFn | str = POSEIDON):
    """Build from an iterable of ``(suid, value)``. Later values overwrite earlier at the same cell."""
    t = cls(spatial_depth, hasher)
    for suid, value in cells_values:
        t.add(suid, value)
    return t

value_at

value_at(suid) -> int | None

The value field element at an exactly-valued cell, else None (absent, partial, or valued only via a coarser ancestor — query at that granularity).

Source code in burin/coverage/value_coverage.py

def value_at(self, suid) -> int | None:
    """The value field element at an exactly-valued cell, else None (absent, partial, or valued
    only via a coarser ancestor — query at that granularity)."""
    base, children = suid_to_path(suid)
    collected = self._collect(base, children)
    if collected is None:
        return None
    _, _, term = collected
    return term if isinstance(term, int) else None

value_proof

value_proof(suid) -> ValueProof | None

Open the value at an exactly-valued cell (None if absent/partial/coarser-valued).

Source code in burin/coverage/value_coverage.py

def value_proof(self, suid) -> ValueProof | None:
    """Open the value at an exactly-valued cell (None if absent/partial/coarser-valued)."""
    base, children = suid_to_path(suid)
    collected = self._collect(base, children)
    if collected is None:
        return None
    root_sibs, internal_sibs, term = collected
    if not isinstance(term, int):
        return None
    return ValueProof(base, tuple(children), term, root_sibs, internal_sibs, self.sd)

non_membership_proof

non_membership_proof(
    suid,
) -> ValueNonMembershipProof | None

Prove a cell carries no value (None if it is valued, or valued via a coarser ancestor).

Source code in burin/coverage/value_coverage.py

def non_membership_proof(self, suid) -> ValueNonMembershipProof | None:
    """Prove a cell carries no value (None if it is valued, or valued via a coarser ancestor)."""
    base, children = suid_to_path(suid)
    if len(children) > self.sd:
        return None
    root_sibs, internal_sibs, term, blocked = self._collect_nm(base, children)
    if blocked or term is not None:
        return None                                # member, or covered by a coarser ancestor
    return ValueNonMembershipProof(base, tuple(children), root_sibs, internal_sibs, self.sd)

ValueNonMembershipProof dataclass

Proves cell (base_idx, children) carries NO value — the absent fact g = EMPTY[d], local (no neighbours, no ordering): Cor 4.4's empty sandwich class.

Source code in burin/coverage/value_coverage.py

@dataclass
class ValueNonMembershipProof:
    """Proves cell ``(base_idx, children)`` carries NO value — the absent fact ``g = EMPTY[d]``,
    local (no neighbours, no ordering): Cor 4.4's empty sandwich class."""

    base_idx: int
    children: tuple[int, ...]
    root_sibs: list[bytes]
    internal_sibs: list[tuple[int, list[bytes]]]
    spatial_depth: int

    def verify(self, root_hash: bytes, hasher: HashFn | str = POSEIDON) -> bool:
        SH = _Hashing(9, 6, self.spatial_depth, hasher)
        level = len(self.children)
        if not (0 <= level <= self.spatial_depth) or len(self.root_sibs) != 5:
            return False
        # bind the claimed spatial cell to the authenticated path (see CoverageProof.verify)
        if tuple(pos for pos, _ in self.internal_sibs) != tuple(self.children):
            return False
        h = SH.EMPTY[self.spatial_depth - level]
        for pos, sibs in reversed(self.internal_sibs):
            if not (0 <= pos < 9) or len(sibs) != 8:
                return False
            it = iter(sibs)
            h = SH.internal([h if i == pos else next(it) for i in range(9)])
        it = iter(self.root_sibs)
        bvec = [h if b == self.base_idx else next(it) for b in range(6)]
        return SH.root(bvec) == root_hash

ValueProof dataclass

Opens cell (base_idx, children) to the value field element value_fe against the root (the 'this cell holds value V' proof). The disclosed value_fe is encode_value(value).

Source code in burin/coverage/value_coverage.py

@dataclass
class ValueProof:
    """Opens cell ``(base_idx, children)`` to the value field element ``value_fe`` against the root
    (the 'this cell holds value V' proof). The disclosed ``value_fe`` is ``encode_value(value)``."""

    base_idx: int
    children: tuple[int, ...]
    value_fe: int
    root_sibs: list[bytes]
    internal_sibs: list[tuple[int, list[bytes]]]
    spatial_depth: int

    def verify(self, root_hash: bytes, hasher: HashFn | str = POSEIDON) -> bool:
        SH = _Hashing(9, 6, self.spatial_depth, hasher)
        level = len(self.children)
        if not (0 <= level <= self.spatial_depth) or len(self.root_sibs) != 5:
            return False
        # bind the claimed spatial cell to the authenticated path (see CoverageProof.verify)
        if tuple(pos for pos, _ in self.internal_sibs) != tuple(self.children):
            return False
        h = _val_full(self.value_fe, self.spatial_depth - level, SH, hasher)
        for pos, sibs in reversed(self.internal_sibs):
            if not (0 <= pos < 9) or len(sibs) != 8:
                return False
            it = iter(sibs)
            h = SH.internal([h if i == pos else next(it) for i in range(9)])
        it = iter(self.root_sibs)
        bvec = [h if b == self.base_idx else next(it) for b in range(6)]
        return SH.root(bvec) == root_hash

allen_classify

allen_classify(
    a_start: int, a_end: int, b_start: int, b_end: int
) -> AllenRelation

Allen relation of A=[a_start,a_end) relative to B=[b_start,b_end). Branch-free.

Source code in burin/coverage/allen.py

def allen_classify(a_start: int, a_end: int, b_start: int, b_end: int) -> AllenRelation:
    """Allen relation of A=[a_start,a_end) relative to B=[b_start,b_end). Branch-free."""
    p = _sign(a_start - b_start)
    q = _sign(a_start - b_end)
    r = _sign(a_end - b_start)
    s = _sign(a_end - b_end)
    key = 27 * (p + 1) + 9 * (q + 1) + 3 * (r + 1) + (s + 1)
    return ALLEN_TABLE[key]

prove_allen

prove_allen(
    temporal_tree: HierarchicalCoverageTree,
    order: int,
    index: int,
    query_lo: int,
    query_hi: int,
) -> AllenProof | None

Build an AllenProof for a committed cell vs. a query interval, or None if the cell is not covered in temporal_tree.

Source code in burin/coverage/allen.py

def prove_allen(temporal_tree: HierarchicalCoverageTree, order: int, index: int,
                query_lo: int, query_hi: int) -> AllenProof | None:
    """Build an AllenProof for a committed cell vs. a query interval, or None if the
    cell is not covered in ``temporal_tree``."""
    if temporal_tree.aperture != 2 or temporal_tree.n_base != 1:
        raise ValueError("prove_allen requires a dyadic temporal tree (aperture=2, n_base=1)")
    mp = temporal_tree.membership_proof_cell(order, index)
    if mp is None:
        return None
    td = temporal_tree.H.R
    start, end = cell_interval(order, index, td)
    rel = allen_classify(start, end, query_lo, query_hi)
    return AllenProof(order, index, query_lo, query_hi, rel, mp, td)

canonical_fingerprint

canonical_fingerprint(
    suids: list[SUID],
    n_side: int = 3,
    resolution: int | None = None,
) -> bytes

Compute the canonical fingerprint for a set of cells.

Full pipeline

cells → canonicalize → spatial aperture-9 Merkle tree → root hash

Same coverage always produces the same 32-byte hash, regardless of input resolution or insertion order (the root is MOC-invariant: rolled-up and expanded inputs canonicalize to the same set → same root).

Parameters:

Name	Type	Description	Default
suids	list[SUID]	List of SUID tuples.	required
resolution	int | None	tree depth (resolution). If None, inferred from the deepest cell in the canonicalized set — which makes rolled/expanded inputs agree. Pass an explicit resolution to match fingerprint_polygon.	None

Returns:

Type	Description
bytes	32-byte Merkle root hash.

Note (v2.3 cutover): the canonical structure is SpatialMerkleTree. Roots differ from ≤v2.2.0.

Source code in burin/coverage/canonicalize.py

def canonical_fingerprint(
    suids: list[SUID], n_side: int = 3, resolution: int | None = None
) -> bytes:
    """
    Compute the canonical fingerprint for a set of cells.

    Full pipeline:
        cells → canonicalize → spatial aperture-9 Merkle tree → root hash

    Same coverage always produces the same 32-byte hash, regardless of input
    resolution or insertion order (the root is MOC-invariant: rolled-up and
    expanded inputs canonicalize to the same set → same root).

    Args:
        suids: List of SUID tuples.
        resolution: tree depth (resolution). If None, inferred from the deepest
            cell in the *canonicalized* set — which makes rolled/expanded inputs
            agree. Pass an explicit resolution to match ``fingerprint_polygon``.

    Returns:
        32-byte Merkle root hash.

    Note (v2.3 cutover): the canonical structure is ``SpatialMerkleTree``.
    Roots differ from ≤v2.2.0.
    """
    keys = [suid_to_bytes(s) for s in suids]
    canonical = canonicalize_keys(keys, n_side)
    csuids = [bytes_to_suid(k) for k in canonical]
    max_depth = resolution if resolution is not None else max(
        (len(s) - 1 for s in csuids), default=0
    )
    return SpatialMerkleTree.from_suids(csuids, max_depth).root_hash

canonical_fingerprint_hex

canonical_fingerprint_hex(
    suids: list[SUID], n_side: int = 3
) -> str

Hex string version of canonical_fingerprint().

Source code in burin/coverage/canonicalize.py

def canonical_fingerprint_hex(suids: list[SUID], n_side: int = 3) -> str:
    """Hex string version of canonical_fingerprint()."""
    return canonical_fingerprint(suids, n_side).hex()

canonicalize_keys

canonicalize_keys(
    keys: list[bytes], n_side: int = 3
) -> list[bytes]

Reduce a set of burin keys to canonical form.

When all N_side² children of a parent are present, replace them with the parent key. Cascade upward until stable.

Processes from finest resolution to coarsest, so each coalescence naturally feeds into the next level — no repeated passes needed.

Parameters:

Name	Type	Description	Default
keys	list[bytes]	List of resolution-first byte keys (from suid_to_bytes)	required
n_side	int	N_side parameter (default 3, giving 9 children per parent)	3

Returns:

Type	Description
list[bytes]	Sorted list of canonical burin keys

Source code in burin/coverage/canonicalize.py

def canonicalize_keys(keys: list[bytes], n_side: int = 3) -> list[bytes]:
    """
    Reduce a set of burin keys to canonical form.

    When all N_side² children of a parent are present, replace them
    with the parent key. Cascade upward until stable.

    Processes from finest resolution to coarsest, so each coalescence
    naturally feeds into the next level — no repeated passes needed.

    Args:
        keys: List of resolution-first byte keys (from suid_to_bytes)
        n_side: N_side parameter (default 3, giving 9 children per parent)

    Returns:
        Sorted list of canonical burin keys
    """
    n_side_sq = n_side**2
    key_set = set(keys)

    if not key_set:
        return []

    max_res = max(k[0] for k in key_set)

    for res in range(max_res, 0, -1):
        keys_at_res = [k for k in key_set if k[0] == res]
        if len(keys_at_res) < n_side_sq:
            continue

        by_parent: dict[tuple, list[bytes]] = defaultdict(list)
        for k in keys_at_res:
            suid = bytes_to_suid(k)
            p_suid = suid[:-1]
            by_parent[p_suid].append(k)

        for p_suid, children in by_parent.items():
            if len(children) == n_side_sq:
                expected = set(sibling_keys(children[0], n_side))
                if set(children) == expected:
                    key_set -= expected
                    key_set.add(suid_to_bytes(p_suid))

    return sorted(key_set)

canonicalize_suids

canonicalize_suids(
    suids: list[SUID], n_side: int = 3
) -> list[SUID]

Canonicalize a list of rHEALPix SUIDs.

Convenience wrapper — converts to keys, canonicalizes, converts back.

Parameters:

Name	Type	Description	Default
suids	list[SUID]	List of SUID tuples like [('Q', 4, 5, 0), ('Q', 4, 5, 1), ...]	required

Returns:

Type	Description
list[SUID]	Sorted list of canonical SUIDs

Source code in burin/coverage/canonicalize.py

def canonicalize_suids(suids: list[SUID], n_side: int = 3) -> list[SUID]:
    """
    Canonicalize a list of rHEALPix SUIDs.

    Convenience wrapper — converts to keys, canonicalizes, converts back.

    Args:
        suids: List of SUID tuples like [('Q', 4, 5, 0), ('Q', 4, 5, 1), ...]

    Returns:
        Sorted list of canonical SUIDs
    """
    keys = [suid_to_bytes(s) for s in suids]
    canonical = canonicalize_keys(keys, n_side)
    return [bytes_to_suid(k) for k in canonical]

fingerprint_polygon

fingerprint_polygon(
    geometry: object,
    resolution: int,
    plane: bool = False,
    n_side: int = 3,
    dggs: object = None,
) -> bytes

Compute a canonical fingerprint for a polygon's rHEALPix coverage.

Full pipeline (v2.3): Shapely polygon → vectorised int64 polyfill → stride-9 coalesce → SpatialMerkleTree (depth = resolution) → root hash

The guarantee: same polygon + same resolution = same 32-byte hash. Two independent providers produce identical fingerprints without coordinating; the root is also MOC-invariant. v2.3 cutover: the canonical structure is the spatial aperture-9 Merkle tree, so roots differ from ≤v2.2.0.

Resolution is part of the standard — different resolutions produce different fingerprints (finer resolution captures more boundary detail).

Parameters:

Name	Type	Description	Default
geometry	object	Shapely Polygon or MultiPolygon (lon/lat).	required
resolution	int	rHEALPix resolution (0-15). Part of the fingerprint identity.	required
plane	bool	Reserved for forward compatibility; the v2.1 fast path operates on lon/lat coordinates and ignores this argument. Pass-through callers using plane=True should keep using canonical_fingerprint over an explicit SUID list until the planar path lands.	False
n_side	int	N_side parameter (default 3). Only N_side=3 is supported in the v2.1 fast path; other values raise ValueError.	3
dggs	object	Reserved for forward compatibility; the v2.1 fast path uses the WGS84 N_side=3 DGGS implicitly via the spatial-id encoding.	None

Returns:

Type	Description
bytes	32-byte Merkle root hash.

Raises:

Type	Description
ValueError	If polyfill returns no cells (polygon strictly smaller than a cell at the requested resolution), if plane=True is passed, if n_side != 3, or if dggs is non-default.

Source code in burin/coverage/canonicalize.py

def fingerprint_polygon(
    geometry: object, resolution: int, plane: bool = False, n_side: int = 3, dggs: object = None
) -> bytes:
    """
    Compute a canonical fingerprint for a polygon's rHEALPix coverage.

    Full pipeline (v2.3):
        Shapely polygon → vectorised int64 polyfill → stride-9 coalesce
                       → SpatialMerkleTree (depth = resolution) → root hash

    The guarantee: same polygon + same resolution = same 32-byte hash. Two
    independent providers produce identical fingerprints without coordinating;
    the root is also MOC-invariant. v2.3 cutover: the canonical structure is
    the spatial aperture-9 Merkle tree, so roots differ from ≤v2.2.0.

    Resolution is part of the standard — different resolutions produce
    different fingerprints (finer resolution captures more boundary
    detail).

    Args:
        geometry: Shapely Polygon or MultiPolygon (lon/lat).
        resolution: rHEALPix resolution (0-15). Part of the fingerprint
            identity.
        plane: Reserved for forward compatibility; the v2.1 fast path
            operates on lon/lat coordinates and ignores this argument.
            Pass-through callers using ``plane=True`` should keep using
            ``canonical_fingerprint`` over an explicit SUID list until
            the planar path lands.
        n_side: N_side parameter (default 3). Only N_side=3 is supported
            in the v2.1 fast path; other values raise ``ValueError``.
        dggs: Reserved for forward compatibility; the v2.1 fast path uses
            the WGS84 N_side=3 DGGS implicitly via the spatial-id
            encoding.

    Returns:
        32-byte Merkle root hash.

    Raises:
        ValueError: If polyfill returns no cells (polygon strictly
            smaller than a cell at the requested resolution), if
            ``plane=True`` is passed, if ``n_side != 3``, or if
            ``dggs`` is non-default.
    """
    if geometry is None:
        raise ValueError("geometry is None")
    if plane:
        raise ValueError(
            "plane=True is not supported by the v2.1 fast path; "
            "use canonical_fingerprint over an explicit SUID list."
        )
    if n_side != 3:
        raise ValueError(
            f"n_side={n_side} is not supported by the v2.1 fast path; only n_side=3."
        )
    if dggs is not None:
        from rhealpixdggs.dggs import WGS84_003

        if dggs is not WGS84_003:
            raise ValueError(
                "Custom dggs is not supported by the v2.1 fast path; pass dggs=None."
            )

    spatial_ids = _polyfill_int64(geometry, resolution)
    if spatial_ids.size == 0:
        raise ValueError(
            f"No cells at resolution {resolution} — polygon may be smaller than cell size"
        )

    canonical_ids = _canonicalize_int64(spatial_ids)

    # Build the canonical structure: the spatial aperture-9 Merkle tree keyed
    # by the SUID path, at depth = resolution. Root is deterministic + MOC-invariant.
    csuids = [_suid_from_spatial_id(int(s)) for s in canonical_ids]
    return SpatialMerkleTree.from_suids(csuids, resolution).root_hash

fingerprint_polygon_hex

fingerprint_polygon_hex(
    geometry: object,
    resolution: int,
    plane: bool = False,
    n_side: int = 3,
    dggs: object = None,
) -> str

Hex string version of fingerprint_polygon().

Source code in burin/coverage/canonicalize.py

def fingerprint_polygon_hex(
    geometry: object, resolution: int, plane: bool = False, n_side: int = 3, dggs: object = None
) -> str:
    """Hex string version of fingerprint_polygon()."""
    return fingerprint_polygon(geometry, resolution, plane, n_side, dggs).hex()

parent_key

parent_key(key: bytes) -> bytes | None

Get the burin key of a cell's parent.

Pure byte operation via SUID roundtrip.

Returns None for base cells (resolution 0).

Source code in burin/coverage/canonicalize.py

def parent_key(key: bytes) -> bytes | None:
    """
    Get the burin key of a cell's parent.

    Pure byte operation via SUID roundtrip.

    Returns None for base cells (resolution 0).
    """
    suid = bytes_to_suid(key)
    if len(suid) <= 1:
        return None
    return suid_to_bytes(suid[:-1])

sibling_keys

sibling_keys(key: bytes, n_side: int = 3) -> list[bytes]

Get all N_side² sibling keys (including the key itself), sorted.

For N_side=3, returns 9 keys — the complete set of children sharing the same parent.

Source code in burin/coverage/canonicalize.py

def sibling_keys(key: bytes, n_side: int = 3) -> list[bytes]:
    """
    Get all N_side² sibling keys (including the key itself), sorted.

    For N_side=3, returns 9 keys — the complete set of children
    sharing the same parent.
    """
    suid = bytes_to_suid(key)
    if len(suid) <= 1:
        return [key]  # base cell has no siblings
    parent_suid = suid[:-1]
    n_side_sq = n_side**2
    return sorted(suid_to_bytes(parent_suid + (i,)) for i in range(n_side_sq))

attestation_message

attestation_message(
    witness_pk: bytes,
    epoch: int,
    prev_hash: bytes,
    root: bytes,
    issued_at: int | None,
    subject: tuple[int, int] | None,
    policy: int,
) -> bytes

Canonical, domain-separated message a witness signs for one attestation. issued_at (when) and subject are optional dimensions, each length-prefixed by a presence byte so 'absent' is distinct from any concrete value (a time-agnostic witness omits issued_at).

Source code in burin/coverage/fraud.py

def attestation_message(witness_pk: bytes, epoch: int, prev_hash: bytes, root: bytes,
                        issued_at: int | None, subject: tuple[int, int] | None, policy: int) -> bytes:
    """Canonical, domain-separated message a witness signs for one attestation. ``issued_at``
    (*when*) and ``subject`` are optional dimensions, each length-prefixed by a presence byte so
    'absent' is distinct from any concrete value (a time-agnostic witness omits ``issued_at``)."""
    out = bytearray(_DOM)
    out += b"\x10"
    out += len(witness_pk).to_bytes(2, "big") + witness_pk
    out += int(epoch).to_bytes(8, "big")
    out += prev_hash
    out += root
    if issued_at is None:                                  # 'when' is optional
        out += b"\x00"
    else:
        out += b"\x01" + int(issued_at).to_bytes(8, "big")
    out += int(policy).to_bytes(1, "big")
    if subject is None:
        out += b"\x00"
    else:
        lo, hi = subject
        out += b"\x01" + int(lo).to_bytes(8, "big") + int(hi).to_bytes(8, "big")
    return bytes(out)

decode_spatial

decode_spatial(spatial_id: int) -> tuple[int, int, int]

Inverse of :func:to_spatial_id.

Parameters:

Name	Type	Description	Default
spatial_id	int	64-bit canonical spatial id.	required

Returns:

Type	Description
tuple[int, int, int]	(face, peano_position, level) triple.

Source code in burin/coverage/spatial.py

def decode_spatial(spatial_id: int) -> tuple[int, int, int]:
    """
    Inverse of :func:`to_spatial_id`.

    Args:
        spatial_id: 64-bit canonical spatial id.

    Returns:
        ``(face, peano_position, level)`` triple.
    """
    level = spatial_id & LEVEL_MASK
    peano = (spatial_id >> PEANO_SHIFT) & PEANO_MASK
    face = (spatial_id >> FACE_SHIFT) & FACE_MASK
    return face, peano, level

from_crypto_bytes

from_crypto_bytes(crypto_bytes: bytes) -> int

Inverse of :func:to_crypto_bytes.

Parameters:

Name	Type	Description	Default
crypto_bytes	bytes	bytes in burin's resolution-first format.	required

Returns:

Type	Description
int	Canonical 64-bit spatial_id.

Raises:

Type	Description
ValueError	if the input is too short or fields are out of range.

Source code in burin/coverage/spatial.py

def from_crypto_bytes(crypto_bytes: bytes) -> int:
    """
    Inverse of :func:`to_crypto_bytes`.

    Args:
        crypto_bytes: bytes in burin's resolution-first format.

    Returns:
        Canonical 64-bit ``spatial_id``.

    Raises:
        ValueError: if the input is too short or fields are out of range.
    """
    if len(crypto_bytes) < 2:
        raise ValueError(f"crypto_bytes too short: {len(crypto_bytes)} bytes")

    level = crypto_bytes[0]
    face = crypto_bytes[1]

    if not (0 <= level <= MAX_LEVEL):
        raise ValueError(f"level {level} out of range [0, {MAX_LEVEL}]")
    if not (0 <= face <= FACE_MASK):
        raise ValueError(f"face {face} out of range [0, {FACE_MASK}]")

    # Unpack rHEALPix child digits (MSB-first), trim to `level`.
    digits: list[int] = []
    for byte in crypto_bytes[2:]:
        digits.append((byte >> 4) & 0x0F)
        digits.append(byte & 0x0F)
    digits = digits[:level]

    # Re-encode digits via the M2 state machine to recover the Peano
    # position. Linear in `level`; for level <= 4 the chunk lookup also
    # works but the state-machine path keeps both branches consistent.
    peano = peano_position_from_digits(digits, level) if level > 0 else 0

    return to_spatial_id(face, peano, level)

spatial_id_from_suid

spatial_id_from_suid(suid: tuple[str | int, ...]) -> int

Convert an rHEALPix SUID tuple to a canonical spatial_id.

Parameters:

Name	Type	Description	Default
suid	tuple[str | int, ...]	SUID tuple like ('N', 3, 2, 1) or ('S',). The first element is either the base-cell letter ('N'..'S') or the corresponding integer index. Subsequent elements are rHEALPix child digits in [0, 9).	required

Returns:

Type	Description
int	Canonical spatial_id.

Source code in burin/coverage/spatial.py

def spatial_id_from_suid(suid: tuple[str | int, ...]) -> int:
    """
    Convert an rHEALPix SUID tuple to a canonical ``spatial_id``.

    Args:
        suid: SUID tuple like ``('N', 3, 2, 1)`` or ``('S',)``. The
            first element is either the base-cell letter (``'N'..'S'``)
            or the corresponding integer index. Subsequent elements are
            rHEALPix child digits in ``[0, 9)``.

    Returns:
        Canonical ``spatial_id``.
    """
    if not suid:
        raise ValueError("suid must be non-empty")

    head = suid[0]
    if isinstance(head, int):
        face = head
    else:
        try:
            face = FACE_TO_INDEX[head]
        except KeyError as exc:
            raise ValueError(f"unknown base cell {head!r}") from exc

    children = [int(c) for c in suid[1:]]
    level = len(children)
    peano = peano_position_from_digits(children, level)
    return to_spatial_id(face, peano, level)

suid_from_spatial_id

suid_from_spatial_id(
    spatial_id: int,
) -> tuple[str | int, ...]

Inverse of :func:spatial_id_from_suid.

Parameters:

Name	Type	Description	Default
spatial_id	int	canonical 64-bit spatial_id.	required

Returns:

Type	Description
str | int	SUID tuple of the form (letter, d0, d1, ..., d_{level-1}),
...	suitable for cross-checking against rhealpixdggs.Cell.suid.

Source code in burin/coverage/spatial.py

def suid_from_spatial_id(spatial_id: int) -> tuple[str | int, ...]:
    """
    Inverse of :func:`spatial_id_from_suid`.

    Args:
        spatial_id: canonical 64-bit ``spatial_id``.

    Returns:
        SUID tuple of the form ``(letter, d0, d1, ..., d_{level-1})``,
        suitable for cross-checking against ``rhealpixdggs.Cell.suid``.
    """
    face, peano, level = decode_spatial(spatial_id)
    letter = INDEX_TO_FACE[face]
    digits = digits_from_peano_position(peano, level) if level > 0 else []
    return (letter, *digits)

to_crypto_bytes

to_crypto_bytes(spatial_id: int) -> bytes

Translate spatial_id to the resolution-first crypto byte layout.

Output is bit-identical to suid_to_bytes(suid) for the cell that spatial_id represents — the compatibility invariant, verified exhaustively through resolution 4.

Format::

[level_byte][face_byte][packed digits, 2 per byte, hi-nibble first]

The last nibble is padded with 0 if level is odd.

Parameters:

Name	Type	Description	Default
spatial_id	int	64-bit canonical spatial id.	required

Returns:

Type	Description
bytes	Crypto bytes consumable by burin's hashing / canonicalisation.

Source code in burin/coverage/spatial.py

def to_crypto_bytes(spatial_id: int) -> bytes:
    """
    Translate ``spatial_id`` to the resolution-first crypto byte layout.

    Output is **bit-identical** to ``suid_to_bytes(suid)`` for the cell
    that ``spatial_id`` represents — the compatibility invariant, verified
    exhaustively through resolution 4.

    Format::

        [level_byte][face_byte][packed digits, 2 per byte, hi-nibble first]

    The last nibble is padded with ``0`` if ``level`` is odd.

    Args:
        spatial_id: 64-bit canonical spatial id.

    Returns:
        Crypto bytes consumable by burin's hashing / canonicalisation.
    """
    face, peano, level = decode_spatial(spatial_id)

    # Decode peano position -> rHEALPix child digits (MSB-first) via the
    # 4-digit-chunk lookup, peeling chunks off the LSB end of `peano`.
    if level == 0:
        digits: list[int] = []
    elif level <= _CHUNK_LEVEL:
        # Single chunk, fast path. Pad the chunk position to 4 levels by
        # treating the missing high digits as zero (state P stays P under
        # zero, see CHILD_STATE table).
        chunk = _PEANO_TO_DIGITS[peano]
        # Take the last `level` digits (the LSB end of the 4-digit chunk
        # corresponds to the deeper levels MSB-first within `level`).
        digits = list(chunk[_CHUNK_LEVEL - level:])
    else:
        # NOTE(M1-multi-chunk): the dual-encoding spec sketches a
        # multi-chunk decoder, but it relies on an additional
        # state-tracking helper that M2 has not exposed yet (the
        # state at the start of each non-leading chunk depends on the
        # cumulative Peano traversal so far). For levels > 4 we fall
        # back to the per-level state-machine walk via
        # ``digits_from_peano_position`` from M2, which is correct by
        # construction. Cost: O(level) instead of O(level / 4); still
        # well below 1 us per cell for level <= 15.
        digits = digits_from_peano_position(peano, level)

    # Pack: [level][face][digits packed 2-per-byte, hi-nibble first].
    # Pad to even length to match burin's suid_to_bytes exactly.
    buf = bytearray((level, face))
    if len(digits) % 2 == 1:
        digits = digits + [0]
    for i in range(0, len(digits), 2):
        hi = digits[i] & 0x0F
        lo = digits[i + 1] & 0x0F
        buf.append((hi << 4) | lo)
    return bytes(buf)

to_spatial_id

to_spatial_id(
    face: int, peano_position: int, level: int
) -> int

Pack (face, peano_position, level) into the 64-bit canonical layout.

Parameters:

Name	Type	Description	Default
face	int	rHEALPix base cell index in [0, 6) (N=0..S=5).	required
peano_position	int	Peano traversal position within the face, in [0, 9**level). Must fit in PEANO_BITS == 57 bits.	required
level	int	cell resolution in [0, MAX_LEVEL] (i.e. 0..15).	required

Returns:

Type	Description
int	64-bit int spatial_id packed as
int	(face << 61) | (peano << 4) | level.

Raises:

Type	Description
ValueError	if any input is out of range.

Source code in burin/coverage/spatial.py

def to_spatial_id(face: int, peano_position: int, level: int) -> int:
    """
    Pack ``(face, peano_position, level)`` into the 64-bit canonical layout.

    Args:
        face: rHEALPix base cell index in ``[0, 6)`` (``N=0..S=5``).
        peano_position: Peano traversal position within the face, in
            ``[0, 9**level)``. Must fit in ``PEANO_BITS == 57`` bits.
        level: cell resolution in ``[0, MAX_LEVEL]`` (i.e. ``0..15``).

    Returns:
        64-bit ``int`` ``spatial_id`` packed as
        ``(face << 61) | (peano << 4) | level``.

    Raises:
        ValueError: if any input is out of range.
    """
    if not (0 <= face <= FACE_MASK):
        raise ValueError(f"face {face} out of range [0, {FACE_MASK}]")
    if not (0 <= level <= MAX_LEVEL):
        raise ValueError(f"level {level} out of range [0, {MAX_LEVEL}]")
    if not (0 <= peano_position < (1 << PEANO_BITS)):
        raise ValueError(
            f"peano_position {peano_position} does not fit in {PEANO_BITS} bits"
        )
    upper = 9**level
    if not (0 <= peano_position < upper) and not (peano_position == 0 and level == 0):
        raise ValueError(
            f"peano_position {peano_position} out of range [0, {upper}) for level {level}"
        )

    return (face << FACE_SHIFT) | (peano_position << PEANO_SHIFT) | level

verify_proof

verify_proof(
    proof: CoverageProof,
    root_hash: bytes,
    max_depth: int,
    hasher: HashFn | str = POSEIDON,
) -> bool

Stateless verification — needs only the proof, root, max_depth, hasher.

Source code in burin/coverage/spatial_merkle.py

def verify_proof(proof: CoverageProof, root_hash: bytes, max_depth: int,
                 hasher: HashFn | str = POSEIDON) -> bool:
    """Stateless verification — needs only the proof, root, max_depth, hasher."""
    return proof.verify(root_hash, max_depth, hasher)

encode_value

encode_value(value, hasher: HashFn | str = POSEIDON) -> int

Canonical opaque value -> one field element (the leaf payload v). A scalar binds directly (dual-mode + ZK-ready: the leaf poseidon([5, v]) is the only hash and the circuit stays cheap). A vector/tuple reduces to one field element via the SAME hasher as the tree — Poseidon on the proof path, keccak/blake on the compute path — so neither path silently depends on the other. Any future type (quantized float, nested commitment) lands here. Pure function of the value (no nonce).

Source code in burin/coverage/value_coverage.py

def encode_value(value, hasher: HashFn | str = POSEIDON) -> int:
    """Canonical opaque value -> one field element (the leaf payload ``v``). A scalar binds directly
    (dual-mode + ZK-ready: the leaf ``poseidon([5, v])`` is the only hash and the circuit stays cheap).
    A vector/tuple reduces to one field element via the SAME ``hasher`` as the tree — Poseidon on the
    proof path, keccak/blake on the compute path — so neither path silently depends on the other. Any
    future type (quantized float, nested commitment) lands here. Pure function of the value (no nonce)."""
    if isinstance(value, (tuple, list)):
        limbs = [int(v) % _pos.P for v in value]
        if hasher == POSEIDON:
            return _pos.poseidon([_VAL_PAYLOAD_FE, *limbs])
        assert not isinstance(hasher, str)
        return int.from_bytes(hasher(_TAG_VAL_PAYLOAD + b"".join(x.to_bytes(32, "big") for x in limbs)), "big") % _pos.P
    return int(value) % _pos.P

bytes_to_suid

bytes_to_suid(data: bytes) -> SUID

Convert byte encoding back to rHEALPix SUID.

Parameters:

Name	Type	Description	Default
data	bytes	Byte encoding from suid_to_bytes()	required

Returns:

Type	Description
SUID	SUID tuple

Example

bytes_to_suid(b'\x03\x00\x32\x10') ('N', 3, 2, 1)

Source code in burin/coverage/suid_encoding.py

def bytes_to_suid(data: bytes) -> SUID:
    """
    Convert byte encoding back to rHEALPix SUID.

    Args:
        data: Byte encoding from suid_to_bytes()

    Returns:
        SUID tuple

    Example:
        >>> bytes_to_suid(b'\\x03\\x00\\x32\\x10')
        ('N', 3, 2, 1)
    """
    if len(data) < 2:
        raise ValueError("Invalid SUID encoding: too short")

    resolution = data[0]
    base_index = data[1]
    base_cell = INDEX_TO_BASE_CELL[base_index]

    # Unpack children
    children = []
    for byte in data[2:]:
        high = (byte >> 4) & 0x0F
        low = byte & 0x0F
        children.append(high)
        children.append(low)

    # Trim to actual resolution
    children = children[:resolution]

    # Build SUID
    suid = [base_cell] + children
    return tuple(suid)

nuniq_to_suid

nuniq_to_suid(nuniq: int, n_side: int = 3) -> SUID

Convert NUNIQ-style integer back to SUID.

Parameters:

Name	Type	Description	Default
nuniq	int	Integer NUNIQ encoding	required
n_side	int	N_side parameter (default 3)	3

Returns:

Type	Description
SUID	SUID tuple

Source code in burin/coverage/suid_encoding.py

def nuniq_to_suid(nuniq: int, n_side: int = 3) -> SUID:
    """
    Convert NUNIQ-style integer back to SUID.

    Args:
        nuniq: Integer NUNIQ encoding
        n_side: N_side parameter (default 3)

    Returns:
        SUID tuple
    """
    n_side_sq = n_side**2

    # Find resolution by checking cumulative cell counts
    offset = 0
    resolution = 0
    while True:
        cells_at_res = 6 * (n_side_sq**resolution)
        if offset + cells_at_res > nuniq:
            break
        offset += cells_at_res
        resolution += 1
        if resolution > 20:  # Safety limit
            raise ValueError(f"Invalid NUNIQ: {nuniq}")

    # Remaining index at this resolution
    remaining = nuniq - offset

    # Find base cell and position
    cells_per_base = n_side_sq**resolution
    base_index = remaining // cells_per_base
    position = remaining % cells_per_base

    base_cell = INDEX_TO_BASE_CELL[base_index]

    # Convert position to child indices
    children = []
    for i in range(resolution):
        power = resolution - 1 - i
        divisor = n_side_sq**power
        child = position // divisor
        position = position % divisor
        children.append(child)

    suid = [base_cell] + children
    return tuple(suid)

string_to_suid

string_to_suid(s: str) -> SUID

Convert string representation back to SUID.

Example

string_to_suid('N321') ('N', 3, 2, 1)

Source code in burin/coverage/suid_encoding.py

def string_to_suid(s: str) -> SUID:
    """
    Convert string representation back to SUID.

    Example:
        >>> string_to_suid('N321')
        ('N', 3, 2, 1)
    """
    if not s or s[0] not in BASE_CELLS:
        raise ValueError(f"Invalid SUID string: {s}")

    base_cell = s[0]
    children = [int(c) for c in s[1:]]
    return tuple([base_cell] + children)

suid_to_bytes

suid_to_bytes(suid: SUID | list, n_side: int = 3) -> bytes

Convert a rHEALPix SUID to canonical byte encoding.

Format: - Byte 0: resolution (0-255) - Byte 1: base cell index (0-5) - Bytes 2+: packed child indices (4 bits each, 2 per byte)

Parameters:

Name	Type	Description	Default
suid	SUID | list	SUID tuple like ('N', 3, 2, 1) or list ['N', 3, 2, 1]	required
n_side	int	N_side parameter (default 3)	3

Returns:

Type	Description
bytes	Canonical byte encoding

Example

suid_to_bytes(('N', 3, 2, 1)) b'\x03\x00\x32\x10' # res=3, base=N(0), children=3,2,1,0(pad)

Source code in burin/coverage/suid_encoding.py

def suid_to_bytes(suid: SUID | list, n_side: int = 3) -> bytes:
    """
    Convert a rHEALPix SUID to canonical byte encoding.

    Format:
    - Byte 0: resolution (0-255)
    - Byte 1: base cell index (0-5)
    - Bytes 2+: packed child indices (4 bits each, 2 per byte)

    Args:
        suid: SUID tuple like ('N', 3, 2, 1) or list ['N', 3, 2, 1]
        n_side: N_side parameter (default 3)

    Returns:
        Canonical byte encoding

    Example:
        >>> suid_to_bytes(('N', 3, 2, 1))
        b'\\x03\\x00\\x32\\x10'  # res=3, base=N(0), children=3,2,1,0(pad)
    """
    suid = tuple(suid)

    # Resolution = len(suid) - 1 (base cell doesn't count)
    resolution = len(suid) - 1

    # Base cell: accept either the letter or an already-computed index.
    base_cell = suid[0]
    base_index = base_cell if isinstance(base_cell, int) else BASE_CELL_TO_INDEX[base_cell]

    # Start building bytes
    result = bytearray()
    result.append(resolution)
    result.append(base_index)

    # Pack children (4 bits each)
    children = [int(c) for c in suid[1:]]

    # Pad to even length if needed
    if len(children) % 2 == 1:
        children.append(0)

    # Pack pairs of children into bytes
    for i in range(0, len(children), 2):
        high = children[i] & 0x0F  # First child in high nibble
        low = children[i + 1] & 0x0F  # Second child in low nibble
        result.append((high << 4) | low)

    return bytes(result)

suid_to_nuniq

suid_to_nuniq(suid: SUID | list, n_side: int = 3) -> int

Convert SUID to NUNIQ-style single integer encoding.

Formula: nuniq = 6 * n_side^(2*res) * base_index + position

Where position is the cell's position within its base cell subtree, computed by treating child indices as base-(n_side²) digits.

This encoding has the property that cells are ordered by: 1. Resolution (lower resolutions first) 2. Base cell (N < O < P < Q < R < S) 3. Position within base cell

Parameters:

Name	Type	Description	Default
suid	SUID | list	SUID tuple like ('N', 3, 2, 1)	required
n_side	int	N_side parameter (default 3)	3

Returns:

Type	Description
int	Integer NUNIQ encoding

Source code in burin/coverage/suid_encoding.py

def suid_to_nuniq(suid: SUID | list, n_side: int = 3) -> int:
    """
    Convert SUID to NUNIQ-style single integer encoding.

    Formula: nuniq = 6 * n_side^(2*res) * base_index + position

    Where position is the cell's position within its base cell subtree,
    computed by treating child indices as base-(n_side²) digits.

    This encoding has the property that cells are ordered by:
    1. Resolution (lower resolutions first)
    2. Base cell (N < O < P < Q < R < S)
    3. Position within base cell

    Args:
        suid: SUID tuple like ('N', 3, 2, 1)
        n_side: N_side parameter (default 3)

    Returns:
        Integer NUNIQ encoding
    """
    suid = tuple(suid)
    resolution = len(suid) - 1

    base_cell = suid[0]
    base_index = base_cell if isinstance(base_cell, int) else BASE_CELL_TO_INDEX[base_cell]

    # Compute position: treat children as base-(n_side²) digits
    n_side_sq = n_side**2
    position = 0
    for i, child in enumerate(suid[1:]):
        # Most significant digit first
        power = resolution - 1 - i
        position += int(child) * (n_side_sq**power)

    # Compute offset for this resolution level
    # All lower resolution cells come first
    offset = 0
    for r in range(resolution):
        # At resolution r, there are 6 * n_side^(2r) cells
        offset += 6 * (n_side_sq**r)

    # Final NUNIQ
    cells_per_base = n_side_sq**resolution
    nuniq = offset + base_index * cells_per_base + position

    return nuniq

suid_to_string

suid_to_string(suid: SUID | list) -> str

Convert SUID to canonical string representation.

Simple and human-readable, good for debugging.

Example

suid_to_string(('N', 3, 2, 1)) 'N321'

Source code in burin/coverage/suid_encoding.py

def suid_to_string(suid: SUID | list) -> str:
    """
    Convert SUID to canonical string representation.

    Simple and human-readable, good for debugging.

    Example:
        >>> suid_to_string(('N', 3, 2, 1))
        'N321'
    """
    return "".join(str(c) for c in suid)

coalesce_ids

coalesce_ids(spatial_ids: ndarray) -> ndarray

Coalesce complete 9-sibling groups up the rHEALPix hierarchy.

Parameters

spatial_ids Sorted uint64 array of spatial_id values at one or more levels (also accepts int64; we cast to uint64 to make the bit-field arithmetic well-defined for face indices >= 4 whose high-bit gets set in the layout). Input from :func:torus.polyfill.polyfill is already sorted at a single level; this function also accepts mixed-level input (we sort defensively) for use as a generic canonicalisation step.

Returns

numpy.ndarray Sorted uint64 array of canonical spatial_id values. Any complete sibling group of 9 cells is collapsed to its parent; the cascade runs to convergence.

Notes

The crypto-bytes set obtained via [to_crypto_bytes(int(s)) for s in canonicalize(...)] is identical to burin.coverage.canonicalize.canonicalize_keys([to_crypto_bytes(int(s)) for s in spatial_ids]), which is the gate enforced by the M4 fingerprint-parity test.

Source code in burin/coverage/_coalesce.py

def canonicalize(spatial_ids: np.ndarray) -> np.ndarray:
    """Coalesce complete 9-sibling groups up the rHEALPix hierarchy.

    Parameters
    ----------
    spatial_ids
        Sorted ``uint64`` array of ``spatial_id`` values at one or more
        levels (also accepts ``int64``; we cast to ``uint64`` to make
        the bit-field arithmetic well-defined for face indices >= 4 whose
        high-bit gets set in the layout). Input from
        :func:`torus.polyfill.polyfill` is already sorted at a single
        level; this function also accepts mixed-level input (we sort
        defensively) for use as a generic canonicalisation step.

    Returns
    -------
    numpy.ndarray
        Sorted ``uint64`` array of canonical ``spatial_id`` values. Any
        complete sibling group of 9 cells is collapsed to its parent;
        the cascade runs to convergence.

    Notes
    -----
    The crypto-bytes set obtained via
    ``[to_crypto_bytes(int(s)) for s in canonicalize(...)]`` is identical
    to ``burin.coverage.canonicalize.canonicalize_keys([to_crypto_bytes(int(s)) for s in spatial_ids])``,
    which is the gate enforced by the M4 fingerprint-parity test.
    """
    if spatial_ids.size == 0:
        return np.empty(0, dtype=np.uint64)

    if spatial_ids.dtype != np.uint64:
        spatial_ids = spatial_ids.astype(np.uint64, copy=False)

    # Defensive: dedupe + sort. Polyfill output already meets both
    # invariants; unique() also gives us the sort.
    arr = np.unique(spatial_ids)

    # Bucket by level. The level field is the bottom 4 bits.
    levels = (arr & _LEVEL_FIELD_MASK).astype(np.int64)
    max_level = int(levels.max())

    # Maintain a per-level pool of cells. We process finest -> coarsest;
    # promoted parents get added to the next-coarser pool.
    pools: list[np.ndarray] = [
        np.empty(0, dtype=np.uint64) for _ in range(max_level + 1)
    ]
    for lvl in range(max_level + 1):
        mask = levels == lvl
        if mask.any():
            pools[lvl] = arr[mask]
            # Already sorted because `arr` is sorted and a level mask
            # preserves order.

    for lvl in range(max_level, 0, -1):
        if pools[lvl].size == 0:
            continue
        promoted, leftover = _coalesce_one_level(pools[lvl], lvl)
        pools[lvl] = leftover
        if promoted.size > 0:
            # Merge promoted with whatever is already at level lvl - 1.
            # The result needs to stay sorted so the next iteration sees
            # a sorted array. np.unique handles both.
            pools[lvl - 1] = np.unique(np.concatenate([pools[lvl - 1], promoted]))

    # Concatenate all pools (each is sorted) into the final array. We
    # then run np.unique once more to give a single sorted output across
    # levels (cells at different levels do not generally interleave but
    # we sort anyway for caller convenience).
    nonempty = [p for p in pools if p.size > 0]
    if not nonempty:
        return np.empty(0, dtype=np.uint64)
    out = np.concatenate(nonempty)
    out.sort(kind="quicksort")
    return out

cell_ij_from_peano

cell_ij_from_peano(
    peano: int, level: int
) -> tuple[int, int]

Map a Peano position at level to the integer grid coordinates (i, j) of the corresponding leaf cell, with i the column index in [0, 3**level) and j the row index measured from the bottom.

This is what prototype/scripts/render_peano.py uses to plot the curve. It is a pure function of the state machine -- no rHEALPix geometry involved.

The relationship between rHEALPix's row-from-top index r and our bottom-up j at level L is r = (3**L - 1) - j.

Source code in burin/coverage/_peano.py

def cell_ij_from_peano(peano: int, level: int) -> tuple[int, int]:
    """
    Map a Peano position at `level` to the integer grid coordinates
    `(i, j)` of the corresponding leaf cell, with `i` the column index in
    `[0, 3**level)` and `j` the row index measured from the **bottom**.

    This is what `prototype/scripts/render_peano.py` uses to plot the
    curve. It is a pure function of the state machine -- no rHEALPix
    geometry involved.

    The relationship between rHEALPix's row-from-top index `r` and our
    bottom-up `j` at level L is `r = (3**L - 1) - j`.
    """
    if level == 0:
        return (0, 0)
    state = ROOT_STATE
    i, j = 0, 0
    side = 3**level
    for k in range(level):
        shift = 9 ** (level - 1 - k)
        pos = (peano // shift) % 9
        sub_side = side // (3 ** (k + 1))
        # Get (i_sub, j_sub) in [0,3)^2 for this state at this peano pos.
        i_sub, j_sub = _state_pos_to_subcell_ij(state, pos)
        i += i_sub * sub_side
        j += j_sub * sub_side
        state = CHILD_STATE[state][pos]
    return i, j

digits_from_peano_position

digits_from_peano_position(
    peano: int, level: int
) -> list[int]

Convert a Peano traversal position into a list of rHEALPix child digits.

Inverse of peano_position_from_digits.

Parameters:

Name	Type	Description	Default
peano	int	Peano position, must satisfy 0 <= peano < 9**level.	required
level	int	tree depth.	required

Returns:

Type	Description
list[int]	List of level rHEALPix child digits, each in [0, 9),
list[int]	most-significant (level-1) first.

Source code in burin/coverage/_peano.py

def digits_from_peano_position(peano: int, level: int) -> list[int]:
    """
    Convert a Peano traversal position into a list of rHEALPix child digits.

    Inverse of `peano_position_from_digits`.

    Args:
        peano: Peano position, must satisfy `0 <= peano < 9**level`.
        level: tree depth.

    Returns:
        List of `level` rHEALPix child digits, each in `[0, 9)`,
        most-significant (level-1) first.
    """
    if level < 0:
        raise ValueError(f"level must be non-negative, got {level}")
    upper = 9**level
    if not (0 <= peano < upper) and not (peano == 0 and level == 0):
        raise ValueError(f"peano position {peano} out of range [0, {upper})")

    # Walk MSB-first: at each level, peek the next base-9 digit (a Peano
    # child position), translate via current state's POS_TO_DIGIT, then
    # advance the state.
    digits: list[int] = []
    state = ROOT_STATE
    for k in range(level):
        # MSB at this depth is the (level-1-k)-th base-9 digit of `peano`
        shift = 9 ** (level - 1 - k)
        pos = (peano // shift) % 9
        digit = POS_TO_DIGIT[state][pos]
        digits.append(digit)
        state = CHILD_STATE[state][pos]
    return digits

peano_position_from_digits

peano_position_from_digits(
    digits: list[int], level: int
) -> int

Convert a sequence of rHEALPix child digits into a Peano traversal position in [0, 9**level).

digits[k] is the rHEALPix child digit (0..8 in row-major top-down order; see module docstring) chosen at depth k+1 inside the face. The most significant choice is digits[0].

The starting state at the face root is ROOT_STATE (== P). Cross-face stitching that varies the per-face starting state is deferred to sub-task M2-cross-face.

Parameters:

Name	Type	Description	Default
digits	list[int]	list of level ints, each in [0, 9), representing the rHEALPix child digit at each level of descent.	required
level	int	number of digits / tree depth. Must equal len(digits).	required

Returns:

Type	Description
int	Peano traversal position in [0, 9**level). If level == 0,
int	returns 0.

Source code in burin/coverage/_peano.py

def peano_position_from_digits(digits: list[int], level: int) -> int:
    """
    Convert a sequence of rHEALPix child digits into a Peano traversal
    position in `[0, 9**level)`.

    `digits[k]` is the rHEALPix child digit (0..8 in row-major top-down
    order; see module docstring) chosen at depth k+1 inside the face. The
    most significant choice is `digits[0]`.

    The starting state at the face root is `ROOT_STATE` (== P). Cross-face
    stitching that varies the per-face starting state is deferred to
    sub-task M2-cross-face.

    Args:
        digits: list of `level` ints, each in `[0, 9)`, representing the
            rHEALPix child digit at each level of descent.
        level: number of digits / tree depth. Must equal `len(digits)`.

    Returns:
        Peano traversal position in `[0, 9**level)`. If `level == 0`,
        returns 0.
    """
    if len(digits) != level:
        raise ValueError(f"len(digits) ({len(digits)}) != level ({level})")
    if not all(0 <= d < 9 for d in digits):
        raise ValueError(f"digit out of range [0, 9): {digits}")

    state = ROOT_STATE
    peano = 0
    for d in digits:
        pos = DIGIT_TO_POS[state][d]
        peano = peano * 9 + pos
        state = CHILD_STATE[state][pos]
    return peano

polyfill

polyfill(polygon, resolution: int) -> ndarray

Compute every cell whose centroid lies inside polygon.

Parameters

polygon A Shapely Polygon (lon/lat). Other geometries that expose the same .contains / .intersects API also work. resolution Target rHEALPix resolution in [0, 15]. Must match the resolution argument used by rhp_wrappers.polyfill.

Returns

numpy.ndarray uint64 array of spatial_id values for every cell at resolution whose ellipsoidal centroid lies inside polygon. The array is sorted in natural uint64 order, which for a fixed level is equivalent to sorting first by face index then by Peano position within the face.

Notes

The output set is bit-identical to::

suid_strings = rhp_wrappers.polyfill(polygon, resolution, plane=False)

i.e. the same set of cells the upstream centroid-in-polygon polyfill would return, just packed as spatial_id integers and sorted.

Source code in burin/coverage/_polyfill.py

def polyfill(polygon, resolution: int) -> np.ndarray:
    """Compute every cell whose centroid lies inside ``polygon``.

    Parameters
    ----------
    polygon
        A Shapely ``Polygon`` (lon/lat). Other geometries that expose
        the same ``.contains`` / ``.intersects`` API also work.
    resolution
        Target rHEALPix resolution in ``[0, 15]``. Must match the
        resolution argument used by ``rhp_wrappers.polyfill``.

    Returns
    -------
    numpy.ndarray
        ``uint64`` array of ``spatial_id`` values for every cell at
        ``resolution`` whose ellipsoidal centroid lies inside ``polygon``.
        The array is sorted in natural ``uint64`` order, which for a
        fixed ``level`` is equivalent to sorting first by face index
        then by Peano position within the face.

    Notes
    -----
    The output set is bit-identical to::

        suid_strings = rhp_wrappers.polyfill(polygon, resolution, plane=False)

    i.e. the same set of cells the upstream centroid-in-polygon polyfill
    would return, just packed as ``spatial_id`` integers and sorted.
    """
    if not (0 <= resolution <= _MAX_DEPTH):
        raise ValueError(f"resolution {resolution} out of range [0, {_MAX_DEPTH}]")

    prepared = prep(polygon)
    out: list[int] = []

    for face_letter in ("N", "O", "P", "Q", "R", "S"):
        face_idx = FACE_TO_INDEX[face_letter]
        suid = (face_letter,)
        _classify_and_recurse(
            suid,
            face_idx,
            0,  # peano_pos at level 0 is always 0
            0,  # level
            ROOT_STATE,
            resolution,
            prepared,
            polygon,
            out,
        )

    if not out:
        return np.empty(0, dtype=np.uint64)

    arr = np.fromiter(out, dtype=np.uint64, count=len(out))
    arr.sort(kind="quicksort")
    arr = np.unique(arr)
    return arr