tx_memory_pool: speedup get_complement() for large requests
What the developer wrote
Authored by jeffro256
tx_memory_pool: speedup get_complement() for large requests
Changes complexity from M*N to (2*N+M)*log2(M). The FCMP++ stressnet recently hit mempool sizes of ~55k txs.
If the requesting node's mempool is populated, this results in an average of (55000*55000)/2
(about 1.5 billion) comparisons for the responding node. Under this commit, this would be reduced to
(55000+55000)*log2(55000) comparisons (about 2.6 million), a 99.83% reduction.
What changed, and why it matters
This commit is a performance optimization for Monero's transaction memory pool. When one node asks another for transactions it is missing, the old code compared every requested hash against every pool transaction one-by-one, which becomes extremely slow when the pool is large (tens of thousands of transactions). The new code sorts the requested hashes once and uses binary search, cutting the work by roughly 99.8%. The main security-relevant angle is that the old code could be abused to make a node waste CPU time, potentially contributing to a denial-of-service condition.
Treat this as a worthwhile hardening/performance fix. Consider pairing it with an upper bound on the number of hashes accepted in a txpool complement request and/or per-peer rate limiting, because the optimization removes the quadratic CPU blow-up but very large requests can still consume memory and bandwidth.
Security signals we found
Algorithmic-complexity reduction in a network-facing RPC/P2P path
Old O(N^2) behavior could be triggered by large mempool sizes and used to consume CPU on responding nodes
No input-size limits or rate limiting are added in this patch
No changes to validation, cryptography, or consensus rules
Evidence from the diff
The patch changes tx_memory_pool::get_complement() from an O(MN) linear scan to an O((2N+M)*log2(M)) algorithm by sorting the incoming hash vector and using std::lower_bound for each local pool transaction. It also adds lexicographic comparison operators (< and >) to crypto::hash so std::sort can order hashes. The signature is changed from const std::vector
Changed components
src/cryptonote_core/tx_pool.cppsrc/cryptonote_core/tx_pool.hsrc/cryptonote_core/cryptonote_core.cppsrc/cryptonote_core/cryptonote_core.hsrc/cryptonote_protocol/cryptonote_protocol_handler.inlsrc/crypto/hash.hInspect captured patch +18 / −8
diff --git a/src/crypto/hash.h b/src/crypto/hash.h
index f96e759..814c493 100644
--- a/src/crypto/hash.h
+++ b/src/crypto/hash.h
@@ -101,6 +101,9 @@ namespace crypto {
constexpr static crypto::hash null_hash = {};
constexpr static crypto::hash8 null_hash8 = {};
+
+ inline bool operator<(const hash &lhs, const hash &rhs) noexcept { return memcmp(&lhs, &rhs, sizeof(hash)) < 0; }
+ inline bool operator>(const hash &lhs, const hash &rhs) noexcept { return rhs < lhs; }
}
CRYPTO_MAKE_HASHABLE(hash)
diff --git a/src/cryptonote_core/cryptonote_core.cpp b/src/cryptonote_core/cryptonote_core.cpp
index 42fdc25..1acef46 100644
--- a/src/cryptonote_core/cryptonote_core.cpp
+++ b/src/cryptonote_core/cryptonote_core.cpp
@@ -1850,9 +1850,9 @@ namespace cryptonote
m_blockchain_storage.flush_invalid_blocks();
}
//-----------------------------------------------------------------------------------------------
- bool core::get_txpool_complement(const std::vector<crypto::hash> &hashes, std::vector<cryptonote::blobdata> &txes)
+ bool core::get_txpool_complement(std::vector<crypto::hash> hashes, std::vector<cryptonote::blobdata> &txes)
{
- return m_mempool.get_complement(hashes, txes);
+ return m_mempool.get_complement(std::move(hashes), txes);
}
//-----------------------------------------------------------------------------------------------
bool core::update_blockchain_pruning()
diff --git a/src/cryptonote_core/cryptonote_core.h b/src/cryptonote_core/cryptonote_core.h
index 763b7e1..999a98c 100644
--- a/src/cryptonote_core/cryptonote_core.h
+++ b/src/cryptonote_core/cryptonote_core.h
@@ -897,7 +897,7 @@ namespace cryptonote
*
* @return true iff success, false otherwise
*/
- bool get_txpool_complement(const std::vector<crypto::hash> &hashes, std::vector<cryptonote::blobdata> &txes);
+ bool get_txpool_complement(std::vector<crypto::hash> hashes, std::vector<cryptonote::blobdata> &txes);
/**
* @brief validates some simple properties of a transaction
diff --git a/src/cryptonote_core/tx_pool.cpp b/src/cryptonote_core/tx_pool.cpp
index c63465e..1655dfb 100644
--- a/src/cryptonote_core/tx_pool.cpp
+++ b/src/cryptonote_core/tx_pool.cpp
@@ -666,17 +666,24 @@ namespace cryptonote
return true;
}
//---------------------------------------------------------------------------------
- bool tx_memory_pool::get_complement(const std::vector<crypto::hash> &hashes, std::vector<cryptonote::blobdata> &txes) const
+ bool tx_memory_pool::get_complement(std::vector<crypto::hash> hashes, std::vector<cryptonote::blobdata> &txes) const
{
CRITICAL_REGION_LOCAL(m_transactions_lock);
CRITICAL_REGION_LOCAL1(m_blockchain);
+ // Sort so we can do binary search later
+ std::sort(hashes.begin(), hashes.end());
+
m_blockchain.for_all_txpool_txes([this, &hashes, &txes](const crypto::hash &txid, const txpool_tx_meta_t &meta, const cryptonote::blobdata_ref*) {
const auto tx_relay_method = meta.get_relay_method();
if (tx_relay_method != relay_method::block && tx_relay_method != relay_method::fluff)
return true;
- const auto i = std::find(hashes.begin(), hashes.end(), txid);
- if (i == hashes.end())
+
+ // Do binary search for our pool TXID in given list, skip to next if already present
+ const auto hash_it = std::lower_bound(hashes.cbegin(), hashes.cend(), txid);
+ if (hash_it != hashes.cend() && *hash_it == txid)
+ return true;
+
{
cryptonote::blobdata bd;
try
diff --git a/src/cryptonote_core/tx_pool.h b/src/cryptonote_core/tx_pool.h
index 1dbfd84..dd96ef7 100644
--- a/src/cryptonote_core/tx_pool.h
+++ b/src/cryptonote_core/tx_pool.h
@@ -493,7 +493,7 @@ namespace cryptonote
/**
* @brief get transactions not in the passed set
*/
- bool get_complement(const std::vector<crypto::hash> &hashes, std::vector<cryptonote::blobdata> &txes) const;
+ bool get_complement(std::vector<crypto::hash> hashes, std::vector<cryptonote::blobdata> &txes) const;
/**
* @brief get info necessary for update of pool-related info in a wallet, preferably incremental
diff --git a/src/cryptonote_protocol/cryptonote_protocol_handler.inl b/src/cryptonote_protocol/cryptonote_protocol_handler.inl
index 30b9b07..c40358b 100644
--- a/src/cryptonote_protocol/cryptonote_protocol_handler.inl
+++ b/src/cryptonote_protocol/cryptonote_protocol_handler.inl
@@ -863,7 +863,7 @@ namespace cryptonote
std::vector<cryptonote::blobdata> local_txs;
std::vector<cryptonote::blobdata> txes;
- if (!m_core.get_txpool_complement(arg.hashes, txes))
+ if (!m_core.get_txpool_complement(std::move(arg.hashes), txes))
{
LOG_ERROR_CCONTEXT("failed to get txpool complement");
return 1;
Why this scored 29/100
Community notes
Notes can correct, qualify, or add evidence to the AI analysis. Every note shown here has been validated by a human moderator.
The AI analysis stands alone for now. Submit a note if you can add evidence or important context.