diff options
| -rw-r--r-- | src/bench/coin_selection.cpp | 2 | ||||
| -rw-r--r-- | src/interfaces/chain.h | 37 | ||||
| -rw-r--r-- | src/node/interfaces.cpp | 21 | ||||
| -rw-r--r-- | src/node/mini_miner.cpp | 7 | ||||
| -rw-r--r-- | src/node/mini_miner.h | 9 | ||||
| -rw-r--r-- | src/test/miniminer_tests.cpp | 399 | ||||
| -rw-r--r-- | src/wallet/coinselection.cpp | 31 | ||||
| -rw-r--r-- | src/wallet/coinselection.h | 62 | ||||
| -rw-r--r-- | src/wallet/feebumper.cpp | 16 | ||||
| -rw-r--r-- | src/wallet/spend.cpp | 50 | ||||
| -rw-r--r-- | src/wallet/spend.h | 6 | ||||
| -rw-r--r-- | src/wallet/test/coinselector_tests.cpp | 270 | ||||
| -rwxr-xr-x | test/functional/test_runner.py | 1 | ||||
| -rwxr-xr-x | test/functional/wallet_spend_unconfirmed.py | 508 |
14 files changed, 1094 insertions, 325 deletions
diff --git a/src/bench/coin_selection.cpp b/src/bench/coin_selection.cpp index 0e110a653a..249b76ee85 100644 --- a/src/bench/coin_selection.cpp +++ b/src/bench/coin_selection.cpp @@ -79,7 +79,7 @@ static void CoinSelection(benchmark::Bench& bench) }; auto group = wallet::GroupOutputs(wallet, available_coins, coin_selection_params, {{filter_standard}})[filter_standard]; bench.run([&] { - auto result = AttemptSelection(1003 * COIN, group, coin_selection_params, /*allow_mixed_output_types=*/true); + auto result = AttemptSelection(wallet.chain(), 1003 * COIN, group, coin_selection_params, /*allow_mixed_output_types=*/true); assert(result); assert(result->GetSelectedValue() == 1003 * COIN); assert(result->GetInputSet().size() == 2); diff --git a/src/interfaces/chain.h b/src/interfaces/chain.h index dd664165d3..b5243725ad 100644 --- a/src/interfaces/chain.h +++ b/src/interfaces/chain.h @@ -216,6 +216,43 @@ public: //! Calculate mempool ancestor and descendant counts for the given transaction. virtual void getTransactionAncestry(const uint256& txid, size_t& ancestors, size_t& descendants, size_t* ancestorsize = nullptr, CAmount* ancestorfees = nullptr) = 0; + //! For each outpoint, calculate the fee-bumping cost to spend this outpoint at the specified + // feerate, including bumping its ancestors. For example, if the target feerate is 10sat/vbyte + // and this outpoint refers to a mempool transaction at 3sat/vbyte, the bump fee includes the + // cost to bump the mempool transaction to 10sat/vbyte (i.e. 7 * mempooltx.vsize). If that + // transaction also has, say, an unconfirmed parent with a feerate of 1sat/vbyte, the bump fee + // includes the cost to bump the parent (i.e. 9 * parentmempooltx.vsize). + // + // If the outpoint comes from an unconfirmed transaction that is already above the target + // feerate or bumped by its descendant(s) already, it does not need to be bumped. Its bump fee + // is 0. Likewise, if any of the transaction's ancestors are already bumped by a transaction + // in our mempool, they are not included in the transaction's bump fee. + // + // Also supported is bump-fee calculation in the case of replacements. If an outpoint + // conflicts with another transaction in the mempool, it is assumed that the goal is to replace + // that transaction. As such, the calculation will exclude the to-be-replaced transaction, but + // will include the fee-bumping cost. If bump fees of descendants of the to-be-replaced + // transaction are requested, the value will be 0. Fee-related RBF rules are not included as + // they are logically distinct. + // + // Any outpoints that are otherwise unavailable from the mempool (e.g. UTXOs from confirmed + // transactions or transactions not yet broadcast by the wallet) are given a bump fee of 0. + // + // If multiple outpoints come from the same transaction (which would be very rare because + // it means that one transaction has multiple change outputs or paid the same wallet using multiple + // outputs in the same transaction) or have shared ancestry, the bump fees are calculated + // independently, i.e. as if only one of them is spent. This may result in double-fee-bumping. This + // caveat can be rectified per use of the sister-function CalculateCombinedBumpFee(…). + virtual std::map<COutPoint, CAmount> CalculateIndividualBumpFees(const std::vector<COutPoint>& outpoints, const CFeeRate& target_feerate) = 0; + + //! Calculate the combined bump fee for an input set per the same strategy + // as in CalculateIndividualBumpFees(…). + // Unlike CalculateIndividualBumpFees(…), this does not return individual + // bump fees per outpoint, but a single bump fee for the shared ancestry. + // The combined bump fee may be used to correct overestimation due to + // shared ancestry by multiple UTXOs after coin selection. + virtual std::optional<CAmount> CalculateCombinedBumpFee(const std::vector<COutPoint>& outpoints, const CFeeRate& target_feerate) = 0; + //! Get the node's package limits. //! Currently only returns the ancestor and descendant count limits, but could be enhanced to //! return more policy settings. diff --git a/src/node/interfaces.cpp b/src/node/interfaces.cpp index a6d84555c0..e0c40036d9 100644 --- a/src/node/interfaces.cpp +++ b/src/node/interfaces.cpp @@ -28,6 +28,7 @@ #include <node/coin.h> #include <node/context.h> #include <node/interface_ui.h> +#include <node/mini_miner.h> #include <node/transaction.h> #include <policy/feerate.h> #include <policy/fees.h> @@ -665,6 +666,26 @@ public: if (!m_node.mempool) return; m_node.mempool->GetTransactionAncestry(txid, ancestors, descendants, ancestorsize, ancestorfees); } + + std::map<COutPoint, CAmount> CalculateIndividualBumpFees(const std::vector<COutPoint>& outpoints, const CFeeRate& target_feerate) override + { + if (!m_node.mempool) { + std::map<COutPoint, CAmount> bump_fees; + for (const auto& outpoint : outpoints) { + bump_fees.emplace(std::make_pair(outpoint, 0)); + } + return bump_fees; + } + return MiniMiner(*m_node.mempool, outpoints).CalculateBumpFees(target_feerate); + } + + std::optional<CAmount> CalculateCombinedBumpFee(const std::vector<COutPoint>& outpoints, const CFeeRate& target_feerate) override + { + if (!m_node.mempool) { + return 0; + } + return MiniMiner(*m_node.mempool, outpoints).CalculateTotalBumpFees(target_feerate); + } void getPackageLimits(unsigned int& limit_ancestor_count, unsigned int& limit_descendant_count) override { const CTxMemPool::Limits default_limits{}; diff --git a/src/node/mini_miner.cpp b/src/node/mini_miner.cpp index 6f253eddfa..2827242f96 100644 --- a/src/node/mini_miner.cpp +++ b/src/node/mini_miner.cpp @@ -7,9 +7,7 @@ #include <consensus/amount.h> #include <policy/feerate.h> #include <primitives/transaction.h> -#include <timedata.h> #include <util/check.h> -#include <util/moneystr.h> #include <algorithm> #include <numeric> @@ -171,9 +169,8 @@ void MiniMiner::DeleteAncestorPackage(const std::set<MockEntryMap::iterator, Ite for (auto& descendant : it->second) { // If these fail, we must be double-deducting. Assume(descendant->second.GetModFeesWithAncestors() >= anc->second.GetModifiedFee()); - Assume(descendant->second.vsize_with_ancestors >= anc->second.GetTxSize()); - descendant->second.fee_with_ancestors -= anc->second.GetModifiedFee(); - descendant->second.vsize_with_ancestors -= anc->second.GetTxSize(); + Assume(descendant->second.GetSizeWithAncestors() >= anc->second.GetTxSize()); + descendant->second.UpdateAncestorState(-anc->second.GetTxSize(), -anc->second.GetModifiedFee()); } } // Delete these entries. diff --git a/src/node/mini_miner.h b/src/node/mini_miner.h index db07e6d1bf..9d9d66bf0b 100644 --- a/src/node/mini_miner.h +++ b/src/node/mini_miner.h @@ -19,12 +19,13 @@ class MiniMinerMempoolEntry const CAmount fee_individual; const CTransactionRef tx; const int64_t vsize_individual; + CAmount fee_with_ancestors; + int64_t vsize_with_ancestors; // This class must be constructed while holding mempool.cs. After construction, the object's // methods can be called without holding that lock. + public: - CAmount fee_with_ancestors; - int64_t vsize_with_ancestors; explicit MiniMinerMempoolEntry(CTxMemPool::txiter entry) : fee_individual{entry->GetModifiedFee()}, tx{entry->GetSharedTx()}, @@ -38,6 +39,10 @@ public: int64_t GetTxSize() const { return vsize_individual; } int64_t GetSizeWithAncestors() const { return vsize_with_ancestors; } const CTransaction& GetTx() const LIFETIMEBOUND { return *tx; } + void UpdateAncestorState(int64_t vsize_change, CAmount fee_change) { + vsize_with_ancestors += vsize_change; + fee_with_ancestors += fee_change; + } }; // Comparator needed for std::set<MockEntryMap::iterator> diff --git a/src/test/miniminer_tests.cpp b/src/test/miniminer_tests.cpp index da724f8d7b..f65356936b 100644 --- a/src/test/miniminer_tests.cpp +++ b/src/test/miniminer_tests.cpp @@ -77,66 +77,66 @@ BOOST_FIXTURE_TEST_CASE(miniminer_1p1c, TestChain100Setup) const CAmount normal_fee{CENT/200}; const CAmount high_fee{CENT/10}; - // Create a parent tx1 and child tx2 with normal fees: - const auto tx1 = make_tx({COutPoint{m_coinbase_txns[0]->GetHash(), 0}}, /*num_outputs=*/2); + // Create a parent tx0 and child tx1 with normal fees: + const auto tx0 = make_tx({COutPoint{m_coinbase_txns[0]->GetHash(), 0}}, /*num_outputs=*/2); + pool.addUnchecked(entry.Fee(normal_fee).FromTx(tx0)); + const auto tx1 = make_tx({COutPoint{tx0->GetHash(), 0}}, /*num_outputs=*/1); pool.addUnchecked(entry.Fee(normal_fee).FromTx(tx1)); - const auto tx2 = make_tx({COutPoint{tx1->GetHash(), 0}}, /*num_outputs=*/1); - pool.addUnchecked(entry.Fee(normal_fee).FromTx(tx2)); - // Create a low-feerate parent tx3 and high-feerate child tx4 (cpfp) - const auto tx3 = make_tx({COutPoint{m_coinbase_txns[1]->GetHash(), 0}}, /*num_outputs=*/2); - pool.addUnchecked(entry.Fee(low_fee).FromTx(tx3)); - const auto tx4 = make_tx({COutPoint{tx3->GetHash(), 0}}, /*num_outputs=*/1); - pool.addUnchecked(entry.Fee(high_fee).FromTx(tx4)); + // Create a low-feerate parent tx2 and high-feerate child tx3 (cpfp) + const auto tx2 = make_tx({COutPoint{m_coinbase_txns[1]->GetHash(), 0}}, /*num_outputs=*/2); + pool.addUnchecked(entry.Fee(low_fee).FromTx(tx2)); + const auto tx3 = make_tx({COutPoint{tx2->GetHash(), 0}}, /*num_outputs=*/1); + pool.addUnchecked(entry.Fee(high_fee).FromTx(tx3)); - // Create a parent tx5 and child tx6 where both have low fees - const auto tx5 = make_tx({COutPoint{m_coinbase_txns[2]->GetHash(), 0}}, /*num_outputs=*/2); + // Create a parent tx4 and child tx5 where both have low fees + const auto tx4 = make_tx({COutPoint{m_coinbase_txns[2]->GetHash(), 0}}, /*num_outputs=*/2); + pool.addUnchecked(entry.Fee(low_fee).FromTx(tx4)); + const auto tx5 = make_tx({COutPoint{tx4->GetHash(), 0}}, /*num_outputs=*/1); pool.addUnchecked(entry.Fee(low_fee).FromTx(tx5)); - const auto tx6 = make_tx({COutPoint{tx5->GetHash(), 0}}, /*num_outputs=*/1); - pool.addUnchecked(entry.Fee(low_fee).FromTx(tx6)); - // Make tx6's modified fee much higher than its base fee. This should cause it to pass + // Make tx5's modified fee much higher than its base fee. This should cause it to pass // the fee-related checks despite being low-feerate. - pool.PrioritiseTransaction(tx6->GetHash(), CENT/100); + pool.PrioritiseTransaction(tx5->GetHash(), CENT/100); - // Create a high-feerate parent tx7, low-feerate child tx8 - const auto tx7 = make_tx({COutPoint{m_coinbase_txns[3]->GetHash(), 0}}, /*num_outputs=*/2); - pool.addUnchecked(entry.Fee(high_fee).FromTx(tx7)); - const auto tx8 = make_tx({COutPoint{tx7->GetHash(), 0}}, /*num_outputs=*/1); - pool.addUnchecked(entry.Fee(low_fee).FromTx(tx8)); + // Create a high-feerate parent tx6, low-feerate child tx7 + const auto tx6 = make_tx({COutPoint{m_coinbase_txns[3]->GetHash(), 0}}, /*num_outputs=*/2); + pool.addUnchecked(entry.Fee(high_fee).FromTx(tx6)); + const auto tx7 = make_tx({COutPoint{tx6->GetHash(), 0}}, /*num_outputs=*/1); + pool.addUnchecked(entry.Fee(low_fee).FromTx(tx7)); std::vector<COutPoint> all_unspent_outpoints({ - COutPoint{tx1->GetHash(), 1}, - COutPoint{tx2->GetHash(), 0}, - COutPoint{tx3->GetHash(), 1}, - COutPoint{tx4->GetHash(), 0}, - COutPoint{tx5->GetHash(), 1}, - COutPoint{tx6->GetHash(), 0}, - COutPoint{tx7->GetHash(), 1}, - COutPoint{tx8->GetHash(), 0} - }); - for (const auto& outpoint : all_unspent_outpoints) BOOST_CHECK(!pool.isSpent(outpoint)); - - std::vector<COutPoint> all_spent_outpoints({ + COutPoint{tx0->GetHash(), 1}, COutPoint{tx1->GetHash(), 0}, + COutPoint{tx2->GetHash(), 1}, COutPoint{tx3->GetHash(), 0}, + COutPoint{tx4->GetHash(), 1}, COutPoint{tx5->GetHash(), 0}, + COutPoint{tx6->GetHash(), 1}, COutPoint{tx7->GetHash(), 0} }); + for (const auto& outpoint : all_unspent_outpoints) BOOST_CHECK(!pool.isSpent(outpoint)); + + std::vector<COutPoint> all_spent_outpoints({ + COutPoint{tx0->GetHash(), 0}, + COutPoint{tx2->GetHash(), 0}, + COutPoint{tx4->GetHash(), 0}, + COutPoint{tx6->GetHash(), 0} + }); for (const auto& outpoint : all_spent_outpoints) BOOST_CHECK(pool.GetConflictTx(outpoint) != nullptr); std::vector<COutPoint> all_parent_outputs({ - COutPoint{tx1->GetHash(), 0}, - COutPoint{tx1->GetHash(), 1}, - COutPoint{tx3->GetHash(), 0}, - COutPoint{tx3->GetHash(), 1}, - COutPoint{tx5->GetHash(), 0}, - COutPoint{tx5->GetHash(), 1}, - COutPoint{tx7->GetHash(), 0}, - COutPoint{tx7->GetHash(), 1} + COutPoint{tx0->GetHash(), 0}, + COutPoint{tx0->GetHash(), 1}, + COutPoint{tx2->GetHash(), 0}, + COutPoint{tx2->GetHash(), 1}, + COutPoint{tx4->GetHash(), 0}, + COutPoint{tx4->GetHash(), 1}, + COutPoint{tx6->GetHash(), 0}, + COutPoint{tx6->GetHash(), 1} }); - std::vector<CTransactionRef> all_transactions{tx1, tx2, tx3, tx4, tx5, tx6, tx7, tx8}; + std::vector<CTransactionRef> all_transactions{tx0, tx1, tx2, tx3, tx4, tx5, tx6, tx7}; struct TxDimensions { int32_t vsize; CAmount mod_fee; CFeeRate feerate; }; @@ -178,47 +178,47 @@ BOOST_FIXTURE_TEST_CASE(miniminer_1p1c, TestChain100Setup) BOOST_CHECK(sanity_check(all_transactions, bump_fees)); BOOST_CHECK_EQUAL(bump_fees.size(), all_unspent_outpoints.size()); - // Check tx1 bumpfee: no other bumper. - const TxDimensions& tx1_dimensions = tx_dims.find(tx1->GetHash())->second; - CAmount bumpfee1 = Find(bump_fees, COutPoint{tx1->GetHash(), 1}); - if (target_feerate <= tx1_dimensions.feerate) { - BOOST_CHECK_EQUAL(bumpfee1, 0); + // Check tx0 bumpfee: no other bumper. + const TxDimensions& tx0_dimensions = tx_dims.find(tx0->GetHash())->second; + CAmount bumpfee0 = Find(bump_fees, COutPoint{tx0->GetHash(), 1}); + if (target_feerate <= tx0_dimensions.feerate) { + BOOST_CHECK_EQUAL(bumpfee0, 0); } else { - // Difference is fee to bump tx1 from current to target feerate. - BOOST_CHECK_EQUAL(bumpfee1, target_feerate.GetFee(tx1_dimensions.vsize) - tx1_dimensions.mod_fee); + // Difference is fee to bump tx0 from current to target feerate. + BOOST_CHECK_EQUAL(bumpfee0, target_feerate.GetFee(tx0_dimensions.vsize) - tx0_dimensions.mod_fee); } - // Check tx3 bumpfee: assisted by tx4. + // Check tx2 bumpfee: assisted by tx3. + const TxDimensions& tx2_dimensions = tx_dims.find(tx2->GetHash())->second; const TxDimensions& tx3_dimensions = tx_dims.find(tx3->GetHash())->second; - const TxDimensions& tx4_dimensions = tx_dims.find(tx4->GetHash())->second; - const CFeeRate tx3_feerate = CFeeRate(tx3_dimensions.mod_fee + tx4_dimensions.mod_fee, tx3_dimensions.vsize + tx4_dimensions.vsize); - CAmount bumpfee3 = Find(bump_fees, COutPoint{tx3->GetHash(), 1}); - if (target_feerate <= tx3_feerate) { - // As long as target feerate is below tx4's ancestor feerate, there is no bump fee. - BOOST_CHECK_EQUAL(bumpfee3, 0); + const CFeeRate tx2_feerate = CFeeRate(tx2_dimensions.mod_fee + tx3_dimensions.mod_fee, tx2_dimensions.vsize + tx3_dimensions.vsize); + CAmount bumpfee2 = Find(bump_fees, COutPoint{tx2->GetHash(), 1}); + if (target_feerate <= tx2_feerate) { + // As long as target feerate is below tx3's ancestor feerate, there is no bump fee. + BOOST_CHECK_EQUAL(bumpfee2, 0); } else { - // Difference is fee to bump tx3 from current to target feerate, without tx4. - BOOST_CHECK_EQUAL(bumpfee3, target_feerate.GetFee(tx3_dimensions.vsize) - tx3_dimensions.mod_fee); + // Difference is fee to bump tx2 from current to target feerate, without tx3. + BOOST_CHECK_EQUAL(bumpfee2, target_feerate.GetFee(tx2_dimensions.vsize) - tx2_dimensions.mod_fee); } - // If tx6’s modified fees are sufficient for tx5 and tx6 to be picked + // If tx5’s modified fees are sufficient for tx4 and tx5 to be picked // into the block, our prospective new transaction would not need to - // bump tx5 when using tx5’s second output. If however even tx6’s + // bump tx4 when using tx4’s second output. If however even tx5’s // modified fee (which essentially indicates "effective feerate") is - // not sufficient to bump tx5, using the second output of tx5 would - // require our transaction to bump tx5 from scratch since we evaluate + // not sufficient to bump tx4, using the second output of tx4 would + // require our transaction to bump tx4 from scratch since we evaluate // transaction packages per ancestor sets and do not consider multiple // children’s fees. + const TxDimensions& tx4_dimensions = tx_dims.find(tx4->GetHash())->second; const TxDimensions& tx5_dimensions = tx_dims.find(tx5->GetHash())->second; - const TxDimensions& tx6_dimensions = tx_dims.find(tx6->GetHash())->second; - const CFeeRate tx5_feerate = CFeeRate(tx5_dimensions.mod_fee + tx6_dimensions.mod_fee, tx5_dimensions.vsize + tx6_dimensions.vsize); - CAmount bumpfee5 = Find(bump_fees, COutPoint{tx5->GetHash(), 1}); - if (target_feerate <= tx5_feerate) { - // As long as target feerate is below tx6's ancestor feerate, there is no bump fee. - BOOST_CHECK_EQUAL(bumpfee5, 0); + const CFeeRate tx4_feerate = CFeeRate(tx4_dimensions.mod_fee + tx5_dimensions.mod_fee, tx4_dimensions.vsize + tx5_dimensions.vsize); + CAmount bumpfee4 = Find(bump_fees, COutPoint{tx4->GetHash(), 1}); + if (target_feerate <= tx4_feerate) { + // As long as target feerate is below tx5's ancestor feerate, there is no bump fee. + BOOST_CHECK_EQUAL(bumpfee4, 0); } else { - // Difference is fee to bump tx5 from current to target feerate, without tx6. - BOOST_CHECK_EQUAL(bumpfee5, target_feerate.GetFee(tx5_dimensions.vsize) - tx5_dimensions.mod_fee); + // Difference is fee to bump tx4 from current to target feerate, without tx5. + BOOST_CHECK_EQUAL(bumpfee4, target_feerate.GetFee(tx4_dimensions.vsize) - tx4_dimensions.mod_fee); } } // Spent outpoints should usually not be requested as they would not be @@ -240,36 +240,36 @@ BOOST_FIXTURE_TEST_CASE(miniminer_1p1c, TestChain100Setup) // even though only one of them is in a to-be-replaced transaction. BOOST_CHECK(sanity_check(all_transactions, bump_fees)); - // Check tx1 bumpfee: no other bumper. - const TxDimensions& tx1_dimensions = tx_dims.find(tx1->GetHash())->second; - CAmount it1_spent = Find(bump_fees, COutPoint{tx1->GetHash(), 0}); - if (target_feerate <= tx1_dimensions.feerate) { - BOOST_CHECK_EQUAL(it1_spent, 0); + // Check tx0 bumpfee: no other bumper. + const TxDimensions& tx0_dimensions = tx_dims.find(tx0->GetHash())->second; + CAmount it0_spent = Find(bump_fees, COutPoint{tx0->GetHash(), 0}); + if (target_feerate <= tx0_dimensions.feerate) { + BOOST_CHECK_EQUAL(it0_spent, 0); } else { - // Difference is fee to bump tx1 from current to target feerate. - BOOST_CHECK_EQUAL(it1_spent, target_feerate.GetFee(tx1_dimensions.vsize) - tx1_dimensions.mod_fee); + // Difference is fee to bump tx0 from current to target feerate. + BOOST_CHECK_EQUAL(it0_spent, target_feerate.GetFee(tx0_dimensions.vsize) - tx0_dimensions.mod_fee); } - // Check tx3 bumpfee: no other bumper, because tx4 is to-be-replaced. - const TxDimensions& tx3_dimensions = tx_dims.find(tx3->GetHash())->second; - const CFeeRate tx3_feerate_unbumped = tx3_dimensions.feerate; - auto it3_spent = Find(bump_fees, COutPoint{tx3->GetHash(), 0}); - if (target_feerate <= tx3_feerate_unbumped) { - BOOST_CHECK_EQUAL(it3_spent, 0); + // Check tx2 bumpfee: no other bumper, because tx3 is to-be-replaced. + const TxDimensions& tx2_dimensions = tx_dims.find(tx2->GetHash())->second; + const CFeeRate tx2_feerate_unbumped = tx2_dimensions.feerate; + auto it2_spent = Find(bump_fees, COutPoint{tx2->GetHash(), 0}); + if (target_feerate <= tx2_feerate_unbumped) { + BOOST_CHECK_EQUAL(it2_spent, 0); } else { - // Difference is fee to bump tx3 from current to target feerate, without tx4. - BOOST_CHECK_EQUAL(it3_spent, target_feerate.GetFee(tx3_dimensions.vsize) - tx3_dimensions.mod_fee); + // Difference is fee to bump tx2 from current to target feerate, without tx3. + BOOST_CHECK_EQUAL(it2_spent, target_feerate.GetFee(tx2_dimensions.vsize) - tx2_dimensions.mod_fee); } - // Check tx5 bumpfee: no other bumper, because tx6 is to-be-replaced. - const TxDimensions& tx5_dimensions = tx_dims.find(tx5->GetHash())->second; - const CFeeRate tx5_feerate_unbumped = tx5_dimensions.feerate; - auto it5_spent = Find(bump_fees, COutPoint{tx5->GetHash(), 0}); - if (target_feerate <= tx5_feerate_unbumped) { - BOOST_CHECK_EQUAL(it5_spent, 0); + // Check tx4 bumpfee: no other bumper, because tx5 is to-be-replaced. + const TxDimensions& tx4_dimensions = tx_dims.find(tx4->GetHash())->second; + const CFeeRate tx4_feerate_unbumped = tx4_dimensions.feerate; + auto it4_spent = Find(bump_fees, COutPoint{tx4->GetHash(), 0}); + if (target_feerate <= tx4_feerate_unbumped) { + BOOST_CHECK_EQUAL(it4_spent, 0); } else { - // Difference is fee to bump tx5 from current to target feerate, without tx6. - BOOST_CHECK_EQUAL(it5_spent, target_feerate.GetFee(tx5_dimensions.vsize) - tx5_dimensions.mod_fee); + // Difference is fee to bump tx4 from current to target feerate, without tx5. + BOOST_CHECK_EQUAL(it4_spent, target_feerate.GetFee(tx4_dimensions.vsize) - tx4_dimensions.mod_fee); } } } @@ -277,145 +277,178 @@ BOOST_FIXTURE_TEST_CASE(miniminer_1p1c, TestChain100Setup) BOOST_FIXTURE_TEST_CASE(miniminer_overlap, TestChain100Setup) { +/* Tx graph for `miniminer_overlap` unit test: + * + * coinbase_tx [mined] ... block-chain + * ------------------------------------------------- + * / | \ \ ... mempool + * / | \ | + * tx0 tx1 tx2 tx4 + * [low] [med] [high] [high] + * \ | / | + * \ | / tx5 + * \ | / [low] + * tx3 / \ + * [high] tx6 tx7 + * [med] [high] + * + * NOTE: + * -> "low"/"med"/"high" denote the _absolute_ fee of each tx + * -> tx3 has 3 inputs and 3 outputs, all other txs have 1 input and 2 outputs + * -> tx3's feerate is lower than tx2's, as tx3 has more weight (due to having more inputs and outputs) + * + * -> tx2_FR = high / tx2_vsize + * -> tx3_FR = high / tx3_vsize + * -> tx3_ASFR = (low+med+high+high) / (tx0_vsize + tx1_vsize + tx2_vsize + tx3_vsize) + * -> tx4_FR = high / tx4_vsize + * -> tx6_ASFR = (high+low+med) / (tx4_vsize + tx5_vsize + tx6_vsize) + * -> tx7_ASFR = (high+low+high) / (tx4_vsize + tx5_vsize + tx7_vsize) */ + CTxMemPool& pool = *Assert(m_node.mempool); LOCK2(::cs_main, pool.cs); TestMemPoolEntryHelper entry; - const CAmount low_fee{CENT/2000}; - const CAmount med_fee{CENT/200}; - const CAmount high_fee{CENT/10}; - - // Create 3 parents of different feerates, and 1 child spending from all 3. - const auto tx1 = make_tx({COutPoint{m_coinbase_txns[0]->GetHash(), 0}}, /*num_outputs=*/2); - pool.addUnchecked(entry.Fee(low_fee).FromTx(tx1)); - const auto tx2 = make_tx({COutPoint{m_coinbase_txns[1]->GetHash(), 0}}, /*num_outputs=*/2); - pool.addUnchecked(entry.Fee(med_fee).FromTx(tx2)); - const auto tx3 = make_tx({COutPoint{m_coinbase_txns[2]->GetHash(), 0}}, /*num_outputs=*/2); + const CAmount low_fee{CENT/2000}; // 500 ṩ + const CAmount med_fee{CENT/200}; // 5000 ṩ + const CAmount high_fee{CENT/10}; // 100_000 ṩ + + // Create 3 parents of different feerates, and 1 child spending outputs from all 3 parents. + const auto tx0 = make_tx({COutPoint{m_coinbase_txns[0]->GetHash(), 0}}, /*num_outputs=*/2); + pool.addUnchecked(entry.Fee(low_fee).FromTx(tx0)); + const auto tx1 = make_tx({COutPoint{m_coinbase_txns[1]->GetHash(), 0}}, /*num_outputs=*/2); + pool.addUnchecked(entry.Fee(med_fee).FromTx(tx1)); + const auto tx2 = make_tx({COutPoint{m_coinbase_txns[2]->GetHash(), 0}}, /*num_outputs=*/2); + pool.addUnchecked(entry.Fee(high_fee).FromTx(tx2)); + const auto tx3 = make_tx({COutPoint{tx0->GetHash(), 0}, COutPoint{tx1->GetHash(), 0}, COutPoint{tx2->GetHash(), 0}}, /*num_outputs=*/3); pool.addUnchecked(entry.Fee(high_fee).FromTx(tx3)); - const auto tx4 = make_tx({COutPoint{tx1->GetHash(), 0}, COutPoint{tx2->GetHash(), 0}, COutPoint{tx3->GetHash(), 0}}, /*num_outputs=*/3); - pool.addUnchecked(entry.Fee(high_fee).FromTx(tx4)); // Create 1 grandparent and 1 parent, then 2 children. - const auto tx5 = make_tx({COutPoint{m_coinbase_txns[3]->GetHash(), 0}}, /*num_outputs=*/2); - pool.addUnchecked(entry.Fee(high_fee).FromTx(tx5)); - const auto tx6 = make_tx({COutPoint{tx5->GetHash(), 0}}, /*num_outputs=*/3); - pool.addUnchecked(entry.Fee(low_fee).FromTx(tx6)); - const auto tx7 = make_tx({COutPoint{tx6->GetHash(), 0}}, /*num_outputs=*/2); - pool.addUnchecked(entry.Fee(med_fee).FromTx(tx7)); - const auto tx8 = make_tx({COutPoint{tx6->GetHash(), 1}}, /*num_outputs=*/2); - pool.addUnchecked(entry.Fee(high_fee).FromTx(tx8)); - - std::vector<CTransactionRef> all_transactions{tx1, tx2, tx3, tx4, tx5, tx6, tx7, tx8}; + const auto tx4 = make_tx({COutPoint{m_coinbase_txns[3]->GetHash(), 0}}, /*num_outputs=*/2); + pool.addUnchecked(entry.Fee(high_fee).FromTx(tx4)); + const auto tx5 = make_tx({COutPoint{tx4->GetHash(), 0}}, /*num_outputs=*/3); + pool.addUnchecked(entry.Fee(low_fee).FromTx(tx5)); + const auto tx6 = make_tx({COutPoint{tx5->GetHash(), 0}}, /*num_outputs=*/2); + pool.addUnchecked(entry.Fee(med_fee).FromTx(tx6)); + const auto tx7 = make_tx({COutPoint{tx5->GetHash(), 1}}, /*num_outputs=*/2); + pool.addUnchecked(entry.Fee(high_fee).FromTx(tx7)); + + std::vector<CTransactionRef> all_transactions{tx0, tx1, tx2, tx3, tx4, tx5, tx6, tx7}; std::vector<int64_t> tx_vsizes; tx_vsizes.reserve(all_transactions.size()); for (const auto& tx : all_transactions) tx_vsizes.push_back(GetVirtualTransactionSize(*tx)); std::vector<COutPoint> all_unspent_outpoints({ + COutPoint{tx0->GetHash(), 1}, COutPoint{tx1->GetHash(), 1}, COutPoint{tx2->GetHash(), 1}, + COutPoint{tx3->GetHash(), 0}, COutPoint{tx3->GetHash(), 1}, - COutPoint{tx4->GetHash(), 0}, + COutPoint{tx3->GetHash(), 2}, COutPoint{tx4->GetHash(), 1}, - COutPoint{tx4->GetHash(), 2}, - COutPoint{tx5->GetHash(), 1}, - COutPoint{tx6->GetHash(), 2}, - COutPoint{tx7->GetHash(), 0}, - COutPoint{tx8->GetHash(), 0} + COutPoint{tx5->GetHash(), 2}, + COutPoint{tx6->GetHash(), 0}, + COutPoint{tx7->GetHash(), 0} }); for (const auto& outpoint : all_unspent_outpoints) BOOST_CHECK(!pool.isSpent(outpoint)); - const auto tx3_feerate = CFeeRate(high_fee, tx_vsizes[2]); - const auto tx4_feerate = CFeeRate(high_fee, tx_vsizes[3]); - // tx4's feerate is lower than tx3's. same fee, different weight. - BOOST_CHECK(tx3_feerate > tx4_feerate); - const auto tx4_anc_feerate = CFeeRate(low_fee + med_fee + high_fee, tx_vsizes[0] + tx_vsizes[1] + tx_vsizes[3]); - const auto tx5_feerate = CFeeRate(high_fee, tx_vsizes[4]); - const auto tx7_anc_feerate = CFeeRate(low_fee + med_fee, tx_vsizes[5] + tx_vsizes[6]); - const auto tx8_anc_feerate = CFeeRate(low_fee + high_fee, tx_vsizes[5] + tx_vsizes[7]); - BOOST_CHECK(tx5_feerate > tx7_anc_feerate); - BOOST_CHECK(tx5_feerate > tx8_anc_feerate); + const auto tx2_feerate = CFeeRate(high_fee, tx_vsizes[2]); + const auto tx3_feerate = CFeeRate(high_fee, tx_vsizes[3]); + // tx3's feerate is lower than tx2's. same fee, different weight. + BOOST_CHECK(tx2_feerate > tx3_feerate); + const auto tx3_anc_feerate = CFeeRate(low_fee + med_fee + high_fee + high_fee, tx_vsizes[0] + tx_vsizes[1] + tx_vsizes[2] + tx_vsizes[3]); + const auto tx3_iter = pool.GetIter(tx3->GetHash()); + BOOST_CHECK(tx3_anc_feerate == CFeeRate(tx3_iter.value()->GetModFeesWithAncestors(), tx3_iter.value()->GetSizeWithAncestors())); + const auto tx4_feerate = CFeeRate(high_fee, tx_vsizes[4]); + const auto tx6_anc_feerate = CFeeRate(high_fee + low_fee + med_fee, tx_vsizes[4] + tx_vsizes[5] + tx_vsizes[6]); + const auto tx6_iter = pool.GetIter(tx6->GetHash()); + BOOST_CHECK(tx6_anc_feerate == CFeeRate(tx6_iter.value()->GetModFeesWithAncestors(), tx6_iter.value()->GetSizeWithAncestors())); + const auto tx7_anc_feerate = CFeeRate(high_fee + low_fee + high_fee, tx_vsizes[4] + tx_vsizes[5] + tx_vsizes[7]); + const auto tx7_iter = pool.GetIter(tx7->GetHash()); + BOOST_CHECK(tx7_anc_feerate == CFeeRate(tx7_iter.value()->GetModFeesWithAncestors(), tx7_iter.value()->GetSizeWithAncestors())); + BOOST_CHECK(tx4_feerate > tx6_anc_feerate); + BOOST_CHECK(tx4_feerate > tx7_anc_feerate); // Extremely high feerate: everybody's bumpfee is from their full ancestor set. { node::MiniMiner mini_miner(pool, all_unspent_outpoints); const CFeeRate very_high_feerate(COIN); - BOOST_CHECK(tx4_anc_feerate < very_high_feerate); + BOOST_CHECK(tx3_anc_feerate < very_high_feerate); BOOST_CHECK(mini_miner.IsReadyToCalculate()); auto bump_fees = mini_miner.CalculateBumpFees(very_high_feerate); BOOST_CHECK_EQUAL(bump_fees.size(), all_unspent_outpoints.size()); BOOST_CHECK(!mini_miner.IsReadyToCalculate()); BOOST_CHECK(sanity_check(all_transactions, bump_fees)); - const auto tx1_bumpfee = bump_fees.find(COutPoint{tx1->GetHash(), 1}); - BOOST_CHECK(tx1_bumpfee != bump_fees.end()); - BOOST_CHECK_EQUAL(tx1_bumpfee->second, very_high_feerate.GetFee(tx_vsizes[0]) - low_fee); - const auto tx4_bumpfee = bump_fees.find(COutPoint{tx4->GetHash(), 0}); - BOOST_CHECK(tx4_bumpfee != bump_fees.end()); - BOOST_CHECK_EQUAL(tx4_bumpfee->second, + const auto tx0_bumpfee = bump_fees.find(COutPoint{tx0->GetHash(), 1}); + BOOST_CHECK(tx0_bumpfee != bump_fees.end()); + BOOST_CHECK_EQUAL(tx0_bumpfee->second, very_high_feerate.GetFee(tx_vsizes[0]) - low_fee); + const auto tx3_bumpfee = bump_fees.find(COutPoint{tx3->GetHash(), 0}); + BOOST_CHECK(tx3_bumpfee != bump_fees.end()); + BOOST_CHECK_EQUAL(tx3_bumpfee->second, very_high_feerate.GetFee(tx_vsizes[0] + tx_vsizes[1] + tx_vsizes[2] + tx_vsizes[3]) - (low_fee + med_fee + high_fee + high_fee)); + const auto tx6_bumpfee = bump_fees.find(COutPoint{tx6->GetHash(), 0}); + BOOST_CHECK(tx6_bumpfee != bump_fees.end()); + BOOST_CHECK_EQUAL(tx6_bumpfee->second, + very_high_feerate.GetFee(tx_vsizes[4] + tx_vsizes[5] + tx_vsizes[6]) - (high_fee + low_fee + med_fee)); const auto tx7_bumpfee = bump_fees.find(COutPoint{tx7->GetHash(), 0}); BOOST_CHECK(tx7_bumpfee != bump_fees.end()); BOOST_CHECK_EQUAL(tx7_bumpfee->second, - very_high_feerate.GetFee(tx_vsizes[4] + tx_vsizes[5] + tx_vsizes[6]) - (high_fee + low_fee + med_fee)); - const auto tx8_bumpfee = bump_fees.find(COutPoint{tx8->GetHash(), 0}); - BOOST_CHECK(tx8_bumpfee != bump_fees.end()); - BOOST_CHECK_EQUAL(tx8_bumpfee->second, very_high_feerate.GetFee(tx_vsizes[4] + tx_vsizes[5] + tx_vsizes[7]) - (high_fee + low_fee + high_fee)); - // Total fees: if spending multiple outputs from tx4 don't double-count fees. - node::MiniMiner mini_miner_total_tx4(pool, {COutPoint{tx4->GetHash(), 0}, COutPoint{tx4->GetHash(), 1}}); - BOOST_CHECK(mini_miner_total_tx4.IsReadyToCalculate()); - const auto tx4_bump_fee = mini_miner_total_tx4.CalculateTotalBumpFees(very_high_feerate); - BOOST_CHECK(!mini_miner_total_tx4.IsReadyToCalculate()); - BOOST_CHECK(tx4_bump_fee.has_value()); - BOOST_CHECK_EQUAL(tx4_bump_fee.value(), + // Total fees: if spending multiple outputs from tx3 don't double-count fees. + node::MiniMiner mini_miner_total_tx3(pool, {COutPoint{tx3->GetHash(), 0}, COutPoint{tx3->GetHash(), 1}}); + BOOST_CHECK(mini_miner_total_tx3.IsReadyToCalculate()); + const auto tx3_bump_fee = mini_miner_total_tx3.CalculateTotalBumpFees(very_high_feerate); + BOOST_CHECK(!mini_miner_total_tx3.IsReadyToCalculate()); + BOOST_CHECK(tx3_bump_fee.has_value()); + BOOST_CHECK_EQUAL(tx3_bump_fee.value(), very_high_feerate.GetFee(tx_vsizes[0] + tx_vsizes[1] + tx_vsizes[2] + tx_vsizes[3]) - (low_fee + med_fee + high_fee + high_fee)); - // Total fees: if spending both tx7 and tx8, don't double-count fees. - node::MiniMiner mini_miner_tx7_tx8(pool, {COutPoint{tx7->GetHash(), 0}, COutPoint{tx8->GetHash(), 0}}); - BOOST_CHECK(mini_miner_tx7_tx8.IsReadyToCalculate()); - const auto tx7_tx8_bumpfee = mini_miner_tx7_tx8.CalculateTotalBumpFees(very_high_feerate); - BOOST_CHECK(!mini_miner_tx7_tx8.IsReadyToCalculate()); - BOOST_CHECK(tx7_tx8_bumpfee.has_value()); - BOOST_CHECK_EQUAL(tx7_tx8_bumpfee.value(), + // Total fees: if spending both tx6 and tx7, don't double-count fees. + node::MiniMiner mini_miner_tx6_tx7(pool, {COutPoint{tx6->GetHash(), 0}, COutPoint{tx7->GetHash(), 0}}); + BOOST_CHECK(mini_miner_tx6_tx7.IsReadyToCalculate()); + const auto tx6_tx7_bumpfee = mini_miner_tx6_tx7.CalculateTotalBumpFees(very_high_feerate); + BOOST_CHECK(!mini_miner_tx6_tx7.IsReadyToCalculate()); + BOOST_CHECK(tx6_tx7_bumpfee.has_value()); + BOOST_CHECK_EQUAL(tx6_tx7_bumpfee.value(), very_high_feerate.GetFee(tx_vsizes[4] + tx_vsizes[5] + tx_vsizes[6] + tx_vsizes[7]) - (high_fee + low_fee + med_fee + high_fee)); } - // Feerate just below tx5: tx7 and tx8 have different bump fees. + // Feerate just below tx4: tx6 and tx7 have different bump fees. { - const auto just_below_tx5 = CFeeRate(tx5_feerate.GetFeePerK() - 5); + const auto just_below_tx4 = CFeeRate(tx4_feerate.GetFeePerK() - 5); node::MiniMiner mini_miner(pool, all_unspent_outpoints); BOOST_CHECK(mini_miner.IsReadyToCalculate()); - auto bump_fees = mini_miner.CalculateBumpFees(just_below_tx5); + auto bump_fees = mini_miner.CalculateBumpFees(just_below_tx4); BOOST_CHECK(!mini_miner.IsReadyToCalculate()); BOOST_CHECK_EQUAL(bump_fees.size(), all_unspent_outpoints.size()); BOOST_CHECK(sanity_check(all_transactions, bump_fees)); + const auto tx6_bumpfee = bump_fees.find(COutPoint{tx6->GetHash(), 0}); + BOOST_CHECK(tx6_bumpfee != bump_fees.end()); + BOOST_CHECK_EQUAL(tx6_bumpfee->second, just_below_tx4.GetFee(tx_vsizes[5] + tx_vsizes[6]) - (low_fee + med_fee)); const auto tx7_bumpfee = bump_fees.find(COutPoint{tx7->GetHash(), 0}); BOOST_CHECK(tx7_bumpfee != bump_fees.end()); - BOOST_CHECK_EQUAL(tx7_bumpfee->second, just_below_tx5.GetFee(tx_vsizes[5] + tx_vsizes[6]) - (low_fee + med_fee)); - const auto tx8_bumpfee = bump_fees.find(COutPoint{tx8->GetHash(), 0}); - BOOST_CHECK(tx8_bumpfee != bump_fees.end()); - BOOST_CHECK_EQUAL(tx8_bumpfee->second, just_below_tx5.GetFee(tx_vsizes[5] + tx_vsizes[7]) - (low_fee + high_fee)); - // Total fees: if spending both tx7 and tx8, don't double-count fees. - node::MiniMiner mini_miner_tx7_tx8(pool, {COutPoint{tx7->GetHash(), 0}, COutPoint{tx8->GetHash(), 0}}); - BOOST_CHECK(mini_miner_tx7_tx8.IsReadyToCalculate()); - const auto tx7_tx8_bumpfee = mini_miner_tx7_tx8.CalculateTotalBumpFees(just_below_tx5); - BOOST_CHECK(!mini_miner_tx7_tx8.IsReadyToCalculate()); - BOOST_CHECK(tx7_tx8_bumpfee.has_value()); - BOOST_CHECK_EQUAL(tx7_tx8_bumpfee.value(), just_below_tx5.GetFee(tx_vsizes[5] + tx_vsizes[6]) - (low_fee + med_fee)); + BOOST_CHECK_EQUAL(tx7_bumpfee->second, just_below_tx4.GetFee(tx_vsizes[5] + tx_vsizes[7]) - (low_fee + high_fee)); + // Total fees: if spending both tx6 and tx7, don't double-count fees. + node::MiniMiner mini_miner_tx6_tx7(pool, {COutPoint{tx6->GetHash(), 0}, COutPoint{tx7->GetHash(), 0}}); + BOOST_CHECK(mini_miner_tx6_tx7.IsReadyToCalculate()); + const auto tx6_tx7_bumpfee = mini_miner_tx6_tx7.CalculateTotalBumpFees(just_below_tx4); + BOOST_CHECK(!mini_miner_tx6_tx7.IsReadyToCalculate()); + BOOST_CHECK(tx6_tx7_bumpfee.has_value()); + BOOST_CHECK_EQUAL(tx6_tx7_bumpfee.value(), just_below_tx4.GetFee(tx_vsizes[5] + tx_vsizes[6]) - (low_fee + med_fee)); } - // Feerate between tx7 and tx8's ancestor feerates: don't need to bump tx6 because tx8 already does. + // Feerate between tx6 and tx7's ancestor feerates: don't need to bump tx5 because tx7 already does. { - const auto just_above_tx7 = CFeeRate(med_fee + 10, tx_vsizes[6]); - BOOST_CHECK(just_above_tx7 <= CFeeRate(low_fee + high_fee, tx_vsizes[5] + tx_vsizes[7])); + const auto just_above_tx6 = CFeeRate(med_fee + 10, tx_vsizes[6]); + BOOST_CHECK(just_above_tx6 <= CFeeRate(low_fee + high_fee, tx_vsizes[5] + tx_vsizes[7])); node::MiniMiner mini_miner(pool, all_unspent_outpoints); BOOST_CHECK(mini_miner.IsReadyToCalculate()); - auto bump_fees = mini_miner.CalculateBumpFees(just_above_tx7); + auto bump_fees = mini_miner.CalculateBumpFees(just_above_tx6); BOOST_CHECK(!mini_miner.IsReadyToCalculate()); BOOST_CHECK_EQUAL(bump_fees.size(), all_unspent_outpoints.size()); BOOST_CHECK(sanity_check(all_transactions, bump_fees)); + const auto tx6_bumpfee = bump_fees.find(COutPoint{tx6->GetHash(), 0}); + BOOST_CHECK(tx6_bumpfee != bump_fees.end()); + BOOST_CHECK_EQUAL(tx6_bumpfee->second, just_above_tx6.GetFee(tx_vsizes[6]) - (med_fee)); const auto tx7_bumpfee = bump_fees.find(COutPoint{tx7->GetHash(), 0}); BOOST_CHECK(tx7_bumpfee != bump_fees.end()); - BOOST_CHECK_EQUAL(tx7_bumpfee->second, just_above_tx7.GetFee(tx_vsizes[6]) - (med_fee)); - const auto tx8_bumpfee = bump_fees.find(COutPoint{tx8->GetHash(), 0}); - BOOST_CHECK(tx8_bumpfee != bump_fees.end()); - BOOST_CHECK_EQUAL(tx8_bumpfee->second, 0); + BOOST_CHECK_EQUAL(tx7_bumpfee->second, 0); } } BOOST_FIXTURE_TEST_CASE(calculate_cluster, TestChain100Setup) @@ -445,12 +478,12 @@ BOOST_FIXTURE_TEST_CASE(calculate_cluster, TestChain100Setup) const auto cluster_501 = pool.GatherClusters({tx_501->GetHash()}); BOOST_CHECK_EQUAL(cluster_501.size(), 0); - // Zig Zag cluster: - // txp0 txp1 txp2 ... txp48 txp49 - // \ / \ / \ \ / - // txc0 txc1 txc2 ... txc48 - // Note that each transaction's ancestor size is 1 or 3, and each descendant size is 1, 2 or 3. - // However, all of these transactions are in the same cluster. + /* Zig Zag cluster: + * txp0 txp1 txp2 ... txp48 txp49 + * \ / \ / \ \ / + * txc0 txc1 txc2 ... txc48 + * Note that each transaction's ancestor size is 1 or 3, and each descendant size is 1, 2 or 3. + * However, all of these transactions are in the same cluster. */ std::vector<uint256> zigzag_txids; for (auto p{0}; p < 50; ++p) { const auto txp = make_tx({COutPoint{GetRandHash(), 0}}, /*num_outputs=*/2); diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp index d6b9b68e1f..391e120932 100644 --- a/src/wallet/coinselection.cpp +++ b/src/wallet/coinselection.cpp @@ -7,6 +7,7 @@ #include <common/system.h> #include <consensus/amount.h> #include <consensus/consensus.h> +#include <interfaces/chain.h> #include <logging.h> #include <policy/feerate.h> #include <util/check.h> @@ -449,19 +450,19 @@ void OutputGroupTypeMap::Push(const OutputGroup& group, OutputType type, bool in } } -CAmount GetSelectionWaste(const std::set<std::shared_ptr<COutput>>& inputs, CAmount change_cost, CAmount target, bool use_effective_value) +CAmount SelectionResult::GetSelectionWaste(CAmount change_cost, CAmount target, bool use_effective_value) { // This function should not be called with empty inputs as that would mean the selection failed - assert(!inputs.empty()); + assert(!m_selected_inputs.empty()); // Always consider the cost of spending an input now vs in the future. CAmount waste = 0; - CAmount selected_effective_value = 0; - for (const auto& coin_ptr : inputs) { + for (const auto& coin_ptr : m_selected_inputs) { const COutput& coin = *coin_ptr; waste += coin.GetFee() - coin.long_term_fee; - selected_effective_value += use_effective_value ? coin.GetEffectiveValue() : coin.txout.nValue; } + // Bump fee of whole selection may diverge from sum of individual bump fees + waste -= bump_fee_group_discount; if (change_cost) { // Consider the cost of making change and spending it in the future @@ -470,6 +471,7 @@ CAmount GetSelectionWaste(const std::set<std::shared_ptr<COutput>>& inputs, CAmo waste += change_cost; } else { // When we are not making change (change_cost == 0), consider the excess we are throwing away to fees + CAmount selected_effective_value = use_effective_value ? GetSelectedEffectiveValue() : GetSelectedValue(); assert(selected_effective_value >= target); waste += selected_effective_value - target; } @@ -488,14 +490,22 @@ CAmount GenerateChangeTarget(const CAmount payment_value, const CAmount change_f } } +void SelectionResult::SetBumpFeeDiscount(const CAmount discount) +{ + // Overlapping ancestry can only lower the fees, not increase them + assert (discount >= 0); + bump_fee_group_discount = discount; +} + + void SelectionResult::ComputeAndSetWaste(const CAmount min_viable_change, const CAmount change_cost, const CAmount change_fee) { const CAmount change = GetChange(min_viable_change, change_fee); if (change > 0) { - m_waste = GetSelectionWaste(m_selected_inputs, change_cost, m_target, m_use_effective); + m_waste = GetSelectionWaste(change_cost, m_target, m_use_effective); } else { - m_waste = GetSelectionWaste(m_selected_inputs, 0, m_target, m_use_effective); + m_waste = GetSelectionWaste(0, m_target, m_use_effective); } } @@ -511,7 +521,12 @@ CAmount SelectionResult::GetSelectedValue() const CAmount SelectionResult::GetSelectedEffectiveValue() const { - return std::accumulate(m_selected_inputs.cbegin(), m_selected_inputs.cend(), CAmount{0}, [](CAmount sum, const auto& coin) { return sum + coin->GetEffectiveValue(); }); + return std::accumulate(m_selected_inputs.cbegin(), m_selected_inputs.cend(), CAmount{0}, [](CAmount sum, const auto& coin) { return sum + coin->GetEffectiveValue(); }) + bump_fee_group_discount; +} + +CAmount SelectionResult::GetTotalBumpFees() const +{ + return std::accumulate(m_selected_inputs.cbegin(), m_selected_inputs.cend(), CAmount{0}, [](CAmount sum, const auto& coin) { return sum + coin->ancestor_bump_fees; }) - bump_fee_group_discount; } void SelectionResult::Clear() diff --git a/src/wallet/coinselection.h b/src/wallet/coinselection.h index afd868fc89..20b2461c04 100644 --- a/src/wallet/coinselection.h +++ b/src/wallet/coinselection.h @@ -17,6 +17,7 @@ #include <optional> + namespace wallet { //! lower bound for randomly-chosen target change amount static constexpr CAmount CHANGE_LOWER{50000}; @@ -26,10 +27,10 @@ static constexpr CAmount CHANGE_UPPER{1000000}; /** A UTXO under consideration for use in funding a new transaction. */ struct COutput { private: - /** The output's value minus fees required to spend it.*/ + /** The output's value minus fees required to spend it and bump its unconfirmed ancestors to the target feerate. */ std::optional<CAmount> effective_value; - /** The fee required to spend this output at the transaction's target feerate. */ + /** The fee required to spend this output at the transaction's target feerate and to bump its unconfirmed ancestors to the target feerate. */ std::optional<CAmount> fee; public: @@ -71,6 +72,9 @@ public: /** The fee required to spend this output at the consolidation feerate. */ CAmount long_term_fee{0}; + /** The fee necessary to bump this UTXO's ancestor transactions to the target feerate */ + CAmount ancestor_bump_fees{0}; + COutput(const COutPoint& outpoint, const CTxOut& txout, int depth, int input_bytes, bool spendable, bool solvable, bool safe, int64_t time, bool from_me, const std::optional<CFeeRate> feerate = std::nullopt) : outpoint{outpoint}, txout{txout}, @@ -83,6 +87,7 @@ public: from_me{from_me} { if (feerate) { + // base fee without considering potential unconfirmed ancestors fee = input_bytes < 0 ? 0 : feerate.value().GetFee(input_bytes); effective_value = txout.nValue - fee.value(); } @@ -104,6 +109,16 @@ public: return outpoint < rhs.outpoint; } + void ApplyBumpFee(CAmount bump_fee) + { + assert(bump_fee >= 0); + ancestor_bump_fees = bump_fee; + assert(fee); + *fee += bump_fee; + // Note: assert(effective_value - bump_fee == nValue - fee.value()); + effective_value = txout.nValue - fee.value(); + } + CAmount GetFee() const { assert(fee.has_value()); @@ -275,26 +290,6 @@ struct OutputGroupTypeMap typedef std::map<CoinEligibilityFilter, OutputGroupTypeMap> FilteredOutputGroups; -/** Compute the waste for this result given the cost of change - * and the opportunity cost of spending these inputs now vs in the future. - * If change exists, waste = change_cost + inputs * (effective_feerate - long_term_feerate) - * If no change, waste = excess + inputs * (effective_feerate - long_term_feerate) - * where excess = selected_effective_value - target - * change_cost = effective_feerate * change_output_size + long_term_feerate * change_spend_size - * - * Note this function is separate from SelectionResult for the tests. - * - * @param[in] inputs The selected inputs - * @param[in] change_cost The cost of creating change and spending it in the future. - * Only used if there is change, in which case it must be positive. - * Must be 0 if there is no change. - * @param[in] target The amount targeted by the coin selection algorithm. - * @param[in] use_effective_value Whether to use the input's effective value (when true) or the real value (when false). - * @return The waste - */ -[[nodiscard]] CAmount GetSelectionWaste(const std::set<std::shared_ptr<COutput>>& inputs, CAmount change_cost, CAmount target, bool use_effective_value = true); - - /** Choose a random change target for each transaction to make it harder to fingerprint the Core * wallet based on the change output values of transactions it creates. * Change target covers at least change fees and adds a random value on top of it. @@ -336,6 +331,8 @@ private: std::optional<CAmount> m_waste; /** Total weight of the selected inputs */ int m_weight{0}; + /** How much individual inputs overestimated the bump fees for the shared ancestry */ + CAmount bump_fee_group_discount{0}; template<typename T> void InsertInputs(const T& inputs) @@ -348,6 +345,22 @@ private: } } + /** Compute the waste for this result given the cost of change + * and the opportunity cost of spending these inputs now vs in the future. + * If change exists, waste = change_cost + inputs * (effective_feerate - long_term_feerate) + * If no change, waste = excess + inputs * (effective_feerate - long_term_feerate) + * where excess = selected_effective_value - target + * change_cost = effective_feerate * change_output_size + long_term_feerate * change_spend_size + * + * @param[in] change_cost The cost of creating change and spending it in the future. + * Only used if there is change, in which case it must be positive. + * Must be 0 if there is no change. + * @param[in] target The amount targeted by the coin selection algorithm. + * @param[in] use_effective_value Whether to use the input's effective value (when true) or the real value (when false). + * @return The waste + */ + [[nodiscard]] CAmount GetSelectionWaste(CAmount change_cost, CAmount target, bool use_effective_value = true); + public: explicit SelectionResult(const CAmount target, SelectionAlgorithm algo) : m_target(target), m_algo(algo) {} @@ -359,11 +372,16 @@ public: [[nodiscard]] CAmount GetSelectedEffectiveValue() const; + [[nodiscard]] CAmount GetTotalBumpFees() const; + void Clear(); void AddInput(const OutputGroup& group); void AddInputs(const std::set<std::shared_ptr<COutput>>& inputs, bool subtract_fee_outputs); + /** How much individual inputs overestimated the bump fees for shared ancestries */ + void SetBumpFeeDiscount(const CAmount discount); + /** Calculates and stores the waste for this selection via GetSelectionWaste */ void ComputeAndSetWaste(const CAmount min_viable_change, const CAmount change_cost, const CAmount change_fee); [[nodiscard]] CAmount GetWaste() const; diff --git a/src/wallet/feebumper.cpp b/src/wallet/feebumper.cpp index 3720d144eb..f99da926bc 100644 --- a/src/wallet/feebumper.cpp +++ b/src/wallet/feebumper.cpp @@ -63,7 +63,7 @@ static feebumper::Result PreconditionChecks(const CWallet& wallet, const CWallet } //! Check if the user provided a valid feeRate -static feebumper::Result CheckFeeRate(const CWallet& wallet, const CFeeRate& newFeerate, const int64_t maxTxSize, CAmount old_fee, std::vector<bilingual_str>& errors) +static feebumper::Result CheckFeeRate(const CWallet& wallet, const CMutableTransaction& mtx, const CFeeRate& newFeerate, const int64_t maxTxSize, CAmount old_fee, std::vector<bilingual_str>& errors) { // check that fee rate is higher than mempool's minimum fee // (no point in bumping fee if we know that the new tx won't be accepted to the mempool) @@ -80,7 +80,17 @@ static feebumper::Result CheckFeeRate(const CWallet& wallet, const CFeeRate& new return feebumper::Result::WALLET_ERROR; } - CAmount new_total_fee = newFeerate.GetFee(maxTxSize); + std::vector<COutPoint> reused_inputs; + reused_inputs.reserve(mtx.vin.size()); + for (const CTxIn& txin : mtx.vin) { + reused_inputs.push_back(txin.prevout); + } + + std::optional<CAmount> combined_bump_fee = wallet.chain().CalculateCombinedBumpFee(reused_inputs, newFeerate); + if (!combined_bump_fee.has_value()) { + errors.push_back(strprintf(Untranslated("Failed to calculate bump fees, because unconfirmed UTXOs depend on enormous cluster of unconfirmed transactions."))); + } + CAmount new_total_fee = newFeerate.GetFee(maxTxSize) + combined_bump_fee.value(); CFeeRate incrementalRelayFee = std::max(wallet.chain().relayIncrementalFee(), CFeeRate(WALLET_INCREMENTAL_RELAY_FEE)); @@ -283,7 +293,7 @@ Result CreateRateBumpTransaction(CWallet& wallet, const uint256& txid, const CCo } temp_mtx.vout = txouts; const int64_t maxTxSize{CalculateMaximumSignedTxSize(CTransaction(temp_mtx), &wallet, &new_coin_control).vsize}; - Result res = CheckFeeRate(wallet, *new_coin_control.m_feerate, maxTxSize, old_fee, errors); + Result res = CheckFeeRate(wallet, temp_mtx, *new_coin_control.m_feerate, maxTxSize, old_fee, errors); if (res != Result::OK) { return res; } diff --git a/src/wallet/spend.cpp b/src/wallet/spend.cpp index fd7f279505..96c9a3dc16 100644 --- a/src/wallet/spend.cpp +++ b/src/wallet/spend.cpp @@ -259,6 +259,7 @@ util::Result<PreSelectedInputs> FetchSelectedInputs(const CWallet& wallet, const { PreSelectedInputs result; const bool can_grind_r = wallet.CanGrindR(); + std::map<COutPoint, CAmount> map_of_bump_fees = wallet.chain().CalculateIndividualBumpFees(coin_control.ListSelected(), coin_selection_params.m_effective_feerate); for (const COutPoint& outpoint : coin_control.ListSelected()) { int input_bytes = -1; CTxOut txout; @@ -294,6 +295,7 @@ util::Result<PreSelectedInputs> FetchSelectedInputs(const CWallet& wallet, const /* Set some defaults for depth, spendable, solvable, safe, time, and from_me as these don't matter for preset inputs since no selection is being done. */ COutput output(outpoint, txout, /*depth=*/ 0, input_bytes, /*spendable=*/ true, /*solvable=*/ true, /*safe=*/ true, /*time=*/ 0, /*from_me=*/ false, coin_selection_params.m_effective_feerate); + output.ApplyBumpFee(map_of_bump_fees.at(output.outpoint)); result.Insert(output, coin_selection_params.m_subtract_fee_outputs); } return result; @@ -314,6 +316,7 @@ CoinsResult AvailableCoins(const CWallet& wallet, const int max_depth = {coinControl ? coinControl->m_max_depth : DEFAULT_MAX_DEPTH}; const bool only_safe = {coinControl ? !coinControl->m_include_unsafe_inputs : true}; const bool can_grind_r = wallet.CanGrindR(); + std::vector<COutPoint> outpoints; std::set<uint256> trusted_parents; for (const auto& entry : wallet.mapWallet) @@ -433,6 +436,8 @@ CoinsResult AvailableCoins(const CWallet& wallet, result.Add(GetOutputType(type, is_from_p2sh), COutput(outpoint, output, nDepth, input_bytes, spendable, solvable, safeTx, wtx.GetTxTime(), tx_from_me, feerate)); + outpoints.push_back(outpoint); + // Checks the sum amount of all UTXO's. if (params.min_sum_amount != MAX_MONEY) { if (result.GetTotalAmount() >= params.min_sum_amount) { @@ -447,6 +452,16 @@ CoinsResult AvailableCoins(const CWallet& wallet, } } + if (feerate.has_value()) { + std::map<COutPoint, CAmount> map_of_bump_fees = wallet.chain().CalculateIndividualBumpFees(outpoints, feerate.value()); + + for (auto& [_, outputs] : result.coins) { + for (auto& output : outputs) { + output.ApplyBumpFee(map_of_bump_fees.at(output.outpoint)); + } + } + } + return result; } @@ -628,13 +643,13 @@ FilteredOutputGroups GroupOutputs(const CWallet& wallet, // Returns true if the result contains an error and the message is not empty static bool HasErrorMsg(const util::Result<SelectionResult>& res) { return !util::ErrorString(res).empty(); } -util::Result<SelectionResult> AttemptSelection(const CAmount& nTargetValue, OutputGroupTypeMap& groups, +util::Result<SelectionResult> AttemptSelection(interfaces::Chain& chain, const CAmount& nTargetValue, OutputGroupTypeMap& groups, const CoinSelectionParams& coin_selection_params, bool allow_mixed_output_types) { // Run coin selection on each OutputType and compute the Waste Metric std::vector<SelectionResult> results; for (auto& [type, group] : groups.groups_by_type) { - auto result{ChooseSelectionResult(nTargetValue, group, coin_selection_params)}; + auto result{ChooseSelectionResult(chain, nTargetValue, group, coin_selection_params)}; // If any specific error message appears here, then something particularly wrong happened. if (HasErrorMsg(result)) return result; // So let's return the specific error. // Append the favorable result. @@ -648,14 +663,14 @@ util::Result<SelectionResult> AttemptSelection(const CAmount& nTargetValue, Outp // over all available coins, which would allow mixing. // If TypesCount() <= 1, there is nothing to mix. if (allow_mixed_output_types && groups.TypesCount() > 1) { - return ChooseSelectionResult(nTargetValue, groups.all_groups, coin_selection_params); + return ChooseSelectionResult(chain, nTargetValue, groups.all_groups, coin_selection_params); } // Either mixing is not allowed and we couldn't find a solution from any single OutputType, or mixing was allowed and we still couldn't // find a solution using all available coins return util::Error(); }; -util::Result<SelectionResult> ChooseSelectionResult(const CAmount& nTargetValue, Groups& groups, const CoinSelectionParams& coin_selection_params) +util::Result<SelectionResult> ChooseSelectionResult(interfaces::Chain& chain, const CAmount& nTargetValue, Groups& groups, const CoinSelectionParams& coin_selection_params) { // Vector of results. We will choose the best one based on waste. std::vector<SelectionResult> results; @@ -680,12 +695,10 @@ util::Result<SelectionResult> ChooseSelectionResult(const CAmount& nTargetValue, // The knapsack solver has some legacy behavior where it will spend dust outputs. We retain this behavior, so don't filter for positive only here. if (auto knapsack_result{KnapsackSolver(groups.mixed_group, nTargetValue, coin_selection_params.m_min_change_target, coin_selection_params.rng_fast, max_inputs_weight)}) { - knapsack_result->ComputeAndSetWaste(coin_selection_params.min_viable_change, coin_selection_params.m_cost_of_change, coin_selection_params.m_change_fee); results.push_back(*knapsack_result); } else append_error(knapsack_result); if (auto srd_result{SelectCoinsSRD(groups.positive_group, nTargetValue, coin_selection_params.m_change_fee, coin_selection_params.rng_fast, max_inputs_weight)}) { - srd_result->ComputeAndSetWaste(coin_selection_params.min_viable_change, coin_selection_params.m_cost_of_change, coin_selection_params.m_change_fee); results.push_back(*srd_result); } else append_error(srd_result); @@ -695,6 +708,27 @@ util::Result<SelectionResult> ChooseSelectionResult(const CAmount& nTargetValue, return errors.empty() ? util::Error() : errors.front(); } + // If the chosen input set has unconfirmed inputs, check for synergies from overlapping ancestry + for (auto& result : results) { + std::vector<COutPoint> outpoints; + std::set<std::shared_ptr<COutput>> coins = result.GetInputSet(); + CAmount summed_bump_fees = 0; + for (auto& coin : coins) { + if (coin->depth > 0) continue; // Bump fees only exist for unconfirmed inputs + outpoints.push_back(coin->outpoint); + summed_bump_fees += coin->ancestor_bump_fees; + } + std::optional<CAmount> combined_bump_fee = chain.CalculateCombinedBumpFee(outpoints, coin_selection_params.m_effective_feerate); + if (!combined_bump_fee.has_value()) { + return util::Error{_("Failed to calculate bump fees, because unconfirmed UTXOs depend on enormous cluster of unconfirmed transactions.")}; + } + CAmount bump_fee_overestimate = summed_bump_fees - combined_bump_fee.value(); + if (bump_fee_overestimate) { + result.SetBumpFeeDiscount(bump_fee_overestimate); + } + result.ComputeAndSetWaste(coin_selection_params.min_viable_change, coin_selection_params.m_cost_of_change, coin_selection_params.m_change_fee); + } + // Choose the result with the least waste // If the waste is the same, choose the one which spends more inputs. return *std::min_element(results.begin(), results.end()); @@ -824,7 +858,7 @@ util::Result<SelectionResult> AutomaticCoinSelection(const CWallet& wallet, Coin for (const auto& select_filter : ordered_filters) { auto it = filtered_groups.find(select_filter.filter); if (it == filtered_groups.end()) continue; - if (auto res{AttemptSelection(value_to_select, it->second, + if (auto res{AttemptSelection(wallet.chain(), value_to_select, it->second, coin_selection_params, select_filter.allow_mixed_output_types)}) { return res; // result found } else { @@ -1120,7 +1154,7 @@ static util::Result<CreatedTransactionResult> CreateTransactionInternal( if (nBytes == -1) { return util::Error{_("Missing solving data for estimating transaction size")}; } - CAmount fee_needed = coin_selection_params.m_effective_feerate.GetFee(nBytes); + CAmount fee_needed = coin_selection_params.m_effective_feerate.GetFee(nBytes) + result.GetTotalBumpFees(); const CAmount output_value = CalculateOutputValue(txNew); Assume(recipients_sum + change_amount == output_value); CAmount current_fee = result.GetSelectedValue() - output_value; diff --git a/src/wallet/spend.h b/src/wallet/spend.h index cc9ccf3011..407627b5f1 100644 --- a/src/wallet/spend.h +++ b/src/wallet/spend.h @@ -123,6 +123,7 @@ FilteredOutputGroups GroupOutputs(const CWallet& wallet, * the solution (according to the waste metric) will be chosen. If a valid input cannot be found from any * single OutputType, fallback to running `ChooseSelectionResult()` over all available coins. * + * param@[in] chain The chain interface to get information on unconfirmed UTXOs bump fees * param@[in] nTargetValue The target value * param@[in] groups The grouped outputs mapped by coin eligibility filters * param@[in] coin_selection_params Parameters for the coin selection @@ -132,7 +133,7 @@ FilteredOutputGroups GroupOutputs(const CWallet& wallet, * or (2) an specific error message if there was something particularly wrong (e.g. a selection * result that surpassed the tx max weight size). */ -util::Result<SelectionResult> AttemptSelection(const CAmount& nTargetValue, OutputGroupTypeMap& groups, +util::Result<SelectionResult> AttemptSelection(interfaces::Chain& chain, const CAmount& nTargetValue, OutputGroupTypeMap& groups, const CoinSelectionParams& coin_selection_params, bool allow_mixed_output_types); /** @@ -140,6 +141,7 @@ util::Result<SelectionResult> AttemptSelection(const CAmount& nTargetValue, Outp * Multiple coin selection algorithms will be run and the input set that produces the least waste * (according to the waste metric) will be chosen. * + * param@[in] chain The chain interface to get information on unconfirmed UTXOs bump fees * param@[in] nTargetValue The target value * param@[in] groups The struct containing the outputs grouped by script and divided by (1) positive only outputs and (2) all outputs (positive + negative). * param@[in] coin_selection_params Parameters for the coin selection @@ -148,7 +150,7 @@ util::Result<SelectionResult> AttemptSelection(const CAmount& nTargetValue, Outp * or (2) an specific error message if there was something particularly wrong (e.g. a selection * result that surpassed the tx max weight size). */ -util::Result<SelectionResult> ChooseSelectionResult(const CAmount& nTargetValue, Groups& groups, const CoinSelectionParams& coin_selection_params); +util::Result<SelectionResult> ChooseSelectionResult(interfaces::Chain& chain, const CAmount& nTargetValue, Groups& groups, const CoinSelectionParams& coin_selection_params); // User manually selected inputs that must be part of the transaction struct PreSelectedInputs diff --git a/src/wallet/test/coinselector_tests.cpp b/src/wallet/test/coinselector_tests.cpp index c8283f453a..9569210ba0 100644 --- a/src/wallet/test/coinselector_tests.cpp +++ b/src/wallet/test/coinselector_tests.cpp @@ -58,15 +58,17 @@ static void add_coin(const CAmount& nValue, int nInput, SelectionResult& result) result.AddInput(group); } -static void add_coin(const CAmount& nValue, int nInput, CoinSet& set, CAmount fee = 0, CAmount long_term_fee = 0) +static void add_coin(const CAmount& nValue, int nInput, SelectionResult& result, CAmount fee, CAmount long_term_fee) { CMutableTransaction tx; tx.vout.resize(nInput + 1); tx.vout[nInput].nValue = nValue; tx.nLockTime = nextLockTime++; // so all transactions get different hashes - COutput coin(COutPoint(tx.GetHash(), nInput), tx.vout.at(nInput), /*depth=*/ 1, /*input_bytes=*/ 148, /*spendable=*/ true, /*solvable=*/ true, /*safe=*/ true, /*time=*/ 0, /*from_me=*/ false, fee); - coin.long_term_fee = long_term_fee; - set.insert(std::make_shared<COutput>(coin)); + std::shared_ptr<COutput> coin = std::make_shared<COutput>(COutPoint(tx.GetHash(), nInput), tx.vout.at(nInput), /*depth=*/ 1, /*input_bytes=*/ 148, /*spendable=*/ true, /*solvable=*/ true, /*safe=*/ true, /*time=*/ 0, /*from_me=*/ false, fee); + OutputGroup group; + group.Insert(coin, /*ancestors=*/ 0, /*descendants=*/ 0); + coin->long_term_fee = long_term_fee; // group.Insert() will modify long_term_fee, so we need to set it afterwards + result.AddInput(group); } static void add_coin(CoinsResult& available_coins, CWallet& wallet, const CAmount& nValue, CFeeRate feerate = CFeeRate(0), int nAge = 6*24, bool fIsFromMe = false, int nInput =0, bool spendable = false, int custom_size = 0) @@ -827,7 +829,6 @@ BOOST_AUTO_TEST_CASE(SelectCoins_test) BOOST_AUTO_TEST_CASE(waste_test) { - CoinSet selection; const CAmount fee{100}; const CAmount change_cost{125}; const CAmount fee_diff{40}; @@ -835,92 +836,179 @@ BOOST_AUTO_TEST_CASE(waste_test) const CAmount target{2 * COIN}; const CAmount excess{in_amt - fee * 2 - target}; - // Waste with change is the change cost and difference between fee and long term fee - add_coin(1 * COIN, 1, selection, fee, fee - fee_diff); - add_coin(2 * COIN, 2, selection, fee, fee - fee_diff); - const CAmount waste1 = GetSelectionWaste(selection, change_cost, target); - BOOST_CHECK_EQUAL(fee_diff * 2 + change_cost, waste1); - selection.clear(); - - // Waste without change is the excess and difference between fee and long term fee - add_coin(1 * COIN, 1, selection, fee, fee - fee_diff); - add_coin(2 * COIN, 2, selection, fee, fee - fee_diff); - const CAmount waste_nochange1 = GetSelectionWaste(selection, 0, target); - BOOST_CHECK_EQUAL(fee_diff * 2 + excess, waste_nochange1); - selection.clear(); - - // Waste with change and fee == long term fee is just cost of change - add_coin(1 * COIN, 1, selection, fee, fee); - add_coin(2 * COIN, 2, selection, fee, fee); - BOOST_CHECK_EQUAL(change_cost, GetSelectionWaste(selection, change_cost, target)); - selection.clear(); - - // Waste without change and fee == long term fee is just the excess - add_coin(1 * COIN, 1, selection, fee, fee); - add_coin(2 * COIN, 2, selection, fee, fee); - BOOST_CHECK_EQUAL(excess, GetSelectionWaste(selection, 0, target)); - selection.clear(); - - // Waste will be greater when fee is greater, but long term fee is the same - add_coin(1 * COIN, 1, selection, fee * 2, fee - fee_diff); - add_coin(2 * COIN, 2, selection, fee * 2, fee - fee_diff); - const CAmount waste2 = GetSelectionWaste(selection, change_cost, target); - BOOST_CHECK_GT(waste2, waste1); - selection.clear(); - - // Waste with change is the change cost and difference between fee and long term fee - // With long term fee greater than fee, waste should be less than when long term fee is less than fee - add_coin(1 * COIN, 1, selection, fee, fee + fee_diff); - add_coin(2 * COIN, 2, selection, fee, fee + fee_diff); - const CAmount waste3 = GetSelectionWaste(selection, change_cost, target); - BOOST_CHECK_EQUAL(fee_diff * -2 + change_cost, waste3); - BOOST_CHECK_LT(waste3, waste1); - selection.clear(); - - // Waste without change is the excess and difference between fee and long term fee - // With long term fee greater than fee, waste should be less than when long term fee is less than fee - add_coin(1 * COIN, 1, selection, fee, fee + fee_diff); - add_coin(2 * COIN, 2, selection, fee, fee + fee_diff); - const CAmount waste_nochange2 = GetSelectionWaste(selection, 0, target); - BOOST_CHECK_EQUAL(fee_diff * -2 + excess, waste_nochange2); - BOOST_CHECK_LT(waste_nochange2, waste_nochange1); - selection.clear(); - - // No Waste when fee == long_term_fee, no change, and no excess - add_coin(1 * COIN, 1, selection, fee, fee); - add_coin(2 * COIN, 2, selection, fee, fee); - const CAmount exact_target{in_amt - fee * 2}; - BOOST_CHECK_EQUAL(0, GetSelectionWaste(selection, /*change_cost=*/0, exact_target)); - selection.clear(); - - // No Waste when (fee - long_term_fee) == (-cost_of_change), and no excess - const CAmount new_change_cost{fee_diff * 2}; - add_coin(1 * COIN, 1, selection, fee, fee + fee_diff); - add_coin(2 * COIN, 2, selection, fee, fee + fee_diff); - BOOST_CHECK_EQUAL(0, GetSelectionWaste(selection, new_change_cost, target)); - selection.clear(); - - // No Waste when (fee - long_term_fee) == (-excess), no change cost - const CAmount new_target{in_amt - fee * 2 - fee_diff * 2}; - add_coin(1 * COIN, 1, selection, fee, fee + fee_diff); - add_coin(2 * COIN, 2, selection, fee, fee + fee_diff); - BOOST_CHECK_EQUAL(0, GetSelectionWaste(selection, /*change_cost=*/ 0, new_target)); - selection.clear(); - - // Negative waste when the long term fee is greater than the current fee and the selected value == target - const CAmount exact_target1{3 * COIN - 2 * fee}; - const CAmount target_waste1{-2 * fee_diff}; // = (2 * fee) - (2 * (fee + fee_diff)) - add_coin(1 * COIN, 1, selection, fee, fee + fee_diff); - add_coin(2 * COIN, 2, selection, fee, fee + fee_diff); - BOOST_CHECK_EQUAL(target_waste1, GetSelectionWaste(selection, /*change_cost=*/ 0, exact_target1)); - selection.clear(); - - // Negative waste when the long term fee is greater than the current fee and change_cost < - (inputs * (fee - long_term_fee)) - const CAmount large_fee_diff{90}; - const CAmount target_waste2{-2 * large_fee_diff + change_cost}; // = (2 * fee) - (2 * (fee + large_fee_diff)) + change_cost - add_coin(1 * COIN, 1, selection, fee, fee + large_fee_diff); - add_coin(2 * COIN, 2, selection, fee, fee + large_fee_diff); - BOOST_CHECK_EQUAL(target_waste2, GetSelectionWaste(selection, change_cost, target)); + // The following tests that the waste is calculated correctly in various scenarios. + // ComputeAndSetWaste will first determine the size of the change output. We don't really + // care about the change and just want to use the variant that always includes the change_cost, + // so min_viable_change and change_fee are set to 0 to ensure that. + { + // Waste with change is the change cost and difference between fee and long term fee + SelectionResult selection1{target, SelectionAlgorithm::MANUAL}; + add_coin(1 * COIN, 1, selection1, fee, fee - fee_diff); + add_coin(2 * COIN, 2, selection1, fee, fee - fee_diff); + selection1.ComputeAndSetWaste(/*min_viable_change=*/0, change_cost, /*change_fee=*/0); + BOOST_CHECK_EQUAL(fee_diff * 2 + change_cost, selection1.GetWaste()); + + // Waste will be greater when fee is greater, but long term fee is the same + SelectionResult selection2{target, SelectionAlgorithm::MANUAL}; + add_coin(1 * COIN, 1, selection2, fee * 2, fee - fee_diff); + add_coin(2 * COIN, 2, selection2, fee * 2, fee - fee_diff); + selection2.ComputeAndSetWaste(/*min_viable_change=*/0, change_cost, /*change_fee=*/0); + BOOST_CHECK_GT(selection2.GetWaste(), selection1.GetWaste()); + + // Waste with change is the change cost and difference between fee and long term fee + // With long term fee greater than fee, waste should be less than when long term fee is less than fee + SelectionResult selection3{target, SelectionAlgorithm::MANUAL}; + add_coin(1 * COIN, 1, selection3, fee, fee + fee_diff); + add_coin(2 * COIN, 2, selection3, fee, fee + fee_diff); + selection3.ComputeAndSetWaste(/*min_viable_change=*/0, change_cost, /*change_fee=*/0); + BOOST_CHECK_EQUAL(fee_diff * -2 + change_cost, selection3.GetWaste()); + BOOST_CHECK_LT(selection3.GetWaste(), selection1.GetWaste()); + } + + { + // Waste without change is the excess and difference between fee and long term fee + SelectionResult selection_nochange1{target, SelectionAlgorithm::MANUAL}; + add_coin(1 * COIN, 1, selection_nochange1, fee, fee - fee_diff); + add_coin(2 * COIN, 2, selection_nochange1, fee, fee - fee_diff); + selection_nochange1.ComputeAndSetWaste(/*min_viable_change=*/0, /*change_cost=*/0, /*change_fee=*/0); + BOOST_CHECK_EQUAL(fee_diff * 2 + excess, selection_nochange1.GetWaste()); + + // Waste without change is the excess and difference between fee and long term fee + // With long term fee greater than fee, waste should be less than when long term fee is less than fee + SelectionResult selection_nochange2{target, SelectionAlgorithm::MANUAL}; + add_coin(1 * COIN, 1, selection_nochange2, fee, fee + fee_diff); + add_coin(2 * COIN, 2, selection_nochange2, fee, fee + fee_diff); + selection_nochange2.ComputeAndSetWaste(/*min_viable_change=*/0, /*change_cost=*/0, /*change_fee=*/0); + BOOST_CHECK_EQUAL(fee_diff * -2 + excess, selection_nochange2.GetWaste()); + BOOST_CHECK_LT(selection_nochange2.GetWaste(), selection_nochange1.GetWaste()); + } + + { + // Waste with change and fee == long term fee is just cost of change + SelectionResult selection{target, SelectionAlgorithm::MANUAL}; + add_coin(1 * COIN, 1, selection, fee, fee); + add_coin(2 * COIN, 2, selection, fee, fee); + selection.ComputeAndSetWaste(/*min_viable_change=*/0, change_cost, /*change_fee=*/0); + BOOST_CHECK_EQUAL(change_cost, selection.GetWaste()); + } + + { + // Waste without change and fee == long term fee is just the excess + SelectionResult selection{target, SelectionAlgorithm::MANUAL}; + add_coin(1 * COIN, 1, selection, fee, fee); + add_coin(2 * COIN, 2, selection, fee, fee); + selection.ComputeAndSetWaste(/*min_viable_change=*/0, /*change_cost=*/0, /*change_fee=*/0); + BOOST_CHECK_EQUAL(excess, selection.GetWaste()); + } + + { + // No Waste when fee == long_term_fee, no change, and no excess + const CAmount exact_target{in_amt - fee * 2}; + SelectionResult selection{exact_target, SelectionAlgorithm::MANUAL}; + add_coin(1 * COIN, 1, selection, fee, fee); + add_coin(2 * COIN, 2, selection, fee, fee); + selection.ComputeAndSetWaste(/*min_viable_change=*/0, /*change_cost=*/0, /*change_fee=*/0); + BOOST_CHECK_EQUAL(0, selection.GetWaste()); + } + + { + // No Waste when (fee - long_term_fee) == (-cost_of_change), and no excess + SelectionResult selection{target, SelectionAlgorithm::MANUAL}; + const CAmount new_change_cost{fee_diff * 2}; + add_coin(1 * COIN, 1, selection, fee, fee + fee_diff); + add_coin(2 * COIN, 2, selection, fee, fee + fee_diff); + selection.ComputeAndSetWaste(/*min_viable_change=*/0, new_change_cost, /*change_fee=*/0); + BOOST_CHECK_EQUAL(0, selection.GetWaste()); + } + + { + // No Waste when (fee - long_term_fee) == (-excess), no change cost + const CAmount new_target{in_amt - fee * 2 - fee_diff * 2}; + SelectionResult selection{new_target, SelectionAlgorithm::MANUAL}; + add_coin(1 * COIN, 1, selection, fee, fee + fee_diff); + add_coin(2 * COIN, 2, selection, fee, fee + fee_diff); + selection.ComputeAndSetWaste(/*min_viable_change=*/0, /*change_cost=*/0, /*change_fee=*/0); + BOOST_CHECK_EQUAL(0, selection.GetWaste()); + } + + { + // Negative waste when the long term fee is greater than the current fee and the selected value == target + const CAmount exact_target{3 * COIN - 2 * fee}; + SelectionResult selection{exact_target, SelectionAlgorithm::MANUAL}; + const CAmount target_waste1{-2 * fee_diff}; // = (2 * fee) - (2 * (fee + fee_diff)) + add_coin(1 * COIN, 1, selection, fee, fee + fee_diff); + add_coin(2 * COIN, 2, selection, fee, fee + fee_diff); + selection.ComputeAndSetWaste(/*min_viable_change=*/0, /*change_cost=*/0, /*change_fee=*/0); + BOOST_CHECK_EQUAL(target_waste1, selection.GetWaste()); + } + + { + // Negative waste when the long term fee is greater than the current fee and change_cost < - (inputs * (fee - long_term_fee)) + SelectionResult selection{target, SelectionAlgorithm::MANUAL}; + const CAmount large_fee_diff{90}; + const CAmount target_waste2{-2 * large_fee_diff + change_cost}; // = (2 * fee) - (2 * (fee + large_fee_diff)) + change_cost + add_coin(1 * COIN, 1, selection, fee, fee + large_fee_diff); + add_coin(2 * COIN, 2, selection, fee, fee + large_fee_diff); + selection.ComputeAndSetWaste(/*min_viable_change=*/0, change_cost, /*change_fee=*/0); + BOOST_CHECK_EQUAL(target_waste2, selection.GetWaste()); + } +} + + +BOOST_AUTO_TEST_CASE(bump_fee_test) +{ + const CAmount fee{100}; + const CAmount min_viable_change{200}; + const CAmount change_cost{125}; + const CAmount change_fee{35}; + const CAmount fee_diff{40}; + const CAmount target{2 * COIN}; + + { + SelectionResult selection{target, SelectionAlgorithm::MANUAL}; + add_coin(1 * COIN, 1, selection, /*fee=*/fee, /*long_term_fee=*/fee + fee_diff); + add_coin(2 * COIN, 2, selection, fee, fee + fee_diff); + const std::vector<std::shared_ptr<COutput>> inputs = selection.GetShuffledInputVector(); + + for (size_t i = 0; i < inputs.size(); ++i) { + inputs[i]->ApplyBumpFee(20*(i+1)); + } + + selection.ComputeAndSetWaste(min_viable_change, change_cost, change_fee); + CAmount expected_waste = fee_diff * -2 + change_cost + /*bump_fees=*/60; + BOOST_CHECK_EQUAL(expected_waste, selection.GetWaste()); + + selection.SetBumpFeeDiscount(30); + selection.ComputeAndSetWaste(min_viable_change, change_cost, change_fee); + expected_waste = fee_diff * -2 + change_cost + /*bump_fees=*/60 - /*group_discount=*/30; + BOOST_CHECK_EQUAL(expected_waste, selection.GetWaste()); + } + + { + // Test with changeless transaction + // + // Bump fees and excess both contribute fully to the waste score, + // therefore, a bump fee group discount will not change the waste + // score as long as we do not create change in both instances. + CAmount changeless_target = 3 * COIN - 2 * fee - 100; + SelectionResult selection{changeless_target, SelectionAlgorithm::MANUAL}; + add_coin(1 * COIN, 1, selection, /*fee=*/fee, /*long_term_fee=*/fee + fee_diff); + add_coin(2 * COIN, 2, selection, fee, fee + fee_diff); + const std::vector<std::shared_ptr<COutput>> inputs = selection.GetShuffledInputVector(); + + for (size_t i = 0; i < inputs.size(); ++i) { + inputs[i]->ApplyBumpFee(20*(i+1)); + } + + selection.ComputeAndSetWaste(min_viable_change, change_cost, change_fee); + CAmount expected_waste = fee_diff * -2 + /*bump_fees=*/60 + /*excess = 100 - bump_fees*/40; + BOOST_CHECK_EQUAL(expected_waste, selection.GetWaste()); + + selection.SetBumpFeeDiscount(30); + selection.ComputeAndSetWaste(min_viable_change, change_cost, change_fee); + expected_waste = fee_diff * -2 + /*bump_fees=*/60 - /*group_discount=*/30 + /*excess = 100 - bump_fees + group_discount*/70; + BOOST_CHECK_EQUAL(expected_waste, selection.GetWaste()); + } } BOOST_AUTO_TEST_CASE(effective_value_test) diff --git a/test/functional/test_runner.py b/test/functional/test_runner.py index f44a5be19f..32aee3aa80 100755 --- a/test/functional/test_runner.py +++ b/test/functional/test_runner.py @@ -316,6 +316,7 @@ BASE_SCRIPTS = [ 'wallet_sendall.py --descriptors', 'wallet_create_tx.py --descriptors', 'wallet_inactive_hdchains.py --legacy-wallet', + 'wallet_spend_unconfirmed.py', 'p2p_fingerprint.py', 'feature_uacomment.py', 'feature_init.py', diff --git a/test/functional/wallet_spend_unconfirmed.py b/test/functional/wallet_spend_unconfirmed.py new file mode 100755 index 0000000000..bfcdeaeaa8 --- /dev/null +++ b/test/functional/wallet_spend_unconfirmed.py @@ -0,0 +1,508 @@ +#!/usr/bin/env python3 +# Copyright (c) 2022 The Bitcoin Core developers +# Distributed under the MIT software license, see the accompanying +# file COPYING or http://www.opensource.org/licenses/mit-license.php. + +from decimal import Decimal, getcontext + +from test_framework.test_framework import BitcoinTestFramework +from test_framework.util import ( + assert_greater_than_or_equal, + assert_equal, + find_vout_for_address, +) + +class UnconfirmedInputTest(BitcoinTestFramework): + def add_options(self, parser): + self.add_wallet_options(parser) + + def set_test_params(self): + getcontext().prec=9 + self.setup_clean_chain = True + self.num_nodes = 1 + + def setup_and_fund_wallet(self, walletname): + self.nodes[0].createwallet(walletname) + wallet = self.nodes[0].get_wallet_rpc(walletname) + + self.def_wallet.sendtoaddress(address=wallet.getnewaddress(), amount=2) + self.generate(self.nodes[0], 1) # confirm funding tx + return wallet + + def skip_test_if_missing_module(self): + self.skip_if_no_wallet() + + def calc_fee_rate(self, tx): + fee = Decimal(-1e8) * tx["fee"] + vsize = tx["decoded"]["vsize"] + return fee / vsize + + def calc_set_fee_rate(self, txs): + fees = Decimal(-1e8) * sum([tx["fee"] for tx in txs]) # fee is negative! + vsizes = sum([tx["decoded"]["vsize"] for tx in txs]) + return fees / vsizes + + def assert_spends_only_parents(self, tx, parent_txids): + parent_checklist = parent_txids.copy() + number_inputs = len(tx["decoded"]["vin"]) + assert_equal(number_inputs, len(parent_txids)) + for i in range(number_inputs): + txid_of_input = tx["decoded"]["vin"][i]["txid"] + assert txid_of_input in parent_checklist + parent_checklist.remove(txid_of_input) + + def assert_undershoots_target(self, tx): + resulting_fee_rate = self.calc_fee_rate(tx) + assert_greater_than_or_equal(self.target_fee_rate, resulting_fee_rate) + + def assert_beats_target(self, tx): + resulting_fee_rate = self.calc_fee_rate(tx) + assert_greater_than_or_equal(resulting_fee_rate, self.target_fee_rate) + + # Meta-Test: try feerate testing function on confirmed UTXO + def test_target_feerate_confirmed(self): + self.log.info("Start test feerate with confirmed input") + wallet = self.setup_and_fund_wallet("confirmed_wallet") + + ancestor_aware_txid = wallet.sendtoaddress(address=self.def_wallet.getnewaddress(), amount=0.5, fee_rate=self.target_fee_rate) + ancestor_aware_tx = wallet.gettransaction(txid=ancestor_aware_txid, verbose=True) + self.assert_beats_target(ancestor_aware_tx) + + wallet.unloadwallet() + + # Spend unconfirmed UTXO from high-feerate parent + def test_target_feerate_unconfirmed_high(self): + self.log.info("Start test feerate with high feerate unconfirmed input") + wallet = self.setup_and_fund_wallet("unconfirmed_high_wallet") + + # Send unconfirmed transaction with high feerate to testing wallet + parent_txid = wallet.sendtoaddress(address=wallet.getnewaddress(), amount=1, fee_rate=3*self.target_fee_rate) + parent_tx = wallet.gettransaction(txid=parent_txid, verbose=True) + self.assert_beats_target(parent_tx) + + ancestor_aware_txid = wallet.sendtoaddress(address=self.def_wallet.getnewaddress(), amount=0.5, fee_rate=self.target_fee_rate) + ancestor_aware_tx = wallet.gettransaction(txid=ancestor_aware_txid, verbose=True) + + self.assert_spends_only_parents(ancestor_aware_tx, [parent_txid]) + + self.assert_beats_target(ancestor_aware_tx) + + wallet.unloadwallet() + + # Spend unconfirmed UTXO from low-feerate parent. Expect that parent gets + # bumped to target feerate. + def test_target_feerate_unconfirmed_low(self): + self.log.info("Start test feerate with low feerate unconfirmed input") + wallet = self.setup_and_fund_wallet("unconfirmed_low_wallet") + + parent_txid = wallet.sendtoaddress(address=wallet.getnewaddress(), amount=1, fee_rate=1) + parent_tx = wallet.gettransaction(txid=parent_txid, verbose=True) + + self.assert_undershoots_target(parent_tx) + + ancestor_aware_txid = wallet.sendtoaddress(address=self.def_wallet.getnewaddress(), amount=0.5, fee_rate=self.target_fee_rate) + ancestor_aware_tx = wallet.gettransaction(txid=ancestor_aware_txid, verbose=True) + + self.assert_spends_only_parents(ancestor_aware_tx, [parent_txid]) + + self.assert_beats_target(ancestor_aware_tx) + resulting_ancestry_fee_rate = self.calc_set_fee_rate([parent_tx, ancestor_aware_tx]) + assert_greater_than_or_equal(resulting_ancestry_fee_rate, self.target_fee_rate) + assert_greater_than_or_equal(self.target_fee_rate*1.01, resulting_ancestry_fee_rate) + + wallet.unloadwallet() + + # Spend UTXO with unconfirmed low feerate parent and grandparent + # txs. Expect that both ancestors get bumped to target feerate. + def test_chain_of_unconfirmed_low(self): + self.log.info("Start test with parent and grandparent tx") + wallet = self.setup_and_fund_wallet("unconfirmed_low_chain_wallet") + + grandparent_txid = wallet.sendtoaddress(address=wallet.getnewaddress(), amount=1.8, fee_rate=1) + gp_tx = wallet.gettransaction(txid=grandparent_txid, verbose=True) + + self.assert_undershoots_target(gp_tx) + + parent_txid = wallet.sendtoaddress(address=wallet.getnewaddress(), amount=1.5, fee_rate=2) + p_tx = wallet.gettransaction(txid=parent_txid, verbose=True) + + self.assert_undershoots_target(p_tx) + + ancestor_aware_txid = wallet.sendtoaddress(address=self.def_wallet.getnewaddress(), amount=1.3, fee_rate=self.target_fee_rate) + ancestor_aware_tx = wallet.gettransaction(txid=ancestor_aware_txid, verbose=True) + self.assert_spends_only_parents(ancestor_aware_tx, [parent_txid]) + + self.assert_beats_target(ancestor_aware_tx) + resulting_ancestry_fee_rate = self.calc_set_fee_rate([gp_tx, p_tx, ancestor_aware_tx]) + assert_greater_than_or_equal(resulting_ancestry_fee_rate, self.target_fee_rate) + assert_greater_than_or_equal(self.target_fee_rate*1.01, resulting_ancestry_fee_rate) + + wallet.unloadwallet() + + # Spend unconfirmed UTXOs from two low feerate parent txs. + def test_two_low_feerate_unconfirmed_parents(self): + self.log.info("Start test with two unconfirmed parent txs") + wallet = self.setup_and_fund_wallet("two_parents_wallet") + + # Add second UTXO to tested wallet + self.def_wallet.sendtoaddress(address=wallet.getnewaddress(), amount=2) + self.generate(self.nodes[0], 1) # confirm funding tx + + parent_one_txid = wallet.sendtoaddress(address=wallet.getnewaddress(), amount=1.5, fee_rate=2) + p_one_tx = wallet.gettransaction(txid=parent_one_txid, verbose=True) + self.assert_undershoots_target(p_one_tx) + + parent_two_txid = wallet.sendtoaddress(address=wallet.getnewaddress(), amount=1.5, fee_rate=1) + p_two_tx = wallet.gettransaction(txid=parent_two_txid, verbose=True) + self.assert_undershoots_target(p_two_tx) + + ancestor_aware_txid = wallet.sendtoaddress(address=self.def_wallet.getnewaddress(), amount=2.8, fee_rate=self.target_fee_rate) + ancestor_aware_tx = wallet.gettransaction(txid=ancestor_aware_txid, verbose=True) + self.assert_spends_only_parents(ancestor_aware_tx, [parent_one_txid, parent_two_txid]) + + self.assert_beats_target(ancestor_aware_tx) + resulting_ancestry_fee_rate = self.calc_set_fee_rate([p_one_tx, p_two_tx, ancestor_aware_tx]) + assert_greater_than_or_equal(resulting_ancestry_fee_rate, self.target_fee_rate) + assert_greater_than_or_equal(self.target_fee_rate*1.01, resulting_ancestry_fee_rate) + + wallet.unloadwallet() + + # Spend two unconfirmed inputs, one each from low and high feerate parents + def test_mixed_feerate_unconfirmed_parents(self): + self.log.info("Start test with two unconfirmed parent txs one of which has a higher feerate") + wallet = self.setup_and_fund_wallet("two_mixed_parents_wallet") + + # Add second UTXO to tested wallet + self.def_wallet.sendtoaddress(address=wallet.getnewaddress(), amount=2) + self.generate(self.nodes[0], 1) # confirm funding tx + + high_parent_txid = wallet.sendtoaddress(address=wallet.getnewaddress(), amount=1.5, fee_rate=self.target_fee_rate*2) + p_high_tx = wallet.gettransaction(txid=high_parent_txid, verbose=True) + # This time the parent is greater than the child + self.assert_beats_target(p_high_tx) + + parent_low_txid = wallet.sendtoaddress(address=wallet.getnewaddress(), amount=1.5, fee_rate=1) + p_low_tx = wallet.gettransaction(txid=parent_low_txid, verbose=True) + # Other parent needs bump + self.assert_undershoots_target(p_low_tx) + + ancestor_aware_txid = wallet.sendtoaddress(address=self.def_wallet.getnewaddress(), amount=2.8, fee_rate=self.target_fee_rate) + ancestor_aware_tx = wallet.gettransaction(txid=ancestor_aware_txid, verbose=True) + self.assert_spends_only_parents(ancestor_aware_tx, [parent_low_txid, high_parent_txid]) + + self.assert_beats_target(ancestor_aware_tx) + resulting_ancestry_fee_rate = self.calc_set_fee_rate([p_high_tx, p_low_tx, ancestor_aware_tx]) + assert_greater_than_or_equal(resulting_ancestry_fee_rate, self.target_fee_rate) + + resulting_bumped_ancestry_fee_rate = self.calc_set_fee_rate([p_low_tx, ancestor_aware_tx]) + assert_greater_than_or_equal(resulting_bumped_ancestry_fee_rate, self.target_fee_rate) + assert_greater_than_or_equal(self.target_fee_rate*1.01, resulting_bumped_ancestry_fee_rate) + + wallet.unloadwallet() + + # Spend from chain with high feerate grandparent and low feerate parent + def test_chain_of_high_low(self): + self.log.info("Start test with low parent and high grandparent tx") + wallet = self.setup_and_fund_wallet("high_low_chain_wallet") + + grandparent_txid = wallet.sendtoaddress(address=wallet.getnewaddress(), amount=1.8, fee_rate=self.target_fee_rate * 10) + gp_tx = wallet.gettransaction(txid=grandparent_txid, verbose=True) + # grandparent has higher feerate + self.assert_beats_target(gp_tx) + + parent_txid = wallet.sendtoaddress(address=wallet.getnewaddress(), amount=1.5, fee_rate=1) + # parent is low feerate + p_tx = wallet.gettransaction(txid=parent_txid, verbose=True) + self.assert_undershoots_target(p_tx) + + ancestor_aware_txid = wallet.sendtoaddress(address=self.def_wallet.getnewaddress(), amount=1.3, fee_rate=self.target_fee_rate) + ancestor_aware_tx = wallet.gettransaction(txid=ancestor_aware_txid, verbose=True) + self.assert_spends_only_parents(ancestor_aware_tx, [parent_txid]) + + self.assert_beats_target(ancestor_aware_tx) + resulting_ancestry_fee_rate = self.calc_set_fee_rate([p_tx, ancestor_aware_tx]) + assert_greater_than_or_equal(resulting_ancestry_fee_rate, self.target_fee_rate) + assert_greater_than_or_equal(self.target_fee_rate*1.01, resulting_ancestry_fee_rate) + resulting_ancestry_fee_rate_with_high_feerate_gp = self.calc_set_fee_rate([gp_tx, p_tx, ancestor_aware_tx]) + # Check that we bumped the parent without relying on the grandparent + assert_greater_than_or_equal(resulting_ancestry_fee_rate_with_high_feerate_gp, self.target_fee_rate*1.1) + + wallet.unloadwallet() + + # Spend UTXO from chain of unconfirmed transactions with low feerate + # grandparent and even lower feerate parent + def test_chain_of_high_low_below_target_feerate(self): + self.log.info("Start test with low parent and higher low grandparent tx") + wallet = self.setup_and_fund_wallet("low_and_lower_chain_wallet") + + grandparent_txid = wallet.sendtoaddress(address=wallet.getnewaddress(), amount=1.8, fee_rate=5) + gp_tx = wallet.gettransaction(txid=grandparent_txid, verbose=True) + + # grandparent has higher feerate, but below target + self.assert_undershoots_target(gp_tx) + + parent_txid = wallet.sendtoaddress(address=wallet.getnewaddress(), amount=1.5, fee_rate=1) + p_tx = wallet.gettransaction(txid=parent_txid, verbose=True) + # parent even lower + self.assert_undershoots_target(p_tx) + + ancestor_aware_txid = wallet.sendtoaddress(address=self.def_wallet.getnewaddress(), amount=1.3, fee_rate=self.target_fee_rate) + ancestor_aware_tx = wallet.gettransaction(txid=ancestor_aware_txid, verbose=True) + self.assert_spends_only_parents(ancestor_aware_tx, [parent_txid]) + + self.assert_beats_target(ancestor_aware_tx) + resulting_ancestry_fee_rate = self.calc_set_fee_rate([gp_tx, p_tx, ancestor_aware_tx]) + assert_greater_than_or_equal(resulting_ancestry_fee_rate, self.target_fee_rate) + assert_greater_than_or_equal(self.target_fee_rate*1.01, resulting_ancestry_fee_rate) + + wallet.unloadwallet() + + # Test fee calculation when bumping while using subtract fee from output (SFFO) + def test_target_feerate_unconfirmed_low_sffo(self): + self.log.info("Start test feerate with low feerate unconfirmed input, while subtracting from output") + wallet = self.setup_and_fund_wallet("unconfirmed_low_wallet_sffo") + + parent_txid = wallet.sendtoaddress(address=wallet.getnewaddress(), amount=1, fee_rate=1) + parent_tx = wallet.gettransaction(txid=parent_txid, verbose=True) + + self.assert_undershoots_target(parent_tx) + + ancestor_aware_txid = wallet.sendtoaddress(address=self.def_wallet.getnewaddress(), amount=0.5, fee_rate=self.target_fee_rate, subtractfeefromamount=True) + ancestor_aware_tx = wallet.gettransaction(txid=ancestor_aware_txid, verbose=True) + + self.assert_spends_only_parents(ancestor_aware_tx, [parent_txid]) + + self.assert_beats_target(ancestor_aware_tx) + resulting_ancestry_fee_rate = self.calc_set_fee_rate([parent_tx, ancestor_aware_tx]) + assert_greater_than_or_equal(resulting_ancestry_fee_rate, self.target_fee_rate) + assert_greater_than_or_equal(self.target_fee_rate*1.01, resulting_ancestry_fee_rate) + + wallet.unloadwallet() + + # Test that parents of preset unconfirmed inputs get cpfp'ed + def test_preset_input_cpfp(self): + self.log.info("Start test with preset input from low feerate unconfirmed transaction") + wallet = self.setup_and_fund_wallet("preset_input") + + parent_txid = wallet.sendtoaddress(address=wallet.getnewaddress(), amount=1, fee_rate=1) + parent_tx = wallet.gettransaction(txid=parent_txid, verbose=True) + + self.assert_undershoots_target(parent_tx) + + number_outputs = len(parent_tx["decoded"]["vout"]) + assert_equal(number_outputs, 2) + + # we don't care which of the two outputs we spent, they're both ours + ancestor_aware_txid = wallet.send(outputs=[{self.def_wallet.getnewaddress(): 0.5}], fee_rate=self.target_fee_rate, options={"add_inputs": True, "inputs": [{"txid": parent_txid, "vout": 0}]})["txid"] + ancestor_aware_tx = wallet.gettransaction(txid=ancestor_aware_txid, verbose=True) + + self.assert_spends_only_parents(ancestor_aware_tx, [parent_txid]) + + self.assert_beats_target(ancestor_aware_tx) + resulting_ancestry_fee_rate = self.calc_set_fee_rate([parent_tx, ancestor_aware_tx]) + assert_greater_than_or_equal(resulting_ancestry_fee_rate, self.target_fee_rate) + assert_greater_than_or_equal(self.target_fee_rate*1.01, resulting_ancestry_fee_rate) + + wallet.unloadwallet() + + # Test that RBFing a transaction with unconfirmed input gets the right feerate + def test_rbf_bumping(self): + self.log.info("Start test to rbf a transaction unconfirmed input to bump it") + wallet = self.setup_and_fund_wallet("bump") + + parent_txid = wallet.sendtoaddress(address=wallet.getnewaddress(), amount=1, fee_rate=1) + parent_tx = wallet.gettransaction(txid=parent_txid, verbose=True) + + self.assert_undershoots_target(parent_tx) + + to_be_rbfed_ancestor_aware_txid = wallet.sendtoaddress(address=self.def_wallet.getnewaddress(), amount=0.5, fee_rate=self.target_fee_rate) + ancestor_aware_tx = wallet.gettransaction(txid=to_be_rbfed_ancestor_aware_txid, verbose=True) + + self.assert_spends_only_parents(ancestor_aware_tx, [parent_txid]) + + self.assert_beats_target(ancestor_aware_tx) + resulting_ancestry_fee_rate = self.calc_set_fee_rate([parent_tx, ancestor_aware_tx]) + assert_greater_than_or_equal(resulting_ancestry_fee_rate, self.target_fee_rate) + assert_greater_than_or_equal(self.target_fee_rate*1.01, resulting_ancestry_fee_rate) + + bumped_ancestor_aware_txid = wallet.bumpfee(txid=to_be_rbfed_ancestor_aware_txid, options={"fee_rate": self.target_fee_rate * 2} )["txid"] + bumped_ancestor_aware_tx = wallet.gettransaction(txid=bumped_ancestor_aware_txid, verbose=True) + self.assert_spends_only_parents(ancestor_aware_tx, [parent_txid]) + + resulting_bumped_fee_rate = self.calc_fee_rate(bumped_ancestor_aware_tx) + assert_greater_than_or_equal(resulting_bumped_fee_rate, 2*self.target_fee_rate) + resulting_bumped_ancestry_fee_rate = self.calc_set_fee_rate([parent_tx, bumped_ancestor_aware_tx]) + assert_greater_than_or_equal(resulting_bumped_ancestry_fee_rate, 2*self.target_fee_rate) + assert_greater_than_or_equal(2*self.target_fee_rate*1.01, resulting_bumped_ancestry_fee_rate) + + wallet.unloadwallet() + + # Test that transaction spending two UTXOs with overlapping ancestry does not bump shared ancestors twice + def test_target_feerate_unconfirmed_low_overlapping_ancestry(self): + self.log.info("Start test where two UTXOs have overlapping ancestry") + wallet = self.setup_and_fund_wallet("overlapping_ancestry_wallet") + + parent_txid = wallet.sendtoaddress(address=wallet.getnewaddress(), amount=1, fee_rate=1) + two_output_parent_tx = wallet.gettransaction(txid=parent_txid, verbose=True) + + self.assert_undershoots_target(two_output_parent_tx) + + # spend both outputs from parent transaction + ancestor_aware_txid = wallet.sendtoaddress(address=self.def_wallet.getnewaddress(), amount=1.5, fee_rate=self.target_fee_rate) + ancestor_aware_tx = wallet.gettransaction(txid=ancestor_aware_txid, verbose=True) + self.assert_spends_only_parents(ancestor_aware_tx, [parent_txid, parent_txid]) + + self.assert_beats_target(ancestor_aware_tx) + resulting_ancestry_fee_rate = self.calc_set_fee_rate([two_output_parent_tx, ancestor_aware_tx]) + assert_greater_than_or_equal(resulting_ancestry_fee_rate, self.target_fee_rate) + assert_greater_than_or_equal(self.target_fee_rate*1.01, resulting_ancestry_fee_rate) + + wallet.unloadwallet() + + # Test that new transaction ignores sibling transaction with low feerate + def test_sibling_tx_gets_ignored(self): + self.log.info("Start test where a low-fee sibling tx gets created and check that bumping ignores it") + wallet = self.setup_and_fund_wallet("ignore-sibling") + + parent_txid = wallet.sendtoaddress(address=wallet.getnewaddress(), amount=1, fee_rate=2) + parent_tx = wallet.gettransaction(txid=parent_txid, verbose=True) + + self.assert_undershoots_target(parent_tx) + + # create sibling tx + sibling_txid = wallet.sendtoaddress(address=self.def_wallet.getnewaddress(), amount=0.9, fee_rate=1) + sibling_tx = wallet.gettransaction(txid=sibling_txid, verbose=True) + self.assert_undershoots_target(sibling_tx) + + # spend both outputs from parent transaction + ancestor_aware_txid = wallet.sendtoaddress(address=self.def_wallet.getnewaddress(), amount=0.5, fee_rate=self.target_fee_rate) + ancestor_aware_tx = wallet.gettransaction(txid=ancestor_aware_txid, verbose=True) + + self.assert_spends_only_parents(ancestor_aware_tx, [parent_txid]) + + self.assert_beats_target(ancestor_aware_tx) + resulting_ancestry_fee_rate = self.calc_set_fee_rate([parent_tx, ancestor_aware_tx]) + assert_greater_than_or_equal(resulting_ancestry_fee_rate, self.target_fee_rate) + assert_greater_than_or_equal(self.target_fee_rate*1.01, resulting_ancestry_fee_rate) + + wallet.unloadwallet() + + # Test that new transaction only pays for itself when high feerate sibling pays for parent + def test_sibling_tx_bumps_parent(self): + self.log.info("Start test where a high-fee sibling tx bumps the parent") + wallet = self.setup_and_fund_wallet("generous-sibling") + + parent_txid = wallet.sendtoaddress(address=wallet.getnewaddress(), amount=1, fee_rate=1) + parent_tx = wallet.gettransaction(txid=parent_txid, verbose=True) + self.assert_undershoots_target(parent_tx) + + # create sibling tx + sibling_txid = wallet.sendtoaddress(address=self.def_wallet.getnewaddress(), amount=0.9, fee_rate=3*self.target_fee_rate) + sibling_tx = wallet.gettransaction(txid=sibling_txid, verbose=True) + self.assert_beats_target(sibling_tx) + + # spend both outputs from parent transaction + ancestor_aware_txid = wallet.sendtoaddress(address=self.def_wallet.getnewaddress(), amount=0.5, fee_rate=self.target_fee_rate) + ancestor_aware_tx = wallet.gettransaction(txid=ancestor_aware_txid, verbose=True) + + self.assert_spends_only_parents(ancestor_aware_tx, [parent_txid]) + + self.assert_beats_target(ancestor_aware_tx) + # Child is only paying for itself… + resulting_fee_rate = self.calc_fee_rate(ancestor_aware_tx) + assert_greater_than_or_equal(1.05 * self.target_fee_rate, resulting_fee_rate) + # …because sibling bumped to parent to ~50 s/vB, while our target is 30 s/vB + resulting_ancestry_fee_rate_sibling = self.calc_set_fee_rate([parent_tx, sibling_tx]) + assert_greater_than_or_equal(resulting_ancestry_fee_rate_sibling, self.target_fee_rate) + # and our resulting "ancestry feerate" is therefore BELOW target feerate + resulting_ancestry_fee_rate = self.calc_set_fee_rate([parent_tx, ancestor_aware_tx]) + assert_greater_than_or_equal(self.target_fee_rate, resulting_ancestry_fee_rate) + + wallet.unloadwallet() + + # Spend a confirmed and an unconfirmed input at the same time + def test_confirmed_and_unconfirmed_parent(self): + self.log.info("Start test with one unconfirmed and one confirmed input") + wallet = self.setup_and_fund_wallet("confirmed_and_unconfirmed_wallet") + confirmed_parent_txid = wallet.sendtoaddress(address=wallet.getnewaddress(), amount=1, fee_rate=self.target_fee_rate) + self.generate(self.nodes[0], 1) # Wallet has two confirmed UTXOs of ~1BTC each + unconfirmed_parent_txid = wallet.sendtoaddress(address=wallet.getnewaddress(), amount=0.5, fee_rate=0.5*self.target_fee_rate) + + # wallet has one confirmed UTXO of 1BTC and two unconfirmed UTXOs of ~0.5BTC each + ancestor_aware_txid = wallet.sendtoaddress(address=self.def_wallet.getnewaddress(), amount=1.4, fee_rate=self.target_fee_rate) + ancestor_aware_tx = wallet.gettransaction(txid=ancestor_aware_txid, verbose=True) + self.assert_spends_only_parents(ancestor_aware_tx, [confirmed_parent_txid, unconfirmed_parent_txid]) + resulting_fee_rate = self.calc_fee_rate(ancestor_aware_tx) + assert_greater_than_or_equal(resulting_fee_rate, self.target_fee_rate) + + wallet.unloadwallet() + + def test_external_input_unconfirmed_low(self): + self.log.info("Send funds to an external wallet then build tx that bumps parent by spending external input") + wallet = self.setup_and_fund_wallet("test_external_wallet") + + external_address = self.def_wallet.getnewaddress() + address_info = self.def_wallet.getaddressinfo(external_address) + external_descriptor = address_info["desc"] + parent_txid = wallet.sendtoaddress(address=external_address, amount=1, fee_rate=1) + parent_tx = wallet.gettransaction(txid=parent_txid, verbose=True) + + self.assert_undershoots_target(parent_tx) + + spend_res = wallet.send(outputs=[{self.def_wallet.getnewaddress(): 0.5}], fee_rate=self.target_fee_rate, options={"inputs":[{"txid":parent_txid, "vout":find_vout_for_address(self.nodes[0], parent_txid, external_address)}], "solving_data":{"descriptors":[external_descriptor]}}) + signed_psbt = self.def_wallet.walletprocesspsbt(spend_res["psbt"]) + external_tx = self.def_wallet.finalizepsbt(signed_psbt["psbt"]) + ancestor_aware_txid = self.def_wallet.sendrawtransaction(external_tx["hex"]) + + ancestor_aware_tx = self.def_wallet.gettransaction(txid=ancestor_aware_txid, verbose=True) + + self.assert_spends_only_parents(ancestor_aware_tx, [parent_txid]) + + self.assert_beats_target(ancestor_aware_tx) + resulting_ancestry_fee_rate = self.calc_set_fee_rate([parent_tx, ancestor_aware_tx]) + assert_greater_than_or_equal(resulting_ancestry_fee_rate, self.target_fee_rate) + assert_greater_than_or_equal(self.target_fee_rate*1.01, resulting_ancestry_fee_rate) + + wallet.unloadwallet() + + + def run_test(self): + self.log.info("Starting UnconfirmedInputTest!") + self.target_fee_rate = 30 + self.def_wallet = self.nodes[0].get_wallet_rpc(self.default_wallet_name) + self.generate(self.nodes[0], 110) + + self.test_target_feerate_confirmed() + + self.test_target_feerate_unconfirmed_high() + + self.test_target_feerate_unconfirmed_low() + + self.test_chain_of_unconfirmed_low() + + self.test_two_low_feerate_unconfirmed_parents() + + self.test_mixed_feerate_unconfirmed_parents() + + self.test_chain_of_high_low() + + self.test_chain_of_high_low_below_target_feerate() + + self.test_target_feerate_unconfirmed_low_sffo() + + self.test_preset_input_cpfp() + + self.test_rbf_bumping() + + self.test_target_feerate_unconfirmed_low_overlapping_ancestry() + + self.test_sibling_tx_gets_ignored() + + self.test_sibling_tx_bumps_parent() + + self.test_confirmed_and_unconfirmed_parent() + + self.test_external_input_unconfirmed_low() + +if __name__ == '__main__': + UnconfirmedInputTest().main() |