Merge #14582: wallet: always do avoid partial spends if fees are within a specified range

7f13dfb587dd6a7a5b7dfbfe689ae0ce818fe5c9 test: test the implicit avoid partial spends functionality (Karl-Johan Alm)
b82067bf696c53f22536f9ca2e51949c164f6b06 wallet: try -avoidpartialspends mode and use its result if fees are below threshold (Karl-Johan Alm)

Pull request description:

  The `-avoidpartialspends` feature is normally disabled, as it may affect the optimal fee for payments. This PR introduces a new parameter `-maxapsfee` (max avoid partial spends fee) which acts on the following values:
  * -1: disable partial spend avoidance completely (do not even try it)
  * 0: only do partial spend avoidance if fees are the same or better as the regular coin selection
  * 1..∞: use APS variant if the absolute fee difference is less than or equal to the max APS fee

  For values other than -1, the code will now try partial spend avoidance once, and if that gives a value within the accepted range, it will use that.

  Example: -maxapsfee=0.00001000 means the wallet will do regular coin select, APS coin select, and then pick AKS iff the absolute fee difference is <= 1000 satoshi.

  Edit: updated this to reflect the fact we are now using a max fee.

ACKs for top commit:
  fjahr:
    tested ACK 7f13dfb587dd6a7a5b7dfbfe689ae0ce818fe5c9
  achow101:
    ACK 7f13dfb587dd6a7a5b7dfbfe689ae0ce818fe5c9
  jonatack:
    ACK 7f13dfb58, code review, debug build, verified the test fails with `AssertionError: not(2 == 1)` for the number of vouts when `-maxapsfee=0.0001` is changed to 0, and verified the new logging with an added assertion.
  meshcollider:
    Code review ACK 7f13dfb587dd6a7a5b7dfbfe689ae0ce818fe5c9

Tree-SHA512: 475929df57f6191bb4e36bfbcad5a280a64bb0ecd8767b76cb2e44e2301235d0eb294a3f2fac5bbf15d35d7ecfba47acb2285feadb883c9ce31c08377e3afb3c

3 files changed, 70 insertions, 1 deletions

diff --git a/src/wallet/init.cpp b/src/wallet/init.cpp
index 4c1fe57c66..bf05ef844a 100644
--- a/src/wallet/init.cpp
+++ b/src/wallet/init.cpp
@@ -49,6 +49,7 @@ void WalletInit::AddWalletOptions(ArgsManager& argsman) const
     argsman.AddArg("-fallbackfee=<amt>", strprintf("A fee rate (in %s/kB) that will be used when fee estimation has insufficient data. 0 to entirely disable the fallbackfee feature. (default: %s)",
                                                                CURRENCY_UNIT, FormatMoney(DEFAULT_FALLBACK_FEE)), ArgsManager::ALLOW_ANY, OptionsCategory::WALLET);
     argsman.AddArg("-keypool=<n>", strprintf("Set key pool size to <n> (default: %u). Warning: Smaller sizes may increase the risk of losing funds when restoring from an old backup, if none of the addresses in the original keypool have been used.", DEFAULT_KEYPOOL_SIZE), ArgsManager::ALLOW_ANY, OptionsCategory::WALLET);
