Edge case in CreateTransaction causes coin selection to fail sometimes when it shouldn't #20347

Thanks very much to @achow101 for his patience while I got to the bottom of this.

The current CreateTransaction logic interacts with branch-and-bound and subtract-fee-from-output in a subtle and slightly-incorrect way, which can cause coin selection to fail sometimes even there are sufficient funds and BnB succeeds. The issue is as follows:

1. On line 2915 SelectCoins is called, which if it succeeds using BnB, leaves a "change" amount which is always absorbed into fee.
2. We then check if the resulting fee is sufficient to pass the transaction. When subtract-fee-from-output is on, BnB uses exact rather than effective values for all inputs and outputs, so this is fairly unlikely to be the case.
3. This is no big deal; since subtract-fee-from-output is on, we can always correct the fee on the next iteration. So on line 3039 we turn off pick_new_inputs; a few lines later we set nFeeRet to nFeeNeeded, and we wrap around to the top of the loop. On the next iteration, we subtract the new nFeeRet value from outputs and don't bother calling SelectCoins again. (If the subtraction failed the transaction was impossible to satisfy anyway and so we just bail.)
4. We recompute nFeeNeeded, which won't have changed since we didn't redo coin selection, and compare nFeeRet against it, which will pass since we explicitly assigned it to be equal in the previous iteration. Then on line 3013 we break out of the loop successfully.

The problem is in Step 4, where we recompute nFeeNeeded and assume that it hasn't changed. In fact, if the BnB "change" value was greater than our discard threshold, we will erroneously add a change output on line 2959 and therefore compute a nFeeNeeded value that is higher than nFeeRet. We then fail the fee-check on an iteration where we hadn't even done coin selection, which causes the transaction to fail with a generic error message.

The reason we add the erroneous change output is the check on line 2940 which avoids adding change outputs when BnB is used. On the second iteration, because coin selection is overridden by the pick_new_inputs variable, we set bnb_used to false.

This bug is pretty hard to trigger under normal circumstances, because it requires BnB to compute a fee greater than our discard threshold but lower than the cost_of_change variable it uses to decide whether it can produce a change-less transaction, and usually the intersection of these conditions is empty. But under extreme fee circumstances I think it can happen, and you can also force it to happen by setting -minrelaytxfee and -discardfee and then trying to fund a transaction whose output amount misses a BnB-findable input amount by a tiny window. I've posted a regression test which reliably triggers.

I think the fix is to just not reset bnb_used when pick_new_inputs is set, but I'm not certain, and in any case @achow101 tells me he has some upcoming refactors which will eliminate this ugly loop entirely.

#17331 should fix this by getting rid of the loop.

Edit: Just tested this, it does indeed fix the problem and the given test case passes.

This can be closed now that #17331 has been merged.