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

5 files changed, 119 insertions, 3 deletions

diff --git a/src/dummywallet.cpp b/src/dummywallet.cpp
index 18dc7a69e2..380d4eb8ac 100644
--- a/src/dummywallet.cpp
+++ b/src/dummywallet.cpp
@@ -35,6 +35,7 @@ void DummyWalletInit::AddWalletOptions(ArgsManager& argsman) const
         "-discardfee=<amt>",
         "-fallbackfee=<amt>",
         "-keypool=<n>",
+        "-maxapsfee=<n>",
         "-maxtxfee=<amt>",
         "-mintxfee=<amt>",
         "-paytxfee=<amt>",
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
diff --git a/test/functional/wallet_groups.py b/test/functional/wallet_groups.py
index b6fe295127..cfdc2d51e6 100755
--- a/test/functional/wallet_groups.py
+++ b/test/functional/wallet_groups.py
@@ -15,8 +15,8 @@ from test_framework.util import (
 class WalletGroupTest(BitcoinTestFramework):
     def set_test_params(self):
         self.setup_clean_chain = True
-        self.num_nodes = 3
-        self.extra_args = [[], [], ['-avoidpartialspends']]
+        self.num_nodes = 4
+        self.extra_args = [[], [], ['-avoidpartialspends'], ["-maxapsfee=0.0001"]]
         self.rpc_timeout = 480
 
     def skip_test_if_missing_module(self):
@@ -64,6 +64,52 @@ class WalletGroupTest(BitcoinTestFramework):
         assert_approx(v[0], 0.2)
         assert_approx(v[1], 1.3, 0.0001)
 
+        # Test 'avoid partial if warranted, even if disabled'
+        self.sync_all()
+        self.nodes[0].generate(1)
+        # Nodes 1-2 now have confirmed UTXOs (letters denote destinations):
+        # Node #1:      Node #2:
+        # - A  1.0      - D0 1.0
+        # - B0 1.0      - D1 0.5
+        # - B1 0.5      - E0 1.0
+        # - C0 1.0      - E1 0.5
+        # - C1 0.5      - F  ~1.3
+        # - D ~0.3
+        assert_approx(self.nodes[1].getbalance(), 4.3, 0.0001)
+        assert_approx(self.nodes[2].getbalance(), 4.3, 0.0001)
+        # Sending 1.4 btc should pick one 1.0 + one more. For node #1,
+        # this could be (A / B0 / C0) + (B1 / C1 / D). We ensure that it is
+        # B0 + B1 or C0 + C1, because this avoids partial spends while not being
+        # detrimental to transaction cost
+        txid3 = self.nodes[1].sendtoaddress(self.nodes[0].getnewaddress(), 1.4)
+        tx3 = self.nodes[1].getrawtransaction(txid3, True)
+        # tx3 should have 2 inputs and 2 outputs
+        assert_equal(2, len(tx3["vin"]))
+        assert_equal(2, len(tx3["vout"]))
+        # the accumulated value should be 1.5, so the outputs should be
+        # ~0.1 and 1.4 and should come from the same destination
+        values = [vout["value"] for vout in tx3["vout"]]
+        values.sort()
+        assert_approx(values[0], 0.1, 0.0001)
+        assert_approx(values[1], 1.4)
+
+        input_txids = [vin["txid"] for vin in tx3["vin"]]
+        input_addrs = [self.nodes[1].gettransaction(txid)['details'][0]['address'] for txid in input_txids]
+        assert_equal(input_addrs[0], input_addrs[1])
+        # Node 2 enforces avoidpartialspends so needs no checking here
+
+        # Test wallet option maxapsfee with Node 3
+        addr_aps = self.nodes[3].getnewaddress()
+        self.nodes[0].sendtoaddress(addr_aps, 1.0)
+        self.nodes[0].sendtoaddress(addr_aps, 1.0)
+        self.nodes[0].generate(1)
+        txid4 = self.nodes[3].sendtoaddress(self.nodes[0].getnewaddress(), 0.1)
+        tx4 = self.nodes[3].getrawtransaction(txid4, True)
+        # tx4 should have 2 inputs and 2 outputs although one output would
+        # have been enough and the transaction caused higher fees
+        assert_equal(2, len(tx4["vin"]))
+        assert_equal(2, len(tx4["vout"]))
+
         # Empty out node2's wallet
         self.nodes[2].sendtoaddress(address=self.nodes[0].getnewaddress(), amount=self.nodes[2].getbalance(), subtractfeefromamount=True)
         self.sync_all()