Branch data Line data Source code
1 : : // Copyright (c) 2017-present The Bitcoin Core developers
2 : : // Distributed under the MIT software license, see the accompanying
3 : : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 : :
5 : : #ifndef BITCOIN_WALLET_COINSELECTION_H
6 : : #define BITCOIN_WALLET_COINSELECTION_H
7 : :
8 : : #include <consensus/amount.h>
9 : : #include <consensus/consensus.h>
10 : : #include <outputtype.h>
11 : : #include <policy/feerate.h>
12 : : #include <primitives/transaction.h>
13 : : #include <random.h>
14 : : #include <util/check.h>
15 : : #include <util/insert.h>
16 : : #include <util/result.h>
17 : :
18 : : #include <optional>
19 : :
20 : :
21 : : namespace wallet {
22 : : //! lower bound for randomly-chosen target change amount
23 : : inline constexpr CAmount CHANGE_LOWER{50'000};
24 : : //! upper bound for randomly-chosen target change amount
25 : : inline constexpr CAmount CHANGE_UPPER{1'000'000};
26 : :
27 : : /** A UTXO under consideration for use in funding a new transaction. */
28 [ + - ]: 2463030 : struct COutput {
29 : : private:
30 : : /** The output's value minus fees required to spend it and bump its unconfirmed ancestors to the target feerate. */
31 : : std::optional<CAmount> effective_value;
32 : :
33 : : /** The fee required to spend this output at the transaction's target feerate and to bump its unconfirmed ancestors to the target feerate. */
34 : : std::optional<CAmount> fee;
35 : :
36 : : public:
37 : : /** The outpoint identifying this UTXO */
38 : : COutPoint outpoint;
39 : :
40 : : /** The output itself */
41 : : CTxOut txout;
42 : :
43 : : /**
44 : : * Depth in block chain.
45 : : * If > 0: the tx is on chain and has this many confirmations.
46 : : * If = 0: the tx is waiting confirmation.
47 : : * If < 0: a conflicting tx is on chain and has this many confirmations. */
48 : : int depth;
49 : :
50 : : /** Pre-computed estimated size of this output as a fully-signed input in a transaction. Can be -1 if it could not be calculated */
51 : : int input_bytes;
52 : :
53 : : /** Whether we know how to spend this output, ignoring the lack of keys */
54 : : bool solvable;
55 : :
56 : : /**
57 : : * Whether this output is considered safe to spend. Unconfirmed transactions
58 : : * from outside keys and unconfirmed replacement transactions are considered
59 : : * unsafe and will not be used to fund new spending transactions.
60 : : */
61 : : bool safe;
62 : :
63 : : /** The time of the transaction containing this output as determined by CWalletTx::nTimeSmart */
64 : : int64_t time;
65 : :
66 : : /** Whether the transaction containing this output is sent from the owning wallet */
67 : : bool from_me;
68 : :
69 : : /** The fee required to spend this output at the consolidation feerate. */
70 : : CAmount long_term_fee{0};
71 : :
72 : : /** The fee necessary to bump this UTXO's ancestor transactions to the target feerate */
73 : : CAmount ancestor_bump_fees{0};
74 : :
75 : 775563 : COutput(const COutPoint& outpoint, const CTxOut& txout, int depth, int input_bytes, bool solvable, bool safe, int64_t time, bool from_me, const std::optional<CFeeRate> feerate = std::nullopt)
76 : 775563 : : outpoint{outpoint},
77 : 775563 : txout{txout},
78 : 775563 : depth{depth},
79 : 775563 : input_bytes{input_bytes},
80 : 775563 : solvable{solvable},
81 : 775563 : safe{safe},
82 : 775563 : time{time},
83 : 775563 : from_me{from_me}
84 : : {
85 [ + + ]: 775563 : if (feerate) {
86 : : // base fee without considering potential unconfirmed ancestors
87 [ + + + - : 264699 : fee = input_bytes < 0 ? 0 : feerate.value().GetFee(input_bytes);
+ - ]
88 [ + - ]: 264699 : effective_value = txout.nValue - fee.value();
89 : : }
90 : 775563 : }
91 : :
92 : 502750 : COutput(const COutPoint& outpoint, const CTxOut& txout, int depth, int input_bytes, bool solvable, bool safe, int64_t time, bool from_me, const CAmount fees)
93 : 502750 : : COutput(outpoint, txout, depth, input_bytes, solvable, safe, time, from_me)
94 : : {
95 : : // if input_bytes is unknown, then fees should be 0, if input_bytes is known, then the fees should be a positive integer or 0 (input_bytes known and fees = 0 only happens in the tests)
96 [ + + - + : 502750 : assert((input_bytes < 0 && fees == 0) || (input_bytes > 0 && fees >= 0));
+ - - + ]
97 [ + - ]: 502750 : fee = fees;
98 [ + - ]: 502750 : effective_value = txout.nValue - fee.value();
99 : 502750 : }
100 : :
101 : 2768628 : bool operator<(const COutput& rhs) const
102 : : {
103 : 2768628 : return outpoint < rhs.outpoint;
104 : : }
105 : :
106 : 148457 : void ApplyBumpFee(CAmount bump_fee)
107 : : {
108 [ - + ]: 148457 : assert(bump_fee >= 0);
109 : 148457 : ancestor_bump_fees = bump_fee;
110 [ - + ]: 148457 : assert(fee);
111 : 148457 : *fee += bump_fee;
112 : : // Note: assert(effective_value - bump_fee == nValue - fee.value());
113 : 148457 : effective_value = txout.nValue - fee.value();
114 : 148457 : }
115 : :
116 : 1521794 : CAmount GetFee() const
117 : : {
118 [ - + ]: 1521794 : assert(fee.has_value());
119 : 1521794 : return fee.value();
120 : : }
121 : :
122 : 1917896 : CAmount GetEffectiveValue() const
123 : : {
124 [ - + ]: 1917896 : assert(effective_value.has_value());
125 : 1917896 : return effective_value.value();
126 : : }
127 : :
128 [ + + + - ]: 272816 : bool HasEffectiveValue() const { return effective_value.has_value(); }
129 : : };
130 : :
131 : : /** Parameters for one iteration of Coin Selection. */
132 : : struct CoinSelectionParams {
133 : : /** Randomness to use in the context of coin selection. */
134 : : FastRandomContext& rng_fast;
135 : : /** Size of a change output in bytes, determined by the output type. */
136 : : int change_output_size = 0;
137 : : /** Size of the input to spend a change output in virtual bytes. */
138 : : int change_spend_size = 0;
139 : : /** Mininmum change to target in Knapsack solver and CoinGrinder:
140 : : * select coins to cover the payment and at least this value of change. */
141 : : CAmount m_min_change_target{0};
142 : : /** Minimum amount for creating a change output.
143 : : * If change budget is smaller than min_change then we forgo creation of change output.
144 : : */
145 : : CAmount min_viable_change{0};
146 : : /** Cost of creating the change output. */
147 : : CAmount m_change_fee{0};
148 : : /** Cost of creating the change output + cost of spending the change output in the future. */
149 : : CAmount m_cost_of_change{0};
150 : : /** The targeted feerate of the transaction being built. */
151 : : CFeeRate m_effective_feerate;
152 : : /** The feerate estimate used to estimate an upper bound on what should be sufficient to spend
153 : : * the change output sometime in the future. */
154 : : CFeeRate m_long_term_feerate;
155 : : /** If the cost to spend a change output at the discard feerate exceeds its value, drop it to fees. */
156 : : CFeeRate m_discard_feerate;
157 : : /** Size of the transaction before coin selection, consisting of the header and recipient
158 : : * output(s), excluding the inputs and change output(s). */
159 : : int tx_noinputs_size = 0;
160 : : /** Indicate that we are subtracting the fee from outputs */
161 : : bool m_subtract_fee_outputs = false;
162 : : /** When true, always spend all (up to OUTPUT_GROUP_MAX_ENTRIES) or none of the outputs
163 : : * associated with the same address. This helps reduce privacy leaks resulting from address
164 : : * reuse. Dust outputs are not eligible to be added to output groups and thus not considered. */
165 : : bool m_avoid_partial_spends = false;
166 : : /**
167 : : * When true, allow unsafe coins to be selected during Coin Selection. This may spend unconfirmed outputs:
168 : : * 1) Received from other wallets, 2) replacing other txs, 3) that have been replaced.
169 : : */
170 : : bool m_include_unsafe_inputs = false;
171 : : /** The version of the transaction we are trying to create. */
172 : : uint32_t m_version{CTransaction::CURRENT_VERSION};
173 : : /** The maximum weight for this transaction. */
174 : : std::optional<int> m_max_tx_weight{std::nullopt};
175 : :
176 : 3703 : CoinSelectionParams(FastRandomContext& rng_fast, int change_output_size, int change_spend_size,
177 : : CAmount min_change_target, CFeeRate effective_feerate,
178 : : CFeeRate long_term_feerate, CFeeRate discard_feerate, int tx_noinputs_size, bool avoid_partial,
179 : : std::optional<int> max_tx_weight = std::nullopt)
180 : 3703 : : rng_fast{rng_fast},
181 : 3703 : change_output_size(change_output_size),
182 : 3703 : change_spend_size(change_spend_size),
183 : 3703 : m_min_change_target(min_change_target),
184 : 3703 : m_effective_feerate(effective_feerate),
185 : 3703 : m_long_term_feerate(long_term_feerate),
186 : 3703 : m_discard_feerate(discard_feerate),
187 : 3703 : tx_noinputs_size(tx_noinputs_size),
188 : 3703 : m_avoid_partial_spends(avoid_partial),
189 [ + - + - : 3703 : m_max_tx_weight(max_tx_weight)
+ - + - +
- + - +
+ ]
190 : : {
191 : : }
192 : 3828 : CoinSelectionParams(FastRandomContext& rng_fast)
193 : 3828 : : rng_fast{rng_fast} {}
194 : : };
195 : :
196 : : /** Parameters for filtering which OutputGroups we may use in coin selection.
197 : : * We start by being very selective and requiring multiple confirmations and
198 : : * then get more permissive if we cannot fund the transaction. */
199 : : struct CoinEligibilityFilter
200 : : {
201 : : /** Minimum number of confirmations for outputs that we sent to ourselves.
202 : : * We may use unconfirmed UTXOs sent from ourselves, e.g. change outputs. */
203 : : const int conf_mine;
204 : : /** Minimum number of confirmations for outputs received from a different wallet. */
205 : : const int conf_theirs;
206 : : /** Maximum number of unconfirmed ancestors aggregated across all UTXOs in an OutputGroup. */
207 : : const uint64_t max_ancestors;
208 : : /** Maximum cluster count that a single UTXO in the OutputGroup may have. In practice, this filter also caps the
209 : : * maximum descendant count, as a transaction's descendant count is never larger than its cluster count. */
210 : : const uint64_t max_cluster_count;
211 : : /** When avoid_reuse=true and there are full groups (OUTPUT_GROUP_MAX_ENTRIES), whether or not to use any partial groups.*/
212 : : const bool m_include_partial_groups{false};
213 : :
214 : : CoinEligibilityFilter() = delete;
215 [ + - ]: 6780 : CoinEligibilityFilter(int conf_mine, int conf_theirs, uint64_t max_ancestors) : conf_mine(conf_mine), conf_theirs(conf_theirs), max_ancestors(max_ancestors), max_cluster_count(max_ancestors) {}
216 [ + - + - ]: 3384 : CoinEligibilityFilter(int conf_mine, int conf_theirs, uint64_t max_ancestors, uint64_t max_cluster_count) : conf_mine(conf_mine), conf_theirs(conf_theirs), max_ancestors(max_ancestors), max_cluster_count(max_cluster_count) {}
217 [ + - + - : 3512 : CoinEligibilityFilter(int conf_mine, int conf_theirs, uint64_t max_ancestors, uint64_t max_cluster_count, bool include_partial) : conf_mine(conf_mine), conf_theirs(conf_theirs), max_ancestors(max_ancestors), max_cluster_count(max_cluster_count), m_include_partial_groups(include_partial) {}
+ - ][ + -
- - - - ]
218 : :
219 : 5775212 : bool operator<(const CoinEligibilityFilter& other) const {
220 : 5775212 : return std::tie(conf_mine, conf_theirs, max_ancestors, max_cluster_count, m_include_partial_groups)
221 : 5775212 : < std::tie(other.conf_mine, other.conf_theirs, other.max_ancestors, other.max_cluster_count, other.m_include_partial_groups);
222 : : }
223 : : };
224 : :
225 : : /** A group of UTXOs paid to the same output script. */
226 [ + - + - : 23869068 : struct OutputGroup
+ - + - +
- ][ + - ]
[ + + - - ]
227 : : {
228 : : /** The list of UTXOs contained in this output group. */
229 : : std::vector<std::shared_ptr<COutput>> m_outputs;
230 : : /** Whether the UTXOs were sent by the wallet to itself. This is relevant because we may want at
231 : : * least a certain number of confirmations on UTXOs received from outside wallets while trusting
232 : : * our own UTXOs more. */
233 : : bool m_from_me{true};
234 : : /** The total value of the UTXOs in sum. */
235 : : CAmount m_value{0};
236 : : /** The minimum number of confirmations the UTXOs in the group have. Unconfirmed is 0. */
237 : : int m_depth{999};
238 : : /** The aggregated count of unconfirmed ancestors of all UTXOs in this
239 : : * group. Not deduplicated and may overestimate when ancestors are shared. */
240 : : size_t m_ancestors{0};
241 : : /** The maximum cluster count of a single UTXO in this output group. */
242 : : size_t m_max_cluster_count{0};
243 : : /** The value of the UTXOs after deducting the cost of spending them at the effective feerate. */
244 : : CAmount effective_value{0};
245 : : /** The fee to spend these UTXOs at the effective feerate. */
246 : : CAmount fee{0};
247 : : /** The fee to spend these UTXOs at the long term feerate. */
248 : : CAmount long_term_fee{0};
249 : : /** The feerate for spending a created change output eventually (i.e. not urgently, and thus at
250 : : * a lower feerate). Calculated using long term fee estimate. This is used to decide whether
251 : : * it could be economical to create a change output. */
252 : : CFeeRate m_long_term_feerate{0};
253 : : /** Indicate that we are subtracting the fee from outputs.
254 : : * When true, the value that is used for coin selection is the UTXO's real value rather than effective value */
255 : : bool m_subtract_fee_outputs{false};
256 : : /** Total weight of the UTXOs in this group. */
257 : : int m_weight{0};
258 : :
259 : 225015 : OutputGroup() = default;
260 : 1095909 : OutputGroup(const CoinSelectionParams& params) :
261 [ + - ]: 1095909 : m_long_term_feerate(params.m_long_term_feerate),
262 [ + - ]: 1095909 : m_subtract_fee_outputs(params.m_subtract_fee_outputs)
263 : : {}
264 : :
265 : : void Insert(const std::shared_ptr<COutput>& output, size_t ancestors, size_t cluster_count);
266 : : bool EligibleForSpending(const CoinEligibilityFilter& eligibility_filter) const;
267 : : CAmount GetSelectionAmount() const;
268 : : };
269 : :
270 [ + - ]: 34343 : struct Groups {
271 : : // Stores 'OutputGroup' containing only positive UTXOs (value > 0).
272 : : std::vector<OutputGroup> positive_group;
273 : : // Stores 'OutputGroup' which may contain both positive and negative UTXOs.
274 : : std::vector<OutputGroup> mixed_group;
275 : : };
276 : :
277 : : /** Stores several 'Groups' whose were mapped by output type. */
278 : 17865 : struct OutputGroupTypeMap
279 : : {
280 : : // Maps output type to output groups.
281 : : std::map<OutputType, Groups> groups_by_type;
282 : : // All inserted groups, no type distinction.
283 : : Groups all_groups;
284 : :
285 : : // Based on the insert flag; appends group to the 'mixed_group' and, if value > 0, to the 'positive_group'.
286 : : // This affects both; the groups filtered by type and the overall groups container.
287 : : void Push(const OutputGroup& group, OutputType type, bool insert_positive, bool insert_mixed);
288 : : // Different output types count
289 [ + + ]: 122 : size_t TypesCount() { return groups_by_type.size(); }
290 : : };
291 : :
292 : : typedef std::map<CoinEligibilityFilter, OutputGroupTypeMap> FilteredOutputGroups;
293 : :
294 : : /** Choose a random change target for each transaction to make it harder to fingerprint the Core
295 : : * wallet based on the change output values of transactions it creates.
296 : : * Change target covers at least change fees and adds a random value on top of it.
297 : : * The random value is between 50ksat and min(2 * payment_value, 1milsat)
298 : : * When payment_value <= 25ksat, the value is just 50ksat.
299 : : *
300 : : * Making change amounts similar to the payment value may help disguise which output(s) are payments
301 : : * are which ones are change. Using double the payment value may increase the number of inputs
302 : : * needed (and thus be more expensive in fees), but breaks analysis techniques which assume the
303 : : * coins selected are just sufficient to cover the payment amount ("unnecessary input" heuristic).
304 : : *
305 : : * @param[in] payment_value Average payment value of the transaction output(s).
306 : : * @param[in] change_fee Fee for creating a change output.
307 : : */
308 : : [[nodiscard]] CAmount GenerateChangeTarget(CAmount payment_value, CAmount change_fee, FastRandomContext& rng);
309 : :
310 : : enum class SelectionAlgorithm : uint8_t
311 : : {
312 : : BNB = 0,
313 : : KNAPSACK = 1,
314 : : SRD = 2,
315 : : CG = 3,
316 : : MANUAL = 4,
317 : : };
318 : :
319 : : std::string GetAlgorithmName(SelectionAlgorithm algo);
320 : :
321 : : struct OutputPtrComparator {
322 : 2768628 : bool operator()(const std::shared_ptr<COutput>& a, const std::shared_ptr<COutput>& b) const {
323 [ + + + - : 2768628 : return *a < *b;
+ + + + -
- - - - -
- - ][ - +
+ + + - ]
324 : : }
325 : : };
326 : : using OutputSet = std::set<std::shared_ptr<COutput>, OutputPtrComparator>;
327 : :
328 [ + - + - : 101122 : struct SelectionResult
+ - + - +
- + - + -
+ - + - ]
329 : : {
330 : : private:
331 : : /** Set of inputs selected by the algorithm to use in the transaction */
332 : : OutputSet m_selected_inputs;
333 : : /** The target the algorithm selected for. Equal to the recipient amount plus non-input fees */
334 : : CAmount m_target;
335 : : /** The algorithm used to produce this result */
336 : : SelectionAlgorithm m_algo;
337 : : /** Whether the input values for calculations should be the effective value (true) or normal value (false) */
338 : : bool m_use_effective{false};
339 : : /** The computed waste */
340 : : std::optional<CAmount> m_waste;
341 : : /** False if algorithm was cut short by hitting limit of attempts and solution is non-optimal */
342 : : bool m_algo_completed{true};
343 : : /** The count of selections that were evaluated by this coin selection attempt */
344 : : size_t m_selections_evaluated;
345 : : /** Total weight of the selected inputs */
346 : : int m_weight{0};
347 : : /** How much individual inputs overestimated the bump fees for the shared ancestry */
348 : : CAmount bump_fee_group_discount{0};
349 : :
350 : : template<typename T>
351 : 248598 : void InsertInputs(const T& inputs)
352 : : {
353 : : // Store sum of combined input sets to check that the results have no shared UTXOs
354 [ - + ]: 248598 : const size_t expected_count = m_selected_inputs.size() + inputs.size();
355 : 248598 : util::insert(m_selected_inputs, inputs);
356 [ - + ]: 248598 : if (m_selected_inputs.size() != expected_count) {
357 [ # # # # ]: 0 : throw std::runtime_error(STR_INTERNAL_BUG("Shared UTXOs among selection results"));
358 : : }
359 : 248598 : }
360 : :
361 : : public:
362 : 21366 : explicit SelectionResult(const CAmount target, SelectionAlgorithm algo)
363 [ + + + - : 21366 : : m_target(target), m_algo(algo) {}
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - ]
[ - + + - ]
364 : :
365 : : SelectionResult() = delete;
366 : :
367 : : /** Get the sum of the input values */
368 : : [[nodiscard]] CAmount GetSelectedValue() const;
369 : :
370 : : [[nodiscard]] CAmount GetSelectedEffectiveValue() const;
371 : :
372 : : [[nodiscard]] CAmount GetTotalBumpFees() const;
373 : :
374 : : void Clear();
375 : :
376 : : void AddInput(const OutputGroup& group);
377 : : void AddInputs(const OutputSet& inputs, bool subtract_fee_outputs);
378 : :
379 : : /** How much individual inputs overestimated the bump fees for shared ancestries */
380 : : void SetBumpFeeDiscount(CAmount discount);
381 : :
382 : : /** Calculates and stores the waste for this result given the cost of change
383 : : * and the opportunity cost of spending these inputs now vs in the future.
384 : : * If change exists, waste = change_cost + inputs * (effective_feerate - long_term_feerate) - bump_fee_group_discount
385 : : * If no change, waste = excess + inputs * (effective_feerate - long_term_feerate) - bump_fee_group_discount
386 : : * where excess = selected_effective_value - target
387 : : * change_cost = effective_feerate * change_output_size + long_term_feerate * change_spend_size
388 : : *
389 : : * @param[in] min_viable_change The minimum amount necessary to make a change output economic
390 : : * @param[in] change_cost The cost of creating a change output and spending it in the future. Only
391 : : * used if there is change, in which case it must be non-negative.
392 : : * @param[in] change_fee The fee for creating a change output
393 : : */
394 : : void RecalculateWaste(CAmount min_viable_change, CAmount change_cost, CAmount change_fee);
395 : : [[nodiscard]] CAmount GetWaste() const;
396 : :
397 : : /** Tracks that algorithm was able to exhaustively search the entire combination space before hitting limit of tries */
398 : : void SetAlgoCompleted(bool algo_completed);
399 : :
400 : : /** Get m_algo_completed */
401 : : bool GetAlgoCompleted() const;
402 : :
403 : : /** Record the number of selections that were evaluated */
404 : : void SetSelectionsEvaluated(size_t attempts);
405 : :
406 : : /** Get selections_evaluated */
407 : : size_t GetSelectionsEvaluated() const ;
408 : :
409 : : /**
410 : : * Combines the @param[in] other selection result into 'this' selection result.
411 : : *
412 : : * Important note:
413 : : * There must be no shared 'COutput' among the two selection results being combined.
414 : : */
415 : : void Merge(const SelectionResult& other);
416 : :
417 : : /** Get m_selected_inputs */
418 : : const OutputSet& GetInputSet() const;
419 : : /** Get the vector of COutputs that will be used to fill in a CTransaction's vin */
420 : : std::vector<std::shared_ptr<COutput>> GetShuffledInputVector() const;
421 : :
422 : : bool operator<(SelectionResult other) const;
423 : :
424 : : /** Get the amount for the change output after paying needed fees.
425 : : *
426 : : * The change amount is not 100% precise due to discrepancies in fee calculation.
427 : : * The final change amount (if any) should be corrected after calculating the final tx fees.
428 : : * When there is a discrepancy, most of the time the final change would be slightly bigger than estimated.
429 : : *
430 : : * Following are the possible factors of discrepancy:
431 : : * + non-input fees always include segwit flags
432 : : * + input fee estimation always include segwit stack size
433 : : * + input fees are rounded individually and not collectively, which leads to small rounding errors
434 : : * - input counter size is always assumed to be 1vbyte
435 : : *
436 : : * @param[in] min_viable_change Minimum amount for change output, if change would be less then we forgo change
437 : : * @param[in] change_fee Fees to include change output in the tx
438 : : * @returns Amount for change output, 0 when there is no change.
439 : : *
440 : : */
441 : : CAmount GetChange(CAmount min_viable_change, CAmount change_fee) const;
442 : :
443 : : CAmount GetTarget() const { return m_target; }
444 : :
445 [ + - + - ]: 3712 : SelectionAlgorithm GetAlgo() const { return m_algo; }
[ + - ]
446 : :
447 [ + - + + : 3325 : int GetWeight() const { return m_weight; }
+ - + - ]
[ + + + + ]
[ - + ]
448 : : };
449 : :
450 : : util::Result<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change,
451 : : int max_selection_weight);
452 : :
453 : : util::Result<SelectionResult> CoinGrinder(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, CAmount change_target, int max_selection_weight);
454 : :
455 : : /** Select coins by Single Random Draw (SRD). SRD selects eligible OutputGroups from a shuffled
456 : : * ordering until the effective value of the input set suffices to create the recipient outputs and a
457 : : * change output with an amount of at least CHANGE_LOWER. While the maximum selection
458 : : * weight is exceeded during selection, the OutputGroup with the lowest effective value is dropped
459 : : * from the selection before additional OutputGroups are selected. Due to this greedy approach,
460 : : * SRD can fail to discover possible solutions in pathological cases.
461 : : *
462 : : * @param[in] utxo_pool The positive effective value OutputGroups eligible for selection
463 : : * @param[in] target_value The target value to select for
464 : : * @param[in] change_fee The cost of adding the change output to the transaction at the transaction’s feerate.
465 : : * @param[in] rng The randomness source to shuffle coins
466 : : * @param[in] max_selection_weight The maximum allowed weight for a selection result to be valid
467 : : * @returns If successful, a valid SelectionResult, otherwise, util::Error
468 : : */
469 : : util::Result<SelectionResult> SelectCoinsSRD(const std::vector<OutputGroup>& utxo_pool, CAmount target_value, CAmount change_fee, FastRandomContext& rng,
470 : : int max_selection_weight);
471 : :
472 : : // Original coin selection algorithm as a fallback
473 : : util::Result<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups, const CAmount& nTargetValue,
474 : : CAmount change_target, FastRandomContext& rng, int max_selection_weight);
475 : : } // namespace wallet
476 : :
477 : : #endif // BITCOIN_WALLET_COINSELECTION_H
|
