> For the complete documentation index, see [llms.txt](https://hub.bsvblockchain.org/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hub.bsvblockchain.org/brc/overlays/0136.md). # Block-Anchored Overlay Synchronization via Block-Aligned Sparse Merkle Trees (BASM) Siggi Oskarsson () Deggen () ## Abstract This BRC defines a lightweight, cryptographically strong synchronization layer for BSV overlay networks that provides **per-block completeness guarantees** for the subset of transactions admitted to a given topic. For every confirmed block, each overlay node deterministically constructs a **Block-Aligned Sparse Merkle Tree (BASM)** over the admitted txids drawn from that block. The BASM is "block-aligned" because its leaves preserve the canonical block order of the admitted transactions, aligning directly with the block's own Merkle structure. It is "sparse" because only the admitted subset of the block's transactions appears as leaves — a filtered, order-preserving projection of the full block. The 32-byte BASM root, together with the block hash and admitted count, forms a **Topic Block Anchor (TBA)**. A cumulative **Topic Anchor Chain (TAC)** hashes together the sequence of TBAs into a single 32-byte commitment to a topic's entire confirmed history. Two nodes serving the same topic can compare their TAC values in a single round trip to determine whether their confirmed sets agree. Where they disagree, divergent heights are identified in `O(log H)` round trips. Reconciliation then uses compound Merkle paths ([BRC-0074](/brc/transactions/0074.md)) to prove block inclusion of any missing txids before fetching the raw transaction data — avoiding the BEEF overhead of double-encoding Merkle paths already provided. This protocol sits above [BRC-0076](/brc/transactions/0076.md) (GASP), upgrading its eventual-consistency guarantees into provable-completeness guarantees once a block is mined. ## Motivation BRC-0076 (GASP) is the workhorse of overlay reconciliation today. It uses bloom filters of spendable `txid+vout` pairs and a recursive INV/request exchange to converge two parties on the same transaction graph. This works very well for pre-confirmation propagation, where there is no shared anchor against which divergence can be measured cryptographically. It has two structural limitations once transactions are mined: 1. **No per-block completeness check.** A node can never definitively say "I have every confirmed transaction matching topic *T* up to height *H*." It can only say "after some number of GASP rounds, my bloom-filter exchange found no new differences with peer *P*." Bloom filters are probabilistic, peer sets are partial, and silence is not a proof of completeness. 2. **No cheap catch-up for fresh or recovered nodes.** A node that has been offline, or that joins a topic for the first time, must walk the entire reachable graph through GASP to gain confidence in its state. There is no compact, comparable fingerprint that summarizes "everything in topic *T* through height *H*." Both problems disappear once the data is in a block. The blockchain is already the canonical, immutable order over confirmed transactions, and every node already trusts it via chain trackers. What is missing is a standardized, per-topic projection of that ordering: a deterministic root committing to exactly the transactions a topic admits in a given block, computed identically by every honest node, and exchangeable in 32 bytes per height. This BRC defines that projection — the Block-Aligned Sparse Merkle Tree — and the reconciliation protocol built on it. It does not replace BRC-0076; it sits above it. GASP continues to handle live propagation and, on demand, supplies missing raw transaction data identified by this protocol, while compound Merkle paths from [BRC-0074](/brc/transactions/0074.md) provide block-inclusion proofs without redundant BEEF encoding. ## Background and Relationship to Existing BRCs This proposal builds on, and is intended to interoperate cleanly with: * [**BRC-0022**](/brc/overlays/0022.md) — *Overlay Network Data Synchronization*. Defines how a transaction is submitted to an overlay node and how a Topic Manager decides admission. The admission predicate referenced in this BRC is exactly the one defined by the topic's BRC-0022 Topic Manager. * [**BRC-0074**](/brc/transactions/0074.md) — *BSV Unified Merkle Path (BUMP) Format*. Compound Merkle paths in BUMP format are used in this BRC to prove the block inclusion of admitted txids during reconciliation. * [**BRC-0076**](/brc/transactions/0076.md) — *Graph Aware Sync Protocol (GASP)*. The existing recursive reconciliation protocol. This BRC complements it by providing block-anchored fingerprints and relies on GASP (or an equivalent transport) to deliver missing raw transaction data. * [**BRC-0088**](/brc/overlays/0088.md) — *Overlay Services Synchronization Architecture (SHIP/SLAP)*. Used to discover peers serving a given topic. The Topic Block Anchor exchange defined here uses peers discovered via SHIP/SLAP. * **Chain Tracker** — Provides the trusted longest-chain headers against which `blockHash` values are validated. Implementations MUST use a chain tracker (for example the chain tracker interface used with Teranode P2P) rather than any specific implementation. ## Specification ### Definitions * **Topic** — a named, deterministic admission policy over BSV transactions, identified by a string `topic` (e.g. `"tm_1sat_ordinals"`). The policy is implemented by a BRC-0022 Topic Manager. * **Admission Predicate** — a pure, deterministic function `admit(topic, tx, chainState) → bool` provided by the topic's Topic Manager. Two honest nodes running the same Topic Manager version against the same chain state MUST return identical results for the same transaction. * **Block** — a confirmed Bitcoin SV block at height `H` with header hash `blockHash` and canonical, ordered transaction list `[tx_0, tx_1, …, tx_{n-1}]`, where `tx_0` is the coinbase. Order is the order the miner placed transactions in the block. * **Admitted List** for `(topic, H)` — the ordered list `A(topic, H) = [txid(tx_i) : 0 ≤ i < n, admit(topic, tx_i, …) = true]`, preserving the block's transaction order. Indices `i` are NOT renumbered. * **Block-Aligned Sparse Merkle Tree (BASM)** — a binary Merkle tree whose leaves are the elements of `A(topic, H)` in block order. The tree is "block-aligned" because the leaf ordering faithfully preserves canonical block order, aligning with the block's own Merkle structure. It is "sparse" because only the admitted subset of the block's transactions appears as leaves. * **BASM Root** `R(topic, H)` — the 32-byte root of the BASM for `(topic, H)`. * **Topic Block Anchor** `TBA(topic, H)` — the tuple `(topic, H, blockHash, R(topic, H), |A(topic, H)|)`. * **Topic Anchor Chain** `TAC(topic, H)` — a cumulative hash committing to all anchors from the topic's genesis height through `H`. ### Construction of the BASM Root Given the Admitted List `A = [txid_0, txid_1, …, txid_{k-1}]` for `(topic, H)`, the BASM Root `R` is computed as follows. All txids are taken in **internal byte order** (the byte representation used by the block's own Merkle tree, not the reversed hex display order). 1. **Empty topic at this height.** If `k = 0`, then `R = 0x00…00` (32 zero bytes). 2. **Single admitted transaction.** If `k = 1`, then `R = A[0]`. No hashing is applied. This matches Bitcoin's block-Merkle convention for single-leaf trees. 3. **Multiple admitted transactions.** If `k ≥ 2`, build a binary Merkle tree using `SHA256d` (double SHA-256) and Bitcoin's odd-leaf duplication rule: * Layer 0 is the list `A` itself, in block order. * To produce layer `L+1` from layer `L`: walk pairs `(a, b)` from left to right. If layer `L` has an odd count, the final element is paired with itself (`b = a`). For each pair, the parent node is `SHA256d(a || b)`. * Repeat until exactly one node remains. That node is `R`. This is the same construction Bitcoin uses for the block's own Merkle root, applied to the filtered, order-preserving admitted sub-list. The choice is intentional: because the BASM leaf order is a contiguous-by-construction subsequence of the block's own leaf order, an admitted txid's position in the BASM is trivially derivable from its block position, and compound BUMP paths can be used directly to prove block inclusion. ### Block-Order Preservation (Normative) Implementations MUST construct `A(topic, H)` by iterating the block's transactions in their canonical block order and appending each admitted txid in that order. Implementations MUST NOT sort, deduplicate, or otherwise reorder the list. Block order is already canonical (fixed by the miner and committed to by the block's own Merkle root); using any other order risks subtle cross-implementation disagreements. ### Edge Cases * **Coinbase.** If the coinbase transaction `tx_0` satisfies the admission predicate, it is admitted at index 0 like any other transaction. Topics that wish to exclude coinbase outputs MUST express that exclusion inside the admission predicate. * **Re-orgs.** Topic Block Anchors are tied to a specific `blockHash`, not to a height alone. After a re-org, anchors for orphaned blocks are discarded and recomputed against the new longest-chain blocks at the affected heights. The chain tracker provides the longest-chain reference. * **Duplicate-leaf attack vector.** Because BASM leaves are real txids drawn from a real block, and any honest node validates each leaf's presence in the block via standard SPV machinery, this BRC inherits the same defenses Bitcoin already applies against the CVE-2012-2459 duplicate-transaction malleation. Implementations MUST reject anchors whose `admittedCount` is inconsistent with the txids the peer produces during the reconciliation phase. ### Topic Block Anchor — Wire Format JSON encoding (canonical for cross-implementation interop): ```json { "topic": "tm_1sat_ordinals", "blockHeight": 850000, "blockHash": "00000000000000000abcdef…", "basmRoot": "8f3a12…", "admittedCount": 47 } ``` All hash fields are lowercase hex in **display (reversed) byte order**, matching the convention used elsewhere in the BSV stack (BUMP, BEEF, block explorers). Implementations MUST reverse to internal byte order before performing any hashing operation. A binary encoding is also defined for high-throughput peer-to-peer use: ``` field size notes --------------------------------------------------------- topic_len varint length of UTF-8 topic string topic topic_len UTF-8 bytes block_height uint32 little-endian block_hash 32 bytes internal byte order basm_root 32 bytes internal byte order admitted_count varint ``` ### Topic Anchor Chain (TAC) For efficient bulk comparison, each node maintains a cumulative hash over its history of Topic Block Anchors for a given topic: ``` TAC(topic, H_genesis - 1) = 0x00…00 TAC(topic, H) = SHA256d( TAC(topic, H - 1) || block_hash(H) || basm_root(topic, H) ) ``` `H_genesis` is the topic's first relevant block height (typically the height at which the Topic Manager was first deployed; topics MAY define their own genesis height). Two nodes that agree on `TAC(topic, H)` necessarily agree on every `TBA(topic, h)` for `H_genesis ≤ h ≤ H`. The 32-byte cumulative hash is therefore a single-shot completeness fingerprint for the topic's entire confirmed history. ### Reconciliation Protocol The protocol defines six messages, all of which MAY be carried over the same transport already used for BRC-0076 (GASP). 1. **`TIP_ANCHOR_REQUEST`** — Alice asks Bob: "What is your `TAC(topic, H_tip)`?" 2. **`TIP_ANCHOR_RESPONSE`** — Bob replies with `(topic, H_tip_Bob, TAC(topic, H_tip_Bob))`. 3. **`HEIGHT_RANGE_REQUEST`** — Alice asks for `TBA(topic, h)` for a range `[h_low, h_high]`. Implementations SHOULD cap range size (e.g. 1024 heights) per request. 4. **`HEIGHT_RANGE_RESPONSE`** — Bob replies with the requested `TBA` list. 5. **`ADMITTED_LIST_REQUEST`** — for any height where BASM roots disagree, Alice asks for the full ordered `A(topic, H)`. 6. **`ADMITTED_LIST_RESPONSE`** — Bob replies with the ordered txid list and the in-block index of each admitted transaction. The in-block indices allow a peer to verify each txid's claimed block position using standard SPV machinery. The reconciliation flow: 1. Alice and Bob exchange `TIP_ANCHOR`. If equal, they are fully synced through the lower of the two tips. Done. 2. If unequal, Alice binary-searches the disagreement: she requests `TBA` at the midpoint height; if it matches Bob's, she searches the upper half, otherwise the lower half. `O(log H)` round trips identify all divergent heights. * In practice, since `TAC` only diverges forward from the first disagreement, a one-sided linear scan from the known-good height forward is simpler. Implementations MAY use either strategy. 3. For each divergent height, Alice requests the `ADMITTED_LIST`. The set difference between Alice's and Bob's lists at that height identifies the exact set of missing txids. 4. For each missing txid, Alice requests a **compound Merkle path** ([BRC-0074](/brc/transactions/0074.md) BUMP format) covering those txids, proving their block inclusion. Alice validates each path against the block header obtained from her chain tracker before proceeding. 5. After verifying block inclusion, Alice requests only the **raw transaction data** for the missing transactions. Because block inclusion has already been cryptographically established via the compound Merkle path, there is no need to re-encode Merkle paths in BEEF format; raw transaction bytes suffice. 6. After processing and admitting the fetched transactions, Alice recomputes `R(topic, H)` and `TAC(topic, h)` for all affected heights and re-runs step 1 if needed. This loop is guaranteed to terminate because each round either confirms agreement at the tip or strictly increases the lowest height of confirmed agreement. ### When to Run Anchor reconciliation is intended as a **periodic and on-demand** layer, not a per-transaction one. Recommended triggers: * On node startup, against several SHIP/SLAP-discovered peers for each hosted topic. * On every new block detected via the chain tracker, after the topic processes the block (cheap: just exchange the new tip anchor). * After detecting any GASP-level discrepancy that could indicate divergent state. * On a slow background timer (e.g. every 5–15 minutes) for general anti-entropy. Live, pre-confirmation propagation continues to be handled by GASP and SHIP/SLAP topic broadcasts. ## Rationale ### Block Order vs. Sorted Order A natural alternative is to sort `A(topic, H)` lexicographically by txid before building the Merkle tree. This BRC deliberately rejects that approach: 1. **Block order is already canonical.** The miner has fixed it, every node already trusts it via the block's own Merkle root, and chain trackers provide it. A sorting step adds a second canonicalization pass that solves a problem the blockchain has already solved. 2. **No tie-breaker convention needed.** Sorted-order schemes require careful specification of hex vs. binary sort, internal vs. display byte order, etc. Each is a potential source of cross-implementation drift. Block order has none of these knobs. 3. **Direct alignment with BUMP (BRC-0074).** Because the BASM leaf order is a subsequence of the block's own Merkle tree leaf order, compound BUMP paths for admitted txids are derived directly from the block's own paths. A sorted BASM would break this alignment and require parallel proof machinery. 4. **Determinism is already implied.** For non-trivial topics, the admission predicate depends on chain state and must be evaluated in some canonical order anyway. Block order is the only chain-state-consistent order. ### Lightweight Transaction Fetch vs. BEEF After verifying compound Merkle paths from BRC-0074, the requesting node has already received cryptographic proof of block inclusion for each missing txid. Re-packaging the same Merkle paths inside a BEEF response would be redundant. This BRC therefore separates the proof step (compound BUMP) from the data step (raw transaction), reducing bandwidth and simplifying the protocol. ## Security Considerations * **Anchor authenticity.** A `basmRoot` value alone is meaningless without the corresponding `blockHash`. Implementations MUST validate `blockHash` against the longest-chain headers from a chain tracker before acting on a peer-supplied anchor. An anchor for an orphaned or fictional block hash is rejected. * **Admission predicate determinism.** The cryptographic guarantees of this protocol assume all honest peers run the same admission predicate. A topic upgrade that changes admission semantics MUST be versioned (e.g. by changing the topic name), or all peers must coordinate the upgrade at a specific block height. Otherwise honest peers will diverge and the protocol will (correctly) report divergence forever. * **No defense against censorship by all peers.** If every peer a node can reach omits the same admitted transaction, the node has no way to detect this from anchors alone. Diverse peer discovery (SHIP/SLAP across multiple advertisement sources) remains the primary defense. * **DoS surface.** `ADMITTED_LIST_REQUEST` for blocks with very large admitted counts is the most expensive operation. Implementations SHOULD rate-limit per-peer, cache `A(topic, H)` lists, and prefer streaming or paginated responses for large lists. * **Re-org handling.** On re-org, all anchors at and above the fork height MUST be invalidated and recomputed from the new longest-chain blocks. `TAC` values from the orphaned chain MUST NOT be retained. * **Compound Merkle path verification.** Implementations MUST verify every compound BUMP path against the block header before admitting transactions fetched via this protocol, even when the block header itself has been validated by a chain tracker. ## Implementation Notes * For the reference Overlay Services Engine and `@bsv/overlay-express`, the natural integration point is the existing `chainTracker.on('block')` hook. After admission processing for a block completes, compute `R(topic, H)`, persist the `TBA`, and update `TAC`. Total per-block overhead is `O(k)` hashing work where `k` is the admitted count, plus one persisted record. * `TAC` allows `O(1)` peer comparison at the tip and `O(log H)` divergence localization. Storing per-height `TBA` records is `O(H)` in space, dominated by the 32-byte root. For a topic active across one million blocks this is approximately 32 MB — negligible. * Implementations MAY publish their current `(topic, H_tip, TAC)` periodically as a SHIP-style on-chain advertisement, providing a public, tamper-evident attestation of the node's claimed topic state. This is OPTIONAL and orthogonal to this BRC. * Implementations MAY commit `TAC(topic, H)` values on-chain (e.g. as PushDrop tokens) as part of a "Proof-of-Indexing" pattern; this is also OPTIONAL and orthogonal. ## Reference Pseudocode ```ts function basmRoot(admittedTxids: Bytes32[]): Bytes32 { if (admittedTxids.length === 0) return ZERO_32 if (admittedTxids.length === 1) return admittedTxids[0] let layer = admittedTxids.slice() // already in block order while (layer.length > 1) { const next: Bytes32[] = [] for (let i = 0; i < layer.length; i += 2) { const left = layer[i] const right = i + 1 < layer.length ? layer[i + 1] : layer[i] next.push(sha256d(concat(left, right))) } layer = next } return layer[0] } function buildAdmittedList( topic: string, block: Block, chainState: ChainState ): Bytes32[] { const out: Bytes32[] = [] for (const tx of block.transactionsInBlockOrder) { if (admit(topic, tx, chainState)) out.push(tx.txid) } return out } function tba(topic: string, block: Block, chainState: ChainState): TBA { const A = buildAdmittedList(topic, block, chainState) return { topic, blockHeight: block.height, blockHash: block.hash, basmRoot: basmRoot(A), admittedCount: A.length, } } function updateTac(prev: Bytes32, blockHash: Bytes32, root: Bytes32): Bytes32 { return sha256d(concat(prev, blockHash, root)) } ``` ## Open Questions for Future BRCs * **Topic BUMP.** A combined Merkle path proving simultaneous inclusion in the block tree and the BASM subtree, leveraging the shared leaf-order structure. Because BASM leaves are a block-order subsequence, such a path is a natural extension of the existing BUMP format. * **On-chain anchor commitments.** Standardizing the format of optional on-chain `TAC` attestations for verifiable, public topic-state claims. * **Multi-topic anchor bundling.** A node hosting many topics may want to compress per-block per-topic anchors into a single per-block multi-topic root, useful for "audit my whole node" workflows. * **Streaming `ADMITTED_LIST` formats.** For very large topics, a chunked or compressed wire format for `A(topic, H)`. ## References * [BRC-0022](/brc/overlays/0022.md) — Overlay Network Data Synchronization (Topic-Based Submission) * [BRC-0074](/brc/transactions/0074.md) — BSV Unified Merkle Path (BUMP) Format * [BRC-0076](/brc/transactions/0076.md) — Graph Aware Sync Protocol (GASP) * [BRC-0088](/brc/overlays/0088.md) — Overlay Services Synchronization Architecture (SHIP/SLAP) * [BRC-0101](/brc/overlays/0101.md) — Diverse Facilitators and URL Protocols for SHIP and SLAP Overlay Advertisements * CVE-2012-2459 — Bitcoin Merkle tree duplicate-leaf vulnerability --- # Agent Instructions This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com. ## Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://hub.bsvblockchain.org/brc/overlays/0136.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.