[WIP] [Wallet] Target effective value during transaction creation #10360

1. 
   instagibbs commented at 5:37 pm on May 8, 2017: member

   Previous fee-targeting behavior lead to needless looping, excessive fees, and surprising behavior.

   This PR changes the “fee targeting” algorithm by considering “effective value” of considered inputs instead of simply trying to hit an absolute fee, seeing if it failed, then trying again with the estimated total fee at the end of the loop.

   The algorithm also doesn’t select any coin with non-positive effective value.

   In short: effectiveValue = nValue - feeRate*num_bytes_for_signed_input

   See #10247 , #7664

   To do:

   1. Previously the wallet just kept stuffing fees until it succeeded. In this PR there is no strict sanity checks on the loop, so if there is some error where we are just shy and cannot re-balance change output to pay for it, it will look forever(I have no idea if this is possible since we should be over-estimating at worst). We should probably have something like #10333 for re-balancing, and then a sanity check to error out if a specified feerate cannot be hit for some reason post-coin selection, perhaps after a fixed number of tries.
   2. This breaks the coinControl->nMinimumTotalFee option. I can’t conceive a use for it, so I want to remove this anyways. https://github.com/bitcoin/bitcoin/pull/10390
2. instagibbs force-pushed on May 8, 2017
3. MarcoFalke added the label Wallet on May 8, 2017
4. 
   instagibbs commented at 9:32 pm on May 8, 2017: member

   Getting travis RPC_WALLET_INSUFFICIENT_FUNDS errors all over the place for one configuration. Can’t reproduce locally…

   /usr/include/c++/4.8/debug/vector:519:error: attempt to erase from container with a past-the-end iterator.

   edit: was indeed erasing past-end of the vector… fixed.

5. instagibbs force-pushed on May 8, 2017
6. instagibbs force-pushed on May 9, 2017
7. 
   morcos commented at 2:32 pm on May 9, 2017: member

   sort of concept ACK

   I think there are a lot of issues to think about in order to make sure we don’t accidentally introduce poor behavior. One simple improvement would be to cache the number of bytes each input would require to spend to create a much simpler calculation of effective value each time through instead of dummy signing an ever growing virtual transaction.

   But I’m more concerned with the interaction between the knapsack solver and the effective value inputs. Since the knapsack solver aims for exact matches (either with or without change), I believe there will be a tendency to often include many very small effective inputs to try to get as close as possible to an arbitrary change number.

8. 
   instagibbs commented at 3:31 pm on May 9, 2017: member

   One simple improvement would be to cache the number of bytes each input would require to spend to create a much simpler calculation of effective value each time through instead of dummy signing an ever growing virtual transaction.

   Yes, some additional refactoring would make sense especially for this. This was probably the most janky part of my implementation.

   I believe there will be a tendency to often include many very small effective inputs to try to get as close as possible to an arbitrary change number.

   As we discussed on IRC, Core already does this, but you mean that previously slightly larger inputs would now fall under this bucket so it may pack even more. It’s hard to say the net effect especially since we disallow negative effective value inputs, but something to think about. OTOH If we wait until everything is an unambiguous win, I am not sure any changes will get merged.

   some chatter about general refactoring on IRC

   I really don’t mind attempting to tackle more refactoring within this PR. I admittedly did just over minimal refactoring to make it work.

9. remove maxTxFee check outside of GetMinimumFee cc61e687c2
10. add FeeRate companions to Get_Fee wallet helpers 61ee854f53
11. Remove absolute fee estimator functions d0947cfda1
12. rename Mempool GetMinFee to GetMinFeeRate 4ebea72f27
13. pull out pre-transaction-completion fee estimation outside main loop 0bc0ba3797
14. replace GetRequiredFee with GetRequiredFeeRate 8e49f95642
15. Move subtractFeeFromOutput logic to after full transaction fee estimation c1ccde5b52
16. Avoid needless copying of coins list in SelectCoinsMinConf 4e3f40980f
17. move CalculateMaximumSignedTxSize to CWallet, use during tx creation 1ff6cd9c22
18. CalculateMaximumSignedTxSize returns -1 more consistently fd42d9ab57
19. COutput caches marginal bytes to spend the output ac04798c46
20. instagibbs force-pushed on May 16, 2017
21. coincontrol updateLabels uses precomputed input sizes c04b88f45e
22. Use effective value of coins to target a defined feerate e1c7677650
23. f'coincontrol updateLabels uses precomputed input sizes' 53da55e48a
24. f'COutput caches marginal bytes to spend the output' 7c6e747477
25. f'Use effective value of coins to target a defined feerate' 412d478ceb
26. instagibbs force-pushed on May 16, 2017
27. f'Use effective value of coins to target a defined feerate' 8b39192c79
28. 
    instagibbs commented at 6:56 pm on June 11, 2017: member

    @gmaxwell notes on IRC that we may want to consider unconfirmed change as smaller effective value by having it also need to pay for the ancestor(s) feerate delta to current confirmation target feerate.
29. 
    instagibbs commented at 7:15 pm on February 8, 2018: member

    closing until BnB PR has been merged, then will revisit our transaction creation strategy as a whole.
30. instagibbs closed this on Feb 8, 2018

    ---

31. laanwj referenced this in commit e057589dc6 on Mar 14, 2018
32. TheHolyRoger referenced this in commit b127150eab on Jul 31, 2020
33. TheHolyRoger referenced this in commit cb394b50d6 on Aug 1, 2020
34. TheHolyRoger referenced this in commit f9096e2157 on Aug 1, 2020
35. TheHolyRoger referenced this in commit 6952af0e6a on Aug 1, 2020
36. DrahtBot locked this on Sep 8, 2021

Contributors
instagibbs morcos

Labels
Wallet