Add internal SPK filtering to SyncRequestBuilder for efficient mempool eviction handling

[notmandatory]

Describe the enhancement

Wallets that create many RBF transactions face a scalability issue when trying to efficiently do SPK syncing because the SyncRequestBuilder includes all revealed internal SPKs in the request, even if the transactions that "use" (create or spend outputs for these SPKs) have been replaced and evicted from the mempool.

New functions are needed to only sync histories for internal SPKs used in canonical transactions that have less than X (default 6) confirmations. In this case an efficient sync request would only include: (revealed external SPKs) U (internal "unused" SPKs), where "unused" means a revealed internal SPK that either (1) has no relevant canonical TXs (either in/out) or (2) has any relevant canonical "unconfirmed" TXs (either in/out). The number of confirmations required for a TX to be "confirmed" should be configurable but default to 6.

Use case

A wallet with 3 revealed external spks and 5 UTXOs, but 100s of revealed internal SPKs should only request SPK histories for 8 SPKs.

Additional context

Discord discussion with @phlip9:

Philip (@phlip9 - lexe.app) — Yesterday at 20:59
Hey I'm looking at the esplora sync for unconfirmed txs and UTXOs. Right now it doesn't handle e.g. an unconfirmed tx getting replaced or dropped from the mempool. See: https://github.com/bitcoindevkit/bdk/blob/master/crates/esplora/src/async_ext.rs#L444

It would make sense to me that we just mark the txid's as evicted if the tx_info returned from esplora is None, i.e.:

for (txid, tx_info) in handles.try_collect::<Vec<_>>().await? {
if let Some(tx_info) = tx_info {
if inserted_txs.insert(txid) {
update.txs.push(tx_info.to_tx().into());
}
insert_anchor_or_seen_at_from_status(&mut update, start_time, txid, tx_info.status);
insert_prevouts(&mut update, tx_info.vin);
} else {
update.evicted_ats.insert((txid, start_time));
}
}

Is there some edge case / use case that this doesn't support? Or would something like the spks_with_expected_txids be required in general? For us at least expected_txids would always (?) be the same as the txids we're syncing.
June 18, 2025

Steve Myers — 09:59
@philip (@phlip9 - lexe.app) which version of BDK are you using? There was a fix in bdk_wallet 2.0 to handle mempool evicted UTXOs getting properly handled in the BDK tx graph, see bdk#1839 (edited)
[10:05]
If you use the BDK provided sqlite persistence you shouldn't see any API changes going from 1.x to 2.0, but if you have your own custom persistence you need to update it to save/load the new fields added to support mempool eviction.

Philip (@phlip9 - lexe.app) — 13:53
yeah we're on BDK 2.0. the difference is that I want our LSP wallet sync to be O(revealed_external_spks + unused_internal_spks + unconf_txs + UTXOs) and not O(revealed_external_spks + revealed_internal_spks). Ideally our incremental sync set doesn't grow significantly over time. Right now it's roughly this:

SyncRequest::builder()
.chain_tip(chain_tip)
.expected_spk_txids(list_expected_spk_txids)
.spks_with_indexes(revealed_external_spks)
.spks_with_indexes(unused_internal_spks)
.outpoints(utxos)
.txids(canonical_unconfirmed_txids)
.build()

So the problem we're hitting is that an internal spk tx makes it to the mempool but then gets dropped/replaced. The internal spk isn't considered unused, so the eviction logic never triggers for that spk. The tx is in utxos and/or canonical_unconfirmed_txids, but those syncers don't mark the tx evicted if the upstream esplora doesn't know about it.

Does this make sense? Are we just holding this wrong? I'm really hoping we don't have to sync an ever growing set of all internal spks ever revealed
[13:55]
@Steve Myers forgot to cc : )
[13:56]
maybe to make this more concrete, we have like 3 revealed external spks and 5 UTXOs, but 100s of revealed internal spks

Steve Myers — 14:00
Could you make an issue for this on the bdk repo and I'll discuss with the team. This could be a case where we need new options for the SyncRequestBuilder to make what you want to do easier.

Philip (@phlip9 - lexe.app) — 14:02
btw here is some more context on our issue: #263
[14:04]
we updated to BDK 2.0, but that sadly didn't fix this issue since we're only syncing unused_internal_spks and not all revealed_internal_spks

