-
Notifications
You must be signed in to change notification settings - Fork 37.7k
p2p: Drop m_recently_announced_invs bloom filter #27675
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Conversation
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers. ReviewsSee the guideline for information on the review process.
If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update. ConflictsReviewers, this pull request conflicts with the following ones:
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. |
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. |
f51fab0
to
9607a50
Compare
9607a50
to
9c4f60a
Compare
4f0075b
to
3d9d11f
Compare
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? |
553df8a
to
71078b3
Compare
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). |
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 After this patch, the logic above won't hold true anymore. If for whatever reason we have more than 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. |
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.
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.
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 |
Right, I don't think I originally fully understood what you meant by that. So the case is:
Provided
I don't think I follow here though. Would you mind elaborating? |
71078b3
to
096c0cc
Compare
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
ACK 1e9684f
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
ACK 1a11806
There was a problem hiding this 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).
Added a commit to fix this.
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 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 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. |
84fab3a
to
fb02ba3
Compare
There was a problem hiding this 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; } |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
is this used anywhere?
There was a problem hiding this comment.
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; |
There was a problem hiding this comment.
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?
ACK fb02ba3 |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
reACK fb02ba3
There was a problem hiding this 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(); |
There was a problem hiding this comment.
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?
There was a problem hiding this comment.
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.
There was a problem hiding this comment.
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) |
There was a problem hiding this comment.
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
.
There was a problem hiding this comment.
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.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
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
…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
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
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
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
andUNCONDITIONAL_RELAY_DELAY
and associated logic.