p2p: Drop m_recently_announced

ajtowns commented at 1:45 pm on May 16, 2023: contributor

This PR replaces the m_recently_announced_invs bloom filter with a simple sequence number tracking the mempool state when we last considered sending an INV message to a node. This saves 33kB per peer (or more if we raise the rate at which we relay transactions over the network, in which case we would need to increase the size of the bloom filter proportionally).

The philosophy here (compare with #18861 and #19109) is that we consider the rate limiting on INV messages to only be about saving bandwidth and not protecting privacy, and therefore after you receive an INV message, it’s immediately fair game to request any transaction that was in the mempool at the time the INV message was sent. We likewise consider the BIP 133 feefilter and BIP 37 bloom filters to be bandwidth optimisations here, and treat transactions as requestable if they would have been announced without those filters. Given that philosophy, tracking the timestamp of the last INV message and comparing that against the mempool entry time allows removal of each of m_recently_announced_invs, m_last_mempool_req and UNCONDITIONAL_RELAY_DELAY and associated logic.

DrahtBot commented at 1:45 pm on May 16, 2023: contributor

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Reviews

See the guideline for information on the review process.

Type	Reviewers
ACK	amitiuttarwar, naumenkogs, glozow
Concept ACK	sdaftuar, MarcoFalke, sipa
Stale ACK	jonatack

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#28107 (util: Type-safe transaction identifiers by dergoegge)
#27630 (p2p: Increase tx relay rate by sdaftuar)
#26283 (p2p: Fill reconciliation sets and request reconciliation (Erlay) by naumenkogs)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

ajtowns commented at 1:48 pm on May 16, 2023: contributor

As justification for ignoring the privacy benefits of rate limiting INV messages, consider the following approach: an attacker makes multiple inbound connections to our peer, and upon receiving an INV of txs a,b,c,d,… via one connection immediately announces the same txs on each of its other connections. In that case the next INV we send on some other connection to the attacker will skip those transactions, providing a new unique set. With this approach, the attacker should be able to receive tx announcements from us at many times the 7tx/s limit we originally set.

ajtowns force-pushed on May 16, 2023

DrahtBot added the label CI failed on May 16, 2023

in src/net_processing.cpp:2264 in 9607a5078d outdated

2275-        // ... or the relay pool.
2276-        auto mi = mapRelay.find(gtxid.GetHash());
2277-        if (mi != mapRelay.end()) return mi->second;
2278-    }
2279+    // Otherwise, the transaction must have been announced recently or removed from the mempool.
2280+    // If the latter, maybe it's in mapRelay!

maflcko commented at 2:04 pm on May 16, 2023:

nit: Looks like this will make inbound peers be treated identical to outbound ones for the purposes of getdata, as long as mapRelay is still around. For in-mempool txs it may be possible to fix by moving the time check outside of info_for_relay into this function and returning a nullptr early if the tx is known to not be announced. For non-mempool txs, I don’t know.

ajtowns commented at 3:11 am on May 17, 2023:

Yeah, this is broken as-is. My original idea was to add a timestamp to the mapRelay entries too, then it was to drop mapRelay and add vExtraTxnForCompact-relay, then I compromised by just doing it wrong…

ajtowns commented at 9:26 pm on June 5, 2023:

This includes commits to drop mapRelay now (cf #27625) so shouldn’t be broken anymore.

in src/kernel/mempool_entry.h:129 in 9607a5078d outdated

125@@ -126,7 +126,7 @@ class CTxMemPoolEntry
126         return GetVirtualTransactionSize(nTxWeight, sigOpCost, ::nBytesPerSigOp);
127     }
128     size_t GetTxWeight() const { return nTxWeight; }
129-    std::chrono::seconds GetTime() const { return std::chrono::seconds{nTime}; }
130+    NodeClock::time_point GetNodeTime() const { return nTime; }

maflcko commented at 2:07 pm on May 16, 2023:

nit: My recommendation would be to not rename the method, or if you want, to pick GetEntryTime() over GetNodeTime(), because the function doesn’t return the current node time but the time of transaction entry.

ajtowns commented at 3:09 am on May 17, 2023:

I mostly renamed it to make sure there’d be compiler errors anywhere that it didn’t get updated, just in case some type conversion happened automatically.

ajtowns commented at 9:27 pm on June 5, 2023:

This isn’t renamed anymore, instead GetEntryTime() is added for the steady clock time tracking mempool entry. (Happy to rename it to something better if someone has a suggestion)

ajtowns force-pushed on May 16, 2023

ajtowns marked this as a draft on May 16, 2023

ajtowns force-pushed on May 17, 2023

ajtowns force-pushed on May 18, 2023

in src/net_processing.cpp:2302 in 023d0503ff outdated

2298@@ -2299,7 +2299,7 @@ void PeerManagerImpl::ProcessGetData(CNode& pfrom, Peer& peer, const std::atomic
2299     std::vector<CInv> vNotFound;
2300     const CNetMsgMaker msgMaker(pfrom.GetCommonVersion());
2301 
2302-    const auto now{GetTime<std::chrono::seconds>()};
2303+    const NodeClock::time_point now = NodeClock::now();

sdaftuar commented at 3:31 pm on May 18, 2023:

The NodeClock::now() time can go backwards, right? If so I think that could pose some issues if we’re primarily relying on system time in order to determine whether transactions should be available for relay. Can we use a steady clock instead?

ajtowns commented at 11:29 am on May 23, 2023:

We could; it’d mean adding an extra field to the mempool, and using both mockable time and steady time for dealing with next invs (mockable time so we can skip over delays in sending invs; steady time for this purpose).

ajtowns commented at 9:28 pm on June 5, 2023:

Switched to steady clock.

sdaftuar commented at 3:41 pm on May 18, 2023: member

Concept ACK on getting rid of the recently announced filter. I think we’d need to use a steady clock to avoid random failures for no good reason, is that easy to do?

ajtowns force-pushed on May 23, 2023

in src/kernel/mempool_persist.cpp:81 in 71078b35ef outdated

77@@ -78,7 +78,7 @@ bool LoadMempool(CTxMemPool& pool, const fs::path& load_path, Chainstate& active
78             }
79             if (nTime > TicksSinceEpoch<std::chrono::seconds>(now - pool.m_expiry)) {
80                 LOCK(cs_main);
81-                const auto& accepted = AcceptToMemoryPool(active_chainstate, tx, nTime, /*bypass_limits=*/false, /*test_accept=*/false);
82+                const auto& accepted = AcceptToMemoryPool(active_chainstate, tx, NodeClock::time_point{std::chrono::seconds{nTime}}, /*bypass_limits=*/false, /*test_accept=*/false);

maflcko commented at 12:20 pm on May 23, 2023:

Might have to use LossyChronoFormatter to avoid the fuzz crash?

ajtowns commented at 4:14 am on June 3, 2023:

I think the answer is just to add a new tx entry field for the steady clock time and use that at natural precision.

ajtowns commented at 9:28 pm on June 5, 2023:

Entry time is no longer saved or loaded, so this is no longer relevant.

sr-gi commented at 6:22 pm on May 23, 2023: member

What’s the rationale regarding optimizing for memory instead of privacy here? I can see how this simplifies the design, however, I fail to see this being an obvious pick given we’d be potentially even more exposed to fingerprinting than before (as is now it is trivial for every connection to probe data on the node’s mempool).

sr-gi commented at 5:52 pm on May 31, 2023: member

So just to be clear, my concern here relates to the fact that the current codebase only allows a peer to request a transaction as long as we have announced that to them (with the exception of data requested after a MEMPOOL message if we happen run signaling bip37).

After this patch, the logic above won’t hold true anymore. If for whatever reason we have more than INV_BROADCAST_MAX transactions to send to a given peer at a given time, and we send an INV message to it, it will immediately be able to request any of those new transactions (even if they were never offered). Whether this is in itself a meaningful privacy leak is unclear to me. Under regular loads (<INV_BROADCAST_MAX pending transactions to be announced), this behaves exactly like the current codebase.

I guess it all boils down to whether potentially allowing a peer to know when a transaction enters our mempool is something we should guard about or not.

ajtowns commented at 5:04 am on June 2, 2023: contributor

What’s the rationale regarding optimizing for memory instead of privacy here? I can see how this simplifies the design, however, I fail to see this being an obvious pick given we’d be potentially even more exposed to fingerprinting than before (as is now it is trivial for every connection to probe data on the node’s mempool).

This isn’t trading off privacy – that’s the point of this comment. It does mean that someone trying to find out whether a recent transaction entered your mempool in the last window doesn’t need multiple inbound connections, but that’s a good thing: having many inbound connections is easy for an attacker, so avoiding the need to make many inbound connections just means those inbound slots become available for honest peers.

So just to be clear, my concern here relates to the fact that the current codebase only allows a peer to request a transaction as long as we have announced that to them (with the exception of data requested after a MEMPOOL message if we happen run signaling bip37).

That’s already the case for any txs that have been in the mempool for greater than two minutes, and any transactions that have been announced to a peer. Generally that’s plenty for fingerprinting – if you announce pairs of conflicting txs randomly to different nodes, then if you do that 20 times at the same low-ish feerate (so that neither will rbf the other), then wait two minutes, you’ll likely already get a nearly unique set of txs that will serve as a fingerprint for any given node.

After this patch, the logic above won’t hold true anymore. If for whatever reason we have more than INV_BROADCAST_MAX transactions to send to a given peer at a given time, and we send an INV message to it, it will immediately be able to request any of those new transactions (even if they were never offered). Whether this is in itself a meaningful privacy leak is unclear to me. Under regular loads (<INV_BROADCAST_MAX pending transactions to be announced), this behaves exactly like the current codebase.

I guess it all boils down to whether potentially allowing a peer to know when a transaction enters our mempool is something we should guard about or not.

The point of the random INV intervals is that we limit the knowledge of when a transaction entered our mempool to a specific window – if we send an INV at t=0s, t=1.1s, t=6.1s, t=6.4s, eg, then our peer can tell the difference between a tx that entered at t=0.5s and t=3s, but can’t tell the difference between t=3s and t=4s or t=5s, because they’re all in the same window. We then use the same window boundaries for all inbound peers so that adding extra inbound peers doesn’t give you more precise knowledge.

If the attacker only has a single inbound connection, then when the number of txs in a window exceeds INV_BROADCAST_MAX they’ll get less information; however as the comment above attempted to explain, adding additional inbound connections and manually announcing some txs on some of the connections will allow an attacker to get the full set of txs included in each window. So I don’t think it makes sense to consider the INV_BROADCAST_MAX limit to have a privacy benefit. (And if we eventually add erlay support, I think that limit goes away entirely for connections doing announcements over erlay rather than INV anyway)

sr-gi commented at 6:46 pm on June 2, 2023: member

What’s the rationale regarding optimizing for memory instead of privacy here? I can see how this simplifies the design, however, I fail to see this being an obvious pick given we’d be potentially even more exposed to fingerprinting than before (as is now it is trivial for every connection to probe data on the node’s mempool).

This isn’t trading off privacy – that’s the point of this comment. It does mean that someone trying to find out whether a recent transaction entered your mempool in the last window doesn’t need multiple inbound connections, but that’s a good thing: having many inbound connections is easy for an attacker, so avoiding the need to make many inbound connections just means those inbound slots become available for honest peers.

Right, I don’t think I originally fully understood what you meant by that. So the case is:

An attacker has n inbound connections to node B (namely A0, ..., An-1)
B sends an INV message containing a, b, c, d through link Ai
- During the same message processing loop for B, A sends a, b, c, d through link Aj
- Now Aj will receive an INV with a disjoint set for a, b, c, d when B picks it in this round

Provided A has enough links with B, it should be able to get all pending connections in B’s mempool in a single round. Is that it? If so, I think this renders all my other comments irrelevant.

That’s already the case for any txs that have been in the mempool for greater than two minutes, and any transactions that have been announced to a peer. Generally that’s plenty for fingerprinting – if you announce pairs of conflicting txs randomly to different nodes, then if you do that 20 times at the same low-ish feerate (so that neither will rbf the other), then wait two minutes, you’ll likely already get a nearly unique set of txs that will serve as a fingerprint for any given node.

I don’t think I follow here though. Would you mind elaborating?

ajtowns force-pushed on Jun 3, 2023

ajtowns force-pushed on Jun 5, 2023

DrahtBot added the label Needs rebase on Jun 12, 2023

ajtowns force-pushed on Jun 12, 2023

ajtowns marked this as ready for review on Jun 12, 2023

ajtowns commented at 11:56 am on June 12, 2023: contributor

[it is trivial for every connection to probe data on the node’s mempool] already the case for any txs that have been in the mempool for greater than two minutes, and any transactions that have been announced to a peer. Generally that’s plenty for fingerprinting – if you announce pairs of conflicting txs randomly to different nodes, then if you do that 20 times at the same low-ish feerate (so that neither will rbf the other), then wait two minutes, you’ll likely already get a nearly unique set of txs that will serve as a fingerprint for any given node.

I don’t think I follow here though. Would you mind elaborating?

The easy way to probe for the presence of transaction X in the mempool is to propose a fake transaction Z that spends an unspent output of X, and a fake transaction Y, with fake signatures for both, and see how its orphan handling behaves. If you receive a request for X and Y, then the victim didn’t have X in its mempool; if you receive a request for just Y, then it did have X in the mempool; if you don’t receive a request for either, then X was not in the mempool and was in its reject filter.

If you want to fingerprint a node, for example to see that an ipv4 address and a tor address are both pointing to the same node, then you need to set things up so that each node in the network has a different set of txs in their mempools, then query them to see if the node behind the ipv4 address and the node behind the tor address have the same set of txs. One way to do that is to propose a bunch of double-spends at the same feerate: a1/a2, b1/b2, c1/c2, etc and fire them off at various nodes on the network, then use the previous technique to see which txs actually ended up in the interesting nodes’ mempools.

None of that requires careful timing – you just need to set the feerates so they won’t either be mined immediately, nor be evicted from the mempool too quickly.

DrahtBot renamed this:
~~net_processing: Drop m_recently_announced_invs bloom filter~~
p2p: Drop m_recently_announced_invs bloom filter
on Jun 12, 2023

DrahtBot removed the label Needs rebase on Jun 12, 2023

DrahtBot removed the label CI failed on Jun 12, 2023

DrahtBot added the label P2P on Jun 12, 2023

DrahtBot added the label CI failed on Jun 14, 2023

maflcko commented at 8:36 am on June 15, 2023: member

I don’t think the multiple inbound connections argument is convincing, unless I am missing something. In practise, the inbound connections are scheduled randomly, so the attacker wouldn’t know which inbound is the next one to announce the known invs on. And once they were scheduled by the victim (or the first inv message was sent by the attacker), it is too late to send another inv message, because only one inv message is processed per scheduling round. I haven’t done any math, but the cost-vs-payoff should only be linear up to two inbound attacking connections, and quickly fade after?

Though, the other arguments seem more convincing, so Concept ACK.

in src/kernel/mempool_entry.h:87 in 500e31e87b outdated

83@@ -83,6 +84,7 @@ class CTxMemPoolEntry
84     const int64_t sigOpCost;        //!< Total sigop cost
85     CAmount m_modified_fee;         //!< Used for determining the priority of the transaction for mining in a block
86     LockPoints lockPoints;          //!< Track the height and time at which tx was final
87+    const SteadyClock::time_point m_entry_time; //!< High-precision time when entering the mempool

maflcko commented at 8:37 am on June 15, 2023:

nit: may be better to put this right after the nTime field to group related stuff?

jonatack commented at 9:49 pm on June 28, 2023:

In 930b1c7323be84ad7fb8371ee744f201325f18bb agree with @MarcoFalke to put this next to nTime, and it may be nice to document how each is used and why the need for both

ajtowns commented at 8:00 pm on June 30, 2023:

No longer relevant

in src/kernel/mempool_entry.h:133 in 500e31e87b outdated

129@@ -127,6 +130,7 @@ class CTxMemPoolEntry
130     }
131     size_t GetTxWeight() const { return nTxWeight; }
132     std::chrono::seconds GetTime() const { return std::chrono::seconds{nTime}; }
133+    SteadyClock::time_point GetEntryTime() const { return m_entry_time; }

maflcko commented at 8:37 am on June 15, 2023:

May be good to explain and document what time point to use when or why there are two different ones?

maflcko commented at 8:39 am on June 15, 2023:

Looks like this one is only to be used internally for relay and the other one is to be used for everything else?

ajtowns commented at 9:21 am on June 15, 2023:

Looks like this one is only to be used internally for relay and the other one is to be used for everything else?

Yeah - SteadyClock times aren’t comparable between runs (particularly if there was a reboot inbetween), so these timestamps are only useful “internally” in general.

Could alternatively store the value of mempool->GetSequence() instead of the SteadyClock time for a similar result.

maflcko commented at 12:29 pm on June 15, 2023:

Looks like the mempool sequence was added in e76fc2b84d065c9d06010d0a10b316f1f9d36fb9 and is exposed publicly. So I guess it won’t be going away any time soon and using it over SteadyClock allows to drop the static_assert about the precision (or just having to think about precision at all), as well as avoiding confusion about having two time points?

ajtowns commented at 8:00 pm on June 30, 2023:

Updated to use the mempool sequence number rather than SteadyClock

ajtowns commented at 9:13 am on June 15, 2023: contributor

I don’t think the multiple inbound connections argument is convincing, unless I am missing something. In practise, the inbound connections are scheduled randomly, so the attacker wouldn’t know which inbound is the next one to announce the known invs on. And once they were scheduled by the victim (or the first inv message was sent by the attacker), it is too late to send another inv message, because only one inv message is processed per scheduling round.

I think that’s incorrect: if you have three inbound peers, A, B and C, the timing may look something like:

t=0, next_inv_to_inbounds = 4.8s
t=1, SendMessages, peerB->m_next_inv_send_time = next_inv_to_inbounds
t=1.001, SendMessages, peerA->m_next_inv_send_time = next_inv_to_inbounds
t=1.002, SendMessages, peerC->m_next_inv_send_time = next_inv_to_inbounds
t=2, RelayTransaction(tx1)
t=3, RelayTransaction(tx2)
t=4, RelayTransaction(tx3)
t=5, SendMessages, peerC->m_next_inv_send_time = next_inv_to_inbounds = 10s, INV tx1, tx2, tx3 to C
t=5.001, SendMessages, peerB->m_next_inv_send_Time = next_inv_to_inbounds, INV tx1, tx2, tx3 to B
t=5.002, SendMessages, peerA->m_next_inv_send_Time = next_inv_to_inbounds, INV tx1, tx2, tx3 to A

Note that NextInvToInbounds only gets a new time if next_inv_to_inbounds < now, which leaves plenty of time for all the inbound peers to be cycled through before a new time is picked.

maflcko commented at 9:59 am on June 15, 2023: member

the timing may look something like:

* t=5, `SendMessages`, `peerC->m_next_inv_send_time = next_inv_to_inbounds = 10s`, INV tx1, tx2, tx3 to C

* t=5.001, `SendMessages`, `peerB->m_next_inv_send_Time = next_inv_to_inbounds`, INV tx1, tx2, tx3 to B

* t=5.002, `SendMessages`, `peerA->m_next_inv_send_Time = next_inv_to_inbounds`, INV tx1, tx2, tx3 to A

It looks like all inbound peers receive the same INVs, which doesn’t look like an attack, but normal operation? Let’s assume INVENTORY_BROADCAST_MAX is 1, so as an attacker you’d get:

t=5, SendMessages, peerC->m_next_inv_send_time = next_inv_to_inbounds = 10s, INV tx1 to C
Attacker fans out INV tx1 on all connections, because it doesn’t know which connection is scheduled/shuffled next
t=5.0001 ProcessMessages, peerB, INV tx1 from B
t=5.001, SendMessages, peerB->m_next_inv_send_Time = next_inv_to_inbounds, INV tx2 to B
t=5.0011 ProcessMessages, peerC, INV tx1 from A
t=5.002, SendMessages, peerA->m_next_inv_send_Time = next_inv_to_inbounds, INV tx2 to A

Thus, an attacker can only trivially double the information it can get (tx1+tx2) vs just (tx1). But getting tx3 with three inbound connections only seems possible with probability less than 1 in a single try.

ajtowns commented at 11:37 am on June 15, 2023: contributor

It looks like all inbound peers receive the same INVs, which doesn’t look like an attack, but normal operation?

Yes, that’s ordinary operation, where everyone finds out all the txids you received in an interval automatically. If you’d instead received more than 35 txids in the interval (tx1 .. tx100, say, with tx1 being highest feerate (compareInvMempoolOrder)) then everyone would receive INV tx1..tx35. For an attacker who wants to know the timing information for all 100 txs, they could make 3 inbound connections, peerA1 through peerA3, as follows:

t=4.5, peerA1 sends INV tx1..tx66 to us
t=4.51, peerA2 sends INV tx34..tx100 to us
t=4.52, peer A3 sends INV tx1..tx33, tx67..tx100 to us

and our response would then be to remove the INVed txs from each peer’s queue, so when we hit next_inv_to_inbounds we’d do:

t=5, SendMessages, peerC->m_next_inv_send_time = next_inv_to_inbounds = 10s, INV tx1..tx35 to C
t=5.001, SendMessages, peerA1->m_next_inv_send_time = next_inv_to_inbounds, INV tx67..tx100 to A1
t=5.002, SendMessages, peerA3->m_next_inv_send_time = next_inv_to_inbounds, INV tx34..tx66 to A3
t=5.003, SendMessages, peerA2->m_next_inv_send_time = next_inv_to_inbounds, INV tx1..tx33 to A2
t=5.004, SendMessages, peerB->m_next_inv_send_time = next_inv_to_inbounds, INV tx1..tx35 to B

and between A1..A3 you receive announcements for all of tx1..tx100 that were accepted into the victim’s mempool between the next_inv_to_inbounds timestamps of t=0 and t=4.8.

ie, basically if the network’s processing up to 7X tx/second, you make X connections to the victim peer, divide the txs you receive into X groups, and announce all txids except for the K’th group to the victim via connection K. (If they request the tx from you, then just quickly reply notfound to avoid biasing the data). Few things to be careful of if you want to actually make that work, but should be find in principle.

maflcko commented at 11:48 am on June 15, 2023: member

announce all txids except for the K’th group to the victim

Ok, looks like you are assuming that the attacker already knows all transactions (or txids), and I assumed this is what the attacker wants to find out.

ajtowns commented at 11:57 am on June 15, 2023: contributor

Ok, looks like you are assuming that the attacker already knows all transactions (or txids), and I assumed this is what the attacker wants to find out.

You find out txids more quickly just by running a public listening node; the extra information that active probing gets you is information about when a tx was first received by different nodes in the network, from which you can then infer some idea about how the network is connected (“which nodes should I disrupt in order to partition the network?”) or which node was the source of a given transaction (to remove pseudonymity). This PR means that instead of actively probing via the above method, you could also actively probe by sending “GETDATA” messages for txids you haven’t yet received an “INV” for.

maflcko commented at 12:45 pm on June 15, 2023: member

This PR means that instead of actively probing via the above method, you could also actively probe by sending “GETDATA” messages for txids you haven’t yet received an “INV” for.

Thanks. My comments are unrelated and can be discarded, because this pull’s goal isn’t to change the externally visible inv sending logic, only the getdata receiving logic.

sr-gi commented at 8:09 pm on June 15, 2023: member

The easy way to probe for the presence of transaction X in the mempool is to propose a fake transaction Z that spends an unspent output of X, and a fake transaction Y, with fake signatures for both, and see how its orphan handling behaves. If you receive a request for X and Y, then the victim didn’t have X in its mempool; if you receive a request for just Y, then it did have X in the mempool; if you don’t receive a request for either, then X was not in the mempool and was in its reject filter.

This feels pretty similar to what TxProbe used to do to infer links between nodes, and ultimately relates to how orphans are treated differently from mempool transactions both when handed and requested.

This is pretty tangential to this PR, but I’m wondering whether it may make sense to change that behavior to always request all the unannounced parents on a given link when an orphan is received through it. In the same way, orphans could be requested, even if known, when offered through a link they haven’t been received from. Validation for this type of transaction may even be simplified, given they are already known, so as long as the same data is received nothing else needs to be checked. At a glance, this looks cheap while it will prevent leaking information related to orphans.

maflcko commented at 10:54 am on June 28, 2023: member

Could rebase for CI?

in src/txmempool.h:411 in 500e31e87b outdated

407@@ -408,6 +408,8 @@ class CTxMemPool
408     using txiter = indexed_transaction_set::nth_index<0>::type::const_iterator;
409     std::vector<std::pair<uint256, txiter>> vTxHashes GUARDED_BY(cs); //!< All tx witness hashes/entries in mapTx, in random order
410 
411+    TxMempoolInfo info_for_relay(const GenTxid& gtxid, SteadyClock::time_point last_inv) const;

jonatack commented at 9:44 pm on June 28, 2023:

In e16fb7d212bf1dbb5086ed8f452e8e80acbe8325 consider adding the info_for_relay() getter declaration next to info() and infoAll()

 0--- a/src/txmempool.h
 1+++ b/src/txmempool.h
 2@@ -411,8 +411,6 @@ public:
 3     using txiter = indexed_transaction_set::nth_index<0>::type::const_iterator;
 4     std::vector<std::pair<uint256, txiter>> vTxHashes GUARDED_BY(cs); //!< All tx witness hashes/entries in mapTx, in random order
 5 
 6-    TxMempoolInfo info_for_relay(const GenTxid& gtxid, SteadyClock::time_point last_inv) const;
 7-
 8     typedef std::set<txiter, CompareIteratorByHash> setEntries;
 9 
10     using Limits = kernel::MemPoolLimits;
11@@ -710,6 +708,7 @@ public:
12         return mapTx.project<0>(mapTx.get<index_by_wtxid>().find(wtxid));
13     }
14     TxMempoolInfo info(const GenTxid& gtxid) const;
15+    TxMempoolInfo info_for_relay(const GenTxid& gtxid, SteadyClock::time_point last_inv) const;
16     std::vector<TxMempoolInfo> infoAll() const;

