diff options
| -rw-r--r-- | src/policy/rbf.cpp | 23 | ||||
| -rw-r--r-- | src/policy/rbf.h | 26 | ||||
| -rw-r--r-- | src/txmempool.cpp | 129 | ||||
| -rw-r--r-- | src/txmempool.h | 23 |
4 files changed, 201 insertions, 0 deletions
diff --git a/src/policy/rbf.cpp b/src/policy/rbf.cpp index f0830d8f22..a2c6990657 100644 --- a/src/policy/rbf.cpp +++ b/src/policy/rbf.cpp @@ -19,6 +19,8 @@ #include <limits> #include <vector> +#include <compare> + RBFTransactionState IsRBFOptIn(const CTransaction& tx, const CTxMemPool& pool) { AssertLockHeld(pool.cs); @@ -181,3 +183,24 @@ std::optional<std::string> PaysForRBF(CAmount original_fees, } return std::nullopt; } + +std::optional<std::pair<DiagramCheckError, std::string>> ImprovesFeerateDiagram(CTxMemPool& pool, + const CTxMemPool::setEntries& direct_conflicts, + const CTxMemPool::setEntries& all_conflicts, + CAmount replacement_fees, + int64_t replacement_vsize) +{ + // Require that the replacement strictly improve the mempool's feerate diagram. + std::vector<FeeFrac> old_diagram, new_diagram; + + const auto diagram_results{pool.CalculateFeerateDiagramsForRBF(replacement_fees, replacement_vsize, direct_conflicts, all_conflicts)}; + + if (!diagram_results.has_value()) { + return std::make_pair(DiagramCheckError::UNCALCULABLE, util::ErrorString(diagram_results).original); + } + + if (!std::is_gt(CompareFeerateDiagram(diagram_results.value().second, diagram_results.value().first))) { + return std::make_pair(DiagramCheckError::FAILURE, "insufficient feerate: does not improve feerate diagram"); + } + return std::nullopt; +} diff --git a/src/policy/rbf.h b/src/policy/rbf.h index 5a33ed64a3..252fbec8e3 100644 --- a/src/policy/rbf.h +++ b/src/policy/rbf.h @@ -9,7 +9,9 @@ #include <primitives/transaction.h> #include <threadsafety.h> #include <txmempool.h> +#include <util/feefrac.h> +#include <compare> #include <cstddef> #include <cstdint> #include <optional> @@ -33,6 +35,13 @@ enum class RBFTransactionState { FINAL, }; +enum class DiagramCheckError { + /** Unable to calculate due to topology or other reason */ + UNCALCULABLE, + /** New diagram wasn't strictly superior */ + FAILURE, +}; + /** * Determine whether an unconfirmed transaction is signaling opt-in to RBF * according to BIP 125 @@ -106,4 +115,21 @@ std::optional<std::string> PaysForRBF(CAmount original_fees, CFeeRate relay_fee, const uint256& txid); +/** + * The replacement transaction must improve the feerate diagram of the mempool. + * @param[in] pool The mempool. + * @param[in] direct_conflicts Set of in-mempool txids corresponding to the direct conflicts i.e. + * input double-spends with the proposed transaction + * @param[in] all_conflicts Set of mempool entries corresponding to all transactions to be evicted + * @param[in] replacement_fees Fees of proposed replacement package + * @param[in] replacement_vsize Size of proposed replacement package + * @returns error type and string if mempool diagram doesn't improve, otherwise std::nullopt. + */ +std::optional<std::pair<DiagramCheckError, std::string>> ImprovesFeerateDiagram(CTxMemPool& pool, + const CTxMemPool::setEntries& direct_conflicts, + const CTxMemPool::setEntries& all_conflicts, + CAmount replacement_fees, + int64_t replacement_vsize) + EXCLUSIVE_LOCKS_REQUIRED(pool.cs); + #endif // BITCOIN_POLICY_RBF_H diff --git a/src/txmempool.cpp b/src/txmempool.cpp index 0bee27c2b2..4047ceda3c 100644 --- a/src/txmempool.cpp +++ b/src/txmempool.cpp @@ -17,6 +17,7 @@ #include <random.h> #include <reverse_iterator.h> #include <util/check.h> +#include <util/feefrac.h> #include <util/moneystr.h> #include <util/overflow.h> #include <util/result.h> @@ -1238,3 +1239,131 @@ std::vector<CTxMemPool::txiter> CTxMemPool::GatherClusters(const std::vector<uin } return clustered_txs; } + +std::optional<std::string> CTxMemPool::CheckConflictTopology(const setEntries& direct_conflicts) +{ + for (const auto& direct_conflict : direct_conflicts) { + // Ancestor and descendant counts are inclusive of the tx itself. + const auto ancestor_count{direct_conflict->GetCountWithAncestors()}; + const auto descendant_count{direct_conflict->GetCountWithDescendants()}; + const bool has_ancestor{ancestor_count > 1}; + const bool has_descendant{descendant_count > 1}; + const auto& txid_string{direct_conflict->GetSharedTx()->GetHash().ToString()}; + // The only allowed configurations are: + // 1 ancestor and 0 descendant + // 0 ancestor and 1 descendant + // 0 ancestor and 0 descendant + if (ancestor_count > 2) { + return strprintf("%s has %u ancestors, max 1 allowed", txid_string, ancestor_count - 1); + } else if (descendant_count > 2) { + return strprintf("%s has %u descendants, max 1 allowed", txid_string, descendant_count - 1); + } else if (has_ancestor && has_descendant) { + return strprintf("%s has both ancestor and descendant, exceeding cluster limit of 2", txid_string); + } + // Additionally enforce that: + // If we have a child, we are its only parent. + // If we have a parent, we are its only child. + if (has_descendant) { + const auto& our_child = direct_conflict->GetMemPoolChildrenConst().begin(); + if (our_child->get().GetCountWithAncestors() > 2) { + return strprintf("%s is not the only parent of child %s", + txid_string, our_child->get().GetSharedTx()->GetHash().ToString()); + } + } else if (has_ancestor) { + const auto& our_parent = direct_conflict->GetMemPoolParentsConst().begin(); + if (our_parent->get().GetCountWithDescendants() > 2) { + return strprintf("%s is not the only child of parent %s", + txid_string, our_parent->get().GetSharedTx()->GetHash().ToString()); + } + } + } + return std::nullopt; +} + +util::Result<std::pair<std::vector<FeeFrac>, std::vector<FeeFrac>>> CTxMemPool::CalculateFeerateDiagramsForRBF(CAmount replacement_fees, int64_t replacement_vsize, const setEntries& direct_conflicts, const setEntries& all_conflicts) +{ + Assume(replacement_vsize > 0); + + auto err_string{CheckConflictTopology(direct_conflicts)}; + if (err_string.has_value()) { + // Unsupported topology for calculating a feerate diagram + return util::Error{Untranslated(err_string.value())}; + } + + // new diagram will have chunks that consist of each ancestor of + // direct_conflicts that is at its own fee/size, along with the replacement + // tx/package at its own fee/size + + // old diagram will consist of each element of all_conflicts either at + // its own feerate (followed by any descendant at its own feerate) or as a + // single chunk at its descendant's ancestor feerate. + + std::vector<FeeFrac> old_chunks; + // Step 1: build the old diagram. + + // The above clusters are all trivially linearized; + // they have a strict topology of 1 or two connected transactions. + + // OLD: Compute existing chunks from all affected clusters + for (auto txiter : all_conflicts) { + // Does this transaction have descendants? + if (txiter->GetCountWithDescendants() > 1) { + // Consider this tx when we consider the descendant. + continue; + } + // Does this transaction have ancestors? + FeeFrac individual{txiter->GetModifiedFee(), txiter->GetTxSize()}; + if (txiter->GetCountWithAncestors() > 1) { + // We'll add chunks for either the ancestor by itself and this tx + // by itself, or for a combined package. + FeeFrac package{txiter->GetModFeesWithAncestors(), static_cast<int32_t>(txiter->GetSizeWithAncestors())}; + if (individual > package) { + // The individual feerate is higher than the package, and + // therefore higher than the parent's fee. Chunk these + // together. + old_chunks.emplace_back(package); + } else { + // Add two points, one for the parent and one for this child. + old_chunks.emplace_back(package - individual); + old_chunks.emplace_back(individual); + } + } else { + old_chunks.emplace_back(individual); + } + } + + // No topology restrictions post-chunking; sort + std::sort(old_chunks.begin(), old_chunks.end(), std::greater()); + std::vector<FeeFrac> old_diagram = BuildDiagramFromChunks(old_chunks); + + std::vector<FeeFrac> new_chunks; + + /* Step 2: build the NEW diagram + * CON = Conflicts of proposed chunk + * CNK = Proposed chunk + * NEW = OLD - CON + CNK: New diagram includes all chunks in OLD, minus + * the conflicts, plus the proposed chunk + */ + + // OLD - CON: Add any parents of direct conflicts that are not conflicted themselves + for (auto direct_conflict : direct_conflicts) { + // If a direct conflict has an ancestor that is not in all_conflicts, + // it can be affected by the replacement of the child. + if (direct_conflict->GetMemPoolParentsConst().size() > 0) { + // Grab the parent. + const CTxMemPoolEntry& parent = direct_conflict->GetMemPoolParentsConst().begin()->get(); + if (!all_conflicts.count(mapTx.iterator_to(parent))) { + // This transaction would be left over, so add to the NEW + // diagram. + new_chunks.emplace_back(parent.GetModifiedFee(), parent.GetTxSize()); + } + } + } + // + CNK: Add the proposed chunk itself + new_chunks.emplace_back(replacement_fees, int32_t(replacement_vsize)); + + // No topology restrictions post-chunking; sort + std::sort(new_chunks.begin(), new_chunks.end(), std::greater()); + std::vector<FeeFrac> new_diagram = BuildDiagramFromChunks(new_chunks); + return std::make_pair(old_diagram, new_diagram); +} diff --git a/src/txmempool.h b/src/txmempool.h index 32f2c024f7..9dd4d56da7 100644 --- a/src/txmempool.h +++ b/src/txmempool.h @@ -21,6 +21,7 @@ #include <util/epochguard.h> #include <util/hasher.h> #include <util/result.h> +#include <util/feefrac.h> #include <boost/multi_index/hashed_index.hpp> #include <boost/multi_index/identity.hpp> @@ -736,6 +737,28 @@ public: return m_sequence_number; } + /** + * Calculate the old and new mempool feerate diagrams relating to the + * clusters that would be affected by a potential replacement transaction. + * (replacement_fees, replacement_vsize) values are gathered from a + * proposed set of replacement transactions that are considered as a single + * chunk, and represent their complete cluster. In other words, they have no + * in-mempool ancestors. + * + * @param[in] replacement_fees Package fees + * @param[in] replacement_vsize Package size (must be greater than 0) + * @param[in] direct_conflicts All transactions that would be removed directly by + * having a conflicting input with a proposed transaction + * @param[in] all_conflicts All transactions that would be removed + * @return old and new diagram pair respectively, or an error string if the conflicts don't match a calculable topology + */ + util::Result<std::pair<std::vector<FeeFrac>, std::vector<FeeFrac>>> CalculateFeerateDiagramsForRBF(CAmount replacement_fees, int64_t replacement_vsize, const setEntries& direct_conflicts, const setEntries& all_conflicts) EXCLUSIVE_LOCKS_REQUIRED(cs); + + /* Check that all direct conflicts are in a cluster size of two or less. Each + * direct conflict may be in a separate cluster. + */ + std::optional<std::string> CheckConflictTopology(const setEntries& direct_conflicts); + private: /** UpdateForDescendants is used by UpdateTransactionsFromBlock to update * the descendants for a single transaction that has been added to the |