wallet::Balance::trusted_pending AND TxBuilder::only_spend_change are broken

[stevenroose]

Describe the bug
TxGraph calculates balance and splits the unconfirmed txs into "trusted" and "untrusted" based on a trust_predicate (trust_predicate: impl FnMut(&OI, ScriptBuf) -> bool). Wallet then uses that method and fills this argument with

            |&(k, _), _| k == KeychainKind::Internal,

This is too naive. While the Internal keychain is intended for change that the wallet controls, there is no guarantee that external users don't pay to change addresses (for example by observing the chain and discovering our change addresses). Hence, utxos that are considered trusted by the Wallet::balance method, can still be maliciously double-spent by external parties.

Similarly, only_spend_change also only checks the keychainkind of the output which does not guarantee it was actually change from one of our own txs:

impl ChangeSpendPolicy {
    pub(crate) fn is_satisfied_by(&self, utxo: &LocalOutput) -> bool {
        match self {
            ChangeSpendPolicy::ChangeAllowed => true,
            ChangeSpendPolicy::OnlyChange => utxo.keychain == KeychainKind::Internal,
            ChangeSpendPolicy::ChangeForbidden => utxo.keychain == KeychainKind::External,
        }
    }
}

While this trust_predicate seems useful, I think a "trusted" notion is confusing. In effect, the intention is already to mean "change", so I would just drop the "trusted" in favor of "change" (or equivalent the internal/external naming) (pending_internal, pending_external) or so. BUT, "internal" does not merely mean from the internal keychain, but actually "originating from a tx that we ourselves have created".

Once that notion is fixed, and change it not just determined based on keychainkind.

[notmandatory]

It looks like the Core wallet is also using a fairly simplistic heuristic for determining what UTXOs are change. Per the below code and comment it only checks if the UTXO address is controlled by the wallet and is not in the address book, which I think means the address was given to the user when asking for a new address. Based on that I think it would also break down in your scenario where a change address was re-used to send a new externally sourced output.

bool CWallet::IsChange(const CTxOut& txout) const
{
    // TODO: fix handling of 'change' outputs. The assumption is that any
    // payment to a script that is ours, but is not in the address book
    // is change. That assumption is likely to break when we implement multisignature
    // wallets that return change back into a multi-signature-protected address;
    // a better way of identifying which outputs are 'the send' and which are
    // 'the change' will need to be implemented (maybe extend CWalletTx to remember
    // which output, if any, was change).
    if (::IsMine(*this, txout.scriptPubKey))
    {
        CTxDestination address;
        if (!ExtractDestination(txout.scriptPubKey, address))
            return true;

        LOCK(cs_wallet);
        if (!mapAddressBook.count(address))
            return true;
    }
    return false;
}

That said I'm not opposed to 1. removing the possibly confusing "trusted" balance verbiage and 2. implementing a better algo to determine which UTXOs should be treated as change. I suspect we're going to have to rethink "change" anyway if we go forward with supporting more than two descriptors in a Wallet. It'd be nice to be able to send from say a P2WSH descriptor UTXO to a 3rd party P2TR address and have the change go back to a P2TR descriptor address in the same wallet. Core's wallet can do stuff like this to improve privacy (see #28).

[stevenroose]

Yeah I think "change" should literally mean that, "an output back to ourselves from a tx we made earlier". But "trusted" could include change, plus confirmed, plus things manually marked as trusted.

This is how I'm now implementing untrusted_utxos manually in our code: https://codeberg.org/ark-bitcoin/bark/src/commit/1155f031516d680d376a72f619dcf9295e98f2ad/bitcoin-ext/src/bdk.rs#L60-L87

Basically for each utxo that is not confirmed deeply enough (we use 2 confirmations, but it's configurable), we check if there is any input that did not come from our wallet by checking if the tx that created the output for that input exists in our wallet. It's not efficient and could be optimized by caching, but for now it works for us.

And then we manually mark these as unspendable when we make a tx: https://codeberg.org/ark-bitcoin/bark/src/commit/1155f031516d680d376a72f619dcf9295e98f2ad/aspd/src/round/mod.rs#L440

[notmandatory]

Moved to bdk_wallet repo.

[ValuedMammal]

My 2 sats after reading this and the related #273

trust_predicate should take into account the outpoint, not just the indexed SPK, since an indexed SPK can occur on multiple transactions which may or may not be trusted. In contrast, knowledge of the outpoint means you can apply trust to all of the txouts of a transaction regardless of the associated keychain.