+    argsman.AddArg("-maxapsfee=<n>", strprintf("Spend up to this amount in additional (absolute) fees (in %s) if it allows the use of partial spend avoidance (default: %s)", CURRENCY_UNIT, FormatMoney(DEFAULT_MAX_AVOIDPARTIALSPEND_FEE)), ArgsManager::ALLOW_ANY, OptionsCategory::WALLET);
     argsman.AddArg("-maxtxfee=<amt>", strprintf("Maximum total fees (in %s) to use in a single wallet transaction; setting this too low may abort large transactions (default: %s)",
         CURRENCY_UNIT, FormatMoney(DEFAULT_TRANSACTION_MAXFEE)), ArgsManager::ALLOW_ANY, OptionsCategory::DEBUG_TEST);
     argsman.AddArg("-mintxfee=<amt>", strprintf("Fees (in %s/kB) smaller than this are considered zero fee for transaction creation (default: %s)",
diff --git a/src/wallet/wallet.cpp b/src/wallet/wallet.cpp
index 9c7b446c23..ac03b3ca9c 100644
--- a/src/wallet/wallet.cpp
+++ b/src/wallet/wallet.cpp
@@ -2677,7 +2677,14 @@ OutputType CWallet::TransactionChangeType(const Optional<OutputType>& change_typ
     return m_default_address_type;
 }
 
-bool CWallet::CreateTransaction(const std::vector<CRecipient>& vecSend, CTransactionRef& tx, CAmount& nFeeRet, int& nChangePosInOut, bilingual_str& error, const CCoinControl& coin_control, bool sign)
+bool CWallet::CreateTransactionInternal(
+        const std::vector<CRecipient>& vecSend,
+        CTransactionRef& tx,
+        CAmount& nFeeRet,
+        int& nChangePosInOut,
+        bilingual_str& error,
+        const CCoinControl& coin_control,
+        bool sign)
 {
     CAmount nValue = 0;
     const OutputType change_type = TransactionChangeType(coin_control.m_change_type ? *coin_control.m_change_type : m_default_change_type, vecSend);
@@ -3032,6 +3039,39 @@ bool CWallet::CreateTransaction(const std::vector<CRecipient>& vecSend, CTransac
     return true;
 }
 
+bool CWallet::CreateTransaction(
+        const std::vector<CRecipient>& vecSend,
+        CTransactionRef& tx,
+        CAmount& nFeeRet,
+        int& nChangePosInOut,
+        bilingual_str& error,
+        const CCoinControl& coin_control,
+        bool sign)
+{
+    int nChangePosIn = nChangePosInOut;
+    CTransactionRef tx2 = tx;
+    bool res = CreateTransactionInternal(vecSend, tx, nFeeRet, nChangePosInOut, error, coin_control, sign);
+    // try with avoidpartialspends unless it's enabled already
+    if (res && nFeeRet > 0 /* 0 means non-functional fee rate estimation */ && m_max_aps_fee > -1 && !coin_control.m_avoid_partial_spends) {
+        CCoinControl tmp_cc = coin_control;
+        tmp_cc.m_avoid_partial_spends = true;
+        CAmount nFeeRet2;
+        int nChangePosInOut2 = nChangePosIn;
+        bilingual_str error2; // fired and forgotten; if an error occurs, we discard the results
+        if (CreateTransactionInternal(vecSend, tx2, nFeeRet2, nChangePosInOut2, error2, tmp_cc, sign)) {
+            // if fee of this alternative one is within the range of the max fee, we use this one
+            const bool use_aps = nFeeRet2 <= nFeeRet + m_max_aps_fee;
+            WalletLogPrintf("Fee non-grouped = %lld, grouped = %lld, using %s\n", nFeeRet, nFeeRet2, use_aps ? "grouped" : "non-grouped");
+            if (use_aps) {
+                tx = tx2;
+                nFeeRet = nFeeRet2;
+                nChangePosInOut = nChangePosInOut2;
+            }
+        }
+    }
+    return res;
+}
+
 void CWallet::CommitTransaction(CTransactionRef tx, mapValue_t mapValue, std::vector<std::pair<std::string, std::string>> orderForm)
 {
     LOCK(cs_wallet);
@@ -3849,6 +3889,21 @@ std::shared_ptr<CWallet> CWallet::CreateWalletFromFile(interfaces::Chain& chain,
         walletInstance->m_min_fee = CFeeRate(n);
     }
 
+    if (gArgs.IsArgSet("-maxapsfee")) {
+        CAmount n = 0;
+        if (gArgs.GetArg("-maxapsfee", "") == "-1") {
+            n = -1;
+        } else if (!ParseMoney(gArgs.GetArg("-maxapsfee", ""), n)) {
+            error = AmountErrMsg("maxapsfee", gArgs.GetArg("-maxapsfee", ""));
+            return nullptr;
+        }
+        if (n > HIGH_APS_FEE) {
+            warnings.push_back(AmountHighWarn("-maxapsfee") + Untranslated(" ") +
+                              _("This is the maximum transaction fee you pay to prioritize partial spend avoidance over regular coin selection."));
+        }
+        walletInstance->m_max_aps_fee = n;
+    }
+
     if (gArgs.IsArgSet("-fallbackfee")) {
         CAmount nFeePerK = 0;
         if (!ParseMoney(gArgs.GetArg("-fallbackfee", ""), nFeePerK)) {
diff --git a/src/wallet/wallet.h b/src/wallet/wallet.h
index a761caf38c..6d9512f59a 100644
--- a/src/wallet/wallet.h
+++ b/src/wallet/wallet.h
@@ -72,6 +72,16 @@ static const CAmount DEFAULT_FALLBACK_FEE = 0;
 static const CAmount DEFAULT_DISCARD_FEE = 10000;
 //! -mintxfee default
 static const CAmount DEFAULT_TRANSACTION_MINFEE = 1000;
+/**
+ * maximum fee increase allowed to do partial spend avoidance, even for nodes with this feature disabled by default
+ *
+ * A value of -1 disables this feature completely.
+ * A value of 0 (current default) means to attempt to do partial spend avoidance, and use its results if the fees remain *unchanged*
+ * A value > 0 means to do partial spend avoidance if the fee difference against a regular coin selection instance is in the range [0..value].
+ */
+static const CAmount DEFAULT_MAX_AVOIDPARTIALSPEND_FEE = 0;
+//! discourage APS fee higher than this amount
+constexpr CAmount HIGH_APS_FEE{COIN / 10000};
 //! minimum recommended increment for BIP 125 replacement txs
 static const CAmount WALLET_INCREMENTAL_RELAY_FEE = 5000;
 //! Default for -spendzeroconfchange
@@ -719,6 +729,8 @@ private:
     // ScriptPubKeyMan::GetID. In many cases it will be the hash of an internal structure
     std::map<uint256, std::unique_ptr<ScriptPubKeyMan>> m_spk_managers;
 
+    bool CreateTransactionInternal(const std::vector<CRecipient>& vecSend, CTransactionRef& tx, CAmount& nFeeRet, int& nChangePosInOut, bilingual_str& error, const CCoinControl& coin_control, bool sign);
+
 public:
     /*
      * Main wallet lock.
@@ -1008,6 +1020,7 @@ public:
      */
     CFeeRate m_fallback_fee{DEFAULT_FALLBACK_FEE};
     CFeeRate m_discard_rate{DEFAULT_DISCARD_FEE};
+    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};
     /**
      * Default output type for change outputs. When unset, automatically choose type