burin.coverage: Capability Brief for an Outside Designer¶

v2.3 update (read first): the canonical fingerprint structure is now the spatial aperture-9 Merkle tree (spatial_merkle.SpatialMerkleTree), replacing the Cartesian treap described below. It is MOC-invariant, has native membership + non-membership proofs, uses a pluggable hash (fast for compute, keccak/Poseidon for transmission), and we have moved off dl-solarity byte-compat (one implementation; the follow-on slice recovers on-chain parity via our own Solidity verifier + Poseidon ZK circuit). The treap (and its dl-solarity byte-compatibility, described below) is now legacy. See CHANGELOG [2.3.0] and DECISIONS D17.

You are designing something that may overlap with this library. Read this first. The goal is not to convince you to use it, but to give you an honest picture of what exists so you can decide: depend on it, reimplement parts of it, supersede it, or integrate around it. Everything below is verifiable against the current master at tag v2.2.0.

TL;DR¶

burin.coverage is a small Python library (~4,000 lines + optional Nim acceleration) that turns a geographic polygon into a deterministic 32-byte fingerprint, and issues O(log n) cryptographic membership and non-membership proofs against that fingerprint.

Two parties computing the pipeline for the same polygon at the same resolution produce the same 32 bytes without coordinating. Anyone holding the fingerprint can verify in O(log n) whether a given rHEALPix cell is covered, without seeing the full cell set.

The fingerprint hashes with Ethereum keccak256 and matches dl-solarity/solidity-lib's on-chain CMT verifier byte-for-byte (as of v2.2.0).

The library is local/stealth and has not been published. Take it as a path dependency or as a reference; don't expect it on PyPI.

What it does (concretely)¶

                                       ┌──────────────────────────┐
   Shapely Polygon                     │       Public API         │
   (lon/lat, WGS84)                    │  fingerprint_polygon()   │
        │                              │  generate_*_proof()      │
        ▼                              │  CartesianMerkleTree     │
   ┌─────────────────┐                 │  spatial_id ↔ SUID       │
   │ polyfill at L=R │  (M4 algo,      └──────────────────────────┘
   │ → spatial_ids   │   vectorised
   │ (uint64 array)  │   on uint64)
   └────────┬────────┘
            │
            ▼
   ┌─────────────────┐
   │  canonicalize   │  Coalesce complete 9-sibling groups
   │  (stride-9      │  to their parent; cascade upward.
   │   sweep)        │  Output: sorted spatial_ids, mixed levels.
   └────────┬────────┘
            │
            ▼
   ┌─────────────────┐
   │ CartesianMerkle │  Deterministic treap (priority = keccak256(key)[:16]).
   │ Tree            │  Node hash = keccak256(pad32(key) || min(l,r) || max(l,r)).
   │ over crypto_    │  Order-independent root. ZK-friendly child sorting.
   │ bytes keys      │
   └────────┬────────┘
            │
            ▼
   ┌─────────────────┐
   │   32-byte root  │  This is the fingerprint.
   └─────────────────┘

Beyond the root, the library issues:

Membership proof for any cell in the canonical set (O(log n) bytes).
Non-membership proof for any cell not in the canonical set, using a proper BST adjacency witness (the fix that closed the v1.0 soundness bug; see DECISIONS D12).

Public API (importable from `burin.coverage`)¶

Core primitive¶

Name	Shape	Notes
`CartesianMerkleTree`	class	`add(key)`, `remove(key)`, `contains(key)`, `keys()`, `root_hash`
`MembershipProof`	dataclass	`key`, `target_left_hash`, `target_right_hash`, `aux_path`, `root_hash`; `verify()`
`NonMembershipProof`	dataclass	`key`, `left_neighbor`, `right_neighbor`, `left_proof`, `right_proof`, `root_hash`; `verify()`
`generate_membership_proof(tree, key)`	fn	`→ MembershipProof \\| None`
`generate_non_membership_proof(tree, key)`	fn	`→ NonMembershipProof \\| None`

End-to-end pipeline¶

Name	Input	Output
`fingerprint_polygon(geometry, resolution)`	Shapely Polygon, int 0–15	32-byte root
`fingerprint_polygon_hex(geometry, resolution)`	same	64-char hex
`canonical_fingerprint(suids)`	`list[SUID]`	32-byte root
`canonicalize_suids(suids)`	`list[SUID]`	canonical `list[SUID]` (mixed resolutions, sorted)
`canonicalize_keys(keys)`	`list[bytes]`	canonical `list[bytes]`

Encodings (three views of one cell)¶

