Merge #15557: Enhance `bumpfee` to include inputs when targeting a feerate

184f8785f wallet_bumpfee.py: add test for change key preservation (Gregory Sanders)
d08becff8 add functional tests for feerate bumpfee with adding inputs (Gregory Sanders)
0ea47ba7b generalize bumpfee to add inputs when needed (Gregory Sanders)

Pull request description:

  When targeting a feerate using `bumpfee`, call a new function that directly uses `CWallet::CreateTransaction` and coin control to get the desired result. This allows us to get a superset of previous behavior, with an arbitrary RBF bump of a transaction provided it passes the preconditional checks and spare confirmed utxos are available.

  Note(s):
  0) The coin selection will use knapsack solver for the residual selection.
  1) This functionality, just like knapsack coin selection in general, will hoover up negative-value inputs when given the chance.
  2) Newly added inputs must be confirmed due to current Core policy. See error: `replacement-adds-unconfirmed`
  3) Supporting this with `totalFee` is difficult since the "minimum total fee" option in `CreateTransaction` logic was (rightly)taken out in #10390 .

ACKs for commit 184f87:
  jnewbery:
    utACK 184f8785f710d58d9ef82e611591c9cbff5ab89d

Tree-SHA512: fb6542bdfb2c6010e328ec475cf9dcbff4eb2b1a1b27f78010214534908987a5635797196fa05edddffcbcf2987335872dc644a99261886d5cbb34a8f262ad3e

6 files changed, 153 insertions, 43 deletions

