[p2p] Introduce node rebroadcast module #21061

I’m importing this file so I can use the default key extractors in the indexed_rebroadcast_set multi_index: 1. https://github.com/bitcoin/bitcoin/pull/21061/files#diff-eccf6b88ae8b612dbdbdb92c110b66e4e7e3ffa665ccdc1acf08093aadc66b82R49 2. https://github.com/bitcoin/bitcoin/pull/21061/files#diff-eccf6b88ae8b612dbdbdb92c110b66e4e7e3ffa665ccdc1acf08093aadc66b82R55

The contents of the boost header file can be found here.

If we’d rather not import another boost header, I can avoid by writing custom key extractors.

Prefer default initialization when a member will always be initialized to the same value.

0    int m_count{1};

And remove m_count from the initializer list.

It seems unnecessary to define a type here. GetRebroadcastTransactions() could just return a vector of std::pairs, and the one caller (UpdatedBlockTip()) can unpack that vector of pairs using :sparkle: s t r u c t u t e d :sparkle: b i n d i n g s :sparkle:. Here’s what the caller would look like:

 0diff --git a/src/net_processing.cpp b/src/net_processing.cpp
 1index 7811e3ca40..e5a425b4c1 100644
 2--- a/src/net_processing.cpp
 3+++ b/src/net_processing.cpp
 4@@ -1393,12 +1393,12 @@ void PeerManagerImpl::UpdatedBlockTip(const CBlockIndex *pindexNew, const CBlock
 5 
 6     // Rebroadcast selected mempool transactions
 7     if (gArgs.GetArg("-rebroadcast", DEFAULT_REBROADCAST_ENABLED)) {
 8-        std::vector<TxIds> rebroadcast_txs = m_txrebroadcast.GetRebroadcastTransactions();
 9+        auto rebroadcast_txs = m_txrebroadcast.GetRebroadcastTransactions();
10 
11         LOCK(cs_main);
12 
13-        for (auto ids : rebroadcast_txs) {
14-            RelayTransaction(ids.m_txid, ids.m_wtxid, m_connman);
15+        for (auto [txid, wtxid] : rebroadcast_txs) {
16+            RelayTransaction(txid, wtxid, m_connman);
17         }
18     }

That client code works whether you return a vector of TxIds or a vector of std::pair<uint256, uint256>>s (which is as it should be :slightly_smiling_face: )

Perhaps make this a unique_ptr, and then pass in a boolean to the PeerManagerImpl ctor to indicate whether you want to enable tx rebroadcast and initialize the pointer.

Then, in UpdatedBlockTip:

 0diff --git a/src/net_processing.cpp b/src/net_processing.cpp
 1index 7811e3ca40..8bb5e8f87f 100644
 2--- a/src/net_processing.cpp
 3+++ b/src/net_processing.cpp
 4@@ -1392,8 +1392,8 @@ void PeerManagerImpl::UpdatedBlockTip(const CBlockIndex *pindexNew, const CBlock
 5     }
 6 
 7     // Rebroadcast selected mempool transactions
 8-    if (gArgs.GetArg("-rebroadcast", DEFAULT_REBROADCAST_ENABLED)) {
 9-        std::vector<TxIds> rebroadcast_txs = m_txrebroadcast.GetRebroadcastTransactions();
10+    if (m_txrebroadcast) {
11+        std::vector<TxIds> rebroadcast_txs = m_txrebroadcast->GetRebroadcastTransactions();
12 
13         LOCK(cs_main);

parametrizing whether the TxRebroadcastHandler is initialized avoids having to read the global args every block, and should make it the code path more obviously isolated and testable.

Separate library imports from local project imports:

0#include <boost/test/unit_test.hpp>
1
2#include <amount.h>

Yes, that’s the right way to do it.

I don’t think we have any guidance in the style guide, but general best practice seems to be to go from small to large: https://stackoverflow.com/a/2762596/933705.

A quick and easy way to do this is to make indexed_rebroadcast_set a class that inherits from the boost::multi_index_container template class (defined in .cpp), forward declare it in .h and make m_attempt_tracker a unique pointer to indexed_rebroadcast_set. A few other things need to be shuffled around to make that work, but here’s a rough implementation:

  0diff --git a/src/test/txrebroadcast_tests.cpp b/src/test/txrebroadcast_tests.cpp
  1index 6fdd5deb8f..d10a962ab3 100644
  2--- a/src/test/txrebroadcast_tests.cpp
  3+++ b/src/test/txrebroadcast_tests.cpp
  4@@ -27,34 +27,13 @@ public:
  5 
  6     bool CheckRecordedAttempt(uint256 txhsh, int expected_count, std::chrono::microseconds expected_timestamp)
  7     {
  8-        const auto it = m_attempt_tracker.find(txhsh);
  9-        if (it == m_attempt_tracker.end()) return false;
 10-        if (it->m_count != expected_count) return false;
 11-
 12-        // Check the recorded timestamp is within 2 seconds of the param passed in
 13-        std::chrono::microseconds delta = expected_timestamp - it->m_last_attempt;
 14-        if (delta.count() > 2) return false;
 15-
 16-        return true;
 17-    };
 18+        return TxRebroadcastHandler::CheckRecordedAttempt(txhsh, expected_count, expected_timestamp);
 19+    }
 20 
 21     void UpdateAttempt(uint256 txhsh, int count)
 22     {
 23-        auto it = m_attempt_tracker.find(txhsh);
 24-        for (int i = 0; i < count; ++i) {
 25-            RecordAttempt(it);
 26-        }
 27-    };
 28-
 29-    void RecordAttempt(indexed_rebroadcast_set::index<index_by_wtxid>::type::iterator& entry_it)
 30-    {
 31-        auto UpdateRebroadcastEntry = [](RebroadcastEntry& rebroadcast_entry) {
 32-            rebroadcast_entry.m_last_attempt = GetTime<std::chrono::microseconds>() - 4h;
 33-            ++rebroadcast_entry.m_count;
 34-        };
 35-
 36-        m_attempt_tracker.modify(entry_it, UpdateRebroadcastEntry);
 37-    };
 38+        TxRebroadcastHandler::UpdateAttempt(txhsh, count);
 39+    }
 40 
 41     void UpdateCachedFeeRate(CFeeRate new_fee_rate)
 42     {
 43diff --git a/src/txrebroadcast.cpp b/src/txrebroadcast.cpp
 44index 3cb9abaf69..49050c0d39 100644
 45--- a/src/txrebroadcast.cpp
 46+++ b/src/txrebroadcast.cpp
 47@@ -10,6 +10,11 @@
 48 #include <txrebroadcast.h>
 49 #include <validation.h>
 50 
 51+#include <boost/multi_index/hashed_index.hpp>
 52+#include <boost/multi_index/member.hpp>
 53+#include <boost/multi_index/ordered_index.hpp>
 54+#include <boost/multi_index_container.hpp>
 55+
 56 /** We rebroadcast 3/4 of max block weight to reduce noise due to circumstances
 57  *  such as miners mining priority transactions. */
 58 static constexpr unsigned int MAX_REBROADCAST_WEIGHT = 3 * MAX_BLOCK_WEIGHT / 4;
 59@@ -30,6 +35,46 @@ static constexpr int MAX_ENTRIES = 500;
 60 /** The maximum age of an entry ~3 months */
 61 static constexpr std::chrono::hours MAX_ENTRY_AGE = std::chrono::hours(3 * 30 * 24);
 62 
 63+/** Used for multi_index tag  */
 64+struct index_by_last_attempt {};
 65+
 66+struct RebroadcastEntry {
 67+    RebroadcastEntry(std::chrono::microseconds now_time, uint256 wtxid)
 68+        : m_last_attempt(now_time),
 69+          m_wtxid(wtxid),
 70+          m_count(1) {}
 71+
 72+    std::chrono::microseconds m_last_attempt;
 73+    const uint256 m_wtxid;
 74+    int m_count;
 75+};
 76+
 77+class indexed_rebroadcast_set : public
 78+boost::multi_index_container<
 79+    RebroadcastEntry,
 80+    boost::multi_index::indexed_by<
 81+        // sorted by wtxid
 82+        boost::multi_index::hashed_unique<
 83+            boost::multi_index::tag<index_by_wtxid>,
 84+            boost::multi_index::member<RebroadcastEntry, const uint256, &RebroadcastEntry::m_wtxid>,
 85+            SaltedTxidHasher
 86+        >,
 87+        // sorted by last rebroadcast time
 88+        boost::multi_index::ordered_non_unique<
 89+            boost::multi_index::tag<index_by_last_attempt>,
 90+            boost::multi_index::member<RebroadcastEntry, std::chrono::microseconds, &RebroadcastEntry::m_last_attempt>
 91+        >
 92+    >
 93+> {};
 94+
 95+TxRebroadcastHandler::TxRebroadcastHandler(CTxMemPool& mempool, ChainstateManager& chainman)
 96+    : m_attempt_tracker{std::make_unique<indexed_rebroadcast_set>()}
 97+    , m_mempool{mempool}
 98+    , m_chainman{chainman}
 99+{}
100+
101+TxRebroadcastHandler::~TxRebroadcastHandler() = default;
102+
103 std::vector<TxIds> TxRebroadcastHandler::GetRebroadcastTransactions()
104 {
105     std::vector<TxIds> rebroadcast_txs;
106@@ -58,12 +103,12 @@ std::vector<TxIds> TxRebroadcastHandler::GetRebroadcastTransactions()
107 
108         // Check if we have previously rebroadcasted, decide if we will this
109         // round, and if so, record the attempt.
110-        auto entry_it = m_attempt_tracker.find(wtxid);
111+        auto entry_it = m_attempt_tracker->find(wtxid);
112 
113-        if (entry_it == m_attempt_tracker.end()) {
114+        if (entry_it == m_attempt_tracker->end()) {
115             // No existing entry, we will rebroadcast, so create a new one
116             RebroadcastEntry entry(start_time, wtxid);
117-            m_attempt_tracker.insert(entry);
118+            m_attempt_tracker->insert(entry);
119         } else if (entry_it->m_count >= MAX_REBROADCAST_COUNT) {
120             // We have already rebroadcast this transaction the maximum number
121             // of times permitted, so skip rebroadcasting.
122@@ -76,7 +121,12 @@ std::vector<TxIds> TxRebroadcastHandler::GetRebroadcastTransactions()
123         } else {
124             // We have rebroadcasted this transaction before, but will try
125             // again now.
126-            RecordAttempt(entry_it);
127+            auto UpdateRebroadcastEntry = [](RebroadcastEntry& rebroadcast_entry) {
128+                rebroadcast_entry.m_last_attempt = GetTime<std::chrono::microseconds>();
129+                ++rebroadcast_entry.m_count;
130+            };
131+
132+            m_attempt_tracker->modify(entry_it, UpdateRebroadcastEntry);
133         }
134 
135         // Add to set of rebroadcast candidates
136@@ -97,6 +147,32 @@ std::vector<TxIds> TxRebroadcastHandler::GetRebroadcastTransactions()
137     return rebroadcast_txs;
138 };
139 
140+void TxRebroadcastHandler::UpdateAttempt(uint256 txhsh, int count)
141+{
142+    auto it = m_attempt_tracker->find(txhsh);
143+    for (int i = 0; i < count; ++i) {
144+        auto UpdateRebroadcastEntry = [](RebroadcastEntry& rebroadcast_entry) {
145+            rebroadcast_entry.m_last_attempt = GetTime<std::chrono::microseconds>() - 4h;
146+            ++rebroadcast_entry.m_count;
147+        };
148+
149+        m_attempt_tracker->modify(it, UpdateRebroadcastEntry);
150+    }
151+};
152+
153+bool TxRebroadcastHandler::CheckRecordedAttempt(uint256 txhsh, int expected_count, std::chrono::microseconds expected_timestamp)
154+{
155+    const auto it = m_attempt_tracker->find(txhsh);
156+    if (it == m_attempt_tracker->end()) return false;
157+    if (it->m_count != expected_count) return false;
158+
159+    // Check the recorded timestamp is within 2 seconds of the param passed in
160+    std::chrono::microseconds delta = expected_timestamp - it->m_last_attempt;
161+    if (delta.count() > 2) return false;
162+
163+    return true;
164+};
165+
166 void TxRebroadcastHandler::CacheMinRebroadcastFee()
167 {
168     // Update stamp of chain tip on cache run
169@@ -109,33 +185,23 @@ void TxRebroadcastHandler::CacheMinRebroadcastFee()
170     LogPrint(BCLog::BENCH, "Caching minimum fee for rebroadcast to %s, took %d µs to calculate.\n", m_cached_fee_rate.ToString(FeeEstimateMode::SAT_VB), delta_time.count());
171 };
172 
173-void TxRebroadcastHandler::RecordAttempt(indexed_rebroadcast_set::index<index_by_wtxid>::type::iterator& entry_it)
174-{
175-    auto UpdateRebroadcastEntry = [](RebroadcastEntry& rebroadcast_entry) {
176-        rebroadcast_entry.m_last_attempt = GetTime<std::chrono::microseconds>();
177-        ++rebroadcast_entry.m_count;
178-    };
179-
180-    m_attempt_tracker.modify(entry_it, UpdateRebroadcastEntry);
181-};
182-
183 void TxRebroadcastHandler::TrimMaxRebroadcast()
184 {
185     // Delete any entries that are older than MAX_ENTRY_AGE
186     std::chrono::microseconds min_age = GetTime<std::chrono::microseconds>() - MAX_ENTRY_AGE;
187 
188-    while (!m_attempt_tracker.empty()) {
189-        auto it = m_attempt_tracker.get<index_by_last_attempt>().begin();
190+    while (!m_attempt_tracker->empty()) {
191+        auto it = m_attempt_tracker->get<index_by_last_attempt>().begin();
192         if (it->m_last_attempt < min_age) {
193-            m_attempt_tracker.get<index_by_last_attempt>().erase(it);
194+            m_attempt_tracker->get<index_by_last_attempt>().erase(it);
195         } else {
196             break;
197         }
198     }
199 
200     // If there are still too many entries, delete the oldest ones
201-    while (m_attempt_tracker.size() > MAX_ENTRIES) {
202-        auto it = m_attempt_tracker.get<index_by_last_attempt>().begin();
203-        m_attempt_tracker.get<index_by_last_attempt>().erase(it);
204+    while (m_attempt_tracker->size() > MAX_ENTRIES) {
205+        auto it = m_attempt_tracker->get<index_by_last_attempt>().begin();
206+        m_attempt_tracker->get<index_by_last_attempt>().erase(it);
207     }
208 };
209diff --git a/src/txrebroadcast.h b/src/txrebroadcast.h
210index 8a176a08bc..ec3ea34ed7 100644
211--- a/src/txrebroadcast.h
212+++ b/src/txrebroadcast.h
213@@ -12,11 +12,6 @@
214 #include <util/time.h>
215 #include <validation.h>
216 
217-#include <boost/multi_index/hashed_index.hpp>
218-#include <boost/multi_index/member.hpp>
219-#include <boost/multi_index/ordered_index.hpp>
220-#include <boost/multi_index_container.hpp>
221-
222 struct TxIds {
223     TxIds(uint256 txid, uint256 wtxid) : m_txid(txid), m_wtxid(wtxid) {}
224 
225@@ -24,43 +19,15 @@ struct TxIds {
226     const uint256 m_wtxid;
227 };
228 
229-struct RebroadcastEntry {
230-    RebroadcastEntry(std::chrono::microseconds now_time, uint256 wtxid)
231-        : m_last_attempt(now_time),
232-          m_wtxid(wtxid),
233-          m_count(1) {}
234-
235-    std::chrono::microseconds m_last_attempt;
236-    const uint256 m_wtxid;
237-    int m_count;
238-};
239-
240-/** Used for multi_index tag  */
241-struct index_by_last_attempt {};
242-
243-using indexed_rebroadcast_set = boost::multi_index_container<
244-    RebroadcastEntry,
245-    boost::multi_index::indexed_by<
246-        // sorted by wtxid
247-        boost::multi_index::hashed_unique<
248-            boost::multi_index::tag<index_by_wtxid>,
249-            boost::multi_index::member<RebroadcastEntry, const uint256, &RebroadcastEntry::m_wtxid>,
250-            SaltedTxidHasher
251-        >,
252-        // sorted by last rebroadcast time
253-        boost::multi_index::ordered_non_unique<
254-            boost::multi_index::tag<index_by_last_attempt>,
255-            boost::multi_index::member<RebroadcastEntry, std::chrono::microseconds, &RebroadcastEntry::m_last_attempt>
256-        >
257-    >
258->;
259+class indexed_rebroadcast_set;
260 
261 class TxRebroadcastHandler
262 {
263 public:
264-    TxRebroadcastHandler(CTxMemPool& mempool, ChainstateManager& chainman)
265-        : m_mempool(mempool),
266-          m_chainman(chainman){};
267+    TxRebroadcastHandler(CTxMemPool& mempool, ChainstateManager& chainman);
268+    ~TxRebroadcastHandler();
269+
270+    TxRebroadcastHandler(const TxRebroadcastHandler& other) = delete;
271 
272     std::vector<TxIds> GetRebroadcastTransactions();
273 
274@@ -75,10 +42,13 @@ protected:
275     CFeeRate m_cached_fee_rate;
276 
277     /** Keep track of previous rebroadcast attempts */
278-    indexed_rebroadcast_set m_attempt_tracker;
279+    std::unique_ptr<indexed_rebroadcast_set> m_attempt_tracker;
280+
281+    /** Test only */
282+    void UpdateAttempt(uint256 txhsh, int count);
283 
284-    /** Update an existing RebroadcastEntry - increment count and update timestamp */
285-    void RecordAttempt(indexed_rebroadcast_set::index<index_by_wtxid>::type::iterator& entry_it);
286+    /** Test only */
287+    bool CheckRecordedAttempt(uint256 txhsh, int expected_count, std::chrono::microseconds expected_timestamp);
288 
289 private:
290     const CTxMemPool& m_mempool;

Not currently, but I think a long-term it’d be good to remove the boost header dependencies from modules that aren’t using boost multi_index. That’d involve refactoring the txmempool interface so it’s not exposing multi_index objects.

To be honest, I’m not entirely sure how much actual benefit this would have on build times and binary size. I think that boost multi_index is almost entirely templates, so if they’re not being instantiated in a translation unit, then it’s probably minimal. Still, I think it’s a good goal in itself to minimize where third party libraries are exposed within our code structure.

Could keep the old cached fee rate here, so that if you try end up doing UpdateTip / CacheMinRebroadcastFee / RebroadcatTxs you can do something sensible?

0   new_tip = ::ChainActive().Tip();
1   if (new_tip != m_tip_at_cache_time) {
2       m_last_cached_fee_rate = m_cached_fee_rate;
3   } else {
4       m_last_cached_fee_rate = max; // ?
5   }
6   m_tip_at_cache_time = new_tip;

Other cases:

• tx was RBFed out of mempool
• parents were invalidated by conflicting tx in mempool and/or block

~I think it boils down to = if we aren’t keeping the tx in mempool, don’t keep it in the rebroadcast tracker.~ I totally misunderstood, I thought you wouldn’t want a tx in rebroadcast tracker if you didn’t have it in mempool, but actually you’d want to keep it for a bit.

Removing entries from m_attempt_tracker when tx is removed from mempool doesn’t seem necessary given m_attempt_tracker isn’t used as a source for txs that need to be rebroadcasted.

I also don’t see an issue with keeping txs that have already been included in a block or RBFed out of mempool in the m_attempt_tracker for up to 90 days (as per current setting) or till it gets removed after 500 limit is reached. Removing these entries from m_attempt_tracker would add unnecessary complexity for a small benefit of a little saved memory as far as I understand. On that note, would perhaps removing the 90 days limit and just keeping the 500 limit still be fine?

Removing entries from m_attempt_tracker when tx is removed from mempool doesn’t seem necessary given m_attempt_tracker isn’t used as a source for txs that need to be rebroadcasted.

I agree that rebroadcast would still work - the problem is more that m_attempt_tracker might not be able to fulfill its intended purpose with a 500 limit if it was keeping track of too many unnecessary transactions (and at the same time expel those that it was meant to keep track off after capacity is reached).

We’re trying to get rid of global calls like Params(). Consider adding a:

0    const CChainParams& m_chainparams;

member to TxRebroadcastHandler and setting it in the ctor (like PeerManagerImpl does)

The type is obvious from the template parameter, so may be a good place to use auto:

0    auto start_time = GetTime<std::chrono::microseconds>();

(and in the other calls to GetTime)

Functions should be capitalized:

0    CFeeRate MinTxFeeRate();

again, maybe avoid greek letters:

0    LogPrint(BCLog::BENCH, "Caching minimum fee for rebroadcast to %s, took %d us to calculate.\n", m_cached_fee_rate.ToString(FeeEstimateMode::SAT_VB), delta_time.count());

min_package_fee_rate seems very cheap to calculate. Perhaps just make it a reference so it’s always returned.

(even better would be:

0std::tuple<int, int, CFeeRate> BlockAssembler::addPackageTxs()

but that’s maybe beyond the scope of this PR)

agree that updating min_package_fee_rate is pretty cheap, there’s no additional calculation, its just updating the stored value, but might do so up to ~once per mempool transaction.

but can you help me understand the context of why you’re suggesting a reference? even if it’s not a lot of calculation, seems unnecessary?

(agree that returning a tuple instead of in/out params would be nice. but leaving other params as is within this PR.)

y so verbose?

0static constexpr std::chrono::hours MAX_ENTRY_AGE = 24h * 30 * 3;

RE oldest vs random: since the attempt tracker updates the timestamp every time a transaction is selected as a candidate for rebroadcast, it makes sense to me that the least relevant would be ones that haven’t been selected for the longest time. usually we use randomness in p2p data structures to ensure that a malicious peer cannot have disproportionate influence, which I don’t think quite applies here. its possible that a peer could roll the attempt tracker, but they would also have to roll filterInventoryKnown in order to spend actual network bandwidth. I haven’t thought this through in great depth, so let me know if I’m missing some reasons why we should consider randomizing.

RE configurable: as sipa mentioned in #21061 (comment), “generally the criterion for deciding whether a parameter should be configurable is whether you can also give advice under which cases users should be changing it, and how.” I am also sensitive to introducing configurable params because it increases the maintenance burden of the project essentially forever. Do you see use cases of how you would recommend users to adjust the attempt tracker? The main reason I’d imagine for wanting a larger tracker is to reduce bandwidth, but in that case I think a “turn rebroadcast off” toggle would make more sense (and of this PR its off by default)

In 06890651027cc50bdf3897283386a973bbf55725 “[mining] Add recency condition on block creation to get rebroadcast set”

This comment could be clearer as m_skip_inclusion_until isn’t really an age. Rather we exclude any transactions that entered the mempool after the time specified by m_skip_inclusion_until.

Used this suggested wording & updated to:

0      * If m_skip_inclusion_until is set in the options, we will exclude any
1      * transactions that entered the mempool after the time specified. This is
2      * currently used for rebroadcast logic. */

In 8b4db051bac56cefa8c85fe20e5548ddfab0f070 “[rebroadcast] Apply a fee rate filter”

I’m having a hard time understanding how this comment explains the condition here. Could you explain in more detail?

you’re right, this comment is really confusing. updated to:

0    // If the cache has run since we received the last block, the fee rate
1    // condition will not filter out any transactions, so skip this run.

And here’s some more explanation:

Let’s refer to the fee rate for a txn to be in the top MAX_REBROADCAST_WEIGHT as top-of-mempool fee rate. The only event that has the ability to decrease the top-of-mempool fee rate is a block being mined. Otherwise, as transactions enter the mempool, the top-of-mempool fee rate either stays the same or increases.

If the top-of-mempool fee rate is only increasing over time, the fee rate cache would not help filter any transactions out.

Our desired order is: cache | block | rebroadcast, with the delta between cache & block to be as small as possible.

The order we want to skip is: block | cache | rebroadcast, because then the fee rate filter will be meaningless, and would simply select the next highest transactions to rebroadcast (which we logically wouldn’t expect to be mined yet).

Does this make sense? Does the update to the comment help clarify? I’m not sure the best way to capture this in the code, so open to suggestions.

In d579110263ad07386f1fbf796a3397a12340b6d5 “[test] Add unit test for rebroadcast attempt logic”

It seems like this for loop is not necessary as it is essentially doing m_count += count. Could instead be:

0    auto UpdateRebroadcastEntry = [last_attempt_time, count](RebroadcastEntry& rebroadcast_entry) {
1        rebroadcast_entry.m_last_attempt = last_attempt_time;
2        rebroadcast_entry.m_count += count;
3    };
4
5    m_attempt_tracker->modify(it, UpdateRebroadcastEntry);

In d579110263ad07386f1fbf796a3397a12340b6d5 “[test] Add unit test for rebroadcast attempt logic”

It seems a bit odd to me that this function is supposed to be a wrapper but it also implements a little bit of test logic in that it changes the recorded last attempt time. I think it would make more sense to have the main test logic calculate the timestamp change and make this function a pure wrapper (or perhaps remove the entire class).

In 0f13d876977d6a83549fa40f68a73308ba10d95d “[test] Add unit test for the fee rate cache”

Seems like this change should be part of the previous commit.

In 0f13d876977d6a83549fa40f68a73308ba10d95d “[test] Add unit test for the fee rate cache”

Seems like this change should be part of the previous commit.

In 7005767691005f66e7e08ec2e575d436dae3be47 “[test] Functional tests for rebroadcast logic.”

0# Copyright (c) 2021 The Bitcoin Core developers

In 7005767691005f66e7e08ec2e575d436dae3be47 “[test] Functional tests for rebroadcast logic.”

getrawtransaction can decode txs too.

0        raw_tx = node.getrawtransaction(input_tx_hsh, True)

In 7005767691005f66e7e08ec2e575d436dae3be47 “[test] Functional tests for rebroadcast logic.”

It would be nice to not require the wallet for a p2p test.

IIUC the purpose of this variable, we assume miners’s mempools to be composed in average of 1/4 of irreplaceable transactions. I.e transactions even if we know better feerate candidates, we won’t be able to replace them as their scores are unduly increased by miner’s mempool policy.

Intuitively, this sounds a lot, do you have any real-world data backing up this assumption ? One could look on how many mined block transactions are under the local node MinTxFeeRate you’ve introduced to determine the size of the surprise set.

What’s the trade-off of picking a value deviating from real-world data ? Well I think you may prevent or delay rebroadcast of transactions in the bottom quarter of block feerate. Due to this delay, broadcasting clients of those transactions may reach a fee-bumping timer and they trigger a RBF/CPFP in consequence. As such bleeding feerate beyond what would have been effective to get into block templates.

If the risk I’m describing is founded, do you think we should preserve transactions broadcaster’s feerate instead of network nodes’ bandwidth ? I’m leaning toward a yes as rebroadcast logic is at least opt-in, but broadcaster won’t be aware of their peers’s policies barring propagation of their good-enough feerate transaction.

Let’s say an attacker partitions a victim’s mempool from the rest of network mempools thanks to maliciously conflicting transactions. E.g send non-rbf signaling, differing transactions to victim and all its tx-relay connected peers.

Those malicious transactions are attached a feerate high-enough to completely occupy the m_attempt_tracker. Due to MIN_REATTEMPT_INTERVAL=4h and assuming 6 blocks per hour, it will require 6 * 4 * 500 = 12000 transactions to jam victim’s rebroadcast attempt. Of course, MAX_REBROADCAST_COUNT should upper bound such behavior, but an attacker can easily renew m_attempt_tracker jamming by RBFing the pinning transactions.

Let’s assume malicious transactions size is MIN_STANDARD_TX_NONWITNESS_SIZE, so 82 bytes. Let’s assume top block feerate is 170 sat/vbyte. Shrugging at RBF replacement fee penalties, 12_000 * 82 * 170 = 167_280_000 sats. So a permanent m_attempt_tracker jamming would require 1,67 BTC available to the attacker, though not burnt if the mempool isolation is operated properly.

Do the attack model seems sound to you ? If so I think we should carefully document risks of m_attempt_tracker pinning and likely scale up parameters value.

what is the fundamental resource that is being spent in this attack? are you evaluating the possibility of asymmetric bandwidth usage? if that’s the case then you also need to factor in rolling over filterInventoryKnown.

also I don’t understand how the attacker avoids spending any funds- say A and A’ are two versions of the same txn via RBF. A is sent to the victim & A’ is sent to the rest of the network. according to the current patch, if A’ gets mined into a block, A is removed from the attempt tracker.

update: wait, you refer to the bandwidth interactions with filterInventoryKnown in your comment #21061 (review), so then I must be missing what you are trying to describe in this attack.

second update: is an assumption behind this hypothetical attack that jamming m_attempt_tracker would prevent a node from rebroadcasting? just want to clarify that rebroadcasts would work without the tracker, its mainly a technique to mitigate bandwidth usage.

Thanks for the second clarifying update, effectively this is documented L124 in src/txrebroadcast.cpp, “No existing entry, we will rebroadcast, so create new one”.

So IIUC, even if m_attempt_tracker is fulfilled with pinning transactions, it won’t block node rebroadcast capability. I think pinning costs of m_attempt_tracker above roughly above but it can’t be abused by an attacker to jam rebroadcasting, so we’re good.

I would recommend to document this “pinning-doesn’t-block-rebroadcast-so-not-a-new-tx-relay jamming-vector” around m_attempt_tracker declaration in src/txreconciliation.h, it’s quite an important design aspect imo.

W.r.t to asymmetric bandwidth usage and risks of bleeding, I don’t think m_attempt_tracker pinning is making it better or worst, I share the opinion we’re ultimately protected by filterInventoryKnown.

I don’t understand how the attacker avoids spending any funds- say A and A’ are two versions of the same txn via RBF. A is sent to the victim & A’ is sent to the rest of the network. according to the current patch, if A’ gets mined into a block, A is removed from the attempt tracker.

I should have precise this point. Transaction A feerate to successfully pin m_attempt_tracker must be at 170 sat/vbyte. However transaction A’ feerate just need to be above miners’mempools min feerates to block propagation of transaction A. If transaction A’ feerate is 2 sat/vbyte, with same equation laid out above, effective pinning cost for an attacker is 12_000 * 82 * 2 = 1_968_000 sats and not 167_280_000 sats. Miners observe and eventually mine transactions with a far lower-feerate than the ones maliciously sent to non-miner nodes. This is what I meant by “not burnt if the mempool isolation is operated properly”.

So IIUC, even if m_attempt_tracker is fulfilled with pinning transactions, it won’t block node rebroadcast capability.

yeah, exactly.

I would recommend to document this “pinning-doesn’t-block-rebroadcast-so-not-a-new-tx-relay jamming-vector” around m_attempt_tracker declaration in src/txreconciliation.h, it’s quite an important design aspect imo.

I don’t think it makes sense to document what data structures don’t do.

I should have precise this point…

Ah I understand now, thanks for clarifying.

Assuming an entry’s m_count reaches MAX_REBROADCAST_COUNT, it should never be again selected by GetRebroadcastTransactions. At that point, should we return an event to the wallet logic inviting to RBF the transaction ?

Otherwise, the entry should stale until deletion by TrimMaxRebroadcast. At that point should we return an event inviting to re-submit the same transaction ? Network mempools might have cleared up in between.

I don’t know if this new rebroadcasting mechanism should be transparent or not to Bitcoin applications vetted with their own rebroadcasting logics.

At that point, should we return an event to the wallet logic inviting to RBF the transaction ?

that’s a cool idea. I don’t think it is applicable yet, but I’ve noted it down for future work where it would be more relevant.

why I don’t think it is applicable yet: as of this patch, ResendWalletTransactions still calls SubmitMemoryPoolAndRelay with the relay bool set to true (aka patch doesn’t change it). This gets used in BroadcastTransaction to force relaying the transaction to peers at the time of submission. in the future, the goal is to disable this (see “Merge Plan & Next Steps” in #21061 (comment)), at which time I believe this sort of mechanism would make sense.

What’s the rational to pick up this value ?

I don’t think Bitcoin applications care about confirmation of transactions broadcast 3 months ago. At the contrary, an attacker could use this really long expiration delay as a fingerprint vector.

Let’s say in optimistic scenarios, a rebroadcast entry has a compelling feerate enough to be selected by GetRebroadcastTransactions after each MIN_REATTEMPT_INTERVAL, after 6 * 4, it’s matured enough to be legitimately expired ? Of course, we can assume some margin of error and double to 48h. Or even select MEMPOOL_EXPIRY as a maximum age. But I don’t understand the month-length delay…

I don’t understand this comment, let me explain some of the mechanisms incase that helps. otherwise, please help me understand what you are trying to communicate.

I don’t think Bitcoin applications care about confirmation of transactions broadcast 3 months ago.

1. the attempt tracker records the timestamp of when the mempool transaction was last selected for rebroadcast, not when it was initially broadcast / ATMPed (see https://github.com/bitcoin/bitcoin/pull/21061/files?file-filters%5B%5D=.cpp&file-filters%5B%5D=.h&file-filters%5B%5D=.py&file-filters%5B%5D=.sh#diff-7dff50848db96bdb8edffc4d21daeca6d9050ec0e67d96072780ea5751e7df06R110 and https://github.com/bitcoin/bitcoin/pull/21061/files?file-filters%5B%5D=.cpp&file-filters%5B%5D=.h&file-filters%5B%5D=.py&file-filters%5B%5D=.sh#diff-7dff50848db96bdb8edffc4d21daeca6d9050ec0e67d96072780ea5751e7df06R125).
2. MAX_ENTRY_AGE is only called from TrimMaxRebroadcast. It is essentially used to say “if a transaction hasn’t been selected for rebroadcast in the past 3 months, remove it from the attempt tracker”

Let’s say in optimistic scenarios, a rebroadcast entry has a compelling feerate enough to be selected by GetRebroadcastTransactions after each MIN_REATTEMPT_INTERVAL, after 6 * 4, it’s matured enough to be legitimately expired ?

can you clarify what you mean by “legitimately expired”? if you mean that we should disable automatic rebroadcast so the txn can (probably) expire from the (majority of) network mempools, then yes I agree. which is why we put it on the tracker. but then, what is the question?

select MEMPOOL_EXPIRY as a maximum age.

if we stored transactions on the attempt tracker for the same duration as MEMPOOL_EXPIRY time, that would leave room for the issue that the attempt tracker is meant to address. for more explanation on that, please see https://github.com/amitiuttarwar/bitcoin-notes/blob/main/rebroadcast-history.md#faq section “What happens if a transaction can / will never be mined?”. expiry would be one of the main ways to get the ping-ponging behavior for never-going-to-be-mined transactions (eg. due to a policy upgrade on the network).

IIRC, by “legitimately expired” I meant a transaction of which m_count has reached MAX_REBROADCAST_COUNT. As we already rebroadcasted this transaction the maximum number of times permitted, we skip its rebroadcasting forever, but without necessarily removing it from m_attempt_tracker ? I think such transaction has exhausted its rebroadcast “credit” and it’s mature enough to be “legitimately” expired or pruned. Though this deletion criteria isn’t currently considered in TrimMaxRebroadcast() ?

I think this deletion criteria would be more efficient to expire transactions from the majority of network mempools rather than MAX_ENTRY_AGE, especially with a 3 months delay.

if we stored transactions on the attempt tracker for the same duration as MEMPOOL_EXPIRY time, that would leave room for the issue that the attempt tracker is meant to address. for more explanation on that, please see https://github.com/amitiuttarwar/bitcoin-notes/blob/main/rebroadcast-history.md#faq section “What happens if a transaction can / will never be mined?”. expiry would be one of the main ways to get the ping-ponging behavior for never-going-to-be-mined transactions (eg. due to a policy upgrade on the network)

IIUC, the problem we’re trying to solve is “How to avoid never-going-to-be-mined transactions to forever ping-pong across the network ?”.

To achieve this aim, I believe we should expire a rebroadcast entry as soon as it has exhausted its rebroadcast count, a hint that either feerate is definitively aloof or severer circumstances as described in documentation. But selecting a MAX_ENTRY_AGE superior to MEMPOOL_EXPIRY moves in the opposite direction.

If rebroadcast entry average rebroadcast interval is superior to 56 hours, 56 * MAX_REBROADCAST_COUNT== MEMPOOL_EXPIRY and node rebroadcast guarantees attempts beyond the mempool expiration limit ?

Or is the behavior I’m describing not possible ? I’m happy to illustrate with a test to assert our intuitions :)

update: Or is the purpose of keeping rebroadcast entry with m_count == MAX_REBROADCAST_COUNT and only expire them when last_attempt is older than MAX_ENTRY_AGE prevent new registration in m_attempt_tracker cache provoked by rebroadcast from other network mempools ? Thus you expect a transaction to expire from mempools after MEMPOOL_EXPIRY, then to avoid network laggards with differing policy to trigger new rebroadcasting wawes, you have MAX_ENTRY_AGE as an upper bound of MEMPOOL_EXPIRY ?

Okay I can see how it solves mempool ping-pong though reasoning could be better documented and still we should envisage to reduce MAX_ENTRY_AGE to minimize node fingerprinting.

it seems like the majority of this comment is based on a misunderstanding of how m_attempt_tracker works.

the update seems like its getting on the right track- the main purpose of tracking rebroadcast entries is to allow enforcing a maximum number of rebroadcast attempts.

IIUC, the problem we’re trying to solve is “How to avoid never-going-to-be-mined transactions to forever ping-pong across the network ?”.

yes, exactly.

but it still seems like there is remaining confusion. MAX_ENTRY_AGE indicates the amount of time has passed since tx A has been rebroadcast to peers. if its been 3 months since we last tried to rebroadcast tx A, we remove the attempts from the tracker. if there is no entry for tx A on the tracker, we don’t have record of the fact that we tried to rebroadcast it, so if tx A is selected by the block assembler, we would rebroadcast it again.

I don’t see how MAX_ENTRY_AGE would viably be used for node fingerprinting when you combine with the other factors such as filterInventoryKnown.

Have you tried to run this branch on mainet with a wide-sized mempool ? I think there is a logger in CacheMinRebroadcastFee, do you have stats to share on how much time it take by attempts ?

Not sure if the block min feerate accuracy is worth the CPU time…

yup, here are some values are for running the whole function. Note that it does not distinguish CPU time vs time spent waiting to acquire the lock, as it currently acquires cs_main and mempool.cs, but the first might be unnecessary (see #21061 (review)):

the median value is 9090 μs, with 75% of the runs being under 11300 μs, and 99% of the run being under 11826 μs.

Not sure if the block min feerate accuracy is worth the CPU time…

its a pretty critical component to this approach, without it the node would most likely be attempting to rebroadcast MAX_REBROADCAST_WEIGHT of transactions on every block.

the median value is 9090 μs, with 75% of the runs being under 11300 μs, and 99% of the run being under 11826 μs.

Okay and with a fulfilled mempool of the default size 300 MiB ? If yes I agree that’s not that much and I think we’re relieved on this concern :) If it does causes issues on low-grade nodes in the future, due to non-linear scaling of the CPU time in function of mempool size, I guess we’ll be able to make this value configurable, offering a trade-off between CPU and bandwidth to node operators.

its a pretty critical component to this approach, without it the node would most likely be attempting to rebroadcast MAX_REBROADCAST_WEIGHT of transactions on every block.

Do you mean without it or with a lower frequency rather than 1 min ? IIUC, the node would attempt to rebroadcast MAX_REBROADCAST_WEIGHT because you don’t account for the fresh arrivals of new transactions. The feerate of those newcomers making most of your rebroadcast candidates irrelevant to block confirmation ? If refreshing the cache was costly, I guess we would run it once between expected block intervals when the odds of having discovered enough new transactions to have a consistent view of next block are high. But cost is pretty low, so I don’t think we care further…

nit: maybe replace 1 by a named constant like CACHE_REBROADCAST_FEERATE_FREQUENCY ?

Okay and with a fulfilled mempool of the default size 300 MiB ? If yes I agree that’s not that much and I think we’re relieved on this concern :)