Smarter coordination of change and fee in CreateTransaction. #9404

pull morcos wants to merge 2 commits into bitcoin:master from morcos:smartChange changing 2 files +33 −2
  1. morcos commented at 5:16 pm on December 21, 2016: member

    Resolves #9466

    I feel bad making the wallet coin selection even more spaghetti like, but I think this is a huge improvement over the existing code and it’s relatively simple to understand.

    Essentially once you pick coins and if you have change, then try to reduce that change to meet the fee instead of repicking coins. Since we aim to have change of .01 BTC if we can’t make an exact match initially, this is usually more than sufficient to be reduced only slightly to pay for the fee.

    I think for 0.15, we could take on a wholesale rewrite of the algorithm, but thats too much to ask for before 0.14. This however might be worthwhile.

    I’m open to suggestions on how to make this cleaner or clearer.

    EDIT: suggest viewing diff with ?w=1

    EDIT 2: This is much simpler now. Also includes another commit to remove further cases of overpaying fees.

  2. fanquake added the label Wallet on Dec 21, 2016
  3. MarcoFalke commented at 4:14 pm on December 30, 2016: member

    Concept ACK

    (Tries to solve issue #4082 et al.)

  4. gmaxwell commented at 3:52 pm on January 4, 2017: contributor
    Concept ACK but will be simpler when rebased on #9465.
  5. morcos force-pushed on Jan 5, 2017
  6. morcos commented at 4:11 pm on January 5, 2017: member

    This has been rebased on #9465 (thanks @gmaxwell)

    It is now much simpler.
    I added a second commit to almost completely resolve #9466

  7. morcos renamed this:
    Make a second pass with same coins in CreateTransaction.
    Smarter coordination of change and fee in CreateTransaction.
    on Jan 5, 2017
  8. laanwj added this to the milestone 0.14.0 on Jan 5, 2017
  9. gmaxwell commented at 9:06 pm on January 5, 2017: contributor

    Beautiful. utACK. Should be rebased on the latest nit-update of 9465 (sorry about that), I expect it will do so cleanly.

    We should open an issue to also resolve these behaviors when nSubtractFeeFromAmount is used; I can understand why you didn’t cover those in this PR; though they should only be of comparable complexity to this change.

  10. sipa commented at 9:37 pm on January 5, 2017: member
    Needs rebase on #9465 merge.
  11. in src/wallet/wallet.cpp: in 53171a915e outdated 
    2533@@ -2534,8 +2534,17 @@ bool CWallet::CreateTransaction(const vector<CRecipient>& vecSend, CWalletTx& wt
2534                     return false;
2535                 }
2536 
2537-                if (nFeeRet >= nFeeNeeded)
2538+                if (nFeeRet >= nFeeNeeded) {
2539+                    // Reduce fee to only the needed amount if we have change output to increase
2540+                    // Do not do this if fee was paid by payee
2541+                    if (nFeeRet > nFeeNeeded && nChangePosInOut != -1 && nSubtractFeeFromAmount == 0) {
    sdaftuar commented at 9:38 pm on January 5, 2017:

    I guess there’s an edge case left here, where if there’s no change output and the fee difference is very large, then we won’t reduce the fee?

    It might be nice to refactor the change-adding logic so that we could add change in that scenario, though I don’t want to hold up this PR which is already a strict improvement, do you think it’s worth adding a comment that points this out though for future reference?

    gmaxwell commented at 1:11 pm on January 6, 2017:

    it’s pretty easy to compute exactly the amount of additional fee adding a change output would imply. So the test becomes if not subtractfrom and excessfee >= CENT/2 + changeaddfee; then set the change to excessfee-changeaddfee. Doing so without creating a hairball with change added in multiple places… less fun.

    Similarly, the remove side could consider eliminating the change output, if doing so would not overpay by too much. (A conservative value would be the changeaddfee but a larger value would be a lot more useful) both both probably better done in another PR.

    morcos commented at 2:37 pm on January 6, 2017:

    Yes my concern is the gap between desired change amounts (CENT/2) and fee overpayments is quite big. Most of the time even if a fee overpayment was bigger than dust, it wouldn’t be so big that you’d actually want to create an output with it.

    I think fixing that should be combined with more robust handling of the minimum output size a wallet would create. Perhaps then there would be cases where we feel we got unlucky with coin selection and we try again to have less overpayment or more reasonable size change.

    The coin selection algorithm is stupid now. Trying to find an exact match makes no sense in a world where every transaction pays fee. So I’d rather not continue adding patches and improvements before we try to improve the basic strategy. I’m happy to give that a shot after 0.14. And I think we can avoid most of these problems from the beginning…

  12. sdaftuar commented at 9:39 pm on January 5, 2017: member
    Looks good, though I guess it needs to be rebased.
  13. in src/wallet/wallet.cpp: in 53171a915e outdated 
    2533@@ -2550,14 +2534,66 @@ bool CWallet::CreateTransaction(const vector<CRecipient>& vecSend, CWalletTx& wt
2534                     return false;
2535                 }
2536 
2537-                if (nFeeRet >= nFeeNeeded)
2538+                if (nFeeRet >= nFeeNeeded) {
2539+                    // Reduce fee to only the needed amount if we have change output to increase
2540+                    // Do not do this if fee was paid by payee
    MarcoFalke commented at 0:45 am on January 6, 2017:
    I might be missing something, but instead of “Do not”, the comment should read “TODO”. Otherwise, it would imply that it is ok for the payee to pay excessive fee whereas for the payer it is not.
  14. MarcoFalke commented at 0:47 am on January 6, 2017: member
    utACK 53171a915e17e83814328cc3792554159a950757, though I’d prefer to have the edge cases mentioned by @sdaftuar and me documented as todos.
  15. in src/wallet/wallet.cpp: in 53171a915e outdated 
    2550+                // Try to reduce change to include necessary fee
2551+                if (nChangePosInOut != -1 && nSubtractFeeFromAmount == 0) {
2552+                    CAmount additionalFeeNeeded = nFeeNeeded - nFeeRet;
2553+                    vector<CTxOut>::iterator change_position = txNew.vout.begin()+nChangePosInOut;
2554+                    // Only reduce change if remaining amount is still a large enough output (CENT/2)
2555+                    if (change_position->nValue >= CENT/2 + additionalFeeNeeded) {
    MarcoFalke commented at 0:52 am on January 6, 2017:
    can you explain why CENT is used instead of MIN_CHANGE, please?
  16. Try to reduce change output to make needed fee in CreateTransaction 
    Once we've picked coins and dummy-signed the transaction to calculate fee, if we don't have sufficient fee, then try to meet the fee by reducing change before resorting to picking new coins.
    42f5ce4093
  17. Don't overpay fee if we have selected new coins that result in a smaller transaction. 
    On repeated calls to SelectCoins we try to meet the fee necessary for the last transaction, the new fee required might be smaller, so increase our change by the difference if we can.
    20449ef09e
  18. in src/wallet/wallet.cpp: in 53171a915e outdated 
    2549+
2550+                // Try to reduce change to include necessary fee
2551+                if (nChangePosInOut != -1 && nSubtractFeeFromAmount == 0) {
2552+                    CAmount additionalFeeNeeded = nFeeNeeded - nFeeRet;
2553+                    vector<CTxOut>::iterator change_position = txNew.vout.begin()+nChangePosInOut;
2554+                    // Only reduce change if remaining amount is still a large enough output (CENT/2)
    MarcoFalke commented at 0:53 am on January 6, 2017:
    nit: No need to mention code specific values in the comment
  19. morcos force-pushed on Jan 6, 2017
  20. morcos commented at 3:26 pm on January 6, 2017: member
    Rebased after #9465 and addressed comments.
  21. sipa commented at 3:41 pm on January 6, 2017: member
    utACK 20449ef09edf8f4f51a3e531d947dd89973c2a31
  22. MarcoFalke commented at 4:45 pm on January 6, 2017: member
    utACK 20449ef. Thanks for addressing the feedback so quick!
  23. sdaftuar commented at 5:11 pm on January 6, 2017: member
    utACK 20449ef09
  24. gmaxwell commented at 8:31 pm on January 6, 2017: contributor
    re-ACK.
  26. TheBlueMatt commented at 6:29 pm on January 8, 2017: member
    utACK 20449ef09edf8f4f51a3e531d947dd89973c2a31
  27. sipa merged this on Jan 9, 2017
  28. sipa closed this on Jan 9, 2017
  29. sipa referenced this in commit 12e3112794 on Jan 9, 2017
  30. RHavar commented at 6:05 am on February 3, 2017: contributor

    What release will this be in? I’ve been losing a lot of money, to what I suspect is this bug, just $50 last transaction: https://live.blockcypher.com/btc/tx/a92a609f1ebdcd5a2b658a35ed562ac8661a90daf773a7a807a71bd8e1990a6a/

    $ bitcoin-cli estimatefee 4 0.00101654

    $ bitcoin-cli listunspent | grep amount | wc -l 692

  31. codablock referenced this in commit 7c5de865d8 on Jan 18, 2018
  32. andvgal referenced this in commit 97491febfa on Jan 6, 2019
  33. CryptoCentric referenced this in commit 66f93f826b on Feb 26, 2019
  34. MarcoFalke locked this on Sep 8, 2021


morcos MarcoFalke gmaxwell sipa sdaftuar Xekyo TheBlueMatt RHavar

Labels
Wallet

Milestone
0.14.0

github-metadata-mirror

This is a metadata mirror of the GitHub repository bitcoin/bitcoin. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2024-07-05 19:13 UTC
This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me