The PR branch HEAD was 0d511965c91 at the time of this review club meeting.
Notes
The PR description summarizes the motivations for
this change and the new eviction strategy: we must ensure the orphanage is DoS-resistant, but also want to prevent any
peer from affecting another peer’s usage of orphanage space.
The PR does a few things: it virtualizes the TxOrphanage class inherited by TxOrphanageImpl, it implements a new
eviction strategy, and it replaces the various TxOrphanage data structure(s) with a single boost::multi_index_container.
With these changes, we can now guarantee at least 1 maximum size-package worth of orphan resolution per peer at a
time. This is tested by the txorphan_protected fuzz test and a few functional tests.
If most peers are not providing orphans, the unused space allocated to them can be used by peers that need it.
An earlier version of this PR implemented the new eviction strategy using the existing TxOrphanage data structures.
This version makes the PR’s behavior changes clearer. It may also demonstrate why a boost::multi_index_container is
the more natural data structure for TxOrphanage, as the original implementation is a bit convoluted.
You can find that version of the PR here.
Why is the current TxOrphanage global maximum size limit of 100 transactions with random eviction problematic? Can you think of a concrete attack scenario that would affect 1-parent-1-child (1p1c) relay?
Can you summarize the changes to the eviction algorithm at a high level?
Why is it desirable to allow peers to exceed their individual limits while the global limits are not reached?
The new algorithm evicts announcements instead of transactions. What is the difference and why does it matter?
Why is there an announcement “limit” but a memory “reservation”?
How does the per-peer memory usage reservation change as the number of peers increases?
How does the per-peer announcement limit change as the number of peers increases? Why is this different from the per-peer memory usage reservation?
Why is it ok to remove orphan expiration?
Should we also remove EraseForBlock and instead rely on eviction to remove orphans that confirm or conflict with
a block? Why or why not?
Going back to your attack scenario from an earlier question, how does this PR improve the reliability of 1p1c relay in adversarial environments?
Implementation
What is the purpose of reimplementing TxOrphanageImpl using a boost::multi_index_container along with the eviction changes?
What is a peer’s “DoS Score” and how is it calculated?
The global memory limit scales with the number of peers. Could this create new DoS vectors where an attacker opens many connections to increase the global limit?
Is it possible for the orphanage to NeedsTrim() when there is no peer whose “DoS Score” is greater than 1?
Is it possible that a peer’s “DoS Score” is greater than 1 but NeedsTrim() returns false?
When evicting orphans, why evict non-reconsiderable orphans before reconsiderable ones? What’s the difference between these categories?
How does the number of announcements represent a meaningful bound on “computation” in TxOrphanage operations?
What is the computational complexity of the LimitOrphansloop? How many heap operations can there be? How many erasures can there be?
How can we test (and do tests exist?) that TxOrphanage’s internal data structures are updated correctly, that its DoS limits are correctly enforced, and that the orphans of “honest” peers are protected from eviction?
How does the txorphan_protectedfuzz harness test that orphans are protected from eviction?
The default announcement limit is increased from 100 to 3000. How was this number chosen and what are the tradeoffs?
<glozow> Why is the current TxOrphanage global maximum size limit of 100 transactions with random eviction problematic? Can you think of a concrete attack scenario that would affect 1-parent-1-child (1p1c) relay?
<glozow> marcofleon: in a 1p1c scenario, the parent isn't in mempool yet. We opportunistically pair it with its child in orphanage if we find one. But if the child gets evicted, then we're out of luck
<monlovesmango> if a malicious peer floods you with orphans, its pretty likely that you will evict a child that could have otherwise been resolved as 1p1c?
<monlovesmango> rather than having a common pool of orphans, this pr will restructure orphanage to track orphanage counts and usage by peer. each peer will be subject to a orphan announcment count limit that is the global max announcement count divided by the number of peers, and allowed a set amount of weight for the orphans they announce
<glozow> This was why I originally thought of doing a "token bucket" approach where we'd allow peers resources based on an amount of tokens, and then either replenished tokens if the orphans were useful or destroyed them if it was just spam
<monlovesmango> pseudoramdom: I was thinking about this too. I think if you flood a node with peers with counts that are just over the limit you could theoretically evict a high weight tx from a peer with high weight announcements but low announcement count
<marcofleon> annoucements are wtxid, peer. so if a peer is misbehaving then the orphan will only be removed for that peer. So a peer can't affect the orphan announcments of other peers
<glozow> pseudoramdom: do you mean for an attacker to try to get us to evict a specific orphan? or to appear less resource-intensive than another peer and get them chosen for eviction instead?
<glozow> I think this relates to pseudoramdom's question: if they did something tricky to try to get a particular orphan of theirs chosen for eviction, that's fine, because we'll keep the transaction as long as another peer has announced it
<glozow> pseudoramdom: the other peer won't experience eviction unless they exceed the limits. This still presents a limitation - peers might get evicted if they're just sending stuff at a far faster rate than we manage to process them - but the point is you can't influence the eviction of another peer's announcements
<monlovesmango> I think bc announcement count affects CPU usage? and its not much of a concern to allocate a certain amount of memory to each peer. guessing here, think I read something like that in the PR notes
<marcofleon> or i think we make the assumption that there is more memory that can be used up to a certain point, but for announcements we're trying to figure out which peer is "overusing" their share
<glozow> sipa: I wouldn't call it an announcement "reservation" though, because you aren't guaranteed it. if more peers appear, your announcement limit decreases.
<sipa> "Yes sir, your reservation for 4 tonight at FancyDining is confirmed." - "What do you mean my reservation was dropped to 3, because another group made a reservation?!"
<glozow> How does the per-peer memory usage reservation change as the number of peers increases? How does the per-peer announcement limit change as the number of peers increases?
<sipa> monlovesmango: more specifically, the *global* announcement limit directly affects the *latency* of trimming announcements - it's not because we have more peers that we can tolerate a longer latency in processing transactions
<sipa> monlovesmango: but for memory usage, it is normal and expected that your maximum memory usage goes up with more peers - if you're memory-constrained, you should limit your number of peers anyway
<glozow> marcofleon: yes exactly, that's the intuition for why the number of announcements is the number we are interested in. not the number of unique orphans (which is what we used to limit)
<monlovesmango> bc the orhpanage now has other concrete metrics by which we can reliable evict orphans which guarantee the oldest and evicted first and orphans that are no longer needed are removed
<sipa> glozow: sure, but the reason for the existence of the global announcement limit is the time that LimitOrphans can take, not AddTx... so perhaps it's worth benchmarking, and seeing if we can perhaps tolerate a higher global announcement limit (or, otherwise, be sad to find out it needs to be reduced)
<glozow> sipa: yeah definitely. I just wanted to add some context for anybody who looks at the old benchmarks. What do you think is an acceptable amount of time?
<glozow> fwiw, I think the worst case for EraseForBlock is probably worse than LimitOrphans. But EraseForBlock happens on the scheduler thread so speed might not be as much of an issue
<glozow> sipa: is that true? You could look at what's in the projected next block and just create conflicting transactions with a lot of nonexistent utxos
<sipa> glozow: sure, but the victim will still never experience it more than once per block, which is expensive. good point though that it's not necessarily the attacker themselves that pay this cost
<glozow> instagibbs: indeed. It would require adding a txid index, but maybe that's what we're evicting in practice anyway! Could measure what it looks like in the wild
<sipa> i think it was me who suggested using a multi_index, and the reason was because i saw the older implementation was effectively implementing a multi-index inefficiently, by having separate data structures for per-peer and per-wtxid information about announcements
<sipa> monlovesmango: think of an SQL database with multiple indexes on various columns, but then in-memory entirely, and in a C++y way; it's more efficient (both in memory and CPU) than having multiple independent maps (one for each index), and much easier to keep consistent (because there is no way for the different indexes to contain different information)
<marcofleon> maximum of cpu score and memory score. cpu score is a peers number of announcments / their per peer limit. and memory score is sum of the weight of a peers announced tx weights / the reserved memory usage per peer
<glozow> monlovesmango: marcofleon: yep. how does this compare to having 2 separate scores, and trimming "while CPU score is exceeded or memory score is exceeded" ?
<sipa> i think the question is: why do we have a *single* DoS score = max(mem_score, ann_score), as opposed to two different DoS scores that are never compared with one another, and a rule "trim the worst announcement offenders while there are any" + 'trim the worst memory offenders while there are any"
<glozow> So we're comparing this approach to having 2 loops. "While global announcement limit is exceeded, pick the peer with the most announcements, evict from them. Then, while global memory limit is exceeded, pick the per with the most memory usage, evict from them."
<glozow> This approach basically rolls them into 1 loop. "While global announcement or memory limit is exceeded, pick the peer with the highest score (max ratio of both) and evict from them."
<monlovesmango> one small flaw with this approach is that if count limit is reached first, the highest DOS peer might actually be violating the memory reservation and removing it won't immediately resolve the global limit being exceeded