aboutsummaryrefslogtreecommitdiff
path: root/src/wallet/coinselection.cpp
AgeCommit message (Collapse)Author
2023-01-03Merge bitcoin/bitcoin#26661: wallet: Coin Selection, return accurate error ↵Andrew Chow
messages 76dc547ee7b05864e7b1b6c55fc0301d47aa3a15 gui: create tx, launch error dialog if backend throws runtime_error (furszy) f4d79477ff0946b0bd340ade9251fa38e3b95dd7 wallet: coin selection, add duplicated inputs checks (furszy) 0aa065b14e67592d5be8f46ebbe5d59a083ff0a5 wallet: return accurate error messages from Coin Selection (furszy) 7e8340ab1a970a14e180b1fcf420b46a5657b062 wallet: make SelectCoins flow return util::Result (furszy) e5e147fe97f706e82bc51358f8bdc355f355be57 wallet: refactor eight consecutive 'AttemptSelection' calls into a loop (furszy) Pull request description: Work decoupled from #25806, which cleanup and improves the Coin Selection flow further. Adding the capability to propagate specific error messages from the Coin Selection process to the user. Instead of always returning the general "Insufficient funds" message which is not always accurate to what happened internally. Letting us instruct the user how to proceed under certain circumstances. The following error messages were added: 1) If the selection result exceeds the maximum transaction weight, we now will return: -> "The inputs size exceeds the maximum weight. Please try sending a smaller amount or manually consolidating your wallet's UTXOs". 2) If the user pre-selected inputs and disallowed the automatic coin selection process (no other inputs are allowed), we now will return: -> "The preselected coins total amount does not cover the transaction target. Please allow other inputs to be automatically selected or include more coins manually". 3) The double-counted preset inputs during Coin Selection error will now throw an "internal bug detected" message instead of crashing the node. The essence of this work comes from several comments: 1. https://github.com/bitcoin/bitcoin/pull/26560#discussion_r1037395665 2. https://github.com/bitcoin/bitcoin/pull/25729#discussion_r940619491 3. https://github.com/bitcoin/bitcoin/pull/25269#pullrequestreview-1135240825 4. https://github.com/bitcoin/bitcoin/issues/23144 (which is connected to #24845) ACKs for top commit: ishaanam: crACK 76dc547ee7b05864e7b1b6c55fc0301d47aa3a15 achow101: ACK 76dc547ee7b05864e7b1b6c55fc0301d47aa3a15 aureleoules: ACK 76dc547ee7b05864e7b1b6c55fc0301d47aa3a15 theStack: ACK 76dc547ee7b05864e7b1b6c55fc0301d47aa3a15 :city_sunrise: Tree-SHA512: 9de30792d7a5849cae77747aa978e70390b66ee9d082779a56088a024f82e725b0af050e6603aece0ac8229f6d73bc471ba97b4ab69dc7eddf419f5f56ae89a5
2023-01-03Merge bitcoin/bitcoin#25932: refactor: Simplify backtrack logicAndrew Chow
81d4a2b14ff65fe07085ef2a967a466015370ce3 refactor: Move feerate comparison invariant outside of the loop (yancy) 365aca40453995163bbd17231251512f9f9a103b refactor: Simplify feerate comparison statement (yancy) Pull request description: This is a small nit, however I think it's more understandable to write: `utxo_pool.at(0).fee > utxo_pool.at(0).long_term_fee` vs `(utxo_pool.at(0).fee - utxo_pool.at(0).long_term_fee) > 0` ACKs for top commit: Xekyo: ACK 81d4a2b14ff65fe07085ef2a967a466015370ce3 achow101: ACK 81d4a2b14ff65fe07085ef2a967a466015370ce3 aureleoules: ACK 81d4a2b14ff65fe07085ef2a967a466015370ce3 Tree-SHA512: 3e89377989c36716b53114fe40178261671dde5688075fab1c21ec173ac310f8c84ed6af90354d7c329176cb7262dfcaa7191fd19847d3b7147a9a10c3e31176
2022-12-24scripted-diff: Bump copyright headersHennadii Stepanov
-BEGIN VERIFY SCRIPT- ./contrib/devtools/copyright_header.py update ./ -END VERIFY SCRIPT- Commits of previous years: - 2021: f47dda2c58b5d8d623e0e7ff4e74bc352dfa83d7 - 2020: fa0074e2d82928016a43ca408717154a1c70a4db - 2019: aaaaad6ac95b402fe18d019d67897ced6b316ee0
2022-12-21wallet: coin selection, add duplicated inputs checksfurszy
As no process should be able to trigger this error using the regular transaction creation process, throw a runtime_error if happens to tell users/devs to report the bug if happens.
2022-12-05wallet: Check max tx weight in coin selectorAurèle Oulès
Co-authored-by: Andrew Chow <github@achow101.com>
2022-12-02wallet: add assert to SelectionResult::Merge for safetyS3RK
2022-10-26wallet: encapsulate pre-selected-inputs lookup into its own functionfurszy
First step towards decoupling the pre-selected-inputs fetching functionality from `SelectCoins`. Which, will let us not waste resources calculating the available coins if one of the pre-set inputs has an error. (right now, if one of the pre-set inputs is invalid, we first walk through the entire wallet txes map just to end up failing right after it finish)
2022-09-17refactor: Move feerate comparison invariant outside of the loopyancy
2022-09-16refactor: Simplify feerate comparison statementyancy
2022-08-15wallet: use GetChange() when computing wasteS3RK
2022-08-15wallet: add SelectionResult::GetChangeS3RK
2022-08-15wallet: add SelectionResult::MergeS3RK
2022-08-15wallet: accurate SelectionResult::m_targetS3RK
SelectionResult::m_target should be equal to actual selection target. Selection target is the sum of all recipient amounts plus non input fees. So we need to remove change_fee from the m_target. It's safe because change target is always greater than the change fee, so we can always cover fees if change output is created.
2022-08-15wallet: ensure m_min_change_target always covers change feeS3RK
2022-06-28Revert "bnb: exit selection when best_waste is 0"Murch
This reverts commit 9b5950db8683f9b4be03f79ee0aae8a780b01a4b. Waste can be negative. At feerates lower than long_term_feerate this means that a waste of 0 may be a suboptimal solution and this causes the search to exit prematurely. Only when the feerate is equal to the long_term_feerate would achieving a waste of 0 indicate that we have achieved an optimal solution, because it would mean that the excess is 0. It seems unlikely that this would ever occur outside of test cases, and even then we should prefer solutions with more inputs over solutions with fewer according to previous decisions—but solutions with more inputs are found later in the branch exploration. The "optimization" described in #18257 and implemented in #18262 is therefore a premature exit on a suboptimal solution and should be reverted.
2022-05-25logging: Unconditionally log levels >= WARNlaanwj
Messages with level `WARN` or higher should be logged even when the category is not provided with `-debug=`, to make sure important warnings are not lost.
2022-05-21Set effective_value when initializing a COutputishaanam
Previously in COutput, effective_value was initialized as the absolute value of the txout, and fee as 0. effective_value along with fee were calculated outside of the COutput constructor and set after the object had been initialized. These changes will allow either the fee or the feerate to be passed in a COutput constructor. If either are provided, fee and effective_value are calculated and set in the constructor. As a result, AvailableCoins also needs to be passed the feerate when utxos are being spent. When balance is calculated or the coins are being listed and feerate is neither available nor required, AvailableCoinsListUnspent is used instead, which runs AvailableCoins while providing the default value for feerate. Unit tests for the calculation of effective value have also been added.
2022-04-14wallet: track which coin selection algorithm produced a SelectionResultAndrew Chow
2022-03-25[wallet] randomly generate change targetsglozow
If the wallet always chooses 1 million sats as its change target, it is easier to fingerprint transactions created by the Core wallet.
2022-03-25refactor coin selection for parameterizable change targetglozow
no behavior changes, since the target is always MIN_CHANGE
2022-03-24Merge bitcoin/bitcoin#24091: wallet: Consolidate CInputCoin and COutputfanquake
049003fe68a4183f6f20da16f58f10079d1e02df coinselection: Remove COutput operators == and != (Andrew Chow) f6c39c6adb6cbf9c87f04d3d667701905ef5c0a0 coinselection: Remove CInputCoin (Andrew Chow) 70f31f1a81710aa59e95770de9a84bf58cbce1e8 coinselection: Use COutput instead of CInputCoin (Andrew Chow) 14fbb57b79c664090f6a4e60d7bdfc9759ff4307 coinselection: Add effective value and fees to COutput (Andrew Chow) f0821230b8de2eec21a869d1edf9e2b9f502de25 moveonly: move COutput to coinselection.h (Andrew Chow) 42e974e15c6deba1d9395a4da9341c9ebec6e8e5 wallet: Remove CWallet and CWalletTx from COutput's constructor (Andrew Chow) 14d04d5ad15ae56df56edee7ca9a202b52037889 wallet: Replace CWalletTx in COutput with COutPoint and CTxOut (Andrew Chow) 0ba4d1916e26e2a5d603edcdb7625463989d25b6 wallet: Provide input bytes to COutput (Andrew Chow) d51f27d3bb0d6e3ca55bcd23ce53e4fe413a9360 wallet: Store whether a COutput is from the wallet (Andrew Chow) b799814bbd53736b79495072f3c9e05989a465e8 wallet: Store tx time in COutput (Andrew Chow) 46022953ee2e8113167bafd1fd48a383a578b13c wallet: Remove use_max_sig default value (Andrew Chow) 10379f007fd2c18f4cd24d0a0783d6d929f45556 scripted-diff: Rename COutput member variables (Andrew Chow) c7c64db41e1718584aa2f30ff27f60ab0966de62 wallet: cleanup COutput constructor (Andrew Chow) Pull request description: While working on coin selection code, it occurred to me that `CInputCoin` is really a subset of `COutput` and the conversion of a `COutput` to a `CInputCoin` does not appear to be all that useful. So this PR adds fields that are present in `CInputCoin` to `COutput` and replaces the usage of `CInputCoin` with `COutput`. `COutput` is also moved to coinselection.h. As part of this move, the usage of `CWalletTx` is removed from `COutput`. It is instead replaced by storing a `COutPoint` and the `CTxOut` rather than the entire `CWalletTx` as coin selection does not really need the full `CWalletTx`. The `CWalletTx` was only used for figuring out whether the transaction containing the output was from the current wallet, and for the transaction's time. These are now parameters to `COutput`'s constructor. ACKs for top commit: ryanofsky: Code review ACK 049003fe68a4183f6f20da16f58f10079d1e02df, just adding comments and removing == operators since last review w0xlt: reACK 049003f Xekyo: reACK 049003fe68a4183f6f20da16f58f10079d1e02df Tree-SHA512: 048b4cd620a0415e1d9fe8597257ee4bc64656566e1d28a9bdd147d6d72dc87c3f34a3339fa9ab6acf42c388df7901fc4ee900ccaabc3de790ffad162b544c15
2022-03-23coinselection: Use COutput instead of CInputCoinAndrew Chow
Also rename setPresetCoins to preset_coins
2022-03-23moveonly: move COutput to coinselection.hAndrew Chow
2022-03-23Merge bitcoin/bitcoin#24560: wallet: Use single FastRandomContext when ↵Andrew Chow
creating a wallet tx fa7deaa0464576a229b5a6ab13ad033c16d0dada wallet: Pass FastRandomContext& to coin selection (MarcoFalke) 77773b061cb13229a8afb46f6f3ab89fc70eabe3 wallet: Pass FastRandomContext& to DiscourageFeeSniping (MarcoFalke) Pull request description: Passing around a single randomness context shouldn't come with any downsides, but documents better where randomness is used and allows the unit test to be deterministic, if they wish to be so. ACKs for top commit: achow101: ACK fa7deaa0464576a229b5a6ab13ad033c16d0dada promag: Code review ACK fa7deaa0464576a229b5a6ab13ad033c16d0dada. glozow: light code review ACK fa7deaa0464576a229b5a6ab13ad033c16d0dada Tree-SHA512: c16287708cc82ce58311710595d0127af42fb156c93fbcaa5bde634ce323d325f4d8c99a74af24423ab22b5ad58163dd771e8b1a0e7d6bff39c9fb2a1cb21bc7
2022-03-21Merge bitcoin/bitcoin#13226: Optimize SelectCoinsBnB by tracking the ↵Andrew Chow
selection by index rather than by position 9d2005285c77f6c4148bccfa0b8b9135abfa021c doc: Revise comments and whitespace to clarify (Ben Woosley) def43a4d888b4a21c082404d1b25707c481d7625 refactor: Rename i to curr_try in SelectCoinsBnB (Ben Woosley) 1dd092367789749527777ac2b256e639f5706584 refactor: Track BnB selection by index (Ben Woosley) Pull request description: This is prompted by #13167 and presented as a friendly alternative to it. IMO you can improve code readability and performance by about 20% by tracking the selected utxos by index, rather than by position. This reduces the storage access complexity from roughly O(utxo_size) to O(selection_size). On my machine (median of 5 trials): ``` BnBExhaustion, 5, 650, 2.2564, 0.000672999, 0.000711565, 0.000693112 - master BnBExhaustion, 5, 650, 1.76232, 0.000528563, 0.000568806, 0.000539147 - this PR ``` ACKs for top commit: achow101: reACK 9d2005285c77f6c4148bccfa0b8b9135abfa021c glozow: code review ACK 9d2005285c77f6c4148bccfa0b8b9135abfa021c Xekyo: reACK 9d2005285c77f6c4148bccfa0b8b9135abfa021c Tree-SHA512: 453ea11ad58c48928dc76956e3e98916f6924e95510eb02fe89a899ff102fe9cc08a04d557f381ad0218a210275e5383101d971c1ffad38b06b1c57d81144315
2022-03-14wallet: Pass FastRandomContext& to coin selectionMarcoFalke
2022-03-14doc: Revise comments and whitespace to clarifyBen Woosley
2022-03-14refactor: Rename i to curr_try in SelectCoinsBnBBen Woosley
Clarifies purpose and removes name collisions with other indicies.
2022-03-14refactor: Track BnB selection by indexBen Woosley
This is a performance optimization - rather than track all visited values in a bool vector, track the selected index in a vector. This results in a complexity reduction of O(utxo_size) to O(selection_size).
2022-03-11[wallet] assert BnB internally calculated waste is the same as ↵glozow
GetSelectionWaste() These two implementations of waste calculation should never deviate. Still keep the SelectCoinsBnB internal calculation because incremental calculate-as-you-go is much more performant than calling GetSelectionWaste() over and over again.
2022-01-06Add src/wallet/* code to wallet:: namespaceRussell Yanofsky
2021-12-30scripted-diff: Bump copyright headersHennadii Stepanov
-BEGIN VERIFY SCRIPT- ./contrib/devtools/copyright_header.py update ./ -END VERIFY SCRIPT- Commits of previous years: * 2020: fa0074e2d82928016a43ca408717154a1c70a4db * 2019: aaaaad6ac95b402fe18d019d67897ced6b316ee0
2021-12-13wallet: Replace Assume with Assert where needed in coinselectionMarcoFalke
2021-12-09Merge bitcoin/bitcoin#22019: wallet: Introduce SelectionResult for ↵W. J. van der Laan
encapsulating a coin selection solution 05300c14392facf38330eb4fcd8e695a838b76f3 Use SelectionResult in SelectCoins (Andrew Chow) 9d9b101d2019d8237546eedd022e74519feb07bb Use SelectionResult in AttemptSelection (Andrew Chow) bb50850a447bdf461ffb76d47d4a4db904fce324 Use SelectionResult for waste calculation (Andrew Chow) e8f7ae5eb3c682d1a80b503f71e06ce76af1b65c Make an OutputGroup for preset inputs (Andrew Chow) 51a9c00b4de707e0a6a1a68ca6f8e38d86c72d94 Return SelectionResult from SelectCoinsSRD (Andrew Chow) 0ef6184575e77b17f5ec6d7ca086900aca79f6d7 Return SelectionResult from KnapsackSolver (Andrew Chow) 60d2ca72e3f4c56433c63b929a88e7a2def06399 Return SelectionResult from SelectCoinsBnB (Andrew Chow) a339add471717623915cd1a846ade4dab2c89deb Make member variables of SelectionResult private (Andrew Chow) cbf0b9f4ff438865a71c7ceb0a543c18a34f41f0 scripted-diff: Use SelectionResult in coin selector tests (Andrew Chow) 9d1d86da04d5d4768975338841285e90b01130b8 Introduce SelectionResult struct (Andrew Chow) 94d851d28cb909a8f1f8ab795f1d9fc74bebfc7f Fix bnb_search_test to use set equivalence for (Andrew Chow) Pull request description: Instead of returning a set of selected coins and their total value as separate items, encapsulate both of these, and other variables, into a new `SelectionResult` struct. This allows us to have all of the things relevant to a coin selection solution be in a single object. `SelectionResult` enables us to implement the waste calculation in a cleaner way. All of the coin selection functions (`SelectCoinsBnB`, `KnapsackSolver`, `AttemptSelection`, and `SelectCoins`) are changed to use a `SelectionResult` as the output parameter. Based on #22009 ACKs for top commit: laanwj: Code review ACK 05300c14392facf38330eb4fcd8e695a838b76f3 Tree-SHA512: e4dbb4d78a6cda9c237d230b19e7265591efac5a101a64e6970f0654e2c4f93d13bb5d07b98e8c7b8d37321753dbfc94c28c3a7810cb1c59b5bc29b08a8493ef
2021-12-05Return SelectionResult from SelectCoinsSRDAndrew Chow
Changes SelectCoinsSRD to return a SelectionResult.
2021-12-05Return SelectionResult from KnapsackSolverAndrew Chow
Returns a std::optional<SelectionResult> from KnapsackSolver instead of using out parameters for the inputs set and selected value.
2021-12-05Return SelectionResult from SelectCoinsBnBAndrew Chow
Removes coins_out and value_ret has SelectCoinsBnB return a std::optional<SelectionResult>
2021-12-05Introduce SelectionResult structAndrew Chow
Introduces a SelectionResult struct which contains the set of selected inputs and the total transaction fee for the transaction. This will be used by the various SelectCoins* functions. Additionally helpers are provided to compute the total input value and result comparisons.
2021-10-11Fix typo and grammarHeebs
Fix typo and grammar in the coin selection algorithm's description.
2021-10-05Merge bitcoin/bitcoin#22951: consensus: move amount.h into consensusMarcoFalke
9d0379cea6c164610d05287ae6dd4e66f35b92b3 consensus: use <cstdint> over <stdint.h> in amount.h (fanquake) 863e52fe63a67fa020fb1ef527b9095a35ab77a5 consensus: make COIN & MAX_MONEY constexpr (fanquake) d09071da5bc997f2de1f55ca7a9babc3d7619329 [MOVEONLY] consensus: move amount.h into consensus (fanquake) Pull request description: A first step (of a few) towards some source code reorganization, as well as making libbitcoinconsensus slightly more self contained. Related to #15732. ACKs for top commit: MarcoFalke: concept ACK 9d0379cea6c164610d05287ae6dd4e66f35b92b 🏝 Tree-SHA512: 97fc79262dcb8c00996852a288fee69ddf8398ae2c95700bba5b326f1f38ffcfaf8fa66e29d0cb446d9b3f4e608a96525fae0c2ad9cd531ad98ad2a4a687cd6a
2021-09-30Merge bitcoin/bitcoin#23104: log: Avoid breaking single log lines over ↵W. J. van der Laan
multiple lines in the log file 2222c04e1b9960030cb590c789a0d2375add4544 log: Adjust coin selection log string (MarcoFalke) fa6c1e850f3a96f884ba8a635b72d3abea1f4e56 test: Fix typos in tests (MarcoFalke) faeae2980fa2493391cdced20950a991e28cf47d log: Avoid broken DEBUG_LOCKORDER log (MarcoFalke) faffaa85cde32b621f598a8ea8dceae34f33f021 log: Avoid broken SELECTCOINS log (MarcoFalke) Pull request description: Follow up to commit d8b4b3077fd20c90b635eff1dd240bdad9725027 ACKs for top commit: laanwj: re-ACK 2222c04e1b9960030cb590c789a0d2375add4544 practicalswift: cr ACK 2222c04e1b9960030cb590c789a0d2375add4544 Tree-SHA512: e0daf76815a1b7c4898ceffedeaf7ede093223abf709874f9a0d78c8e41551c14e8b56d055c8fdf06ec698df64e67dfc168bbd8716131b23648d1d1294fa6636
2021-09-30[MOVEONLY] consensus: move amount.h into consensusfanquake
Move amount.h to consensus/amount.h. Renames, adds missing and removes uneeded includes.
2021-09-29log: Adjust coin selection log stringMarcoFalke
Replace the outdated function name with words from the English language. Logging the function name can be toggled with -logsourcelocations.
2021-09-27log: Avoid broken SELECTCOINS logMarcoFalke
Before this patch, the log might be corrupted by other threads logging at the same time. For example, another RPC thread: [httpworker.1] [default wallet] keypool reserve 1296 [httpworker.1] SelectCoins() best subset: Received a POST request for / from 127.0.0.1:53732 [httpworker.3] ThreadRPCServer method=getnetworkinfo user=__cookie__ [httpworker.1] 0.78125 0.1953125 0.02441406 0.00610351 0.00305175 0.00152587 total 1.01025417
2021-09-23Add SelectCoinsSRD functionAndrew Chow
2021-08-27Add waste metric calculation functionAndrew Chow
2021-08-13wallet: Use GetSelectionAmount for target value calculationsAndrew Chow
For target value calculations, GetSelectionAmount should be used, not m_effective_value or m_value. Specifically, ApproximateBestSubset mistakenly uses m_value when calculating whether the target value has been met. This has been changed to use GetSelectionAmount.
2021-05-19Have OutputGroup determine the value to useAndrew Chow
Instead of hijacking the effective_feerate to use the correct value during coin selection, have OutputGroup be aware of whether we are subtracting the fee from the outputs and provide the correct value to use for selection. To do this, OutputGroup now takes CoinSelectionParams and has a new function GetSelectionAmount().
2021-05-19Have KnapsackSolver actually use effective valuesAndrew Chow
Although the CreateTransaction loop currently remains, it should be largely unused. KnapsackSolver will now account for transaction fees when doing its selection. In the previous commit, SelectCoinsMinConf was refactored to have some calculations become shared for KnapsackSolver and SelectCoinsBnB. In this commit, KnapsackSolver will now use the not_input_fees and effective_feerate so that it include the fee for non-input things (excluding a change output) so that the algorithm will select enough to cover those fees. This is necessary for selecting on effective values. Additionally, the OutputGroups created for KnapsackSolver will actually have their effective values calculated and set, and KnapsackSolver will do its selection on those effective values. Lastly, SelectCoins is modified to use the same value for preselected inputs for BnB and KnapsackSolver. While it will still use the real value when subtracting the fee from outputs, this behavior will be the same regardless of the algo used for selecting additional inputs.
2021-05-19Roll static tx fees into nValueToSelect instead of having it be separateAndrew Chow
The fees for transaction overhead and recipient outputs are now included in nTargetValue instead of being a separate parameter. For the coin selection algorithms, it doesn't matter that these are separate as in either case, the algorithm needs to select enough to cover these fees. Note that setting nValueToSelect is changed as it now includes not_input_fees. Without the change to how nValueToSelect is increased for KnapsackSolver, this would result in overpaying fees. The change to increase by the difference between nFeeRet and not_input_fees allows this to have the same behavior as previously. Additionally, because we assume that KnapsackSolver will always find a solution that requires change (we assume that BnB always finds a non-change solution), we also include the fee for the change output in KnapsackSolver's target. As part of this, we also use the changeless nFeeRet when iterating for KnapsackSolver. This is because we include the change fee when doing KnapsackSolver, so nFeeRet on further iterations won't include the change fee.
generated by cgit v1.2.3 (git 2.26.2) at 2024-11-09 09:45:10 +0000