Do not answer GETDATA for to-be-announced tx

sipa commented at 7:20 am on May 4, 2020: member

This PR intends to improve transaction-origin privacy.

In general, we should try to not leak information about what transactions we have (recently) learned about before deciding to announce them to our peers. There is a controlled transaction dissemination process that reveals our transactions to peers that has various safeguards for privacy (it’s rate-limited, delayed & batched, deterministically sorted, …), and ideally there is no way to test which transactions we have before that controlled process reveals them. The handling of the mempool BIP35 message has protections in this regard as well, as it would be an obvious way to bypass these protections (handled asynchronously after a delay, also deterministically sorted).

However, currently, if we receive a GETDATA for a transaction that we have not yet announced to the requester, we will still respond to it if it was announced to some other peer already (because it needs to be in mapRelay, which only happens on the first announcement). This is a slight privacy leak.

Thankfully, this seems easy to solve: setInventontoryTxToSend keeps track of the txids we have yet to announce to a peer - which almost(*) exactly corresponds to the transactions we know of that we haven’t revealed to that peer. By checking whether a txid is in that set before responding to a GETDATA, we can filter these out.

(*) Locally resubmitted or rebroadcasted transactions may end up in setInventoryTxToSend while the peer already knows we have them, which could result in us incorrectly claiming we don’t have such transactions if coincidentally requested right after we schedule reannouncing them, but before they’re actually INVed. This is made even harder by the fact that filterInventoryKnown will generally keep known reannouncements out of setInventoryTxToSend unless it overflows (which needs 50000 INVs in either direction before it happens).

The condition for responding now becomes:

0  (not in setInventoryTxToSend) AND
1  (
2    (in relay map) OR
3    (
4      (in mempool) AND
5      (old enough that it could have expired from relay map) AND
6      (older than our last getmempool response)
7    )
8  )

fanquake added the label P2P on May 4, 2020

sipa added the label Privacy on May 4, 2020

DrahtBot commented at 7:52 am on May 4, 2020: member

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

Conflicts

No conflicts as of last run.

laanwj commented at 1:35 pm on May 4, 2020: member

Concept ACK

practicalswift commented at 2:03 pm on May 4, 2020: contributor

Concept ACK

amitiuttarwar commented at 6:16 pm on May 4, 2020: contributor

Concept ACK. code looks reasonable, just checks for presence on setInventoryTxToSend before sending the TX. I’ll review in more depth later this week, but one piece of feedback for the description

I got a bit confused by this part:

I believe it is however still possible to GETDATA a transaction that we have just learned about (from another peer, or from our local wallet), and answer it before we have announced it to the requesting peer.

An attempt to reword based on my understanding: if we recently learned about a transaction & a peer sends us a GETDATA before we announce it to them, we should not fulfill the request. That is a privacy leak.

in src/net_processing.cpp:1640 in 998d436337 outdated

