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