BIP 331: Ancestor Package Relay #1382

 137 | +[[File:./bip-package-relay/tx_scenarios.png|800px]]
 138 | +
 139 | +'''No Package Information Round:''' Instead of having a package information round, just use the
 140 | +child's wtxid to refer to the package and always send the entire package together. This would make
 141 | +it very likely for honest nodes to redownload duplicate transactions.
 142 | +[[File:./bip-package-relay/no_package_info.png|900px]]

---

  88 | +changing its txid; a node cannot use txid to deduplicate transactions it has already downloaded
  89 | +or validated. Ideally, two nodes that both support BIP339 wtxid-based transaction relay shouldn't
  90 | +ever need to use txid-based transaction relay.
  91 | +
  92 | +A single use case of txid-based relay remains: handling "orphan" transactions that spend
  93 | +output(s) from a transaction they are unaware of.  Orphans are common for new nodes that have just

---

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

---

 108 | +
 109 | +A transaction's '''ancestors''' include, recursively, its parents, the parents of its parents, etc.
 110 | +A transaction's '''descendants''' include, recursively, its children, the children of its children,
 111 | +etc. A transaction's parent is its ancestor, but an ancestor is not necessarily a parent.
 112 | +
 113 | +A '''package''' is an ordered list of transactions, representable by a connected Directed Acyclic

---

 131 | +For example, consider the following scenarios (where the mempool minimum feerate is 3sat/vB and all
 132 | +transactions are the same size):
 133 | +
 134 | +* Package {A, B} where A pays 0 satoshis and B pays 8000 satoshis in fees.
 135 | +* Package {C, D} where C pays 0 satoshis and D pays 1200 satoshis in fees.
 136 | +* Package {E, F, G, H, J} that pays 4000, 8000, 0, 2000, and 4000 satoshis in fees, respectively.

---

 129 | +network bandwidth, avoid downloading a transaction more than once, avoid downloading transactions
 130 | +that are eventually rejected, and minimize storage allocated for not-yet-validated transactions.
 131 | +For example, consider the following scenarios (where the mempool minimum feerate is 3sat/vB and all
 132 | +transactions are the same size):
 133 | +
 134 | +* Package {A, B} where A pays 0 satoshis and B pays 8000 satoshis in fees.

---

 133 | +
 134 | +* Package {A, B} where A pays 0 satoshis and B pays 8000 satoshis in fees.
 135 | +* Package {C, D} where C pays 0 satoshis and D pays 1200 satoshis in fees.
 136 | +* Package {E, F, G, H, J} that pays 4000, 8000, 0, 2000, and 4000 satoshis in fees, respectively.
 137 | +[[File:./bip-0331/tx_scenarios.png|800px]]
 138 | +

---

 138 | +
 139 | +'''No Package Information Round:''' Instead of having a package information round, just use the
 140 | +child's wtxid to refer to the package and always send the entire package together. This would make
 141 | +it very likely for honest nodes to redownload duplicate transactions.
 142 | +[[File:./bip-0331/no_package_info.png|900px]]
 143 | +

---

 159 | +Too-low-feerate transactions (i.e. below the node's minimum mempool feerate) with high-feerate
 160 | +descendants can also be relayed this way. If the peers are using BIP133 fee filters and a
 161 | +low-feerate transaction is below the node's fee filer, the sender will not announce it. The
 162 | +high-feerate transaction is seen and handled as an orphan, the transactions are validated as a
 163 | +package, and so the protocol naturally works for this use case.<ref>'''Does this mean BIP133 is
 164 | +required for package relay to work?'''No. If the low-feerate transaction was sent because it wasn't

---

 269 | +
 270 | +# The "pkgtxns" message has the structure defined above, with pchCommand == "pkgtxns".
 271 | +
 272 | +# A "pkgtxns" message should contain the transaction data requested using "getpkgtxns".
 273 | +
 274 | +# Upon reeipt of a "pkgtxns" message, the node should validate the transactions together as a package rather than individually.

---

 331 | +# This inv type should only be used if both peers agreed to send version 0 packages. If a "getdata" message with type MSG_ANCPKGINFO is received from a peer with which ancestor package relay was not negotiated, the sender may be disconnected.
 332 | +
 333 | +====MSG_PKGTXNS====
 334 | +
 335 | +# A new inv type (MSG_PKGTXNS == 0x7) is added, for use only in "notfound" messages pertaining to
 336 | +package transactions.

---

 203 | +
 204 | +===Combined Hash===
 205 | +
 206 | +A "combined hash" serves as a unique "package id" for some list of unique transactions.
 207 | +
 208 | +The combined hash of a package of transactions is equal to the hash of each transaction's wtxid, concatenated in lexicographical order.

---

 314 | +
 315 | +# Upon receipt of a malformed "ancpkginfo" message that does not contain the ancestor package of the transaction (which the node learns after receiving the transaction data and validating them), the sender may be disconnected.
 316 | +
 317 | +# A node MUST NOT send a "ancpkginfo" message that has not been requested by the recipient. Upon receipt of an unsolicited "ancpkginfo", a node may disconnect the sender.
 318 | +
 319 | +# A "ancpkginfo" message should only be sent if both peers agreed to send version 0 packages. If a "ancpkginfo" message is received from a peer with which ancestor package relay was not negotiated, the sender may be disconnected.

---

  25 | +selecting them for inclusion in blocks
  26 | +<ref>[https://github.com/bitcoin/bitcoin/pull/7600 Select transactions using feerate-with-ancestors]</ref>.
  27 | +Incentive-compatible mempool and miner policies help create a fair, fee-based market for block
  28 | +space. While miners maximize transaction fees in order to earn higher block rewards, non-mining
  29 | +users participating in transaction relay reap many benefits from employing policies that result in a
  30 | +mempool with the same contents, including faster compact block relay and more accurate fee

---

  61 | +</ref>
  62 | +
  63 | +These transactions must meet a certain confirmation target to be effective, but their feerates
  64 | +are negotiated well ahead of broadcast time. If the forecasted feerate was too low and no
  65 | +fee-bumping options are available, attackers can steal money from their counterparties.  Always
  66 | +overestimating fees may sidestep this issue temporarily (while mempool traffic is low and

---

  59 | +* [https://github.com/t-bast/lightning-docs/blob/master/pinning-attacks.md T-bast's Pinning Attacks Document]
  60 | +* [https://gist.github.com/instagibbs/60264606e181451e977e439a49f69fe1 Eltoo Pinning]
  61 | +</ref>
  62 | +
  63 | +These transactions must meet a certain confirmation target to be effective, but their feerates
  64 | +are negotiated well ahead of broadcast time. If the forecasted feerate was too low and no

---

  62 | +
  63 | +These transactions must meet a certain confirmation target to be effective, but their feerates
  64 | +are negotiated well ahead of broadcast time. If the forecasted feerate was too low and no
  65 | +fee-bumping options are available, attackers can steal money from their counterparties.  Always
  66 | +overestimating fees may sidestep this issue temporarily (while mempool traffic is low and
  67 | +predictable), but this solution is not foolproof and wastes users' money. For some attacks,

---

  77 | +
  78 | +Theoretically, developing a safe and incentive-compatible package mempool acceptance policy is
  79 | +sufficient to solve this issue. Nodes could opportunistically accept packages (e.g. by trying
  80 | +combinations of transactions rejected from their mempools), but this practice would likely be
  81 | +inefficient at best and open new Denial of Service attacks at worst.  As such, this proposal
  82 | +suggests adding new p2p messages enabling nodes to request and share package validation-related

---

  88 | +changing its txid; a node cannot use txid to deduplicate transactions it has already downloaded
  89 | +or validated. Ideally, two nodes that both support BIP339 wtxid-based transaction relay shouldn't
  90 | +ever need to use txid-based transaction relay.
  91 | +
  92 | +A single use case of txid-based relay remains: handling "orphan" transactions that spend output(s)
  93 | +from a transaction the receiving node is unaware of.  Orphans are common for new nodes that have

---

 132 | +transactions are 1000vB in size):
 133 | +
 134 | +* Package {A, B} where A pays 0 satoshis and B pays 8000 satoshis in fees.
 135 | +* Package {C, D} where C pays 0 satoshis and D pays 1200 satoshis in fees.
 136 | +* Package {E, F, G, H, J} that pay 4000, 8000, 0, 2000, and 4000 satoshis in fees, respectively.
 137 | +[[File:./bip-0331/tx_scenarios.png|800px]]

---

 133 | +
 134 | +* Package {A, B} where A pays 0 satoshis and B pays 8000 satoshis in fees.
 135 | +* Package {C, D} where C pays 0 satoshis and D pays 1200 satoshis in fees.
 136 | +* Package {E, F, G, H, J} that pay 4000, 8000, 0, 2000, and 4000 satoshis in fees, respectively.
 137 | +[[File:./bip-0331/tx_scenarios.png|800px]]
 138 | +< br/>

---

 205 | +
 206 | +===Combined Hash===
 207 | +
 208 | +A "combined hash" serves as a unique "package id" for some list of unique transactions.
 209 | +
 210 | +The combined hash of a package of transactions is equal to the hash of each transaction's wtxid, concatenated in lexicographical order.

---

  67 | +predictable), but this solution is not foolproof and wastes users' money. For some attacks,
  68 | +the available defenses require nodes to have a bird's-eye view of Bitcoin nodes' mempools,
  69 | +which is an unreasonable security requirement.
  70 | +
  71 | +The best solution is to enable nodes to consider packages of transactions as a unit, e.g. one or
  72 | +more low-fee parent transactions with a high-fee child, instead of separately. A package-aware

---

 149 | +transaction download fails for some reason, it shouldn't be used as the default because it always
 150 | +requires storage of unvalidated transactions.
 151 | +[[File:./bip-0331/package_info_only.png|1200px]]
 152 | +</ref>
 153 | +
 154 | +Upon encountering an orphan, a node may request ancestor package information delineating the wtxids

---

 119 | +
 120 | +==Specification==
 121 | +
 122 | +===Intended Protocol Flow===
 123 | +
 124 | +Package Relay consists of two phases: a package information round and a transaction data round.

---

 159 | +[[File:./bip-0331/protocol_flow.png|1200px]]
 160 | +
 161 | +Too-low-feerate transactions (i.e. below the node's minimum mempool feerate) with high-feerate
 162 | +descendants can also be relayed this way. If the peers are using BIP133 fee filters and a
 163 | +low-feerate transaction is below the node's fee filer, the sender will not announce it. The
 164 | +high-feerate transaction is seen and handled as an orphan, the transactions are validated as a

---

 160 | +
 161 | +Too-low-feerate transactions (i.e. below the node's minimum mempool feerate) with high-feerate
 162 | +descendants can also be relayed this way. If the peers are using BIP133 fee filters and a
 163 | +low-feerate transaction is below the node's fee filer, the sender will not announce it. The
 164 | +high-feerate transaction is seen and handled as an orphan, the transactions are validated as a
 165 | +package, and so the protocol naturally works for this use case.<ref>'''Does this mean BIP133 is

