From 0c74716c50384677724247e05e6592f845fc8635 Mon Sep 17 00:00:00 2001 From: glozow Date: Tue, 20 Apr 2021 10:44:11 -0700 Subject: [docs] format existing comments as doxygen Co-authored-by: Xekyo --- src/wallet/wallet.h | 32 ++++++++++++++++---------------- 1 file changed, 16 insertions(+), 16 deletions(-) diff --git a/src/wallet/wallet.h b/src/wallet/wallet.h index c4acef8705..cc197d329c 100644 --- a/src/wallet/wallet.h +++ b/src/wallet/wallet.h @@ -368,7 +368,7 @@ public: CTransactionRef tx; - /* New transactions start as UNCONFIRMED. At BlockConnected, + /** New transactions start as UNCONFIRMED. At BlockConnected, * they will transition to CONFIRMED. In case of reorg, at BlockDisconnected, * they roll back to UNCONFIRMED. If we detect a conflicting transaction at * block connection, we update conflicted tx and its dependencies as CONFLICTED. @@ -383,7 +383,7 @@ public: ABANDONED }; - /* Confirmation includes tx status and a triplet of {block height/block hash/tx index in block} + /** Confirmation includes tx status and a triplet of {block height/block hash/tx index in block} * at which tx has been confirmed. All three are set to 0 if tx is unconfirmed or abandoned. * Meaning of these fields changes with CONFLICTED state where they instead point to block hash * and block height of the deepest conflicting tx. @@ -481,7 +481,7 @@ public: CAmount GetImmatureWatchOnlyCredit(const bool fUseCache = true) const; CAmount GetChange() const; - // Get the marginal bytes if spending the specified output from this transaction + /** Get the marginal bytes if spending the specified output from this transaction */ int GetSpendSize(unsigned int out, bool use_max_sig = false) const { return CalculateMaximumSignedInputSize(tx->vout[out], pwallet, use_max_sig); @@ -495,7 +495,7 @@ public: return (GetDebit(filter) > 0); } - // True if only scriptSigs are different + /** True if only scriptSigs are different */ bool IsEquivalentTo(const CWalletTx& tx) const; bool InMempool() const; @@ -503,7 +503,7 @@ public: int64_t GetTxTime() const; - // Pass this transaction to node for mempool insertion and relay to peers if flag set to true + /** Pass this transaction to node for mempool insertion and relay to peers if flag set to true */ bool SubmitMemoryPoolAndRelay(std::string& err_string, bool relay); // TODO: Remove "NO_THREAD_SAFETY_ANALYSIS" and replace it with the correct @@ -613,7 +613,7 @@ struct CoinSelectionParams CFeeRate m_long_term_feerate; CFeeRate m_discard_feerate; size_t tx_noinputs_size = 0; - //! Indicate that we are subtracting the fee from outputs + /** Indicate that we are subtracting the fee from outputs */ bool m_subtract_fee_outputs = false; bool m_avoid_partial_spends = false; @@ -682,10 +682,10 @@ private: */ bool AddToWalletIfInvolvingMe(const CTransactionRef& tx, CWalletTx::Confirmation confirm, bool fUpdate) EXCLUSIVE_LOCKS_REQUIRED(cs_wallet); - /* Mark a transaction (and its in-wallet descendants) as conflicting with a particular block. */ + /** Mark a transaction (and its in-wallet descendants) as conflicting with a particular block. */ void MarkConflicted(const uint256& hashBlock, int conflicting_height, const uint256& hashTx); - /* Mark a transaction's inputs dirty, thus forcing the outputs to be recomputed */ + /** Mark a transaction's inputs dirty, thus forcing the outputs to be recomputed */ void MarkInputsDirty(const CTransactionRef& tx) EXCLUSIVE_LOCKS_REQUIRED(cs_wallet); void SyncMetaData(std::pair) EXCLUSIVE_LOCKS_REQUIRED(cs_wallet); @@ -722,7 +722,7 @@ private: */ uint256 m_last_block_processed GUARDED_BY(cs_wallet); - /* Height of last block processed is used by wallet to know depth of transactions + /** Height of last block processed is used by wallet to know depth of transactions * without relying on Chain interface beyond asynchronous updates. For safety, we * initialize it to -1. Height is a pointer on node's tip and doesn't imply * that the wallet has scanned sequentially all blocks up to this one. @@ -739,7 +739,7 @@ private: bool CreateTransactionInternal(const std::vector& vecSend, CTransactionRef& tx, CAmount& nFeeRet, int& nChangePosInOut, bilingual_str& error, const CCoinControl& coin_control, FeeCalculation& fee_calc_out, bool sign); public: - /* + /** * Main wallet lock. * This lock protects all the fields added by CWallet. */ @@ -956,9 +956,9 @@ public: * calling CreateTransaction(); */ bool FundTransaction(CMutableTransaction& tx, CAmount& nFeeRet, int& nChangePosInOut, bilingual_str& error, bool lockUnspents, const std::set& setSubtractFeeFromOutputs, CCoinControl); - // Fetch the inputs and sign with SIGHASH_ALL. + /** Fetch the inputs and sign with SIGHASH_ALL. */ bool SignTransaction(CMutableTransaction& tx) const EXCLUSIVE_LOCKS_REQUIRED(cs_wallet); - // Sign the tx given the input coins and sighash. + /** Sign the tx given the input coins and sighash. */ bool SignTransaction(CMutableTransaction& tx, const std::map& coins, int sighash, std::map& input_errors) const; SigningResult SignMessage(const std::string& message, const PKHash& pkhash, std::string& str_sig) const; @@ -1333,10 +1333,10 @@ public: } }; -// Calculate the size of the transaction assuming all signatures are max size -// Use DummySignatureCreator, which inserts 71 byte signatures everywhere. -// NOTE: this requires that all inputs must be in mapWallet (eg the tx should -// be IsAllFromMe). +/** Calculate the size of the transaction assuming all signatures are max size +* Use DummySignatureCreator, which inserts 71 byte signatures everywhere. +* NOTE: this requires that all inputs must be in mapWallet (eg the tx should +* be IsAllFromMe). */ std::pair CalculateMaximumSignedTxSize(const CTransaction &tx, const CWallet *wallet, bool use_max_sig = false) EXCLUSIVE_LOCKS_REQUIRED(wallet->cs_wallet); std::pair CalculateMaximumSignedTxSize(const CTransaction &tx, const CWallet *wallet, const std::vector& txouts, bool use_max_sig = false); -- cgit v1.2.3 From 58ea324fdd906204bb77ea4be1c01a3ab56cf86f Mon Sep 17 00:00:00 2001 From: glozow Date: Wed, 21 Apr 2021 15:52:29 -0700 Subject: [docs] add doxygen comments to wallet code Co-authored-by: Xekyo --- src/wallet/coinselection.h | 30 +++++++++++++++++++++++++++- src/wallet/wallet.h | 50 ++++++++++++++++++++++++++++++++++++++++++++-- 2 files changed, 77 insertions(+), 3 deletions(-) diff --git a/src/wallet/coinselection.h b/src/wallet/coinselection.h index f0e1addaf1..5c1b36be6e 100644 --- a/src/wallet/coinselection.h +++ b/src/wallet/coinselection.h @@ -15,6 +15,7 @@ static constexpr CAmount MIN_CHANGE{COIN / 100}; //! final minimum change amount after paying for fees static const CAmount MIN_FINAL_CHANGE = MIN_CHANGE/2; +/** A UTXO under consideration for use in funding a new transaction. */ class CInputCoin { public: CInputCoin(const CTransactionRef& tx, unsigned int i) @@ -56,31 +57,58 @@ public: } }; +/** Parameters for filtering which OutputGroups we may use in coin selection. + * We start by being very selective and requiring multiple confirmations and + * then get more permissive if we cannot fund the transaction. */ struct CoinEligibilityFilter { + /** Minimum number of confirmations for outputs that we sent to ourselves. + * We may use unconfirmed UTXOs sent from ourselves, e.g. change outputs. */ const int conf_mine; + /** Minimum number of confirmations for outputs received from a different + * wallet. We never spend unconfirmed foreign outputs as we cannot rely on these funds yet. */ const int conf_theirs; + /** Maximum number of unconfirmed ancestors aggregated across all UTXOs in an OutputGroup. */ const uint64_t max_ancestors; + /** Maximum number of descendants that a single UTXO in the OutputGroup may have. */ const uint64_t max_descendants; - const bool m_include_partial_groups{false}; //! Include partial destination groups when avoid_reuse and there are full groups + /** When avoid_reuse=true and there are full groups (OUTPUT_GROUP_MAX_ENTRIES), whether or not to use any partial groups.*/ + const bool m_include_partial_groups{false}; 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) {} 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) {} 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) {} }; +/** A group of UTXOs paid to the same output script. */ struct OutputGroup { + /** The list of UTXOs contained in this output group. */ std::vector m_outputs; + /** Whether the UTXOs were sent by the wallet to itself. This is relevant because we may want at + * least a certain number of confirmations on UTXOs received from outside wallets while trusting + * our own UTXOs more. */ bool m_from_me{true}; + /** The total value of the UTXOs in sum. */ CAmount m_value{0}; + /** The minimum number of confirmations the UTXOs in the group have. Unconfirmed is 0. */ int m_depth{999}; + /** The aggregated count of unconfirmed ancestors of all UTXOs in this + * group. Not deduplicated and may overestimate when ancestors are shared. */ size_t m_ancestors{0}; + /** The maximum count of descendants of a single UTXO in this output group. */ size_t m_descendants{0}; + /** The value of the UTXOs after deducting the cost of spending them at the effective feerate. */ CAmount effective_value{0}; + /** The fee to spend these UTXOs at the effective feerate. */ CAmount fee{0}; + /** The target feerate of the transaction we're trying to build. */ CFeeRate m_effective_feerate{0}; + /** The fee to spend these UTXOs at the long term feerate. */ CAmount long_term_fee{0}; + /** The feerate for spending a created change output eventually (i.e. not urgently, and thus at + * a lower feerate). Calculated using long term fee estimate. This is used to decide whether + * it could be economical to create a change output. */ CFeeRate m_long_term_feerate{0}; OutputGroup() {} diff --git a/src/wallet/wallet.h b/src/wallet/wallet.h index cc197d329c..03adca7a89 100644 --- a/src/wallet/wallet.h +++ b/src/wallet/wallet.h @@ -564,7 +564,15 @@ class COutput { public: const CWalletTx *tx; + + /** Index in tx->vout. */ int i; + + /** + * Depth in block chain. + * If > 0: the tx is on chain and has this many confirmations. + * If = 0: the tx is waiting confirmation. + * If < 0: a conflicting tx is on chain and has this many confirmations. */ int nDepth; /** Pre-computed estimated size of this output as a fully-signed input in a transaction. Can be -1 if it could not be calculated */ @@ -604,17 +612,30 @@ public: } }; +/** Parameters for one iteration of Coin Selection. */ struct CoinSelectionParams { + /** Toggles use of Branch and Bound instead of Knapsack solver. */ bool use_bnb = true; + /** Size of a change output in bytes, determined by the output type. */ size_t change_output_size = 0; + /** Size of the input to spend a change output in virtual bytes. */ size_t change_spend_size = 0; + /** The targeted feerate of the transaction being built. */ CFeeRate m_effective_feerate; + /** The feerate estimate used to estimate an upper bound on what should be sufficient to spend + * the change output sometime in the future. */ CFeeRate m_long_term_feerate; + /** If the cost to spend a change output at the discard feerate exceeds its value, drop it to fees. */ CFeeRate m_discard_feerate; + /** Size of the transaction before coin selection, consisting of the header and recipient + * output(s), excluding the inputs and change output(s). */ size_t tx_noinputs_size = 0; /** Indicate that we are subtracting the fee from outputs */ bool m_subtract_fee_outputs = false; + /** When true, always spend all (up to OUTPUT_GROUP_MAX_ENTRIES) or none of the outputs + * associated with the same address. This helps reduce privacy leaks resulting from address + * reuse. Dust outputs are not eligible to be added to output groups and thus not considered. */ bool m_avoid_partial_spends = false; CoinSelectionParams(bool use_bnb, size_t change_output_size, size_t change_spend_size, CFeeRate effective_feerate, @@ -652,7 +673,10 @@ private: //! the current wallet version: clients below this version are not able to load the wallet int nWalletVersion GUARDED_BY(cs_wallet){FEATURE_BASE}; + /** The next scheduled rebroadcast of wallet transactions. */ int64_t nNextResend = 0; + /** Whether this wallet will submit newly created transactions to the node's mempool and + * prompt rebroadcasts (see ResendWalletTransactions()). */ bool fBroadcastTransactions = false; // Local time that the tip block was received. Used to schedule wallet rebroadcasts. std::atomic m_best_block_time {0}; @@ -694,6 +718,7 @@ private: * Should be called with non-zero block_hash and posInBlock if this is for a transaction that is included in a block. */ void SyncTransaction(const CTransactionRef& tx, CWalletTx::Confirmation confirm, bool update_tx = true) EXCLUSIVE_LOCKS_REQUIRED(cs_wallet); + /** WalletFlags set on this wallet. */ std::atomic m_wallet_flags{0}; bool SetAddressBookWithDB(WalletBatch& batch, const CTxDestination& address, const std::string& strName, const std::string& strPurpose); @@ -753,8 +778,11 @@ public: /** * Select a set of coins such that nValueRet >= nTargetValue and at least - * all coins from coinControl are selected; Never select unconfirmed coins - * if they are not ours + * all coins from coin_control are selected; never select unconfirmed coins if they are not ours + * param@[out] setCoinsRet Populated with inputs including pre-selected inputs from + * coin_control and Coin Selection if successful. + * param@[out] nValueRet Total value of selected coins including pre-selected ones + * from coin_control and Coin Selection if successful. */ bool SelectCoins(const std::vector& vAvailableCoins, const CAmount& nTargetValue, std::set& setCoinsRet, CAmount& nValueRet, const CCoinControl& coin_control, CoinSelectionParams& coin_selection_params, bool& bnb_used) const EXCLUSIVE_LOCKS_REQUIRED(cs_wallet); @@ -788,6 +816,8 @@ public: /** Interface to assert chain access */ bool HaveChain() const { return m_chain ? true : false; } + /** Map from txid to CWalletTx for all transactions this wallet is + * interested in, including received and sent transactions. */ std::map mapWallet GUARDED_BY(cs_wallet); typedef std::multimap TxItems; @@ -799,6 +829,10 @@ public: std::map m_address_book GUARDED_BY(cs_wallet); const CAddressBookData* FindAddressBookEntry(const CTxDestination&, bool allow_change = false) const EXCLUSIVE_LOCKS_REQUIRED(cs_wallet); + /** Set of Coins owned by this wallet that we won't try to spend from. A + * Coin may be locked if it has already been used to fund a transaction + * that hasn't confirmed yet. We wouldn't consider the Coin spent already, + * but also shouldn't try to use it again. */ std::set setLockedCoins GUARDED_BY(cs_wallet); /** Registered interfaces::Chain::Notifications handler. */ @@ -833,6 +867,11 @@ public: * small change; This method is stochastic for some inputs and upon * completion the coin set and corresponding actual target value is * assembled + * param@[in] coins Set of UTXOs to consider. These will be categorized into + * OutputGroups and filtered using eligibility_filter before + * selecting coins. + * param@[out] setCoinsRet Populated with the coins selected if successful. + * param@[out] nValueRet Used to return the total value of selected coins. */ bool SelectCoinsMinConf(const CAmount& nTargetValue, const CoinEligibilityFilter& eligibility_filter, std::vector coins, std::set& setCoinsRet, CAmount& nValueRet, const CoinSelectionParams& coin_selection_params, bool& bnb_used) const; @@ -1015,6 +1054,8 @@ public: CFeeRate m_pay_tx_fee{DEFAULT_PAY_TX_FEE}; unsigned int m_confirm_target{DEFAULT_TX_CONFIRM_TARGET}; + /** Allow Coin Selection to pick unconfirmed UTXOs that were sent from our own wallet if it + * cannot fund the transaction otherwise. */ bool m_spend_zero_conf_change{DEFAULT_SPEND_ZEROCONF_CHANGE}; bool m_signal_rbf{DEFAULT_WALLET_RBF}; bool m_allow_fallback_fee{true}; //!< will be false if -fallbackfee=0 @@ -1025,7 +1066,12 @@ public: * Override with -fallbackfee */ CFeeRate m_fallback_fee{DEFAULT_FALLBACK_FEE}; + + /** If the cost to spend a change output at this feerate is greater than the value of the + * output itself, just drop it to fees. */ CFeeRate m_discard_rate{DEFAULT_DISCARD_FEE}; + + /** The maximum fee amount we're willing to pay to prioritize partial spend avoidance. */ CAmount m_max_aps_fee{DEFAULT_MAX_AVOIDPARTIALSPEND_FEE}; //!< note: this is absolute fee, not fee rate OutputType m_default_address_type{DEFAULT_ADDRESS_TYPE}; /** -- cgit v1.2.3 From 6ba892126d354219b146f0c7f35d472f9c14bdac Mon Sep 17 00:00:00 2001 From: glozow Date: Thu, 22 Apr 2021 06:17:21 -0700 Subject: refactor + document coin selection strategy Co-authored-by: Xekyo --- src/wallet/wallet.cpp | 63 ++++++++++++++++++++++++++++++++++++++++----------- 1 file changed, 50 insertions(+), 13 deletions(-) diff --git a/src/wallet/wallet.cpp b/src/wallet/wallet.cpp index 332e7b1397..f0aaee7e4e 100644 --- a/src/wallet/wallet.cpp +++ b/src/wallet/wallet.cpp @@ -2478,7 +2478,7 @@ bool CWallet::SelectCoins(const std::vector& vAvailableCoins, const CAm } } - // remove preset inputs from vCoins + // remove preset inputs from vCoins so that Coin Selection doesn't pick them. for (std::vector::iterator it = vCoins.begin(); it != vCoins.end() && coin_control.HasSelected();) { if (setPresetCoins.count(it->GetInputCoin())) @@ -2490,9 +2490,9 @@ bool CWallet::SelectCoins(const std::vector& vAvailableCoins, const CAm unsigned int limit_ancestor_count = 0; unsigned int limit_descendant_count = 0; chain().getPackageLimits(limit_ancestor_count, limit_descendant_count); - size_t max_ancestors = (size_t)std::max(1, limit_ancestor_count); - size_t max_descendants = (size_t)std::max(1, limit_descendant_count); - bool fRejectLongChains = gArgs.GetBoolArg("-walletrejectlongchains", DEFAULT_WALLET_REJECT_LONG_CHAINS); + const size_t max_ancestors = (size_t)std::max(1, limit_ancestor_count); + const size_t max_descendants = (size_t)std::max(1, limit_descendant_count); + const bool fRejectLongChains = gArgs.GetBoolArg("-walletrejectlongchains", DEFAULT_WALLET_REJECT_LONG_CHAINS); // form groups from remaining coins; note that preset coins will not // automatically have their associated (same address) coins included @@ -2502,16 +2502,53 @@ bool CWallet::SelectCoins(const std::vector& vAvailableCoins, const CAm // explicitly shuffling the outputs before processing Shuffle(vCoins.begin(), vCoins.end(), FastRandomContext()); } - bool res = value_to_select <= 0 || - SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(1, 6, 0), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used) || - SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(1, 1, 0), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used) || - (m_spend_zero_conf_change && SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0, 1, 2), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) || - (m_spend_zero_conf_change && SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0, 1, std::min((size_t)4, max_ancestors/3), std::min((size_t)4, max_descendants/3)), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) || - (m_spend_zero_conf_change && SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0, 1, max_ancestors/2, max_descendants/2), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) || - (m_spend_zero_conf_change && SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0, 1, max_ancestors-1, max_descendants-1, true /* include_partial_groups */), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) || - (m_spend_zero_conf_change && !fRejectLongChains && SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0, 1, std::numeric_limits::max(), std::numeric_limits::max(), true /* include_partial_groups */), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); - // because SelectCoinsMinConf clears the setCoinsRet, we now add the possible inputs to the coinset + // Coin Selection attempts to select inputs from a pool of eligible UTXOs to fund the + // transaction at a target feerate. If an attempt fails, more attempts may be made using a more + // permissive CoinEligibilityFilter. + const bool res = [&] { + // Pre-selected inputs already cover the target amount. + if (value_to_select <= 0) return true; + + // If possible, fund the transaction with confirmed UTXOs only. Prefer at least six + // confirmations on outputs received from other wallets and only spend confirmed change. + if (SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(1, 6, 0), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) return true; + if (SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(1, 1, 0), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) return true; + + // Fall back to using zero confirmation change (but with as few ancestors in the mempool as + // possible) if we cannot fund the transaction otherwise. We never spend unconfirmed + // outputs received from other wallets. + if (m_spend_zero_conf_change) { + if (SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0, 1, 2), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) return true; + if (SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0, 1, std::min((size_t)4, max_ancestors/3), std::min((size_t)4, max_descendants/3)), + vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) { + return true; + } + if (SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0, 1, max_ancestors/2, max_descendants/2), + vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) { + return true; + } + // If partial groups are allowed, relax the requirement of spending OutputGroups (groups + // of UTXOs sent to the same address, which are obviously controlled by a single wallet) + // in their entirety. + if (SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0, 1, max_ancestors-1, max_descendants-1, true /* include_partial_groups */), + vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) { + return true; + } + // Try with unlimited ancestors/descendants. The transaction will still need to meet + // mempool ancestor/descendant policy to be accepted to mempool and broadcasted, but + // OutputGroups use heuristics that may overestimate ancestor/descendant counts. + if (!fRejectLongChains && SelectCoinsMinConf(value_to_select, + CoinEligibilityFilter(0, 1, std::numeric_limits::max(), std::numeric_limits::max(), true /* include_partial_groups */), + vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) { + return true; + } + } + // Coin Selection failed. + return false; + }(); + + // SelectCoinsMinConf clears setCoinsRet, so add the preset inputs from coin_control to the coinset util::insert(setCoinsRet, setPresetCoins); // add preset inputs to the total value selected -- cgit v1.2.3