Smarter coordination of change and fee in CreateTransaction. #9404

morcos · 2016-12-21T17:16:35Z

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.

maflcko · 2016-12-30T16:14:56Z

Concept ACK

(Tries to solve issue #4082 et al.)

gmaxwell · 2017-01-04T15:52:21Z

Concept ACK but will be simpler when rebased on #9465.

morcos · 2017-01-05T16:11:00Z

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

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

gmaxwell · 2017-01-05T21:06:18Z

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.

sipa · 2017-01-05T21:37:53Z

Needs rebase on #9465 merge.

sdaftuar

Looks good, though I guess it needs to be rebased.

sdaftuar · 2017-01-05T21:38:07Z

src/wallet/wallet.cpp

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?

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.

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...

maflcko

utACK 53171a915e17e83814328cc3792554159a950757, though I'd prefer to have the edge cases mentioned by @sdaftuar and me documented as todos.

maflcko · 2017-01-06T00:45:49Z

src/wallet/wallet.cpp

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.

maflcko · 2017-01-06T00:52:22Z

src/wallet/wallet.cpp

can you explain why CENT is used instead of MIN_CHANGE, please?

maflcko · 2017-01-06T00:53:07Z

src/wallet/wallet.cpp

nit: No need to mention code specific values in the comment

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.

…ler 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.

morcos · 2017-01-06T15:26:54Z

Rebased after #9465 and addressed comments.

sipa · 2017-01-06T15:41:11Z

utACK 20449ef

maflcko · 2017-01-06T16:45:19Z

utACK 20449ef. Thanks for addressing the feedback so quick!

sdaftuar · 2017-01-06T17:11:06Z

utACK 20449ef

gmaxwell · 2017-01-06T20:31:27Z

re-ACK.

murchandamus · 2017-01-08T11:42:11Z

utACK 20449ef

TheBlueMatt · 2017-01-08T18:29:33Z

utACK 20449ef

…ion. 20449ef Don't overpay fee if we have selected new coins that result in a smaller transaction. (Alex Morcos) 42f5ce4 Try to reduce change output to make needed fee in CreateTransaction (Alex Morcos)

RHavar · 2017-02-03T06:05:30Z

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

…ransaction. 20449ef Don't overpay fee if we have selected new coins that result in a smaller transaction. (Alex Morcos) 42f5ce4 Try to reduce change output to make needed fee in CreateTransaction (Alex Morcos)

fanquake added the Wallet label Dec 21, 2016

morcos mentioned this pull request Jan 4, 2017

[Wallet] Do not perform ECDSA signing in the fee calculation inner loop. #9465

Merged

gmaxwell mentioned this pull request Jan 4, 2017

Prevent fee overpayment when nFeeNeeded decreases in CreateTransaction iterations #9466

Closed

morcos force-pushed the smartChange branch from ae20cc8 to 53171a9 Compare January 5, 2017 16:10

morcos changed the title ~~Make a second pass with same coins in CreateTransaction.~~ Smarter coordination of change and fee in CreateTransaction. Jan 5, 2017

laanwj added this to the 0.14.0 milestone Jan 5, 2017

sdaftuar reviewed Jan 5, 2017

View reviewed changes

maflcko reviewed Jan 6, 2017

View reviewed changes

src/wallet/wallet.cpp Outdated

Copy link

Member

maflcko Jan 6, 2017

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

can you explain why CENT is used instead of MIN_CHANGE, please?

maflcko reviewed Jan 6, 2017

View reviewed changes

src/wallet/wallet.cpp Outdated

Copy link

Member

maflcko Jan 6, 2017

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

nit: No need to mention code specific values in the comment

morcos added 2 commits January 6, 2017 10:12

Try to reduce change output to make needed fee in CreateTransaction

42f5ce4

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.

Don't overpay fee if we have selected new coins that result in a smal…

20449ef

…ler 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.

morcos force-pushed the smartChange branch from 53171a9 to 20449ef Compare January 6, 2017 15:26

murchandamus mentioned this pull request Jan 8, 2017

Revisit Coin Selection #7664

Closed

sipa merged commit 20449ef into bitcoin:master Jan 9, 2017

morcos mentioned this pull request Jan 13, 2017

CreateTransaction can include much too high a fee #4082

Closed

sipa mentioned this pull request Jan 23, 2017

coin selection code does very badly in some cases #1643

Closed

bitcoin locked as resolved and limited conversation to collaborators Sep 8, 2021

Smarter coordination of change and fee in CreateTransaction. #9404

Smarter coordination of change and fee in CreateTransaction. #9404

Uh oh!

Conversation

morcos commented Dec 21, 2016 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

maflcko commented Dec 30, 2016

Uh oh!

gmaxwell commented Jan 4, 2017

Uh oh!

morcos commented Jan 5, 2017

Uh oh!

gmaxwell commented Jan 5, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

sipa commented Jan 5, 2017

Uh oh!

sdaftuar left a comment

Choose a reason for hiding this comment

Uh oh!

sdaftuar Jan 5, 2017

Choose a reason for hiding this comment

Uh oh!

gmaxwell Jan 6, 2017

Choose a reason for hiding this comment

Uh oh!

morcos Jan 6, 2017

Choose a reason for hiding this comment

Uh oh!

maflcko left a comment • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

maflcko Jan 6, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

maflcko Jan 6, 2017

Choose a reason for hiding this comment

Uh oh!

maflcko Jan 6, 2017

Choose a reason for hiding this comment

Uh oh!

morcos commented Jan 6, 2017

Uh oh!

sipa commented Jan 6, 2017

Uh oh!

maflcko commented Jan 6, 2017

Uh oh!

sdaftuar commented Jan 6, 2017

Uh oh!

gmaxwell commented Jan 6, 2017

Uh oh!

murchandamus commented Jan 8, 2017

Uh oh!

TheBlueMatt commented Jan 8, 2017

Uh oh!

RHavar commented Feb 3, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

10 participants

morcos commented Dec 21, 2016 •

edited

Loading

gmaxwell commented Jan 5, 2017 •

edited

Loading

maflcko left a comment •

edited

Loading

maflcko Jan 6, 2017 •

edited

Loading

RHavar commented Feb 3, 2017 •

edited

Loading