Obviously this will fail tests and need docs fixed up. I'll do that unless there are NACKs.

(un?) related: According to https://transactionfee.info/charts/inputs-types-by-count/ about 80% of spends today are using the witness stack.

Light concept ACK

Talking about potential privacy loss, isn't the main concern here to consider how hard it is to deduce which one is the change output? (https://en.bitcoin.it/wiki/Privacy#Change_address_detection)
For the mentioned special scenario "p2sh-witness as address type and there are no bech32(m) outputs." and a simple spend to a P2SH(-wrapped) destination:

• On master, the change address is also P2SH(-wrapped) -> Perfect, both outputs are equally likely to be change.
• On the PR branch, the change address is bech32(m). Is this slightly worse? (Or even better, as analyzers assume the change address type usually matches the input type and would wrongly deduce that the bech32(m) output is actually the destination?)

Just thinking out loud, would be very interested to hear comments about this.

On master, the change address is also P2SH(-wrapped) -> Perfect, both outputs are equally likely to be change.

Not sure this is necessarily true. If the payment is unwrapped to be non-witness and our change is unwrapped to be witness (which is likely because ~80% of all spends are using the witness stack and also P2SH seems to be exclusively used for wrapping a witness program), then this can be combined with other leaks to determine the change address.

On the PR branch, the change address is bech32(m). Is this slightly worse? (Or even better, as analyzers assume the change address type usually matches the input type and would wrongly deduce that the bech32(m) output is actually the destination?)

As you say it might be slightly worse or slightly better, depending on the context. After all those are heuristics.

An alternative approach I could think of would be to treat a wallet that can provide bech32m addresses as a taproot wallet. A wallet that can provide bech32 as a wpkh wallet.

if tx_has_any_tr_output and wallet_has_tr:
 return bech32m
if tx_has_any_wpkh and wallet_has_wpkh:
 return bech32
if wallet_has_tr:
 return bech32m
if wallet_has_wpkh:
 return bech32

Obviously this will break again once we add output script descriptor support for v2 witness programs.

Happy to implement this nonetheless if reviewers think it is useful.

Instead of always using bech32(m), I feel like we should just do the inverse of the current implementation - prefer bech32(m) and use p2sh-segwit if there is a p2sh-segwit output.

prefer bech32(m) and use p2sh-segwit if there is a p2sh-segwit output.

I don't think it is possible to see whether a p2sh is segwit or not. While it is likely that a p2sh is segwit, I don't see a benefit to pick p2sh-segwit change over native segwit change (potentially wpkh). (See OP for explanation).

I don't think it is possible to see whether a p2sh is segwit or not.

p2sh-segwit if there are any p2sh outputs, rather.

While it is likely that a p2sh is segwit, I don't see a benefit to pick p2sh-segwit change over native segwit change (potentially wpkh). (See OP for explanation).

I disagree that there is little or no benefit. Given that the majority of p2sh inputs are nested segwit, it is likely that when those outputs are eventually spent, they will be revealed to be segwit as well, so there is less information to be able to determine which is change. Furthermore, the change output would be less likely to be identified before the outputs are spent.

Ok, will try to propose an alternative

Done in #23789