Add change output if necessary to reduce excess fee #10712

morcos commented at 5:29 PM on June 30, 2017: member

This is an alternative to #10333

See commit messages.

The first commit is mostly code move, it just moves the change creation code out of the loop. @instagibbs

in src/wallet/wallet.cpp:2758 in 93197a7cab outdated

2750 | @@ -2744,8 +2751,18 @@ bool CWallet::CreateTransaction(const std::vector<CRecipient>& vecSend, CWalletT
2751 |                      // TODO: The case where nSubtractFeeFromAmount > 0 remains
2752 |                      // to be addressed because it requires returning the fee to
2753 |                      // the payees and not the change output.
2754 | -                    // TODO: The case where there is no change output remains
2755 | -                    // to be addressed so we avoid creating too small an output.
2756 | +                    CAmount max_excess_fee = GetMinimumFee(change_prototype_size, currentConfirmationTarget, ::mempool, ::feeEstimator, nullptr) +
2757 | +                        GetDustThreshold(change_prototype_txout, ::dustRelayFee);
2758 | +                    // If we have no change and a big enough excess fee, then

instagibbs commented at 5:42 PM on June 30, 2017:

please move first explanation a few lines before for the "increase change" to appropriate spot

ryanofsky commented at 10:24 PM on July 10, 2017:

please move first explanation a few lines before for the "increase change" to appropriate spot

I think order of the comments does makes sense. First comment describes the normal case, second comment describes unhandled special case, and third comment describes handled special case accompanied by implementation for that case.

I might move the code for the normal case above the code & comments for the two special cases, though this would increase the size of the diff. Just a thought, though.

instagibbs commented at 1:56 PM on July 11, 2017:

He moved it, the comment wasn't marked as resolved. Happy with current arrangement.

in src/wallet/wallet.cpp:2775 in 93197a7cab outdated

2770 | @@ -2754,6 +2771,11 @@ bool CWallet::CreateTransaction(const std::vector<CRecipient>& vecSend, CWalletT
2771 |                      }
2772 |                      break; // Done, enough fee included.
2773 |                  }
2774 | +                else if (!pick_new_inputs) {
2775 | +                    // This shouldn't happen

instagibbs commented at 5:48 PM on June 30, 2017:

nit: slightly longer explanation for reader?

"This shouldn't happen, we should have had enough excess fee to pay for the newly created change output."

With fix on the nFeeRet, a very slight increase in fee between estimation calls(can that happen?) will result in this triggering.

morcos commented at 7:31 PM on June 30, 2017:

yes, i don't think that can happen (a change in fee estimation) but belts and suspenders. In any case will be cleaned up post 0.15 with effective value logic and only calculating the needed fee rate once.

in src/wallet/wallet.cpp:2776 in 252837b04a outdated

2772 | @@ -2774,6 +2773,8 @@ bool CWallet::CreateTransaction(const std::vector<CRecipient>& vecSend, CWalletT
2773 |              }
2774 |          }
2775 |  
2776 | +        if (nChangePosInOut == -1) reserveKey.ReturnKey(); // Return any reserved key if we don't have change

instagibbs commented at 5:51 PM on June 30, 2017:

looks like a capital "K" snuck in here.

morcos commented at 7:30 PM on June 30, 2017:

weird, i fixed that but must have not committed before push

instagibbs commented at 8:08 PM on June 30, 2017:

sorry to both you again on this but it appears to still be there

in src/wallet/wallet.cpp:2763 in 93197a7cab outdated