jonatack commented at 9:55 pm on June 28, 2023: member

Initial concept/approach ACK 500e31e87b33418a0747a0f3118db9ceb23896be

ajtowns force-pushed on Jun 30, 2023

ajtowns commented at 8:01 pm on June 30, 2023: contributor

Rebased and switched to using the mempool sequence instead of SteadyClock

jonatack commented at 9:11 pm on June 30, 2023: member

Seeing this thread safety warning locally with the fuzz build only (ARM64 clang 16).

0net_processing.cpp:5769:63: warning: calling function 'GetSequence' requires holding mutex 'm_mempool.cs' exclusively [-Wthread-safety-analysis]
1                    tx_relay->m_last_inv_sequence = m_mempool.GetSequence();
2                                                              ^
31 warning generated.

ajtowns force-pushed on Jul 2, 2023

in src/kernel/mempool_entry.h:131 in 284516f8e4 outdated

122@@ -120,6 +123,13 @@ class CTxMemPoolEntry
123           nModFeesWithAncestors{nFee},
124           nSigOpCostWithAncestors{sigOpCost} {}
125 
126+    CTxMemPoolEntry(const CTxMemPoolEntry&) = default;
127+    CTxMemPoolEntry& operator=(const CTxMemPoolEntry&) = delete;
128+
129+    // can't be moved
130+    CTxMemPoolEntry(CTxMemPoolEntry&&) = default;
131+    CTxMemPoolEntry& operator=(CTxMemPoolEntry&&) = delete;

jonatack commented at 5:44 pm on July 5, 2023:

eb4dc54 Are these special member functions needed, and if yes, declare them all? A comment in the commit explaining why they are added would be helpful.

0+    CTxMemPoolEntry() = delete;
1+    ~CTxMemPoolEntry() = default;
2     CTxMemPoolEntry(const CTxMemPoolEntry&) = default;
3-    CTxMemPoolEntry& operator=(const CTxMemPoolEntry&) = delete;
4-
5-    // can't be moved
6+    CTxMemPoolEntry& operator=(const CTxMemPoolEntry&) = delete; // disallow copy assignment
7     CTxMemPoolEntry(CTxMemPoolEntry&&) = default;
8-    CTxMemPoolEntry& operator=(CTxMemPoolEntry&&) = delete;
9+    CTxMemPoolEntry& operator=(CTxMemPoolEntry&&) = delete;  // disallow move assignment

ajtowns commented at 10:07 pm on July 5, 2023:

Oh, yuck; that’s a bad rebase. :(

in src/util/epochguard.h:62 in 284516f8e4 outdated

59     public:
60         Marker() = default;
61         Marker(const Marker&) = default;
62-        Marker(Marker&&) = delete;
63+        Marker(Marker&&) = default;
64+        Marker& operator=(const Marker&) = delete;

jonatack commented at 6:06 pm on July 5, 2023:

eb4dc54 These changes seem needed due to the special member functions added to CTxMemPoolEntry in the same commit? If they are changed, a comment in the commit explaining why would be helpful.

in src/node/interfaces.cpp:679 in 284516f8e4 outdated

675@@ -676,7 +676,7 @@ class ChainImpl : public Chain
676     {
677         if (!m_node.mempool) return true;
678         LockPoints lp;
679-        CTxMemPoolEntry entry(tx, 0, 0, 0, false, 0, lp);
680+        CTxMemPoolEntry entry(tx, 0, 0, 0, 0, false, 0, lp);

jonatack commented at 6:26 pm on July 5, 2023:

Unrelated to this pull, but seems odd that entry_height is set to 0 here when 1 is the usual initial value.

in src/net_processing.cpp:2291 in 284516f8e4 outdated

2293-        // or is older than UNCONDITIONAL_RELAY_DELAY, permit the request
2294-        // unconditionally.
2295-        if ((mempool_req.count() && txinfo.m_time <= mempool_req) || txinfo.m_time <= now - UNCONDITIONAL_RELAY_DELAY) {
2296-            return std::move(txinfo.tx);
2297-        }
2298+        return std::move(txinfo.tx);

jonatack commented at 6:49 pm on July 5, 2023:

ca6379eb While touching this, with guaranteed copy elision it’s now almost always a pessimization to return std::move(local) (and the other remaining return values in this function are return it->second; and {}).

0        return txinfo.tx;

ajtowns commented at 10:14 pm on July 5, 2023:

That’s moving a member of a local struct/object, not a simple local, so it can’t have been constructed in place and copy/move elision isn’t possible, though?

jonatack commented at 10:17 pm on July 5, 2023:

Ah, you may be right.

https://shaharmike.com/cpp/rvo/#returning-member

jonatack commented at 11:05 pm on July 5, 2023:

 0// rvo.cpp
 1
 2#include <iostream>
 3
 4struct Snitch {   // Note: All methods have side effects
 5    Snitch() { std::cout << "ctor" << std::endl; }
 6    ~Snitch() { std::cout << "dtor" << std::endl; }
 7
 8    Snitch(const Snitch&) { std::cout << "copy ctor" << std::endl; }
 9    Snitch(Snitch&&) { std::cout << "move ctor" << std::endl; }
10
11    Snitch& operator=(const Snitch&) {
12        std::cout << "copy assignment" << std::endl;
13        return *this;
14    }
15
16    Snitch& operator=(Snitch&&) {
17        std::cout << "move assignment" << std::endl;
18        return *this;
19    }
20};
21
22struct Wrapper {
23    Snitch snitch;
24    int i;
25};
26
27Snitch foo() {
28    auto s = Wrapper().snitch;
29    return s;
30}
31
32Snitch foo_move() {
33    auto s = Wrapper().snitch;
34    return std::move(s);
35}
36
37
38int main() {
39    std::cout << "\nfoo_move..." << std::endl;
40    Snitch t = foo_move();
41
42    std::cout << "\nfoo..." << std::endl;
43    Snitch s = foo();
44
45    std::cout << "\ndone..." << std::endl;
46    return 0;
47}
48
49// $ clang++ -std=c++17 -stdlib=libc++ rvo.cpp && ./a.out
50//
51// foo_move...
52// ctor
53// move ctor
54// dtor
55// move ctor
56// dtor
57//
58// foo...
59// ctor
60// move ctor
61// dtor
62//
63// done...
64// dtor
65// dtor

Not necessarily for this pull, but was curious to find out.

ajtowns commented at 11:27 pm on July 5, 2023:

I think the test you want is auto s = Wrapper(); return std::move(s.snitch);

jonatack commented at 11:29 pm on July 5, 2023:

You’re right, thanks.

0foo_move...
1ctor
2move ctor
3dtor
4
5foo...
6ctor
7copy ctor
8dtor

in src/net_processing.cpp:5754 in 284516f8e4 outdated

5753                             m_connman.PushMessage(pto, msgMaker.Make(NetMsgType::INV, vInv));
5754                             vInv.clear();
5755                         }
5756                         tx_relay->m_tx_inventory_known_filter.insert(hash);
5757-                        if (hash != txid) {
5758+                        if (peer->m_wtxid_relay && hash != txinfo.tx->GetHash()) {

jonatack commented at 7:31 pm on July 5, 2023:

https://github.com/bitcoin/bitcoin/commit/ca6379eba56ca8f669fea6c91877e9ecbb31451b why is peer->m_wtxid_relay added in this conditional? (in which case the comment just below would need updating)

ajtowns commented at 11:11 pm on July 5, 2023:

For wtxid relay peers the prior .insert(hash) line adds the wtxid to the filter; for non-wtxid relay peers, it adds the txid to the filter. We only need to do a second insert to add the txid for wtxid relay peers, and then only when the wtxid is actually different to the txid. The extra check is just because testing a bool is easier than comparing two uint256s.

jonatack commented at 10:09 pm on July 6, 2023:

Thanks, makes sense, and I see that your change makes the conditional here the same as in ProcessMessage::TX followed by the same comment; that m_wtxid_relay check and both comments were added in ac88e2eb6198.

0        if (peer->m_wtxid_relay && txid != wtxid) {
1            // Insert txid into m_tx_inventory_known_filter, even for
2            // wtxidrelay peers. This prevents re-adding of
3            // unconfirmed parents to the recently_announced
4            // filter, when a child tx is requested. See
5            // ProcessGetData().
6            AddKnownTx(*peer, txid);
7        }

glozow commented at 10:04 am on July 7, 2023:

Is adding the txid still necessary though?

IIUC, the purpose of adding this transaction’s txid to inventory_known_filter is to save a step if this transaction has an unconfirmed child (if it already existed in this filter, then we wouldn’t add it to the recently_announced filter). The PR is deleting those lines from ProcessGetData, and that’s fine since an unconfirmed parent’s sequence number should before that of its child. But I’m not able to see another reason why we should add the txid to the inventory_known_filter, so why not delete this whole block?

If it’s still needed, it probably makes sense to update the 2 comments since they mention recently_announced filter.

sipa commented at 0:06 am on July 9, 2023:

since an unconfirmed parent’s sequence number should before that of its child.

What if a reorg happens, which adds a formerly-confirmed parent of an unconfirmed transaction back to the mempool?

I don’t think this example is particularly relevant in this situation (in such circumstances suboptimal relay is to be expected anyway), but perhaps it’s enough to make a blanket assumption that parent.entry_sequence < child.entry_sequence.

ajtowns commented at 2:34 am on July 13, 2023:

Maybe we could recover that as an invariant by having txs added in MaybeUpdateMempoolForReorg set the sequence number as 0? The idea being that if they’ve made it into a block then we’ve probably announced the headers already so it’s no secret that we knew about the tx anyway…

ajtowns commented at 11:26 am on July 15, 2023:

But I’m not able to see another reason why we should add the txid to the inventory_known_filter, so why not delete this whole block?

That seems correct to me.

ajtowns commented at 10:14 pm on July 15, 2023:

Updated to not add txids to the known filter for wtxid peers, and to set the entry sequence to 0 when adding txs that were in a block that was reorged out.

naumenkogs commented at 10:42 am on July 17, 2023:

This is done in the following commit c88deec

in src/net_processing.cpp:5751 in 284516f8e4 outdated

5769+                    // We don't hold cs_main or mempool.cs prior to setting current_time,
5770+                    // so it's possible a tx could have been added to the mempool and included
5771+                    // in m_tx_inventory_to_send and INVed above with a mempool nTime after
5772+                    // current_time. As such, only get the current time after sending all the invs.
5773+                    LOCK(m_mempool.cs);
5774+                    tx_relay->m_last_inv_sequence = m_mempool.GetSequence();

jonatack commented at 7:35 pm on July 5, 2023:

https://github.com/bitcoin/bitcoin/commit/ca6379eba56ca8f669fea6c91877e9ecbb31451b It looks like the documentation above needs updating, i.e. s/current_time/current sequence/, now that tx_relay->m_last_inv_send_time = SteadyClock::now(); in this commit was changed to tx_relay->m_last_inv_sequence = m_mempool.GetSequence();

ajtowns commented at 11:23 pm on July 5, 2023:

Updated

naumenkogs commented at 10:32 am on July 17, 2023:

34eab37b08bb9f23459aad179685a505a46759d7 Seems to be still talking about current_time?

ajtowns commented at 9:33 am on July 19, 2023:

I think I messed this up in the bad rebase :( Should be fixed now.

in src/txmempool.h:713 in 284516f8e4 outdated

707@@ -708,6 +708,7 @@ class CTxMemPool
708         return mapTx.project<0>(mapTx.get<index_by_wtxid>().find(wtxid));
709     }
710     TxMempoolInfo info(const GenTxid& gtxid) const;
711+    TxMempoolInfo info_for_relay(const GenTxid& gtxid, uint64_t last_sequence) const;

jonatack commented at 8:30 pm on July 5, 2023:

https://github.com/bitcoin/bitcoin/commit/eb4dc54b3c9b9edad9b469b07cbac0573bbf1a37 A Doxygen doc explaining the for_relay aspect and last_sequence logic would be handy.

amitiuttarwar commented at 1:07 am on August 1, 2023:

out of curiosity, why did you opt to make a separate function instead of having last_sequence be an optional field on info? is it to make it more apparent to future callers (aka devs implementing new call sites) that last_sequence must be passed in when retrieving a TxMempoolInfo with intent to relay?

glozow commented at 11:25 am on August 1, 2023:

A comment might be helpful

0    /** Returns info for a transaction if its entry_sequence <= last_sequence. */
1    TxMempoolInfo info_for_relay(const GenTxid& gtxid, uint64_t last_sequence) const;

jonatack commented at 8:38 pm on July 5, 2023: member

Approach ACK with some questions and feedback.

The last push changed from storing the entry time to using the sequence number in mempool#GetSequence per #27675 (review).

The CTxMemPool::m_sequence_number documentation could use updating in this case regarding its expanded role

0    // In-memory counter for external mempool tracking purposes.
1    // This number is incremented once every time a transaction
2    // is added or removed from the mempool for any reason.
3    mutable uint64_t m_sequence_number GUARDED_BY(cs){1};

and this part of the PR description updated: tracking the timestamp of the last INV message and comparing that against the mempool entry time.

ajtowns force-pushed on Jul 5, 2023

ajtowns commented at 11:30 pm on July 5, 2023: contributor

Updated for jonatack’s review – removes unneeded code changes, updates comments.

DrahtBot removed the label CI failed on Jul 6, 2023

in src/txmempool.h:334 in 172fa815e0 outdated

333@@ -334,6 +334,9 @@ class CTxMemPool
334     // In-memory counter for external mempool tracking purposes.

jonatack commented at 10:15 pm on July 6, 2023:

caf32d2 mentioning m_sequence_number’s new responsibility for p2p tx relay might be helpful (or alternatively, drop “external”)

0    // In-memory counter for internal (p2p tx relay) and external (zmq) mempool tracking purposes.

glozow commented at 9:19 am on July 7, 2023:

I think this just refers to external to the mempool.

jonatack commented at 3:20 pm on July 7, 2023:

There’s also the RPC, so maybe (or something equivalent)

// In-memory counter used for P2P tx relay, RPC, and ZMQ mempool tracking purposes.

in src/kernel/mempool_entry.h:135 in 172fa815e0 outdated

131@@ -130,6 +132,7 @@ class CTxMemPoolEntry
132     int32_t GetTxWeight() const { return nTxWeight; }
133     std::chrono::seconds GetTime() const { return std::chrono::seconds{nTime}; }
134     unsigned int GetHeight() const { return entryHeight; }
135+    uint64_t GetSequence() const { return entry_sequence; }

jonatack commented at 10:20 pm on July 6, 2023:

caf32d2 nit if you retouch, could be [[nodiscard]]

ajtowns commented at 11:48 am on July 15, 2023:

It’s okay to discard it though – you just might as well not have called the function in the first place if you don’t care about the return value? (And given it’s inline, presumably the compiler will treat it as if it wasn’t called anyway).

jonatack commented at 2:27 pm on July 15, 2023:

Right, nodiscard is “use it or lose it” (remove it) – applicable to getter/pure functions and any interfaces where the return value must be checked. Unlike the latter, if the result of a getter is not used it would not be incorrect, but in that case the call is useless and should be removed; nodiscard just enforces it.

ajtowns commented at 10:13 pm on July 15, 2023:

I can see the point of adding nodiscard in that case for confusing APIs (eg, where someone not familiar with the API might write foo.empty() when they meant foo.clear()) but for a foo.GetBar() function, it just seems like busy work, that I don’t think makes sense to do.

maflcko commented at 1:18 pm on July 26, 2023:

Agree as well.

I think it is fine to only add [[nodiscard]] to functions where it is harmful to drop the result. Otherwise one ends up adding the attribute to every function that isn’t void, which seems bloaty and unreadable?

If that was the goal, it could be easier achieved with a clang-tidy plugin, without touching or bloating any code at all.

jonatack commented at 4:57 pm on July 26, 2023:

Right, nodiscard is “use it or lose it” (remove it) – applicable to getter/pure functions and any interfaces where the return value must be checked. Unlike the latter, if the result of a getter is not used it would not be incorrect, but in that case the call is useless and should be removed; nodiscard just enforces it.

I use nodiscard for these two cases I describe, where it can simplify review and find issues for me. For instance, when adding it to a declaration I was touching in a pull, it revealed that a relevant unit test was not using the results and thereby highlighted that assertions were missing, which I added. When reviewing a pull having a pure function with many callers or one that is incorrect if not checked, I might add nodiscard and rebuild, and it saves me time if it is already present when initially building the commit.

jonatack commented at 11:07 pm on July 6, 2023: member

ACK 172fa815e08b54c61b24d552f065df15046aef3c

With this simplification, test coverage for the new logic might be feasible?

in src/net_processing.cpp:150 in 172fa815e0 outdated

146@@ -147,8 +147,12 @@ static constexpr auto OUTBOUND_INVENTORY_BROADCAST_INTERVAL{2s};
147 /** Maximum rate of inventory items to send per second.
148  *  Limits the impact of low-fee transaction floods. */
149 static constexpr unsigned int INVENTORY_BROADCAST_PER_SECOND = 7;
150+/** Target number of inventory items to send per transmission. */

glozow commented at 10:43 am on July 7, 2023:

0/** Target number of transaction inventory items to send per transmission. */

naumenkogs commented at 12:43 pm on July 12, 2023: member

Concept ACK

I was curious whether bumping a sequence number (RBF, then RBF back the target tx) is anything interesting. I think it’s ok:

it doesn’t provide any advantage for relay-delay over the regular RBF
it doesn’t look different either (NOTFOUND as opposed to ignoring the GETDATA or whatnot) — might be worth mentioning somewhere that they should look equal?

ajtowns force-pushed on Jul 15, 2023

in src/validation.cpp:839 in fec00d787b outdated

833@@ -834,7 +834,10 @@ bool MemPoolAccept::PreChecks(ATMPArgs& args, Workspace& ws)
834         }
835     }
836 
837-    entry.reset(new CTxMemPoolEntry(ptx, ws.m_base_fees, nAcceptTime, m_active_chainstate.m_chain.Height(), m_pool.GetSequence(),
838+    // Set entry_sequence to 0 when bypass_limits is used; this allows txs from a block
839+    // reorg to be marked earlier than any child txs that were already in the mempool.
840+    const uint64_t entry_sequence = args.m_bypass_limits ? 0 : m_pool.GetSequence();

naumenkogs commented at 10:18 am on July 17, 2023:

fec00d787b5530bbe892bef575fbb3cdc9d586ca

nit: you may drop the args. part and it will work because bypass_limits var is initialized above.

ajtowns commented at 9:33 am on July 19, 2023:

Dropped

naumenkogs commented at 11:01 am on July 17, 2023: member

ACK 0753120b6cb270914753d30a2626272f896a8545 modulo this (probably lost?) comment

My favorite achievement of this PR is dropping the complication of associated logic :)

DrahtBot requested review from jonatack on Jul 17, 2023

sipa commented at 8:42 pm on July 17, 2023: member

Concept/approach ACK.

ajtowns force-pushed on Jul 19, 2023

naumenkogs commented at 9:41 am on July 25, 2023: member

ACK f5d17e1a3f2856483ad3a6abcf3ea415f2d05fde

ajtowns force-pushed on Jul 27, 2023

ajtowns commented at 2:53 am on July 27, 2023: contributor

Updated to remove some unnecessary constructor changes and misleading comments associated with them.

naumenkogs commented at 9:34 am on July 27, 2023: member

ACK 7efb30b

fanquake requested review from mzumsande on Jul 27, 2023

fanquake requested review from amitiuttarwar on Jul 27, 2023

in src/test/util/txmempool.h:34 in 18f9f3059e outdated

30@@ -30,6 +31,7 @@ struct TestMemPoolEntryHelper {
31     TestMemPoolEntryHelper& Fee(CAmount _fee) { nFee = _fee; return *this; }
32     TestMemPoolEntryHelper& Time(NodeSeconds tp) { time = tp; return *this; }
33     TestMemPoolEntryHelper& Height(unsigned int _height) { nHeight = _height; return *this; }
34+    TestMemPoolEntryHelper& Sequence(uint64_t _seq) { m_sequence = _seq; return *this; }

amitiuttarwar commented at 11:25 pm on July 31, 2023:

is this used anywhere?

ajtowns commented at 0:47 am on August 10, 2023:

No, it’s not

in src/kernel/mempool_entry.h:82 in 7efb30b87d outdated

78@@ -79,6 +79,7 @@ class CTxMemPoolEntry
79     const size_t nUsageSize;        //!< ... and total memory usage
80     const int64_t nTime;            //!< Local time when entering the mempool
81     const unsigned int entryHeight; //!< Chain height when entering the mempool
82+    const uint64_t entry_sequence;  //!< Sequence number when entering the mempool

glozow commented at 8:28 am on August 1, 2023:

nit: this comment could be misleading after ffa081b007300f28fd9cffe6f4795c1125e2f373

0    const uint64_t entry_sequence;  //!< Sequence number used to determine whether this transaction is too recent for relay.

in src/validation.cpp:839 in 7efb30b87d outdated

833@@ -834,7 +834,10 @@ bool MemPoolAccept::PreChecks(ATMPArgs& args, Workspace& ws)
834         }
835     }
836 
837-    entry.reset(new CTxMemPoolEntry(ptx, ws.m_base_fees, nAcceptTime, m_active_chainstate.m_chain.Height(),
838+    // Set entry_sequence to 0 when bypass_limits is used; this allows txs from a block
839+    // reorg to be marked earlier than any child txs that were already in the mempool.
840+    const uint64_t entry_sequence = bypass_limits ? 0 : m_pool.GetSequence();

glozow commented at 11:35 am on August 1, 2023:

I think there may be an off-by-one here? The sequence number isn’t incremented until TransactionAddedToMempool() fires later. Which means we could have: t=0: mempool sequence is 1 t=1: tx A is submitted, CTxMemPoolEntry is constructed with entry_sequence = m_pool.GetSequence() = 1 t=2: main signals fires TransactionAddedToMempool(A, m_pool.GetAndIncrementSequence()) with sequence 2 t=3: p2p announces A, m_last_inv_sequence = m_mempool.GetSequence() = 2 t=4: new tx B is submitted, CTxMemPoolEntry is constructed with entry_sequence = m_pool.GetSequence() = 2 t=5: main signals fires TransactionAddedToMempool(B, m_pool.GetAndIncrementSequence()) with sequence 3 t=6: spy node requests A and B. FindTxForGetData() calls info_for_relay(last_sequence=2). A’s sequence is 1 and B’s sequence is 2. They are both requestable.

I don’t think it’s problematic that the TransactionAddedToMempool sequence and entry_sequence are not the same, but we shouldn’t relay B in this situation.

Perhaps it makes sense to use m_pool.GetSequence() + 1 here?

Tested in https://github.com/glozow/bitcoin/commit/258b1c8ced55b528d1afc585c23a3d98fa30394b#diff-ad4f4d79f7e644c4ec85670cece6e14ded4302c45016b085bb9bdea5a1075d9cR105-R111

glozow commented at 11:38 am on August 1, 2023:

nit: the commit message for ffa081b007300f28fd9cffe6f4795c1125e2f373 is “validation: when adding txs due to a block reorg, allow immediate relay” but the immediate relay behavior isn’t until the subsequent commit when the bloom filter is removed

maflcko commented at 1:34 pm on August 1, 2023:

The sequence number isn’t incremented until TransactionAddedToMempool() fires later.

Doesn’t that mean there are races? (There is no guarantee that TransactionAddedToMempool() will always run in the near future)?

Basically, I am wondering what happens if you reorder t=2 and t=3 in your example.

ajtowns commented at 2:16 pm on August 1, 2023:

Doesn’t that mean there are races? (There is no guarantee that TransactionAddedToMempool() will always run in the near future)?

The mempool value is incremented when TrAddedTMP is queued, not when it’s eventually run – the increment happens first, then the result of the increment is passed through and queued up. So I don’t think there’s any racy here.

Perhaps it makes sense to use m_pool.GetSequence() + 1 here?

I think it would make more sense to change info_for_relay?

 0TxMempoolInfo CTxMemPool::info_for_relay(const GenTxid& gtxid, uint64_t last_sequence) const
 1{
 2    LOCK(cs);
 3    indexed_transaction_set::const_iterator i = (gtxid.IsWtxid() ? get_iter_from_wtxid(gtxid.GetHash()) : mapTx.find(gtxid.GetHash()));
 4//  if (i == mapTx.end() || last_sequence < i->GetSequence()) {
 5    if (i == mapTx.end() || last_sequence <= i->GetSequence()) {
 6        return TxMempoolInfo();
 7    } else {
 8        return GetInfo(i);
 9    }
10}

glozow commented at 2:48 pm on August 1, 2023:

Doesn’t that mean there are races? (There is no guarantee that TransactionAddedToMempool() will always run in the near future)?

I meant TransactionAddedToMempool event happening, not the validation interface clients’ callbacks. IIUC the event firing on main signals (which calls GetAndIncrementSequence()) happens in validation before ProcessTransaction returns: https://github.com/bitcoin/bitcoin/blob/e5a9f2fb62dc4db6cad21b2997d96a881ea64125/src/validation.cpp#L1234

The queued callbacks are scheduled and may not have necessarily happened yet, but PeerManager doesn’t implement TransactionAddedToMempool. It is only interested in the current GetSequence() and what is recorded in mempool_sequence.

Basically, I am wondering what happens if you reorder t=2 and t=3 in your example.

My understanding is that GetSequence() returns 2 when ProcessTransaction is done, even if t=2 and t=3 are swapped.

glozow commented at 3:03 pm on August 1, 2023:

Ah I didn’t see the last message.

I think it would make more sense to change info_for_relay?

sounds good to me

ajtowns commented at 11:32 am on August 3, 2023:

Updated. This also changes the initial value for m_last_inv_sequence to 1 instead of 0. (Note that I reversed the order of the if .. else in info_for_relay so GetSeq() < last becomes ! (GetSeq() <= last) which is last < GetSeq())

glozow commented at 12:37 pm on August 1, 2023: member

Approach ACK, mempool sequence seems suitable for this.

I think we should add a functional test, perhaps something like this

mempool_entry: add mempool entry sequence number 1e9684f39f

validation: when adding txs due to a block reorg, allow immediate relay a70beafdb2

net_processing: drop m_recently_announced_invs bloom filter

Rather than using a bloom filter to track announced invs, simply allow
a peer to request any tx that entered the mempool prior to the last INV
message we sent them. This also obsoletes the UNCONDITIONAL_RELAY_DELAY.

6ec1809d33

net_processing: don't add txids to m_tx_inventory_known_filter

We no longer have m_recently_announced_invs, so there is no need to add
txids to m_tx_inventory_known_filter to dedupe that filter.

e4ffabbffa

ajtowns force-pushed on Aug 3, 2023

test: Check tx from disconnected block is immediately requestable

Check that peers can immediately request txs from blocks that have been
reorged out and are now in our mempool.

6fa49937e4

net_processing: Clean up INVENTORY_BROADCAST_MAX constants 1a118062fb

ajtowns force-pushed on Aug 3, 2023

DrahtBot added the label CI failed on Aug 3, 2023

ajtowns commented at 11:36 am on August 3, 2023: contributor

Update for glozow’s review; fixes off-by-one error and adds some glozow’s test coverage of reorg behaviour

DrahtBot removed the label CI failed on Aug 3, 2023

in src/kernel/mempool_entry.h:82 in 1e9684f39f outdated

78@@ -79,6 +79,7 @@ class CTxMemPoolEntry
79     const size_t nUsageSize;        //!< ... and total memory usage
80     const int64_t nTime;            //!< Local time when entering the mempool
81     const unsigned int entryHeight; //!< Chain height when entering the mempool
82+    const uint64_t entry_sequence;  //!< Sequence number used to determine w hether this transaction is too recent for relay

naumenkogs commented at 8:43 am on August 4, 2023:

1e9684f39fba909b3501e9402d5b61f4bf744ff2 “w hether”

naumenkogs approved

naumenkogs commented at 8:51 am on August 4, 2023: member

ACK 1e9684f39fba909b3501e9402d5b61f4bf744ff2

glozow commented at 3:08 pm on August 4, 2023: member

ACK 1a118062fbc4ec8f645f4ec4298d869a869c3344

DrahtBot requested review from naumenkogs on Aug 4, 2023

mzumsande commented at 8:22 am on August 7, 2023: contributor

My understanding is that there is a bit of a trade-off with respect to memory (correct me if the byte counting is off!): While it saves 33kB per peer (so ~4MB with 125 peers; ~250kB for non-listening nodes with 8 peers), it also adds at least 8 bytes per mempool entry for uint64_t entry_sequence. (for me, sizeof(CTxMemPoolEntry) even grows from 264 to 280 bytes - packing effects?). This seems a bit unsatisfactory because the entry_sequence data won’t be needed after a few seconds (i.e. after we’ve sent an inv to each peer).

Assuming a full mempool with ~150k mempool entries, that is between 1.2 and 2.4MB. Because this is included in the maxmempool limit, it’s effectively a decrease in mempool capacity instead of additional memory when the mempool is full.

I wonder if there would be a more memory-efficient way to achieve the same behavior - did you consider something like a global list of all recent transactions with timestamp, from which entries could get removed regularly (i.e., after we have sent an inv to each tx-relay peer).

ajtowns commented at 10:23 am on August 7, 2023: contributor

(for me, sizeof(CTxMemPoolEntry) even grows from 264 to 280 bytes - packing effects?)

Added a commit to fix this.

My understanding is that there is a bit of a trade-off with respect to memory (correct me if the byte counting is off!): While it saves 33kB per peer (so ~4MB with 125 peers; ~250kB for non-listening nodes with 8 peers), it also adds at least 8 bytes per mempool entry for uint64_t entry_sequence. [..] This seems a bit unsatisfactory because the entry_sequence data won’t be needed after a few seconds (i.e. after we’ve sent an inv to each peer).

Assuming a full mempool with ~150k mempool entries, that is between 1.2 and 2.4MB. Because this is included in the maxmempool limit, it’s effectively a decrease in mempool capacity instead of additional memory when the mempool is full.

Effectively, that’s a 0.4% increase in memory usage per tx (2000B per tx for 150k txs in 300MB becomes 2008B per tx for 149.4k txs in 300MB).

The main point here though is that with this change is for the case where we need to increase the number of (tx relay) peers or the tx acceptance rate – the former meaning we’d need to allocate more bloom filters, and the latter meaning we’d need each bloom filter to be significantly bigger (cf #27630).

I wonder if there would be a more memory-efficient way to achieve the same behavior - did you consider something like a global list of all recent transactions with timestamp, from which entries could get removed regularly (i.e., after we have sent an inv to each tx-relay peer).

I did think about that, but it seemed significantly more complicated – you’d need to either have a map of txid-to-sequence, or a map of txiter-to-sequence; the former would be wasting 24B per entry duplicating the txid, but the latter would need a lot of care to make sure there aren’t dangling references to txiters that have been removed from the mempool (and may be reallocated). You’d also need to regularly remove things from this map based on something like min(peer.last_inv) over each peer, which seems slightly awkward – the information in the mempool starts depending on p2p state, rather than just the txs that are in the mempool.

I do think those approaches would both result in measurable memory savings (1.2MB down to perhaps 100kB at 22tx/sec over 60 seconds?), but to me it just doesn’t seem worth the complexity overall.

mempool_entry: improve struct packing fb02ba3c5f

ajtowns force-pushed on Aug 7, 2023

DrahtBot added the label CI failed on Aug 7, 2023

DrahtBot removed the label CI failed on Aug 7, 2023

amitiuttarwar commented at 11:28 pm on August 9, 2023: contributor

review ACK fb02ba3c5f5

it’s been a while since I’ve hung out with mempool transaction code, so in addition to reading through the code I spent a good chunk of energy refreshing contextual behaviors. some context behind the ack:

thinking through if there is a meaningful shift in privacy model: I find these changes acceptable
understanding the memory tradeoff: this approach makes sense to me, esp with #27630 in the pipeline
re-familiarizing myself with how transactions enter the mempool
understanding how the mempool sequence number is handled
thinking through edge cases & understanding the ones flagged in prior review of this PR

tangential to this PR, but sharing since I noticed- m_sequence_number could be private and non mutable by removing the const from GetAndIncrementSequence (which doesn’t conceptually make sense anyway)

DrahtBot requested review from glozow on Aug 9, 2023

naumenkogs commented at 9:28 am on August 16, 2023: member

ACK fb02ba3c5f5bcd96b5e3622ef001b8e57ce63fc0

DrahtBot removed review request from naumenkogs on Aug 16, 2023

glozow commented at 7:27 pm on August 16, 2023: member

reACK fb02ba3c5f5bcd96b5e3622ef001b8e57ce63fc0

fanquake merged this on Aug 17, 2023

fanquake closed this on Aug 17, 2023

in src/validation.cpp:839 in a70beafdb2 outdated

833@@ -834,7 +834,10 @@ bool MemPoolAccept::PreChecks(ATMPArgs& args, Workspace& ws)
834         }
835     }
836 
837-    entry.reset(new CTxMemPoolEntry(ptx, ws.m_base_fees, nAcceptTime, m_active_chainstate.m_chain.Height(), m_pool.GetSequence(),
838+    // Set entry_sequence to 0 when bypass_limits is used; this allows txs from a block
839+    // reorg to be marked earlier than any child txs that were already in the mempool.
840+    const uint64_t entry_sequence = bypass_limits ? 0 : m_pool.GetSequence();

maflcko commented at 10:24 am on August 17, 2023:

a70beafdb22564043dc24fc98133fdadbaf77d8a: This seems fragile documentation-wise, because someone may assume the sequence number is both unique for any tx, and strictly monotonically increasing for any child tx. Both assumptions are violated here, and it could make sense to update the doxygen of CTxMemPoolEntry.m_sequence for that?

Also, may be better to drop the entry_ prefix from the CTxMemPoolEntry::entry_sequence member, since the scope is already clear from the surrounding class. Also, could drop the entry_ prefix from the constructor parameter name. Finally, could add the m_ prefix for class members for new code?

ajtowns commented at 2:35 am on August 18, 2023:

Unique for any tx and strictly monotonically increasing for child txs would also be violated for accepting packages to the mempool, I think.

glozow commented at 7:40 am on August 22, 2023:

Every tx submitted together in SubmitPackage has the same sequence number yes. But it should hold that if x is spent by y then x.sequence <= y.sequence.

maflcko commented at 10:57 am on August 17, 2023: member

lgtm, one doc nit.

Approach ACK fb02ba3c5f5bcd96b5e3622ef001b8e57ce63fc0, though I have not closely reviewed e4ffabbffacc4b890d393aafcc8286916ef887d8 🏁

Signature:

0untrusted comment: signature from minisign secret key on empty file; verify via: minisign -Vm "${path_to_any_empty_file}" -P RWTRmVTMeKV5noAMqVlsMugDDCyyTSbA3Re5AkUrhvLVln0tSaFWglOw -x "${path_to_this_whole_four_line_signature_blob}"
1RUTRmVTMeKV5npGrKx1nqXCw5zeVHdtdYURB/KlyA/LMFgpNCs+SkW9a8N95d+U4AP1RJMi+krxU1A3Yux4bpwZNLvVBKy0wLgM=
2trusted comment: Approach ACK fb02ba3c5f5bcd96b5e3622ef001b8e57ce63fc0, though I have not closely reviewed e4ffabbffacc4b890d393aafcc8286916ef887d8 🏁
3wZjhZp82DT5gvd1V2EbD+Lsejn1GZvm9++6dmmXGfe1v+61gbP3gMtecA9Vz94YNZ3KT8EyzjbMr83Tiw/rEBg==

sidhujag referenced this in commit 277f832b16 on Aug 17, 2023

in test/functional/mempool_reorg.py:98 in fb02ba3c5f

93+            assert_equal(peer1.last_message["tx"].tx.getwtxid(),tx_disconnected["tx"].getwtxid())
94+
95+        self.nodes[1].setmocktime(int(time.time()) + 30)
96+        peer1.sync_with_ping()
97+        # the transactions are now announced
98+        assert_equal(len(peer1.get_invs()), 3)

maflcko commented at 9:39 am on September 5, 2023:

This fails intermittently: https://cirrus-ci.com/task/5321300021870592?logs=ci#L3730

 02023-09-02T03:19:54.625000Z TestFramework (INFO): Test that transactions from disconnected blocks are available for relay immediately
 12023-09-02T03:19:55.970000Z TestFramework (ERROR): Assertion failed
 2Traceback (most recent call last):
 3  File "/ci_container_base/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/test/functional/test_framework/test_framework.py", line 131, in main
 4    self.run_test()
 5  File "/ci_container_base/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/test/functional/mempool_reorg.py", line 193, in run_test
 6    self.test_reorg_relay()
 7  File "/ci_container_base/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/test/functional/mempool_reorg.py", line 98, in test_reorg_relay
 8    assert_equal(len(peer1.get_invs()), 3)
 9  File "/ci_container_base/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/test/functional/test_framework/util.py", line 57, in assert_equal
10    raise AssertionError("not(%s)" % " == ".join(str(arg) for arg in (thing1, thing2) + args))
11AssertionError: not(0 == 3)

You will need to call sync_send_with_ping, not sync_with_ping.

maflcko commented at 9:40 am on September 5, 2023:

I wonder if sync_send_with_ping can be renamed to sync_with_ping to avoid this in the future.

maflcko commented at 10:13 am on September 5, 2023:

https://github.com/bitcoin/bitcoin/pull/28409

fanquake referenced this in commit cf421820f5 on Sep 6, 2023

Frank-GER referenced this in commit 285f33cff6 on Sep 8, 2023

fanquake referenced this in commit 1f352cf2fd on Dec 8, 2023

Fabcien referenced this in commit 2af41ff856 on Apr 15, 2024

bitcoin locked this on Sep 4, 2024

p2p: Drop m_recently_announced_invs bloom filter #27675

Reviews

Conflicts