Skip to content

burin.coverage: Architecture, Theory, and Security

Single living reference for the equal-area coverage engine.

History. burin.coverage began as a flat Cartesian Merkle Tree (a keccak-priority treap, tree.py/proofs.py). That structure was removed at the v3.0.0 cutover; the canonical structure is the aperture-9 rHEALPix SpatialMerkleTree (Poseidon over BN254), which is MOC-invariant and carries clean membership / non-membership proofs with no adjacency witness. CHANGELOG.md records the transition. This document describes the current engine.

§1 What this library is

burin.coverage is the equal-area coverage engine: an aperture-9 rHEALPix SpatialMerkleTree with a canonical Poseidon (BN254) commitment, specialized for rHEALPix DGGS cell sets. The product is a deterministic 32-byte spatial fingerprint pipeline:

Shapely polygon
    → polyfill(resolution)                 (rHEALPix cells covering the polygon)
    → canonicalize_suids                   (coalesce complete 9-sibling groups, cascade)
    → SpatialMerkleTree.from_suids         (aperture-9 Poseidon tree; MOC-invariant root)
    → 32 bytes

Two independent parties computing the pipeline for the same polygon at the same resolution produce the same 32 bytes, down to the last bit. Beyond the fingerprint, the library offers O(log n) membership and non-membership coverage proofs against the root, temporal and space-time coverage trees over the same topology, and a value-bearing variant.

§2 Architecture (load-bearing modules)

burin.coverage/
├── __init__.py          # public API surface
├── poseidon.py          # canonical Poseidon over BN254 + the dual EMPTY/FULL ladders
├── spatial_merkle.py    # SpatialMerkleTree (aperture-9, n_base-6) + CoverageProof
├── coverage_tree.py     # HierarchicalCoverageTree(aperture, n_base) — space AND time
├── st_coverage.py       # nested space-time coverage (spatial leaf = temporal sub-root)
├── value_coverage.py    # value-bearing coverage (leaf carries an opaque value)
├── fraud.py             # signed attestations + the 3 fraud classes (accountability)
├── allen.py             # Allen interval algebra (authenticated temporal relations)
├── suid_encoding.py     # resolution-first byte + field encoding for rHEALPix SUIDs
├── canonicalize.py      # coalescence + fingerprint_polygon pipeline
├── spatial.py           # int64 spatial-id encoding / crypto-bytes
├── tables.py            # precomputed neighbour / face-transition tables
└── _polyfill / _peano / _coalesce   # numpy int64 fast paths (public: polyfill, coalesce_ids, …)

HierarchicalCoverageTree(9, 6) is bit-identical to SpatialMerkleTree; the same class at (2, 1) is the dyadic temporal coverage tree. st_coverage and value_coverage reuse the same Poseidon topology with different leaf payloads.

§3 Theory

3.1 The SpatialMerkleTree

A sparse aperture-9 Merkle tree over the rHEALPix cell hierarchy. A cell's SUID is its path: ('Q', 4, 5, 3) is literally root → base Q → child 4 → child 5 → child 3. A node is one of three things:

node := None (EMPTY subtree) | FULL (fully-covered subtree) | dict[int, node] (partial)

Hashing (Poseidon mode, the canonical default). Domain separation is by arity plus two reserved leaf constants:

EMPTY[0] = 0,   FULL[0] = 1                       (0 and 1 are outside Poseidon's image
EMPTY[d] = Poseidon9( [EMPTY[d-1]] × 9 )           except by a negligible preimage, so a
FULL[d]  = Poseidon9( [FULL[d-1]]  × 9 )           leaf can equal neither by accident)
internal(children) = Poseidon9(child hashes)       (arity-9 internal node)
root(bases)        = Poseidon6(6 base subtree hashes)   (N, O, P, Q, R, S)

These are the dual default-hash ladders: EMPTY[·] carries sparsity / non-membership, FULL[·] carries roll-up. A keccak/blake mode (tag-and-concatenate) is also accepted for compute-only trees; the commitment path is Poseidon so it equals the ZK circuit's root by construction (parity-gated by zk/vectors.json).

MOC-invariance / roll-up (T2.4). Because a fully-covered region hashes to FULL[d] regardless of how finely it is spelled out, a rolled-up region (one canonical cell) and its full 9ᵏ expansion (every descendant present) produce the identical root. So a whole continent and a single field each cost one 32-byte mark, and the mark reveals nothing about how finely you counted. Heterogeneous coverage does not collapse — a partial dict node hashes differently from FULL[d].

3.2 Determinism

Claim. For any finite set S of rHEALPix cells, the root hash is a pure function of the coverage S denotes — independent of insertion order and of how the region is tiled (roll-up-independent).

Why. There are no priorities, no randomness, no insertion-order state: add places each cell on its SUID path and marks the subtree FULL, and the node representation is canonicalized (nine FULL children collapse to one FULL node). Two tilings of the same ground reduce to the same sparse None | FULL | dict structure and hence the same root. Verified empirically by order-independence sweeps (tests/coverage/test_analysis_team_review.py) and cross-language Poseidon parity against circomlibjs (tests/test_parity.py).

3.3 Canonicalization

The rHEALPix property that a parent cell is exactly the union of its N_side² children means a cell set has many equivalent representations; the canonical form is the coarsest.

Rule. If all N_side² children of a parent are present, replace them with the parent; cascade upward. canonicalize_suids (and the int64 fast path coalesce_ids) scan fine-to-coarse once — because SUIDs are resolution-first encoded, siblings are contiguous in sorted order, so complete-group detection is a linear scan. In the fingerprint pipeline this is largely a performance step: the tree's roll-up already makes the root tiling-independent, so canonicalization and the tree agree on the same 32 bytes.

