Return-Path: <bastien.teinturier@acinq.fr> Received: from smtp1.osuosl.org (smtp1.osuosl.org [IPv6:2605:bc80:3010::138]) by lists.linuxfoundation.org (Postfix) with ESMTP id C8D15C000D for <bitcoin-dev@lists.linuxfoundation.org>; Wed, 22 Sep 2021 07:10:55 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp1.osuosl.org (Postfix) with ESMTP id A904382B34 for <bitcoin-dev@lists.linuxfoundation.org>; Wed, 22 Sep 2021 07:10:55 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org X-Spam-Flag: NO X-Spam-Score: -1.899 X-Spam-Level: X-Spam-Status: No, score=-1.899 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, 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: smtp1.osuosl.org (amavisd-new); dkim=pass (2048-bit key) header.d=acinq-fr.20210112.gappssmtp.com Received: from smtp1.osuosl.org ([127.0.0.1]) by localhost (smtp1.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id O40DrOuhG3AO for <bitcoin-dev@lists.linuxfoundation.org>; Wed, 22 Sep 2021 07:10:52 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.8.0 Received: from mail-qk1-x730.google.com (mail-qk1-x730.google.com [IPv6:2607:f8b0:4864:20::730]) by smtp1.osuosl.org (Postfix) with ESMTPS id 2EF9282B53 for <bitcoin-dev@lists.linuxfoundation.org>; Wed, 22 Sep 2021 07:10:52 +0000 (UTC) Received: by mail-qk1-x730.google.com with SMTP id bk29so6369126qkb.8 for <bitcoin-dev@lists.linuxfoundation.org>; Wed, 22 Sep 2021 00:10:51 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=acinq-fr.20210112.gappssmtp.com; s=20210112; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=MQHec3QYqY8/FbKZKVZTR09Mx9sQ60YjAvnPFK2+tfQ=; b=KbdgcnQBVriFNWSCUhuWe5uqXCll27TDTwBIfV9IYZNQF9exwMruthQqClUUqL/cqR cY3SAJCDp9At7bi6HvrQT36lEh8K3Z7o4DwKOXIITQ7G52Xcdl7MIrbUKfs06t8cOvAP grzD4SlpIc1m1irXGE41VxUYjm4fjhKrzP9pwmS9XGPA4epI0nRgr/ZMc7jf/WEcDb2D 8s8SdYJXopglS5Cp/602F2mfvjB8+FXUmAFNPin6dHInBcj3wbDq/WSdffNGAKJs5cQR Y48qMCcFdxprpvsBUJuPWBlvbHfL4eD/yYdIU6EfTblvmYfLm9GwG2K6opij+tKxNysE rydQ== 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=MQHec3QYqY8/FbKZKVZTR09Mx9sQ60YjAvnPFK2+tfQ=; b=4vqP6jU/CXCorT9IIXLP4R0tGd1XOrblHicVR+JuOYnmgGAzoPv5fPwHAoVvnUNaf4 ZquNo0PEX8At/0N9Vo4U3BeajgFO7qJ+0SbYDNom7keMQBPAYAUcSdeV4XkLkEWI+zQs 77ccH6t27bsaSBGnMwEAkAXDz2aBd1MuVfjbBuPWj8voH6uFJFI/DQ4sXn+odYTPb63/ s3Y+47x239nxgbxonMbNgiQYuRADmm3/J0oWG9HX6FZQFSlJGVPqDL1V9BeURF9BQ51x 40ogXSBdvFua1m1AIE5Zyo/1QH78W+BmCduNQwb9uWiedpsl9lT/e5OnZwWO7ua1mitm eDtw== X-Gm-Message-State: AOAM532lFzEgjBQWIpVQmON/UpYOkNYdt+nt2Hradz6uKo3ZAySLEmuH wgpZqWttU44rIiDAkolhsl7LIw+OZizlWhmrrEBQA4ckT6I= X-Google-Smtp-Source: ABdhPJwjhatFh6iLhTirBs3v/9REzXQRWJBO28lA+kyMtBOfOuiicMrvnyqCEmyhr37GKpp8aNj+BKUPzH/V1M7tfyw= X-Received: by 2002:a25:3613:: with SMTP id d19mr43435587yba.3.1632294650846; Wed, 22 Sep 2021 00:10:50 -0700 (PDT) MIME-Version: 1.0 References: <CAFXO6=+cHyQKM2n9yn4EhwLZO+AUB0ZD81qWPxmpN27rjUoU3w@mail.gmail.com> <CACdvm3NdqYFvJ9t4ocXjdLT09fPu40YYwdvpvOnyYCmk5QXyrQ@mail.gmail.com> <CAFXO6=+auN_X=C52WB8fBqREUYahnFr1dzYotys7k7x+PjO1DQ@mail.gmail.com> <CACdvm3Oo6ABbK79FvuAnZyJ+v4EU3nY=Zi1yzWmv45j5LjWSOg@mail.gmail.com> <CAFXO6=LrHWsddH7VP_AgK93Thw8mdeqmCjjkdXAZy1mymyBefA@mail.gmail.com> In-Reply-To: <CAFXO6=LrHWsddH7VP_AgK93Thw8mdeqmCjjkdXAZy1mymyBefA@mail.gmail.com> From: Bastien TEINTURIER <bastien@acinq.fr> Date: Wed, 22 Sep 2021 09:10:38 +0200 Message-ID: <CACdvm3Ou_o31m1bbn6wkpxvfCiOUDYLF-4s5MVK9Z3i6=w=LzA@mail.gmail.com> To: Gloria Zhao <gloriajzhao@gmail.com> Content-Type: multipart/alternative; boundary="000000000000d5345f05cc903608" X-Mailman-Approved-At: Wed, 22 Sep 2021 08:19:44 +0000 Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org> 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 <bitcoin-dev.lists.linuxfoundation.org> List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe> List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/> List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org> List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help> List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe> X-List-Received-Date: Wed, 22 Sep 2021 07:10:55 -0000 --000000000000d5345f05cc903608 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable 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 <gloriajzhao@gmail.com> 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 <bastien@acinq.fr> > 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-e8= fc-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 <gloriajzhao@gmail.com> = a >> =C3=A9crit : >> >>> 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. >>> >>> > 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 adversarial >>> counterparty attempts to monopolize the mempool descendant limit of the >>> shared transaction A in order to prevent you from submitting a fee-bum= ping >>> child C; I've tried to illustrate this as diagram A here: >>> https://user-images.githubusercontent.com/25183001/134159860-068080d0-b= bb6-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 a= s an >>> individual transaction, and allow it due to the CPFP carve out exemptio= n. A >>> more general goal is: if a transaction would propagate successfully on = its >>> own now, it should still propagate regardless of whether it is included= in >>> a package. The best way to ensure this, as far as I can tell, is to alw= ays >>> 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 ca= se >>> 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 <bastien@acinq.fr> >>> 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 assumption= s >>>>> 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 Core >>>>> 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 applied= 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 Bitcoin >>>>> Core][3]. >>>>> - Note that feerate is not necessarily based on the base fees and >>>>> 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, including >>>>> Child Pays >>>>> for Parent (CPFP) and [BIP125][12] Replace-by-Fee (RBF). Our intentio= n >>>>> 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 broadcas= t >>>>> 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 t= o >>>>> protect >>>>> us from resource exhaustion and aid our efforts to keep the highest f= ee >>>>> 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 tim= e >>>>> 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 spending >>>>> 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 a= t >>>>> 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 with >>>>> 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, but >>>>> a large >>>>> part of the changes are in the mempool's package validation logic. We >>>>> call this >>>>> *Package Mempool Accept*. >>>>> >>>>> ### Previous Work >>>>> >>>>> * Given that mempool validation is DoS-sensitive and complex, it woul= d >>>>> 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 fo= r >>>>> 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'l= l >>>>> 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 pas= s >>>>> 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 th= e >>>>> package >>>>> is treated as each other's ancestor and descendant. [8] >>>>> Packages for which ancestor/descendant limits are accurately captured >>>>> by this >>>>> heuristic: [19] >>>>> >>>>> There are also limitations such as the fact that CPFP carve out is no= t >>>>> 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 wallets >>>>> can >>>>> create a package that utilizes CPFP. >>>>> - Parents are allowed to RBF mempool transactions with a set of rules >>>>> 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. W= e >>>>> 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 package >>>>> is exactly >>>>> 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 it= s >>>>> 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 shar= e >>>>> 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 package >>>>> as one big >>>>> transaction, where: >>>>> >>>>> - Inputs =3D all the inputs of parents + inputs of the child that com= e >>>>> from >>>>> confirmed UTXOs >>>>> - Outputs =3D all the outputs of the child + all outputs of the paren= ts >>>>> 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 virt= ual >>>>> 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 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 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 th= e >>>>> 300vB >>>>> package. The calculcation after deduplication is 100sat increase for = a >>>>> package >>>>> of size 200vB, which correctly fails BIP125#4. Assume all transaction= s >>>>> 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 (which >>>>> would thus >>>>> make its inputs unavailable). >>>>> >>>>> *Rationale*: Even if we are using package feerate, a package will not >>>>> propagate >>>>> as intended if RBF still 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 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 feerat= e >>>>> 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 replacemen= t >>>>> 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 replac= e >>>>> 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." Exampl= e >>>>> 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 (which >>>>> 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 to >>>>> only allow >>>>> the child to have new unconfirmed inputs, either, because it can stil= l >>>>> 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 origina= l >>>>> ones. As >>>>> a result, the entire package is required to be a higher feerate minin= g >>>>> 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 t= he >>>>> transaction(s) it is replacing. In fact, it may have 0 fees, and th= e >>>>> 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 have >>>>> 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 i= s >>>>> 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 i= s >>>>> incentive-compatible. In fact, to be conservative, package validation >>>>> 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 transactions= ? >>>>> >>>>> 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 has >>>>> 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, no= t >>>>> always >>>>> possible for pruning nodes, and unnecessary because we're not going t= o >>>>> 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/1f0b563738199ca60d32b4ba779797fc= 97d040fe/bip-0141.mediawiki#transaction-size-calculations >>>>> [3]: >>>>> https://github.com/bitcoin/bitcoin/blob/94f83534e4b771944af7d9ed0f407= 46f392eb75e/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-34d21af3c614e= a3cee120df276c9c4ae95053830d7f1d3deaf009a4625409ad2R1101-R1104 >>>>> [14]: >>>>> https://user-images.githubusercontent.com/25183001/133567078-075a971c= -0619-4339-9168-b41fd2b90c28.png >>>>> [15]: >>>>> https://user-images.githubusercontent.com/25183001/132856734-fc17da75= -f875-44bb-b954-cb7a1725cc0d.png >>>>> [16]: >>>>> https://user-images.githubusercontent.com/25183001/133567347-a3e2e4a8= -ae9c-49f8-abb9-81e8e0aba224.png >>>>> [17]: >>>>> https://user-images.githubusercontent.com/25183001/133567370-21566d0e= -36c8-4831-b1a8-706634540af3.png >>>>> [18]: >>>>> https://user-images.githubusercontent.com/25183001/133567444-bfff1142= -439f-4547-800a-2ba2b0242bcb.png >>>>> [19]: >>>>> https://user-images.githubusercontent.com/25183001/133456219-0bb447cb= -dcb4-4a31-b9c1-7d86205b68bc.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/mailman/listinfo/bitcoin-dev >>>>> >>>> --000000000000d5345f05cc903608 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable <div dir=3D"ltr">Great, thanks for this clarification!<div><br></div><div>C= an you confirm that this won't be an issue either with your</div><div>e= xample 2C (in your first set of diagrams)? If I understand it</div><div>cor= rectly it shouldn't, but I'd rather be 100% sure.</div><div><br></d= iv><div>A package A=C2=A0+ C will be able to replace A'=C2=A0+ B regard= less of</div><div>the weight of A'=C2=A0+ B?</div><div><br></div><div>T= hanks,</div><div>Bastien</div></div><br><div class=3D"gmail_quote"><div dir= =3D"ltr" class=3D"gmail_attr">Le=C2=A0mar. 21 sept. 2021 =C3=A0=C2=A018:42,= Gloria Zhao <<a href=3D"mailto:gloriajzhao@gmail.com">gloriajzhao@gmail= .com</a>> a =C3=A9crit=C2=A0:<br></div><blockquote class=3D"gmail_quote"= style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);p= adding-left:1ex"><div dir=3D"ltr"><div>Hi Bastien,</div><div><br></div><div= >Excellent diagram :D</div><div><br></div><div>> Here the issue is that = a revoked commitment tx A' is pinned in other<br>> mempools, with a = long chain of descendants (or descendants that reach<br>> the maximum re= placeable size).</div><div>> We would really like A + C to be able to re= place this pinned A'.<br>> We can't submit individually because = A on its own won't replace A'...<span><br></span></div><div><br></d= iv><div>Right, this is a key motivation for having Package RBF. In this cas= e, A+C can replace A' + B1...B24.</div><div><br></div><div> 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 i= ncluding CPFP carve out. As long as A only conflicts with A', it won= 9;t be trying to replace more than 100 transactions. The proposed package R= BF will allow C to pay for A's conflicts, since their package feerate i= s used in the fee comparisons. A is not a descendant of A', so the exis= tence of B1...B24 does not prevent the replacement.</div><div><br></div><di= v>Best,</div><div>Gloria<br></div></div><br><div class=3D"gmail_quote"><div= dir=3D"ltr" class=3D"gmail_attr">On Tue, Sep 21, 2021 at 4:18 PM Bastien T= EINTURIER <<a href=3D"mailto:bastien@acinq.fr" target=3D"_blank">bastien= @acinq.fr</a>> wrote:<br></div><blockquote class=3D"gmail_quote" style= =3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding= -left:1ex"><div dir=3D"ltr">Hi Gloria,<br><br>> I believe this attack is= mitigated as long as we attempt to submit transactions individually<br><br= >Unfortunately not, as there exists a pinning scenario in LN where a<br>dif= ferent commit tx is pinned, but you actually can't know which one.<br><= br>Since I really like your diagrams, I made one as well to illustrate:<br>= <a href=3D"https://user-images.githubusercontent.com/31281497/134198114-5e9= c6857-e8fc-405a-be57-18181d5e54cb.jpg" target=3D"_blank">https://user-image= s.githubusercontent.com/31281497/134198114-5e9c6857-e8fc-405a-be57-18181d5e= 54cb.jpg</a><br><br>Here the issue is that a revoked commitment tx A' i= s pinned in other<br>mempools, with a long chain of descendants (or descend= ants that reach<br>the maximum replaceable size).<br><br>We would really li= ke A + C to be able to replace this pinned A'.<br>We can't submit i= ndividually because A on its own won't replace A'...<br><br>> I = would note that this proposal doesn't accommodate something like diagra= m B, where C is getting CPFP carve out and wants to bring a +1<br><br>No wo= rries, that case shouldn't be a concern.<br>I believe any L2 protocol c= an always ensure it confirms such tx trees<br>"one depth after the oth= er" without impacting funds safety, so it<br>only needs to ensure A + = C can get into mempools.<br><br>Thanks,<br>Bastien</div><br><div class=3D"g= mail_quote"><div dir=3D"ltr" class=3D"gmail_attr">Le=C2=A0mar. 21 sept. 202= 1 =C3=A0=C2=A013:18, Gloria Zhao <<a href=3D"mailto:gloriajzhao@gmail.co= m" target=3D"_blank">gloriajzhao@gmail.com</a>> a =C3=A9crit=C2=A0:<br><= /div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;bo= rder-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir=3D"ltr"><di= v>Hi Bastien,</div><div><br></div><div>Thank you for your feedback!<br></di= v><div><br></div><div>> In your example we have a parent transaction A a= lready in the mempool<br>> and an unrelated child B. We submit a package= C + D where C spends<br>> another of A's inputs. You're highlig= hting that this package may be<br>> rejected because of the unrelated tr= ansaction(s) B.<br><br>> The way I see this, an attacker can abuse this = rule to ensure<br>> transaction A stays pinned in the mempool without co= nfirming by<br>> broadcasting a set of child transactions that reach the= se limits<br>> and pay low fees (where A would be a commit tx in LN).</d= iv><div><br></div><div>I believe you are describing a pinning attack in whi= ch your adversarial counterparty attempts to monopolize the mempool descend= ant limit of the shared=C2=A0 transaction A in order to prevent you from su= bmitting a fee-bumping child C; I've tried to illustrate this as diagra= m A here: <a href=3D"https://user-images.githubusercontent.com/25183001/134= 159860-068080d0-bbb6-4356-ae74-00df00644c74.png" target=3D"_blank">https://= user-images.githubusercontent.com/25183001/134159860-068080d0-bbb6-4356-ae7= 4-00df00644c74.png</a> (please let me know if I'm misunderstanding).</d= iv><div><br></div><div>I believe this attack is mitigated as long as we att= empt to submit transactions individually (and thus take advantage of CPFP c= arve 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 exempt= ion. A more general goal is: if a transaction would propagate successfully = on its own now, it should still propagate regardless of whether it is inclu= ded in a package. The best way to ensure this, as far as I can tell, is to = always try to submit them individually first.<br></div><div><br></div><div>= I would note that this proposal doesn't accommodate something like diag= ram 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 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 ab= out limitations around the CPFP carve out, this is it.</div><div><br></div>= <div>Let me know if this addresses your concerns?<br></div><div><br></div><= div>Thanks,</div><div>Gloria<br></div></div><br><div class=3D"gmail_quote">= <div dir=3D"ltr" class=3D"gmail_attr">On Mon, Sep 20, 2021 at 10:19 AM Bast= ien TEINTURIER <<a href=3D"mailto:bastien@acinq.fr" target=3D"_blank">ba= stien@acinq.fr</a>> wrote:<br></div><blockquote class=3D"gmail_quote" st= yle=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padd= ing-left:1ex"><div dir=3D"ltr">Hi Gloria,<br><br>Thanks for this detailed p= ost!<br><br>The illustrations you provided are very useful for this kind of= graph<br>topology problems.<br><br>The rules you lay out for package RBF l= ook good to me at first glance<br>as there are some subtle improvements com= pared to BIP 125.<br><br>> 1. A package cannot exceed `MAX_PACKAGE_COUNT= =3D25` count and<br>> `MAX_PACKAGE_SIZE=3D101KvB` total size [8]<br><br>= I have a question regarding this rule, as your example 2C could be<br>conce= rning for LN (unless I didn't understand it correctly).<br><br>This als= o touches on the package RBF rule 5 ("The package cannot<br>replace mo= re than 100 mempool transactions.")<br><br>In your example we have a p= arent transaction A already in the mempool<br>and an unrelated child B. We = submit a package C + D where C spends<br>another of A's inputs. You'= ;re highlighting that this package may be<br>rejected because of the unrela= ted transaction(s) B.<br><br>The way I see this, an attacker can abuse this= rule to ensure<br>transaction A stays pinned in the mempool without confir= ming by<br>broadcasting a set of child transactions that reach these limits= <br>and pay low fees (where A would be a commit tx in LN).<br><br>We had to= create the CPFP carve-out rule explicitly to work around<br>this limitatio= n, and I think it would be necessary for package RBF<br>as well, because in= such cases we do want to be able to submit a<br>package A + C where C pays= high fees to speed up A's confirmation,<br>regardless of unrelated unc= onfirmed children of A...<br><br>We could submit only C to benefit from the= existing CPFP carve-out<br>rule, but that wouldn't work if our local m= empool doesn't have A yet,<br>but other remote mempools do.<br><br>Is m= y concern justified? Is this something that we should dig into a<br>bit dee= per?<br><br>Thanks,<br>Bastien</div><br><div class=3D"gmail_quote"><div dir= =3D"ltr" class=3D"gmail_attr">Le=C2=A0jeu. 16 sept. 2021 =C3=A0=C2=A009:55,= Gloria Zhao via bitcoin-dev <<a href=3D"mailto:bitcoin-dev@lists.linuxf= oundation.org" target=3D"_blank">bitcoin-dev@lists.linuxfoundation.org</a>&= gt; a =C3=A9crit=C2=A0:<br></div><blockquote class=3D"gmail_quote" style=3D= "margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-le= ft:1ex"><div dir=3D"ltr">Hi there,<br><br>I'm writing to propose a set = of mempool policy changes to enable package<br>validation (in preparation f= or package relay) in Bitcoin Core. These would not<br>be consensus or P2P p= rotocol changes. However, since mempool policy<br>significantly affects tra= nsaction propagation, I believe this is relevant for<br>the mailing list.<b= r><br>My proposal enables packages consisting of multiple parents and 1 chi= ld. If you<br>develop software that relies on specific transaction relay as= sumptions and/or<br>are interested in using package relay in the future, I&= #39;m very interested to hear<br>your feedback on the utility or restrictiv= eness of these package policies for<br>your use cases.<br><br>A draft imple= mentation of this proposal can be found in [Bitcoin Core<br>PR#22290][1].<b= r><br>An illustrated version of this post can be found at<br><div><a href= =3D"https://gist.github.com/glozow/dc4e9d5c5b14ade7cdfac40f43adb18a" target= =3D"_blank">https://gist.github.com/glozow/dc4e9d5c5b14ade7cdfac40f43adb18a= </a>.</div><div>I have also linked the images below.</div><br>## Background= <br><br>Feel free to skip this section if you are already familiar with mem= pool policy<br>and package relay terminology.<br><br>### Terminology Clarif= ications<br><br>* Package =3D an ordered list of related transactions, repr= esentable by a Directed<br>=C2=A0 Acyclic Graph.<br>* Package Feerate =3D t= he total modified fees divided by the total virtual size of<br>=C2=A0 all t= ransactions in the package.<br>=C2=A0 =C2=A0 - Modified fees =3D a transact= ion's base fees + fee delta applied by the user<br>=C2=A0 =C2=A0 =C2=A0= with `prioritisetransaction`. As such, we expect this to vary across<br>me= mpools.<br>=C2=A0 =C2=A0 - Virtual Size =3D the maximum of virtual sizes ca= lculated using [BIP141<br>=C2=A0 =C2=A0 =C2=A0 virtual size][2] and sigop w= eight. [Implemented here in Bitcoin Core][3].<br>=C2=A0 =C2=A0 - Note that = feerate is not necessarily based on the base fees and serialized<br>=C2=A0 = =C2=A0 =C2=A0 size.<br><br>* Fee-Bumping =3D user/wallet actions that take = advantage of miner incentives to<br>=C2=A0 boost a transaction's candid= acy for inclusion in a block, including Child Pays<br>for Parent (CPFP) and= [BIP125][12] Replace-by-Fee (RBF). Our intention in<br>mempool policy is t= o recognize when the new transaction is more economical to<br>mine than the= original one(s) but not open DoS vectors, so there are some<br>limitations= .<br><br>### Policy<br><br>The purpose of the mempool is to store the best = (to be most incentive-compatible<br>with miners, highest feerate) candidate= s for inclusion in a block. Miners use<br>the mempool to build block templa= tes. The mempool is also useful as a cache for<br>boosting block relay and = validation performance, aiding transaction relay, and<br>generating feerate= estimations.<br><br>Ideally, all consensus-valid transactions paying reaso= nable fees should make it<br>to miners through normal transaction relay, wi= thout any special connectivity or<br>relationships with miners. On the othe= r hand, nodes do not have unlimited<br>resources, and a P2P network designe= d to let any honest node broadcast their<br>transactions also exposes the t= ransaction validation engine to DoS attacks from<br>malicious peers.<br><br= >As such, for unconfirmed transactions we are considering for our mempool, = we<br>apply a set of validation rules in addition to consensus, primarily t= o protect<br>us from resource exhaustion and aid our efforts to keep the hi= ghest fee<br>transactions. We call this mempool _policy_: a set of (configu= rable,<br>node-specific) rules that transactions must abide by in order to = be accepted<br>into our mempool. Transaction "Standardness" rules= and mempool restrictions such<br>as "too-long-mempool-chain" are= both examples of policy.<br><br>### Package Relay and Package Mempool Acce= pt<br><br>In transaction relay, we currently consider transactions one at a= time for<br>submission to the mempool. This creates a limitation in the no= de's ability to<br>determine which transactions have the highest feerat= es, since we cannot take<br>into account descendants (i.e. cannot use CPFP)= until all the transactions are<br>in the mempool. Similarly, we cannot use= a transaction's descendants when<br>considering it for RBF. When an in= dividual transaction does not meet the mempool<br>minimum feerate and the u= ser isn't able to create a replacement transaction<br>directly, it will= not be accepted by mempools.<br><br>This limitation presents a security is= sue for applications and users relying on<br>time-sensitive transactions. F= or example, Lightning and other protocols create<br>UTXOs with multiple spe= nding paths, where one counterparty's spending path opens<br>up after a= timelock, and users are protected from cheating scenarios as long as<br>th= ey redeem on-chain in time. A key security assumption is that all parties&#= 39;<br>transactions will propagate and confirm in a timely manner. This ass= umption can<br>be broken if fee-bumping does not work as intended.<br><br>T= he end goal for Package Relay is to consider multiple transactions at the s= ame<br>time, e.g. a transaction with its high-fee child. This may help us b= etter<br>determine whether transactions should be accepted to our mempool, = especially if<br>they don't meet fee requirements individually or are b= etter RBF candidates as a<br>package. A combination of changes to mempool v= alidation logic, policy, and<br>transaction relay allows us to better propa= gate the transactions with the<br>highest package feerates to miners, and m= akes fee-bumping tools more powerful<br>for users.<br><br>The "relay&q= uot; part of Package Relay suggests P2P messaging changes, but a large<br>p= art of the changes are in the mempool's package validation logic. We ca= ll this<br>*Package Mempool Accept*.<br><br>### Previous Work<br><br>* Give= n that mempool validation is DoS-sensitive and complex, it would be<br>=C2= =A0 dangerous to haphazardly tack on package validation logic. Many efforts= have<br>been made to make mempool validation less opaque (see [#16400][4],= [#21062][5],<br>[#22675][6], [#22796][7]).<br>* [#20833][8] Added basic ca= pabilities for package validation, test accepts only<br>=C2=A0 (no submissi= on to mempool).<br>* [#21800][9] Implemented package ancestor/descendant li= mit checks for arbitrary<br>=C2=A0 packages. Still test accepts only.<br>* = Previous package relay proposals (see [#16401][10], [#19621][11]).<br><br>#= ## Existing Package Rules<br><br>These are in master as introduced in [#208= 33][8] and [#21800][9]. I'll consider<br>them as "given" in t= he rest of this document, though they can be changed, since<br>package vali= dation is test-accept only right now.<br><br>1. A package cannot exceed `MA= X_PACKAGE_COUNT=3D25` count and<br>`MAX_PACKAGE_SIZE=3D101KvB` total size [= 8]<br><br>=C2=A0 =C2=A0*Rationale*: This is already enforced as mempool anc= estor/descendant limits.<br>Presumably, transactions in a package are all r= elated, so exceeding this limit<br>would mean that the package can either b= e split up or it wouldn't pass this<br>mempool policy.<br><br>2. Packag= es must be topologically sorted: if any dependencies exist between<br>trans= actions, parents must appear somewhere before children. [8]<br><br>3. A pac= kage cannot have conflicting transactions, i.e. none of them can spend<br><= div>the same inputs. This also means there cannot be duplicate transactions= . [8]</div><div><br></div>4. When packages are evaluated against ancestor/d= escendant limits in a test<br>accept, the union of all of their descendants= and ancestors is considered. This<br>is essentially a "worst case&quo= t; heuristic where every transaction in the package<br>is treated as each o= ther's ancestor and descendant. [8]<br>Packages for which ancestor/des= cendant limits are accurately captured by this<br><div>heuristic: [19]</div= ><br>There are also limitations such as the fact that CPFP carve out is not= applied<br>to package transactions. #20833 also disables RBF in package va= lidation; this<br>proposal overrides that to allow packages to use RBF.<br>= <br>## Proposed Changes<br><br>The next step in the Package Mempool Accept = project is to implement submission<br>to mempool, initially through RPC onl= y. This allows us to test the submission<br>logic before exposing it on P2P= .<br><br>### Summary<br><br>- Packages may contain already-in-mempool trans= actions.<br>- Packages are 2 generations, Multi-Parent-1-Child.<br>- Fee-re= lated checks use the package feerate. This means that wallets can<br>create= a package that utilizes CPFP.<br>- Parents are allowed to RBF mempool tran= sactions with a set of rules similar<br>=C2=A0 to BIP125. This enables a co= mbination of CPFP and RBF, where a<br>transaction's descendant fees pay= for replacing mempool conflicts.<br><br>There is a draft implementation in= [#22290][1]. It is WIP, but feedback is<br>always welcome.<br><br>### Deta= ils<br><br>#### Packages May Contain Already-in-Mempool Transactions<br><br= >A package may contain transactions that are already in the mempool. We rem= ove<br>("deduplicate") those transactions from the package for th= e purposes of package<br>mempool acceptance. If a package is empty after de= duplication, we do nothing.<br><br>*Rationale*: Mempools vary across the ne= twork. It's possible for a parent to be<br>accepted to the mempool of a= peer on its own due to differences in policy and<br>fee market fluctuation= s. We should not reject or penalize the entire package for<br>an individual= transaction as that could be a censorship vector.<br><br>#### Packages Are= Multi-Parent-1-Child<br><br>Only packages of a specific topology are permi= tted. Namely, a package is exactly<br>1 child with all of its unconfirmed p= arents. After deduplication, the package<br>may be exactly the same, empty,= 1 child, 1 child with just some of its<br>unconfirmed parents, etc. Note t= hat it's possible for the parents to be indirect<br>descendants/ancesto= rs of one another, or for parent and child to share a parent,<br>so we cann= ot make any other topology assumptions.<br><br>*Rationale*: This allows for= fee-bumping by CPFP. Allowing multiple parents<br>makes it possible to fee= -bump a batch of transactions. Restricting packages to a<br>defined topolog= y is also easier to reason about and simplifies the validation<br>logic gre= atly. Multi-parent-1-child allows us to think of the package as one big<br>= transaction, where:<br><br>- Inputs =3D all the inputs of parents + inputs = of the child that come from<br>=C2=A0 confirmed UTXOs<br>- Outputs =3D all = the outputs of the child + all outputs of the parents that<br>=C2=A0 aren&#= 39;t spent by other transactions in the package<br><br>Examples of packages= that follow this rule (variations of example A show some<br>possibilities = after deduplication): ![image][15]<br><br>#### Fee-Related Checks Use Packa= ge Feerate<br><br>Package Feerate =3D the total modified fees divided by th= e total virtual size of<br>all transactions in the package.<br><br>To meet = the two feerate requirements of a mempool, i.e., the pre-configured<br>mini= mum relay feerate (`minRelayTxFee`) and dynamic mempool minimum feerate, th= e<br>total package feerate is used instead of the individual feerate. The i= ndividual<br>transactions are allowed to be below feerate requirements if t= he package meets<br>the feerate requirements. For example, the parent(s) in= the package can have 0<br>fees but be paid for by the child.<br><br>*Ratio= nale*: This can be thought of as "CPFP within a package," solving= the<br>issue of a parent not meeting minimum fees on its own. This allows = L2<br>applications to adjust their fees at broadcast time instead of oversh= ooting or<br>risking getting stuck/pinned.<br><br>We use the package feerat= e of the package *after deduplication*.<br><br>*Rationale*: =C2=A0It would = be incorrect to use the fees of transactions that are<br>already in the mem= pool, as we do not want a transaction's fees to be<br>double-counted fo= r both its individual RBF and package RBF.<br><br>Examples F and G [14] sho= w the same package, but P1 is submitted individually before<br>the package = in example G. In example F, we can see that the 300vB package pays<br>an ad= ditional 200sat in fees, which is not enough to pay for its own bandwidth<b= r>(BIP125#4). In example G, we can see that P1 pays enough to replace M1, b= ut<br>using P1's fees again during package submission would make it loo= k like a 300sat<br>increase for a 200vB package. Even including its fees an= d size would not be<br>sufficient in this example, since the 300sat looks l= ike enough for the 300vB<br>package. The calculcation after deduplication i= s 100sat increase for a package<br>of size 200vB, which correctly fails BIP= 125#4. Assume all transactions have a<br>size of 100vB.<br><br>#### Package= RBF<br><br>If a package meets feerate requirements as a package, the paren= ts in the<br>transaction are allowed to replace-by-fee mempool transactions= . The child cannot<br>replace mempool transactions. Multiple transactions c= an replace the same<br>transaction, but in order to be valid, none of the t= ransactions can try to<br>replace an ancestor of another transaction in the= same package (which would thus<br>make its inputs unavailable).<br><br>*Ra= tionale*: Even if we are using package feerate, a package will not propagat= e<br>as intended if RBF still requires each individual transaction to meet = the<br>feerate requirements.<br><br>We use a set of rules slightly modified= from BIP125 as follows:<br><br>##### Signaling (Rule #1)<br><br>All mempoo= l transactions to be replaced must signal replaceability.<br><br>*Rationale= *: Package RBF signaling logic should be the same for package RBF and<br>si= ngle transaction acceptance. This would be updated if single transaction<br= >validation moves to full RBF.<br><br>##### New Unconfirmed Inputs (Rule #2= )<br><br>A package may include new unconfirmed inputs, but the ancestor fee= rate of the<br>child must be at least as high as the ancestor feerates of e= very transaction<br>being replaced. This is contrary to BIP125#2, which sta= tes "The replacement<br>transaction may only include an unconfirmed in= put if that input was included in<br>one of the original transactions. (An = unconfirmed input spends an output from a<br>currently-unconfirmed transact= ion.)"<br><br>*Rationale*: The purpose of BIP125#2 is to ensure that t= he replacement<br>transaction has a higher ancestor score than the original= transaction(s) (see<br>[comment][13]). Example H [16] shows how adding a n= ew unconfirmed input can lower the<br>ancestor score of the replacement tra= nsaction. P1 is trying to replace M1, and<br>spends an unconfirmed output o= f M2. P1 pays 800sat, M1 pays 600sat, and M2 pays<br>100sat. Assume all tra= nsactions have a size of 100vB. While, in isolation, P1<br>looks like a bet= ter mining candidate than M1, it must be mined with M2, so its<br>ancestor = feerate is actually 4.5sat/vB.=C2=A0 This is lower than M1's ancestor<b= r>feerate, which is 6sat/vB.<br><br>In package RBF, the rule analogous to B= IP125#2 would be "none of the<br>transactions in the package can spend= new unconfirmed inputs." Example J [17] shows<br>why, if any of the p= ackage transactions have ancestors, package feerate is no<br>longer accurat= e. Even though M2 and M3 are not ancestors of P1 (which is the<br>replaceme= nt transaction in an RBF), we're actually interested in the entire<br>p= ackage. A miner should mine M1 which is 5sat/vB instead of M2, M3, P1, P2, = and<br>P3, which is only 4sat/vB. The Package RBF rule cannot be loosened t= o only allow<br>the child to have new unconfirmed inputs, either, because i= t can still cause us<br>to overestimate the package's ancestor score.<b= r><br>However, enforcing a rule analogous to BIP125#2 would not only make P= ackage RBF<br>less useful, but would also break Package RBF for packages wi= th parents already<br>in the mempool: if a package parent has already been = submitted, it would look<br>like the child is spending a "new" un= confirmed input. In example K [18], we're<br>looking to replace M1 with= the entire package including P1, P2, and P3. We must<br>consider the case = where one of the parents is already in the mempool (in this<br>case, P2), w= hich means we must allow P3 to have new unconfirmed inputs. However,<br>M2 = lowers the ancestor score of P3 to 4.3sat/vB, so we should not replace M1<b= r>with this package.<br><br>Thus, the package RBF rule regarding new unconf= irmed inputs is less strict than<br>BIP125#2. However, we still achieve the= same goal of requiring the replacement<br>transactions to have a ancestor = score at least as high as the original ones. As<br>a result, the entire pac= kage is required to be a higher feerate mining candidate<br>than each of th= e replaced transactions.<br><br>Another note: the [comment][13] above the B= IP125#2 code in the original RBF<br>implementation suggests that the rule w= as intended to be temporary.<br><br>##### Absolute Fee (Rule #3)<br><br>The= package must increase the absolute fee of the mempool, i.e. the total fees= <br>of the package must be higher than the absolute fees of the mempool tra= nsactions<br>it replaces. Combined with the CPFP rule above, this differs f= rom BIP125 Rule #3<br>- an individual transaction in the package may have l= ower fees than the<br>=C2=A0 transaction(s) it is replacing. In fact, it ma= y have 0 fees, and the child<br>pays for RBF.<br><br>##### Feerate (Rule #4= )<br><br>The package must pay for its own bandwidth; the package feerate mu= st be higher<br>than the replaced transactions by at least minimum relay fe= erate<br>(`incrementalRelayFee`). Combined with the CPFP rule above, this d= iffers from<br>BIP125 Rule #4 - an individual transaction in the package ca= n have a lower<br>feerate than the transaction(s) it is replacing. In fact,= it may have 0 fees,<br>and the child pays for RBF.<br><br>##### Total Numb= er of Replaced Transactions (Rule #5)<br><br>The package cannot replace mor= e than 100 mempool transactions. This is identical<br>to BIP125 Rule #5.<br= ><br>### Expected FAQs<br><br>1. Is it possible for only some of the packag= e to make it into the mempool?<br><br>=C2=A0 =C2=A0Yes, it is. However, sin= ce we evict transactions from the mempool by<br>descendant score and the pa= ckage child is supposed to be sponsoring the fees of<br>its parents, the mo= st common scenario would be all-or-nothing. This is<br>incentive-compatible= . In fact, to be conservative, package validation should<br>begin by trying= to submit all of the transactions individually, and only use the<br>packag= e mempool acceptance logic if the parents fail due to low feerate.<br><br>2= . Should we allow packages to contain already-confirmed transactions?<br><b= r>=C2=A0 =C2=A0 No, for practical reasons. In mempool validation, we actual= ly aren't able to<br>tell with 100% confidence if we are looking at a t= ransaction that has already<br>confirmed, because we look up inputs using a= UTXO set. If we have historical<br>block data, it's possible to look f= or it, but this is inefficient, not always<br>possible for pruning nodes, a= nd unnecessary because we're not going to do<br>anything with the trans= action anyway. As such, we already have the expectation<br>that transaction= relay is somewhat "stateful" i.e. nobody should be relaying<br>t= ransactions that have already been confirmed. Similarly, we shouldn't b= e<br>relaying packages that contain already-confirmed transactions.<br><br>= [1]: <a href=3D"https://github.com/bitcoin/bitcoin/pull/22290" target=3D"_b= lank">https://github.com/bitcoin/bitcoin/pull/22290</a><br>[2]: <a href=3D"= https://github.com/bitcoin/bips/blob/1f0b563738199ca60d32b4ba779797fc97d040= fe/bip-0141.mediawiki#transaction-size-calculations" target=3D"_blank">http= s://github.com/bitcoin/bips/blob/1f0b563738199ca60d32b4ba779797fc97d040fe/b= ip-0141.mediawiki#transaction-size-calculations</a><br>[3]: <a href=3D"http= s://github.com/bitcoin/bitcoin/blob/94f83534e4b771944af7d9ed0f40746f392eb75= e/src/policy/policy.cpp#L282" target=3D"_blank">https://github.com/bitcoin/= bitcoin/blob/94f83534e4b771944af7d9ed0f40746f392eb75e/src/policy/policy.cpp= #L282</a><br>[4]: <a href=3D"https://github.com/bitcoin/bitcoin/pull/16400"= target=3D"_blank">https://github.com/bitcoin/bitcoin/pull/16400</a><br>[5]= : <a href=3D"https://github.com/bitcoin/bitcoin/pull/21062" target=3D"_blan= k">https://github.com/bitcoin/bitcoin/pull/21062</a><br>[6]: <a href=3D"htt= ps://github.com/bitcoin/bitcoin/pull/22675" target=3D"_blank">https://githu= b.com/bitcoin/bitcoin/pull/22675</a><br>[7]: <a href=3D"https://github.com/= bitcoin/bitcoin/pull/22796" target=3D"_blank">https://github.com/bitcoin/bi= tcoin/pull/22796</a><br>[8]: <a href=3D"https://github.com/bitcoin/bitcoin/= pull/20833" target=3D"_blank">https://github.com/bitcoin/bitcoin/pull/20833= </a><br>[9]: <a href=3D"https://github.com/bitcoin/bitcoin/pull/21800" targ= et=3D"_blank">https://github.com/bitcoin/bitcoin/pull/21800</a><br>[10]: <a= href=3D"https://github.com/bitcoin/bitcoin/pull/16401" target=3D"_blank">h= ttps://github.com/bitcoin/bitcoin/pull/16401</a><br>[11]: <a href=3D"https:= //github.com/bitcoin/bitcoin/pull/19621" target=3D"_blank">https://github.c= om/bitcoin/bitcoin/pull/19621</a><br>[12]: <a href=3D"https://github.com/bi= tcoin/bips/blob/master/bip-0125.mediawiki" target=3D"_blank">https://github= .com/bitcoin/bips/blob/master/bip-0125.mediawiki</a><br>[13]: <a href=3D"ht= tps://github.com/bitcoin/bitcoin/pull/6871/files#diff-34d21af3c614ea3cee120= df276c9c4ae95053830d7f1d3deaf009a4625409ad2R1101-R1104" target=3D"_blank">h= ttps://github.com/bitcoin/bitcoin/pull/6871/files#diff-34d21af3c614ea3cee12= 0df276c9c4ae95053830d7f1d3deaf009a4625409ad2R1101-R1104</a><br>[14]: <a hre= f=3D"https://user-images.githubusercontent.com/25183001/133567078-075a971c-= 0619-4339-9168-b41fd2b90c28.png" target=3D"_blank">https://user-images.gith= ubusercontent.com/25183001/133567078-075a971c-0619-4339-9168-b41fd2b90c28.p= ng</a><br>[15]: <a href=3D"https://user-images.githubusercontent.com/251830= 01/132856734-fc17da75-f875-44bb-b954-cb7a1725cc0d.png" target=3D"_blank">ht= tps://user-images.githubusercontent.com/25183001/132856734-fc17da75-f875-44= bb-b954-cb7a1725cc0d.png</a><br>[16]: <a href=3D"https://user-images.github= usercontent.com/25183001/133567347-a3e2e4a8-ae9c-49f8-abb9-81e8e0aba224.png= " target=3D"_blank">https://user-images.githubusercontent.com/25183001/1335= 67347-a3e2e4a8-ae9c-49f8-abb9-81e8e0aba224.png</a><br>[17]: <a href=3D"http= s://user-images.githubusercontent.com/25183001/133567370-21566d0e-36c8-4831= -b1a8-706634540af3.png" target=3D"_blank">https://user-images.githubusercon= tent.com/25183001/133567370-21566d0e-36c8-4831-b1a8-706634540af3.png</a><br= >[18]: <a href=3D"https://user-images.githubusercontent.com/25183001/133567= 444-bfff1142-439f-4547-800a-2ba2b0242bcb.png" target=3D"_blank">https://use= r-images.githubusercontent.com/25183001/133567444-bfff1142-439f-4547-800a-2= ba2b0242bcb.png</a><br>[19]: <a href=3D"https://user-images.githubuserconte= nt.com/25183001/133456219-0bb447cb-dcb4-4a31-b9c1-7d86205b68bc.png" target= =3D"_blank">https://user-images.githubusercontent.com/25183001/133456219-0b= b447cb-dcb4-4a31-b9c1-7d86205b68bc.png</a><br>[20]: <a href=3D"https://user= -images.githubusercontent.com/25183001/132857787-7b7c6f56-af96-44c8-8d78-98= 3719888c19.png" target=3D"_blank">https://user-images.githubusercontent.com= /25183001/132857787-7b7c6f56-af96-44c8-8d78-983719888c19.png</a><br></div> _______________________________________________<br> bitcoin-dev mailing list<br> <a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">= bitcoin-dev@lists.linuxfoundation.org</a><br> <a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" = rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev</a><br> </blockquote></div> </blockquote></div> </blockquote></div> </blockquote></div> </blockquote></div> --000000000000d5345f05cc903608--