Name	Bytes	Use
`SUID` tuple	`('Q', 4, 5, 3)`	human-readable rHEALPix cell ID
`crypto_bytes` (CMT key)	`[resolution][base][packed children]`	input to the CMT — hashed
`spatial_id` int64	`face(3) \\| peano(57) \\| level(4)`	in-memory fast path — stride-9 sibling adjacency

Conversions: suid_to_cmt_key, cmt_key_to_suid, suid_to_string, string_to_suid, suid_to_nuniq, nuniq_to_suid, plus (v2.1) to_spatial_id, decode_spatial, spatial_id_from_suid, suid_from_spatial_id, to_crypto_bytes, from_crypto_bytes.

Critical invariant: crypto_bytes is the hash input. spatial_id is only a representation; it carries no separate identity. Round-tripping crypto_bytes → spatial_id → crypto_bytes is bit-identical (exhaustively tested on 44,286 cells through resolution 4).

Auxiliary¶

Name	Use
`parent_key(key)`, `sibling_keys(key)`	byte-level cell-hierarchy ops
`burin.coverage.projections` (separate module)	optional Nim-accelerated rHEALPix projections (`rhealpix_forward`/`_inverse`, `healpix_forward_ellipsoid`/`_inverse_ellipsoid`); falls back to `rhealpixdggs` if no Nim build
`burin.coverage.tables` (separate module)	`NEIGHBOR_OFFSETS`, `FACE_TRANSITIONS`, `LEVEL_METRICS` — precomputed cell topology

Integration paths¶

A. Take as a path dependency (recommended for nearby Python projects)¶

# pyproject.toml of your design
[project]
dependencies = ["py-cmt @ file:///path/to/burin/coverage engine"]

Or with uv:

uv add /path/to/burin/coverage engine

Runtime dependencies pulled in: rhealpixdggs, shapely, eth-hash, numpy. Total install footprint: small. No Nim toolchain required for the default install.

B. Reimplement specific capabilities¶

If you only need the fingerprint and don't want the proof machinery, the reimplement cost is well under a day:

Just the fingerprint (canonicalize + hash a sorted byte set): ~150 lines.
CMT (treap + Merkle hashing): ~250 lines. Be careful about the priority/heap invariant and the child-sort symmetry. The child-sort symmetry is what makes the hash ZK-circuit-friendly. See burin.coverage/tree.py for the reference.
Vectorised polyfill (M4 algorithm): ~300 lines, but only worth it if you need the 15× speedup. Pure-Python rhealpixdggs.polyfill is correct and adequate for most use cases.

C. Supersede¶

You'd want to supersede if your design needs: - A different DGGS (S2, H3, HEALPix): burin.coverage is rHEALPix-bound. You'd swap the encoding and lose canonicalize's 9-sibling assumption. - A different hash (Poseidon for ZK efficiency, BLAKE3 for speed): keccak256 is hardcoded for Ethereum compatibility. A swap is a 5-line diff but breaks all on-chain compatibility. - A different proof scheme (Verkle, RSA accumulator, Sparse Merkle): CMT was chosen for ZK-circuit alignment with dl-solarity and determinism without randomness. If your verifier infrastructure is different, the primitive itself needs swapping.

D. Integrate around it¶

Build the things burin.coverage doesn't: - STAC extension spec defining how to embed the fingerprint. - ZK circuit (Circom or Noir) that verifies a MembershipProof and outputs a SNARK. - On-chain verifier (a sibling on-chain-verifier repo is already in the user's plans). - MOC-style set operations over fingerprints (union, intersection, difference). None of these exist here.

What `burin.coverage` explicitly does NOT do¶

Missing	Workaround
STAC extension definition	Embed `fingerprint_polygon_hex()` output in any STAC field; spec is TBD
ZK circuit	None included. The proof format is structured for one but no `.circom` / `.noir` ships
On-chain verifier	Lives in a sibling on-chain-verifier repo
Set operations (union/∩/∖)	Reduce to canonical form, then operate on cell sets externally
Poseidon hash variant	keccak256 only; Poseidon would be a v3.x effort
Privacy / zk-hiding	The fingerprint COMMITS to coverage. Anyone with the resolution + a candidate polygon can compute and compare
Streaming / incremental proofs	Whole-tree only; updating means re-canonicalising
H3 / S2 / HEALPix interop	rHEALPix only
`n_side ≠ 3` in the fast path	`_polyfill` raises ValueError; pure-Python path supports other `n_side` for non-fingerprint work
Planar coordinates in `fingerprint_polygon`	`plane=True` raises ValueError; lon/lat only

Decision points the outside design must know¶

1. The hash is Ethereum keccak256 (often confused with NIST SHA3-256)¶

These are NOT interchangeable. They share the Keccak-f[1600] permutation but use different sponge padding (0x01 vs 0x06) and produce different 32-byte outputs. v2.0.0 and v2.1.0 shipped with sha3_256 by accident; v2.2.0 corrected this. Any design choosing a hash that isn't keccak256 loses Ethereum/Solidity compatibility entirely.