3.4 Membership proofs

Prove a cell is covered with O(log n) size and verification. A CoverageProof (present=True) carries:

  • base_idx, children: the claimed cell (base 0..5 and the digit path)
  • root_sibs: the 5 sibling base-subtree hashes
  • internal_sibs: root→leaf, one (child_pos, 8 sibling hashes) per level
  • aperture, n_base: so verification is fully stateless

The verifier seeds the leaf as FULL[max_depth − len(children)], splices it into each level using the recorded sibling hashes at the recorded positions, hashes up to the 6-base root, and checks equality. The child index at each level must equal the corresponding entry of children (bound as of v3.0.0) — without it a genuine proof for one cell could be relabelled as a sibling. Verified by the forgery / path-binding battery in tests/coverage/test_proof_path_binding.py.

3.5 Non-membership proofs

Prove a cell is not covered, also O(log n). This is where the coverage tree is cleaner than the old treap: a non-membership proof is just a membership proof with present=False, seeding the leaf as EMPTY[max_depth − len(children)] instead of FULL[·]. There is no predecessor/successor witness and no adjacency argument — an absent subtree hashes to the EMPTY ladder, and recomputing the root from that empty leaf either matches (the cell really is absent) or does not (it is covered). The generator returns None for a cell that is covered or only partially covered, so the trichotomy a verifier faces is FULL / EMPTY / partial. The temporal and value variants (st_coverage, value_coverage) carry the same structure with their leaf payloads.

3.6 SUID encoding

rHEALPix SUIDs are tuples (base_cell, c₀, …, c_{r-1}) with base_cell ∈ {N,O,P,Q,R,S} and cᵢ ∈ {0,…,N_side²−1}. Two encodings:

  • Resolution-first bytes (suid_to_bytes): [resolution][base index][packed children, 4 bits each]. Bijective (exhaustively verified through resolution 4 — 44,286 SUIDs, zero collisions, exhaustively through resolution 4); parents sort before children; siblings contiguous (enables linear-scan canonicalization).
  • Field element (suid_to_field): the injective NUNIQ integer, used to bind a cell into the Poseidon composite so the whole commitment path stays keccak-free.

3.7 Security model (what we claim, what we don't)

We claim: - Determinism of the root under the coverage set S (order- and tiling-independent). - Soundness of membership / non-membership verification against the adversarial test batteries (tests/coverage/test_proof_path_binding.py, test_proofs_*, and the tamper cases throughout). - Collision resistance of the root reduces to Poseidon collision resistance on BN254. - Cross-implementation parity: the Python root equals the circomlibjs root and the in-circuit circom root, gated by zk/vectors.json.

We do not claim: - Zero-knowledge from the tree itself. These are non-interactive Merkle proofs over a hash; the ZK selective-disclosure layer lives in zk/ (real PLONK, Poseidon). - Non-equivocation across roots. An adversary who controls the root can present two trees; pin the root externally, or use the signed append-only attestation + fraud proofs in fraud.py. - Useful privacy from the fingerprint alone. It is a commitment; privacy comes from the DGGS zoom level (disclose "within region R") and the ZK layer.

§4 Decisions

  • SpatialMerkleTree over the Cartesian treap. The coverage tree is MOC-invariant (a rolled-up region and its expansion hash identically), gives native non-membership from the EMPTY ladder with no adjacency witness, and its subtree hashes are spatial-region content addresses. The treap had none of these and was removed at v3.0.0.
  • Poseidon over BN254 on the commitment path. Makes the coverage root equal to the ZK circuit's root by construction, so a proof about the root is a proof about the fingerprint. keccak survives only as the seal's transport composite and the 24-word checksum; a keccak/blake mode remains for compute-only trees.
  • Resolution-first SUID encoding: parents sort before children and siblings are contiguous, enabling linear-scan canonicalization.
  • One tree, any aperture (HierarchicalCoverageTree): space (9, 6), time (2, 1), and the nested space-time mesh all reuse the same structure and proofs.

§5 Tests and audit artifacts

  • tests/coverage/test_spatial_merkle.py — MOC-invariance, tamper rejection, cross-hash checks.
  • tests/coverage/test_coverage_tree.py — bit-identity of HierarchicalCoverageTree(9,6) and SpatialMerkleTree; temporal path adapter.
  • tests/coverage/test_proof_path_binding.py — the v3.0.0 path-binding fix (relabel rejected; honest witness unframable; real coverage-shrink still caught).
  • tests/coverage/test_canonicalize.py, test_boundary.py, test_polyfill_antimeridian.py — coalescence, cross-face polyfill, and the +180 antimeridian bbox fix vs the rhp_wrappers oracle.
  • tests/coverage/test_st_coverage.py, test_value_coverage.py, test_fraud.py, test_allen.py — the space-time, value, accountability, and interval layers.
  • tests/test_parity.py — cross-language Poseidon parity: the Python root equals the circomlibjs root, anchored to published circomlib vectors and zk/vectors.json.

§6 Potential extensions (not implemented)

Conceivable uses of the primitive; none are implemented here, and listing them implies nothing about plans.

  • STAC egress deduplication (publish the fingerprint in catalog metadata for pre-download compare).
  • On-chain coverage commitments using the root as a Solidity-verifiable value (would want the Poseidon root + a Poseidon verifier, not the removed keccak treap).
  • MOC-like set operations (union / intersection / difference) with per-operation soundness analysis.

Claims about any of the above should reference code that implements them, not this list.