---

 281 | +It was [https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-May/020496.html suggested] that
 282 | +this message is not package-specific and generally useful for downloading transactions as
 283 | +batches.</ref>
 284 | +
 285 | +
 286 | +====ancpkginfo====

---

 326 | +
 327 | +# A new inv type (MSG_ANCPKGINFO == 0x6) is added, for use only in getdata requests pertaining to ancestor packages.
 328 | +
 329 | +# As a getdata request type, it indicates that the sender wants a "ancpkginfo" containing all of the unconfirmed ancestors of a transaction, referenced by wtxid.
 330 | +
 331 | +# Upon receipt of a "getdata(MSG_ANCPKGINFO)" request for, the node should respond with the "ancpkginfo" corresponding to the transaction's unconfirmed ancestor package, or with NOTFOUND.  The wtxid of the requested transaction should be the last item in the list. The node should not assume that the sender is requesting the transaction data as well.

---

 328 | +
 329 | +# As a getdata request type, it indicates that the sender wants a "ancpkginfo" containing all of the unconfirmed ancestors of a transaction, referenced by wtxid.
 330 | +
 331 | +# Upon receipt of a "getdata(MSG_ANCPKGINFO)" request for, the node should respond with the "ancpkginfo" corresponding to the transaction's unconfirmed ancestor package, or with NOTFOUND.  The wtxid of the requested transaction should be the last item in the list. The node should not assume that the sender is requesting the transaction data as well.
 332 | +
 333 | +# The inv type should not be used in announcements, i.e. "inv(MSG_ANCPKGINFO)" should never be sent.

