Coin selection should include checks to avoid creating ambiguous transaction history.

[evanlinjin]

Describe the bug

In summary:

• Coin selection should not consider coins from transactions that are replacing other transactions.
• Coin selection should not consider coins from transactions that have been replaced.

Additional context

From Bitcoin Core:

        // We should not consider coins from transactions that are replacing
        // other transactions.
        //
        // Example: There is a transaction A which is replaced by bumpfee
        // transaction B. In this case, we want to prevent creation of
        // a transaction B' which spends an output of B.
        //
        // Reason: If transaction A were initially confirmed, transactions B
        // and B' would no longer be valid, so the user would have to create
        // a new transaction C to replace B'. However, in the case of a
        // one-block reorg, transactions B' and C might BOTH be accepted,
        // when the user only wanted one of them. Specifically, there could
        // be a 1-block reorg away from the chain where transactions A and C
        // were accepted to another chain where B, B', and C were all
        // accepted.
        if (nDepth == 0 && wtx.mapValue.count("replaces_txid")) {
            safeTx = false;
        }


        // Similarly, we should not consider coins from transactions that
        // have been replaced. In the example above, we would want to prevent
        // creation of a transaction A' spending an output of A, because if
        // transaction B were initially confirmed, conflicting with A and
        // A', we wouldn't want to the user to create a transaction D
        // intending to replace A', but potentially resulting in a scenario
        // where A, A', and D could all be accepted (instead of just B and
        // D, or just A and A' like the user would want).
        if (nDepth == 0 && wtx.mapValue.count("replaced_by_txid")) {
            safeTx = false;
        }

https://github.com/bitcoin/bitcoin/blob/e7ca8afef62cec200024030272e81a4e3f011822/src/wallet/spend.cpp#L147-L176

[danielabrozzoni]

Coin selection should not consider coins from transactions that have been replaced.

That's probably already solved, we mark as spent the replaced txouts... (see #700)

[evanlinjin]

@danielabrozzoni (I should probably verify this) but I assume we only mark after we re-sync correct?

[danielabrozzoni]

Yep, that's right

[afilini]

What do you mean we should not consider? Should we just add them to the unspendable list? Should we "penalize" them in some way, but still use them if we don't have any other option?

[evanlinjin]

What do you mean we should not consider? Should we just add them to the unspendable list? Should we "penalize" them in some way, but still use them if we don't have any other option?

I think these seem like security issues if these types of UTXOs were considered as part of coin selection no matter the circumstance. So I think completely avoiding them in the unspendable list seems like a good idea.

I'm thinking we probably want an additional boolean field in TxParams, something like include_replacing_or_replaced_txs for the crazy people that want to include it.

[afilini]

The main issue here is that BDK doesn't keep track of whether a tx is a replacement for a specific txid, and I'm guessing this may not even be possible with most backends, especially if you have the same mnemonic on multiple devices.

For example, with electrum I could detect if a tx which is in by database is replaced by another, but if I sync starting from scratch or for whatever reason I didn't have that previous tx in my database (maybe I haven't synced in a while) I won't be able to know that this tx is a replacement.

[afilini]

I was going to suggest to just avoid spending unconfirmed utxos even if they come from ourselves, but if I understand this correctly even if we wait one confirmation it's not guaranteed we will be ok, because this issue assumes a one block reorg. But I think even core doesn't bother checking for a given number of confirmations, I see a nDepth == 0 which I think means unconfirmed

[evanlinjin]

@afilini thank you for your insights. I'll think about this over the weekends and hopefully we can come up with an elegant solution! 🤞

[evanlinjin]

...but if I understand this correctly even if we wait one confirmation it's not guaranteed we will be ok, because this issue assumes a one block reorg.

@afilini I don't think this is correct.

We are preparing for a potential situation where the original tx is confirmed before the RBF tx, and the RBF tx already has a spend. The spend will be "evicted" if the original tx gets confirmed. So the user would want to "recoup" the spend by creating a new tx. The "recouped" spend and the original spend may exist in the same history if a reorg happens and the RBF tx is confirmed instead.

I think the solution to this problem is simple with the redesigned structures. It is to not pick UTXOs of unconfirmed txs that have conflicts.

cc @danielabrozzoni

[danielabrozzoni]

I think the solution to this problem is simple with the redesigned structures. It is to not pick UTXOs of unconfirmed txs that have conflicts.

This seems fair to me.