Skip to content

Instantly share code, notes, and snippets.

Last active June 5, 2023 16:43
Show Gist options
  • Save glozow/7c0ff639f996e660146314edffa6f06c to your computer and use it in GitHub Desktop.
Save glozow/7c0ff639f996e660146314edffa6f06c to your computer and use it in GitHub Desktop.

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.
Copy link

instagibbs commented Jun 2, 2023

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment