Undetected double-spent

[ErikDeSmedt]

Describe the bug

1. Alice has an empty wallet
2. Alice receives a transaction (called tx1a) from Bob and observes it in the mempool.
3. Bob double-spends tx1a creating tx1b
4. A block is mined containing tx1b
5. Alice observes tx1b in a block.

Alice will still consider tx1a as a pending transaction.

To Reproduce
See this https://github.com/ErikDeSmedt/bdk-gists/blob/master/tests/wallet.rs

Expected behavior

I would expect that Alice her wallet wouldn't use tx1a anymore. The output

• should not be used for coin-selection
• should not be part of the balance (untrusted_pending)

Build environment

• BDK tag/commit: 1.0.0-beta.5
• OS+version: debian
• Rust/Cargo version: cargo 1.79.0 (ffa9cf99a 2024-06-03)

Additional context

I discovered this bug in a test-case where the entire wallet was unusable.

[ValuedMammal]

tx1b is not discovered on the second sync because it's not "relevant" to alice's wallet, so you'd have to manually insert it similar to tx1a for it to be seen as conflicting (I wonder if this situation is alleviated by using compact block filters).

[ErikDeSmedt]

I've edited the script and applied tx1b manually.

Using wallet.apply_unconfirmed_transaction([tx1b, 101)] doesn't change the state of the wallet. The apply_unconfirmed_transaction also considers tx1b as not "relevant".

Is there any method to remove tx1b from the wallet?

PS: This is related to bitcoindevkit/bdk_wallet#41. I tried to explicitly cancel the transaction as a work-around

[ValuedMammal]

Thanks for sharing the example code. You're right that apply_unconfirmed_txs won't work in the case of tx1b. I think the way to do this currently is to apply an update to alice's wallet containing tx1b with a later timestamp.

    // We also add tx1b to the wallet
    let tx_update = TxUpdate {
        txs: vec![std::sync::Arc::new(tx1b.clone())],
        ..Default::default()
    };
    let update = bdk_wallet::Update {
        tx_update,
        ..Default::default()
    };
    let _ = alice.apply_update_at(update, Some(101)).unwrap();
    
    println!("After applying tx1b");
    println!("- alice.list_unspent(): {:?}", alice.list_unspent().map(|o| o.outpoint).collect::<Vec<_>>());
    println!("- alice.list_transaction(): {:?}", alice.transactions().map(|t| t.tx_node.txid).collect::<Vec<_>>());
    println!("- alice.list_transaction(): {:?}", alice.transactions().map(|t| t.chain_position).collect::<Vec<_>>());
    println!("- alice.balance: {:?}", alice.balance());

    // I expect list_unspent to be empty.
    // (tx1a) was double-spent
    assert_eq!(alice.list_unspent().collect::<Vec<_>>(), vec![]);
    assert_eq!(alice.transactions().collect::<Vec<_>>().len(), 1);
    let tx = alice.transactions().next().unwrap().tx_node;
    assert_eq!(tx.txid, tx1b.compute_txid());

[ValuedMammal]

I'm not sure if that's the ideal solution long term, depending on the use case. One thing that's unclear from the example is whether alice and Bitcoin Core represent distinct entities or if there's reason to think alice should be aware of the other wallet. If so, I can imagine a feature that would let you add extra keychains to the wallet for the purpose of watching other transactions.

I agree that cancel_tx is under-powered and probably requires more engineering of the internals to make sense.

Also I seem to recall that doing a sync via electrum or esplora would allow you to watch for the status of a txid of interest, in this case the unconfirmed tx1a. We have some example code demonstrating this https://github.com/bitcoindevkit/bdk/tree/master/example-crates/example_esplora

*digging deeper it appears for esplora you would actually watch for the spend status of an outpoint of interest, in this case unspent[0]

[ErikDeSmedt]

I discovered the issue when testing the unilateral exit procedure of our Ark implementation. This issue contains a write-up of what the issue is and how it affects us.

However, to my understanding the issue is broader.
If Alice receives a transaction tx1 which is double-spent by an external actor.

• Alice will always have that transaction tx1 in her wallet.
• Alice has no good method to get rid of that Transaction
• If she makes a payment that combines an output from tx1 and a utxo from her own wallet tx2 will be stuck in the wallet. This will actually lock funds that Alice owns

[notmandatory]

It seems we may need to monitor during a sync/scan not just the histories of our wallet's descriptors SPKs but also the UTXOs that are used as inputs to one of our unconfirmed transactions. If we knew that a UTXO was now invalid (ie. spent and confirmed in a different TX) then we could mark our TX as "double spent" or something like that so they could be filtered out. Have you seen bitcoindevkit/bdk_wallet#40? the redesign that @LLFourn has in mind should probably take into account this situation from also.

One question, do you know how other wallets handle this situation? If you setup the same situation in Core's wallet or in Sparrow do you know how they handle it?

[stevenroose]

I have no idea what other wallets do, I'm sorry. I'm not sure many wallets allow foreign inputs. (And we are eternally grateful that BDK does!)

[evanlinjin]

Thanks for taking the time to report this. This is a big problem (and I'm also not sure if other wallets/libraries would handle this properly). @LLFourn talked to me briefly this morning about how to fix this. This is my recollection + some of my own thoughts thrown in.

To fix this problem, we need to redefine what is considered relevant by our receiving structures, and make sure our chain sources emit the replacing tx.

Step 1: Redefine what is considered "relevant" in IndexedTxGraph.

• Affected methods: batch_insert_relevant_unconfirmed, batch_insert_relevant and apply_block_relevant.
• Current behavior: a tx's relevancy is determined purely by the spks referenced by the tx's inputs/outputs.
• Proposed behavior: Keep the current behavior, but add the following rule: if a tx shares inputs with anything contained in the TxGraph, we should also consider it relevant. We can call TxGraph::direct_conflicts for this.

Step 2: Ensure our chain sources emit the replacement txs.

For the bdk_bitcoind_rpc crate, all blocks and all mempool transactions are emitted so the changes in Step 1 alone should allow us to detect replacement txs. We can use this to write a test to validate the validity of Step 1 changes.

Things get more tricky for spk-based chain sources (Electrum and Esplora). I'll do a bit more thinking this weekend.

[evanlinjin]

@LagginTimes agreed to help out on this. He will implement the Step 1 fixes and also testing this scenario with bdk_bitcoind_rpc.