diff --git a/src/interfaces/wallet.cpp b/src/interfaces/wallet.cpp
index f98a49f9b1..ed73a71354 100644
--- a/src/interfaces/wallet.cpp
+++ b/src/interfaces/wallet.cpp
@@ -269,8 +269,13 @@ public:
         CAmount& new_fee,
         CMutableTransaction& mtx) override
     {
-        return feebumper::CreateTransaction(m_wallet.get(), txid, coin_control, total_fee, errors, old_fee, new_fee, mtx) ==
-               feebumper::Result::OK;
+        if (total_fee > 0) {
+            return feebumper::CreateTotalBumpTransaction(m_wallet.get(), txid, coin_control, total_fee, errors, old_fee, new_fee, mtx) ==
+                feebumper::Result::OK;
+        } else {
+            return feebumper::CreateRateBumpTransaction(m_wallet.get(), txid, coin_control, errors, old_fee, new_fee, mtx) ==
+                feebumper::Result::OK;
+        }
     }
     bool signBumpTransaction(CMutableTransaction& mtx) override { return feebumper::SignTransaction(m_wallet.get(), mtx); }
     bool commitBumpTransaction(const uint256& txid,
diff --git a/src/wallet/coincontrol.h b/src/wallet/coincontrol.h
index 48a924abfb..9257b272bc 100644
--- a/src/wallet/coincontrol.h
+++ b/src/wallet/coincontrol.h
@@ -36,6 +36,8 @@ public:
     bool m_avoid_partial_spends;
     //! Fee estimation mode to control arguments to estimateSmartFee
     FeeEstimateMode m_fee_mode;
+    //! Minimum chain depth value for coin availability
+    int m_min_depth{0};
 
     CCoinControl()
     {
diff --git a/src/wallet/feebumper.cpp b/src/wallet/feebumper.cpp
index b547ea21d9..4ec9dca420 100644
--- a/src/wallet/feebumper.cpp
+++ b/src/wallet/feebumper.cpp
@@ -75,9 +75,11 @@ bool TransactionCanBeBumped(const CWallet* wallet, const uint256& txid)
     return res == feebumper::Result::OK;
 }
 
-Result CreateTransaction(const CWallet* wallet, const uint256& txid, const CCoinControl& coin_control, CAmount total_fee, std::vector<std::string>& errors,
-                         CAmount& old_fee, CAmount& new_fee, CMutableTransaction& mtx)
+Result CreateTotalBumpTransaction(const CWallet* wallet, const uint256& txid, const CCoinControl& coin_control, CAmount total_fee, std::vector<std::string>& errors,
+                                  CAmount& old_fee, CAmount& new_fee, CMutableTransaction& mtx)
 {
+    new_fee = total_fee;
+
     auto locked_chain = wallet->chain().lock();
     LOCK(wallet->cs_wallet);
     errors.clear();
@@ -121,7 +123,6 @@ Result CreateTransaction(const CWallet* wallet, const uint256& txid, const CCoin
     // calculate the old fee and fee-rate
     old_fee = wtx.GetDebit(ISMINE_SPENDABLE) - wtx.tx->GetValueOut();
     CFeeRate nOldFeeRate(old_fee, txSize);
-    CFeeRate nNewFeeRate;
     // The wallet uses a conservative WALLET_INCREMENTAL_RELAY_FEE value to
     // future proof against changes to network wide policy for incremental relay
     // fee that our node may not be aware of.
@@ -131,34 +132,17 @@ Result CreateTransaction(const CWallet* wallet, const uint256& txid, const CCoin
         walletIncrementalRelayFee = nodeIncrementalRelayFee;
     }
 
-    if (total_fee > 0) {
-        CAmount minTotalFee = nOldFeeRate.GetFee(maxNewTxSize) + nodeIncrementalRelayFee.GetFee(maxNewTxSize);
-        if (total_fee < minTotalFee) {
-            errors.push_back(strprintf("Insufficient totalFee, must be at least %s (oldFee %s + incrementalFee %s)",
-                                                                FormatMoney(minTotalFee), FormatMoney(nOldFeeRate.GetFee(maxNewTxSize)), FormatMoney(nodeIncrementalRelayFee.GetFee(maxNewTxSize))));
-            return Result::INVALID_PARAMETER;
-        }
-        CAmount requiredFee = GetRequiredFee(*wallet, maxNewTxSize);
-        if (total_fee < requiredFee) {
-            errors.push_back(strprintf("Insufficient totalFee (cannot be less than required fee %s)",
-                                                                FormatMoney(requiredFee)));
-            return Result::INVALID_PARAMETER;
-        }
-        new_fee = total_fee;
-        nNewFeeRate = CFeeRate(total_fee, maxNewTxSize);
-    } else {
-        new_fee = GetMinimumFee(*wallet, maxNewTxSize, coin_control, nullptr /* FeeCalculation */);
-        nNewFeeRate = CFeeRate(new_fee, maxNewTxSize);
-
-        // New fee rate must be at least old rate + minimum incremental relay rate
-        // walletIncrementalRelayFee.GetFeePerK() should be exact, because it's initialized
-        // in that unit (fee per kb).
-        // However, nOldFeeRate is a calculated value from the tx fee/size, so
-        // add 1 satoshi to the result, because it may have been rounded down.
-        if (nNewFeeRate.GetFeePerK() < nOldFeeRate.GetFeePerK() + 1 + walletIncrementalRelayFee.GetFeePerK()) {
-            nNewFeeRate = CFeeRate(nOldFeeRate.GetFeePerK() + 1 + walletIncrementalRelayFee.GetFeePerK());
-            new_fee = nNewFeeRate.GetFee(maxNewTxSize);
-        }
+    CAmount minTotalFee = nOldFeeRate.GetFee(maxNewTxSize) + nodeIncrementalRelayFee.GetFee(maxNewTxSize);
+    if (total_fee < minTotalFee) {
+        errors.push_back(strprintf("Insufficient totalFee, must be at least %s (oldFee %s + incrementalFee %s)",
+            FormatMoney(minTotalFee), FormatMoney(nOldFeeRate.GetFee(maxNewTxSize)), FormatMoney(nodeIncrementalRelayFee.GetFee(maxNewTxSize))));
+        return Result::INVALID_PARAMETER;
+    }
+    CAmount requiredFee = GetRequiredFee(*wallet, maxNewTxSize);
+    if (total_fee < requiredFee) {
+        errors.push_back(strprintf("Insufficient totalFee (cannot be less than required fee %s)",
+            FormatMoney(requiredFee)));
+        return Result::INVALID_PARAMETER;
     }
 
     // Check that in all cases the new fee doesn't violate maxTxFee
@@ -175,14 +159,14 @@ Result CreateTransaction(const CWallet* wallet, const uint256& txid, const CCoin
     // in a rare situation where the mempool minimum fee increased significantly since the fee estimation just a
     // moment earlier. In this case, we report an error to the user, who may use total_fee to make an adjustment.
     CFeeRate minMempoolFeeRate = wallet->chain().mempoolMinFee();
+    CFeeRate nNewFeeRate = CFeeRate(total_fee, maxNewTxSize);
     if (nNewFeeRate.GetFeePerK() < minMempoolFeeRate.GetFeePerK()) {
         errors.push_back(strprintf(
             "New fee rate (%s) is lower than the minimum fee rate (%s) to get into the mempool -- "
-            "the totalFee value should be at least %s or the settxfee value should be at least %s to add transaction",
+            "the totalFee value should be at least %s to add transaction",
             FormatMoney(nNewFeeRate.GetFeePerK()),
             FormatMoney(minMempoolFeeRate.GetFeePerK()),
-            FormatMoney(minMempoolFeeRate.GetFee(maxNewTxSize)),
-            FormatMoney(minMempoolFeeRate.GetFeePerK())));
+            FormatMoney(minMempoolFeeRate.GetFee(maxNewTxSize))));
         return Result::WALLET_ERROR;
     }
 
@@ -212,6 +196,109 @@ Result CreateTransaction(const CWallet* wallet, const uint256& txid, const CCoin
         }
     }
 
+    return Result::OK;
+}
+
+
+Result CreateRateBumpTransaction(CWallet* wallet, const uint256& txid, const CCoinControl& coin_control, std::vector<std::string>& errors,
+                                 CAmount& old_fee, CAmount& new_fee, CMutableTransaction& mtx)
+{
+    // We are going to modify coin control later, copy to re-use
+    CCoinControl new_coin_control(coin_control);
+
+    auto locked_chain = wallet->chain().lock();
+    LOCK(wallet->cs_wallet);
+    errors.clear();
+    auto it = wallet->mapWallet.find(txid);
+    if (it == wallet->mapWallet.end()) {
+        errors.push_back("Invalid or non-wallet transaction id");
+        return Result::INVALID_ADDRESS_OR_KEY;
+    }
+    const CWalletTx& wtx = it->second;
+
+    Result result = PreconditionChecks(*locked_chain, wallet, wtx, errors);
+    if (result != Result::OK) {
+        return result;
+    }
+
+    // Fill in recipients(and preserve a single change key if there is one)
+    std::vector<CRecipient> recipients;
+    for (const auto& output : wtx.tx->vout) {
+        if (!wallet->IsChange(output)) {
+            CRecipient recipient = {output.scriptPubKey, output.nValue, false};
+            recipients.push_back(recipient);
+        } else {
+            CTxDestination change_dest;
+            ExtractDestination(output.scriptPubKey, change_dest);
+            new_coin_control.destChange = change_dest;
+        }
+    }
+
+    // Get the fee rate of the original transaction. This is calculated from
+    // the tx fee/vsize, so it may have been rounded down. Add 1 satoshi to the
+    // result.
+    old_fee = wtx.GetDebit(ISMINE_SPENDABLE) - wtx.tx->GetValueOut();
+    int64_t txSize = GetVirtualTransactionSize(*(wtx.tx));
+    // Feerate of thing we are bumping
+    CFeeRate feerate(old_fee, txSize);
+    feerate += CFeeRate(1);
+
+    // The node has a configurable incremental relay fee. Increment the fee by
+    // the minimum of that and the wallet's conservative
+    // WALLET_INCREMENTAL_RELAY_FEE value to future proof against changes to
+    // network wide policy for incremental relay fee that our node may not be
+    // aware of. This ensures we're over the over the required relay fee rate
+    // (BIP 125 rule 4).  The replacement tx will be at least as large as the
+    // original tx, so the total fee will be greater (BIP 125 rule 3)
+    CFeeRate node_incremental_relay_fee = wallet->chain().relayIncrementalFee();
+    CFeeRate wallet_incremental_relay_fee = CFeeRate(WALLET_INCREMENTAL_RELAY_FEE);
+    feerate += std::max(node_incremental_relay_fee, wallet_incremental_relay_fee);
+
+    // Fee rate must also be at least the wallet's GetMinimumFeeRate
+    CFeeRate min_feerate(GetMinimumFeeRate(*wallet, new_coin_control, /* feeCalc */ nullptr));
+
+    // Set the required fee rate for the replacement transaction in coin control.
+    new_coin_control.m_feerate = std::max(feerate, min_feerate);
+
+    // Fill in required inputs we are double-spending(all of them)
+    // N.B.: bip125 doesn't require all the inputs in the replaced transaction to be
+    // used in the replacement transaction, but it's very important for wallets to make
+    // sure that happens. If not, it would be possible to bump a transaction A twice to
+    // A2 and A3 where A2 and A3 don't conflict (or alternatively bump A to A2 and A2
+    // to A3 where A and A3 don't conflict). If both later get confirmed then the sender
+    // has accidentally double paid.
+    for (const auto& inputs : wtx.tx->vin) {
+        new_coin_control.Select(COutPoint(inputs.prevout));
+    }
+    new_coin_control.fAllowOtherInputs = true;
+
+    // We cannot source new unconfirmed inputs(bip125 rule 2)
+    new_coin_control.m_min_depth = 1;
+
+    CTransactionRef tx_new = MakeTransactionRef();
+    CReserveKey reservekey(wallet);
+    CAmount fee_ret;
+    int change_pos_in_out = -1; // No requested location for change
+    std::string fail_reason;
+    if (!wallet->CreateTransaction(*locked_chain, recipients, tx_new, reservekey, fee_ret, change_pos_in_out, fail_reason, new_coin_control, false)) {
+        errors.push_back("Unable to create transaction: " + fail_reason);
+        return Result::WALLET_ERROR;
+    }
+
+    // If change key hasn't been ReturnKey'ed by this point, we take it out of keypool
+    reservekey.KeepKey();
+
+    // Write back new fee if successful
+    new_fee = fee_ret;
+
+    // Write back transaction
+    mtx = CMutableTransaction(*tx_new);
+    // Mark new tx not replaceable, if requested.
+    if (!coin_control.m_signal_bip125_rbf.get_value_or(wallet->m_signal_rbf)) {
+        for (auto& input : mtx.vin) {
+            if (input.nSequence < 0xfffffffe) input.nSequence = 0xfffffffe;
+        }
+    }
 
     return Result::OK;
 }
diff --git a/src/wallet/feebumper.h b/src/wallet/feebumper.h
index a1eb5d0e0d..f9cbfc5f68 100644
--- a/src/wallet/feebumper.h
+++ b/src/wallet/feebumper.h
@@ -28,8 +28,8 @@ enum class Result
 //! Return whether transaction can be bumped.
 bool TransactionCanBeBumped(const CWallet* wallet, const uint256& txid);
 
-//! Create bumpfee transaction.
-Result CreateTransaction(const CWallet* wallet,
+//! Create bumpfee transaction based on total amount.
+Result CreateTotalBumpTransaction(const CWallet* wallet,
                          const uint256& txid,
                          const CCoinControl& coin_control,
                          CAmount total_fee,
@@ -38,6 +38,15 @@ Result CreateTransaction(const CWallet* wallet,
                          CAmount& new_fee,
                          CMutableTransaction& mtx);
 
+//! Create bumpfee transaction based on feerate estimates.
+Result CreateRateBumpTransaction(CWallet* wallet,
+                         const uint256& txid,
+                         const CCoinControl& coin_control,
+                         std::vector<std::string>& errors,
+                         CAmount& old_fee,
+                         CAmount& new_fee,
+                         CMutableTransaction& mtx);
+
 //! Sign the new transaction,
 //! @return false if the tx couldn't be found or if it was
 //! impossible to create the signature(s)
diff --git a/src/wallet/rpcwallet.cpp b/src/wallet/rpcwallet.cpp
index cb6f7637ad..c0c9345bd7 100644
--- a/src/wallet/rpcwallet.cpp
+++ b/src/wallet/rpcwallet.cpp
@@ -3167,9 +3167,9 @@ static UniValue bumpfee(const JSONRPCRequest& request)
             RPCHelpMan{"bumpfee",
                 "\nBumps the fee of an opt-in-RBF transaction T, replacing it with a new transaction B.\n"
                 "An opt-in RBF transaction with the given txid must be in the wallet.\n"
-                "The command will pay the additional fee by decreasing (or perhaps removing) its change output.\n"
-                "If the change output is not big enough to cover the increased fee, the command will currently fail\n"
-                "instead of adding new inputs to compensate. (A future implementation could improve this.)\n"
+                "The command will pay the additional fee by reducing change outputs or adding inputs when necessary. It may add a new change output if one does not already exist.\n"
+                "If `totalFee` is given, adding inputs is not supported, so there must be a single change output that is big enough or it will fail.\n"
+                "All inputs in the original transaction will be included in the replacement transaction.\n"
                 "The command will fail if the wallet or mempool contains a transaction that spends one of T's outputs.\n"
                 "By default, the new fee will be calculated automatically using estimatesmartfee.\n"
                 "The user can specify a confirmation target for estimatesmartfee.\n"
@@ -3266,7 +3266,14 @@ static UniValue bumpfee(const JSONRPCRequest& request)
     CAmount old_fee;
     CAmount new_fee;
     CMutableTransaction mtx;
-    feebumper::Result res = feebumper::CreateTransaction(pwallet, hash, coin_control, totalFee, errors, old_fee, new_fee, mtx);
+    feebumper::Result res;
+    if (totalFee > 0) {
+        // Targeting total fee bump. Requires a change output of sufficient size.
+        res = feebumper::CreateTotalBumpTransaction(pwallet, hash, coin_control, totalFee, errors, old_fee, new_fee, mtx);
+    } else {
+        // Targeting feerate bump.
+        res = feebumper::CreateRateBumpTransaction(pwallet, hash, coin_control, errors, old_fee, new_fee, mtx);
+    }
     if (res != feebumper::Result::OK) {
         switch(res) {
             case feebumper::Result::INVALID_ADDRESS_OR_KEY:
diff --git a/src/wallet/wallet.cpp b/src/wallet/wallet.cpp
index 9ee6329f8c..98ba489729 100644
--- a/src/wallet/wallet.cpp
+++ b/src/wallet/wallet.cpp
@@ -2736,7 +2736,7 @@ bool CWallet::CreateTransaction(interfaces::Chain::Lock& locked_chain, const std
         LOCK(cs_wallet);
         {
             std::vector<COutput> vAvailableCoins;
-            AvailableCoins(*locked_chain, vAvailableCoins, true, &coin_control);
+            AvailableCoins(*locked_chain, vAvailableCoins, true, &coin_control, 1, MAX_MONEY, MAX_MONEY, 0, coin_control.m_min_depth);
             CoinSelectionParams coin_selection_params; // Parameters for coin selection, init with dummy
 
             // Create change script that will be used if we need change