---

 314 | +downloaded. See [https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-June/020558.html discussion].
 315 | +</ref>
 316 | +
 317 | +# Upon receipt of a "ancpkginfo" message, the node may use it to request the transactions not already in its mempool.
 318 | +
 319 | +# Upon receipt of a malformed "ancpkginfo" message that does not contain the ancestor package of the transaction (which the node learns after receiving the transaction data and validating them), the sender may be disconnected.

---

 330 | +
 331 | +# Upon receipt of a "getdata(MSG_ANCPKGINFO)" request for, the node should respond with the "ancpkginfo" corresponding to the transaction's unconfirmed ancestor package, or with NOTFOUND.  The wtxid of the requested transaction should be the last item in the list. The node should not assume that the sender is requesting the transaction data as well.
 332 | +
 333 | +# The inv type should not be used in announcements, i.e. "inv(MSG_ANCPKGINFO)" should never be sent.
 334 | +
 335 | +# This inv type should only be used if both peers agreed to send version 0 packages. If a "getdata" message with type MSG_ANCPKGINFO is received from a peer with which ancestor package relay was not negotiated, the sender may be disconnected.

---

 318 | +
 319 | +# Upon receipt of a malformed "ancpkginfo" message that does not contain the ancestor package of the transaction (which the node learns after receiving the transaction data and validating them), the sender may be disconnected.
 320 | +
 321 | +# A node MUST NOT send a "ancpkginfo" message that has not been requested by the recipient. Upon receipt of an unsolicited "ancpkginfo", a node may disconnect the sender.
 322 | +
 323 | +# A "ancpkginfo" message should only be sent if both peers agreed to send version 0 packages. If a "ancpkginfo" message is received from a peer with which ancestor package relay was not negotiated, the sender may be disconnected.

---

 254 | +
 255 | +# The "getpkgtxns" message has the structure defined above, with pchCommand == "getpkgtxns".
 256 | +
 257 | +# A "getpkgtxns" message should be used to request all or some of the transactions previously announced in a "ancpkginfo" message, specified by witness transaction id. This message is intended to allow nodes to avoid downloading and storing transactions that cannot be validated immediately.
 258 | +
 259 | +# Upon receipt of a "getpkgtxns" message, a node must respond with either a "pkgtxns" containing the requested transactions or "notfound" messages indicating one or more of the transactions is unavailable.<ref>'''Why isn't package relay negotiation required for getpkgtxns?'''

---

 186 | +right, I propose we hold off on sender-initiated for now, deploy receiver-initiated package relay,
 187 | +observe its usage and figure out where we can save a round trip, and then introduce a
 188 | +well-researched sender-initiated package relay protocol.</ref>
 189 | +
 190 | +Ancestor package relay is negotiated between two peers during the version handshake using a
 191 | +"sendpackages" message containing version=1. It requires both peers to support wtxid-based relay

---

 238 | +Yes, this is allowed in order to reduce the number of negotiation steps. This means nodes can
 239 | +announce features without first checking what the other peer has sent, and then apply logic at the
 240 | +end. See [https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-May/020510.html discussion].
 241 | +</ref>
 242 | +
 243 | +# Version=0 packages correspond to ancestor packages, i.e. "ancpkginfo" and "MSG_ANCPKGINFO".

---

 348 | +Older clients remain fully compatible and interoperable after this change. Clients implementing this
 349 | +protocol will only attempt to send and request packages if agreed upon during the version handshake.
 350 | +<ref>'''Will package relay cause non-package relay nodes to waste bandwidth on low-feerate transactions?'''
 351 | +If a node supports package relay, it may accept low-feerate transactions (e.g. paying zero fees)
 352 | +into its mempool, but non-package relay nodes would most likely reject them. To mitigate bandwidth
 353 | +waste, a package relay node should probably not announce descendants of below-fee-filter

---

 362 | +
 363 | +==Implementation==
 364 | +
 365 | +Implementation for Bitcoin Core: https://github.com/glozow/bitcoin/tree/2023-01-package-relay
 366 | +
 367 | +Caveat: the crux of package relay is a mempool policy that works.

