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

instagibbs · 2017-05-08T17:37:44Z

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:

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 [wallet] fee fixes: always create change, adjust value, and p… #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.
This breaks the coinControl->nMinimumTotalFee option. I can't conceive a use for it, so I want to remove this anyways. [wallet] remove minimum total fee option #10390

instagibbs · 2017-05-08T21:32:21Z

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.

morcos · 2017-05-09T14:32:07Z

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.

instagibbs · 2017-05-09T15:31:45Z

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.

…tion

instagibbs · 2017-06-11T18:56:28Z

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

instagibbs · 2018-02-08T19:15:58Z

closing until BnB PR has been merged, then will revisit our transaction creation strategy as a whole.

@xekyo

73b5bf2 Add a test to make sure that negative effective values are filtered (Andrew Chow) 76d2f06 Benchmark BnB in the worst case where it exhausts (Andrew Chow) 6a34ff5 Have SelectCoinsMinConf and SelectCoins use BnB or Knapsack and use it (Andrew Chow) fab0488 Add a GetMinimumFeeRate function which is wrapped by GetMinimumFee (Andrew Chow) cd927ff Move original knapsack solver tests to coinselector_tests.cpp (Andrew Chow) fb716f7 Move current coin selection algorithm to coinselection.{cpp,h} (Andrew Chow) 4566ab7 Add tests for the Branch and Bound algorithm (Andrew Chow) 4b2716d Remove coinselection.h -> wallet.h circular dependency (Andrew Chow) 7d77eb1 Use a struct for output eligibility (Andrew Chow) ce7435c Move output eligibility to a separate function (Andrew Chow) 0185939 Implement Branch and Bound coin selection in a new file (Andrew Chow) f84fed8 Store effective value, fee, and long term fee in CInputCoin (Andrew Chow) 12ec29d Calculate and store the number of bytes required to spend an input (Andrew Chow) Pull request description: This is an implementation of the [Branch and Bound coin selection algorithm written by Murch](http://murch.one/wp-content/uploads/2016/11/erhardt2016coinselection.pdf) (@xekyo). I have it set so this algorithm will run first and if it fails, it will fall back to the current coin selection algorithm. The coin selection algorithms and tests have been refactored to separate files instead of having them all in wallet.cpp. I have added some tests for the new algorithm and a test for all of coin selection in general. However, more tests may be needed, but I will need help with coming up with more test cases. This PR uses some code borrowed from #10360 to use effective values when selecting coins. Tree-SHA512: b0500f406bf671e74984fae78e2d0fbc5e321ddf4f06182c5855e9d1984c4ef2764c7586d03e16fa4b578c340b21710324926f9ca472d5447a0d1ed43eb4357e

@xekyo

73b5bf2 Add a test to make sure that negative effective values are filtered (Andrew Chow) 76d2f06 Benchmark BnB in the worst case where it exhausts (Andrew Chow) 6a34ff5 Have SelectCoinsMinConf and SelectCoins use BnB or Knapsack and use it (Andrew Chow) fab0488 Add a GetMinimumFeeRate function which is wrapped by GetMinimumFee (Andrew Chow) cd927ff Move original knapsack solver tests to coinselector_tests.cpp (Andrew Chow) fb716f7 Move current coin selection algorithm to coinselection.{cpp,h} (Andrew Chow) 4566ab7 Add tests for the Branch and Bound algorithm (Andrew Chow) 4b2716d Remove coinselection.h -> wallet.h circular dependency (Andrew Chow) 7d77eb1 Use a struct for output eligibility (Andrew Chow) ce7435c Move output eligibility to a separate function (Andrew Chow) 0185939 Implement Branch and Bound coin selection in a new file (Andrew Chow) f84fed8 Store effective value, fee, and long term fee in CInputCoin (Andrew Chow) 12ec29d Calculate and store the number of bytes required to spend an input (Andrew Chow) Pull request description: This is an implementation of the [Branch and Bound coin selection algorithm written by Murch](http://murch.one/wp-content/uploads/2016/11/erhardt2016coinselection.pdf) (@xekyo). I have it set so this algorithm will run first and if it fails, it will fall back to the current coin selection algorithm. The coin selection algorithms and tests have been refactored to separate files instead of having them all in wallet.cpp. I have added some tests for the new algorithm and a test for all of coin selection in general. However, more tests may be needed, but I will need help with coming up with more test cases. This PR uses some code borrowed from bitcoin#10360 to use effective values when selecting coins. Tree-SHA512: b0500f406bf671e74984fae78e2d0fbc5e321ddf4f06182c5855e9d1984c4ef2764c7586d03e16fa4b578c340b21710324926f9ca472d5447a0d1ed43eb4357e

@xekyo

73b5bf2 Add a test to make sure that negative effective values are filtered (Andrew Chow) 76d2f06 Benchmark BnB in the worst case where it exhausts (Andrew Chow) 6a34ff5 Have SelectCoinsMinConf and SelectCoins use BnB or Knapsack and use it (Andrew Chow) fab0488 Add a GetMinimumFeeRate function which is wrapped by GetMinimumFee (Andrew Chow) cd927ff Move original knapsack solver tests to coinselector_tests.cpp (Andrew Chow) fb716f7 Move current coin selection algorithm to coinselection.{cpp,h} (Andrew Chow) 4566ab7 Add tests for the Branch and Bound algorithm (Andrew Chow) 4b2716d Remove coinselection.h -> wallet.h circular dependency (Andrew Chow) 7d77eb1 Use a struct for output eligibility (Andrew Chow) ce7435c Move output eligibility to a separate function (Andrew Chow) 0185939 Implement Branch and Bound coin selection in a new file (Andrew Chow) f84fed8 Store effective value, fee, and long term fee in CInputCoin (Andrew Chow) 12ec29d Calculate and store the number of bytes required to spend an input (Andrew Chow) Pull request description: This is an implementation of the [Branch and Bound coin selection algorithm written by Murch](http://murch.one/wp-content/uploads/2016/11/erhardt2016coinselection.pdf) (@xekyo). I have it set so this algorithm will run first and if it fails, it will fall back to the current coin selection algorithm. The coin selection algorithms and tests have been refactored to separate files instead of having them all in wallet.cpp. I have added some tests for the new algorithm and a test for all of coin selection in general. However, more tests may be needed, but I will need help with coming up with more test cases. This PR uses some code borrowed from bitcoin#10360 to use effective values when selecting coins. Tree-SHA512: b0500f406bf671e74984fae78e2d0fbc5e321ddf4f06182c5855e9d1984c4ef2764c7586d03e16fa4b578c340b21710324926f9ca472d5447a0d1ed43eb4357e

@xekyo

73b5bf2 Add a test to make sure that negative effective values are filtered (Andrew Chow) 76d2f06 Benchmark BnB in the worst case where it exhausts (Andrew Chow) 6a34ff5 Have SelectCoinsMinConf and SelectCoins use BnB or Knapsack and use it (Andrew Chow) fab0488 Add a GetMinimumFeeRate function which is wrapped by GetMinimumFee (Andrew Chow) cd927ff Move original knapsack solver tests to coinselector_tests.cpp (Andrew Chow) fb716f7 Move current coin selection algorithm to coinselection.{cpp,h} (Andrew Chow) 4566ab7 Add tests for the Branch and Bound algorithm (Andrew Chow) 4b2716d Remove coinselection.h -> wallet.h circular dependency (Andrew Chow) 7d77eb1 Use a struct for output eligibility (Andrew Chow) ce7435c Move output eligibility to a separate function (Andrew Chow) 0185939 Implement Branch and Bound coin selection in a new file (Andrew Chow) f84fed8 Store effective value, fee, and long term fee in CInputCoin (Andrew Chow) 12ec29d Calculate and store the number of bytes required to spend an input (Andrew Chow) Pull request description: This is an implementation of the [Branch and Bound coin selection algorithm written by Murch](http://murch.one/wp-content/uploads/2016/11/erhardt2016coinselection.pdf) (@xekyo). I have it set so this algorithm will run first and if it fails, it will fall back to the current coin selection algorithm. The coin selection algorithms and tests have been refactored to separate files instead of having them all in wallet.cpp. I have added some tests for the new algorithm and a test for all of coin selection in general. However, more tests may be needed, but I will need help with coming up with more test cases. This PR uses some code borrowed from bitcoin#10360 to use effective values when selecting coins. Tree-SHA512: b0500f406bf671e74984fae78e2d0fbc5e321ddf4f06182c5855e9d1984c4ef2764c7586d03e16fa4b578c340b21710324926f9ca472d5447a0d1ed43eb4357e

@xekyo

73b5bf2 Add a test to make sure that negative effective values are filtered (Andrew Chow) 76d2f06 Benchmark BnB in the worst case where it exhausts (Andrew Chow) 6a34ff5 Have SelectCoinsMinConf and SelectCoins use BnB or Knapsack and use it (Andrew Chow) fab0488 Add a GetMinimumFeeRate function which is wrapped by GetMinimumFee (Andrew Chow) cd927ff Move original knapsack solver tests to coinselector_tests.cpp (Andrew Chow) fb716f7 Move current coin selection algorithm to coinselection.{cpp,h} (Andrew Chow) 4566ab7 Add tests for the Branch and Bound algorithm (Andrew Chow) 4b2716d Remove coinselection.h -> wallet.h circular dependency (Andrew Chow) 7d77eb1 Use a struct for output eligibility (Andrew Chow) ce7435c Move output eligibility to a separate function (Andrew Chow) 0185939 Implement Branch and Bound coin selection in a new file (Andrew Chow) f84fed8 Store effective value, fee, and long term fee in CInputCoin (Andrew Chow) 12ec29d Calculate and store the number of bytes required to spend an input (Andrew Chow) Pull request description: This is an implementation of the [Branch and Bound coin selection algorithm written by Murch](http://murch.one/wp-content/uploads/2016/11/erhardt2016coinselection.pdf) (@xekyo). I have it set so this algorithm will run first and if it fails, it will fall back to the current coin selection algorithm. The coin selection algorithms and tests have been refactored to separate files instead of having them all in wallet.cpp. I have added some tests for the new algorithm and a test for all of coin selection in general. However, more tests may be needed, but I will need help with coming up with more test cases. This PR uses some code borrowed from bitcoin#10360 to use effective values when selecting coins. Tree-SHA512: b0500f406bf671e74984fae78e2d0fbc5e321ddf4f06182c5855e9d1984c4ef2764c7586d03e16fa4b578c340b21710324926f9ca472d5447a0d1ed43eb4357e

instagibbs force-pushed the feedo branch from 6a22edd to e172717 Compare May 8, 2017 18:56

maflcko added the Wallet label May 8, 2017

instagibbs force-pushed the feedo branch 2 times, most recently from 122ed3d to 61792a2 Compare May 9, 2017 13:10

instagibbs added 11 commits May 16, 2017 10:37

remove maxTxFee check outside of GetMinimumFee

cc61e68

add FeeRate companions to Get_Fee wallet helpers

61ee854

Remove absolute fee estimator functions

d0947cf

rename Mempool GetMinFee to GetMinFeeRate

4ebea72

pull out pre-transaction-completion fee estimation outside main loop

0bc0ba3

replace GetRequiredFee with GetRequiredFeeRate

8e49f95

Move subtractFeeFromOutput logic to after full transaction fee estima…

c1ccde5

…tion

Avoid needless copying of coins list in SelectCoinsMinConf

4e3f409

move CalculateMaximumSignedTxSize to CWallet, use during tx creation

1ff6cd9

CalculateMaximumSignedTxSize returns -1 more consistently

fd42d9a

COutput caches marginal bytes to spend the output

ac04798

instagibbs force-pushed the feedo branch from e345c79 to 550783e Compare May 16, 2017 14:52

instagibbs added 5 commits May 16, 2017 11:42

coincontrol updateLabels uses precomputed input sizes

c04b88f

Use effective value of coins to target a defined feerate

e1c7677

f'coincontrol updateLabels uses precomputed input sizes'

53da55e

f'COutput caches marginal bytes to spend the output'

7c6e747

f'Use effective value of coins to target a defined feerate'

412d478

instagibbs force-pushed the feedo branch from 5d6b80a to 412d478 Compare May 16, 2017 15:43

f'Use effective value of coins to target a defined feerate'

8b39192

achow101 mentioned this pull request Jun 20, 2017

Coin Selection with Murch's algorithm #10637

Merged

instagibbs mentioned this pull request Jul 3, 2017

Add change output if necessary to reduce excess fee #10712

Merged

instagibbs closed this Feb 8, 2018

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

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

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

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

Uh oh!

instagibbs commented May 8, 2017 •

edited

Loading

Uh oh!

instagibbs commented May 8, 2017 •

edited

Loading

Uh oh!

morcos commented May 9, 2017

Uh oh!

instagibbs commented May 9, 2017

Uh oh!

instagibbs commented Jun 11, 2017

Uh oh!

instagibbs commented Feb 8, 2018

Uh oh!

Uh oh!

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

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

Uh oh!

Conversation

instagibbs commented May 8, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

instagibbs commented May 8, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

morcos commented May 9, 2017

Uh oh!

instagibbs commented May 9, 2017

Uh oh!

instagibbs commented Jun 11, 2017

Uh oh!

instagibbs commented Feb 8, 2018

Uh oh!

Uh oh!

instagibbs commented May 8, 2017 •

edited

Loading

instagibbs commented May 8, 2017 •

edited

Loading