Line data Source code
1 : // Copyright (c) 2017-2022 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 : static constexpr CAmount CHANGE_LOWER{50000};
24 : //! upper bound for randomly-chosen target change amount
25 : static constexpr CAmount CHANGE_UPPER{1000000};
26 :
27 : /** A UTXO under consideration for use in funding a new transaction. */
28 : 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 have the private keys to spend this output */
54 : bool spendable;
55 :
56 : /** Whether we know how to spend this output, ignoring the lack of keys */
57 : bool solvable;
58 :
59 : /**
60 : * Whether this output is considered safe to spend. Unconfirmed transactions
61 : * from outside keys and unconfirmed replacement transactions are considered
62 : * unsafe and will not be used to fund new spending transactions.
63 : */
64 : bool safe;
65 :
66 : /** The time of the transaction containing this output as determined by CWalletTx::nTimeSmart */
67 : int64_t time;
68 :
69 : /** Whether the transaction containing this output is sent from the owning wallet */
70 : bool from_me;
71 :
72 : /** The fee required to spend this output at the consolidation feerate. */
73 0 : CAmount long_term_fee{0};
74 :
75 : /** The fee necessary to bump this UTXO's ancestor transactions to the target feerate */
76 0 : CAmount ancestor_bump_fees{0};
77 :
78 0 : COutput(const COutPoint& outpoint, const CTxOut& txout, int depth, int input_bytes, bool spendable, bool solvable, bool safe, int64_t time, bool from_me, const std::optional<CFeeRate> feerate = std::nullopt)
79 0 : : outpoint{outpoint},
80 0 : txout{txout},
81 0 : depth{depth},
82 0 : input_bytes{input_bytes},
83 0 : spendable{spendable},
84 0 : solvable{solvable},
85 0 : safe{safe},
86 0 : time{time},
87 0 : from_me{from_me}
88 : {
89 0 : if (feerate) {
90 : // base fee without considering potential unconfirmed ancestors
91 0 : fee = input_bytes < 0 ? 0 : feerate.value().GetFee(input_bytes);
92 0 : effective_value = txout.nValue - fee.value();
93 0 : }
94 0 : }
95 :
96 : COutput(const COutPoint& outpoint, const CTxOut& txout, int depth, int input_bytes, bool spendable, bool solvable, bool safe, int64_t time, bool from_me, const CAmount fees)
97 : : COutput(outpoint, txout, depth, input_bytes, spendable, solvable, safe, time, from_me)
98 : {
99 : // 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)
100 : assert((input_bytes < 0 && fees == 0) || (input_bytes > 0 && fees >= 0));
101 : fee = fees;
102 : effective_value = txout.nValue - fee.value();
103 : }
104 :
105 : std::string ToString() const;
106 :
107 : bool operator<(const COutput& rhs) const
108 : {
109 : return outpoint < rhs.outpoint;
110 : }
111 :
112 0 : void ApplyBumpFee(CAmount bump_fee)
113 : {
114 0 : assert(bump_fee >= 0);
115 0 : ancestor_bump_fees = bump_fee;
116 0 : assert(fee);
117 0 : *fee += bump_fee;
118 : // Note: assert(effective_value - bump_fee == nValue - fee.value());
119 0 : effective_value = txout.nValue - fee.value();
120 0 : }
121 :
122 0 : CAmount GetFee() const
123 : {
124 0 : assert(fee.has_value());
125 0 : return fee.value();
126 : }
127 :
128 0 : CAmount GetEffectiveValue() const
129 : {
130 0 : assert(effective_value.has_value());
131 0 : return effective_value.value();
132 : }
133 :
134 0 : bool HasEffectiveValue() const { return effective_value.has_value(); }
135 : };
136 :
137 : /** Parameters for one iteration of Coin Selection. */
138 : struct CoinSelectionParams {
139 : /** Randomness to use in the context of coin selection. */
140 : FastRandomContext& rng_fast;
141 : /** Size of a change output in bytes, determined by the output type. */
142 0 : size_t change_output_size = 0;
143 : /** Size of the input to spend a change output in virtual bytes. */
144 0 : size_t change_spend_size = 0;
145 : /** Mininmum change to target in Knapsack solver: select coins to cover the payment and
146 : * at least this value of change. */
147 0 : CAmount m_min_change_target{0};
148 : /** Minimum amount for creating a change output.
149 : * If change budget is smaller than min_change then we forgo creation of change output.
150 : */
151 0 : CAmount min_viable_change{0};
152 : /** Cost of creating the change output. */
153 0 : CAmount m_change_fee{0};
154 : /** Cost of creating the change output + cost of spending the change output in the future. */
155 0 : CAmount m_cost_of_change{0};
156 : /** The targeted feerate of the transaction being built. */
157 : CFeeRate m_effective_feerate;
158 : /** The feerate estimate used to estimate an upper bound on what should be sufficient to spend
159 : * the change output sometime in the future. */
160 : CFeeRate m_long_term_feerate;
161 : /** If the cost to spend a change output at the discard feerate exceeds its value, drop it to fees. */
162 : CFeeRate m_discard_feerate;
163 : /** Size of the transaction before coin selection, consisting of the header and recipient
164 : * output(s), excluding the inputs and change output(s). */
165 0 : size_t tx_noinputs_size = 0;
166 : /** Indicate that we are subtracting the fee from outputs */
167 0 : bool m_subtract_fee_outputs = false;
168 : /** When true, always spend all (up to OUTPUT_GROUP_MAX_ENTRIES) or none of the outputs
169 : * associated with the same address. This helps reduce privacy leaks resulting from address
170 : * reuse. Dust outputs are not eligible to be added to output groups and thus not considered. */
171 0 : bool m_avoid_partial_spends = false;
172 : /**
173 : * When true, allow unsafe coins to be selected during Coin Selection. This may spend unconfirmed outputs:
174 : * 1) Received from other wallets, 2) replacing other txs, 3) that have been replaced.
175 : */
176 0 : bool m_include_unsafe_inputs = false;
177 :
178 : CoinSelectionParams(FastRandomContext& rng_fast, size_t change_output_size, size_t change_spend_size,
179 : CAmount min_change_target, CFeeRate effective_feerate,
180 : CFeeRate long_term_feerate, CFeeRate discard_feerate, size_t tx_noinputs_size, bool avoid_partial)
181 : : rng_fast{rng_fast},
182 : change_output_size(change_output_size),
183 : change_spend_size(change_spend_size),
184 : m_min_change_target(min_change_target),
185 : m_effective_feerate(effective_feerate),
186 : m_long_term_feerate(long_term_feerate),
187 : m_discard_feerate(discard_feerate),
188 : tx_noinputs_size(tx_noinputs_size),
189 : m_avoid_partial_spends(avoid_partial)
190 : {
191 : }
192 0 : CoinSelectionParams(FastRandomContext& rng_fast)
193 0 : : 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 number of descendants that a single UTXO in the OutputGroup may have. */
209 : const uint64_t max_descendants;
210 : /** When avoid_reuse=true and there are full groups (OUTPUT_GROUP_MAX_ENTRIES), whether or not to use any partial groups.*/
211 0 : const bool m_include_partial_groups{false};
212 :
213 : CoinEligibilityFilter() = delete;
214 0 : CoinEligibilityFilter(int conf_mine, int conf_theirs, uint64_t max_ancestors) : conf_mine(conf_mine), conf_theirs(conf_theirs), max_ancestors(max_ancestors), max_descendants(max_ancestors) {}
215 0 : CoinEligibilityFilter(int conf_mine, int conf_theirs, uint64_t max_ancestors, uint64_t max_descendants) : conf_mine(conf_mine), conf_theirs(conf_theirs), max_ancestors(max_ancestors), max_descendants(max_descendants) {}
216 0 : CoinEligibilityFilter(int conf_mine, int conf_theirs, uint64_t max_ancestors, uint64_t max_descendants, bool include_partial) : conf_mine(conf_mine), conf_theirs(conf_theirs), max_ancestors(max_ancestors), max_descendants(max_descendants), m_include_partial_groups(include_partial) {}
217 :
218 0 : bool operator<(const CoinEligibilityFilter& other) const {
219 0 : return std::tie(conf_mine, conf_theirs, max_ancestors, max_descendants, m_include_partial_groups)
220 0 : < std::tie(other.conf_mine, other.conf_theirs, other.max_ancestors, other.max_descendants, other.m_include_partial_groups);
221 : }
222 : };
223 :
224 : /** A group of UTXOs paid to the same output script. */
225 : struct OutputGroup
226 : {
227 : /** The list of UTXOs contained in this output group. */
228 : std::vector<std::shared_ptr<COutput>> m_outputs;
229 : /** Whether the UTXOs were sent by the wallet to itself. This is relevant because we may want at
230 : * least a certain number of confirmations on UTXOs received from outside wallets while trusting
231 : * our own UTXOs more. */
232 0 : bool m_from_me{true};
233 : /** The total value of the UTXOs in sum. */
234 0 : CAmount m_value{0};
235 : /** The minimum number of confirmations the UTXOs in the group have. Unconfirmed is 0. */
236 0 : int m_depth{999};
237 : /** The aggregated count of unconfirmed ancestors of all UTXOs in this
238 : * group. Not deduplicated and may overestimate when ancestors are shared. */
239 0 : size_t m_ancestors{0};
240 : /** The maximum count of descendants of a single UTXO in this output group. */
241 0 : size_t m_descendants{0};
242 : /** The value of the UTXOs after deducting the cost of spending them at the effective feerate. */
243 0 : CAmount effective_value{0};
244 : /** The fee to spend these UTXOs at the effective feerate. */
245 0 : CAmount fee{0};
246 : /** The fee to spend these UTXOs at the long term feerate. */
247 0 : CAmount long_term_fee{0};
248 : /** The feerate for spending a created change output eventually (i.e. not urgently, and thus at
249 : * a lower feerate). Calculated using long term fee estimate. This is used to decide whether
250 : * it could be economical to create a change output. */
251 : CFeeRate m_long_term_feerate{0};
252 : /** Indicate that we are subtracting the fee from outputs.
253 : * When true, the value that is used for coin selection is the UTXO's real value rather than effective value */
254 : bool m_subtract_fee_outputs{false};
255 : /** Total weight of the UTXOs in this group. */
256 0 : int m_weight{0};
257 :
258 : OutputGroup() {}
259 0 : OutputGroup(const CoinSelectionParams& params) :
260 0 : m_long_term_feerate(params.m_long_term_feerate),
261 0 : m_subtract_fee_outputs(params.m_subtract_fee_outputs)
262 0 : {}
263 :
264 : void Insert(const std::shared_ptr<COutput>& output, size_t ancestors, size_t descendants);
265 : bool EligibleForSpending(const CoinEligibilityFilter& eligibility_filter) const;
266 : CAmount GetSelectionAmount() const;
267 : };
268 :
269 : struct Groups {
270 : // Stores 'OutputGroup' containing only positive UTXOs (value > 0).
271 : std::vector<OutputGroup> positive_group;
272 : // Stores 'OutputGroup' which may contain both positive and negative UTXOs.
273 : std::vector<OutputGroup> mixed_group;
274 : };
275 :
276 : /** Stores several 'Groups' whose were mapped by output type. */
277 : struct OutputGroupTypeMap
278 : {
279 : // Maps output type to output groups.
280 : std::map<OutputType, Groups> groups_by_type;
281 : // All inserted groups, no type distinction.
282 : Groups all_groups;
283 :
284 : // Based on the insert flag; appends group to the 'mixed_group' and, if value > 0, to the 'positive_group'.
285 : // This affects both; the groups filtered by type and the overall groups container.
286 : void Push(const OutputGroup& group, OutputType type, bool insert_positive, bool insert_mixed);
287 : // Different output types count
288 0 : size_t TypesCount() { return groups_by_type.size(); }
289 : };
290 :
291 : typedef std::map<CoinEligibilityFilter, OutputGroupTypeMap> FilteredOutputGroups;
292 :
293 : /** Choose a random change target for each transaction to make it harder to fingerprint the Core
294 : * wallet based on the change output values of transactions it creates.
295 : * Change target covers at least change fees and adds a random value on top of it.
296 : * The random value is between 50ksat and min(2 * payment_value, 1milsat)
297 : * When payment_value <= 25ksat, the value is just 50ksat.
298 : *
299 : * Making change amounts similar to the payment value may help disguise which output(s) are payments
300 : * are which ones are change. Using double the payment value may increase the number of inputs
301 : * needed (and thus be more expensive in fees), but breaks analysis techniques which assume the
302 : * coins selected are just sufficient to cover the payment amount ("unnecessary input" heuristic).
303 : *
304 : * @param[in] payment_value Average payment value of the transaction output(s).
305 : * @param[in] change_fee Fee for creating a change output.
306 : */
307 : [[nodiscard]] CAmount GenerateChangeTarget(const CAmount payment_value, const CAmount change_fee, FastRandomContext& rng);
308 :
309 : enum class SelectionAlgorithm : uint8_t
310 : {
311 : BNB = 0,
312 : KNAPSACK = 1,
313 : SRD = 2,
314 : MANUAL = 3,
315 : };
316 :
317 : std::string GetAlgorithmName(const SelectionAlgorithm algo);
318 :
319 : struct SelectionResult
320 : {
321 : private:
322 : /** Set of inputs selected by the algorithm to use in the transaction */
323 : std::set<std::shared_ptr<COutput>> m_selected_inputs;
324 : /** The target the algorithm selected for. Equal to the recipient amount plus non-input fees */
325 : CAmount m_target;
326 : /** The algorithm used to produce this result */
327 : SelectionAlgorithm m_algo;
328 : /** Whether the input values for calculations should be the effective value (true) or normal value (false) */
329 0 : bool m_use_effective{false};
330 : /** The computed waste */
331 : std::optional<CAmount> m_waste;
332 : /** Total weight of the selected inputs */
333 0 : int m_weight{0};
334 : /** How much individual inputs overestimated the bump fees for the shared ancestry */
335 0 : CAmount bump_fee_group_discount{0};
336 :
337 : template<typename T>
338 0 : void InsertInputs(const T& inputs)
339 : {
340 : // Store sum of combined input sets to check that the results have no shared UTXOs
341 0 : const size_t expected_count = m_selected_inputs.size() + inputs.size();
342 0 : util::insert(m_selected_inputs, inputs);
343 0 : if (m_selected_inputs.size() != expected_count) {
344 0 : throw std::runtime_error(STR_INTERNAL_BUG("Shared UTXOs among selection results"));
345 : }
346 0 : }
347 :
348 : /** Compute the waste for this result given the cost of change
349 : * and the opportunity cost of spending these inputs now vs in the future.
350 : * If change exists, waste = change_cost + inputs * (effective_feerate - long_term_feerate)
351 : * If no change, waste = excess + inputs * (effective_feerate - long_term_feerate)
352 : * where excess = selected_effective_value - target
353 : * change_cost = effective_feerate * change_output_size + long_term_feerate * change_spend_size
354 : *
355 : * @param[in] change_cost The cost of creating change and spending it in the future.
356 : * Only used if there is change, in which case it must be positive.
357 : * Must be 0 if there is no change.
358 : * @param[in] target The amount targeted by the coin selection algorithm.
359 : * @param[in] use_effective_value Whether to use the input's effective value (when true) or the real value (when false).
360 : * @return The waste
361 : */
362 : [[nodiscard]] CAmount GetSelectionWaste(CAmount change_cost, CAmount target, bool use_effective_value = true);
363 :
364 : public:
365 0 : explicit SelectionResult(const CAmount target, SelectionAlgorithm algo)
366 0 : : m_target(target), m_algo(algo) {}
367 :
368 : SelectionResult() = delete;
369 :
370 : /** Get the sum of the input values */
371 : [[nodiscard]] CAmount GetSelectedValue() const;
372 :
373 : [[nodiscard]] CAmount GetSelectedEffectiveValue() const;
374 :
375 : [[nodiscard]] CAmount GetTotalBumpFees() const;
376 :
377 : void Clear();
378 :
379 : void AddInput(const OutputGroup& group);
380 : void AddInputs(const std::set<std::shared_ptr<COutput>>& inputs, bool subtract_fee_outputs);
381 :
382 : /** How much individual inputs overestimated the bump fees for shared ancestries */
383 : void SetBumpFeeDiscount(const CAmount discount);
384 :
385 : /** Calculates and stores the waste for this selection via GetSelectionWaste */
386 : void ComputeAndSetWaste(const CAmount min_viable_change, const CAmount change_cost, const CAmount change_fee);
387 : [[nodiscard]] CAmount GetWaste() const;
388 :
389 : /**
390 : * Combines the @param[in] other selection result into 'this' selection result.
391 : *
392 : * Important note:
393 : * There must be no shared 'COutput' among the two selection results being combined.
394 : */
395 : void Merge(const SelectionResult& other);
396 :
397 : /** Get m_selected_inputs */
398 : const std::set<std::shared_ptr<COutput>>& GetInputSet() const;
399 : /** Get the vector of COutputs that will be used to fill in a CTransaction's vin */
400 : std::vector<std::shared_ptr<COutput>> GetShuffledInputVector() const;
401 :
402 : bool operator<(SelectionResult other) const;
403 :
404 : /** Get the amount for the change output after paying needed fees.
405 : *
406 : * The change amount is not 100% precise due to discrepancies in fee calculation.
407 : * The final change amount (if any) should be corrected after calculating the final tx fees.
408 : * When there is a discrepancy, most of the time the final change would be slightly bigger than estimated.
409 : *
410 : * Following are the possible factors of discrepancy:
411 : * + non-input fees always include segwit flags
412 : * + input fee estimation always include segwit stack size
413 : * + input fees are rounded individually and not collectively, which leads to small rounding errors
414 : * - input counter size is always assumed to be 1vbyte
415 : *
416 : * @param[in] min_viable_change Minimum amount for change output, if change would be less then we forgo change
417 : * @param[in] change_fee Fees to include change output in the tx
418 : * @returns Amount for change output, 0 when there is no change.
419 : *
420 : */
421 : CAmount GetChange(const CAmount min_viable_change, const CAmount change_fee) const;
422 :
423 0 : CAmount GetTarget() const { return m_target; }
424 :
425 : SelectionAlgorithm GetAlgo() const { return m_algo; }
426 :
427 0 : int GetWeight() const { return m_weight; }
428 : };
429 :
430 : util::Result<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change,
431 : int max_weight);
432 :
433 : /** Select coins by Single Random Draw. OutputGroups are selected randomly from the eligible
434 : * outputs until the target is satisfied
435 : *
436 : * @param[in] utxo_pool The positive effective value OutputGroups eligible for selection
437 : * @param[in] target_value The target value to select for
438 : * @param[in] rng The randomness source to shuffle coins
439 : * @param[in] max_weight The maximum allowed weight for a selection result to be valid
440 : * @returns If successful, a valid SelectionResult, otherwise, util::Error
441 : */
442 : util::Result<SelectionResult> SelectCoinsSRD(const std::vector<OutputGroup>& utxo_pool, CAmount target_value, CAmount change_fee, FastRandomContext& rng,
443 : int max_weight);
444 :
445 : // Original coin selection algorithm as a fallback
446 : util::Result<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups, const CAmount& nTargetValue,
447 : CAmount change_target, FastRandomContext& rng, int max_weight);
448 : } // namespace wallet
449 :
450 : #endif // BITCOIN_WALLET_COINSELECTION_H
|
