1 // Copyright (c) 2017-2022 The Limenka 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 LIMENKA_WALLET_COINSELECTION_H
6 #define LIMENKA_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 CAmount long_term_fee{0};
74 75 /** The fee necessary to bump this UTXO's ancestor transactions to the target feerate */
76 CAmount ancestor_bump_fees{0};
77 78 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 : outpoint{outpoint},
80 txout{txout},
81 depth{depth},
82 input_bytes{input_bytes},
83 spendable{spendable},
84 solvable{solvable},
85 safe{safe},
86 time{time},
87 from_me{from_me}
88 {
89 if (feerate) {
90 // base fee without considering potential unconfirmed ancestors
91 fee = input_bytes < 0 ? 0 : feerate.value().GetFee(input_bytes);
92 effective_value = txout.nValue - fee.value();
93 }
94 }
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 void ApplyBumpFee(CAmount bump_fee)
113 {
114 assert(bump_fee >= 0);
115 ancestor_bump_fees = bump_fee;
116 assert(fee);
117 *fee += bump_fee;
118 // Note: assert(effective_value - bump_fee == nValue - fee.value());
119 effective_value = txout.nValue - fee.value();
120 }
121 122 CAmount GetFee() const
123 {
124 assert(fee.has_value());
125 return fee.value();
126 }
127 128 CAmount GetEffectiveValue() const
129 {
130 assert(effective_value.has_value());
131 return effective_value.value();
132 }
133 134 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 int change_output_size = 0;
143 /** Size of the input to spend a change output in virtual bytes. */
144 int change_spend_size = 0;
145 /** Mininmum change to target in Knapsack solver and CoinGrinder:
146 * select coins to cover the payment and at least this value of change. */
147 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 CAmount min_viable_change{0};
152 /** Cost of creating the change output. */
153 CAmount m_change_fee{0};
154 /** Cost of creating the change output + cost of spending the change output in the future. */
155 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 int tx_noinputs_size = 0;
166 /** Indicate that we are subtracting the fee from outputs */
167 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 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 bool m_include_unsafe_inputs = false;
177 /** The maximum weight for this transaction. */
178 std::optional<int> m_max_tx_weight{std::nullopt};
179 180 // Privacy-focused coin selection parameters
181 /** Enable privacy-first coin selection (temporal clustering) */
182 bool m_privacy_first = true;
183 /** Time window for temporal clustering (seconds) */
184 int64_t m_temporal_window = 3600;
185 /** Target number of outputs when merging UTXOs */
186 int m_target_merge_outputs = 2;
187 188 CoinSelectionParams(FastRandomContext& rng_fast, int change_output_size, int change_spend_size,
189 CAmount min_change_target, CFeeRate effective_feerate,
190 CFeeRate long_term_feerate, CFeeRate discard_feerate, int tx_noinputs_size, bool avoid_partial,
191 std::optional<int> max_tx_weight = std::nullopt,
192 bool privacy_first = true, int64_t temporal_window = 3600, int target_merge_outputs = 2)
193 : rng_fast{rng_fast},
194 change_output_size(change_output_size),
195 change_spend_size(change_spend_size),
196 m_min_change_target(min_change_target),
197 m_effective_feerate(effective_feerate),
198 m_long_term_feerate(long_term_feerate),
199 m_discard_feerate(discard_feerate),
200 tx_noinputs_size(tx_noinputs_size),
201 m_avoid_partial_spends(avoid_partial),
202 m_max_tx_weight(max_tx_weight),
203 m_privacy_first(privacy_first),
204 m_temporal_window(temporal_window),
205 m_target_merge_outputs(target_merge_outputs)
206 {
207 }
208 CoinSelectionParams(FastRandomContext& rng_fast)
209 : rng_fast{rng_fast} {}
210 };
211 212 /** Parameters for filtering which OutputGroups we may use in coin selection.
213 * We start by being very selective and requiring multiple confirmations and
214 * then get more permissive if we cannot fund the transaction. */
215 struct CoinEligibilityFilter
216 {
217 /** Minimum number of confirmations for outputs that we sent to ourselves.
218 * We may use unconfirmed UTXOs sent from ourselves, e.g. change outputs. */
219 const int conf_mine;
220 /** Minimum number of confirmations for outputs received from a different wallet. */
221 const int conf_theirs;
222 /** Maximum number of unconfirmed ancestors aggregated across all UTXOs in an OutputGroup. */
223 const uint64_t max_ancestors;
224 /** Maximum number of descendants that a single UTXO in the OutputGroup may have. */
225 const uint64_t max_descendants;
226 /** When avoid_reuse=true and there are full groups (OUTPUT_GROUP_MAX_ENTRIES), whether or not to use any partial groups.*/
227 const bool m_include_partial_groups{false};
228 229 CoinEligibilityFilter() = delete;
230 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) {}
231 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) {}
232 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) {}
233 234 bool operator<(const CoinEligibilityFilter& other) const {
235 return std::tie(conf_mine, conf_theirs, max_ancestors, max_descendants, m_include_partial_groups)
236 < std::tie(other.conf_mine, other.conf_theirs, other.max_ancestors, other.max_descendants, other.m_include_partial_groups);
237 }
238 };
239 240 /** A group of UTXOs paid to the same output script. */
241 struct OutputGroup
242 {
243 /** The list of UTXOs contained in this output group. */
244 std::vector<std::shared_ptr<COutput>> m_outputs;
245 /** Whether the UTXOs were sent by the wallet to itself. This is relevant because we may want at
246 * least a certain number of confirmations on UTXOs received from outside wallets while trusting
247 * our own UTXOs more. */
248 bool m_from_me{true};
249 /** The total value of the UTXOs in sum. */
250 CAmount m_value{0};
251 /** The minimum number of confirmations the UTXOs in the group have. Unconfirmed is 0. */
252 int m_depth{999};
253 /** The aggregated count of unconfirmed ancestors of all UTXOs in this
254 * group. Not deduplicated and may overestimate when ancestors are shared. */
255 size_t m_ancestors{0};
256 /** The maximum count of descendants of a single UTXO in this output group. */
257 size_t m_descendants{0};
258 /** The value of the UTXOs after deducting the cost of spending them at the effective feerate. */
259 CAmount effective_value{0};
260 /** The fee to spend these UTXOs at the effective feerate. */
261 CAmount fee{0};
262 /** The fee to spend these UTXOs at the long term feerate. */
263 CAmount long_term_fee{0};
264 /** The feerate for spending a created change output eventually (i.e. not urgently, and thus at
265 * a lower feerate). Calculated using long term fee estimate. This is used to decide whether
266 * it could be economical to create a change output. */
267 CFeeRate m_long_term_feerate{0};
268 /** Indicate that we are subtracting the fee from outputs.
269 * When true, the value that is used for coin selection is the UTXO's real value rather than effective value */
270 bool m_subtract_fee_outputs{false};
271 /** Total weight of the UTXOs in this group. */
272 int m_weight{0};
273 274 OutputGroup() = default;
275 OutputGroup(const CoinSelectionParams& params) :
276 m_long_term_feerate(params.m_long_term_feerate),
277 m_subtract_fee_outputs(params.m_subtract_fee_outputs)
278 {}
279 280 void Insert(const std::shared_ptr<COutput>& output, size_t ancestors, size_t descendants);
281 bool EligibleForSpending(const CoinEligibilityFilter& eligibility_filter) const;
282 CAmount GetSelectionAmount() const;
283 };
284 285 struct Groups {
286 // Stores 'OutputGroup' containing only positive UTXOs (value > 0).
287 std::vector<OutputGroup> positive_group;
288 // Stores 'OutputGroup' which may contain both positive and negative UTXOs.
289 std::vector<OutputGroup> mixed_group;
290 };
291 292 /** Stores several 'Groups' whose were mapped by output type. */
293 struct OutputGroupTypeMap
294 {
295 // Maps output type to output groups.
296 std::map<OutputType, Groups> groups_by_type;
297 // All inserted groups, no type distinction.
298 Groups all_groups;
299 300 // Based on the insert flag; appends group to the 'mixed_group' and, if value > 0, to the 'positive_group'.
301 // This affects both; the groups filtered by type and the overall groups container.
302 void Push(const OutputGroup& group, OutputType type, bool insert_positive, bool insert_mixed);
303 // Different output types count
304 size_t TypesCount() { return groups_by_type.size(); }
305 };
306 307 typedef std::map<CoinEligibilityFilter, OutputGroupTypeMap> FilteredOutputGroups;
308 309 /** Choose a random change target for each transaction to make it harder to fingerprint the Core
310 * wallet based on the change output values of transactions it creates.
311 * Change target covers at least change fees and adds a random value on top of it.
312 * The random value is between 50ksat and min(2 * payment_value, 1milsat)
313 * When payment_value <= 25ksat, the value is just 50ksat.
314 *
315 * Making change amounts similar to the payment value may help disguise which output(s) are payments
316 * are which ones are change. Using double the payment value may increase the number of inputs
317 * needed (and thus be more expensive in fees), but breaks analysis techniques which assume the
318 * coins selected are just sufficient to cover the payment amount ("unnecessary input" heuristic).
319 *
320 * @param[in] payment_value Average payment value of the transaction output(s).
321 * @param[in] change_fee Fee for creating a change output.
322 */
323 [[nodiscard]] CAmount GenerateChangeTarget(const CAmount payment_value, const CAmount change_fee, FastRandomContext& rng);
324 325 enum class SelectionAlgorithm : uint8_t
326 {
327 BNB = 0,
328 KNAPSACK = 1,
329 SRD = 2,
330 CG = 3,
331 MANUAL = 4,
332 TEMPORAL = 5, // Privacy-first: temporal clustering
333 };
334 335 std::string GetAlgorithmName(const SelectionAlgorithm algo);
336 337 struct SelectionResult
338 {
339 private:
340 /** Set of inputs selected by the algorithm to use in the transaction */
341 std::set<std::shared_ptr<COutput>> m_selected_inputs;
342 /** The target the algorithm selected for. Equal to the recipient amount plus non-input fees */
343 CAmount m_target;
344 /** The algorithm used to produce this result */
345 SelectionAlgorithm m_algo;
346 /** Whether the input values for calculations should be the effective value (true) or normal value (false) */
347 bool m_use_effective{false};
348 /** The computed waste */
349 std::optional<CAmount> m_waste;
350 /** False if algorithm was cut short by hitting limit of attempts and solution is non-optimal */
351 bool m_algo_completed{true};
352 /** The count of selections that were evaluated by this coin selection attempt */
353 size_t m_selections_evaluated;
354 /** Total weight of the selected inputs */
355 int m_weight{0};
356 /** How much individual inputs overestimated the bump fees for the shared ancestry */
357 CAmount bump_fee_group_discount{0};
358 359 template<typename T>
360 void InsertInputs(const T& inputs)
361 {
362 // Store sum of combined input sets to check that the results have no shared UTXOs
363 const size_t expected_count = m_selected_inputs.size() + inputs.size();
364 util::insert(m_selected_inputs, inputs);
365 if (m_selected_inputs.size() != expected_count) {
366 throw std::runtime_error(STR_INTERNAL_BUG("Shared UTXOs among selection results"));
367 }
368 }
369 370 public:
371 explicit SelectionResult(const CAmount target, SelectionAlgorithm algo)
372 : m_target(target), m_algo(algo) {}
373 374 SelectionResult() = delete;
375 376 /** Get the sum of the input values */
377 [[nodiscard]] CAmount GetSelectedValue() const;
378 379 [[nodiscard]] CAmount GetSelectedEffectiveValue() const;
380 381 [[nodiscard]] CAmount GetTotalBumpFees() const;
382 383 void Clear();
384 385 void AddInput(const OutputGroup& group);
386 void AddInputs(const std::set<std::shared_ptr<COutput>>& inputs, bool subtract_fee_outputs);
387 388 /** How much individual inputs overestimated the bump fees for shared ancestries */
389 void SetBumpFeeDiscount(const CAmount discount);
390 391 /** Calculates and stores the waste for this result given the cost of change
392 * and the opportunity cost of spending these inputs now vs in the future.
393 * If change exists, waste = change_cost + inputs * (effective_feerate - long_term_feerate) - bump_fee_group_discount
394 * If no change, waste = excess + inputs * (effective_feerate - long_term_feerate) - bump_fee_group_discount
395 * where excess = selected_effective_value - target
396 * change_cost = effective_feerate * change_output_size + long_term_feerate * change_spend_size
397 *
398 * @param[in] min_viable_change The minimum amount necessary to make a change output economic
399 * @param[in] change_cost The cost of creating a change output and spending it in the future. Only
400 * used if there is change, in which case it must be non-negative.
401 * @param[in] change_fee The fee for creating a change output
402 */
403 void RecalculateWaste(const CAmount min_viable_change, const CAmount change_cost, const CAmount change_fee);
404 [[nodiscard]] CAmount GetWaste() const;
405 406 /** Tracks that algorithm was able to exhaustively search the entire combination space before hitting limit of tries */
407 void SetAlgoCompleted(bool algo_completed);
408 409 /** Get m_algo_completed */
410 bool GetAlgoCompleted() const;
411 412 /** Record the number of selections that were evaluated */
413 void SetSelectionsEvaluated(size_t attempts);
414 415 /** Get selections_evaluated */
416 size_t GetSelectionsEvaluated() const ;
417 418 /**
419 * Combines the @param[in] other selection result into 'this' selection result.
420 *
421 * Important note:
422 * There must be no shared 'COutput' among the two selection results being combined.
423 */
424 void Merge(const SelectionResult& other);
425 426 /** Get m_selected_inputs */
427 const std::set<std::shared_ptr<COutput>>& GetInputSet() const;
428 /** Get the vector of COutputs that will be used to fill in a CTransaction's vin */
429 std::vector<std::shared_ptr<COutput>> GetShuffledInputVector() const;
430 431 bool operator<(SelectionResult other) const;
432 433 /** Get the amount for the change output after paying needed fees.
434 *
435 * The change amount is not 100% precise due to discrepancies in fee calculation.
436 * The final change amount (if any) should be corrected after calculating the final tx fees.
437 * When there is a discrepancy, most of the time the final change would be slightly bigger than estimated.
438 *
439 * Following are the possible factors of discrepancy:
440 * + non-input fees always include segwit flags
441 * + input fee estimation always include segwit stack size
442 * + input fees are rounded individually and not collectively, which leads to small rounding errors
443 * - input counter size is always assumed to be 1vbyte
444 *
445 * @param[in] min_viable_change Minimum amount for change output, if change would be less then we forgo change
446 * @param[in] change_fee Fees to include change output in the tx
447 * @returns Amount for change output, 0 when there is no change.
448 *
449 */
450 CAmount GetChange(const CAmount min_viable_change, const CAmount change_fee) const;
451 452 CAmount GetTarget() const { return m_target; }
453 454 SelectionAlgorithm GetAlgo() const { return m_algo; }
455 456 int GetWeight() const { return m_weight; }
457 };
458 459 util::Result<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change,
460 int max_selection_weight);
461 462 util::Result<SelectionResult> CoinGrinder(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, CAmount change_target, int max_selection_weight);
463 464 /** Select coins by Single Random Draw. OutputGroups are selected randomly from the eligible
465 * outputs until the target is satisfied
466 *
467 * @param[in] utxo_pool The positive effective value OutputGroups eligible for selection
468 * @param[in] target_value The target value to select for
469 * @param[in] rng The randomness source to shuffle coins
470 * @param[in] max_selection_weight The maximum allowed weight for a selection result to be valid
471 * @returns If successful, a valid SelectionResult, otherwise, util::Error
472 */
473 util::Result<SelectionResult> SelectCoinsSRD(const std::vector<OutputGroup>& utxo_pool, CAmount target_value, CAmount change_fee, FastRandomContext& rng,
474 int max_selection_weight);
475 476 // Original coin selection algorithm as a fallback
477 util::Result<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups, const CAmount& nTargetValue,
478 CAmount change_target, FastRandomContext& rng, int max_selection_weight);
479 480 /** Privacy-first coin selection: temporal clustering algorithm.
481 * Prefers UTXOs created within the same time window (temporal cluster).
482 * Minimizes inputs while keeping UTXOs from the same source together.
483 */
484 util::Result<SelectionResult> SelectCoinsTemporal(std::vector<OutputGroup>& utxo_pool,
485 const CAmount& selection_target,
486 int64_t temporal_window,
487 int target_outputs,
488 int max_selection_weight);
489 } // namespace wallet
490 491 #endif // LIMENKA_WALLET_COINSELECTION_H
492