The PR branch HEAD was 866c805 at the time of this review club meeting.
Notes
PR 15644 was merged
over a year ago. It changes the way a node looks through its orphan
set to figure out if orphans can now be processed and added to the
mempool.
A transaction is an orphan if we’re missing one or more of its inputs (we
refer to the transactions that create the transaction outputs spent by the
orphan as parent transactions). This might be a valid transaction, but we
don’t know yet. We have to be careful with orphan management because orphans
cannot be validated.
Orphans are stored in a map called mapOrphanTransactions by their
txid. We limit the number of orphan transactions to
-maxorphantx
which is by default 100.
Why might we want a node to keep track of orphans at all? What does
this help with?
Look at the way orphans are added to the orphan maps and how
orphans are re-evaluated when we accept new transactions to the
mempool. What happens when a node receives a transaction where it
has not seen the transaction’s inputs?
Observe that
mapOrphanTransactionsByPrev
is a map of outpoints to a set of iterators over the orphan transactions map.
Why do you think it’s written the way it is, instead of storing, say, orphan
txids?
Can you think of a problem with the pre-PR version of the code?
What is it and how does the PR fix it? Hint: look at what we are
iterating over when processing orphans pre- and post- PR.
How might the adoption of something like SIGHASH_NOINPUT affect orphan processing?
<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
<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
<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!
<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.
<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?
<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)
<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 :) )
<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
<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
<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
<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
<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
<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
<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
<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
<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
<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
<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!
<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)
<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
<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...
<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
<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
<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
<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
<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
<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
<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
<michaelfolkson> We can expect there to be many more orphans right? And delays in processing "justice transactions" with eltoo will be problematic for Lightning
<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.
<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
<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.
<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.
<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