Line data Source code
1 : // Copyright (c) 2017-2021 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 <policy/feerate.h>
10 : #include <primitives/transaction.h>
11 : #include <random.h>
12 : #include <util/result.h>
13 :
14 : #include <optional>
15 :
16 : namespace wallet {
17 : //! lower bound for randomly-chosen target change amount
18 : static constexpr CAmount CHANGE_LOWER{50000};
19 : //! upper bound for randomly-chosen target change amount
20 : static constexpr CAmount CHANGE_UPPER{1000000};
21 :
22 : /** A UTXO under consideration for use in funding a new transaction. */
23 : struct COutput {
24 : private:
25 : /** The output's value minus fees required to spend it.*/
26 : std::optional<CAmount> effective_value;
27 :
28 : /** The fee required to spend this output at the transaction's target feerate. */
29 : std::optional<CAmount> fee;
30 :
31 : public:
32 : /** The outpoint identifying this UTXO */
33 : COutPoint outpoint;
34 :
35 : /** The output itself */
36 : CTxOut txout;
37 :
38 : /**
39 : * Depth in block chain.
40 : * If > 0: the tx is on chain and has this many confirmations.
41 : * If = 0: the tx is waiting confirmation.
42 : * If < 0: a conflicting tx is on chain and has this many confirmations. */
43 : int depth;
44 :
45 : /** Pre-computed estimated size of this output as a fully-signed input in a transaction. Can be -1 if it could not be calculated */
46 : int input_bytes;
47 :
48 : /** Whether we have the private keys to spend this output */
49 : bool spendable;
50 :
51 : /** Whether we know how to spend this output, ignoring the lack of keys */
52 : bool solvable;
53 :
54 : /**
55 : * Whether this output is considered safe to spend. Unconfirmed transactions
56 : * from outside keys and unconfirmed replacement transactions are considered
57 : * unsafe and will not be used to fund new spending transactions.
58 : */
59 : bool safe;
60 :
61 : /** The time of the transaction containing this output as determined by CWalletTx::nTimeSmart */
62 : int64_t time;
63 :
64 : /** Whether the transaction containing this output is sent from the owning wallet */
65 : bool from_me;
66 :
67 : /** The fee required to spend this output at the consolidation feerate. */
68 167841 : CAmount long_term_fee{0};
69 :
70 335682 : 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)
71 167841 : : outpoint{outpoint},
72 167841 : txout{txout},
73 167841 : depth{depth},
74 167841 : input_bytes{input_bytes},
75 167841 : spendable{spendable},
76 167841 : solvable{solvable},
77 167841 : safe{safe},
78 167841 : time{time},
79 167841 : from_me{from_me}
80 167841 : {
81 167841 : if (feerate) {
82 117637 : fee = input_bytes < 0 ? 0 : feerate.value().GetFee(input_bytes);
83 117637 : effective_value = txout.nValue - fee.value();
84 117637 : }
85 335682 : }
86 :
87 50133 : 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)
88 50133 : : COutput(outpoint, txout, depth, input_bytes, spendable, solvable, safe, time, from_me)
89 : {
90 : // 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)
91 50133 : assert((input_bytes < 0 && fees == 0) || (input_bytes > 0 && fees >= 0));
92 50133 : fee = fees;
93 50133 : effective_value = txout.nValue - fee.value();
94 50133 : }
95 :
96 : std::string ToString() const;
97 :
98 1941264 : bool operator<(const COutput& rhs) const
99 : {
100 1941264 : return outpoint < rhs.outpoint;
101 : }
102 :
103 910839 : CAmount GetFee() const
104 : {
105 910839 : assert(fee.has_value());
106 910839 : return fee.value();
107 : }
108 :
109 1032938 : CAmount GetEffectiveValue() const
110 : {
111 1032938 : assert(effective_value.has_value());
112 1032938 : return effective_value.value();
113 : }
114 : };
115 :
116 : /** Parameters for one iteration of Coin Selection. */
117 : struct CoinSelectionParams {
118 : /** Randomness to use in the context of coin selection. */
119 : FastRandomContext& rng_fast;
120 : /** Size of a change output in bytes, determined by the output type. */
121 226 : size_t change_output_size = 0;
122 : /** Size of the input to spend a change output in virtual bytes. */
123 226 : size_t change_spend_size = 0;
124 : /** Mininmum change to target in Knapsack solver: select coins to cover the payment and
125 : * at least this value of change. */
126 226 : CAmount m_min_change_target{0};
127 : /** Cost of creating the change output. */
128 3731 : CAmount m_change_fee{0};
129 : /** Cost of creating the change output + cost of spending the change output in the future. */
130 3731 : CAmount m_cost_of_change{0};
131 : /** The fee to spend these UTXOs at the long term feerate. */
132 : CFeeRate m_effective_feerate;
133 : /** The feerate estimate used to estimate an upper bound on what should be sufficient to spend
134 : * the change output sometime in the future. */
135 : CFeeRate m_long_term_feerate;
136 : /** If the cost to spend a change output at the discard feerate exceeds its value, drop it to fees. */
137 : CFeeRate m_discard_feerate;
138 226 : size_t tx_noinputs_size = 0;
139 : /** Indicate that we are subtracting the fee from outputs */
140 3731 : bool m_subtract_fee_outputs = false;
141 : /** When true, always spend all (up to OUTPUT_GROUP_MAX_ENTRIES) or none of the outputs
142 : * associated with the same address. This helps reduce privacy leaks resulting from address
143 : * reuse. Dust outputs are not eligible to be added to output groups and thus not considered. */
144 226 : bool m_avoid_partial_spends = false;
145 :
146 7010 : CoinSelectionParams(FastRandomContext& rng_fast, size_t change_output_size, size_t change_spend_size,
147 : CAmount min_change_target, CFeeRate effective_feerate,
148 : CFeeRate long_term_feerate, CFeeRate discard_feerate, size_t tx_noinputs_size, bool avoid_partial)
149 3505 : : rng_fast{rng_fast},
150 3505 : change_output_size(change_output_size),
151 3505 : change_spend_size(change_spend_size),
152 3505 : m_min_change_target(min_change_target),
153 3505 : m_effective_feerate(effective_feerate),
154 3505 : m_long_term_feerate(long_term_feerate),
155 3505 : m_discard_feerate(discard_feerate),
156 3505 : tx_noinputs_size(tx_noinputs_size),
157 3505 : m_avoid_partial_spends(avoid_partial)
158 3505 : {
159 7010 : }
160 678 : CoinSelectionParams(FastRandomContext& rng_fast)
161 678 : : rng_fast{rng_fast} {}
162 : };
163 :
164 : /** Parameters for filtering which OutputGroups we may use in coin selection.
165 : * We start by being very selective and requiring multiple confirmations and
166 : * then get more permissive if we cannot fund the transaction. */
167 : struct CoinEligibilityFilter
168 : {
169 : /** Minimum number of confirmations for outputs that we sent to ourselves.
170 : * We may use unconfirmed UTXOs sent from ourselves, e.g. change outputs. */
171 : const int conf_mine;
172 : /** Minimum number of confirmations for outputs received from a different wallet. */
173 : const int conf_theirs;
174 : /** Maximum number of unconfirmed ancestors aggregated across all UTXOs in an OutputGroup. */
175 : const uint64_t max_ancestors;
176 : /** Maximum number of descendants that a single UTXO in the OutputGroup may have. */
177 : const uint64_t max_descendants;
178 : /** When avoid_reuse=true and there are full groups (OUTPUT_GROUP_MAX_ENTRIES), whether or not to use any partial groups.*/
179 689 : const bool m_include_partial_groups{false};
180 :
181 2019 : 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) {}
182 48 : 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) {}
183 16 : 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) {}
184 : };
185 :
186 : /** A group of UTXOs paid to the same output script. */
187 : struct OutputGroup
188 : {
189 : /** The list of UTXOs contained in this output group. */
190 : std::vector<COutput> m_outputs;
191 : /** Whether the UTXOs were sent by the wallet to itself. This is relevant because we may want at
192 : * least a certain number of confirmations on UTXOs received from outside wallets while trusting
193 : * our own UTXOs more. */
194 875584 : bool m_from_me{true};
195 : /** The total value of the UTXOs in sum. */
196 875584 : CAmount m_value{0};
197 : /** The minimum number of confirmations the UTXOs in the group have. Unconfirmed is 0. */
198 875584 : int m_depth{999};
199 : /** The aggregated count of unconfirmed ancestors of all UTXOs in this
200 : * group. Not deduplicated and may overestimate when ancestors are shared. */
201 875584 : size_t m_ancestors{0};
202 : /** The maximum count of descendants of a single UTXO in this output group. */
203 875584 : size_t m_descendants{0};
204 : /** The value of the UTXOs after deducting the cost of spending them at the effective feerate. */
205 875584 : CAmount effective_value{0};
206 : /** The fee to spend these UTXOs at the effective feerate. */
207 875584 : CAmount fee{0};
208 : /** The target feerate of the transaction we're trying to build. */
209 276722 : CFeeRate m_effective_feerate{0};
210 : /** The fee to spend these UTXOs at the long term feerate. */
211 875584 : CAmount long_term_fee{0};
212 : /** The feerate for spending a created change output eventually (i.e. not urgently, and thus at
213 : * a lower feerate). Calculated using long term fee estimate. This is used to decide whether
214 : * it could be economical to create a change output. */
215 276722 : CFeeRate m_long_term_feerate{0};
216 : /** Indicate that we are subtracting the fee from outputs.
217 : * When true, the value that is used for coin selection is the UTXO's real value rather than effective value */
218 276722 : bool m_subtract_fee_outputs{false};
219 :
220 830166 : OutputGroup() {}
221 1197724 : OutputGroup(const CoinSelectionParams& params) :
222 598862 : m_effective_feerate(params.m_effective_feerate),
223 598862 : m_long_term_feerate(params.m_long_term_feerate),
224 598862 : m_subtract_fee_outputs(params.m_subtract_fee_outputs)
225 1197724 : {}
226 :
227 : void Insert(const COutput& output, size_t ancestors, size_t descendants, bool positive_only);
228 : bool EligibleForSpending(const CoinEligibilityFilter& eligibility_filter, bool isISLocked) const;
229 : CAmount GetSelectionAmount() const;
230 : };
231 :
232 : /** Compute the waste for this result given the cost of change
233 : * and the opportunity cost of spending these inputs now vs in the future.
234 : * If change exists, waste = change_cost + inputs * (effective_feerate - long_term_feerate)
235 : * If no change, waste = excess + inputs * (effective_feerate - long_term_feerate)
236 : * where excess = selected_effective_value - target
237 : * change_cost = effective_feerate * change_output_size + long_term_feerate * change_spend_size
238 : *
239 : * Note this function is separate from SelectionResult for the tests.
240 : *
241 : * @param[in] inputs The selected inputs
242 : * @param[in] change_cost The cost of creating change and spending it in the future.
243 : * Only used if there is change, in which case it must be positive.
244 : * Must be 0 if there is no change.
245 : * @param[in] target The amount targeted by the coin selection algorithm.
246 : * @param[in] use_effective_value Whether to use the input's effective value (when true) or the real value (when false).
247 : * @return The waste
248 : */
249 : [[nodiscard]] CAmount GetSelectionWaste(const std::set<COutput>& inputs, CAmount change_cost, CAmount target, bool use_effective_value = true);
250 :
251 :
252 : /** Choose a random change target for each transaction to make it harder to fingerprint the Core
253 : * wallet based on the change output values of transactions it creates.
254 : * The random value is between 50ksat and min(2 * payment_value, 1milsat)
255 : * When payment_value <= 25ksat, the value is just 50ksat.
256 : *
257 : * Making change amounts similar to the payment value may help disguise which output(s) are payments
258 : * are which ones are change. Using double the payment value may increase the number of inputs
259 : * needed (and thus be more expensive in fees), but breaks analysis techniques which assume the
260 : * coins selected are just sufficient to cover the payment amount ("unnecessary input" heuristic).
261 : *
262 : * @param[in] payment_value Average payment value of the transaction output(s).
263 : */
264 : [[nodiscard]] CAmount GenerateChangeTarget(CAmount payment_value, FastRandomContext& rng);
265 :
266 : enum class SelectionAlgorithm : uint8_t
267 : {
268 : BNB = 0,
269 : KNAPSACK = 1,
270 : SRD = 2,
271 : MANUAL = 3,
272 : };
273 :
274 : std::string GetAlgorithmName(const SelectionAlgorithm algo);
275 :
276 : struct SelectionResult
277 : {
278 : private:
279 : /** Set of inputs selected by the algorithm to use in the transaction */
280 : std::set<COutput> m_selected_inputs;
281 : /** Whether the input values for calculations should be the effective value (true) or normal value (false) */
282 5884 : bool m_use_effective{false};
283 : /** The computed waste */
284 : std::optional<CAmount> m_waste;
285 :
286 : public:
287 : /** The target the algorithm selected for. Note that this may not be equal to the recipient amount as it can include non-input fees */
288 : const CAmount m_target;
289 : /** The algorithm used to produce this result */
290 : const SelectionAlgorithm m_algo;
291 :
292 17652 : explicit SelectionResult(const CAmount target, SelectionAlgorithm algo)
293 11768 : : m_target(target), m_algo(algo) {}
294 :
295 : SelectionResult() = delete;
296 :
297 : /** Get the sum of the input values */
298 : [[nodiscard]] CAmount GetSelectedValue() const;
299 :
300 : void Clear();
301 :
302 : void AddInput(const OutputGroup& group);
303 :
304 : /** Calculates and stores the waste for this selection via GetSelectionWaste */
305 : void ComputeAndSetWaste(CAmount change_cost);
306 : [[nodiscard]] CAmount GetWaste() const;
307 :
308 : /** Get m_selected_inputs */
309 : const std::set<COutput>& GetInputSet() const;
310 : /** Get the vector of COutputs that will be used to fill in a CTransaction's vin */
311 : std::vector<COutput> GetShuffledInputVector() const;
312 :
313 : bool operator<(SelectionResult other) const;
314 : };
315 :
316 : util::Result<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change,
317 : int max_weight);
318 :
319 : /** Select coins by Single Random Draw. OutputGroups are selected randomly from the eligible
320 : * outputs until the target is satisfied
321 : *
322 : * @param[in] utxo_pool The positive effective value OutputGroups eligible for selection
323 : * @param[in] target_value The target value to select for
324 : * @param[in] rng The randomness source to shuffle coins
325 : * @param[in] max_weight The maximum allowed weight for a selection result to be valid
326 : * @returns If successful, a valid SelectionResult, otherwise, util::Error
327 : */
328 : util::Result<SelectionResult> SelectCoinsSRD(const std::vector<OutputGroup>& utxo_pool, CAmount target_value, FastRandomContext& rng,
329 : int max_weight);
330 :
331 : // Original coin selection algorithm as a fallback
332 : util::Result<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups, const CAmount& nTargetValue,
333 : CAmount change_target, FastRandomContext& rng, int max_weight, bool fFullyMixedOnly,
334 : CAmount maxTxFee);
335 : } // namespace wallet
336 :
337 : #endif // BITCOIN_WALLET_COINSELECTION_H
|