---

 110 | +A transaction's '''descendants''' include, recursively, its children, the children of its children,
 111 | +etc. A transaction's parent is its ancestor, but an ancestor is not necessarily a parent.
 112 | +
 113 | +A '''package''' is a list of transactions, representable by a connected Directed Acyclic
 114 | +Graph (a directed edge exists between a transaction that spends the output of another transaction).
 115 | +Typically, a package refers to unconfirmed transactions.

---

 154 | +Upon encountering an orphan, a node may request ancestor package information delineating the wtxids
 155 | +of the transaction's unconfirmed ancestors. This is done without using txid-based relay. The package
 156 | +information can be used to request transaction data. As these transactions are dependent upon one
 157 | +another to be valid, the transactions can be requested and sent as a batch.
 158 | +
 159 | +[[File:./bip-0331/protocol_flow.png|1200px]]

---

 218 | +====sendpackages====
 219 | +
 220 | +{|
 221 | +|  Field Name  ||  Type  ||  Size  ||  Purpose
 222 | +|-
 223 | +|version || uint32_t || 4 || Denotes a package version supported by the node.

---

 231 | +# Upon receipt of a "sendpackages" message with a version that is not supported, a node must treat the peer as if it never received the message.
 232 | +
 233 | +# The "sendpackages" message MUST be sent before sending a "verack" message. If a "sendpackages" message is received afer "verack", the sender may be disconnected.
 234 | +
 235 | +# A node that sends "sendpackages" MUST also send "wtxidrelay". Upon receipt of a "verack", if the sender has sent a "sendpackages" but not "wtxidrelay", the sender may be disconnected.
 236 | +

---

 334 | +
 335 | +# This inv type should only be used if both peers agreed to send version 0 packages. If a "getdata" message with type MSG_ANCPKGINFO is received from a peer with which ancestor package relay was not negotiated, the sender may be disconnected.
 336 | +
 337 | +====MSG_PKGTXNS====
 338 | +
 339 | +# A new inv type (MSG_PKGTXNS == 0x7) is added, for use only in "notfound" messages pertaining to package transactions.

---

  29 | +users participating in transaction relay reap many benefits from employing policies that result in a
  30 | +mempool with the same contents, including faster compact block relay and more accurate fee
  31 | +estimation. Additionally, users may take advantage of mempool and miner policy to bump the priority
  32 | +of their transactions by attaching high-fee descendants (Child Pays for Parent or CPFP).
  33 | +
  34 | +Only considering transactions one at a time for submission to the mempool creates a limitation in

---

  37 | +transaction's descendants when considering which of two conflicting transactions to keep (Replace by
  38 | +Fee or RBF).
  39 | +
  40 | +When a user's transaction does not meet a mempool's minimum feerate and they cannot create a
  41 | +replacement transaction directly, their transaction will simply be rejected by this mempool. They
  42 | +also cannot attach a descendant to pay for replacing a conflicting transaction.

---

 158 | +
 159 | +[[File:./bip-0331/protocol_flow.png|1200px]]
 160 | +
 161 | +Too-low-feerate transactions (i.e. below the node's minimum mempool feerate) with high-feerate
 162 | +descendants can also be relayed this way. If the peers are using BIP133 fee filters and a
 163 | +low-feerate transaction is below the node's fee filer, the sender will not announce it. The

---

 183 | +to design the sender-initiated protocol carefully, and inform the design decisions using data
 184 | +collected from the mainnet p2p network. However, there is no historical transaction data to use
 185 | +because the goal is to enable currently-rejected transactions to propagate. In order to get this
 186 | +right, I propose we hold off on sender-initiated for now, deploy receiver-initiated package relay,
 187 | +observe its usage and figure out where we can save a round trip, and then introduce a
 188 | +well-researched sender-initiated package relay protocol.</ref>

---

 203 | +
 204 | +[[File:./bip-0331/version_negotiation.png|600px]]
 205 | +
 206 | +===Combined Hash===
 207 | +
 208 | +A "combined hash" serves as a unique "package id" for some list of unique transactions.

---

 233 | +historical data is available, as one of the primary goals of this protocol is to enable
 234 | +currently-rejected transactions to propagate. After deploying receiver-initiated package relay, we
 235 | +can observe its usage and then introduce a sender-initiated package relay protocol informed by data
 236 | +collected from the p2p network.</ref>
 237 | +
 238 | +===Combined Hash===

---

 258 | +|-
 259 | +|}
 260 | +
 261 | +# The "sendpackages" message has the structure defined above, with pchCommand == "sendpackages".
 262 | +
 263 | +# During version handshake, nodes should one "sendpackages" message indicating they support package relay, with the versions field indicating which versions of they support.

---

 122 | +ancestors.
 123 | +
 124 | +In a '''topologically sorted''' package, each parent appears somewhere in the list before its child.
 125 | +
 126 | +==Specification==
 127 | +

---

 178 | +supporting version n, it should be easy to announce support for version n-1, but not version n,
 179 | +packages.</ref>
 180 | +
 181 | +[[File:./bip-0331/version_negotiation.png|400px]]
 182 | +
 183 | +===Ancestor Package Information===

---

 159 | +
 160 | +This protocol can be extended to include more types of package information in the future, while
 161 | +continuing to use the same messages for transaction data download.
 162 | +[[File:./bip-0331/generic_package_relay.png|600px]]
 163 | +
 164 | +Package relay is negotiated between two peers during the version handshake using a "sendpackages"

---

 280 | +|txns||List of wtxids||txns_length * 32|| The wtxids of each transaction in the package.
 281 | +|}
 282 | +
 283 | +# The "getpkgtxns" message has the structure defined above, with pchCommand == "getpkgtxns".
 284 | +
 285 | +# A "getpkgtxns" message should be used to request some list of transactions specified by witness transaction id. It indicates that the node wants to receiver either all the specified transactions or none of them. This messages is intended to allow nodes to avoid downloading and storing transactions that cannot be validated without each other. The list of transactions does not need to correspond to a previously-received pkginfo message.

---

 260 | +
 261 | +# The "sendpackages" message has the structure defined above, with pchCommand == "sendpackages".
 262 | +
 263 | +# During version handshake, nodes should one "sendpackages" message indicating they support package relay, with the versions field indicating which versions of they support.
 264 | +
 265 | +# The "sendpackages" message MUST be sent before sending a "verack" message. If a "sendpackages" message is received afer "verack", the sender may be disconnected.

---

 282 | +
 283 | +# The "getpkgtxns" message has the structure defined above, with pchCommand == "getpkgtxns".
 284 | +
 285 | +# A "getpkgtxns" message should be used to request some list of transactions specified by witness transaction id. It indicates that the node wants to receiver either all the specified transactions or none of them. This messages is intended to allow nodes to avoid downloading and storing transactions that cannot be validated without each other. The list of transactions does not need to correspond to a previously-received pkginfo message.
 286 | +
 287 | +# Upon receipt of a "getpkgtxns" message, a node should respond with either a "pkgtxns" containing all of the requested transactions in the same order specified in the "getpkgtxns" request or one "notfound" message of type MSG_PKGTXNS and combined hash indicating one or more of the transactions is unavailable.<ref>'''Why isn't package relay negotiation required for getpkgtxns?'''

