Ancestor Package Relay

  BIP: 331
  Layer: Peer Services
  Title: Ancestor Package Relay
  Authors: Gloria Zhao 
  Status: Draft
  Type: Specification
  Assigned: 2022-08-08
  License: BSD-3-Clause
  Discussion: 2022-05-17 https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-May/020493.html [bitcoin-dev] post

Abstract

Peer-to-peer protocol messages enabling nodes to request and relay the unconfirmed ancestor package of a given transaction, and to request and relay transactions in batches.

Motivation

Propagate High Feerate Transactions

Since v0.13, Bitcoin Core has used ancestor packages instead of individual transactions to evaluate the incentive compatibility of transactions in the mempool and selecting them for inclusion in blocks . Incentive-compatible mempool and miner policies help create a fair, fee-based market for block space. While miners maximize transaction fees in order to earn higher block rewards, non-mining users participating in transaction relay reap many benefits from employing policies that result in a mempool with similar contents, including faster compact block relay and more accurate fee estimation. Additionally, users may take advantage of mempool and miner policy to bump the priority of their transactions by attaching high-fee descendants (Child Pays for Parent or CPFP).

Only individually considering transactions for submission to the mempool creates a limitation in the node's ability to determine which transactions to include in the mempool, since it cannot take into account descendants until all the transactions are in the mempool. Similarly, it cannot use a transaction's descendants when considering which of two conflicting transactions to keep (Replace by Fee or RBF).

When a user's transaction does not meet a mempool's minimum feerate and they cannot create a replacement transaction directly, their transaction will simply be rejected by this mempool or evicted if already included. They also cannot attach a descendant to pay for replacing a conflicting transaction; it would be rejected for spending inputs that do not exist.

This limitation harms users' ability to fee-bump their transactions. Further, it presents security and complexity issues in contracting protocols which rely on presigned, time-sensitive transactions to prevent cheating. In other words, a key security assumption of many contracting protocols is that all parties can propagate and confirm transactions in a timely manner. Increasing attention has been brought to "pinning attacks," a type of censorship in which the attacker uses mempool policy restrictions to prevent a transaction from being relayed or getting mined.

These transactions must meet a certain confirmation target to be effective, but their feerates are negotiated well ahead of broadcast time. If the forecast feerate was too low and no fee-bumping options are available, attackers can steal money from their counterparties. Always overestimating fees may sidestep this issue (but only while mempool traffic is low and predictable), but this solution is not guaranteed to work and wastes users' money. For some attacks, the available defenses require nodes to have a bird's-eye view of Bitcoin nodes' mempools, which is an unreasonable security requirement.

Part of the solution is to enable nodes to consider packages of transactions as a unit, e.g. one or more low-fee ancestor transactions with a high-fee descendant, instead of separately. A package-aware mempool policy can help determine if it would actually be economically rational to accept a transaction to the mempool if it doesn't meet fee requirements individually. Network-wide adoption of these policies would create a more purely-feerate-based market for block space and allow contracting protocols to adjust fees (and therefore mining priority) at broadcast time.

Theoretically, developing a safe and incentive-compatible package mempool acceptance policy is sufficient to solve this issue. Nodes could opportunistically accept packages (e.g. by trying combinations of transactions rejected from their mempools), but this practice would likely be inefficient at best and open new Denial of Service attacks at worst. As such, this proposal suggests adding new p2p messages enabling nodes to request and share package-validation-related information with one another, resulting in a more efficient and reliable way to propagate packages.

Handle Orphans Better

Txid-based transaction relay is problematic since a transaction's witness may be malleated without changing its txid; a node cannot use txid to deduplicate transactions it has already downloaded or validated. Ideally, two nodes that both support BIP339 wtxid-based transaction relay shouldn't ever need to use txid-based transaction relay.

