The PR branch HEAD was 2da7ee37b at the time of this review club meeting.
Notes
If a spy is able to identify which node initially broadcast a transaction,
there’s a high probability that that node is the source wallet for the
transaction.
To avoid that privacy leak, we try to be intentional about how we relay and request transactions. We
don’t want to reveal the exact contents of our mempool or the precise timing
when we received a transaction.
PR 18861 improved
transaction-origin privacy. The idea is that if we haven’t yet announced a
transaction to a peer, we shouldn’t fulfill any GETDATA requests for that
transaction from that peer.
The implementation for that PR checks the list of transactions we are about to
announce to the peer (setInventoryTxToSend), and if it finds the transaction
that the peer has requested, then responds with a NOTFOUND instead of with the transaction. While this helps in many cases,
it is an imperfect heuristic. Think about why that is (see question 3 below).
This week’s PR further reduces the possible attack surface. It introduces a
per-peer rolling bloom filter (m_recently_announced_invs) to track which
transactions were recently announced to the peer. When the peer requests a
transaction, we check the filter before fulfilling the request and relaying the
transaction.
<michaelfolkson> So my (limited) understanding is that the previous PR fixed a lot of the premature announcement logic. And so now we are working out what still needs to be fixed
<amiti> from the notes: PR 18861 improved transaction-origin privacy. The idea is that if we haven’t yet announced a transaction to a peer, we shouldn’t fulfill any GETDATA requests for that transaction from that peer. The implementation for that PR checks the list of transactions we are about to announce to the peer (setInventoryTxToSend), and if it
<amiti> finds the transaction that the peer has requested, then responds with a NOTFOUND instead of with the transaction. While this helps in many cases, it is an imperfect heuristic.
<troygiorshev> The issue in sipa's original PR description is a "false negative" sort of problem, right? i.e. we'll tell a node that we don't have a transaction even when they know that we actually do?
<sipa> overall: well, memory usage - we could also just keep a list of all things we've ever announced to a peer, and only allow them to query exactly that... but that would easily run into memory problems
<jnewbery> so using the old heuristic, if a node connects to us and immediately asks for a transaction, it won't be in the setInventoryTxToSend, and we'll happily send the transaction
<michaelfolkson> overall: Yeah I think it is just privacy. Apart from privacy, announcing prematurely doesn't matter. Unless you literally don't want to be announcing it at all (not a concern)
<andrewtoth> still a little unclear on the second point though. how does using setInventoryTxToSend prevent some locally resubmitted invs from being requested?
<amiti> andrewtoth: the idea is if we are using setInventoryTxToSend to prevent fulfilling a txn request, if we put a txn on there for a _second_ time, then it would be valid for the peer to request (since we prev announced), but we would deny them the txn
<michaelfolkson> sipa: Not permitting the providing of what they request right? They are free to request whatever they want. Just don't want to give it to them
<amiti> sipa: my understanding of your comment there was that you were identifying the precise steps / timing that would have to happen to not serve the txn, is that correct?
<luke-jr> amiti: unless I'm confusing my own comment (it's been a while), it seems sendrawtransaction (ie, the user explicitly wants to relay it) could end with it not being relayed even if it would have otherwise been?
<sipa> andrewtoth: an analogy i like: a civilian engineer designs building resistant to natural causes (earthquakes, ...), and needs probability. a military engineer designs structures that are designed to protect against attacks; they don't go compute the probability that a missile will randomly hit it; they care about how hard it is for an attack that make that happen
<amiti> ok, so these are some of the identified drawbacks of using `setInventoryTxToSend` as a heuristic. what does PR 19109 implement as an alternative solution?
<jnewbery> felixweiss_k: without having specific numbers, I think a good rule is that keeping sets of items per-peer isn't scalable, but keeping a probabilistic filter is
<sipa> or, alternatively, actual acconting of memory, and a way to deprioritize/disconnect peer if we're using to much memory on behalf of a peer, and it gets tight
<jnewbery> sipa: I think deprioritizing based on memory usage would be difficult. How do you shed the memory? Deprioriritizing based on CPU/bandwidth usage seems much easier
<amiti> lets jump into this question: What are some relevant considerations when reviewing/implementing a bloom filter? What choices does this patch make?
<jnewbery> and we roll through the different filters (ie put items into the first filter until it's at capacity, then the second, then the third, then delete the first filter and start filling it again)
<felixweis_k> when you add, you add to the latest 2, when you check you check for OR in any of the 3? then a counter as to when advance the "ring buffer"?
<sipa> but also a factor 2 again because we need 2 bits per entry (which can store a number from 0 to 3... 0 for unused; 1-3 for each of the 3 generations)
<jnewbery> felixweiss_k: you only add to the latest generation I believe. And yes, there's a counter to determine which generation we should be adding to
<sipa> because we might have forgotten some protocol interaction where someone ends up legitimately requesting something that the filter approach disallows
<nehan> jnewbery: vRecvGetData isn't protected by cs_vRecv. But as you both pointed out it's only accessed in one thread. That seems worth documenting to me though.
<jnewbery> vRecvGetData and orphan_work_set are similar - they're both work queues for an individual peer. As such they're only pushed to/popped from in ProcessMessages
<amiti> a__jonas, troygiorshev: that conversation calculated the number of transactions in 15 minutes, because after 15 minutes is the time set by mapRelay. after that review, sipa introduced `UNCONDITIONAL_RELAY_DELAY` as 2 mins. so now, if a peer requests a txn thats >2 minutes old, we will serve
<sipa> jnewbery: so, you're right - the memory usage of the rolling bloom filter (which i'll completely unambiguously abbreviate to RBF) is indeed exactly equal to having 3 completely separate bloom filters
<jnewbery> sipa: I haven't looked at the implementation recently, but do the 3 bloom filters use the same hash functions? If so, my comment ("3x constant factor in checking for membership") isn't correct because you'd only do the hashing once