---

 303 | +
 304 | +# A "pkgtxns" message should contain the transaction data requested using "getpkgtxns".
 305 | +
 306 | +# Upon receipt of a "pkgtxns" message, the node should validate the transactions together as a package rather than individually.
 307 | +
 308 | +# A "pkgtxns" message should only be sent to a peer that requested the package using "getpkgtxns".  If a node receives an unsolicited package, the sender may be disconnected.<ref>'''Why isn't package relay negotiation required for pkgtxns?'''

---

 180 | +
 181 | +[[File:./bip-0331/version_negotiation.png|400px]]
 182 | +
 183 | +===Ancestor Package Information===
 184 | +
 185 | +Ancestor Package Relay allows nodes to send and request a transaction's list of unconfirmed

---

 262 | +
 263 | +# During version handshake, nodes should one "sendpackages" message indicating they support package relay, with the versions field indicating which versions of they support.
 264 | +
 265 | +# The "sendpackages" message MUST be sent before sending a "verack" message. If a "sendpackages" message is received afer "verack", the sender may be disconnected.
 266 | +
 267 | +# Upon successful connection ("verack" sent by both peers), a node may relay packages with the peer if they did not set "fRelay" to false in the "version" message, both peers sent "wtxidrelay", and both peers sent "sendpackages" for matching version(s). Peers should relay packages corresponding to versions that both sent "sendpackages" for.<ref>'''Is it ok to send "sendpackages" to a peer that specified fRelay=false in their "version" message?'''

---

 184 | +
 185 | +Ancestor Package Relay allows nodes to send and request a transaction's list of unconfirmed
 186 | +ancestors.  Nodes indicate support for Ancestor Package Relay by adding the
 187 | +<code>PKG_RELAY_ANCPKG = (1 << 0)</code> bit in their "sendpackages" messages during version handshake.
 188 | +
 189 | +===Intended Protocol Flow===