A single use case of txid-based relay remains: handling "orphan" transactions that spend output(s) from an unconfirmed transaction the receiving node is unaware of. Orphan transactions are very common for new nodes that have just completed Initial Block Download and do not have an up-to-date mempool. Nodes also download transactions from multiple peers. If the peer from which a child transaction was requested responds faster than the peer from which its parent was requested, that child is seen as an orphan transaction.

Nodes may handle orphans by storing them in a cache and requesting any missing parent(s) by txid (prevouts specify txid, not wtxid). These parents may end up being orphans as well, if they also spend unconfirmed inputs that the node is unaware of. This method of handling orphans is problematic for two reasons: it requires nodes to allocate memory for unvalidated data received on the p2p network and it relies on txid-based relay between two wtxid-relay peers.

This proposal makes orphan resolution more efficient and no longer require txid-based relay.

Definitions

Given any two transactions Tx0 and Tx1 where Tx1 spends an output of Tx0, Tx0 is a parent of Tx1 and Tx1 is a child of Tx0.

A transaction's ancestors include, recursively, its parents, the parents of its parents, etc. A transaction's descendants include, recursively, its children, the children of its children, etc. A transaction's parent is its ancestor, but an ancestor is not necessarily a parent.

A package is a list of transactions, representable by a connected Directed Acyclic Graph (a directed edge exists between a transaction that spends the output of another transaction). In this proposal, a package is limited to unconfirmed transactions.

An ancestor package consists of an unconfirmed transaction with all of its unconfirmed ancestors.

In a topologically sorted package, each parent appears somewhere in the list before its child.

Specification

Ancestor Package Relay includes two parts: a package information round and a transaction data download round. The package information round is used to help a receiver learn what transactions are in a package and decide whether they want to download them. The transaction data round is used to help a node download multiple transactions in one message instead of as separate messages.

Package relay is negotiated between two peers during the version handshake using a "sendpackages" message. The versions field within "sendpackages" is interpreted as a bitfield; peers may relay multiple versions of packages. Package relay requires both peers to support wtxid-based relay because package transactions are referenced by their wtxids.

400px

Nodes indicate support for batched transaction data round ("getpkgtxns", "pkgtxns", and "MSG_PKGTXNS") using the PKG_RELAY_PKGTXNS = (1 << 0) bit in their "sendpackages" messages during version handshake. They indicate support for the ancestor package information round ("ancpkginfo", "MSG_ANCPKGINFO") using the PKG_RELAY_ANC = (1 << 1) bit in their "sendpackages" messages during version handshake.

Protocol Flow Examples

This package relay protocol satisfies both use cases (orphan transaction handling and high-feerate transaction paying for low-feerate ancestors).

Orphan Transaction Handling

Upon receiving an orphan transaction, a node may request ancestor package information delineating the wtxids of the transaction's unconfirmed ancestors. This is done without using txid-based relay. The package information can be used to request transaction data. As these transactions are dependent upon one another to be valid, the transactions can be requested and sent as a batch.

Contrast this protocol with legacy orphan handling, which requires requesting the missing transactions by their txids and may require new round trips for each generation of missing parents. 1000px

Fee-Bumped Transactions

Too-low-feerate transactions (i.e. below the node's minimum mempool feerate) with high-feerate descendants can also be relayed this way. If the peers are using BIP133 fee filters and a low-feerate transaction is below the node's fee filter, the sender will not announce it. The high-feerate transaction will be sent by the sender, and received and handled as an orphan by the receiver, the transactions are validated as a package, and so the protocol naturally works for this use case.

This does not mean BIP133 is required for package relay to work, provided that nodes do not immediately reject transactions previously found to be too low feerate. If the low-feerate transaction was sent and rejected, the receiver should later re-request and accept it after learning that it is the ancestor of another transaction, and that they meet the receiver's mempool policy requirements when validated together.

600px

This protocol is receiver-initiated only; nodes do not proactively announce packages to their peers.

Combined Hash

A "combined hash" serves as a unique "packa