Return-Path: Received: from smtp4.osuosl.org (smtp4.osuosl.org [IPv6:2605:bc80:3010::137]) by lists.linuxfoundation.org (Postfix) with ESMTP id EF8D0C000D for ; Wed, 22 Sep 2021 13:26:30 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp4.osuosl.org (Postfix) with ESMTP id C398B40763 for ; Wed, 22 Sep 2021 13:26:30 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org X-Spam-Flag: NO X-Spam-Score: -2.098 X-Spam-Level: X-Spam-Status: No, score=-2.098 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no Authentication-Results: smtp4.osuosl.org (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com Received: from smtp4.osuosl.org ([127.0.0.1]) by localhost (smtp4.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id FQ06Z-9hwWOU for ; Wed, 22 Sep 2021 13:26:27 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.8.0 Received: from mail-qk1-x734.google.com (mail-qk1-x734.google.com [IPv6:2607:f8b0:4864:20::734]) by smtp4.osuosl.org (Postfix) with ESMTPS id 5439640715 for ; Wed, 22 Sep 2021 13:26:26 +0000 (UTC) Received: by mail-qk1-x734.google.com with SMTP id f130so9520057qke.6 for ; Wed, 22 Sep 2021 06:26:26 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=NpSBGYvWx50/AqLw68YamhXa5fkms5n8drNGSh7o89M=; b=HKVqSHmKxh3GYNqJNWHkTV/bJo94+osw2sI+X3vi2muqy7h76F0pPNW66jYs/7GDKU eZ/w1EMgEnor5w03DYpl1qROUJoi05Tmyr5Th7jtb1x4exCGUX71mc25WrE+RPMUGTjX LwTyYTpZlYs/e8VEUCGoq5+UEyzeXY5XpojFuwHmDderLnDM1EaVQomjJFDoGhJ4fjoM UXYI4UjIwhoZjNJQW0AdiRW/lVXBlCOQ/8zCP3dnBpBLO3mNuQXpuA2TMwHB0rsa11dT 8ecp7AFZOI1ernnwwweRtM1LBzn0ZeWutl1uF5JlsUGZQ3SU9faxy38Q9+wVRFRw7uUP aSKA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=NpSBGYvWx50/AqLw68YamhXa5fkms5n8drNGSh7o89M=; b=adcwL5kXIosVIPIALoNI506yymyFxHDCSS/w1+cQCsaDnA44/PGxBgl14zZIVKjV40 +dDrXXZRPyXUNyNCbYtMSIPily6jOqjgkqQAHr4grMCC/LjoV6BMoIwbXSfpqnR15toj SdZr3zH7QU5zmwdn6GQYNOXrI0+UccxPo4pSVCdKarro/kejGSmXi7sY1vdA8wU2GtMb aeKrsdi+cdqju16RByT2g45maYqoGhTpyjp7jTfqvb9C1TxcH4OeO6YoUy5MoNJVuxVI 28sBEKRCBE0SakTie0B8GDw0RVXHrGLolZywSMJDSDTSMxkUNfnjltYMfb9smjfSlmW0 ii8Q== X-Gm-Message-State: AOAM533YgpHXoSZgsCvvKWcXNcg3SeEnQdJB+LBQkvFQgXQ645IVL77v LZPCW58ZOLcBZkSA4Nur6FLpJUGMzmkXQj2PL3JNZNx/T1NsHw== X-Google-Smtp-Source: ABdhPJybp6HrcNJjBH8U6AkoMQPmZvqQUjNWGQ9TxdxRqlHc3QSAvo2lDj4+mk0q7wtUkjH3zVEGVBxJ/a6iYT3f/EU= X-Received: by 2002:a25:bc0e:: with SMTP id i14mr42482004ybh.324.1632317185622; Wed, 22 Sep 2021 06:26:25 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Gloria Zhao Date: Wed, 22 Sep 2021 14:26:14 +0100 Message-ID: To: Bastien TEINTURIER Content-Type: multipart/alternative; boundary="00000000000002858905cc9576a9" X-Mailman-Approved-At: Wed, 22 Sep 2021 14:00:28 +0000 Cc: Bitcoin Protocol Discussion Subject: Re: [bitcoin-dev] Proposal: Package Mempool Accept and Package RBF X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 22 Sep 2021 13:26:31 -0000 --00000000000002858905cc9576a9 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi Bastien, > A package A + C will be able to replace A' + B regardless of > the weight of A' + B? Correct, the weight of A' + B will not prevent A+C from replacing it (as long as A+C pays enough fees). In example 2C, we would be able to replace A with a package. Best, Gloria On Wed, Sep 22, 2021 at 8:10 AM Bastien TEINTURIER wrote= : > Great, thanks for this clarification! > > Can you confirm that this won't be an issue either with your > example 2C (in your first set of diagrams)? If I understand it > correctly it shouldn't, but I'd rather be 100% sure. > > A package A + C will be able to replace A' + B regardless of > the weight of A' + B? > > Thanks, > Bastien > > Le mar. 21 sept. 2021 =C3=A0 18:42, Gloria Zhao a > =C3=A9crit : > >> Hi Bastien, >> >> Excellent diagram :D >> >> > Here the issue is that a revoked commitment tx A' is pinned in other >> > mempools, with a long chain of descendants (or descendants that reach >> > the maximum replaceable size). >> > We would really like A + C to be able to replace this pinned A'. >> > We can't submit individually because A on its own won't replace A'... >> >> Right, this is a key motivation for having Package RBF. In this case, A+= C >> can replace A' + B1...B24. >> >> Due to the descendant limit (each node operator can increase it on their >> own node, but the default is 25), A' should have no more than 25 >> descendants, even including CPFP carve out. As long as A only conflicts >> with A', it won't be trying to replace more than 100 transactions. The >> proposed package RBF will allow C to pay for A's conflicts, since their >> package feerate is used in the fee comparisons. A is not a descendant of >> A', so the existence of B1...B24 does not prevent the replacement. >> >> Best, >> Gloria >> >> On Tue, Sep 21, 2021 at 4:18 PM Bastien TEINTURIER >> wrote: >> >>> Hi Gloria, >>> >>> > I believe this attack is mitigated as long as we attempt to submit >>> transactions individually >>> >>> Unfortunately not, as there exists a pinning scenario in LN where a >>> different commit tx is pinned, but you actually can't know which one. >>> >>> Since I really like your diagrams, I made one as well to illustrate: >>> >>> https://user-images.githubusercontent.com/31281497/134198114-5e9c6857-e= 8fc-405a-be57-18181d5e54cb.jpg >>> >>> Here the issue is that a revoked commitment tx A' is pinned in other >>> mempools, with a long chain of descendants (or descendants that reach >>> the maximum replaceable size). >>> >>> We would really like A + C to be able to replace this pinned A'. >>> We can't submit individually because A on its own won't replace A'... >>> >>> > I would note that this proposal doesn't accommodate something like >>> diagram B, where C is getting CPFP carve out and wants to bring a +1 >>> >>> No worries, that case shouldn't be a concern. >>> I believe any L2 protocol can always ensure it confirms such tx trees >>> "one depth after the other" without impacting funds safety, so it >>> only needs to ensure A + C can get into mempools. >>> >>> Thanks, >>> Bastien >>> >>> Le mar. 21 sept. 2021 =C3=A0 13:18, Gloria Zhao = a >>> =C3=A9crit : >>> >>>> Hi Bastien, >>>> >>>> Thank you for your feedback! >>>> >>>> > In your example we have a parent transaction A already in the mempoo= l >>>> > and an unrelated child B. We submit a package C + D where C spends >>>> > another of A's inputs. You're highlighting that this package may be >>>> > rejected because of the unrelated transaction(s) B. >>>> >>>> > The way I see this, an attacker can abuse this rule to ensure >>>> > transaction A stays pinned in the mempool without confirming by >>>> > broadcasting a set of child transactions that reach these limits >>>> > and pay low fees (where A would be a commit tx in LN). >>>> >>>> I believe you are describing a pinning attack in which your adversaria= l >>>> counterparty attempts to monopolize the mempool descendant limit of th= e >>>> shared transaction A in order to prevent you from submitting a fee-bu= mping >>>> child C; I've tried to illustrate this as diagram A here: >>>> https://user-images.githubusercontent.com/25183001/134159860-068080d0-= bbb6-4356-ae74-00df00644c74.png >>>> (please let me know if I'm misunderstanding). >>>> >>>> I believe this attack is mitigated as long as we attempt to submit >>>> transactions individually (and thus take advantage of CPFP carve out) >>>> before attempting package validation. So, in scenario A2, even if the >>>> mempool receives a package with A+C, it would deduplicate A, submit C = as an >>>> individual transaction, and allow it due to the CPFP carve out exempti= on. A >>>> more general goal is: if a transaction would propagate successfully on= its >>>> own now, it should still propagate regardless of whether it is include= d in >>>> a package. The best way to ensure this, as far as I can tell, is to al= ways >>>> try to submit them individually first. >>>> >>>> I would note that this proposal doesn't accommodate something like >>>> diagram B, where C is getting CPFP carve out and wants to bring a +1 (= e.g. >>>> C has very low fees and is bumped by D). I don't think this is a use c= ase >>>> since C should be the one fee-bumping A, but since we're talking about >>>> limitations around the CPFP carve out, this is it. >>>> >>>> Let me know if this addresses your concerns? >>>> >>>> Thanks, >>>> Gloria >>>> >>>> On Mon, Sep 20, 2021 at 10:19 AM Bastien TEINTURIER >>>> wrote: >>>> >>>>> Hi Gloria, >>>>> >>>>> Thanks for this detailed post! >>>>> >>>>> The illustrations you provided are very useful for this kind of graph >>>>> topology problems. >>>>> >>>>> The rules you lay out for package RBF look good to me at first glance >>>>> as there are some subtle improvements compared to BIP 125. >>>>> >>>>> > 1. A package cannot exceed `MAX_PACKAGE_COUNT=3D25` count and >>>>> > `MAX_PACKAGE_SIZE=3D101KvB` total size [8] >>>>> >>>>> I have a question regarding this rule, as your example 2C could be >>>>> concerning for LN (unless I didn't understand it correctly). >>>>> >>>>> This also touches on the package RBF rule 5 ("The package cannot >>>>> replace more than 100 mempool transactions.") >>>>> >>>>> In your example we have a parent transaction A already in the mempool >>>>> and an unrelated child B. We submit a package C + D where C spends >>>>> another of A's inputs. You're highlighting that this package may be >>>>> rejected because of the unrelated transaction(s) B. >>>>> >>>>> The way I see this, an attacker can abuse this rule to ensure >>>>> transaction A stays pinned in the mempool without confirming by >>>>> broadcasting a set of child transactions that reach these limits >>>>> and pay low fees (where A would be a commit tx in LN). >>>>> >>>>> We had to create the CPFP carve-out rule explicitly to work around >>>>> this limitation, and I think it would be necessary for package RBF >>>>> as well, because in such cases we do want to be able to submit a >>>>> package A + C where C pays high fees to speed up A's confirmation, >>>>> regardless of unrelated unconfirmed children of A... >>>>> >>>>> We could submit only C to benefit from the existing CPFP carve-out >>>>> rule, but that wouldn't work if our local mempool doesn't have A yet, >>>>> but other remote mempools do. >>>>> >>>>> Is my concern justified? Is this something that we should dig into a >>>>> bit deeper? >>>>> >>>>> Thanks, >>>>> Bastien >>>>> >>>>> Le jeu. 16 sept. 2021 =C3=A0 09:55, Gloria Zhao via bitcoin-dev < >>>>> bitcoin-dev@lists.linuxfoundation.org> a =C3=A9crit : >>>>> >>>>>> Hi there, >>>>>> >>>>>> I'm writing to propose a set of mempool policy changes to enable >>>>>> package >>>>>> validation (in preparation for package relay) in Bitcoin Core. These >>>>>> would not >>>>>> be consensus or P2P protocol changes. However, since mempool policy >>>>>> significantly affects transaction propagation, I believe this is >>>>>> relevant for >>>>>> the mailing list. >>>>>> >>>>>> My proposal enables packages consisting of multiple parents and 1 >>>>>> child. If you >>>>>> develop software that relies on specific transaction relay >>>>>> assumptions and/or >>>>>> are interested in using package relay in the future, I'm very >>>>>> interested to hear >>>>>> your feedback on the utility or restrictiveness of these package >>>>>> policies for >>>>>> your use cases. >>>>>> >>>>>> A draft implementation of this proposal can be found in [Bitcoin Cor= e >>>>>> PR#22290][1]. >>>>>> >>>>>> An illustrated version of this post can be found at >>>>>> https://gist.github.com/glozow/dc4e9d5c5b14ade7cdfac40f43adb18a. >>>>>> I have also linked the images below. >>>>>> >>>>>> ## Background >>>>>> >>>>>> Feel free to skip this section if you are already familiar with >>>>>> mempool policy >>>>>> and package relay terminology. >>>>>> >>>>>> ### Terminology Clarifications >>>>>> >>>>>> * Package =3D an ordered list of related transactions, representable= by >>>>>> a Directed >>>>>> Acyclic Graph. >>>>>> * Package Feerate =3D the total modified fees divided by the total >>>>>> virtual size of >>>>>> all transactions in the package. >>>>>> - Modified fees =3D a transaction's base fees + fee delta applie= d >>>>>> by the user >>>>>> with `prioritisetransaction`. As such, we expect this to vary >>>>>> across >>>>>> mempools. >>>>>> - Virtual Size =3D the maximum of virtual sizes calculated using >>>>>> [BIP141 >>>>>> virtual size][2] and sigop weight. [Implemented here in Bitcoi= n >>>>>> Core][3]. >>>>>> - Note that feerate is not necessarily based on the base fees an= d >>>>>> serialized >>>>>> size. >>>>>> >>>>>> * Fee-Bumping =3D user/wallet actions that take advantage of miner >>>>>> incentives to >>>>>> boost a transaction's candidacy for inclusion in a block, includin= g >>>>>> Child Pays >>>>>> for Parent (CPFP) and [BIP125][12] Replace-by-Fee (RBF). Our >>>>>> intention in >>>>>> mempool policy is to recognize when the new transaction is more >>>>>> economical to >>>>>> mine than the original one(s) but not open DoS vectors, so there are >>>>>> some >>>>>> limitations. >>>>>> >>>>>> ### Policy >>>>>> >>>>>> The purpose of the mempool is to store the best (to be most >>>>>> incentive-compatible >>>>>> with miners, highest feerate) candidates for inclusion in a block. >>>>>> Miners use >>>>>> the mempool to build block templates. The mempool is also useful as = a >>>>>> cache for >>>>>> boosting block relay and validation performance, aiding transaction >>>>>> relay, and >>>>>> generating feerate estimations. >>>>>> >>>>>> Ideally, all consensus-valid transactions paying reasonable fees >>>>>> should make it >>>>>> to miners through normal transaction relay, without any special >>>>>> connectivity or >>>>>> relationships with miners. On the other hand, nodes do not have >>>>>> unlimited >>>>>> resources, and a P2P network designed to let any honest node >>>>>> broadcast their >>>>>> transactions also exposes the transaction validation engine to DoS >>>>>> attacks from >>>>>> malicious peers. >>>>>> >>>>>> As such, for unconfirmed transactions we are considering for our >>>>>> mempool, we >>>>>> apply a set of validation rules in addition to consensus, primarily >>>>>> to protect >>>>>> us from resource exhaustion and aid our efforts to keep the highest >>>>>> fee >>>>>> transactions. We call this mempool _policy_: a set of (configurable, >>>>>> node-specific) rules that transactions must abide by in order to be >>>>>> accepted >>>>>> into our mempool. Transaction "Standardness" rules and mempool >>>>>> restrictions such >>>>>> as "too-long-mempool-chain" are both examples of policy. >>>>>> >>>>>> ### Package Relay and Package Mempool Accept >>>>>> >>>>>> In transaction relay, we currently consider transactions one at a >>>>>> time for >>>>>> submission to the mempool. This creates a limitation in the node's >>>>>> ability to >>>>>> determine which transactions have the highest feerates, since we >>>>>> cannot take >>>>>> into account descendants (i.e. cannot use CPFP) until all the >>>>>> transactions are >>>>>> in the mempool. Similarly, we cannot use a transaction's descendants >>>>>> when >>>>>> considering it for RBF. When an individual transaction does not meet >>>>>> the mempool >>>>>> minimum feerate and the user isn't able to create a replacement >>>>>> transaction >>>>>> directly, it will not be accepted by mempools. >>>>>> >>>>>> This limitation presents a security issue for applications and users >>>>>> relying on >>>>>> time-sensitive transactions. For example, Lightning and other >>>>>> protocols create >>>>>> UTXOs with multiple spending paths, where one counterparty's spendin= g >>>>>> path opens >>>>>> up after a timelock, and users are protected from cheating scenarios >>>>>> as long as >>>>>> they redeem on-chain in time. A key security assumption is that all >>>>>> parties' >>>>>> transactions will propagate and confirm in a timely manner. This >>>>>> assumption can >>>>>> be broken if fee-bumping does not work as intended. >>>>>> >>>>>> The end goal for Package Relay is to consider multiple transactions >>>>>> at the same >>>>>> time, e.g. a transaction with its high-fee child. This may help us >>>>>> better >>>>>> determine whether transactions should be accepted to our mempool, >>>>>> especially if >>>>>> they don't meet fee requirements individually or are better RBF >>>>>> candidates as a >>>>>> package. A combination of changes to mempool validation logic, >>>>>> policy, and >>>>>> transaction relay allows us to better propagate the transactions wit= h >>>>>> the >>>>>> highest package feerates to miners, and makes fee-bumping tools more >>>>>> powerful >>>>>> for users. >>>>>> >>>>>> The "relay" part of Package Relay suggests P2P messaging changes, bu= t >>>>>> a large >>>>>> part of the changes are in the mempool's package validation logic. W= e >>>>>> call this >>>>>> *Package Mempool Accept*. >>>>>> >>>>>> ### Previous Work >>>>>> >>>>>> * Given that mempool validation is DoS-sensitive and complex, it >>>>>> would be >>>>>> dangerous to haphazardly tack on package validation logic. Many >>>>>> efforts have >>>>>> been made to make mempool validation less opaque (see [#16400][4], >>>>>> [#21062][5], >>>>>> [#22675][6], [#22796][7]). >>>>>> * [#20833][8] Added basic capabilities for package validation, test >>>>>> accepts only >>>>>> (no submission to mempool). >>>>>> * [#21800][9] Implemented package ancestor/descendant limit checks >>>>>> for arbitrary >>>>>> packages. Still test accepts only. >>>>>> * Previous package relay proposals (see [#16401][10], [#19621][11]). >>>>>> >>>>>> ### Existing Package Rules >>>>>> >>>>>> These are in master as introduced in [#20833][8] and [#21800][9]. >>>>>> I'll consider >>>>>> them as "given" in the rest of this document, though they can be >>>>>> changed, since >>>>>> package validation is test-accept only right now. >>>>>> >>>>>> 1. A package cannot exceed `MAX_PACKAGE_COUNT=3D25` count and >>>>>> `MAX_PACKAGE_SIZE=3D101KvB` total size [8] >>>>>> >>>>>> *Rationale*: This is already enforced as mempool >>>>>> ancestor/descendant limits. >>>>>> Presumably, transactions in a package are all related, so exceeding >>>>>> this limit >>>>>> would mean that the package can either be split up or it wouldn't >>>>>> pass this >>>>>> mempool policy. >>>>>> >>>>>> 2. Packages must be topologically sorted: if any dependencies exist >>>>>> between >>>>>> transactions, parents must appear somewhere before children. [8] >>>>>> >>>>>> 3. A package cannot have conflicting transactions, i.e. none of them >>>>>> can spend >>>>>> the same inputs. This also means there cannot be duplicate >>>>>> transactions. [8] >>>>>> >>>>>> 4. When packages are evaluated against ancestor/descendant limits in >>>>>> a test >>>>>> accept, the union of all of their descendants and ancestors is >>>>>> considered. This >>>>>> is essentially a "worst case" heuristic where every transaction in >>>>>> the package >>>>>> is treated as each other's ancestor and descendant. [8] >>>>>> Packages for which ancestor/descendant limits are accurately capture= d >>>>>> by this >>>>>> heuristic: [19] >>>>>> >>>>>> There are also limitations such as the fact that CPFP carve out is >>>>>> not applied >>>>>> to package transactions. #20833 also disables RBF in package >>>>>> validation; this >>>>>> proposal overrides that to allow packages to use RBF. >>>>>> >>>>>> ## Proposed Changes >>>>>> >>>>>> The next step in the Package Mempool Accept project is to implement >>>>>> submission >>>>>> to mempool, initially through RPC only. This allows us to test the >>>>>> submission >>>>>> logic before exposing it on P2P. >>>>>> >>>>>> ### Summary >>>>>> >>>>>> - Packages may contain already-in-mempool transactions. >>>>>> - Packages are 2 generations, Multi-Parent-1-Child. >>>>>> - Fee-related checks use the package feerate. This means that wallet= s >>>>>> can >>>>>> create a package that utilizes CPFP. >>>>>> - Parents are allowed to RBF mempool transactions with a set of rule= s >>>>>> similar >>>>>> to BIP125. This enables a combination of CPFP and RBF, where a >>>>>> transaction's descendant fees pay for replacing mempool conflicts. >>>>>> >>>>>> There is a draft implementation in [#22290][1]. It is WIP, but >>>>>> feedback is >>>>>> always welcome. >>>>>> >>>>>> ### Details >>>>>> >>>>>> #### Packages May Contain Already-in-Mempool Transactions >>>>>> >>>>>> A package may contain transactions that are already in the mempool. >>>>>> We remove >>>>>> ("deduplicate") those transactions from the package for the purposes >>>>>> of package >>>>>> mempool acceptance. If a package is empty after deduplication, we do >>>>>> nothing. >>>>>> >>>>>> *Rationale*: Mempools vary across the network. It's possible for a >>>>>> parent to be >>>>>> accepted to the mempool of a peer on its own due to differences in >>>>>> policy and >>>>>> fee market fluctuations. We should not reject or penalize the entire >>>>>> package for >>>>>> an individual transaction as that could be a censorship vector. >>>>>> >>>>>> #### Packages Are Multi-Parent-1-Child >>>>>> >>>>>> Only packages of a specific topology are permitted. Namely, a packag= e >>>>>> is exactly >>>>>> 1 child with all of its unconfirmed parents. After deduplication, th= e >>>>>> package >>>>>> may be exactly the same, empty, 1 child, 1 child with just some of i= ts >>>>>> unconfirmed parents, etc. Note that it's possible for the parents to >>>>>> be indirect >>>>>> descendants/ancestors of one another, or for parent and child to >>>>>> share a parent, >>>>>> so we cannot make any other topology assumptions. >>>>>> >>>>>> *Rationale*: This allows for fee-bumping by CPFP. Allowing multiple >>>>>> parents >>>>>> makes it possible to fee-bump a batch of transactions. Restricting >>>>>> packages to a >>>>>> defined topology is also easier to reason about and simplifies the >>>>>> validation >>>>>> logic greatly. Multi-parent-1-child allows us to think of the packag= e >>>>>> as one big >>>>>> transaction, where: >>>>>> >>>>>> - Inputs =3D all the inputs of parents + inputs of the child that co= me >>>>>> from >>>>>> confirmed UTXOs >>>>>> - Outputs =3D all the outputs of the child + all outputs of the pare= nts >>>>>> that >>>>>> aren't spent by other transactions in the package >>>>>> >>>>>> Examples of packages that follow this rule (variations of example A >>>>>> show some >>>>>> possibilities after deduplication): ![image][15] >>>>>> >>>>>> #### Fee-Related Checks Use Package Feerate >>>>>> >>>>>> Package Feerate =3D the total modified fees divided by the total >>>>>> virtual size of >>>>>> all transactions in the package. >>>>>> >>>>>> To meet the two feerate requirements of a mempool, i.e., the >>>>>> pre-configured >>>>>> minimum relay feerate (`minRelayTxFee`) and dynamic mempool minimum >>>>>> feerate, the >>>>>> total package feerate is used instead of the individual feerate. The >>>>>> individual >>>>>> transactions are allowed to be below feerate requirements if the >>>>>> package meets >>>>>> the feerate requirements. For example, the parent(s) in the package >>>>>> can have 0 >>>>>> fees but be paid for by the child. >>>>>> >>>>>> *Rationale*: This can be thought of as "CPFP within a package," >>>>>> solving the >>>>>> issue of a parent not meeting minimum fees on its own. This allows L= 2 >>>>>> applications to adjust their fees at broadcast time instead of >>>>>> overshooting or >>>>>> risking getting stuck/pinned. >>>>>> >>>>>> We use the package feerate of the package *after deduplication*. >>>>>> >>>>>> *Rationale*: It would be incorrect to use the fees of transactions >>>>>> that are >>>>>> already in the mempool, as we do not want a transaction's fees to be >>>>>> double-counted for both its individual RBF and package RBF. >>>>>> >>>>>> Examples F and G [14] show the same package, but P1 is submitted >>>>>> individually before >>>>>> the package in example G. In example F, we can see that the 300vB >>>>>> package pays >>>>>> an additional 200sat in fees, which is not enough to pay for its own >>>>>> bandwidth >>>>>> (BIP125#4). In example G, we can see that P1 pays enough to replace >>>>>> M1, but >>>>>> using P1's fees again during package submission would make it look >>>>>> like a 300sat >>>>>> increase for a 200vB package. Even including its fees and size would >>>>>> not be >>>>>> sufficient in this example, since the 300sat looks like enough for >>>>>> the 300vB >>>>>> package. The calculcation after deduplication is 100sat increase for >>>>>> a package >>>>>> of size 200vB, which correctly fails BIP125#4. Assume all >>>>>> transactions have a >>>>>> size of 100vB. >>>>>> >>>>>> #### Package RBF >>>>>> >>>>>> If a package meets feerate requirements as a package, the parents in >>>>>> the >>>>>> transaction are allowed to replace-by-fee mempool transactions. The >>>>>> child cannot >>>>>> replace mempool transactions. Multiple transactions can replace the >>>>>> same >>>>>> transaction, but in order to be valid, none of the transactions can >>>>>> try to >>>>>> replace an ancestor of another transaction in the same package (whic= h >>>>>> would thus >>>>>> make its inputs unavailable). >>>>>> >>>>>> *Rationale*: Even if we are using package feerate, a package will no= t >>>>>> propagate >>>>>> as intended if RBF still requires each individual transaction to mee= t >>>>>> the >>>>>> feerate requirements. >>>>>> >>>>>> We use a set of rules slightly modified from BIP125 as follows: >>>>>> >>>>>> ##### Signaling (Rule #1) >>>>>> >>>>>> All mempool transactions to be replaced must signal replaceability. >>>>>> >>>>>> *Rationale*: Package RBF signaling logic should be the same for >>>>>> package RBF and >>>>>> single transaction acceptance. This would be updated if single >>>>>> transaction >>>>>> validation moves to full RBF. >>>>>> >>>>>> ##### New Unconfirmed Inputs (Rule #2) >>>>>> >>>>>> A package may include new unconfirmed inputs, but the ancestor >>>>>> feerate of the >>>>>> child must be at least as high as the ancestor feerates of every >>>>>> transaction >>>>>> being replaced. This is contrary to BIP125#2, which states "The >>>>>> replacement >>>>>> transaction may only include an unconfirmed input if that input was >>>>>> included in >>>>>> one of the original transactions. (An unconfirmed input spends an >>>>>> output from a >>>>>> currently-unconfirmed transaction.)" >>>>>> >>>>>> *Rationale*: The purpose of BIP125#2 is to ensure that the replaceme= nt >>>>>> transaction has a higher ancestor score than the original >>>>>> transaction(s) (see >>>>>> [comment][13]). Example H [16] shows how adding a new unconfirmed >>>>>> input can lower the >>>>>> ancestor score of the replacement transaction. P1 is trying to >>>>>> replace M1, and >>>>>> spends an unconfirmed output of M2. P1 pays 800sat, M1 pays 600sat, >>>>>> and M2 pays >>>>>> 100sat. Assume all transactions have a size of 100vB. While, in >>>>>> isolation, P1 >>>>>> looks like a better mining candidate than M1, it must be mined with >>>>>> M2, so its >>>>>> ancestor feerate is actually 4.5sat/vB. This is lower than M1's >>>>>> ancestor >>>>>> feerate, which is 6sat/vB. >>>>>> >>>>>> In package RBF, the rule analogous to BIP125#2 would be "none of the >>>>>> transactions in the package can spend new unconfirmed inputs." >>>>>> Example J [17] shows >>>>>> why, if any of the package transactions have ancestors, package >>>>>> feerate is no >>>>>> longer accurate. Even though M2 and M3 are not ancestors of P1 (whic= h >>>>>> is the >>>>>> replacement transaction in an RBF), we're actually interested in the >>>>>> entire >>>>>> package. A miner should mine M1 which is 5sat/vB instead of M2, M3, >>>>>> P1, P2, and >>>>>> P3, which is only 4sat/vB. The Package RBF rule cannot be loosened t= o >>>>>> only allow >>>>>> the child to have new unconfirmed inputs, either, because it can >>>>>> still cause us >>>>>> to overestimate the package's ancestor score. >>>>>> >>>>>> However, enforcing a rule analogous to BIP125#2 would not only make >>>>>> Package RBF >>>>>> less useful, but would also break Package RBF for packages with >>>>>> parents already >>>>>> in the mempool: if a package parent has already been submitted, it >>>>>> would look >>>>>> like the child is spending a "new" unconfirmed input. In example K >>>>>> [18], we're >>>>>> looking to replace M1 with the entire package including P1, P2, and >>>>>> P3. We must >>>>>> consider the case where one of the parents is already in the mempool >>>>>> (in this >>>>>> case, P2), which means we must allow P3 to have new unconfirmed >>>>>> inputs. However, >>>>>> M2 lowers the ancestor score of P3 to 4.3sat/vB, so we should not >>>>>> replace M1 >>>>>> with this package. >>>>>> >>>>>> Thus, the package RBF rule regarding new unconfirmed inputs is less >>>>>> strict than >>>>>> BIP125#2. However, we still achieve the same goal of requiring the >>>>>> replacement >>>>>> transactions to have a ancestor score at least as high as the >>>>>> original ones. As >>>>>> a result, the entire package is required to be a higher feerate >>>>>> mining candidate >>>>>> than each of the replaced transactions. >>>>>> >>>>>> Another note: the [comment][13] above the BIP125#2 code in the >>>>>> original RBF >>>>>> implementation suggests that the rule was intended to be temporary. >>>>>> >>>>>> ##### Absolute Fee (Rule #3) >>>>>> >>>>>> The package must increase the absolute fee of the mempool, i.e. the >>>>>> total fees >>>>>> of the package must be higher than the absolute fees of the mempool >>>>>> transactions >>>>>> it replaces. Combined with the CPFP rule above, this differs from >>>>>> BIP125 Rule #3 >>>>>> - an individual transaction in the package may have lower fees than >>>>>> the >>>>>> transaction(s) it is replacing. In fact, it may have 0 fees, and >>>>>> the child >>>>>> pays for RBF. >>>>>> >>>>>> ##### Feerate (Rule #4) >>>>>> >>>>>> The package must pay for its own bandwidth; the package feerate must >>>>>> be higher >>>>>> than the replaced transactions by at least minimum relay feerate >>>>>> (`incrementalRelayFee`). Combined with the CPFP rule above, this >>>>>> differs from >>>>>> BIP125 Rule #4 - an individual transaction in the package can have a >>>>>> lower >>>>>> feerate than the transaction(s) it is replacing. In fact, it may hav= e >>>>>> 0 fees, >>>>>> and the child pays for RBF. >>>>>> >>>>>> ##### Total Number of Replaced Transactions (Rule #5) >>>>>> >>>>>> The package cannot replace more than 100 mempool transactions. This >>>>>> is identical >>>>>> to BIP125 Rule #5. >>>>>> >>>>>> ### Expected FAQs >>>>>> >>>>>> 1. Is it possible for only some of the package to make it into the >>>>>> mempool? >>>>>> >>>>>> Yes, it is. However, since we evict transactions from the mempool >>>>>> by >>>>>> descendant score and the package child is supposed to be sponsoring >>>>>> the fees of >>>>>> its parents, the most common scenario would be all-or-nothing. This = is >>>>>> incentive-compatible. In fact, to be conservative, package validatio= n >>>>>> should >>>>>> begin by trying to submit all of the transactions individually, and >>>>>> only use the >>>>>> package mempool acceptance logic if the parents fail due to low >>>>>> feerate. >>>>>> >>>>>> 2. Should we allow packages to contain already-confirmed transaction= s? >>>>>> >>>>>> No, for practical reasons. In mempool validation, we actually >>>>>> aren't able to >>>>>> tell with 100% confidence if we are looking at a transaction that ha= s >>>>>> already >>>>>> confirmed, because we look up inputs using a UTXO set. If we have >>>>>> historical >>>>>> block data, it's possible to look for it, but this is inefficient, >>>>>> not always >>>>>> possible for pruning nodes, and unnecessary because we're not going >>>>>> to do >>>>>> anything with the transaction anyway. As such, we already have the >>>>>> expectation >>>>>> that transaction relay is somewhat "stateful" i.e. nobody should be >>>>>> relaying >>>>>> transactions that have already been confirmed. Similarly, we >>>>>> shouldn't be >>>>>> relaying packages that contain already-confirmed transactions. >>>>>> >>>>>> [1]: https://github.com/bitcoin/bitcoin/pull/22290 >>>>>> [2]: >>>>>> https://github.com/bitcoin/bips/blob/1f0b563738199ca60d32b4ba779797f= c97d040fe/bip-0141.mediawiki#transaction-size-calculations >>>>>> [3]: >>>>>> https://github.com/bitcoin/bitcoin/blob/94f83534e4b771944af7d9ed0f40= 746f392eb75e/src/policy/policy.cpp#L282 >>>>>> [4]: https://github.com/bitcoin/bitcoin/pull/16400 >>>>>> [5]: https://github.com/bitcoin/bitcoin/pull/21062 >>>>>> [6]: https://github.com/bitcoin/bitcoin/pull/22675 >>>>>> [7]: https://github.com/bitcoin/bitcoin/pull/22796 >>>>>> [8]: https://github.com/bitcoin/bitcoin/pull/20833 >>>>>> [9]: https://github.com/bitcoin/bitcoin/pull/21800 >>>>>> [10]: https://github.com/bitcoin/bitcoin/pull/16401 >>>>>> [11]: https://github.com/bitcoin/bitcoin/pull/19621 >>>>>> [12]: https://github.com/bitcoin/bips/blob/master/bip-0125.mediawiki >>>>>> [13]: >>>>>> https://github.com/bitcoin/bitcoin/pull/6871/files#diff-34d21af3c614= ea3cee120df276c9c4ae95053830d7f1d3deaf009a4625409ad2R1101-R1104 >>>>>> [14]: >>>>>> https://user-images.githubusercontent.com/25183001/133567078-075a971= c-0619-4339-9168-b41fd2b90c28.png >>>>>> [15]: >>>>>> https://user-images.githubusercontent.com/25183001/132856734-fc17da7= 5-f875-44bb-b954-cb7a1725cc0d.png >>>>>> [16]: >>>>>> https://user-images.githubusercontent.com/25183001/133567347-a3e2e4a= 8-ae9c-49f8-abb9-81e8e0aba224.png >>>>>> [17]: >>>>>> https://user-images.githubusercontent.com/25183001/133567370-21566d0= e-36c8-4831-b1a8-706634540af3.png >>>>>> [18]: >>>>>> https://user-images.githubusercontent.com/25183001/133567444-bfff114= 2-439f-4547-800a-2ba2b0242bcb.png >>>>>> [19]: >>>>>> https://user-images.githubusercontent.com/25183001/133456219-0bb447c= b-dcb4-4a31-b9c1-7d86205b68bc.png >>>>>> [20]: >>>>>> https://user-images.githubusercontent.com/25183001/132857787-7b7c6f5= 6-af96-44c8-8d78-983719888c19.png >>>>>> _______________________________________________ >>>>>> bitcoin-dev mailing list >>>>>> bitcoin-dev@lists.linuxfoundation.org >>>>>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >>>>>> >>>>> --00000000000002858905cc9576a9 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi Bastien,

> A package A= =C2=A0+ C will be able to replace A'=C2=A0+ B regardless of
> th= e weight of A'=C2=A0+ B?

Correct, the we= ight of A'=C2=A0+ B will not prevent A+C from replacing it (as long as = A+C pays enough fees). In example 2C, we would be able to replace A with a = package.

Best,
Gloria

On We= d, Sep 22, 2021 at 8:10 AM Bastien TEINTURIER <bastien@acinq.fr> wrote:
Great, thanks for this clarific= ation!

Can you confirm that this won't be an issue e= ither with your
example 2C (in your first set of diagrams)? If I = understand it
correctly it shouldn't, but I'd rather be 1= 00% sure.

A package A=C2=A0+ C will be able to rep= lace A'=C2=A0+ B regardless of
the weight of A'=C2=A0+ B?=

Thanks,
Bastien

Le=C2=A0mar. 21 se= pt. 2021 =C3=A0=C2=A018:42, Gloria Zhao <gloriajzhao@gmail.com> a =C3=A9crit=C2= =A0:
Hi Bastien,

Excellent diagram :D
<= div>
> Here the issue is that a revoked commitment tx A= 9; is pinned in other
> mempools, with a long chain of descendants (o= r descendants that reach
> the maximum replaceable size).
&= gt; We would really like A + C to be able to replace this pinned A'.> We can't submit individually because A on its own won't repla= ce A'...

Right, this is a key= motivation for having Package RBF. In this case, A+C can replace A' + = B1...B24.

Due to the descendant limit (each node = operator can increase it on their own node, but the default is 25), A' = should have no more than 25 descendants, even including CPFP carve out. As = long as A only conflicts with A', it won't be trying to replace mor= e than 100 transactions. The proposed package RBF will allow C to pay for A= 's conflicts, since their package feerate is used in the fee comparison= s. A is not a descendant of A', so the existence of B1...B24 does not p= revent the replacement.

Best,
Gloria
=

On Tue, Sep 21, 2021 at 4:18 PM Bastien TEINTURIER <bastien@acinq.fr> wrote:
=
Hi= Gloria,

> I believe this attack is mitigated as long as we attem= pt to submit transactions individually

Unfortunately not, as there e= xists a pinning scenario in LN where a
different commit tx is pinned, bu= t you actually can't know which one.

Since I really like your di= agrams, I made one as well to illustrate:
https://user-images.githubusercontent.com/312814= 97/134198114-5e9c6857-e8fc-405a-be57-18181d5e54cb.jpg

Here the i= ssue is that a revoked commitment tx A' is pinned in other
mempools,= with a long chain of descendants (or descendants that reach
the maximum= replaceable size).

We would really like A + C to be able to replace= this pinned A'.
We can't submit individually because A on its o= wn won't replace A'...

> I would note that this proposal = doesn't accommodate something like diagram B, where C is getting CPFP c= arve out and wants to bring a +1

No worries, that case shouldn't= be a concern.
I believe any L2 protocol can always ensure it confirms s= uch tx trees
"one depth after the other" without impacting fun= ds safety, so it
only needs to ensure A + C can get into mempools.
Thanks,
Bastien

Le=C2=A0mar. 21 sept. 2021 =C3=A0=C2=A013:18, Gloria Zh= ao <gloriajzh= ao@gmail.com> a =C3=A9crit=C2=A0:
Hi Bastien,

Thank you for your feedback!

> In = your example we have a parent transaction A already in the mempool
> = and an unrelated child B. We submit a package C + D where C spends
> = another of A's inputs. You're highlighting that this package may be=
> rejected because of the unrelated transaction(s) B.

> Th= e way I see this, an attacker can abuse this rule to ensure
> transac= tion A stays pinned in the mempool without confirming by
> broadcasti= ng a set of child transactions that reach these limits
> and pay low = fees (where A would be a commit tx in LN).

I belie= ve you are describing a pinning attack in which your adversarial counterpar= ty attempts to monopolize the mempool descendant limit of the shared=C2=A0 = transaction A in order to prevent you from submitting a fee-bumping child C= ; I've tried to illustrate this as diagram A here: https://user-images.githubusercontent.= com/25183001/134159860-068080d0-bbb6-4356-ae74-00df00644c74.png (please= let me know if I'm misunderstanding).

I belie= ve this attack is mitigated as long as we attempt to submit transactions in= dividually (and thus take advantage of CPFP carve out) before attempting pa= ckage validation. So, in scenario A2, even if the mempool receives a packag= e with A+C, it would deduplicate A, submit C as an individual transaction, = and allow it due to the CPFP carve out exemption. A more general goal is: i= f a transaction would propagate successfully on its own now, it should stil= l propagate regardless of whether it is included in a package. The best way= to ensure this, as far as I can tell, is to always try to submit them indi= vidually first.

I would note that this proposa= l doesn't accommodate something like diagram B, where C is getting CPFP= carve out and wants to bring a=C2=A0+1 (e.g. C has very low fees and is bu= mped by D). I don't think this is a use case since C should be the one = fee-bumping A, but since we're talking about limitations around the CPF= P carve out, this is it.

Let me know if this addre= sses your concerns?

Thanks,
Gloria

On Mon, Sep 20, 2021 at 10:19 AM Bastien TEINTURIER <bastien@acinq.fr> wrote:<= br>
Hi Gloria,

Thanks for this detailed post!

The illustrations = you provided are very useful for this kind of graph
topology problems.
The rules you lay out for package RBF look good to me at first glance=
as there are some subtle improvements compared to BIP 125.

> = 1. A package cannot exceed `MAX_PACKAGE_COUNT=3D25` count and
> `MAX_= PACKAGE_SIZE=3D101KvB` total size [8]

I have a question regarding th= is rule, as your example 2C could be
concerning for LN (unless I didn= 9;t understand it correctly).

This also touches on the package RBF r= ule 5 ("The package cannot
replace more than 100 mempool transactio= ns.")

In your example we have a parent transaction A already in= the mempool
and an unrelated child B. We submit a package C + D where C= spends
another of A's inputs. You're highlighting that this pac= kage may be
rejected because of the unrelated transaction(s) B.

T= he way I see this, an attacker can abuse this rule to ensure
transaction= A stays pinned in the mempool without confirming by
broadcasting a set = of child transactions that reach these limits
and pay low fees (where A = would be a commit tx in LN).

We had to create the CPFP carve-out rul= e explicitly to work around
this limitation, and I think it would be nec= essary for package RBF
as well, because in such cases we do want to be a= ble to submit a
package A + C where C pays high fees to speed up A's= confirmation,
regardless of unrelated unconfirmed children of A...
<= br>We could submit only C to benefit from the existing CPFP carve-out
ru= le, but that wouldn't work if our local mempool doesn't have A yet,=
but other remote mempools do.

Is my concern justified? Is this s= omething that we should dig into a
bit deeper?

Thanks,
Bastien=

= Le=C2=A0jeu. 16 sept. 2021 =C3=A0=C2=A009:55, Gloria Zhao via bitcoin-dev &= lt;bitcoin-dev@lists.linuxfoundation.org> a =C3=A9crit=C2=A0:
Hi th= ere,

I'm writing to propose a set of mempool policy changes to e= nable package
validation (in preparation for package relay) in Bitcoin C= ore. These would not
be consensus or P2P protocol changes. However, sinc= e mempool policy
significantly affects transaction propagation, I believ= e this is relevant for
the mailing list.

My proposal enables pack= ages consisting of multiple parents and 1 child. If you
develop software= that relies on specific transaction relay assumptions and/or
are intere= sted in using package relay in the future, I'm very interested to hear<= br>your feedback on the utility or restrictiveness of these package policie= s for
your use cases.

A draft implementation of this proposal can= be found in [Bitcoin Core
PR#22290][1].

An illustrated version o= f this post can be found at
I have also link= ed the images below.

## Background

Feel free to skip this s= ection if you are already familiar with mempool policy
and package relay= terminology.

### Terminology Clarifications

* Package =3D an= ordered list of related transactions, representable by a Directed
=C2= =A0 Acyclic Graph.
* Package Feerate =3D the total modified fees divided= by the total virtual size of
=C2=A0 all transactions in the package.=C2=A0 =C2=A0 - Modified fees =3D a transaction's base fees + fee delt= a applied by the user
=C2=A0 =C2=A0 =C2=A0 with `prioritisetransaction`.= As such, we expect this to vary across
mempools.
=C2=A0 =C2=A0 - Vir= tual Size =3D the maximum of virtual sizes calculated using [BIP141
=C2= =A0 =C2=A0 =C2=A0 virtual size][2] and sigop weight. [Implemented here in B= itcoin Core][3].
=C2=A0 =C2=A0 - Note that feerate is not necessarily ba= sed on the base fees and serialized
=C2=A0 =C2=A0 =C2=A0 size.

* = Fee-Bumping =3D user/wallet actions that take advantage of miner incentives= to
=C2=A0 boost a transaction's candidacy for inclusion in a block,= including Child Pays
for Parent (CPFP) and [BIP125][12] Replace-by-Fee = (RBF). Our intention in
mempool policy is to recognize when the new tran= saction is more economical to
mine than the original one(s) but not open= DoS vectors, so there are some
limitations.

### Policy

Th= e purpose of the mempool is to store the best (to be most incentive-compati= ble
with miners, highest feerate) candidates for inclusion in a block. M= iners use
the mempool to build block templates. The mempool is also usef= ul as a cache for
boosting block relay and validation performance, aidin= g transaction relay, and
generating feerate estimations.

Ideally,= all consensus-valid transactions paying reasonable fees should make it
= to miners through normal transaction relay, without any special connectivit= y or
relationships with miners. On the other hand, nodes do not have unl= imited
resources, and a P2P network designed to let any honest node broa= dcast their
transactions also exposes the transaction validation engine = to DoS attacks from
malicious peers.

As such, for unconfirmed tra= nsactions we are considering for our mempool, we
apply a set of validati= on rules in addition to consensus, primarily to protect
us from resource= exhaustion and aid our efforts to keep the highest fee
transactions. We= call this mempool _policy_: a set of (configurable,
node-specific) rule= s that transactions must abide by in order to be accepted
into our mempo= ol. Transaction "Standardness" rules and mempool restrictions suc= h
as "too-long-mempool-chain" are both examples of policy.
=
### Package Relay and Package Mempool Accept

In transaction rela= y, we currently consider transactions one at a time for
submission to th= e mempool. This creates a limitation in the node's ability to
determ= ine which transactions have the highest feerates, since we cannot take
i= nto account descendants (i.e. cannot use CPFP) until all the transactions a= re
in the mempool. Similarly, we cannot use a transaction's descenda= nts when
considering it for RBF. When an individual transaction does not= meet the mempool
minimum feerate and the user isn't able to create = a replacement transaction
directly, it will not be accepted by mempools.=

This limitation presents a security issue for applications and user= s relying on
time-sensitive transactions. For example, Lightning and oth= er protocols create
UTXOs with multiple spending paths, where one counte= rparty's spending path opens
up after a timelock, and users are prot= ected from cheating scenarios as long as
they redeem on-chain in time. A= key security assumption is that all parties'
transactions will prop= agate and confirm in a timely manner. This assumption can
be broken if f= ee-bumping does not work as intended.

The end goal for Package Relay= is to consider multiple transactions at the same
time, e.g. a transacti= on with its high-fee child. This may help us better
determine whether tr= ansactions should be accepted to our mempool, especially if
they don'= ;t meet fee requirements individually or are better RBF candidates as a
= package. A combination of changes to mempool validation logic, policy, and<= br>transaction relay allows us to better propagate the transactions with th= e
highest package feerates to miners, and makes fee-bumping tools more p= owerful
for users.

The "relay" part of Package Relay su= ggests P2P messaging changes, but a large
part of the changes are in the= mempool's package validation logic. We call this
*Package Mempool A= ccept*.

### Previous Work

* Given that mempool validation is = DoS-sensitive and complex, it would be
=C2=A0 dangerous to haphazardly t= ack on package validation logic. Many efforts have
been made to make mem= pool validation less opaque (see [#16400][4], [#21062][5],
[#22675][6], = [#22796][7]).
* [#20833][8] Added basic capabilities for package validat= ion, test accepts only
=C2=A0 (no submission to mempool).
* [#21800][= 9] Implemented package ancestor/descendant limit checks for arbitrary
= =C2=A0 packages. Still test accepts only.
* Previous package relay propo= sals (see [#16401][10], [#19621][11]).

### Existing Package Rules
These are in master as introduced in [#20833][8] and [#21800][9]. I= 9;ll consider
them as "given" in the rest of this document, th= ough they can be changed, since
package validation is test-accept only r= ight now.

1. A package cannot exceed `MAX_PACKAGE_COUNT=3D25` count = and
`MAX_PACKAGE_SIZE=3D101KvB` total size [8]

=C2=A0 =C2=A0*Rati= onale*: This is already enforced as mempool ancestor/descendant limits.
= Presumably, transactions in a package are all related, so exceeding this li= mit
would mean that the package can either be split up or it wouldn'= t pass this
mempool policy.

2. Packages must be topologically sor= ted: if any dependencies exist between
transactions, parents must appear= somewhere before children. [8]

3. A package cannot have conflicting= transactions, i.e. none of them can spend
the same inputs. This al= so means there cannot be duplicate transactions. [8]

4.= When packages are evaluated against ancestor/descendant limits in a testaccept, the union of all of their descendants and ancestors is considered= . This
is essentially a "worst case" heuristic where every tra= nsaction in the package
is treated as each other's ancestor and desc= endant. [8]
Packages for which ancestor/descendant limits are accuratel= y captured by this
heuristic: [19]

There are also limitati= ons such as the fact that CPFP carve out is not applied
to package trans= actions. #20833 also disables RBF in package validation; this
proposal o= verrides that to allow packages to use RBF.

## Proposed Changes
<= br>The next step in the Package Mempool Accept project is to implement subm= ission
to mempool, initially through RPC only. This allows us to test th= e submission
logic before exposing it on P2P.

### Summary

= - Packages may contain already-in-mempool transactions.
- Packages are 2= generations, Multi-Parent-1-Child.
- Fee-related checks use the package= feerate. This means that wallets can
create a package that utilizes CPF= P.
- Parents are allowed to RBF mempool transactions with a set of rules= similar
=C2=A0 to BIP125. This enables a combination of CPFP and RBF, w= here a
transaction's descendant fees pay for replacing mempool confl= icts.

There is a draft implementation in [#22290][1]. It is WIP, but= feedback is
always welcome.

### Details

#### Packages May= Contain Already-in-Mempool Transactions

A package may contain trans= actions that are already in the mempool. We remove
("deduplicate&qu= ot;) those transactions from the package for the purposes of package
mem= pool acceptance. If a package is empty after deduplication, we do nothing.<= br>
*Rationale*: Mempools vary across the network. It's possible for= a parent to be
accepted to the mempool of a peer on its own due to diff= erences in policy and
fee market fluctuations. We should not reject or p= enalize the entire package for
an individual transaction as that could b= e a censorship vector.

#### Packages Are Multi-Parent-1-Child
Only packages of a specific topology are permitted. Namely, a package is e= xactly
1 child with all of its unconfirmed parents. After deduplication,= the package
may be exactly the same, empty, 1 child, 1 child with just = some of its
unconfirmed parents, etc. Note that it's possible for th= e parents to be indirect
descendants/ancestors of one another, or for pa= rent and child to share a parent,
so we cannot make any other topology a= ssumptions.

*Rationale*: This allows for fee-bumping by CPFP. Allowi= ng multiple parents
makes it possible to fee-bump a batch of transaction= s. Restricting packages to a
defined topology is also easier to reason a= bout and simplifies the validation
logic greatly. Multi-parent-1-child a= llows us to think of the package as one big
transaction, where:

-= Inputs =3D all the inputs of parents + inputs of the child that come from<= br>=C2=A0 confirmed UTXOs
- Outputs =3D all the outputs of the child + a= ll outputs of the parents that
=C2=A0 aren't spent by other transact= ions in the package

Examples of packages that follow this rule (vari= ations of example A show some
possibilities after deduplication): ![imag= e][15]

#### Fee-Related Checks Use Package Feerate

Package Fe= erate =3D the total modified fees divided by the total virtual size of
a= ll transactions in the package.

To meet the two feerate requirements= of a mempool, i.e., the pre-configured
minimum relay feerate (`minRelay= TxFee`) and dynamic mempool minimum feerate, the
total package feerate i= s used instead of the individual feerate. The individual
transactions ar= e allowed to be below feerate requirements if the package meets
the feer= ate requirements. For example, the parent(s) in the package can have 0
f= ees but be paid for by the child.

*Rationale*: This can be thought o= f as "CPFP within a package," solving the
issue of a parent no= t meeting minimum fees on its own. This allows L2
applications to adjust= their fees at broadcast time instead of overshooting or
risking getting= stuck/pinned.

We use the package feerate of the package *after dedu= plication*.

*Rationale*: =C2=A0It would be incorrect to use the fees= of transactions that are
already in the mempool, as we do not want a tr= ansaction's fees to be
double-counted for both its individual RBF an= d package RBF.

Examples F and G [14] show the same package, but P1 i= s submitted individually before
the package in example G. In example F, = we can see that the 300vB package pays
an additional 200sat in fees, whi= ch is not enough to pay for its own bandwidth
(BIP125#4). In example G, = we can see that P1 pays enough to replace M1, but
using P1's fees ag= ain during package submission would make it look like a 300sat
increase = for a 200vB package. Even including its fees and size would not be
suffi= cient in this example, since the 300sat looks like enough for the 300vB
= package. The calculcation after deduplication is 100sat increase for a pack= age
of size 200vB, which correctly fails BIP125#4. Assume all transactio= ns have a
size of 100vB.

#### Package RBF

If a package mee= ts feerate requirements as a package, the parents in the
transaction are= allowed to replace-by-fee mempool transactions. The child cannot
replac= e mempool transactions. Multiple transactions can replace the same
trans= action, but in order to be valid, none of the transactions can try to
re= place an ancestor of another transaction in the same package (which would t= hus
make its inputs unavailable).

*Rationale*: Even if we are usi= ng package feerate, a package will not propagate
as intended if RBF stil= l requires each individual transaction to meet the
feerate requirements.=

We use a set of rules slightly modified from BIP125 as follows:
=
##### Signaling (Rule #1)

All mempool transactions to be replace= d must signal replaceability.

*Rationale*: Package RBF signaling log= ic should be the same for package RBF and
single transaction acceptance.= This would be updated if single transaction
validation moves to full RB= F.

##### New Unconfirmed Inputs (Rule #2)

A package may inclu= de new unconfirmed inputs, but the ancestor feerate of the
child must be= at least as high as the ancestor feerates of every transaction
being re= placed. This is contrary to BIP125#2, which states "The replacementtransaction may only include an unconfirmed input if that input was includ= ed in
one of the original transactions. (An unconfirmed input spends an = output from a
currently-unconfirmed transaction.)"

*Rational= e*: The purpose of BIP125#2 is to ensure that the replacement
transactio= n has a higher ancestor score than the original transaction(s) (see
[com= ment][13]). Example H [16] shows how adding a new unconfirmed input can low= er the
ancestor score of the replacement transaction. P1 is trying to re= place M1, and
spends an unconfirmed output of M2. P1 pays 800sat, M1 pay= s 600sat, and M2 pays
100sat. Assume all transactions have a size of 100= vB. While, in isolation, P1
looks like a better mining candidate than M1= , it must be mined with M2, so its
ancestor feerate is actually 4.5sat/v= B.=C2=A0 This is lower than M1's ancestor
feerate, which is 6sat/vB.=

In package RBF, the rule analogous to BIP125#2 would be "none = of the
transactions in the package can spend new unconfirmed inputs.&quo= t; Example J [17] shows
why, if any of the package transactions have anc= estors, package feerate is no
longer accurate. Even though M2 and M3 are= not ancestors of P1 (which is the
replacement transaction in an RBF), w= e're actually interested in the entire
package. A miner should mine = M1 which is 5sat/vB instead of M2, M3, P1, P2, and
P3, which is only 4sa= t/vB. The Package RBF rule cannot be loosened to only allow
the child to= have new unconfirmed inputs, either, because it can still cause us
to o= verestimate the package's ancestor score.

However, enforcing a r= ule analogous to BIP125#2 would not only make Package RBF
less useful, b= ut would also break Package RBF for packages with parents already
in the= mempool: if a package parent has already been submitted, it would look
= like the child is spending a "new" unconfirmed input. In example = K [18], we're
looking to replace M1 with the entire package includin= g P1, P2, and P3. We must
consider the case where one of the parents is = already in the mempool (in this
case, P2), which means we must allow P3 = to have new unconfirmed inputs. However,
M2 lowers the ancestor score of= P3 to 4.3sat/vB, so we should not replace M1
with this package.

= Thus, the package RBF rule regarding new unconfirmed inputs is less strict = than
BIP125#2. However, we still achieve the same goal of requiring the = replacement
transactions to have a ancestor score at least as high as th= e original ones. As
a result, the entire package is required to be a hig= her feerate mining candidate
than each of the replaced transactions.
=
Another note: the [comment][13] above the BIP125#2 code in the original= RBF
implementation suggests that the rule was intended to be temporary.=

##### Absolute Fee (Rule #3)

The package must increase the a= bsolute fee of the mempool, i.e. the total fees
of the package must be h= igher than the absolute fees of the mempool transactions
it replaces. Co= mbined with the CPFP rule above, this differs from BIP125 Rule #3
- an i= ndividual transaction in the package may have lower fees than the
=C2=A0= transaction(s) it is replacing. In fact, it may have 0 fees, and the child=
pays for RBF.

##### Feerate (Rule #4)

The package must pa= y for its own bandwidth; the package feerate must be higher
than the rep= laced transactions by at least minimum relay feerate
(`incrementalRelayF= ee`). Combined with the CPFP rule above, this differs from
BIP125 Rule #= 4 - an individual transaction in the package can have a lower
feerate th= an the transaction(s) it is replacing. In fact, it may have 0 fees,
and = the child pays for RBF.

##### Total Number of Replaced Transactions = (Rule #5)

The package cannot replace more than 100 mempool transacti= ons. This is identical
to BIP125 Rule #5.

### Expected FAQs
1. Is it possible for only some of the package to make it into the mempoo= l?

=C2=A0 =C2=A0Yes, it is. However, since we evict transactions fro= m the mempool by
descendant score and the package child is supposed to b= e sponsoring the fees of
its parents, the most common scenario would be = all-or-nothing. This is
incentive-compatible. In fact, to be conservativ= e, package validation should
begin by trying to submit all of the transa= ctions individually, and only use the
package mempool acceptance logic i= f the parents fail due to low feerate.

2. Should we allow packages t= o contain already-confirmed transactions?

=C2=A0 =C2=A0 No, for prac= tical reasons. In mempool validation, we actually aren't able to
tel= l with 100% confidence if we are looking at a transaction that has already<= br>confirmed, because we look up inputs using a UTXO set. If we have histor= ical
block data, it's possible to look for it, but this is inefficie= nt, not always
possible for pruning nodes, and unnecessary because we= 9;re not going to do
anything with the transaction anyway. As such, we a= lready have the expectation
that transaction relay is somewhat "sta= teful" i.e. nobody should be relaying
transactions that have alread= y been confirmed. Similarly, we shouldn't be
relaying packages that = contain already-confirmed transactions.

[1]: https://github.com/bit= coin/bitcoin/pull/22290
[2]: https://github.com/bitcoin/bips/= blob/1f0b563738199ca60d32b4ba779797fc97d040fe/bip-0141.mediawiki#transactio= n-size-calculations
[3]: https://github.com/bitcoin/bitcoin/blob/94f83534e4b7719= 44af7d9ed0f40746f392eb75e/src/policy/policy.cpp#L282
[4]: https://g= ithub.com/bitcoin/bitcoin/pull/16400
[5]: https://github.com/bitcoi= n/bitcoin/pull/21062
[6]: https://github.com/bitcoin/bitcoin/pull/2= 2675
[7]: https://github.com/bitcoin/bitcoin/pull/22796
[8]:= https://github.com/bitcoin/bitcoin/pull/20833
[9]: https://github= .com/bitcoin/bitcoin/pull/21800
[10]: https://github.com/bitcoin/bi= tcoin/pull/16401
[11]: https://github.com/bitcoin/bitcoin/pull/1962= 1
[12]: https://github.com/bitcoin/bips/blob/maste= r/bip-0125.mediawiki
[13]: https://github.com/bitcoin/bi= tcoin/pull/6871/files#diff-34d21af3c614ea3cee120df276c9c4ae95053830d7f1d3de= af009a4625409ad2R1101-R1104
[14]: https://user-images.githubusercontent.com/25183001/1= 33567078-075a971c-0619-4339-9168-b41fd2b90c28.png
[15]: https://user-images.githubuser= content.com/25183001/132856734-fc17da75-f875-44bb-b954-cb7a1725cc0d.png=
[16]: https://= user-images.githubusercontent.com/25183001/133567347-a3e2e4a8-ae9c-49f8-abb= 9-81e8e0aba224.png
[17]: https://user-images.githubusercontent.com/25183001/133567370-= 21566d0e-36c8-4831-b1a8-706634540af3.png
[18]: https://user-images.githubusercontent.c= om/25183001/133567444-bfff1142-439f-4547-800a-2ba2b0242bcb.png
[19]:= https://user-imag= es.githubusercontent.com/25183001/133456219-0bb447cb-dcb4-4a31-b9c1-7d86205= b68bc.png
[20]: https://user-images.githubusercontent.com/25183001/132857787-7b7c6f56-= af96-44c8-8d78-983719888c19.png
_______________________________________________
bitcoin-dev mailing list
= bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev
--00000000000002858905cc9576a9--