wallet: avoid knapsack when there’s no change #17246

1. 
   Sjors commented at 8:30 am on October 25, 2019: member

   Builds on top of #17219

   Avoid knapsack when there’s no change, by enabling BnB when subtracting fees from outputs. Gotchas:

   1. when coins are pre-selected, it still uses knapsack
   2. it still excludes dust inputs based on their value minus the fees needed to spend them, but it does not use their effective value in BnB. I don’t think this matters in practice, because subtractFeesFromOutputs is generally used to spend either all coins or a selected bunch. But there is an edge case where e.g. it can choose between two 0.01 BTC inputs, one SegWit and one legacy, and it won’t care.
2. laanwj added the label Wallet on Oct 25, 2019
3. 
   DrahtBot commented at 1:12 pm on October 25, 2019: member

   The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

   Conflicts

   Reviewers, this pull request conflicts with the following ones:

   • #17331 (Use effective values throughout coin selection by achow101)
   • #17290 (Enable BnB coin selection for preset inputs and subtract fee from outputs by achow101)
   • #17237 (wallet: LearnRelatedScripts only if KeepDestination by promag)

   If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

4. 
   achow101 commented at 3:47 pm on October 25, 2019: member

   I don’t think this is really the right approach to allowing subtractFeeFromOutputs. Instead of passing along subtractFeeFromOutputs to BnB, I think it makes more sense to just change the effective_values of each input to be nValue and change the non_input_fees to 0, BnB doesn’t need to know whether subtractFeeFromOutputs is being used.

   I can work on this as an alternative if you’d like.

5. 
   Sjors commented at 6:17 pm on October 25, 2019: member

   Happy to see an alternative approach. Ideally though, I think BnB should know about subtractFeeFromOutputs. It should try to find a set of coins as close to the target as possible, minizing the fees subtracted from the output. With regular wallets this doesn’t matter much, but if you have to choose between spending a P2WPK coin or some 15-of-15 multisig it does.
6. 
   achow101 commented at 6:55 pm on October 25, 2019: member

   Ideally though, I think BnB should know about subtractFeeFromOutputs. It should try to find a set of coins as close to the target as possible, minizing the fees subtracted from the output. With regular wallets this doesn’t matter much, but if you have to choose between spending a P2WPK coin or some 15-of-15 multisig it does.

   BnB should already be minimizing transaction fees as part of reducing “waste”.

7. 
   Sjors commented at 7:06 pm on October 25, 2019: member

   If the effective value of inputs is equal to their nominal value then, afaik, waste reduction only tries to find the smallest possible set of coins. It won’t optimize for which coins are cheapest to spend based on (witness) size.
8. 
   achow101 commented at 10:45 pm on October 25, 2019: member

   I looked more closely at your changes, and it seems like you’ve actually done what I suggested, just in a more verbose way. It could be done with fewer changes.
9. 
   Sjors commented at 8:47 am on October 26, 2019: member

   That’s probably because I went all over the place while trying to get this to work, and chased down a few other rabbit holes (like trying to make BnB find a solution with subtractFeeFromOutputs that actually takes input fees into account). Happy to shorten it a bit.
10. DrahtBot added the label Needs rebase on Oct 29, 2019
11. [wallet] translate "Keypool ran out" message 6b1440e8a5
12. [wallet] CreateTransaction: simplify change address check 6af7fded06
13. [wallet] allow transaction without change if keypool is empty 388b153f9e
14. [wallet] enable BnB for subtractFeeFromOutputs

    This allows skipping the knapsack solver when we can't generate a change address.

    d29efe647e
15. Sjors force-pushed on Oct 29, 2019
16. DrahtBot removed the label Needs rebase on Oct 29, 2019
17. 
    Sjors commented at 12:33 pm on November 4, 2019: member

    Closing in favor of #17290, which is simpler and achieves more:

    • it enables BnB with pre-selected coins, which this PR doesn’t
    • it has a test that checks that BnB was used (the same effect as the test here that disables knapsack)
    • it still excludes dust inputs (based on input size * fee)
18. Sjors closed this on Nov 4, 2019

    ---

19. meshcollider referenced this in commit cef87f7a48 on Nov 22, 2019
20. sidhujag referenced this in commit 1dc1ca3075 on Nov 22, 2019
21. sidhujag referenced this in commit d130bdca8e on Nov 10, 2020
22. DrahtBot locked this on Dec 16, 2021

Contributors
Sjors DrahtBot achow101

Labels
Wallet