orphanage_protection_token_bucket.md

Token Bucket Orphan Protection Design Document

This document describes the orphan protection scheme implemented in bitcoin/bitcoin#27742.

Orphanage Today

• When tx is missing inputs, add to orphanage and request parents
  • If any parents were rejected, don’t store in orphanage (fRejectedParents)
• On each tx acceptance
  • Orphanage tracks who provided orphan - adds it to work set
  • On peer’s next ProcessMessages(), first ProcessOrphanTx before other messages
  • 1 orphan validation (accept or reject) per turn (see bitcoin/bitcoin#26551)
• Size bounds: maximum 100 orphans
  • Each must be within standard size. Can be any size under that.
  • Theoretical memory bound is 100 * 400KB (actually much bigger since these are CTransactionRefs)
  • If exceeded, orphanage evicts one at random (otherwise attackers can game it).

Orphanage Problems + Design Goals

The current orphanage has the most important property, DoS resistance, in that peers cannot cause the orphanage to grow unbounded. Things that are missing:

• Some Degree of Reliability: A peer can still make your orphanage useless by sending you tons of orphans
• Effective Usage of Resources: Does not protect the actual scarce resource, which is memory
  • Theoretical maximum is 100 * 400KB, but we evict much sooner than that since most “normal” transactions are likely much smaller than 100KvB.

Package Relay Redownloads

For package relay, the question is: what do we do in this situation:

1. Received orphan E. Stored E in orphanage and requested ancpkginfo.
2. Got a list of wtxids in the package: A, B, C, D, E.
3. Requested those transactions via getpkgtxns(A, B, C, D).
4. Orphanage reached capacity, E was evicted.
5. Received pkgtxns(A, B, C, D).

Should we try to store A, B, C, D in the orphanage and re-download E? No, because we may go into a cycle of continuously re-downloading the transactions we still need to submit the package as the ones we have drop out. Should we always re-download E at step 3? That's not very good - in the honest/average cases, we shouldn't download transactions multiple times, as it's a waste of bandwidth. What we should do is attempt to protect E from eviction while we are downloading the package. However, we should do this in a fair manner to prevent any one peer from dominating our orphanage.

General Changes to Orphanage

Multiple Announcers: The orphanage now remembers multiple peers as announcers for the same orphan.

• In AddTx, if the orphan is already present, the peer is added to the set of announcers.
• An additional EraseOrphanOfPeer is added so that, if one of the announcers did not respond when we asked for ancestors, we can remove them as an announcer.
• An orphan tx is only removed if its announcers set becomes empty.

Track and Limit Total Bytes: The orphanage tracks the total number of bytes used by the transactions. LimitOrphans is changed to start evicting when the total number of bytes reaches a maximum.

• It also tracks the total bytes provided per peer.
• The maximum is set to the current theoretical maximum, 100 * 400KB = 40MB.
• For now, eviction is triggered by both count>100 and size>40MB (which means no behavior change). In the future, we can remove the count condition.

Protection: A caller may mark an orphan as protected. While an orphan is protected, it cannot be selected for random eviction in LimitOrphans.

• An orphan can still be removed when it reaches its expiry.
• The orphanage does not take any responsibility for bounding the amount of protected orphans.
• Q: should these count within the 100count / 40MB limits? Should we add additional limits to the size of the {protected, unprotected, total} portions of the orphanage?
• Multiple peers can protect the same orphan. The orphan becomes unprotected when all protections are removed.

Don't Reject If Low Fee Parents: A new rejections cache is added for transactions that are invalid on their own but may be reconsidered in a package, i.e. ones that fail for fee-related reasons. We only give up on an orphan if its parent is in the non-reconsiderable rejections cache.

Token Bucket Orphanage Protection

Opportunistically Protect Orphans: Attempt to protect package relay peers' orphans from eviction. We will try to do this whenever we make progress:

• When we add the orphan to orphanage and add the peer to the orphan resolution tracker.
• When we send a request for ancpkginfo.
• When we are about to send a getpkgtxns request.

We remove a peer's protection for an orphan when we don't think we'll make further progress:

• They send a "notfound" in response to our request for ancpkginfo.
• Our request for ancpkginfo timed out.
• We've received all of the transactions in the package and have passed it to validation.
• We made a "final" decision on this tx (accepted to mempool, validated and rejected, confirmed, conflicted).
• We made a "final" decision that one of the transactions in this package is invalid (rejected and not eligible for reconsideration, conflicted in block).
• We received a "notfound" for transaction data in the package.
• Our request for package transaction data timed out.

Redownload if we can't protect: When sending the getpkgtxns, if we are not certain we will keep a transaction we already have, we will download it again. As explained above, the alternative is to potentially redownload everything.

Limit protections per peer: Each peer has a limited amount of orphans they can protect. They have a "token bucket" and spend tokens to gain access to the protected orphanage. Each token is worth 1 byte of protected orphan tx data.

• Outbounds get 400,000 bytes worth.
• Inbounds get 50,000 bytes worth.
• Future improvements can make the allocation dynamic. For example:
  • Reduce tokens of peers whose orphans don't make it into our mempool.
  • Increase tokens for peers who frequently give us orphans that make it into our mempool.

Delay and drop orphan resolution candidates when appropriate: When we receive an orphan and are recording the peer as a potential resolution candidate:

• Delay the request if:
  • the peer is using "a lot" of space in our orphanage.
  • we wouldn't be able to protect the orphan right now.
  • Delay because it's possible the peer is just relaying a lot of packages honestly with us. We can try to load-balance by requesting from another peer instead. Also, perhaps we can't protect now, but after a few seconds, more protection slots will open up after their packages are accepted.
• Drop the request (but we can still have other peers as candidates) if:
  • the peer is using "way too much" space in our orphanage.

Q: should these count within the 100count / 40MB limits? Should we add additional limits to the size of the {protected, unprotected, total} portions of the orphanage?

Conceptually I think having separate limits is slightly cleaner, possibly helps legacy orphan behavior for non-package peers, but opens the door for more memory usage, especially if there's a bug somewhere, e.g., forgetting to unprotect.