--- Day changed Wed Jul 22 2020 00:15 -!- S3RK [~s3rk@47.246.66.116] has joined #bitcoin-core-pr-reviews 00:29 -!- S3RK [~s3rk@47.246.66.116] has quit [Remote host closed the connection] 00:53 -!- S3RK [~s3rk@47.246.66.116] has joined #bitcoin-core-pr-reviews 00:57 -!- S3RK [~s3rk@47.246.66.116] has quit [Ping timeout: 258 seconds] 01:05 -!- S3RK [~s3rk@47.246.66.116] has joined #bitcoin-core-pr-reviews 01:30 -!- vasild [~vd@gateway/tor-sasl/vasild] has joined #bitcoin-core-pr-reviews 01:50 -!- jonatack [~jon@192.113.14.109.rev.sfr.net] has joined #bitcoin-core-pr-reviews 01:56 -!- jonatack [~jon@192.113.14.109.rev.sfr.net] has quit [Ping timeout: 256 seconds] 02:20 -!- Davterra [~tralfaz@104.200.129.213] has quit [Quit: Leaving] 02:34 -!- S3RK [~s3rk@47.246.66.116] has quit [Remote host closed the connection] 02:56 -!- S3RK [~s3rk@47.246.66.116] has joined #bitcoin-core-pr-reviews 03:01 -!- S3RK [~s3rk@47.246.66.116] has quit [Ping timeout: 258 seconds] 03:03 -!- Gerhard14Deckow [~Gerhard14@static.57.1.216.95.clients.your-server.de] has joined #bitcoin-core-pr-reviews 03:08 -!- S3RK [~s3rk@47.246.66.116] has joined #bitcoin-core-pr-reviews 03:08 -!- Gerhard14Deckow [~Gerhard14@static.57.1.216.95.clients.your-server.de] has quit [Ping timeout: 256 seconds] 03:27 -!- jonatack [~jon@2a01:e0a:53c:a200:bb54:3be5:c3d0:9ce5] has joined #bitcoin-core-pr-reviews 03:53 -!- reallll [~belcher@unaffiliated/belcher] has joined #bitcoin-core-pr-reviews 03:57 -!- belcher_ [~belcher@unaffiliated/belcher] has quit [Ping timeout: 256 seconds] 03:57 -!- S3RK [~s3rk@47.246.66.116] has quit [Remote host closed the connection] 03:58 -!- S3RK [~s3rk@47.246.66.116] has joined #bitcoin-core-pr-reviews 04:03 -!- reallll is now known as belcher 04:03 -!- S3RK [~s3rk@47.246.66.116] has quit [Ping timeout: 256 seconds] 04:35 -!- Zenton [~user@unaffiliated/vicenteh] has quit [Quit: ERC (IRC client for Emacs 26.3)] 04:35 -!- Zenton [~user@unaffiliated/vicenteh] has joined #bitcoin-core-pr-reviews 04:50 -!- S3RK [~s3rk@47.246.66.116] has joined #bitcoin-core-pr-reviews 04:55 -!- S3RK [~s3rk@47.246.66.116] has quit [Ping timeout: 260 seconds] 05:38 -!- Netsplit *.net <-> *.split quits: felixfoertsch 05:40 -!- Davterra [~Davterra@37.120.208.245] has joined #bitcoin-core-pr-reviews 05:40 -!- SergeySherkunov4 [leinlawunm@gateway/shell/matrix.org/x-ynygbzpgleustwpc] has quit [Write error: Connection reset by peer] 05:40 -!- Davterra [~Davterra@37.120.208.245] has quit [Max SendQ exceeded] 05:41 -!- pinheadmz [~pinheadmz@pool-100-33-69-78.nycmny.fios.verizon.net] has quit [Ping timeout: 246 seconds] 05:41 -!- Davterra [~Davterra@37.120.208.245] has joined #bitcoin-core-pr-reviews 05:47 -!- SergeySherkunov[ [leinlawunm@gateway/shell/matrix.org/x-pedtcghdznyxqxkp] has joined #bitcoin-core-pr-reviews 05:49 -!- fedorafa_ [~fedorafan@unaffiliated/fedorafan] has joined #bitcoin-core-pr-reviews 05:51 -!- fedorafa_ [~fedorafan@unaffiliated/fedorafan] has left #bitcoin-core-pr-reviews ["Textual IRC Client: www.textualapp.com"] 06:02 -!- felixfoertsch [felixfoert@gateway/shell/matrix.org/x-rdndmcoackcqrzxf] has joined #bitcoin-core-pr-reviews 06:31 -!- foxp2 [~foxp2@ec2-52-71-103-222.compute-1.amazonaws.com] has joined #bitcoin-core-pr-reviews 06:45 -!- foxp2 [~foxp2@ec2-52-71-103-222.compute-1.amazonaws.com] has quit [Ping timeout: 258 seconds] 07:04 -!- slivera [~slivera@103.231.88.27] has quit [Remote host closed the connection] 07:05 -!- gzhao408 [~textual@c-73-252-251-3.hsd1.ca.comcast.net] has joined #bitcoin-core-pr-reviews 07:14 -!- SergeySherkunov[ [leinlawunm@gateway/shell/matrix.org/x-pedtcghdznyxqxkp] has quit [Quit: Idle for 30+ days] 07:21 -!- gzhao408 [~textual@c-73-252-251-3.hsd1.ca.comcast.net] has quit [Quit: My MacBook has gone to sleep. ZZZzzz…] 07:22 -!- S3RK [~s3rk@47.246.66.116] has joined #bitcoin-core-pr-reviews 07:23 -!- troygiorshev [~troygiors@CPEdcef09a0ed55-CM0c473d74be00.cpe.net.cable.rogers.com] has quit [Ping timeout: 240 seconds] 07:24 -!- troygiorshev [~troygiors@CPEdcef09a0ed55-CM0c473d74be00.cpe.net.cable.rogers.com] has joined #bitcoin-core-pr-reviews 07:29 -!- S3RK [~s3rk@47.246.66.116] has quit [Ping timeout: 256 seconds] 07:41 -!- gzhao408 [~textual@c-73-252-251-3.hsd1.ca.comcast.net] has joined #bitcoin-core-pr-reviews 08:31 -!- vasild_ [~vd@gateway/tor-sasl/vasild] has joined #bitcoin-core-pr-reviews 08:34 -!- vasild [~vd@gateway/tor-sasl/vasild] has quit [Ping timeout: 240 seconds] 08:34 -!- vasild_ is now known as vasild 08:58 -!- Talkless [~Talkless@hst-227-49.splius.lt] has joined #bitcoin-core-pr-reviews 09:00 < jnewbery> We'll get started in about an hour 09:02 < gzhao408> wooooo!!!!! 09:02 < nehan> gzhao408: :) 09:06 < jnewbery> gzhao408: I agree! 09:13 -!- factoid [~factoid@195.181.160.175.adsl.inet-telecom.org] has joined #bitcoin-core-pr-reviews 09:40 -!- adiabat [~adiabat@63.209.32.102] has joined #bitcoin-core-pr-reviews 09:41 -!- troygiorshev [~troygiors@CPEdcef09a0ed55-CM0c473d74be00.cpe.net.cable.rogers.com] has quit [Ping timeout: 246 seconds] 09:41 -!- troygiorshev [~troygiors@CPEdcef09a0ed55-CM0c473d74be00.cpe.net.cable.rogers.com] has joined #bitcoin-core-pr-reviews 09:44 -!- theStack [~honeybadg@vps1648322.vs.webtropia-customer.com] has joined #bitcoin-core-pr-reviews 09:46 -!- thomasb06 [~user@eth-west-pareq2-46-193-0-224.wb.wifirst.net] has joined #bitcoin-core-pr-reviews 09:50 < brikk> +1 for a review of the build system I've learned so much from fanquake's docs and direct help already and look forward to more valuable insights 09:51 -!- lightlike [~lightlike@p200300c7ef136c009026ef0fb1599862.dip0.t-ipconnect.de] has joined #bitcoin-core-pr-reviews 09:55 -!- mikerah[m] [mikerahmat@gateway/shell/matrix.org/x-ckezpppbphuptimy] has joined #bitcoin-core-pr-reviews 09:59 -!- swapna [443ee3e6@c-68-62-227-230.hsd1.al.comcast.net] has joined #bitcoin-core-pr-reviews 10:00 < jnewbery> #startmeeting 10:00 < jnewbery> hi everyone! 10:00 < emzy> hi 10:00 < troygiorshev> hi 10:00 < willcl_ark> hi 10:00 < nehan> hi everyone! 10:00 < swapna> hi eveyone! 10:00 < michaelfolkson> hi 10:00 < ariard> hi 10:00 < felixweis> hiu 10:00 < lightlike> hi 10:00 < theStack> hi 10:00 < factoid> hi 10:00 < gzhao408> hi! 10:00 < adiabat> hi 10:00 < nehan> thanks for joining today. notes and questions here: https://bitcoincore.reviews/15644.html 10:01 < ajonas> hi 10:01 < amiti> hi 10:01 < nehan> reminder, feel free to ask ANY questions. and let us know if this is your first time at review club! 10:01 < nehan> today we're going to talk about orphan processing. who's had a chance to review the pr? (y/n) 10:01 < amiti> y 10:01 < adiabat> y 10:02 < willcl_ark> y 10:02 < troygiorshev> y 10:02 < theStack> n 10:02 < felixweis> n 10:02 < jnewbery> y 10:02 < lightlike> y 10:02 < emzy> y/n 10:02 < michaelfolkson> y 10:02 < swapna> n 10:02 < gzhao408> y 10:02 < factoid> y 10:03 -!- pinheadmz [~pinheadmz@pool-100-33-69-78.nycmny.fios.verizon.net] has joined #bitcoin-core-pr-reviews 10:03 < nehan> ok. so as stated in the notes, an orphan transaction is one where we are missing one or more of its inputs 10:03 < pinheadmz> hi 10:03 < nehan> first question: Why might we want a node to keep track of orphans at all? What does this help with? 10:03 < nehan> one could imagine just dropping transactions if we can't validate them immediately 10:04 < adiabat> It seems like if you don't, you still have to keep track of the fact that you saw it, and not request it again 10:04 < willcl_ark> if we already have the orphan then as soon as we have the parent we can validate immediately without needing to receive/request again 10:04 < adiabat> but if you only keep track of "this is bad/invalid" then when it's no longer an orphan you won't get it until it's in a block 10:04 < emzy> could be that the order they arive are different. So the missing input will arive later. 10:04 < michaelfolkson> Though it is removed after 20 mins. Is that right? Seems short time 10:05 < nehan> good points. adiabat: given that the orphan map is limited in size, we cannot guarantee we will never request something again 10:05 < adiabat> would a different strategy be to hang up on or ban nodes that give you an orphan tx? Are there problems or DoS attacks with doing that? 10:06 < amiti> also helps enable CPFP (child pays for parent). if the mempool conditions means the parent isn't accepted, the child would need to be accepted first in order to include both into a block 10:06 < jnewbery> adiabat: we can only add txs to 'recent rejects' if we know that they're definitely invalid. Otherwise, there are tx censorship attacks 10:06 < gzhao408> seems reasonable to only keep for a short period of time, I'm imagining the case where they're both relayed and you just happen to receive the child first 10:06 < nehan> adiabat: good question! what do people think? 10:06 < ariard> well the sending node may not be the one responsible for the tx being an orphan at reception, parent might have been replaced 10:06 < nehan> i think that would be a bad idea, especially on startup, when your mempool is empty and you might receive transactions out of order 10:06 < factoid> ariard +1 10:07 < jnewbery> nehan: +1. Orphans are most common at startup or when making new connections 10:07 < sipa> orphan transactions are not a sign of misbehavior; they arise naturally due to variations in network connections 10:07 < adiabat> it does seem to put a lot of responsibility on the sending node, they'd need to make sure to send all invs in order 10:07 < nehan> and a sending node just doesn't know what its peer has seen/not seen 10:07 < ariard> they do send inv in topology-order in SendMessages IIRC 10:07 < nehan> unless it sent it itself! 10:07 < sipa> and the sending node cannot know if perpahs they already gave you the parent, but you replaced it! 10:07 < nehan> or that ^ 10:07 < nehan> ok let's move on to how orphans are handled 10:08 < amiti> also a node might request a parent from one peer, child from another & the child is delivered first. doesn't seem like a fault of the peer that delivered! 10:08 < nehan> what happens regarding orphans when we accept a new transaction to the mempool? 10:08 < jnewbery> adiabat: that is indeed what we do: https://github.com/bitcoin/bitcoin/blob/2c0c3f8e8ca6c64234b1861583f55da2bb385446/src/net_processing.cpp#L4203-L4206 10:08 < lightlike> also, if we just discarded the orphans, we might request and discard them again multiple times from different peers even before getting a parent, which seems ineffective. 10:08 < gzhao408> a clarification question: how sure are we that an orphan is a valid orphan as opposed to invalid? what validation has it passed before it's called a TX_MISSING_INPUTS? 10:09 < sipa> jnewbery, adiabat: but all we can do is _announce_ in topology order; it doesn't guarantee that things are requested/received in the same order when multiple nodes are involved (as amiti points out) 10:09 < sipa> gzhao408: none 10:09 < sipa> syntactic validity 10:09 < ariard> gzhao408: every check in PreChecks before hitting TX_MISSING_INPUTS, like transaction standard size or nLocktime finality 10:09 < pinheadmz> nehan when a tx is accpted ot mempool we check it against the map of known orphans 10:09 < pinheadmz> to see if it resolves anything 10:10 < adiabat> maybe make a new type of INV message that has clumps, like these 4 txids should be requested at once (this is probably a bad idea; just making stuff up :) ) 10:10 < pinheadmz> with this PR, IIUC, we only resolve one orphan at a time 10:10 < ariard> requesting/reception might be biased by your connection type and sending nodes shouldn't make assumptions on receiving peer topology 10:10 < sipa> adiabat: there is a very long term plan for that, it's called package relay, but it's nontrivial 10:11 < nehan> pinheadmz: yes! 10:11 < sipa> adiabat: and it's indeed probably the only complete solution to orphan processing and a number of other issues 10:11 < jnewbery> adiabat: we're getting a bit off-topic, but the idea you're referring to is called 'package relay' 10:11 < factoid> gzhao408 sipa ariard, it's the case, isn't it, that we can be certain a transaction is invalid, we can't be certain it is valid -- right? 10:11 < michaelfolkson> It depends how "expensive" certain operations are. Rejecting it and then requesting the orphan transaction again has to be compared to storing and retrieving from memory 10:11 < pinheadmz> factoid somethings maybe like MAXMONEY etc 10:11 < pinheadmz> but most TX checks require context (utxo set) 10:11 < adiabat> sipa, jnewbery: oh cool that it isn't inherenly a bad idea but yes sounds complicated & getting of topic, thanks 10:11 < nehan> what happens if the orphan we are checking is now accepted to the mempool? 10:12 < nehan> (it has been un-orphaned) 10:12 < willcl_ark> it waits for a parent to arrive which validates it 10:12 < ariard> factoid: validity might change due to order of transaction reception or your block tip, but once it's a valid one it should be guaranteed to stay so 10:12 < nehan> willcl_ark: not exactly. that's what just happened (a parent arrived that enabled us to validate it; it was valid; we put it in the mempool) 10:13 < pinheadmz> nehan do we check the orphanmap again for more decesndants? 10:13 < ariard> adiabat: fyi https://bitcoincore.reviews/15644.html 10:13 < nehan> pinheadmz: yes! this newly unorphaned transaction might be a parent to _other_ orphan transactions! 10:13 < ariard> pinheadmz: yes we do recursively call ProcessOprhanTx IIRC 10:13 < amiti> pinheadmz: +1 10:14 < factoid> uh oh >:) 10:14 < factoid> the harbinger to resource exhaustion? 10:14 < nehan> yeah so we see that we need to be careful here. 10:15 < nehan> what happens when a node receives a transaction and it hasn't seen one or more of the transaction's inputs? 10:15 < nehan> (basically, how do orphans get processed and saved) 10:16 < michaelfolkson> Stored in mapOrphanTransactions 10:16 < jnewbery> nehan: we add them to a global map, but there are also a few other data structures involved 10:17 < nehan> michaelfolkson: jnewbery: yep 10:17 < pinheadmz> and the map is limited to size of 100 10:18 < sipa> and each orphan is limited in size 10:18 < nehan> https://github.com/bitcoin/bitcoin/blob/master/src/net_processing.cpp#L916 10:19 < pinheadmz> sipa ah didnt know - so if a tx is too big we wont even store it in the map? 10:19 < nehan> that is done in AddOrphanTx. it ignores large orphans. the other important datastructure is mapOrphanTransactionsByPrev. how does that work? 10:19 < pinheadmz> just a lost cause 10:19 < pinheadmz> 100k is pretty fair i guess 10:19 < nehan> pinheadmz: we could process it again once we get its parents 10:20 < michaelfolkson> But removed at random rather than by lowest fee when full and also removed after 20 minutes. Was unsure why 10:20 < michaelfolkson> 20 minutes by default, obviously can change that if you want 10:20 < sipa> orphan transactions are primarily just a way to resolve things that are sent out of order 10:21 < sipa> usually, when they happen, they resolve immediately 10:21 < pinheadmz> nehan mapOrphanTransactionsByPrev is used to match new incoming TX with orphans it resolves 10:21 < sipa> (as we request the parent) 10:21 < nehan> i *think* that saving orphans is not required for correct operation. it's an optimization. 10:21 < nehan> someone should check me on that 10:21 < pinheadmz> nehan the reason a tx is orhpaned is bc we dont know the coins (prevs) its spending - so when a tx comes in that creates those prevs, we can find the orphan and REUNITE THE FAMILY 10:21 < sipa> nehan: well that depends on how you define correct operation; ignoring every tx announcement is arguably equally correct 10:22 < adiabat> yeah blocksonly works fine, as long as not everyone does that 10:22 < nehan> sipa: so it would require some other way to hear about invs again 10:22 < jnewbery> nehan: you're correct. We don't make any guarantees with orphans. They do help you get a better view of the mempool more quickly, and they may help with compact block relay 10:22 < sipa> nehan: but sure, orphan processing is a best effort, and its primary motivation is making sure compact block reconstruction doesn't need a roundtrip because of a just-missed out of order relay 10:22 < nehan> anyone want to answer the mapOrphanTransactionsByPrev question? Why is it a map of iterators? 10:23 < sipa> iterators are smaller than uint256s 10:23 < sipa> (8 vs 32 bytes) 10:23 < aj> nehan: (map of sets of iterators) 10:23 < nehan> sipa: yes. iterators are 8 bytes (on my platform) vs 32 10:24 < factoid> If we don't know the the market is for transactions bidding into blocks, they other fee estimations will break -- so that's important to make sure orphans are represent in those stats 10:24 < amiti> nehan: mapOrphanTransactionsByPrev is a map of outpoint -> to iterators, so it can point to the relevant entries on the orphan list. I thought for quicker access 10:24 < nehan> amiti: yes that is also true! it saves you a lookup into mapOrphanTransactions. but that is limited in size to 100 so imho that's not necessarily worth optimizing 10:25 < amiti> yeah fair 10:25 < jnewbery> if it were txids, we'd just be using those txids to index into mapOrphanTransactions, so we just store the iterators 10:25 < nehan> aj: yes good point 10:25 < sipa> the point of having the byPrev map is to quickly find potential dependent orphans that can get reprocessed, without needing to walk the entire set 10:25 < ariard> factoid: I think orphans aren't processed by fee estimator as we can't' know their validity and otherwise that would be a vector to manipulate your feerate 10:26 < sipa> it being a map of iterators is both a size savings, and also avoids another lookup in the primary map (compared to it storing a uint256) 10:27 < nehan> there are a couple of other interesting things to point out: if we receive an orphan from a peer, that peer is the best one to ask about the parents. cause it shouldn't be relaying a txn if it can't validate it! 10:27 < jnewbery> important to note: mapOrphanTransactions is a std::map, so inserting or erasing elements doesn't invalidate iterators into the map (except an iterator to the erased element) 10:28 < factoid> ariard ah yeah -- I suppose I meant if we have a delayed (maybe it's negligible amount of time) processing of a txn from orphan to valid, that'll delay a node's view of what the block-space market might be 10:28 < nehan> jnewbery: good point 10:28 < sipa> ariard: damn, i just realized you've responding to the nickname factoid here, instead of just dropping random factoids 10:29 < factoid> ok fixed 10:29 < factoid> oops 10:29 < factoid> maybe now 10:29 < nehan> now the fun part. Can you think of a problem with the pre-PR version of the code? What is it and how does the PR fix it? 10:29 < sipa> factoid: nothing to fix, i was just confused :) 10:29 < ariard> sipa: ah googling factoid :) 10:30 < pinheadmz> nehan well i suppose another peer could be realyign the missing parent? 10:30 < nehan> 10:30 < pinheadmz> but becuase we stick with the loop before moving on to the next peer's cue, we could be wasting time 10:31 < nehan> there's something really bad with the pre-PR code 10:31 < nehan> it helps to take a look at what the pre-PR code is iterating over vs the post-PR code 10:31 < pinheadmz> the workQueue 10:32 < pinheadmz> ooh i see something that adds an element back to the queue 10:32 < nehan> yes. there is a workQueue, and what type is in the workqueue? 10:32 < factoid> an attacker can tie up our node processing orphan decendents by stacking a big list of orphaned transaction? 10:32 < pinheadmz> std::deque 10:32 < theStack> so basically a denial of service attack was possible? 10:33 < nehan> pinheadmz: yes! we are iterating over outpoints. each of these outpoints *might* be an input to an orphaned transaction. in fact, it could be an input to MULTIPLE orphan transactions... 10:33 < nehan> factoid: sort of! 10:33 < emzy> I also think it is a anti DOS fix. 10:33 < factoid> I was thinking the attack would be something like: create transaction{A..ZZZ}, send over transaction{B..ZZZ}, then send transaction{A} force node to iterate through the rest of the set 10:34 < nehan> and multiple outpoints might be consumed by the same orphan 10:34 < nehan> does anyone know the limit on # of inputs for a valid transaction? 10:35 < pinheadmz> heh, 0xffffff ? 10:35 < emzy> I think there is none. 10:35 < theStack> in practice it's only limited by the total size i guess? 10:35 < felixweis> ~ 2700 in pracise 10:35 < sipa> an input is at least 41 vbytes 10:35 < nehan> emzy: theStack: yes! i think it's in the thousands 10:35 < pinheadmz> oops ffffff would be max output count i guess 10:35 < troygiorshev> felixweis: i think you missed a 0 10:36 < sipa> (well, 41 non-witness bytes) 10:36 < felixweis> ok ~ 2400 10:36 < pinheadmz> ah so even though the map is limited to 100, if all 100 of those txs have max # inputs, it can really hurt 10:36 < nehan> each orphan could be as large as 100KB 10:37 < nehan> but it's even worse than that! 10:37 < nehan> in the pre-PR code, how many times might a single orphan be considered? 10:37 < aj> pinheadmz: you mean ffffffff (8 f's, not 6) right? 10:37 < pinheadmz> aj ty. 10:39 < pinheadmz> nehan as many times as its input count ? per incoming potential parent 10:39 < factoid> nehan (N^2-n)/2? 10:39 < amiti> before the pr, the same orphan could be considered again for each output of a txn. so ~3000 times I believe? 10:39 < nehan> hint: we're iterating over outputs. an orphan might refer to many of the outputs in the workQueue, but maybe when we consider it (for a single output) it still has unknown inputs 10:39 < nehan> factoid: what's N and n? 10:39 < factoid> sorry both lowercase 10:39 < factoid> n = 100 or whatever our limit is 10:40 < pinheadmz> so an orphan can have as many missing parents as it has inputs 10:40 < nehan> amiti: right! an orphan might be considered # of output times in the loop! and there could be thousands of outputs... 10:41 < pinheadmz> so for each output in work q we checked each input of each orphan 10:41 < pinheadmz> oh no not quite bc there is amap 10:41 < nehan> pinheadmz: close! we check each orphan that refers to this output 10:41 < nehan> so an attacker could set up some transactions that are very bad 10:43 < nehan> she could make 100 100KB orphans with, let's say, k+1 inputs where k is in the thousands (I don't know the exact number but if someone does feel free to chime in). Let's say k=2000 10:43 < nehan> as a node, i'd receive those orphans and happily put them in my orphan map. note that this doesn't cost the attacker anything other than the bandwidth of sending those out 10:44 < nehan> all those orphans take the same k inputs plus one input which is different for each orphan 10:44 -!- S3RK [~s3rk@47.246.66.116] has joined #bitcoin-core-pr-reviews 10:45 < nehan> then, the attacker crafts a transaction that will be accepted to the mempool and triggers the work of looking in the orphan map 10:45 < thomasb06> https://bitcoin.stackexchange.com/questions/85752/maximum-number-of-inputs-per-transaction 10:45 < nehan> thomasb06: thanks! 10:45 < thomasb06> ;p 10:46 < nehan> that exact number doesn't matter as much for this attack as long as it's greater than the number of max outputs 10:47 < pinheadmz> nehan why the k+1 scheme? 10:47 < nehan> let's say the special attacker transaction has k outputs, which are referenced by every orphan in the orphan map 10:47 < nehan> what happens? 10:47 < michaelfolkson> "The maximum number of inputs that can fit in a valid transaction is 27022." 10:47 < pinheadmz> why couldnt all the orphns just have 2000 totally random prevs ? 10:47 < nehan> pinheadmz: we're trying to craft a resource-intensive attack 10:47 < felixweis> this feels off by an order of magnitue 10:48 < nehan> pinheadmz: we want to make the node process all the orphans. if it's a random prev, then the special transaction won't match any orphans in the orphan map 10:48 < sipa> felixweis: validity vs standardness 10:48 < pinheadmz> i see 10:48 < troygiorshev> felixweis: it's a very contrived example. no security or anything 10:48 < felixweis> oh if its a mined block. not having to adhere to isStandard() 10:48 < pinheadmz> do we call acceptToMemoryPool on every single input match? 10:48 < nehan> felixweis: yeah i'm not trying to get my attack transactions mined in a block, just accepted to the mempool! important note, thanks 10:48 -!- S3RK [~s3rk@47.246.66.116] has quit [Ping timeout: 240 seconds] 10:49 < pinheadmz> so an orphan with 1000 inputs. a single parent comes in. we call ATMP(orphan) which fails bc the other 999 are still missing... ? 10:50 < nehan> i actually wrote a test to conduct this attack here, it might be easier to look at that: https://github.com/narula/bitcoin/blob/pr15644test/test/functional/p2p_orphan.py#L69 10:50 < nehan> * wrote with amiti! 10:50 < michaelfolkson> Oh wow 10:50 < amiti> :) 10:50 < emzy> Hacker ;) 10:51 < gzhao408> but now we also don't consider orphans bigger than MAX_STANDARD_TX_WEIGHT right? 10:51 < gzhao408> oh or this is still within that restriction 10:51 < nehan> the key thing to notice is that the pre-PR version of the code did two things: 1) it looped through all the outputs and orphans without stopping and 2) it would potentially process one orphan many times 10:52 < gzhao408> ok yeah sorry, kinda off topic :sweat_smile: 10:53 < nehan> gzhao408: not at all! you are right it checks that before adding something to the orphan map: https://github.com/bitcoin/bitcoin/blob/master/src/net_processing.cpp#L930 10:54 < pinheadmz> when you say loop thgouh all the orphans, you mean as a result of mapOrphanTransactionsByPrev.find() ? 10:54 < nehan> ok so in the worst case, an attacker could make a node process 100*100KB*orphans*k amount of data. if k=2000, that's 20 GB!!! 10:55 < nehan> oops 100 orphans * 100 KB max orphan size * k outpoints 10:55 < pinheadmz> while (!vWorkQueue.empty()) I understand loops through all the new outputs generated by valid incoming (potential) parents right? 10:56 < nehan> pinheadmz: yes! that lookup might return every orphan in the orphan map: https://github.com/bitcoin/bitcoin/pull/15644/commits/9453018fdc8f02d42832374bcf1d6e3a1df02281#diff-eff7adeaec73a769788bb78858815c91L2388 10:56 < michaelfolkson> This test will be opened as a separate PR to Core to check that orphan processing is actually interruptible right? 10:56 < pinheadmz> ohhhhhhh light bulb! thank you 10:56 < nehan> pinheadmz: answering your previous question about mapOrphanTransactionByPrev.find() 10:56 < lightlike> how long would that take in the worst case? Is that the runtime of the test you linked? 10:56 < jnewbery> and the attack is almost free for the attacker. They have to provide 10MB of transactions, but apart from the parent, none of those need to actually be valid, so they don't cost anything 10:57 < michaelfolkson> Plus we should chat NOINPUT/ANYPREVOUT. aj is here ;) 10:57 < nehan> lightlike: the test case hung for a long time and crashed, so i'm not sure how long it takes! good question! 10:58 < pinheadmz> so, sipa -- was this PR a stealthy fix? 10:58 < nehan> oh right shoot. last question: how is orphan processing affected by SIGHASH_NOINPUT / etc? 10:58 < nehan> michaelfolkson: thank you! 10:59 < michaelfolkson> We can expect there to be many more orphans right? And delays in processing "justice transactions" with eltoo will be problematic for Lightning 10:59 < ariard> in fact that's just a sighash flag so tx parent can be fulfilled by initial sender to favor propagation 10:59 < nehan> i don't totally know the answer to this question, except that it's helpful right now that you can't create an orphan without first creating its parent. SIGHASH_NOINPUT changes that. 10:59 < jnewbery> mapOrphanTransactionsByPrev is no longer enough, since a SIGHASH_NOPREVOUT input doesn't refer to a single outpoint 10:59 < pinheadmz> nehan oh dang hadn't thought of this - do we actually need to check all the scripts? I would think that sighashnoinput just shouldnt be allowed to be an orphan 10:59 < ariard> michaelfolkson: not only justice txn almost all LN txn are time-sensitive 10:59 < sipa> nehan: i don't see how that is related 10:59 < sipa> you still need the parent to construct the tx 10:59 < sipa> you don't need the parent to construct a signature 11:00 < sipa> but does that change anything materially? 11:00 < nehan> sipa: i might be getting this wrong. but the orphan tx doesn't necessarily commit to one parent 11:00 < jnewbery> ⏰ 11:00 < ariard> nehan: I think you're blurring p2p relay and script validation here 11:00 < nehan> er, one output. it could be satisfied by many outputs! 11:00 < pinheadmz> oh the sig doesnt cover the txid of the coin being spent 11:00 < pinheadmz> but it is still there in teh tx message 11:00 < ariard> your noinput tx can still include an outpoint at tx-relay 11:00 < nehan> ok wrapping up. but feel free to continue the conversation here, i woudl love to understand the last question better 11:00 < sipa> nehan: a tx's input still refers to explicit txids being spent from 11:00 < michaelfolkson> Indeed ariard. Assuming CLTVs aren't really high right? If they are non-justice transactions aren't time pressured 11:01 < nehan> thanks everyone! 11:01 < troygiorshev> thanks nehan! 11:01 < pinheadmz> 👏👏👏 11:01 < theStack> thanks to nehan and everyone 11:01 < factoid> thanks nehan 11:01 < thomasb06> thanks 11:01 < lightlike> thanks! 11:01 < emzy> Thanks nehan and everyone else. I learned much! 11:01 < ariard> michaelfolkson: would say no, with current deployed timelocks it's easier to target CLTV ones than justice CSV ones 11:02 < felixweis> thanks 11:02 < jnewbery> ariard sipa: ah you're right. The tx does still refer to the outpoint. It's just the sighash that changes. Sorry nehan - I got myself confused when we talked about this earlier. 11:02 < jnewbery> thanks for hosting nehan. Great meeting! 11:02 < michaelfolkson> Interesting... can you explain why ariard? 11:02 < nehan> jnewbery: np! helpful to understand this better 11:02 < michaelfolkson> Thanks nehan! 11:03 < nehan> so nothing would need to change because the orphan still refers to a referrable parent? 11:03 < sipa> yes 11:03 -!- theStack [~honeybadg@vps1648322.vs.webtropia-customer.com] has quit [Quit: Lost terminal] 11:03 < ariard> michaelfolkson: https://arxiv.org/pdf/2006.01418.pdf, look on 4.5 A3, that's lowest timelock and that's a CLTV one 11:04 < ariard> nehan: yes tx refers to a parent but the sigs in its witness doesn't commit to this parent 11:04 < nehan> right, ty. so the transaction could be malleated to refer to invalid inputs, making it an orphan? 11:04 < pinheadmz> sipa is there a stealthy security story around this PR? since the attack is so cheap? The PR description isnt too explicit in this sense 11:04 < ariard> but matt as some kind of blind package relay proposal which would reintroduce this issue 11:04 < sipa> pinheadmz: i'd rather not comment at this point 11:05 < pinheadmz> ok 11:05 < jnewbery> oh, if anyone is in the mood for more orphan handling code, there's a small PR here: https://github.com/bitcoin/bitcoin/pull/19498 which fixes up some of the loose ends from this PR. 11:05 < ariard> nehan: depends by whom, an infrastructure attacker yes, but why a honest relay node would do this?? 11:06 < ariard> and it shouldn't be pinned in recentRejects, malleating inputs change txid ofc 11:08 < emzy> Is this only an optimation? chnaging -maxorphantx to a very low number (3) would not hurt the network? 11:09 < emzy> The whole caching of orphans 11:09 < sipa> it'd potentially affect block propagation 11:10 < emzy> Is it not only relevant for the mempool? 11:10 < sipa> compact block reconstruction depends on having the block's transactions ahead of time 11:10 < sipa> in the mempool, or "extra pool" (which is indirectly populated by orphans too) 11:10 < emzy> Ok. I see. 11:11 < emzy> can result in slower block propagation 11:11 < emzy> tnx 11:12 < sipa> and it's really an all or nothing thing- to get the best propagation speed, a node needs to have _all_ the transactions 11:12 < sipa> otherwise an additional roundtrip is needed 11:12 < emzy> but how could be an orphan included in a block? 11:13 < sipa> because the miner has the parent, and you don't 11:13 -!- gzhao408 [~textual@c-73-252-251-3.hsd1.ca.comcast.net] has quit [Quit: My MacBook has gone to sleep. ZZZzzz…] 11:13 < emzy> ok but then you need the additional roundtrip anyway 11:14 < sipa> i think you're confused, but i don't know about what :) 11:14 < aj> nehan: SIGHASH_NOINPUT doesn't matter for orphan processing -- you don't look at validating the sigs until you've got all the parents. what it means is you could take a tx with a parent [txid,n] and change it to a different parent [txid',n'] while keeping the same sig, but that would produce a different transaction with different txid and wtxid, and it may not even be a doublespend at that 11:14 < aj> point, so it's really just another tx 11:15 < emzy> sipa: ok. I will try to figure it out myself. Good for lerning :) 11:15 < sipa> emzy: the orphan pool helps with tx propagation- without out, we'll just miss certain transactions for slightly longer 11:15 < sipa> missing a transaction is bad if it is included in a block, because that means an additional roundtrip at _block propagation_ time 11:15 -!- lightlike [~lightlike@p200300c7ef136c009026ef0fb1599862.dip0.t-ipconnect.de] has quit [Quit: Leaving] 11:15 < emzy> oh, now I get it! 11:15 < sipa> and latency of block propagation is critical; for transactions it isn't 11:17 -!- troygiorshev [~troygiors@CPEdcef09a0ed55-CM0c473d74be00.cpe.net.cable.rogers.com] has quit [Ping timeout: 240 seconds] 11:17 < emzy> I got it. Tnx again. 11:18 -!- troygiorshev [~troygiors@CPEdcef09a0ed55-CM0c473d74be00.cpe.net.cable.rogers.com] has joined #bitcoin-core-pr-reviews 11:30 -!- swapna [443ee3e6@c-68-62-227-230.hsd1.al.comcast.net] has quit [Remote host closed the connection] 11:38 -!- gzhao408 [~textual@c-73-252-251-3.hsd1.ca.comcast.net] has joined #bitcoin-core-pr-reviews 11:38 -!- Talkless [~Talkless@hst-227-49.splius.lt] has quit [Quit: Konversation terminated!] 11:41 -!- gzhao408 [~textual@c-73-252-251-3.hsd1.ca.comcast.net] has quit [Client Quit] 13:24 -!- S3RK [~s3rk@47.246.66.116] has joined #bitcoin-core-pr-reviews 13:29 -!- S3RK [~s3rk@47.246.66.116] has quit [Ping timeout: 256 seconds] 14:05 -!- slivera [~slivera@103.231.88.27] has joined #bitcoin-core-pr-reviews 14:05 -!- Tralfaz [~Davterra@37.120.208.253] has joined #bitcoin-core-pr-reviews 14:06 -!- Davterra [~Davterra@37.120.208.245] has quit [Ping timeout: 240 seconds] 14:08 -!- Tralfaz [~Davterra@37.120.208.253] has quit [Read error: Connection reset by peer] 14:36 -!- thomasb06 [~user@eth-west-pareq2-46-193-0-224.wb.wifirst.net] has quit [Remote host closed the connection] 14:51 -!- Davterra [~Davterra@37.120.208.253] has joined #bitcoin-core-pr-reviews 16:22 -!- harrigan [~harrigan@ptr-93-89-242-235.ip.airwire.ie] has quit [Ping timeout: 240 seconds] 16:25 -!- harrigan [~harrigan@ptr-93-89-242-235.ip.airwire.ie] has joined #bitcoin-core-pr-reviews 16:59 -!- MasterdonX [~masterdon@194.150.167.55] has quit [Ping timeout: 246 seconds] 17:02 -!- MasterdonX [~masterdon@202.143.111.143] has joined #bitcoin-core-pr-reviews 17:06 -!- troygiorshev [~troygiors@CPEdcef09a0ed55-CM0c473d74be00.cpe.net.cable.rogers.com] has quit [Ping timeout: 260 seconds] 17:07 -!- troygiorshev [~troygiors@CPEdcef09a0ed55-CM0c473d74be00.cpe.net.cable.rogers.com] has joined #bitcoin-core-pr-reviews 17:11 -!- troygiorshev [~troygiors@CPEdcef09a0ed55-CM0c473d74be00.cpe.net.cable.rogers.com] has quit [Ping timeout: 240 seconds] 17:12 -!- troygiorshev [~troygiors@CPEdcef09a0ed55-CM0c473d74be00.cpe.net.cable.rogers.com] has joined #bitcoin-core-pr-reviews 17:14 -!- slivera [~slivera@103.231.88.27] has quit [Remote host closed the connection] 17:26 -!- S3RK [~s3rk@47.246.66.116] has joined #bitcoin-core-pr-reviews 17:30 -!- S3RK [~s3rk@47.246.66.116] has quit [Ping timeout: 260 seconds] 17:53 -!- S3RK [~s3rk@47.246.66.116] has joined #bitcoin-core-pr-reviews 18:03 -!- harrigan [~harrigan@ptr-93-89-242-235.ip.airwire.ie] has quit [Quit: ZNC 1.7.5 - https://znc.in] 18:05 -!- harrigan [~harrigan@ptr-93-89-242-235.ip.airwire.ie] has joined #bitcoin-core-pr-reviews 18:18 -!- sipa [~pw@gateway/tor-sasl/sipa1024] has quit [Remote host closed the connection] 18:18 -!- sipa [~pw@gateway/tor-sasl/sipa1024] has joined #bitcoin-core-pr-reviews 19:24 -!- factoid [~factoid@195.181.160.175.adsl.inet-telecom.org] has quit [Quit: factoid] 20:07 -!- mol_ [~mol@unaffiliated/molly] has joined #bitcoin-core-pr-reviews 20:10 -!- mol [~mol@unaffiliated/molly] has quit [Ping timeout: 246 seconds] 20:31 -!- vasild_ [~vd@gateway/tor-sasl/vasild] has joined #bitcoin-core-pr-reviews 20:34 -!- vasild [~vd@gateway/tor-sasl/vasild] has quit [Ping timeout: 240 seconds] 20:34 -!- vasild_ is now known as vasild 20:53 -!- S3RK [~s3rk@47.246.66.116] has quit [Remote host closed the connection] 20:54 -!- S3RK [~s3rk@47.246.66.116] has joined #bitcoin-core-pr-reviews 20:58 -!- S3RK [~s3rk@47.246.66.116] has quit [Ping timeout: 240 seconds] 21:17 -!- S3RK [~s3rk@47.246.66.116] has joined #bitcoin-core-pr-reviews 21:32 -!- molz_ [~mol@unaffiliated/molly] has joined #bitcoin-core-pr-reviews 21:36 -!- mol_ [~mol@unaffiliated/molly] has quit [Ping timeout: 264 seconds] 22:32 -!- S3RK [~s3rk@47.246.66.116] has quit [Remote host closed the connection] 22:58 -!- S3RK [~s3rk@47.246.66.116] has joined #bitcoin-core-pr-reviews 23:02 -!- S3RK [~s3rk@47.246.66.116] has quit [Ping timeout: 260 seconds] 23:29 -!- jonatack [~jon@2a01:e0a:53c:a200:bb54:3be5:c3d0:9ce5] has quit [Ping timeout: 272 seconds] 23:31 -!- vindard [~vindard@190.83.165.233] has quit [Ping timeout: 258 seconds] 23:33 -!- vindard [~vindard@190.83.165.233] has joined #bitcoin-core-pr-reviews 23:57 -!- S3RK [~s3rk@47.246.66.116] has joined #bitcoin-core-pr-reviews