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.