Stop relaying non-mempool txs, improve tx privacy slightly (
p2p) Nov 13, 2019
Transactions in Bitcoin are gossiped by
inv messages (a list of tx hashes) after they have been validated by the node. Peers can respond to these
messages with a
getdata message to request the transaction.
Bitcoin Core keeps a “relay memory” of all transactions that were sent out as
invs for 15 minutes.
requests are answered from this relay memory.
A recent change (#16851) in the
master branch of Bitcoin Core
enables relay of transactions that have been removed from the relay memory. The motivation for this change was that
low fee transactions that either didn’t make the inital relay or were evicted later on can now be requested. This
allows for example to bump a low fee transaction higher in the mempool with a CPFP transaction.
Also, it makes it possible for nodes to catch up on parent transaction when the node has been started with an empty
Transactions that made it into the relay memory stay there for 15 minutes, even if they have been included in a block
or have been replaced by a higher fee transaction in the mempool.
The proposed change
(#17303)) removes the relay memory and uses the mempool exclusively as
the relay memory. The change claims to improve privacy. Questions
Did you review the PR?
Concept ACK, approach ACK, tested ACK, or
(Don’t forget to put your PR review on GitHub.)
What steps did you take, beyond reading the code?
What is a shared pointer and why are transactions in Bitcoin Core generally managed as a shared pointer
What is the difference between the memory pool (
mempool) and the relay memory (
Is there an upper bound on the memory usage of the relay memory (
mapRelay)? Under what circumstances is the expected
memory usage low, under what circumstances is the memory usage high? (Hint:
CTransactionRef is a shared pointer)
Transactions are added to
mapRelay when they are announced via an
mapRelay keep track of which peers
it announced a transaction to? If no, how does that affect transaction relay privacy?
Are there any remaining transaction relay privacy issues after this change?
Do you think this change can be tested efficiently with unit or functional tests and why?
1 13:00 <@jnewbery> #startmeeting
6 13:00 <coma-shuffling> hi
12 13:00 <@jnewbery> Hi folks. MarcoFalke has very kindly offered to host this week. I'll say a few words and then hand over to him.
13 13:00 <@jnewbery> First, I wanted to repeat what I said last week about using this channel.
14 13:00 <@jnewbery> Please just jump right in! The host will prompt the conversation with the questions at https://bitcoincore.reviews/, but don't feel like you need to wait until after those questions to make your comment or ask your question.
16 13:01 <@jnewbery> You're not being rude if the host asks a question and you make an unrelated comment!
17 13:01 <@jnewbery> We can have multiple threads going at the same time. If it gets too confusing the host can step in and ask people to address one topic first, but in general just go for it.
18 13:01 <@jnewbery> Also, don't ask to ask questions. There's no need to say things like "I have a question that I think might be off topic" or "is it ok if I ask my question now?". Just jump right in and ask. If it's off-topic, then people will tell you!
21 13:01 <@jnewbery> There were a couple of questions asked before the meeting. I'll repeat them here so they make it to the meeting log.
22 13:01 <@jnewbery> < pinheadmz> 1 why is the loglevel for the testframework not `debug` (or even `spam`) by default? Today's PR modifies a test where I found the `debug` level output especially helpful
23 13:01 <@jnewbery> < pinheadmz> 2 the python tests often have random elements or non-deterministic elements. Today's test runs 100 times and breaks once a certain case is found -- 100 iterations make the expected behavior very likely, but couldn't the tests be written more acutely?
24 13:01 <@jnewbery> < MarcoFalke> re 1) log level of debug by default would be a bit spammy in the normal case (no failures expected). If you debug a test, you are assumed to either set -l DEBUG or combine the logs after a failure has been detected, in which case the debug messages are included as well
25 13:01 <@jnewbery> < MarcoFalke> re 2) let's discuss that in the meeting
26 13:01 <@jnewbery> ok, that's all I had to say. Over to Marco...
27 13:02 <MarcoFalke> hi, so let's get started with the basics. Everyone is familiar with how tx relay works in Bitcoin?
28 13:02 <MarcoFalke> Any questions about the gossip protocol?
31 13:03 <MarcoFalke> Ok, jumping into the questions, then
32 13:04 <MarcoFalke> So let's start by the general goal of this pull request
33 13:04 <MarcoFalke> Anyone want to take a try at giving a brief summary?
35 13:05 <pinheadmz> seems like, there is this mapRelay where we kinda buffer TXs even after theyve been evicted from the mempool, for up to 15 minutes
36 13:05 <pinheadmz> This PR takes that out - so if a peer requests a tx that isnt STILL in the mempool, they get a notfound back
37 13:05 <coma-shuffling> reduce resource load, some privacy improvments?
38 13:06 <MarcoFalke> both correct
39 13:06 <pinheadmz> I dont understand what the mapRelay was used for beore this PR - the change makes so much sense !
40 13:06 <ajonas> So relay transaction seems like sort of an odd thing (was added for caching purposes?) and generally removing it simplifies the logic but also I'm a little unclear as to why this was added in the beginning
41 13:06 <@jnewbery> I had the same question. Why didn't we always just relay from the mempool? Privacy/fingerprinting concerns?
43 13:07 <MarcoFalke> mapRelay has been introduced before I was around, so I might not be able to answer that question with certainty
44 13:08 <jasonzhouu> Is relay momory mainly used to increase privacy, comparing to memery pool?
45 13:08 <@jnewbery> as a tip for code excavation, `git log -S <string>` shows all commits where that string is part of the diff
46 13:08 <@jnewbery> if I run `git log -SmapRelay`, I see that it was there in the first commit
47 13:09 <MarcoFalke> Previously transactions have been copied around in full, and CTransactionRef was introduced later on
48 13:09 <pinheadmz> jnewbery: cool trick tnx! and interesting its so old
49 13:09 <pinheadmz> who's sirius-m ?!
50 13:09 <MarcoFalke> It might have been neccessary in the early design of Bitcoin Core to have a copy of the tx around
51 13:10 <MarcoFalke> I think sirius has transformed the svn repo into a git repo
52 13:10 <ariard> isn't mapRelay a reason to be a useful tx relay peer if you have a mempool set to 0?
53 13:10 <ariard> or before than mempool was operational?
54 13:10 <@jnewbery> sirius is Martii Malmi. I think he was the second contributor to Bitcoin after Satoshi
55 13:11 <MarcoFalke> ariard: transactions are only added to mapRelay after they made it into the mempool
56 13:11 <fjahr> I did not dig deeper into this but on some level it made sense to me to decouple mempool behavior from relay behavior for privacy reasons.
57 13:11 <coma-shuffling> jnewbery correct
58 13:11 <@jnewbery> ariard: you can't relay transactions without a mempool
59 13:12 <@jnewbery> AcceptToMemoryPool is where we do our standardness checks
60 13:12 <ariard> jnewbery, MarcoFalke: looking on first git commit, seems mapRelay was already there
61 13:13 <MarcoFalke> fjahr: Good point. However, I think mempool and relay are too closely coupled to achieve good tx-origin privacy . There are a lot of tricks you can play to leak privacy
62 13:13 <pinheadmz> also interesting that the old txs in the maprelay arent pruned on a timeout or anything, just when sendMessages() is called
63 13:13 <pinheadmz> (IIUC)
64 13:14 <@jnewbery> pinheadmz: right, it's lazy deletion
65 13:14 <MarcoFalke> pinheadmz: The send messages function is called in a tight loop anyway, so it is close enough to a timeout
67 13:16 <MarcoFalke> I think the main goal of the mapRelay expiry is to have some upper bound on its memory usage, which is achieved by the tight loop. (To some extend)
68 13:17 <MarcoFalke> Ok, my first question:
69 13:17 <MarcoFalke> What is a shared pointer and why are transactions in Bitcoin Core generally managed as a shared pointer (CTransactionRef)?
70 13:17 <coma-shuffling> It's referenced in relation to "CRITICAL_BLOCK" parts
71 13:18 <ajonas> shared_ptr is a smart pointer that retains shared ownership of an object through a pointer.
72 13:18 <ajonas> google!!
73 13:18 <jkczyz> It is a smart pointer that uses reference counting to determine when the memory can be deleted
74 13:19 <MarcoFalke> Yes, so why are transactions in bitcoin core managed that way?
75 13:19 <ajonas> because they are managed in a few different places
76 13:19 <jonatack> MarcoFalke: with a shared_ptr as opposed to a unique_ptr?
77 13:20 <fjahr> and because it saves memory
78 13:20 <MarcoFalke> fjahr: Yes
79 13:20 <jkczyz> Someone decided to punt on ownership :P
80 13:20 <jonatack> yes, when you heap-allocate a resource that needs to be shared among multiple objects
81 13:20 <MarcoFalke> jonatack: Good question! any takers?
82 13:21 <jonatack> there was a PR review discussion on this between sipa/gmax and jonas schnelli recently
83 13:21 <jkczyz> jonatack: Do you have a reference? I'd be intereted in reading
84 13:22 <jonatack> shared = more flexibility but more going on so slight perf hit, iirc
85 13:22 <jonatack> wrt unique
86 13:22 <MarcoFalke> jonatack: It is a shared_ptr to minimize mental load. I think a unique_ptr makes most sense when there is exaclty one owner, but in Bitcoin Core there can be many owners of a single transaction: E.g. (1) the most recent block, (2) the mempool, (3) mapRelay, (4) anything I forgot?
88 13:23 <ajonas> am I right with a unique pointer once it's destroyed in one place it is reclaimed, but shared is all have to destroy it in order to deallocate?
89 13:23 <jonatack> jnewbery: yes, ty!
90 13:23 <MarcoFalke> (4) the miner
91 13:23 <jonatack> jnewbery: please give a masterclass on finding things quickly in GH :)
93 13:24 <MarcoFalke> ajonas: The shared pointer uses a reference count as pointed out by jkczyz. This is a slight overhead over unique_ptr, but gives more flexibility
94 13:24 <MarcoFalke> The shared pointer releases the memory when the count goes to 0
95 13:25 <jonatack> jnewbery: oh ty, using the PR filters in the GH web interface. will use that more.
96 13:25 <ajonas> marcofalke: OK. Guess I didn't quite get that.
97 13:26 <MarcoFalke> so unique_ptr is like a shared_ptr where the count can only be 0 or 1 exactly
98 13:26 <MarcoFalke> ok, going to the next question
99 13:26 <MarcoFalke> What is the difference between the memory pool (mempool) and the relay memory (mapRelay)?
100 13:27 <pinheadmz> one thing for sure, made clear by this PR: mempool txs can be evicted for several reasons. the maprealy just expires after a set time
101 13:27 <MarcoFalke> pinheadmz: Correct
102 13:27 <MarcoFalke> Any other ideas what is different between them?
103 13:28 <ariard> the mempool is a storage for unconf txn to help block construction
104 13:28 <MarcoFalke> Or rather: What is common between them?
105 13:28 <jasonzhouu> relay memory needs `inv`
106 13:28 <ariard> it also serves for fee estimation and tx relay
107 13:28 <MarcoFalke> jasonzhouu: Right. Transactions are only added to the relay memory after the first inv for the tx has been sent out
108 13:28 <MarcoFalke> ariard: Correct
109 13:29 <fjahr> mempool can be restricted in size and maprelay not I think
110 13:29 <ariard> so there is an overlap between goals of both rn
111 13:29 <MarcoFalke> fjahr: Good point. Can you explain why?
112 13:29 <pinheadmz> i wonder if the original design was mempool would just be for cooking up blocks, and maprelay was for p2p ?
113 13:30 <MarcoFalke> Or let's start easy: Can it be that the mempool and mapRelay have the same transactions in them?
114 13:30 <ariard> there is a maxmempool option to restrict size
116 13:30 <amiti> mapRelay will only have txns that have been previously accepted to the mempool, but they might no longer be there..
117 13:30 <ariard> pinheadmz: yep was my wonder earlier
118 13:30 <jasonzhouu> If mempool don't has limit size, then there is posibility of DoS attack.
119 13:30 <fjahr> during the first 15min after startup anyway
120 13:30 <amiti> I think the reason theres no explicit constraint on mapRelay is bc its implicit with size of mempool + time out ?
121 13:31 <MarcoFalke> amiti: Yes, sort of
123 13:32 <MarcoFalke> Good old days when 0.11.0 nodes ran OOM
124 13:32 <@jnewbery> prior to that you could OOM a node by filling up its mempool
125 13:32 <MarcoFalke> Even with txs that pay no fee :)
126 13:32 <fjahr> the point of the maprelay is to help with relay and so restricting it would hinder it so that would work against that goal
127 13:33 <pinheadmz> jnewbery: no surprise, there was no volume back then :-)
128 13:33 <MarcoFalke> ok, next question: Is there an upper bound on the memory usage of the relay memory (mapRelay)? Under what circumstances is the expected memory usage low, under what circumstances is the memory usage high? (Hint: CTransactionRef is a shared pointer)
129 13:33 <@jnewbery> At a high level, I'd answer the question by saying that the mempool has a lot more structure than mapRelay
130 13:33 <jonatack> jnewbery: was that the vuln demoed live onstage in 2016 at Breaking Bitcoin in Paris?
131 13:34 <MarcoFalke> jnewbery: Also good point
132 13:34 <@jnewbery> jonatack: no, that was something different
133 13:34 <amiti> MarcoFalke: could you elaborate on "Yes, sort of"? what is correct / what am I missing ?
134 13:34 <MarcoFalke> amiti: You are correct
135 13:34 <@jnewbery> the mempool should always be consistent (ie the entire mempool can be made into a valid block if we ignore block weight limits)
136 13:35 <@jnewbery> the mempool is also indexed in various ways that are useful for its clients
137 13:35 <MarcoFalke> ok, let's move on to the next question
138 13:35 <MarcoFalke> Is there an upper bound on the memory usage of the relay memory (mapRelay)?
140 13:36 <MarcoFalke> amiti already gave an answer, but could someone elaborate the point
141 13:36 <ariard> there is an upper bound based on time and not on size, compare to the mempool
142 13:37 <MarcoFalke> ajonas: Good point. That is one way to look at it. Does that give us nice estimates about the memory usage of mapRelay?
143 13:38 <MarcoFalke> ariard: Good point. But why is it not on size? Note that transactions are only added to mapRelay after they entered the mempool?
144 13:39 <pinheadmz> hmm all this talk about sahred pointers - maprealy shouldn't increase mem usage at all except in the case that mempool evicts a tx that maprelay still hangs on to
145 13:39 <amiti> could mapRelay theoretically increase memory usage a lot if theres a lot of churn in the mempool? eg. small mempool and txns are getting INVed but then kicked out really rapidly
146 13:40 <jasonzhouu> The max of relay memory is txs that have ever been included in mempool?
147 13:40 <jasonzhouu> in the last 15 minutes
148 13:40 <MarcoFalke> pinheadmz: Yes. Though, we store the txid and expiry time.
149 13:40 <MarcoFalke> amiti: Yes.
150 13:41 <MarcoFalke> jasonzhouu: Yes
151 13:41 <ariard> MarcoFalke: because there is an assumption than size of mapRelay can't be bigger than mempool one due to dependency of former on latter ?
152 13:42 <@jnewbery> ariard: I'm not sure if there's any such assumption (and if there were, it'd be invalid because of the reason amiti said)
153 13:42 <MarcoFalke> So under what circumstances are txs evicted from the memory?
154 13:42 <MarcoFalke> *mempool
155 13:42 <amiti> for the reasons you listed in the PR description ... :)
156 13:42 <MarcoFalke> amiti: heh
157 13:42 <amiti> expiry, size limit, reorg, block, conflict, replaced
158 13:42 <pinheadmz> RBF, blcok inclusion, mempool size limit
159 13:43 <amiti> I have some questions about concerns that reviewers brought up...
160 13:43 <jasonzhouu> 1. be included in block
161 13:43 <amiti> sdaftuar mentions these changes can turn nodes with small mempools into "accidental DoSers", which I didn't fully understand.. so a node would send an INV to its peer, peer asks for GETDATA, during that time the txn has been evicted from the node's mempool so then it responds with NOTFOUND. why is this a DoS though? is it bc the peer waits until the request times out before asking another node for the tx?
162 13:43 <jasonzhouu> 2. be replaced by higher fee tx
163 13:44 <MarcoFalke> On a high level I found that rbfed txs and txs included in blocks were the primary reason that mapRelay uses more memory than the mempool
164 13:44 <MarcoFalke> (Assuming the mempool does not operate on its size limit)
165 13:44 <MarcoFalke> amiti: Good question!
166 13:44 <pinheadmz> That alone is a great reason for this PR - why relay a tx that has already been RBF'd
167 13:45 <amiti> ^ maybe because of privacy reasons, as mentioned from naumenkogs review
168 13:45 <MarcoFalke> amiti: You answered that question yourself: "the peer waits until the request times out before asking another node for the tx"
169 13:45 <jonatack> MarcoFalke: how did you find that?
170 13:46 <MarcoFalke> jonatack: Run a Bitcoin Core full node with some added LogPrintf calls
171 13:46 <jonatack> "net" logging too?
172 13:46 <MarcoFalke> amiti: more specifically, we ignore NOTFOUND from peers to the extend that we don't use them to reschedule the tx download from a different peer
175 13:47 <MarcoFalke> Ok, moving to the next question
176 13:47 <MarcoFalke> Transactions are added to mapRelay when they are announced via an inv. Does mapRelay keep track of which peers it announced a transaction to? If no, how does that affect transaction relay privacy?
177 13:48 <amiti> jnewbery, MarcoFalke: thanks :)
178 13:49 <pinheadmz> we dont
179 13:49 <ajonas> MarcoFalke: I don't believe it does keep track, which is what Gleb is proposing with a bloom filter to track it.
180 13:49 <pinheadmz> mapRelay.insert(std::make_pair(hash, std::move(txinfo.tx)));
181 13:49 <amiti> I believe this PR added the param `m_last_inv_sent` to keep track of the time the last set of INVs was announced to a peer, but doesn't keep track of specifically which one
183 13:50 <MarcoFalke> pinheadmz: ajonas: Is the issue in the current code or is that introduced in my change?
184 13:50 <MarcoFalke> And how does it affect privacy?
185 13:50 <ajonas> current
186 13:50 <MarcoFalke> I.e. what is the attack scenario?
187 13:50 <pinheadmz> yeah maprealy is kinda dumb, just a list of txs, no peer info
188 13:51 <ajonas> means it's still vulnerable to inferring your location in the tx relay network topology
189 13:51 <MarcoFalke> How would you leak that?
190 13:51 <pinheadmz> but i feel like i must be missing something, bc we woldnt send the same tx to a peer twice, or if it was the peer that sent it to us in the first place...
191 13:52 <MarcoFalke> pinheadmz: We do (if they send a GETDATA twice)
193 13:52 <jonatack> flooding with the same tx iiuc
194 13:52 <ajonas> basically flood network with tx_a and then selectively announce tx_b (RBF of tx_a). Start querying for tx_a - whoever responds with NOTFOUND received tx_b which means the node is closer to the node target.
195 13:53 <pinheadmz> ajonas: wouldnt that be the behavior AFTER this is merged?
196 13:53 <MarcoFalke> ajonas: Yes. And the privacy leak that allows us to infer the source of a transaction? (current master code)
197 13:53 <MarcoFalke> Yeah, sorry. I was asking about BEFORE this is merged
198 13:54 <pinheadmz> because the maprelay would still send tx_a to anyone who asked, even if the replacement was in the mempool
199 13:54 <pinheadmz> heh, well I guess you could send a MEMPOOL request ?
200 13:54 <amiti> I think currently the attack would be to have lots of connections to nodes on the network & send out GETDATAs for any new txn to identify which nodes already have the txn
201 13:55 <amiti> and they would respond even though they didnt send you an INV message yet
202 13:55 <MarcoFalke> amiti: Correct!
203 13:55 <MarcoFalke> amiti: How many connections do you need per node on the network?
204 13:56 <amiti> uhhh... I'm guessing more than one bc otherwise you wouldn't ask this question?
205 13:56 <amiti> but I don't see why
207 13:56 <MarcoFalke> Yes, just one inbound cnnection is enough
209 13:56 <MarcoFalke> Ok, to wrap up...
210 13:57 <coma-shuffling> wasn't such an attack presented at Scaling Bitcoin Tel Aviv?
211 13:57 <MarcoFalke> Any questions left?
212 13:57 <pinheadmz> coma-shuffling: that involved orphan txs i think
213 13:57 <coma-shuffling> ah
214 13:57 <pinheadmz> MarcoFalke: yeah i was just wondering about testing
215 13:57 <MarcoFalke> < pinheadmz> 2 the python tests often have random elements or non-deterministic elements. Today's test runs 100 times and breaks once a certain case is found -- 100 iterations make the expected behavior very likely, but couldn't the tests be written more acutely?
216 13:58 <amiti> ya- question around naumenkogs review. MarcoFalke: what do you think about the concern?
217 13:58 <pinheadmz> i downloaded the PR and tried the test with and without the change. also tried the new test against the current code (without PR) nothing really changes there
218 13:58 <pinheadmz> I see in the test you are being explicit that if a node did relay the tx back, you check that they got it in an inv or tx message
220 13:58 <MarcoFalke> amiti: I think that my set of changes should be kept to a minimum that is still an improvement. I don't claim to fix all privacy issues and I think even fixing one is reason enough
221 13:58 <amiti> ya I agree
222 13:59 <MarcoFalke> amiti: Also the memory improvements might be worth it
223 13:59 <MarcoFalke> amiti: Not to mention bandwidth
224 13:59 <MarcoFalke> jnewbery: I disagree
225 13:59 <ajonas> but reintroducing mapRelay again seems like a lot of churn
226 13:59 <ajonas> as Gleb is suggesting
227 14:00 <MarcoFalke> jnewbery: I think that suhas DOS case is an edge case and should not happen very often in the network.
228 14:00 <jonatack> MarcoFalke: do you think the new tests cover the change of behavior sufficiently? What do you think about the current state of our p2p testing?
229 14:00 <MarcoFalke> INV("endmeeting")
231 14:00 <fjahr> NOTFOUND
232 14:00 <MarcoFalke> lets keep going for two more minutes
234 14:01 <jonatack> "Test coverage of our networking code"
235 14:01 <MarcoFalke> jnewbery: And we do handle the case (even though it takes 120 secs or so to timeout)
236 14:02 <MarcoFalke> jnewbery: Though, I'd like to see suhas fix as well. Assuming it doesn't itself result in a CPU DOS vector
237 14:02 <MarcoFalke> ajonas: I don't think reintroducing mapRelay should be done
238 14:02 <MarcoFalke> ajonas: If it is necessary, I'd rather have a limited map of map_recently_rbfd_txs
239 14:03 <MarcoFalke> jonatack: pinheadmz: Good question about testing!
240 14:03 <amiti> ya, I was wondering that .... if the attack is just about RBF txns, we'd hypothetically only have to keep track of those
241 14:03 <MarcoFalke> What are the complications to test such a change? I.e. how to test the privacy guarantees?
242 14:03 <MarcoFalke> amiti: Yes, agree.
243 14:04 <MarcoFalke> Has anyone seen my test changes? What is the test doing before and what is it doing after my changes?
244 14:04 <MarcoFalke> We will wrap up in one minute :)
245 14:05 <MarcoFalke> #endmeeting
246 14:05 <pinheadmz> all you added to the test was checking that if the tx was already announced to us, the txid exists in a inv or tx message
247 14:05 <@jnewbery> Thanks MarcoFalke. Great meeting!
248 14:05 <coma-shuffling> thanks MarcoFalke
249 14:05 <MarcoFalke> jnewbery: Thanks for suggesting it to me
250 14:06 <jasonzhouu> Thanks MacroFalke
251 14:06 <jonatack> thanks everyone
252 14:06 <MarcoFalke> Happy to do more of these
253 14:06 <ariard> thanks MarcoFalke!
254 14:06 <pinheadmz> thanks everyone!
255 14:06 <amiti> thank you !
256 14:06 <jonatack> thank you MarcoFalke for hosting]
257 14:06 <ajonas> thanks Marco
258 14:06 <MarcoFalke> thanks everyone for the answers and questions. Really high quality today
259 14:06 <@jnewbery> I'll try to get notes and questions up for next week's meeting before the weekend. I'm travelling so I might not be able to attend but I think I have a host lined up
260 14:07 <jonatack> jasonzhouu: MacroFalke, i like that +1