---

  45 | +This limitation harms users' ability to fee-bump their transactions. Further, it presents a security
  46 | +issue in contracting protocols which rely on presigned, time-sensitive transactions<ref>'''Examples of time-sensitive pre-signed transactions in L2 protocols.'''
  47 | +* [https://github.com/lightning/bolts/blob/master/03-transactions.md#htlc-timeout-and-htlc-success-transactions HTCL-Timeout in LN Penalty]
  48 | +* [https://github.com/revault/practical-revault/blob/master/transactions.md#cancel_tx Unvault Cancel in Revault]
  49 | +* [https://github.com/discreetlogcontracts/dlcspecs/blob/master/Transactions.md#refund-transaction Refund Transaction in Discreet Log Contracts]
  50 | +* [https://gist.github.com/instagibbs/60264606e181451e977e439a49f69fe1 Updates in Eltoo]

---

 137 | +that are eventually rejected, and minimize storage allocated for not-yet-validated transactions.
 138 | +
 139 | +<br />
 140 | +
 141 | +'''No Package Information Round:''' One proposal is to just use the child's wtxid to refer to the
 142 | +package and always send the entire package together, skipping the package information round.

---

 160 | +multiple versions of packages. Package relay requires both peers to support wtxid-based relay
 161 | +because package transactions are referenced by their wtxids.
 162 | +<ref>'''Why do we need multiple versions? Why can't we just support arbitrary packages?'''
 163 | +Attempting to support arbitrary packages in mempool validation may result in very complex logic, new
 164 | +Denial of Service attack vectors, and policy limitations that could be leveraged to censor
 165 | +transactions (aka "pinning attacks"). This protocol is extensible to support up to 32 types of

---

 215 | +<ref>'''Why no sender-initiated protocol?''' Sender-initiated package
 216 | +relay can, theoretically, save a round trip by notifying the receiver ahead of time that they will
 217 | +probably need to request and validate a group of transactions together in order for them to be
 218 | +accepted. As with any proactive communication, there is a chance that the receiver already knows
 219 | +this information, so this network bandwidth may be wasted. Shortened latency is less significant
 220 | +than wasted bandwidth.

---

 384 | +continuing to use the same messages for transaction data download. One would define a new package
 385 | +information message, allocate its corresponding inv type, and its bit in the versions field of
 386 | +"sendpackages".  A future version of package relay may allow a sender-initiated dialogue if it is
 387 | +specified that the "*PKGINFO" inv type can be used in an "inv" message.
 388 | +<br />
 389 | +[[File:./bip-0331/generic_package_relay.png|600px]]

---

  15 | +Peer-to-peer protocol messages enabling nodes to request and relay the unconfirmed ancestor package
  16 | +of a given transaction, and to request and relay transactions in batches.
  17 | +
  18 | +==Motivation==
  19 | +
  20 | +(1) Help incentive-compatible transactions propagate.

---

  81 | +combinations of transactions rejected from their mempools), but this practice would likely be
  82 | +inefficient at best and open new Denial of Service attacks at worst.  As such, this proposal
  83 | +suggests adding new p2p messages enabling nodes to request and share package-validation-related
  84 | +information with one another, resulting in a more efficient and reliable way to propagate packages.
  85 | +
  86 | +(2) Eliminate the need for txid-based transaction relay and make orphan handling more robust.

---

 123 | +
 124 | +In a '''topologically sorted''' package, each parent appears somewhere in the list before its child.
 125 | +
 126 | +==Specification==
 127 | +
 128 | +Ancestor Package Relay includes two parts: package information and transaction data download.

---

 126 | +==Specification==
 127 | +
 128 | +Ancestor Package Relay includes two parts: package information and transaction data download.
 129 | +A package information round is used to help a receiver learn what transactions are in a package and
 130 | +whether they want to download them. The transaction data round is used to help a node download
 131 | +multiple transactions in one message instead of as separate messages.

---

 156 | +</ref>
 157 | +
 158 | +Package relay is negotiated between two peers during the version handshake using a "sendpackages"
 159 | +message. The versions field within "sendpackages" is interpreted as a bitfield; peers may relay
 160 | +multiple versions of packages. Package relay requires both peers to support wtxid-based relay
 161 | +because package transactions are referenced by their wtxids.

---

 167 | +different types of packages and/or contain more information than a list of wtxids, e.g. feerate or
 168 | +relationships between transactions.</ref>
 169 | +<ref>'''Why send one message per version instead of sending a single message for the highest
 170 | +supported version?''' It should also be possible to support some subset of the existing package
 171 | +types. For example, if a node's mempool policy doesn't support or a node implementation stops
 172 | +supporting version n, it should be easy to announce support for version n-1, but not version n,

---

 303 | +
 304 | +====MSG_ANCPKGINFO====
 305 | +
 306 | +# A new inv type (MSG_ANCPKGINFO == 0x7) is added, for use only in getdata requests pertaining to ancestor packages.
 307 | +
 308 | +# As a getdata request type, it indicates that the sender wants a "ancpkginfo" containing all of the unconfirmed ancestors of a transaction, referenced by wtxid.

---

 305 | +
 306 | +# A new inv type (MSG_ANCPKGINFO == 0x7) is added, for use only in getdata requests pertaining to ancestor packages.
 307 | +
 308 | +# As a getdata request type, it indicates that the sender wants a "ancpkginfo" containing all of the unconfirmed ancestors of a transaction, referenced by wtxid.
 309 | +
 310 | +# Upon receipt of a "getdata(MSG_ANCPKGINFO)" request, the node should respond with an "ancpkginfo" message corresponding to the transaction's unconfirmed ancestor package, or with "notfound".  The wtxid of the requested transaction should be the last item in the list.

---

 307 | +
 308 | +# As a getdata request type, it indicates that the sender wants a "ancpkginfo" containing all of the unconfirmed ancestors of a transaction, referenced by wtxid.
 309 | +
 310 | +# Upon receipt of a "getdata(MSG_ANCPKGINFO)" request, the node should respond with an "ancpkginfo" message corresponding to the transaction's unconfirmed ancestor package, or with "notfound".  The wtxid of the requested transaction should be the last item in the list.
 311 | +
 312 | +# The inv type should not be used in announcements, i.e. "inv(MSG_ANCPKGINFO)" must never be sent.  If a "inv(MSG_ANCPKGINFO)" is received, the sender may be disconnected.

---

 146 | +
 147 | +[[File:./bip-0331/no_package_info.png|600px]]
 148 | +<br />
 149 | +
 150 | +'''Package Information Only:''' Just having package information gives enough information for the
 151 | +receiver to accept the packages. Omit the "getpkgtxns" and "pkgtxns" messages and just download the

---

 346 | +
 347 | +# A "pkgtxns" message should contain the transaction data requested using "getpkgtxns".
 348 | +
 349 | +# Upon receipt of a "pkgtxns" message, the node should validate the transactions together as a package rather than individually.
 350 | +
 351 | +# A "pkgtxns" message should only be sent to a peer that requested the package using "getpkgtxns".  If a node receives an unsolicited package, the sender may be disconnected.<ref>'''Why isn't package relay negotiation required for pkgtxns?'''

---

 325 | +
 326 | +# The "getpkgtxns" message has the structure defined above, with pchCommand == "getpkgtxns".
 327 | +
 328 | +# A "getpkgtxns" message should be used to request some list of transactions specified by witness transaction id. It indicates that the node wants to receive either all the specified transactions or none of them. This message is intended to allow nodes to avoid downloading and storing transactions that cannot be validated without each other. The list of transactions does not need to correspond to a previously-received pkginfo message.
 329 | +
 330 | +# Upon receipt of a "getpkgtxns" message, a node should respond with either a "pkgtxns" containing all of the requested transactions in the same order specified in the "getpkgtxns" request or one "notfound" message of type MSG_PKGTXNS and combined hash of all of the wtxids in the "getpkgtxns" request (only one "notfound" message and nothing else), indicating one or more of the transactions is unavailable.<ref>'''Why isn't package relay negotiation required for getpkgtxns?'''

---

 372 | +non-package relay peers.
 373 | +</ref>
 374 | +<ref>'''Is Package Erlay possible?'''
 375 | +A client using BIP330 reconciliation-based transaction relay (Erlay) is able to use package relay
 376 | +without interference. After reconciliation, any transactions with unconfirmed ancestors may be
 377 | +relayed using ancestor package relay.

---

 344 | +
 345 | +# The "pkgtxns" message has the structure defined above, with pchCommand == "pkgtxns".
 346 | +
 347 | +# A "pkgtxns" message should contain the transaction data requested using "getpkgtxns".
 348 | +
 349 | +# Upon receipt of a "pkgtxns" message, the node should validate the transactions together as a package rather than individually.

---

 329 | +
 330 | +# A "getpkgtxns" message should be used to request some list of transactions specified by witness transaction id. It indicates that the node wants to receive either all the specified transactions or none of them. This message is intended to allow nodes to avoid downloading and storing transactions that cannot be validated without each other. The list of transactions does not need to correspond to a previously-received pkginfo message.
 331 | +
 332 | +# Upon receipt of a "getpkgtxns" message, a node should respond with either a "pkgtxns" containing all of the requested transactions in the same order specified in the "getpkgtxns" request or one "notfound" message of type MSG_PKGTXNS and combined hash of all of the wtxids in the "getpkgtxns" request (only one "notfound" message and nothing else), indicating one or more of the transactions is unavailable.
 333 | +
 334 | +# A "getpkgtxns" message must contain at most 100 wtxids. Upon receipt of a "getpkgtxns" message with more than 100 wtxids, a node may ignore the message (to avoid calculating the combined hash) and disconnect the sender.

---

 269 | +|txns||List of wtxids||txns_length * 32|| The wtxids of each transaction in the package.
 270 | +|}
 271 | +
 272 | +# The "ancpkginfo" message has the structure defined above, with pchCommand == "ancpkginfo".
 273 | +
 274 | +# The "txns" field should contain a list of wtxids which constitute the ancestor package of the last wtxid. The sender should - but is not required to - sort these wtxids in topological order. The topological sort can be achieved by sorting the transactions by mempool acceptance order (if parents are always accepted before children). Nodes should not disconnect or punish a peer who provides a list not sorted in topological order.<ref>'''Why not include feerate information to help the receiver decide whether these transactions are worth downloading?'''

---

 264 | +{|
 265 | +|  Field Name  ||  Type  ||  Size  ||   Purpose
 266 | +|-
 267 | +|txns_length||CompactSize||1 or 3 bytes|| The number of transactions provided.
 268 | +|-
 269 | +|txns||List of wtxids||txns_length * 32|| The wtxids of each transaction in the package.

---

 297 | +
 298 | +# Upon receipt of a "ancpkginfo" message, the node may use it to request the transactions it does not already have (e.g. using "getpkgtxns" or "tx").
 299 | +
 300 | +# Upon receipt of a malformed "ancpkginfo" message, the sender may be disconnected. An "ancpkginfo" message is malformed if it contains duplicate wtxids or conflicting transactions (spending the same inputs). The receiver may learn that a package info was malformed after downloading the transactions.
 301 | +
 302 | +# A node MUST NOT send a "ancpkginfo" message that has not been requested by the recipient. Upon receipt of an unsolicited "ancpkginfo", a node may disconnect the sender.

---

 325 | +|txns||List of wtxids||txns_length * 32|| The wtxids of each transaction in the package.
 326 | +|}
 327 | +
 328 | +# The "getpkgtxns" message has the structure defined above, with pchCommand == "getpkgtxns".
 329 | +
 330 | +# A "getpkgtxns" message should be used to request some list of transactions specified by witness transaction id. It indicates that the node wants to receive either all the specified transactions or none of them. This message is intended to allow nodes to avoid downloading and storing transactions that cannot be validated without each other. The list of transactions does not need to correspond to a previously-received pkginfo message.

---

 327 | +
 328 | +# The "getpkgtxns" message has the structure defined above, with pchCommand == "getpkgtxns".
 329 | +
 330 | +# A "getpkgtxns" message should be used to request some list of transactions specified by witness transaction id. It indicates that the node wants to receive either all the specified transactions or none of them. This message is intended to allow nodes to avoid downloading and storing transactions that cannot be validated without each other. The list of transactions does not need to correspond to a previously-received pkginfo message.
 331 | +
 332 | +# Upon receipt of a "getpkgtxns" message, a node should respond with either a "pkgtxns" containing all of the requested transactions in the same order specified in the "getpkgtxns" request or one "notfound" message of type MSG_PKGTXNS and combined hash of all of the wtxids in the "getpkgtxns" request (only one "notfound" message and nothing else), indicating one or more of the transactions is unavailable.

---

 347 | +
 348 | +# The "pkgtxns" message has the structure defined above, with pchCommand == "pkgtxns".
 349 | +
 350 | +# A "pkgtxns" message should contain the transaction data requested using "getpkgtxns".
 351 | +
 352 | +# A "pkgtxns" message should only be sent to a peer that requested the package using "getpkgtxns". If a node receives an unsolicited package, it may choose to validate the transactions or not, and the sender may be disconnected.

---

 357 | +
 358 | +# A new inv type (MSG_PKGTXNS == 0x6) is added, for use only in "notfound" messages pertaining to package transactions.
 359 | +
 360 | +# As a notfound type, it indicates that the sender is unable to send all the transactions requested in a prior "getpkgtxns" message. The hash used is equal to the combined hash (defined above) of the wtxids in the getpkgtxns request.
 361 | +
 362 | +# This inv type should only be used in "notfound" messages, i.e. "inv(MSG_PKGTXNS)" and "getdata(MSG_PKGTXNS)" must never be sent.

---

 329 | +
 330 | +# A "getpkgtxns" message should be used to request some list of transactions specified by witness transaction id. It indicates that the node wants to receive either all the specified transactions or none of them. This message is intended to allow nodes to avoid downloading and storing transactions that cannot be validated without each other. The list of transactions does not need to correspond to a previously-received ancpkginfo message.
 331 | +
 332 | +# Upon receipt of a "getpkgtxns" message, a node should respond with either a "pkgtxns" containing all of the requested transactions in the same order specified in the "getpkgtxns" request or one "notfound" message of type MSG_PKGTXNS and combined hash of all of the wtxids in the "getpkgtxns" request (only one "notfound" message and nothing else), indicating one or more of the transactions is unavailable.
 333 | +
 334 | +# A "getpkgtxns" message must contain at most 100 wtxids. Upon receipt of a "getpkgtxns" message with more than 100 wtxids, a node may ignore the message (to avoid calculating the combined hash) and disconnect the sender.

---

  30 | +mempool with similar contents, including faster compact block relay and more accurate fee
  31 | +estimation. Additionally, users may take advantage of mempool and miner policy to bump the priority
  32 | +of their transactions by attaching high-fee descendants (Child Pays for Parent or CPFP).
  33 | +
  34 | +Only individually considering transactions for submission to the mempool creates a limitation in
  35 | +the node's ability to determine which transactions have the highest feerates, since it cannot take

---

  36 | +into account descendants until all the transactions are in the mempool. Similarly, it cannot use a
  37 | +transaction's descendants when considering which of two conflicting transactions to keep (Replace by
  38 | +Fee or RBF).
  39 | +
  40 | +When a user's transaction does not meet a mempool's minimum feerate and they cannot create a
  41 | +replacement transaction directly, their transaction will simply be rejected by this mempool. They

---

  41 | +replacement transaction directly, their transaction will simply be rejected by this mempool. They
  42 | +also cannot attach a descendant to pay for replacing a conflicting transaction; it would be rejected
  43 | +for spending inputs that do not exist.
  44 | +
  45 | +This limitation harms users' ability to fee-bump their transactions. Further, it presents a security
  46 | +issue in contracting protocols which rely on presigned, time-sensitive transactions<ref>'''Examples of time-sensitive pre-signed transactions in L2 protocols.'''

---

  67 | +overestimating fees may sidestep this issue (but only while mempool traffic is low and
  68 | +predictable), but this solution is not guaranteed to work and wastes users' money. For some attacks,
  69 | +the available defenses require nodes to have a bird's-eye view of Bitcoin nodes' mempools, which is
  70 | +an unreasonable security requirement.
  71 | +
  72 | +The best solution is to enable nodes to consider packages of transactions as a unit, e.g. one or

---

 101 | +(prevouts specify txid, not wtxid). These parents may end up being orphans as well, if they also
 102 | +spend unconfirmed inputs that the node is unaware of. This method of handling orphans is problematic
 103 | +for two reasons: it requires nodes to allocate memory for unvalidated data received on the p2p
 104 | +network and it relies on txid-based relay between two wtxid-relay peers.
 105 | +
 106 | +This proposal makes orphan-fetching more efficient and no longer require txid-based relay.

---

 307 | +
 308 | +# A new inv type (MSG_ANCPKGINFO == 0x7) is added, for use only in getdata requests pertaining to ancestor packages.
 309 | +
 310 | +# As a getdata request type, it indicates that the sender wants an "ancpkginfo" containing all of the unconfirmed ancestors of a transaction, referenced by wtxid.
 311 | +
 312 | +# Upon receipt of a "getdata(MSG_ANCPKGINFO)" request, the node should respond with an "ancpkginfo" message corresponding to the transaction's unconfirmed ancestor package, or with "notfound".  The wtxid of the requested transaction must be the last item in the list, as the last item is used to determine which transaction the "ancpkginfo" pertains to.

---

 355 | +
 356 | +====MSG_PKGTXNS====
 357 | +
 358 | +# A new inv type (MSG_PKGTXNS == 0x6) is added, for use only in "notfound" messages pertaining to package transactions.
 359 | +
 360 | +# As a notfound type, it indicates that the sender is unable to send all the transactions requested in a prior "getpkgtxns" message. The hash used is equal to the combined hash (defined above) of the wtxids in the getpkgtxns request.

---

 270 | +|}
 271 | +
 272 | +# The "ancpkginfo" message has the structure defined above, with pchCommand == "ancpkginfo".
 273 | +
 274 | +# The "txns" field should contain a list of wtxids which constitute the ancestor package of the last wtxid. For the receiver's convenience, the sender should - but is not required to - sort the wtxids in topological order. The topological sort can be achieved by sorting the transactions by mempool acceptance order (if parents are always accepted before children). Apart from the last wtxid which is used to learn which transaction the message corresponds to, there is no enforced ordering. Nodes should not disconnect or punish a peer who provides a list not sorted in topological order.<ref>'''Why not include feerate information to help the receiver decide whether these transactions are worth downloading?'''
 275 | +Peers are not trusted to provide correct information, so a reported low feerate should not stop a