2760 | +                    // new inputs. We now know we only need the smaller fee
2761 | +                    // (because of reduced tx size) and so we should add a
2762 | +                    // change input. Only try this once.
2763 | +                    if (nFeeRet > nFeeNeeded + max_excess_fee && nChangePosInOut == -1 && nSubtractFeeFromAmount == 0 && pick_new_inputs) {
2764 | +                        pick_new_inputs = false;
2765 | +                        nFeeRet = nFeeNeeded;

instagibbs commented at 6:02 PM on June 30, 2017:

this needs to be nFeeRet = nFeeNeeded + GetMinimumFee(change_prototype_size, currentConfirmationTarget, ::mempool, ::feeEstimator, nullptr) ; at a minimum, right?

nFeeNeeded at this point will not pay for the new change output.

morcos commented at 7:29 PM on June 30, 2017:

oops, correct

instagibbs commented at 6:19 PM on June 30, 2017: member

imo this is superior in its simplicity and targeting the exact situation better over #10333 .

A bit worried about the failure case triggering anytime fee estimations change. I know you don't want to in this PR, but pulling out the estimation and getting a feerate that is reapplied in the main loop seems worth it, is easy to review, and will have to be done anyways for effective value work.

morcos force-pushed on Jun 30, 2017

morcos commented at 7:51 PM on June 30, 2017: member

Fixed bug and nits and squashed @instagibbs I'm fine with doing the GetMinimumFeeRate refactor for 0.15, but I already did a lot of other work on GetMinimumFee in #10706 which I would really like to get in for 0.15, so I'm wary of piling on too many changes that touch the same lines of code and not being able to get them all in.

fanquake added the label Wallet on Jul 1, 2017

promag commented at 9:06 AM on July 3, 2017: member

All return points should call reservekey.ReturnKey()?

promag commented at 9:16 AM on July 3, 2017: member

Reference #10247.

promag commented at 9:18 AM on July 3, 2017: member

utACK.

IMO going for one last iteration and to have one more flag is a clear sign that a more thoughtful refactor should be done. Not that I'm against this change, but reading this code should be plain and easy.

instagibbs commented at 12:20 PM on July 3, 2017: member

@promag this is a bugfix with limited scope. Switching to effective value calculation fixes this in a more natural fashion. See: #10360 and https://github.com/bitcoin/bitcoin/pull/10637

promag commented at 9:10 AM on July 4, 2017: member

Nit, should variables be in camel or snake case? Also could you fix brace styles for the moved code?

morcos commented at 4:36 PM on July 5, 2017: member

@promag New variables are supposed to be snake_case, did I miss one? If there are any other changes, I can fix the braces, but I didn't touch the moved code.

As for calling ReturnKey, I suppose that does make sense, but the existing code did not do that, and I haven't materially changed that behavior. I'm happy to add it though if I should? (Clarification: My only hesitation is that it looks to me like it's fine to call ReturnKey even if you haven't reserved one, but I'm just not that familiar with the code or it's design, so was hesitant to put in extra calls to ReturnKey where one might not have actually been reserved)

promag commented at 12:10 AM on July 6, 2017: member

@morcos another PR is fine. As @instagibbs said, this is a bugfix.

laanwj added this to the "Blockers" column in a project

laanwj commented at 2:09 PM on July 6, 2017: member

Replaced #10333 with this one in "High priority for review" (reviewing a closed PR with high priority makes little sense).

jonasschnelli added this to the milestone 0.15.0 on Jul 6, 2017

in src/wallet/wallet.cpp:2806 in d64a4b94ea outdated

2799 | @@ -2773,7 +2800,7 @@ bool CWallet::CreateTransaction(const std::vector<CRecipient>& vecSend, CWalletT
2800 |              }
2801 |          }
2802 |  
2803 | -        if (nChangePosInOut == -1) reserveKey.ReturnKey(); // Return any reserved key if we don't have change
2804 | +        if (nChangePosInOut == -1) reservekey.ReturnKey(); // Return any reserved key if we don't have change

ryanofsky commented at 9:38 PM on July 10, 2017:

In commit "Fix rare edge case of paying too many fees"

This needs to be moved to the previous commit for it to compile.

in src/wallet/wallet.cpp:2759 in d64a4b94ea outdated

2761 | +
2762 | +                    // If we have no change and a big enough excess fee, then
2763 | +                    // try to construct transaction again only without picking
2764 | +                    // new inputs. We now know we only need the smaller fee
2765 | +                    // (because of reduced tx size) and so we should add a
2766 | +                    // change input. Only try this once.

ryanofsky commented at 10:03 PM on July 10, 2017:

change output

ryanofsky commented at 10:29 PM on July 10, 2017: member

Wow, this code is ridiculously complicated. Pretty clean fix, though. Would be nice if we could mock SelectCoins and easily write unit tests for these cases.

utACK d64a4b94ea809179e8cc9a92be75036bc8bd4fbf

morcos force-pushed on Jul 11, 2017

morcos commented at 12:21 AM on July 11, 2017: member

Fixed commit history and fixed comment nit

git diff d64a4b9 533b3f0

-                    // change input. Only try this once.
+                    // change output. Only try this once.

TheBlueMatt commented at 12:31 AM on July 11, 2017: member

utACK 533b3f07f0525939d5fef2d22ec1ee699b7d437b

in src/wallet/wallet.cpp:2781 in 533b3f07f0 outdated

2774 | @@ -2754,6 +2775,12 @@ bool CWallet::CreateTransaction(const std::vector<CRecipient>& vecSend, CWalletT
2775 |                      }
2776 |                      break; // Done, enough fee included.
2777 |                  }
2778 | +                else if (!pick_new_inputs) {

sipa commented at 8:30 AM on July 11, 2017:

Nit: else on the same line as }

instagibbs commented at 1:57 PM on July 11, 2017: member

utACK https://github.com/bitcoin/bitcoin/pull/10712/commits/533b3f07f0525939d5fef2d22ec1ee699b7d437b

ryanofsky commented at 2:45 PM on July 11, 2017: member

utACK 533b3f07f0525939d5fef2d22ec1ee699b7d437b. Changes since last review were what Alex mentioned.

Only reserve key for scriptChange once in CreateTransaction

This does not affect behavior but allows us to have access to an output to
scriptChange even if we currently do not have change in the transaction.

253cd7ec4f

Fix rare edge case of paying too many fees when transaction has no change.

Due to the iterative process of selecting new coins in each loop a new fee is
calculated that needs to be met each time.  In the typical case if the most
recent iteration of the loop produced a much smaller transaction and we have now
gathered inputs with too many fees, we can just reduce the change.  However in
the case where there is no change output, it is possible to end up with a
transaction which drastically overpays fees.  This commit addresses that case,
by creating a change output if the overpayment is large enough to support it,
this is accomplished by rerunning the transaction creation loop without
selecting new coins.

Thanks to instagibbs for working on this as well

0f402b9263

morcos force-pushed on Jul 11, 2017

morcos commented at 4:28 PM on July 11, 2017: member

This was rebased to add 2 new arguments to GetMinimumFee line which were introduced in #10589

Will change again as it conflicts with #10706 on that same point (depending on which is merged first, but I think this is ready)

laanwj merged this on Jul 11, 2017

laanwj closed this on Jul 11, 2017

laanwj referenced this in commit e8b95239ee on Jul 11, 2017

ryanofsky commented at 5:40 PM on July 11, 2017: member

utACK 0f402b9263b0579b29aa0f841fc64ad58d3efba6. Only difference is rebase.

sipa commented at 6:03 PM on July 11, 2017: member

Posthumous utACK 0f402b9

laanwj removed this from the "Blockers" column in a project

PastaPastaPasta referenced this in commit 2122416793 on Aug 6, 2019

PastaPastaPasta referenced this in commit f9ca5db82c on Aug 6, 2019

PastaPastaPasta referenced this in commit b501fae48f on Aug 6, 2019

PastaPastaPasta referenced this in commit b5b7868c15 on Aug 7, 2019

PastaPastaPasta referenced this in commit a76e442f95 on Aug 8, 2019

PastaPastaPasta referenced this in commit 00ceca6216 on Aug 12, 2019

barrystyle referenced this in commit 4f15dfe35d on Jan 22, 2020

DrahtBot locked this on Sep 8, 2021