1632@@ -1633,24 +1633,34 @@ void static ProcessGetData(CNode* pfrom, const CChainParams& chainparams, CConnm
1633             const CInv &inv = *it;
1634             it++;
1635 
1636+            bool too_recent = false;
1637+            {
1638+                // Check if the requested transaction is so recent that we're just
1639+                // about to announce it to the peer; if so, they certainly shouldn't
1640+                // know we already have it.

luke-jr commented at 8:06 pm on May 4, 2020:

setInventoryTxToSend isn’t only for initial broadcasts, though. At least the RPC method sendrawtransaction can add a transaction to it that has already been relayed previously.

sipa commented at 8:28 pm on May 4, 2020:

That’s a good point.

One possibility is making setInventoryTxToSend track a boolean determining if it’s a possible re-submission.

Another is just not caring. The entries in setInventoryTxToSend are filtered by filterInventoryKnown, so it won’t contain anything we know the other party already knows about. Of course, that filter is limited in size, but with 50000 entries I believe it can’t expire entries faster than after 47 minutes (50000 invs / 35 (invs / msg) * (2s / msg) = 2857s), long after the entries are gone from the relay map (from which they expire after 15 minutes).

In other words: this is worrying about the situation where (a) you announced an INV (b) at least 47 minutes passed, during which you respond to a BIP35 mempool request from the peer (c) you try to rebroadcast (d) in the few seconds after the rebroadcast is scheduled but before it’s sent out, you receive a GETDATA.

luke-jr changes_requested

luke-jr commented at 8:07 pm on May 4, 2020: member

Concept ACK, but I think this implementation is buggy:

naumenkogs commented at 2:13 am on May 5, 2020: member

Concept ACK.

jnewbery commented at 10:04 pm on May 6, 2020: member

Concept ACK. I agree with @amitiuttarwar that the PR description is confusing (you switch the perspective of ‘we’ being the node sending the GETDATA and ‘we’ being the node receiving it). PR descriptions end up in the merge commit, so it’d be good to fix that up.

I think that rather than adding another bool to the already complex ProcessGetData which only exists to skip over a code block, it’d be clearer to refactor the getdata tx processing into its own function. That turns your change into a two line fix.

I’ve done that here: https://github.com/jnewbery/bitcoin/tree/pr18861.1. Feel free to use it if you think it’s useful.

(The function signature for ProcessGetTransactionData() isn’t great, and I’d prefer to send individual NOTFOUND messages within that function instead of batching them, but that’s no longer a pure refactor and could be done later.)

sipa commented at 8:30 am on May 7, 2020: member

(The function signature for ProcessGetTransactionData() isn’t great, and I’d prefer to send individual NOTFOUND messages within that function instead of batching them, but that’s no longer a pure refactor and could be done later.)

It would be unfortunate to make the protocol implementation less efficient just because it results in slightly cleaner code. How about an alternative, where a helper function is introduced that just returns true or false, which ProcessGetData then calls to determine which request should be turned into a TX, and which batched into NOTFOUND (where the actual construction/sending of those messages remains in ProcessGetData)?

jnewbery commented at 4:16 pm on May 7, 2020: member

(apologies that this conversation has wandered off-topic for the fix in this PR)

It would be unfortunate to make the protocol implementation less efficient just because it results in slightly cleaner code.

Let me turn that around, and say “it would be unfortunate to make less clean code, in order to make the wire protocol infinitesimally more efficient.”

Remember that the notfound path is the rare, failure case. How rare? Here are some stats from my node’s first two peers:

 0> bcli getpeerinfo
 1[
 2  {
 3    "id": 0,
 4    [...]
 5    "bytessent_per_msg": {
 6      [...]
 7      "notfound": 122,
 8      [...]
 9      "tx": 212229,
10    },
11    "bytesrecv_per_msg": {
12      [...]
13      "notfound": 427,
14      [...]
15      "tx": 31755274,
16    }
17  },
18  {
19    "id": 1,
20    [...]
21    "bytessent_per_msg": {
22      [...]
23      "notfound": 1098,
24      [...]
25      "tx": 108708,
26    },
27    "bytesrecv_per_msg": {
28      [...]
29      "notfound": 926,
30      [...]
31      "tx": 93436726,
32    }
33  },
34[...]

Almost all notfound messages are 61 bytes (24 bytes header + 37 bytes data). Let’s assume that an average tx message is 250 bytes for header+data.

That means for my first two peers I sent/received ~42 notfound messages and sent/received ~500,000 tx messages.

Looking through my debug logs, the vast majority of notfound messages are 37 bytes, indicating a single item. So, for almost all calls of ProcessGetData(), there are zero or one notfound items, and batching has no effect on wire efficiency. Batching notfounds would save <100 messages per day for me (run grep "sending notfound" .bitcoin/debug.log | grep -v "37 bytes" to see for yourself).

In the adversarial case, it’s more expensive for us to serve transactions than notfounds, so being more efficient doesn’t protect us from any attacks.

Sending notfounds individually also has the nice effect of making getdata responses serial in the order we received them.

How about […] a helper function […] that just returns true or false

I think that’s better than the status quo, but I prefer delgating out to a function to do all the transaction GETDATA processing and message sending, so that it matches the responsibilities of ProcessGetBlockData() exactly.

sipa force-pushed on May 7, 2020

sipa commented at 6:28 pm on May 7, 2020: member

@jnewbery I’ve abstracted out a function for determining what tx requests to respond to. We can talk about further abstractions later. @amitiuttarwar I’ve also rewritten the PR description with a bunch of background information, and summarized the issue @luke-jr’s brought up above.

in src/net_processing.cpp:1622 in a00dae0108 outdated

1617+
1618+    auto mi = mapRelay.find(inv.hash);
1619+    if (mi != mapRelay.end()) {
1620+        // Send stream from relay memory
1621+        return mi->second;
1622+    } else {

jnewbery commented at 10:27 pm on May 7, 2020:

nit: no need for this else. The if clause returns early.

sipa commented at 10:54 pm on May 7, 2020:

Done, also reflowed the code a bit more.

jnewbery commented at 10:28 pm on May 7, 2020: member

utACK a00dae0108b50d951f8307cc63ee0353d3c5e712

sipa force-pushed on May 7, 2020

jnewbery commented at 1:27 am on May 8, 2020: member

utACK 353a391356fcf758f67683ecd2cbef759665b30b

naumenkogs commented at 1:41 pm on May 8, 2020: member

utACK 353a391 I like that we got rid of the push variable, looks cleaner now.

Do you think there can be timing analysis, to distinguish “it’s in the setInventoryTxToSend, not sharing with you” and “I couldn’t find it in the mempool”. Maybe I’m overthinking and mempool lookup is fast enough to not make any difference (should be same order as internet latencies or lower), but is that true for full mempools?

If really only applies to txs left MapRelay (but still in the mempool. (because I assume MapRelay lookups are very fast, unlike maybe mempool lookups).

jnewbery commented at 3:25 pm on May 8, 2020: member

Maybe I’m overthinking and mempool lookup is fast enough to not make any difference (should be same order as internet latencies or lower), but is that true for full mempools?

If really only applies to txs left MapRelay (but still in the mempool. (because I assume MapRelay lookups are very fast, unlike maybe mempool lookups).

Both mapRelay and mempool lookups should be fast. mapRelay is a map, so lookups are O(logn), but the map is small. Mempool lookups are by an unordered map of txid, so are O(1). We could make mapRelay an unordered map for O(1) lookups, but I think we probably just want to remove it entirely eventually (#17303).

in src/net_processing.cpp:1608 in 353a391356 outdated

1603@@ -1604,6 +1604,34 @@ void static ProcessGetBlockData(CNode* pfrom, const CChainParams& chainparams, c
1604     }
1605 }
1606 
1607+//! Determine whether or not a peer can request a transaction, and return a reference to it if so.
1608+Optional<CTransactionRef> static FindTxForGetData(CNode* peer, const CInv& inv, std::chrono::microseconds mempool_req, std::chrono::microseconds longlived_mempool_time) EXCLUSIVE_LOCKS_REQUIRED(cs_main)

amitiuttarwar commented at 8:09 pm on May 9, 2020:

nit: could update CInv& inv to be uint256& tx_hsh since function just uses inv to look up the hash 3 times?

sipa commented at 8:27 pm on May 12, 2020:

Agree, done.

in src/net_processing.cpp:1618 in 353a391356 outdated

1613+    {
1614+        LOCK(peer->m_tx_relay->cs_tx_inventory);
1615+        if (peer->m_tx_relay->setInventoryTxToSend.count(inv.hash)) return {};
1616+    }
1617+
1618+    // Send stream from relay memory

amitiuttarwar commented at 8:15 pm on May 9, 2020:

not sure what “stream” means here. mi will be an iterator to a uint256, CTransaction element on the map. I think this is a relic, but might be worth updating (or just removing) if you touch the code again.

sipa commented at 8:30 pm on May 12, 2020:

It’s a relic indeed. The relay pool used to store the serialized transaction stream rather than transaction objects. Fixed.

amitiuttarwar commented at 8:31 pm on May 9, 2020: contributor

code review ACK 353a391

a couple non-blocking nits / questions. probably not worth fixing unless you touch the code for other reasons
definitely like the code cleanup, its easier to reason about with less nested conditionals (although still a bit tricky.. I can’t wait to get rid of mapRelay! )
checked all the code paths of how a transaction could end up on setInventoryTxToSend
thought through possible unexpected cases that would lead to us incorrectly claiming we don’t have the transaction. agree that the likelihood is minuscule & don’t think the consequence would be dramatically negative, so the benefit far outweighs.
nice PR description :)

thanks!

jnewbery commented at 6:29 pm on May 11, 2020: member

This probably about ready for merge now, so no need to make any changes now, but would it make sense to just take cs_main inside FindTxForGetData()? It would mean taking and releasing the lock multilple times, but would avoid holding onto it while serializing and sending the TX message.

jonatack commented at 8:29 pm on May 11, 2020: member

ACK 353a391356f

I agree with Amiti’s and John’s latest comments for a follow-up or happy to re-ACK.

Abstract logic to determine whether to answer tx GETDATA c6131bf407

Push down use of cs_main into FindTxForGetData f2f32a3dee

sipa force-pushed on May 12, 2020

sipa commented at 8:31 pm on May 12, 2020: member

@jnewbery Done. Added a middle commit (review with -w) that pushes the cs_main lock down.

Additionally, got rid of the Optional; CTransactionRefs can already store a nullptr.

jonatack commented at 10:03 pm on May 12, 2020: member

re-ACK 2b3f101

naumenkogs commented at 10:14 pm on May 12, 2020: member

The solution doesn’t help if an attacker connects to us right after we put the transaction in MapRelay (by announcing to someone else).

I think the fix should be made as a follow-up. We discussed several alternatives with @sipa and it’s not a super-trivial fix to add it here right away.

This PR is still an improvement over existing behavior (now an attacker has to reconnect), and a nice refactor. utACK 2b3f101

sipa commented at 10:21 pm on May 12, 2020: member

Good find, @naumenkogs.

My thinking is that the best solution is actually introducing a separate rolling bloom filter (like filterInventoryKnown) for just outgoing announcements. It can be much smaller (we control the rate we announce things at, so given a limit of say 15 minutes to respond, there is an upper bound on the size), and then only permit GETDATA’ing things in that filter. I believe that can replace the setInventoryTxToSend test introduced here (while solving @luke-jr’s concern above). It would also make me more comfortable with dropping mapRelay (after fixing the rescheduling of downloads after a NOTFOUND).

I think the changes here are still an improvement, so I suggest going ahead with this if reviewers agree, and work on the above as a follow-up.

Do not answer GETDATA for to-be-announced tx 2896c412fa

sipa force-pushed on May 12, 2020

naumenkogs commented at 10:35 pm on May 12, 2020: member

utACK 2896c41

jonatack commented at 10:53 pm on May 12, 2020: member

ACK 2896c412fadbc03916 per git diff 2b3f101 2896c41 only change since previous review is moving the recency check up to be verified first in FindTxForGetData, as it was originally in 353a391 (good catch), before looking up the transaction in the relay pool.

sipa commented at 10:58 pm on May 12, 2020: member

@jonatack It was originally in the right place, I accidentally moved it in the push-cs_main-down change, which @naumenkogs discovered, so I quickly pushed again. Happy to see you and him discovering that; that’s a good sign for our review process.

jnewbery commented at 0:51 am on May 13, 2020: member

code review ACK 2896c412fadbc03916a33028f4f50fd87ac48edb

Very nice cleanup :)

fanquake requested review from amitiuttarwar on May 13, 2020

in src/net_processing.cpp:1612 in 2896c412fa

1607@@ -1608,6 +1608,37 @@ void static ProcessGetBlockData(CNode* pfrom, const CChainParams& chainparams, c
1608     }
1609 }
1610 
1611+//! Determine whether or not a peer can request a transaction, and return it (or nullptr if not found or not allowed).
1612+CTransactionRef static FindTxForGetData(CNode* peer, const uint256& txid, const std::chrono::seconds mempool_req, const std::chrono::seconds longlived_mempool_time) LOCKS_EXCLUDED(cs_main)

amitiuttarwar commented at 9:07 pm on May 14, 2020:

I’m trying to better understand the lock enforcements & have some questions..

I noticed that ProcessGetData has both LOCKS_EXCLUDED thread safety annotation as well as an AssertLockNotHeld check. I suspect its a product of development over time & is now redundant, but want to confirm my understanding.

LOCKS_EXCLUDED enables clang to do static analysis when we compile with the -Wthread-safety option. Does the travis build that says sanitizers: thread (TSan) run with this option?

I was trying to understand the limitations of the clang analysis. All I found was a lack of negative capabilities (aka can’t check if a function doesn’t have the excluded annotation), which doesn’t seem relevant here.

And then AssertLockNotHeld() looks like our custom logic that would do runtime assertions.

From a kind-of-clumsy search through git history, it looks like AssertLockNotHeld was added to ProcessGetData before the LOCKS_EXCLUDED annotation was. But it looks like threadsafety.h has defined LOCKS_EXCLUDED since 2014. So I can’t color the context of decisions.

To bring this back to this PR, my fundamental question is: what is the difference of guarantees between LOCKS_EXCLUDED and AssertLockNotHeld? Would there be a reason to add the second check as well?

sipa commented at 9:24 pm on May 14, 2020:

They’re somewhat orthogonal, I think.

Annotations:

[+] Is a compile-time check, and guarantee absence of issues in every possible code path
[-] Only works in clang
[-] Can’t be used in some more advanced locking scenarios

Assertions:

[+] Works in GCC and Clang
[+] Isn’t restricted to analyzable cases
[-] Is only a runtime check; it needs test cases that actually exercise the bug
[-] Needs building with -DDEBUG_LOCKORDER

Perhaps at some point it’s time to evaluate if we can pick just one over the other (which I guess would be the annotations approach), but they’re not exactly identical.

amitiuttarwar commented at 10:18 pm on May 14, 2020:

ok gotcha. thanks thats very helpful.

so assuming we regularly run the compile-time checks, for this specific case the guarantee from the annotations > guarantee from the assertion.

I don’t see any travis jobs that are running -Wthread-safety (and since my previous comment learned that clang thread safety analysis is different than the clang thread sanitizer)

does that mean if somebody added code that acquired cs_main and invoked FindTxForGetData, we’d be relying on a reviewer to either notice or compile with -Wthread-safety to raise an error?

I do see travis jobs that pass through -DDEBUG_LOCKORDER, so assuming we have good functional test coverage, throwing the assertion could cause a travis failure in that circumstance?

It might not be super important / worth invalidating ACKs to add the additional check. The lock expectations have been made very apparent and if new code tried to call this function with the lock acquired, I think we’d catch it in the review process. But on the other hand if we have tooling that reduces dependency on careful review, might as well use it?

I’m about ready to ACK this PR, just would like to make sure my understanding is clear

sipa commented at 10:26 pm on May 14, 2020:

I think configure.ac turns on -Wthread-safety-analysis and -Werror=thread-safety-analysis by default if the compiler supports it.

amitiuttarwar commented at 10:32 pm on May 14, 2020:

ah, thank you.

amitiuttarwar commented at 10:33 pm on May 14, 2020: contributor

code review ACK 2896c412fa

ajtowns commented at 5:11 am on May 19, 2020: member

ACK 2896c412fadbc03916a33028f4f50fd87ac48edb

fanquake commented at 7:12 am on May 19, 2020: member

Thanks for following up @ajtowns.

fanquake merged this on May 19, 2020

fanquake closed this on May 19, 2020

sidhujag referenced this in commit 633765e498 on May 19, 2020

in src/net_processing.cpp:1651 in f2f32a3dee outdated

1659-            if (pfrom->fPauseSend)
1660-                break;
1661+    // Process as many TX items from the front of the getdata queue as
1662+    // possible, since they're common and it's efficient to batch process
1663+    // them.
1664+    while (it != pfrom->vRecvGetData.end() && (it->type == MSG_TX || it->type == MSG_WITNESS_TX)) {

narula commented at 4:18 pm on July 8, 2020:

You are no longer holding cs_main. Why is it OK to access vRecvGetData here without a lock?

jnewbery commented at 5:03 pm on July 8, 2020:

vRecvGetData isn’t guarded by cs_main. In fact, it’s not guarded by anything 😱

All access of vRecvGetData is in ProcessMessages(), which only ever runs single threaded in the Message Handler thread, so this is safe, but ideally it’d be guarded by some synchronization method in case that ever changes.

narula commented at 5:26 pm on July 8, 2020:

Right. Previous to this commit, the mempool, vRecvGetData, and m_tx_relay were all accessed atomically under cs_main. This changes that and uses finer-grained locking.

I think all the other accesses are safe but I wasn’t certain about vRecvGetData.

sipa commented at 5:29 pm on July 8, 2020:

@narula Nice catch. Indeed, as @jnewbery says, it isn’t formally protected by anything right now. That’s fine because (a) it’s only accessed from one thread (b) every access to it actually holds cs_vRecv (just checked).

narula commented at 5:52 pm on July 8, 2020:

Could you point out where cs_vRecv is taken before vRecvGetData is accessed here? I only see it locked in two places in net.cpp, and I can’t connect either of them to ProcessMessages. The non-stats one is in ReceiveMsgBytes.

sipa commented at 5:54 pm on July 8, 2020:

~~net locks cs_vRecv and holds it while calling ProcessMessages. I checked by adding the annotation and recompiling.~~

EDIT: i’m wrong

narula commented at 7:31 pm on July 8, 2020:

ok! based on discussion in PR review club today I’ll PR a change to guard it by cs_vRecv, and look at orphan_work_set too. To be clear: there’s no data race now, but it’s worth fixing up in case these fields are accessed from multiple threads in the future.

fanquake referenced this in commit 5550fa5983 on Jul 14, 2020

sidhujag referenced this in commit 0090059f60 on Jul 14, 2020

lehuuhieu7777 approved

fanquake referenced this in commit c92aa8357c on Oct 19, 2020

sidhujag referenced this in commit 0075365b36 on Oct 19, 2020

Fabcien referenced this in commit db81f26de6 on Feb 4, 2021

DrahtBot locked this on Feb 15, 2022

Do not answer GETDATA for to-be-announced tx #18861

Conflicts