Steve Myers — 14:06
ah OK the current plan for managing unbroadcast Tx is in #257 which is draft but should be ready to review , we'd love feedback from your project to see if addresses what you need
[14:07]
it's currently a breaking change since we want to persist the list of unboardcast tx, but could make a version with the logic but not the persistence that could be released sooner and would still be useful

Philip (@phlip9 - lexe.app) — 14:09
i'm not sure the BroadcastQueue helps, since the tx in question was broadcast successfully, it was just RBF'd by our counterparty later. the issue is that we're not detecting the original tx getting replaced, which would transition the internal spk back to unused (which would pick up the RBF tx)
[14:10]
or maybe what we need is something like "all revealed internal spks that don't yet have a canonical confirmed tx with at least 6 confs"
[14:11]
since the spk sync would "automatically " pick up any replacements

Steve Myers — 14:13
then it does sound like more customization of the sync request is possibly what you need. It is possible to manually filter UTXOs by how many confirmations they have, but then it sounds like you want to get the SPKs for just these UTXOs to put in your sync request

1
[14:16]
so instead of all the used SPKs just the ones with less than 6 confirmations right? (edited)

Philip (@phlip9 - lexe.app) — 14:17
right, I think it would be all (revealed external SPKs) U (unused internal SPKs) U (used internal SPKs with less than 6 confs) (edited)
[14:18]
or whatever your conf safety threshold is

Steve Myers — 14:18
got it, still sounds like something new functions on the sync builder could do
[14:20]
also by all unused you mean external and internal right?

Philip (@phlip9 - lexe.app) — 14:21
i think we still need all revealed external spks
[14:21]
since we can't guarantee much about them
[14:22]
edited above to clarify internal only

Steve Myers — 15:18
onemore clarification, in above when you say "used" or "unused" do you mean spent (ie. used as an input) in a TX?
Philip (@phlip9 - lexe.app) — 15:33
maybe it's more accurate to say: a revealed internal spk that either (1) has no relevant canonical txs (either in/out) or (2) has any relevant canonical unconfirmed or <=6 confs txs (either in/out).
I think that should cover it?

[phlip9]

@notmandatory Here's roughly an implementation of this incremental sync strategy that I'm testing.

