Skip to content

[HARDEN-0805] Subtree-root SPV proofs are still unverifiable: no BUMP leaf node, and a block path over placeholder subtree roots #1500

Description

@freemans13

What happens

The asset server's GET /merkle_proof/{hash} falls back to a subtree proof when the
queried hash turns out to be a subtree root rather than a transaction
(services/asset/httpimpl/GetMerkleProof.go). That proof is built by
ConstructSubtreeMerkleProof and converted to BUMP by bump.ConvertToBUMP. The BUMP it
produces cannot be verified by any BRC-74 client, for two independent reasons.

PR #1482 fixed the offsets on this path — they were previously derived from a -1
sentinel folded to 0xFFFFFFFF, so every level carried garbage. The offsets are correct
now. The proof is still unusable, and this issue covers what is left.

1. There is no leaf node to start from

ConstructSubtreeMerkleProof sets TxID: chainhash.Hash{} (util/merkleproof/merkle_proof.go:459,
commented "Empty for subtree proofs"). ConvertToBUMP only emits the level-0 leaf node —
the BRC-74 flag-0x02 entry naming the thing being proven — when proof.TxID is
non-zero (util/bump/format.go:159). So the subtree-proof BUMP has siblings at every
level and nothing to fold them against.

Confirmed end to end against the go-bc reference implementation: build the exact
structure ConstructSubtreeMerkleProof returns (zero TxID, TxIndexInSubtree: -1,
SubtreeIndex: 3, two block-proof levels), run it through ConvertToBUMP
EncodeBinarybc.NewBUMPFromBytesCalculateRootGivenTxid. The offsets come out
2 and 0, which are correct, and go-bc then fails with:

the BUMP does not contain the txid: 0100...00aa

The obvious fix is to populate the leaf from proof.SubtreeRoot, which
ConstructSubtreeMerkleProof already sets. That needs a decision first — see the open
question below.

2. The block path is built over placeholder subtree roots

ConstructSubtreeMerkleProof calls GenerateBlockMerkleProof(block.Subtrees, subtreeIdx)
on the raw stored subtree roots (util/merkleproof/merkle_proof.go:439). Subtree 0's
stored root is computed with the coinbase placeholder in slot 0, not the real coinbase
txid. Reconciling to the block header's merkle root requires substituting the real
coinbase and recomputing subtree 0's root — which ConstructMerkleProof does
(merkle_proof.go:188-193) and this function does not.

So even once a leaf node exists, the fold will not reach the header's merkle root for any
block whose proof path includes subtree 0's root — which is essentially all of them, since
subtree 0's root is a sibling somewhere on nearly every path. This is the same defect
class already documented in util/bump/production_repro_test.go.

Why it matters

This is a silent-wrong-answer failure, not a crash. The endpoint returns HTTP 200 with a
well-formed BUMP; the failure only surfaces inside whichever third-party SPV client tries
to verify it. Nothing on the node notices.

Severity is bounded by how much this path is used — it is a fallback for subtree-root
queries, not the transaction path, which is correct and covered by
coinbase_placeholder_crosscheck_test.go.

Open question before fixing

BRC-74 defines BUMP leaves as transaction IDs. A subtree root is not a txid, so a "BUMP
proving a subtree root" is arguably not a valid BUMP at all, and a client that accepted
one would be treating an interior node as a leaf. Three options:

  1. Populate the leaf from SubtreeRoot and fix the placeholder substitution, accepting
    that the result is a BRC-74-shaped proof of a non-txid leaf.
  2. Stop serving BUMP for subtree-root queries and return a different representation, or a
    clear error, rather than a proof no client can check.
  3. Expand the subtree proof into a real transaction-level proof.

Option 2 is the most defensible if nothing currently consumes this path; option 1 is the
smallest change. Worth confirming who actually calls it before picking.

Repro

Add to util/bump/:

proof := &merkleproof.MerkleProof{
    TxID:             chainhash.Hash{},   // as ConstructSubtreeMerkleProof sets it
    BlockHeight:      800000,
    SubtreeIndex:     3,
    TxIndexInSubtree: -1,                 // subtree-proof sentinel
    SubtreeRoot:      subtreeRoot,
    SubtreeProof:     []chainhash.Hash{},
    BlockProof:       []chainhash.Hash{sib, sib2},
}
b, _ := bump.ConvertToBUMP(proof)
bin, _ := b.EncodeBinary()
parsed, _ := bc.NewBUMPFromBytes(bin)
_, err := parsed.CalculateRootGivenTxid(subtreeRoot.String())
// err: the BUMP does not contain the txid

Found while reviewing #1482.

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

Labels

Type

No type

Projects

No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions