Skip to content

Conversation

ajtowns
Copy link
Contributor

@ajtowns ajtowns commented May 16, 2023

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
Copy link
Contributor

DrahtBot commented May 16, 2023

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
Copy link
Contributor Author

ajtowns commented May 16, 2023

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.

@sdaftuar
Copy link
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 ajtowns force-pushed the 202305-droprecentinvbloom branch 2 times, most recently from 553df8a to 71078b3 Compare May 23, 2023 10:54
@sr-gi
Copy link
Member

sr-gi commented May 23, 2023

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
Copy link
Member

sr-gi commented May 31, 2023

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
Copy link
Contributor Author

ajtowns commented Jun 2, 2023

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
Copy link
Member

sr-gi commented Jun 2, 2023

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 ajtowns force-pushed the 202305-droprecentinvbloom branch from 71078b3 to 096c0cc Compare June 3, 2023 01:11
@DrahtBot DrahtBot removed the CI failed label Aug 3, 2023
Copy link
Member

@naumenkogs naumenkogs left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

ACK 1e9684f

Copy link
Member

@glozow glozow left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

ACK 1a11806

@DrahtBot DrahtBot requested a review from naumenkogs August 4, 2023 15:08
Copy link
Contributor

@mzumsande mzumsande left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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
Copy link
Contributor Author

ajtowns commented Aug 7, 2023

(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.

@ajtowns ajtowns force-pushed the 202305-droprecentinvbloom branch from 84fab3a to fb02ba3 Compare August 7, 2023 10:24
Copy link
Contributor

@amitiuttarwar amitiuttarwar left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

review ACK fb02ba3

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)

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

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

is this used anywhere?

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

No, it's not

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

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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?

@DrahtBot DrahtBot requested a review from glozow August 9, 2023 23:28
@naumenkogs
Copy link
Member

ACK fb02ba3

@DrahtBot DrahtBot removed the request for review from naumenkogs August 16, 2023 09:28
Copy link
Member

@glozow glozow left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

reACK fb02ba3

Copy link
Member

@maflcko maflcko left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

lgtm, one doc nit.

Approach ACK fb02ba3, though I have not closely reviewed e4ffabb 🏁

Show signature

Signature:

untrusted 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}"
RUTRmVTMeKV5npGrKx1nqXCw5zeVHdtdYURB/KlyA/LMFgpNCs+SkW9a8N95d+U4AP1RJMi+krxU1A3Yux4bpwZNLvVBKy0wLgM=
trusted comment: Approach ACK fb02ba3c5f5bcd96b5e3622ef001b8e57ce63fc0, though I have not closely reviewed e4ffabbffacc4b890d393aafcc8286916ef887d8 🏁
wZjhZp82DT5gvd1V2EbD+Lsejn1GZvm9++6dmmXGfe1v+61gbP3gMtecA9Vz94YNZ3KT8EyzjbMr83Tiw/rEBg==

entry.reset(new CTxMemPoolEntry(ptx, ws.m_base_fees, nAcceptTime, m_active_chainstate.m_chain.Height(), m_pool.GetSequence(),
// Set entry_sequence to 0 when bypass_limits is used; this allows txs from a block
// reorg to be marked earlier than any child txs that were already in the mempool.
const uint64_t entry_sequence = bypass_limits ? 0 : m_pool.GetSequence();
Copy link
Member

@maflcko maflcko Aug 17, 2023

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

a70beaf: 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?

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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.

self.nodes[1].setmocktime(int(time.time()) + 30)
peer1.sync_with_ping()
# the transactions are now announced
assert_equal(len(peer1.get_invs()), 3)
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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

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

You will need to call sync_send_with_ping, not sync_with_ping.

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

fanquake added a commit that referenced this pull request Sep 6, 2023
fae0b21 test: Combine sync_send_with_ping and sync_with_ping (MarcoFalke)

Pull request description:

  This reduces bloat, complexity, and makes tests less fragile to intermittent failures, see #27675 (comment).

  This should not cause any noticeable slowdown, or may even be faster, because active polling will be done at most once.

ACKs for top commit:
  glozow:
    Concept ACK fae0b21
  theStack:
    ACK fae0b21 🏓

Tree-SHA512: 6c543241a7b85458dc7ff6a6203316b80a6227d83d38427e74f53f4c666a882647a8a221e5259071ee7bb5dfd63476fb03c9b558a1ea546734b14728c3c619ba
Frank-GER pushed a commit to syscoin/syscoin that referenced this pull request Sep 8, 2023
…ping

fae0b21 test: Combine sync_send_with_ping and sync_with_ping (MarcoFalke)

Pull request description:

  This reduces bloat, complexity, and makes tests less fragile to intermittent failures, see bitcoin#27675 (comment).

  This should not cause any noticeable slowdown, or may even be faster, because active polling will be done at most once.

ACKs for top commit:
  glozow:
    Concept ACK fae0b21
  theStack:
    ACK fae0b21 🏓

Tree-SHA512: 6c543241a7b85458dc7ff6a6203316b80a6227d83d38427e74f53f4c666a882647a8a221e5259071ee7bb5dfd63476fb03c9b558a1ea546734b14728c3c619ba
fanquake added a commit that referenced this pull request Dec 8, 2023
97c0dfa test: Extends MEMPOOL msg functional test (Sergi Delgado Segura)

Pull request description:

  Currently, p2p_filter.py::test_msg_mempool is not testing much. This extends the tests so the interaction between sending `MEMPOOL` messages with a filter that does not include all transactions in the mempool reacts, plus how it interacts with `INV` messages, especially after the changes introduced by #27675

ACKs for top commit:
  instagibbs:
    ACK 97c0dfa
  theStack:
    re-ACK 97c0dfa

Tree-SHA512: 746fdc867630f40509e6341f484a238dd855ae6d1be5eca121974491e4ca272dee88af4b90dda55ea9a5a19cbff198fa91ffa0c5bf1ddf0232b2c1b215b05b9a
Fabcien pushed a commit to Bitcoin-ABC/bitcoin-abc that referenced this pull request Apr 15, 2024
Summary:
This reduces bloat, complexity, and makes tests less fragile to intermittent failures.

This is a backport of [[bitcoin/bitcoin#28409 | core#28409]]

Note: I don't know if this already fixes any existing intermittent failure, but at least it will prevent introducing a new one when backporting [[bitcoin/bitcoin#27675 | core#27675]]

Test Plan: `ninja check-functional`

Reviewers: #bitcoin_abc, Fabien

Reviewed By: #bitcoin_abc, Fabien

Differential Revision: https://reviews.bitcoinabc.org/D15979
@bitcoin bitcoin locked and limited conversation to collaborators Sep 4, 2024
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
Projects
None yet
Development

Successfully merging this pull request may close these issues.