/// Build an incremental sync request to efficiently sync our local BDK
/// wallet state with a remote esplora REST API blockchain data source.
///
/// Our sync request is a collection of spks (script pubkeys) we want to
/// query for relevant chain+mempool transaction updates.
///
/// This incremental sync tries to be efficient in that our sync request
/// fetches `O(revealed external spks + pending internal spks)` spk
/// histories. This is in contrast to the default BDK spk sync, which
/// fetches `O(revealed external spks + revealed internal spks)` spk
/// histories. For our LSP, we have a large (# users), ever-growing set
/// of revealed internal spks, vs a relatively small (# UTXOs) set of
/// pending internal spks.
///
/// The main idea is that in the happy path, spks from our `Internal` keychain
/// only ever recv once and spend once, so if a used internal spk has only one
/// recv and one (sufficiently confirmed) spend, we can skip syncing it.
///
/// The actual sync request built here is a little more conservative, in
/// that we want to handle various edge cases such as reorgs, replaced txs,
/// race-y accidental re-use, etc. So we will skip syncing an internal spk
/// if the txs in and txs out are all balanced and finalized (or there are
/// no txs out).
///
/// OTOH we can't guarantee much about external keychain spks, so we have to
/// sync every revealed external spk in perpetuity. In the future, we may
/// optimize this so that ancient external spks are synced less frequently.
fn build_sync_request_at(
    wallet: &Wallet,
    synced_at_secs: u64,
) -> SyncRequest<(KeychainKind, u32)> {
    let keychains = wallet.spk_index();
    let tx_graph = wallet.tx_graph();
    let local_chain = wallet.local_chain();
    let chain_tip = local_chain.tip();

    enum SpkInfo {
        External {
            spk: bitcoin::ScriptBuf,
        },
        Internal {
            spk: bitcoin::ScriptBuf,
            num_in: u32,
            num_finalized_out: u32,
        },
    }

    // Collect info about spks relevant to canonical txs, which we'll later
    // use to determine which spks to sync.
    let mut spk_infos = HashMap::<(KeychainKind, u32), SpkInfo>::new();

    // All txids relevant to each spk we want to sync. Ok to reference spks
    // that we don't actually sync.
    let mut expected_spk_txids =
        HashSet::<(bitcoin::ScriptBuf, bitcoin::Txid)>::new();

    // All confirmed or unconfirmed txs deemed to be part of the canonical
    // history.
    let canonical_tx_iter = tx_graph.list_canonical_txs(
        local_chain,
        chain_tip.block_id(),
        CanonicalizationParams::default(),
    );
    for c_tx in canonical_tx_iter {
        let tx = &c_tx.tx_node.tx;
        let txid = c_tx.tx_node.txid;

        // We'll consider a tx finalized if it has enough confs.
        let conf_height =
            c_tx.chain_position.confirmation_height_upper_bound();
        let is_finalized = match conf_height {
            Some(height) => {
                let confs = chain_tip.height().saturating_sub(height) + 1;
                confs >= ANTI_REORG_DELAY
            }
            // unconfirmed => not finalized
            None => false,
        };

        // The relevant spks for this tx, i.e., spks the tx spends or
        // receives funds to. Both internal and external spks.
        let relevant_spks = keychains.inner().relevant_spks_of_tx(tx);

        for ((keychain_kind, index), spk) in relevant_spks {
            let keychain_index = (keychain_kind, index);
            let entry =
                spk_infos.entry(keychain_index).or_insert_with(|| {
                    let spk = spk.clone();
                    if keychain_kind == KeychainKind::External {
                        SpkInfo::External { spk }
                    } else {
                        SpkInfo::Internal {
                            spk,
                            num_in: 0,
                            num_finalized_out: 0,
                        }
                    }
                });

            if let SpkInfo::Internal {
                spk: _,
                num_in,
                num_finalized_out,
            } = entry
            {
                let tx_num_in = tx
                    .output
                    .iter()
                    .filter(|output| output.script_pubkey == spk)
                    .count();

                let tx_num_finalized_out = if is_finalized {
                    tx.input
                        .iter()
                        .filter_map(|input| {
                            keychains.txout(input.previous_output).filter(
                                |(tx_keychain_index, _output)| {
                                    *tx_keychain_index == keychain_index
                                },
                            )
                        })
                        .count()
                } else {
                    0
                };

                *num_in += tx_num_in as u32;
                *num_finalized_out += tx_num_finalized_out as u32;
            }

            // It's OK that this may include more (spk, txid)'s than we
            // actually sync since BDK will just not look at spks that
            // aren't synced.
            expected_spk_txids.insert((spk, c_tx.tx_node.txid));
        }
    }

    let used_spks_to_sync =
        spk_infos
            .into_iter()
            .filter_map(|(keychain_index, spk_info)| {
                match spk_info {
                    // Sync all used external spks
                    SpkInfo::External { spk } => Some((keychain_index, spk)),
                    // Sync all used internal spks that have pending spends
                    // or have no finalized spends at all.
                    SpkInfo::Internal {
                        spk,
                        num_in,
                        num_finalized_out,
                    } if num_in > num_finalized_out || num_finalized_out == 0 =>
                        Some((keychain_index, spk)),
                    _ => None,
                }
            });

    SyncRequest::builder_at(synced_at_secs)
        .chain_tip(chain_tip)
        // We always sync revealed but unused spks, regardless of internal
        // vs external.
        .spks_with_indexes(keychains.unused_spks())
        // Also sync (1) all used external spks, and (2) used but pending
        // internal spks.
        .spks_with_indexes(used_spks_to_sync)
        // All relevant txids for the spks we want to sync, so BDK can
        // determine if a tx was evicted.
        .expected_spk_txids(expected_spk_txids)
        .build()
}

[ValuedMammal]

the tx in question was broadcast successfully, it was just RBF'd by our counterparty later. the issue is that we're not detecting the original tx getting replaced, which would transition the internal spk back to unused (which would pick up the RBF tx)

It might sound obvious but are you applying the unconfirmed tx to the wallet after broadcasting? This would be necessary to ensure that it is returned in the list of canonical txs and similarly in the result of list_expected_spk_txids.

I'm not sure we can rely on the SPK being "transitioned back to unused", since it was in fact used in a relevant tx. From the snippet it's a little difficult to follow the num_in / num_out logic, but I understand the intention of "used but pending internal spks" as opposed to every revealed internal spk.