2. Three encodings, one identity¶

A single rHEALPix cell has three Python representations: - SUID tuple is human-readable, the form rHEALPix returns - crypto_bytes is the CMT key, hashed - spatial_id int64 is the in-memory fast path

crypto_bytes is identity for CMT/hash purposes. The other two are views. Designs that store cells should pick one canonical form per storage tier and convert at boundaries.

3. Determinism is the whole product¶

burin.coverage's value is "same inputs → same 32 bytes." This requires: - Deterministic priority (keccak256(key)[:16]) - Order-independent treap structure (BST + heap invariants jointly admit one shape per key set) - Order-independent hash (children sorted before hashing, which also makes ZK circuit verification cheap) - Deterministic polyfill (centroid-in-polygon at a chosen resolution) - Deterministic canonical form (cascading 9-sibling coalescence)

If your design changes any of these, you break interoperability with every other burin.coverage user. That includes the on-chain verifier.

4. Resolution is part of the fingerprint identity¶

Two providers MUST agree on: - DGGS (WGS84_003 from rhealpixdggs) - Resolution (0–15) - Polyfill algorithm (centroid-in-polygon)

Different resolutions produce different fingerprints by design. Finer resolution captures more boundary detail. Treat resolution as a CRS-like declaration in metadata.

5. The non-membership proof had a critical bug that is now fixed¶

v1.0.0 NonMembershipProof.verify() accepted sandwich attacks (proving real members absent by flanking them with other members). v2.0.0 added a BST adjacency witness via the aux_paths. The fix is documented in DECISIONS D12 and SYNTHESIS §3.5. Do not assume v1.0.0 proof formats are forward-compatible with v2.0+ verifiers.

Performance¶

Numbers measured at v2.2.0 on a current Mac, Central Park polygon:

Resolution	Cells (approx)	v2.0 fingerprint_polygon	v2.1+ (M4 algo)	Speedup
9	~5	<1 ms	<1 ms	n/a
11	~50	~3 s (Manhattan)	~0.4 s	6.9×
13	~5,000	~53 s	~3.5 s	15.3×

The M4 algorithm replaces the 96%-of-time per-cell polyfill loop with Peano-interval bbox subdivision and stride-9 vectorised coalesce. Worth knowing if your design will fingerprint many polygons or large regions.

Optional Nim acceleration is available for projections (14–169× faster than pure Python), but requires a Nim 2.x toolchain at build time. The default install is pure-Python and never blocks.

Compatibility & versioning¶

Current tag: v2.2.0 (2026-05-something, keccak256 corrected)
Earlier tags: v2.1.0 (M4 + spatial_id, sha3-based, do not use it), v2.0.0 (cleanup + non-membership soundness fix, sha3-based, do not use it), v1.0.1 (honest snapshot with documented defects)
Breaking changes between v1 → v2 → v2.2 are documented in CHANGELOG.md. Any fingerprint, proof, or root hash from before v2.2.0 is incompatible at the byte level, even though the math was right.
Python: ≥3.11 (uses bytes | str unions and from __future__ import annotations).
License: undeclared. Project is private/stealth. A license decision must precede any distribution.

Audit posture¶

114 tests pass (including hypothesis property tests for non-membership proof soundness and a parity gate for the M4 algorithm against the v2.0 reference).
The adversarial test suite (tests/) rejects the known forgery classes, checks order-independence and determinism across shuffles, gates cross-language Poseidon parity, and exhaustively collision-checks the SUID encoding through resolution 4.
Pyright clean (core is strict). Ruff clean.

An early audit drove the v2.0 cleanup; later additions are gated by the parity tests and the test batteries.

Recommended brief-handoff message to the outside agent¶

If you're literally handing this to another agent, here's the short version:

burin.coverage v2.2.0 is a working, tested, locally-developed Python library that fingerprints rHEALPix polygons to 32 bytes and proves cell membership / non-membership against the root. Hash is Ethereum keccak256 (so it matches dl-solarity/solidity-lib). The fingerprint is order- and resolution-independent given a fixed rHEALPix grid and max polyfill resolution. Three things it does NOT provide: a STAC extension spec, a ZK circuit, on-chain code. If your design needs any of those, you build them on top of burin.coverage rather than inside it. Take it as a path dependency or copy tree.py + canonicalize.py + proofs.py + suid_encoding.py (~1,500 lines) if you want a standalone embed. The optional Nim acceleration is purely a performance win and can be ignored. See docs/SYNTHESIS.md for internal details, CHANGELOG.md for the version history, and the tests/ suite for the proof-of-correctness battery.