---

 230 | +===Combined Hash===
 231 | +
 232 | +A "combined hash" serves as a unique "package id" for some list of transactions and helps provide a
 233 | +meaningful but short "notfound" response to "getpkgtxns."
 234 | +
 235 | +The combined hash of a package of transactions is equal to the double-sha256 hash of each transaction's

---

 348 | +
 349 | +# A "pkgtxns" message should contain the transaction data requested using "getpkgtxns".
 350 | +
 351 | +# A "pkgtxns" message should only be sent to a peer that requested the package using "getpkgtxns". If a node receives an unsolicited package, it may choose to validate the transactions or not, and the sender may be disconnected.
 352 | +
 353 | +# This message must only be used if both peers both set <code>PKG_RELAY_PKGTXNS</code> in their "sendpackages" message. If a "getpkgtxns" message is received from a peer with which this type of package relay was not negotiated, no response should be sent and the sender may be disconnected.

---

 352 | +
 353 | +# This message must only be used if both peers both set <code>PKG_RELAY_PKGTXNS</code> in their "sendpackages" message. If a "getpkgtxns" message is received from a peer with which this type of package relay was not negotiated, no response should be sent and the sender may be disconnected.
 354 | +
 355 | +====MSG_PKGTXNS====
 356 | +
 357 | +# A new inv type (MSG_PKGTXNS == 0x6) is added, for use only in "notfound" messages pertaining to package transactions.

---

 298 | +
 299 | +# Upon receipt of a malformed "ancpkginfo" message, the sender may be disconnected. An "ancpkginfo" message is malformed if it contains duplicate wtxids or conflicting transactions (spending the same inputs). The receiver may learn that a package info was malformed after downloading the transactions.
 300 | +
 301 | +# A node MUST NOT send a "ancpkginfo" message that has not been requested by the recipient. Upon receipt of an unsolicited "ancpkginfo", a node may disconnect the sender.
 302 | +
 303 | +# This message must only be used if both peers both set <code>PKG_RELAY_ANC</code> in their "sendpackages" message. If an "ancpkginfo" message is received from a peer with which this type of package relay was not negotiated, no response should be sent and the sender may be disconnected.

---