Branch data Line data Source code
# 1 : : // Copyright (c) 2017-2019 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 <amount.h>
# 9 : : #include <policy/feerate.h>
# 10 : : #include <primitives/transaction.h>
# 11 : : #include <random.h>
# 12 : :
# 13 : : //! target minimum change amount
# 14 : : static constexpr CAmount MIN_CHANGE{COIN / 100};
# 15 : : //! final minimum change amount after paying for fees
# 16 : : static const CAmount MIN_FINAL_CHANGE = MIN_CHANGE/2;
# 17 : :
# 18 : : /** A UTXO under consideration for use in funding a new transaction. */
# 19 : : class CInputCoin {
# 20 : : public:
# 21 : : CInputCoin(const CTransactionRef& tx, unsigned int i)
# 22 : 2016490 : {
# 23 [ - + ]: 2016490 : if (!tx)
# 24 : 0 : throw std::invalid_argument("tx should not be null");
# 25 [ - + ]: 2016490 : if (i >= tx->vout.size())
# 26 : 0 : throw std::out_of_range("The output index is out of range");
# 27 : :
# 28 : 2016490 : outpoint = COutPoint(tx->GetHash(), i);
# 29 : 2016490 : txout = tx->vout[i];
# 30 : 2016490 : effective_value = txout.nValue;
# 31 : 2016490 : }
# 32 : :
# 33 : : CInputCoin(const CTransactionRef& tx, unsigned int i, int input_bytes) : CInputCoin(tx, i)
# 34 : 1966386 : {
# 35 : 1966386 : m_input_bytes = input_bytes;
# 36 : 1966386 : }
# 37 : :
# 38 : : COutPoint outpoint;
# 39 : : CTxOut txout;
# 40 : : CAmount effective_value;
# 41 : : CAmount m_fee{0};
# 42 : : CAmount m_long_term_fee{0};
# 43 : :
# 44 : : /** Pre-computed estimated size of this output as a fully-signed input in a transaction. Can be -1 if it could not be calculated */
# 45 : : int m_input_bytes{-1};
# 46 : :
# 47 : 1442412 : bool operator<(const CInputCoin& rhs) const {
# 48 : 1442412 : return outpoint < rhs.outpoint;
# 49 : 1442412 : }
# 50 : :
# 51 : 0 : bool operator!=(const CInputCoin& rhs) const {
# 52 : 0 : return outpoint != rhs.outpoint;
# 53 : 0 : }
# 54 : :
# 55 : 1144 : bool operator==(const CInputCoin& rhs) const {
# 56 : 1144 : return outpoint == rhs.outpoint;
# 57 : 1144 : }
# 58 : : };
# 59 : :
# 60 : : /** Parameters for one iteration of Coin Selection. */
# 61 : : struct CoinSelectionParams
# 62 : : {
# 63 : : /** Size of a change output in bytes, determined by the output type. */
# 64 : : size_t change_output_size = 0;
# 65 : : /** Size of the input to spend a change output in virtual bytes. */
# 66 : : size_t change_spend_size = 0;
# 67 : : /** Cost of creating the change output. */
# 68 : : CAmount m_change_fee{0};
# 69 : : /** Cost of creating the change output + cost of spending the change output in the future. */
# 70 : : CAmount m_cost_of_change{0};
# 71 : : /** The targeted feerate of the transaction being built. */
# 72 : : CFeeRate m_effective_feerate;
# 73 : : /** The feerate estimate used to estimate an upper bound on what should be sufficient to spend
# 74 : : * the change output sometime in the future. */
# 75 : : CFeeRate m_long_term_feerate;
# 76 : : /** If the cost to spend a change output at the discard feerate exceeds its value, drop it to fees. */
# 77 : : CFeeRate m_discard_feerate;
# 78 : : /** Size of the transaction before coin selection, consisting of the header and recipient
# 79 : : * output(s), excluding the inputs and change output(s). */
# 80 : : size_t tx_noinputs_size = 0;
# 81 : : /** Indicate that we are subtracting the fee from outputs */
# 82 : : bool m_subtract_fee_outputs = false;
# 83 : : /** When true, always spend all (up to OUTPUT_GROUP_MAX_ENTRIES) or none of the outputs
# 84 : : * associated with the same address. This helps reduce privacy leaks resulting from address
# 85 : : * reuse. Dust outputs are not eligible to be added to output groups and thus not considered. */
# 86 : : bool m_avoid_partial_spends = false;
# 87 : :
# 88 : : CoinSelectionParams(size_t change_output_size, size_t change_spend_size, CFeeRate effective_feerate,
# 89 : : CFeeRate long_term_feerate, CFeeRate discard_feerate, size_t tx_noinputs_size, bool avoid_partial) :
# 90 : : change_output_size(change_output_size),
# 91 : : change_spend_size(change_spend_size),
# 92 : : m_effective_feerate(effective_feerate),
# 93 : : m_long_term_feerate(long_term_feerate),
# 94 : : m_discard_feerate(discard_feerate),
# 95 : : tx_noinputs_size(tx_noinputs_size),
# 96 : : m_avoid_partial_spends(avoid_partial)
# 97 : 103 : {}
# 98 : 5009 : CoinSelectionParams() {}
# 99 : : };
# 100 : :
# 101 : : /** Parameters for filtering which OutputGroups we may use in coin selection.
# 102 : : * We start by being very selective and requiring multiple confirmations and
# 103 : : * then get more permissive if we cannot fund the transaction. */
# 104 : : struct CoinEligibilityFilter
# 105 : : {
# 106 : : /** Minimum number of confirmations for outputs that we sent to ourselves.
# 107 : : * We may use unconfirmed UTXOs sent from ourselves, e.g. change outputs. */
# 108 : : const int conf_mine;
# 109 : : /** Minimum number of confirmations for outputs received from a different wallet. */
# 110 : : const int conf_theirs;
# 111 : : /** Maximum number of unconfirmed ancestors aggregated across all UTXOs in an OutputGroup. */
# 112 : : const uint64_t max_ancestors;
# 113 : : /** Maximum number of descendants that a single UTXO in the OutputGroup may have. */
# 114 : : const uint64_t max_descendants;
# 115 : : /** When avoid_reuse=true and there are full groups (OUTPUT_GROUP_MAX_ENTRIES), whether or not to use any partial groups.*/
# 116 : : const bool m_include_partial_groups{false};
# 117 : :
# 118 : 6922 : 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) {}
# 119 : 244 : 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) {}
# 120 : 118 : 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) {}
# 121 : : };
# 122 : :
# 123 : : /** A group of UTXOs paid to the same output script. */
# 124 : : struct OutputGroup
# 125 : : {
# 126 : : /** The list of UTXOs contained in this output group. */
# 127 : : std::vector<CInputCoin> m_outputs;
# 128 : : /** Whether the UTXOs were sent by the wallet to itself. This is relevant because we may want at
# 129 : : * least a certain number of confirmations on UTXOs received from outside wallets while trusting
# 130 : : * our own UTXOs more. */
# 131 : : bool m_from_me{true};
# 132 : : /** The total value of the UTXOs in sum. */
# 133 : : CAmount m_value{0};
# 134 : : /** The minimum number of confirmations the UTXOs in the group have. Unconfirmed is 0. */
# 135 : : int m_depth{999};
# 136 : : /** The aggregated count of unconfirmed ancestors of all UTXOs in this
# 137 : : * group. Not deduplicated and may overestimate when ancestors are shared. */
# 138 : : size_t m_ancestors{0};
# 139 : : /** The maximum count of descendants of a single UTXO in this output group. */
# 140 : : size_t m_descendants{0};
# 141 : : /** The value of the UTXOs after deducting the cost of spending them at the effective feerate. */
# 142 : : CAmount effective_value{0};
# 143 : : /** The fee to spend these UTXOs at the effective feerate. */
# 144 : : CAmount fee{0};
# 145 : : /** The target feerate of the transaction we're trying to build. */
# 146 : : CFeeRate m_effective_feerate{0};
# 147 : : /** The fee to spend these UTXOs at the long term feerate. */
# 148 : : CAmount long_term_fee{0};
# 149 : : /** The feerate for spending a created change output eventually (i.e. not urgently, and thus at
# 150 : : * a lower feerate). Calculated using long term fee estimate. This is used to decide whether
# 151 : : * it could be economical to create a change output. */
# 152 : : CFeeRate m_long_term_feerate{0};
# 153 : : /** Indicate that we are subtracting the fee from outputs.
# 154 : : * When true, the value that is used for coin selection is the UTXO's real value rather than effective value */
# 155 : : bool m_subtract_fee_outputs{false};
# 156 : :
# 157 : 276706 : OutputGroup() {}
# 158 : : OutputGroup(const CoinSelectionParams& params) :
# 159 : : m_effective_feerate(params.m_effective_feerate),
# 160 : : m_long_term_feerate(params.m_long_term_feerate),
# 161 : : m_subtract_fee_outputs(params.m_subtract_fee_outputs)
# 162 : 1460352 : {}
# 163 : :
# 164 : : void Insert(const CInputCoin& output, int depth, bool from_me, size_t ancestors, size_t descendants, bool positive_only);
# 165 : : bool EligibleForSpending(const CoinEligibilityFilter& eligibility_filter) const;
# 166 : : CAmount GetSelectionAmount() const;
# 167 : : };
# 168 : :
# 169 : : bool SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change, std::set<CInputCoin>& out_set, CAmount& value_ret);
# 170 : :
# 171 : : // Original coin selection algorithm as a fallback
# 172 : : bool KnapsackSolver(const CAmount& nTargetValue, std::vector<OutputGroup>& groups, std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet);
# 173 : :
# 174 : : #endif // BITCOIN_WALLET_COINSELECTION_H
|