path: root/38/3a55e53a22374be9d6981999dbe2a324664385

Return-Path: <bastien.teinturier@acinq.fr>
Received: from smtp4.osuosl.org (smtp4.osuosl.org [IPv6:2605:bc80:3010::137])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 7A31DC000D
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue, 21 Sep 2021 15:18:44 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp4.osuosl.org (Postfix) with ESMTP id 5C60E4029F
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue, 21 Sep 2021 15:18:44 +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: smtp4.osuosl.org (amavisd-new);
 dkim=pass (2048-bit key) header.d=acinq-fr.20210112.gappssmtp.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 zOAubS5CGKHJ
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue, 21 Sep 2021 15:18:41 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.8.0
Received: from mail-qk1-x72b.google.com (mail-qk1-x72b.google.com
 [IPv6:2607:f8b0:4864:20::72b])
 by smtp4.osuosl.org (Postfix) with ESMTPS id 221E640270
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue, 21 Sep 2021 15:18:40 +0000 (UTC)
Received: by mail-qk1-x72b.google.com with SMTP id p4so55865288qki.3
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue, 21 Sep 2021 08:18:40 -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=FM+Cj/MdVPuxyHYn+eIDNprqV2fapZ0UMrvydkbTynY=;
 b=PuFhGUkEhVDetN25LQeGIzti7/XbCa9YmSifvC1aao3RS5qVeswRUh6nzZL7djVnoT
 MnPK5IYRYKuvxSvwWCT7e7kyJ7rK5fHS0AleQB/dW+FQ6hRKY8PhBZR8PXK0t8FvzmXq
 1XaQr6OAs7GOrnFa/depGLuNQYAR0kCLcvqbEMPrS0vVxJe8Hs9mynAIxRYMAudBTYAe
 evR/Gxl1AGGCk7WnCgj7DCrvLJ3R9uGNgwgikqb2P8jlP1O1ZiLh3ckLwVGhTVl7j3lM
 /LLYsQ7qZmFO3gp/3cNIEK8JgWV1agfbNPnd5ffWdnfda4b8oMlAr74rF5mtnQMyFabO
 d5YQ==
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=FM+Cj/MdVPuxyHYn+eIDNprqV2fapZ0UMrvydkbTynY=;
 b=NVFbCYNz76BYOn3HDNU1GoICkxySQ1u48fVPQy//WQvH+VBg29K2mQQqMiOscDKMHJ
 jtv2kLbR13asSGnczvWAL/dzSzqzO5cL4p7c4v+cX8F8U2JvgtZSi72QQ9BPzLlE8DBL
 ydT7/8P+AzFFZNCeFFl8R/bTcb56Osmt3hVIaTh4DkW/N/hCIF2UQ7QKZLJMz8Dc9Qpw
 rXwy4VI9IUTxHuIlY/YLLCY63q3YQ3K9o+019GDlayllJOLnjRrE3owwjXKCK/10ykly
 sUax5KHz1gdYfHwMIGZ5qIqgT54CnKRztfWSQaj2kihGDWf6LxDMtL2N8MMgh8M0c0JR
 +CYQ==
X-Gm-Message-State: AOAM531thk0eirIUhfyFgzNbmg4gDX1N6tcr1QCbQ36NSnh/IgOjjNvb
 TaL3pJcumH1k68gcw9YwJQs6fsWSaXMA4JhemnXR+w==
X-Google-Smtp-Source: ABdhPJyDhfHJPuOP9o9lii5p0Adi4zs4h8zPFLzYTHkpiYwCUHxbAI2Z/CtxHrb+BUMLFcnnsarsnNW6C3y1iBPXbr4=
X-Received: by 2002:a05:6902:56d:: with SMTP id
 a13mr39430970ybt.512.1632237519601; 
 Tue, 21 Sep 2021 08:18:39 -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>
In-Reply-To: <CAFXO6=+auN_X=C52WB8fBqREUYahnFr1dzYotys7k7x+PjO1DQ@mail.gmail.com>
From: Bastien TEINTURIER <bastien@acinq.fr>
Date: Tue, 21 Sep 2021 17:18:28 +0200
Message-ID: <CACdvm3Oo6ABbK79FvuAnZyJ+v4EU3nY=Zi1yzWmv45j5LjWSOg@mail.gmail.com>
To: Gloria Zhao <gloriajzhao@gmail.com>
Content-Type: multipart/alternative; boundary="0000000000008b953905cc82e937"
X-Mailman-Approved-At: Tue, 21 Sep 2021 16:01:00 +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: Tue, 21 Sep 2021 15:18:44 -0000

--0000000000008b953905cc82e937
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

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-e8fc-=
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-bumpi=
ng
> child C; I've tried to illustrate this as diagram A here:
> https://user-images.githubusercontent.com/25183001/134159860-068080d0-bbb=
6-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 exemption.=
 A
> more general goal is: if a transaction would propagate successfully on it=
s
> own now, it should still propagate regardless of whether it is included i=
n
> a package. The best way to ensure this, as far as I can tell, is to alway=
s
> try to submit them individually first.
>
> 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 (e.g. C has
> very low fees and is bumped 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 limitation=
s
> 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 packag=
e
>>> 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 intereste=
d
>>> 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 virt=
ual
>>> size of
>>>   all transactions in the package.
>>>     - Modified fees =3D a transaction's base fees + fee delta applied b=
y
>>> 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 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 so=
me
>>> 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 unlimit=
ed
>>> 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 wh=
en
>>> considering it for RBF. When an individual transaction does not meet th=
e
>>> 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 at
>>> the same
>>> time, e.g. a transaction with its high-fee child. This may help us bett=
er
>>> 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 t=
he
>>> 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 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 thi=
s
>>> 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 ca=
n
>>> 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 captured b=
y
>>> 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 wallets c=
an
>>> 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. 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 package i=
s
>>> 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 its
>>> 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 package a=
s
>>> one big
>>> transaction, where:
>>>
>>> - Inputs =3D all the inputs of parents + inputs of the child that come =
from
>>>   confirmed UTXOs
>>> - Outputs =3D all the outputs of the child + all outputs of the parents
>>> that
>>>   aren't spent by other transactions in the package
>>>
>>> Examples of packages that follow this rule (variations of example A sho=
w
>>> some
>>> possibilities after deduplication): ![image][15]
>>>
>>> #### Fee-Related Checks Use Package Feerate
>>>
>>> Package Feerate =3D the total modified fees divided by the total virtua=
l
>>> 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 packag=
e
>>> 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 tha=
t
>>> 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 no=
t
>>> 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 th=
e
>>> transaction are allowed to replace-by-fee mempool transactions. The
>>> child cannot
>>> replace mempool transactions. Multiple transactions can replace the sam=
e
>>> 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 t=
he
>>> 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 outpu=
t
>>> from a
>>> currently-unconfirmed transaction.)"
>>>
>>> *Rationale*: The purpose of BIP125#2 is to ensure that the replacement
>>> 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 ancest=
or
>>> 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 (which i=
s
>>> 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 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 woul=
d
>>> 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 (i=
n
>>> 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 BIP12=
5
>>> 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 differ=
s
>>> 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 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 validation
>>> should
>>> begin by trying to submit all of the transactions individually, and onl=
y
>>> 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, 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/1f0b563738199ca60d32b4ba779797fc97=
d040fe/bip-0141.mediawiki#transaction-size-calculations
>>> [3]:
>>> https://github.com/bitcoin/bitcoin/blob/94f83534e4b771944af7d9ed0f40746=
f392eb75e/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-34d21af3c614ea3=
cee120df276c9c4ae95053830d7f1d3deaf009a4625409ad2R1101-R1104
>>> [14]:
>>> https://user-images.githubusercontent.com/25183001/133567078-075a971c-0=
619-4339-9168-b41fd2b90c28.png
>>> [15]:
>>> https://user-images.githubusercontent.com/25183001/132856734-fc17da75-f=
875-44bb-b954-cb7a1725cc0d.png
>>> [16]:
>>> https://user-images.githubusercontent.com/25183001/133567347-a3e2e4a8-a=
e9c-49f8-abb9-81e8e0aba224.png
>>> [17]:
>>> https://user-images.githubusercontent.com/25183001/133567370-21566d0e-3=
6c8-4831-b1a8-706634540af3.png
>>> [18]:
>>> https://user-images.githubusercontent.com/25183001/133567444-bfff1142-4=
39f-4547-800a-2ba2b0242bcb.png
>>> [19]:
>>> https://user-images.githubusercontent.com/25183001/133456219-0bb447cb-d=
cb4-4a31-b9c1-7d86205b68bc.png
>>> [20]:
>>> https://user-images.githubusercontent.com/25183001/132857787-7b7c6f56-a=
f96-44c8-8d78-983719888c19.png
>>> _______________________________________________
>>> bitcoin-dev mailing list
>>> bitcoin-dev@lists.linuxfoundation.org
>>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>>
>>

--0000000000008b953905cc82e937
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Hi Gloria,<br><br>&gt; I believe this attack is mitigated =
as long as we attempt to submit transactions individually<br><br>Unfortunat=
ely not, as there exists a pinning scenario in LN where a<br>different comm=
it tx is pinned, but you actually can&#39;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-5e9c6857-e8fc-=
405a-be57-18181d5e54cb.jpg">https://user-images.githubusercontent.com/31281=
497/134198114-5e9c6857-e8fc-405a-be57-18181d5e54cb.jpg</a><br><br>Here the =
issue is that a revoked commitment tx A&#39; is pinned in other<br>mempools=
, with a long chain of descendants (or descendants that reach<br>the maximu=
m replaceable size).<br><br>We would really like A + C to be able to replac=
e this pinned A&#39;.<br>We can&#39;t submit individually because A on its =
own won&#39;t replace A&#39;...<br><br>&gt; I would note that this proposal=
 doesn&#39;t accommodate something like diagram B, where C is getting CPFP =
carve out and wants to bring a +1<br><br>No worries, that case shouldn&#39;=
t be a concern.<br>I believe any L2 protocol can always ensure it confirms =
such tx trees<br>&quot;one depth after the other&quot; without impacting fu=
nds safety, so it<br>only needs to ensure A + C can get into mempools.<br><=
br>Thanks,<br>Bastien</div><br><div class=3D"gmail_quote"><div dir=3D"ltr" =
class=3D"gmail_attr">Le=C2=A0mar. 21 sept. 2021 =C3=A0=C2=A013:18, Gloria Z=
hao &lt;<a href=3D"mailto:gloriajzhao@gmail.com">gloriajzhao@gmail.com</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"><div>Hi Bastien,</div><div><br></div><div>Thank yo=
u for your feedback!<br></div><div><br></div><div>&gt; In your example we h=
ave a parent transaction A already in the mempool<br>&gt; and an unrelated =
child B. We submit a package C + D where C spends<br>&gt; another of A&#39;=
s inputs. You&#39;re highlighting that this package may be<br>&gt; rejected=
 because of the unrelated transaction(s) B.<br><br>&gt; The way I see this,=
 an attacker can abuse this rule to ensure<br>&gt; transaction A stays pinn=
ed in the mempool without confirming by<br>&gt; broadcasting a set of child=
 transactions that reach these limits<br>&gt; and pay low fees (where A wou=
ld be a commit tx in LN).</div><div><br></div><div>I believe you are descri=
bing a pinning attack in which your adversarial counterparty attempts to mo=
nopolize the mempool descendant limit of the shared=C2=A0 transaction A in =
order to prevent you from submitting a fee-bumping child C; I&#39;ve tried =
to illustrate this as diagram A here: <a href=3D"https://user-images.github=
usercontent.com/25183001/134159860-068080d0-bbb6-4356-ae74-00df00644c74.png=
" target=3D"_blank">https://user-images.githubusercontent.com/25183001/1341=
59860-068080d0-bbb6-4356-ae74-00df00644c74.png</a> (please let me know if I=
&#39;m misunderstanding).</div><div><br></div><div>I believe this attack is=
 mitigated as long as we attempt to submit transactions individually (and t=
hus 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 wo=
uld deduplicate A, submit C as an individual transaction, and allow it due =
to the CPFP carve out exemption. A more general goal is: if a transaction w=
ould propagate successfully on its own now, it should still propagate regar=
dless 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 individually first.<b=
r></div><div><br></div><div>I would note that this proposal doesn&#39;t acc=
ommodate something like diagram B, where C is getting CPFP carve out and wa=
nts to bring a=C2=A0+1 (e.g. C has very low fees and is bumped by D). I don=
&#39;t think this is a use case since C should be the one fee-bumping A, bu=
t since we&#39;re talking about limitations around the CPFP carve out, this=
 is it.</div><div><br></div><div>Let me know if this addresses your concern=
s?<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, S=
ep 20, 2021 at 10:19 AM Bastien TEINTURIER &lt;<a href=3D"mailto:bastien@ac=
inq.fr" target=3D"_blank">bastien@acinq.fr</a>&gt; wrote:<br></div><blockqu=
ote 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><b=
r>Thanks for this detailed post!<br><br>The illustrations you provided are =
very useful for this kind of graph<br>topology problems.<br><br>The rules y=
ou lay out for package RBF look good to me at first glance<br>as there are =
some subtle improvements compared to BIP 125.<br><br>&gt; 1. A package cann=
ot exceed `MAX_PACKAGE_COUNT=3D25` count and<br>&gt; `MAX_PACKAGE_SIZE=3D10=
1KvB` total size [8]<br><br>I have a question regarding this rule, as your =
example 2C could be<br>concerning for LN (unless I didn&#39;t understand it=
 correctly).<br><br>This also touches on the package RBF rule 5 (&quot;The =
package cannot<br>replace more than 100 mempool transactions.&quot;)<br><br=
>In your example we have a parent transaction A already in the mempool<br>a=
nd an unrelated child B. We submit a package C + D where C spends<br>anothe=
r of A&#39;s inputs. You&#39;re highlighting that this package may be<br>re=
jected because of the unrelated transaction(s) B.<br><br>The way I see this=
, an attacker can abuse this rule to ensure<br>transaction A stays pinned i=
n the mempool without confirming by<br>broadcasting a set of child transact=
ions 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 w=
ork around<br>this limitation, and I think it would be necessary for packag=
e RBF<br>as well, because in such cases we do want to be able to submit a<b=
r>package A + C where C pays high fees to speed up A&#39;s confirmation,<br=
>regardless of unrelated unconfirmed children of A...<br><br>We could submi=
t only C to benefit from the existing CPFP carve-out<br>rule, but that woul=
dn&#39;t work if our local mempool doesn&#39;t have A yet,<br>but other rem=
ote mempools do.<br><br>Is my concern justified? Is this something that we =
should dig into a<br>bit deeper?<br><br>Thanks,<br>Bastien</div><br><div cl=
ass=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_attr">Le=C2=A0jeu. 16 s=
ept. 2021 =C3=A0=C2=A009:55, Gloria Zhao via bitcoin-dev &lt;<a href=3D"mai=
lto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">bitcoin-dev@li=
sts.linuxfoundation.org</a>&gt; a =C3=A9crit=C2=A0:<br></div><blockquote cl=
ass=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 there,<br><br>I&#39=
;m writing to propose a set of mempool policy changes to enable package<br>=
validation (in preparation for package relay) in Bitcoin Core. These would =
not<br>be consensus or P2P protocol changes. However, since mempool policy<=
br>significantly affects transaction propagation, I believe this is relevan=
t for<br>the mailing list.<br><br>My proposal enables packages consisting o=
f multiple parents and 1 child. If you<br>develop software that relies on s=
pecific transaction relay assumptions and/or<br>are interested in using pac=
kage relay in the future, I&#39;m very interested to hear<br>your feedback =
on the utility or restrictiveness of these package policies for<br>your use=
 cases.<br><br>A draft implementation of this proposal can be found in [Bit=
coin Core<br>PR#22290][1].<br><br>An illustrated version of this post can b=
e found at<br><div><a href=3D"https://gist.github.com/glozow/dc4e9d5c5b14ad=
e7cdfac40f43adb18a" target=3D"_blank">https://gist.github.com/glozow/dc4e9d=
5c5b14ade7cdfac40f43adb18a</a>.</div><div>I have also linked the images bel=
ow.</div><br>## Background<br><br>Feel free to skip this section if you are=
 already familiar with mempool policy<br>and package relay terminology.<br>=
<br>### Terminology Clarifications<br><br>* Package =3D an ordered list of =
related transactions, representable by a Directed<br>=C2=A0 Acyclic Graph.<=
br>* Package Feerate =3D the total modified fees divided by the total virtu=
al size of<br>=C2=A0 all transactions in the package.<br>=C2=A0 =C2=A0 - Mo=
dified fees =3D a transaction&#39;s base fees + fee delta applied by the us=
er<br>=C2=A0 =C2=A0 =C2=A0 with `prioritisetransaction`. As such, we expect=
 this to vary across<br>mempools.<br>=C2=A0 =C2=A0 - Virtual Size =3D the m=
aximum of virtual sizes calculated using [BIP141<br>=C2=A0 =C2=A0 =C2=A0 vi=
rtual size][2] and sigop weight. [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&#39;s candidacy for inclusion in a block, including Child Pay=
s<br>for Parent (CPFP) and [BIP125][12] Replace-by-Fee (RBF). Our intention=
 in<br>mempool policy is to recognize when the new transaction is more econ=
omical to<br>mine than the original one(s) but not open DoS vectors, so the=
re are some<br>limitations.<br><br>### Policy<br><br>The purpose of the mem=
pool is to store the best (to be most incentive-compatible<br>with miners, =
highest feerate) candidates for inclusion in a block. Miners use<br>the mem=
pool to build block templates. 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 reasonable fees should make it<br>to miners through no=
rmal transaction relay, without any special connectivity or<br>relationship=
s with miners. On the other hand, nodes do not have unlimited<br>resources,=
 and a P2P network designed to let any honest node broadcast their<br>trans=
actions also exposes the transaction validation engine to DoS attacks from<=
br>malicious peers.<br><br>As such, for unconfirmed transactions we are con=
sidering for our mempool, we<br>apply a set of validation rules in addition=
 to consensus, primarily to protect<br>us from resource exhaustion and aid =
our efforts to keep the highest fee<br>transactions. We call this mempool _=
policy_: a set of (configurable,<br>node-specific) rules that transactions =
must abide by in order to be accepted<br>into our mempool. Transaction &quo=
t;Standardness&quot; rules and mempool restrictions such<br>as &quot;too-lo=
ng-mempool-chain&quot; are both examples of policy.<br><br>### Package Rela=
y and Package Mempool Accept<br><br>In transaction relay, we currently cons=
ider transactions one at a time for<br>submission to the mempool. This crea=
tes a limitation in the node&#39;s ability to<br>determine which transactio=
ns have the highest feerates, since we cannot take<br>into account descenda=
nts (i.e. cannot use CPFP) until all the transactions are<br>in the mempool=
. Similarly, we cannot use a transaction&#39;s descendants when<br>consider=
ing it for RBF. When an individual transaction does not meet the mempool<br=
>minimum feerate and the user isn&#39;t able to create a replacement transa=
ction<br>directly, it will not be accepted by mempools.<br><br>This limitat=
ion presents a security issue for applications and users relying on<br>time=
-sensitive transactions. For example, Lightning and other protocols create<=
br>UTXOs with multiple spending paths, where one counterparty&#39;s spendin=
g path opens<br>up after a timelock, and users are protected from cheating =
scenarios as long as<br>they redeem on-chain in time. A key security assump=
tion is that all parties&#39;<br>transactions will propagate and confirm in=
 a timely manner. This assumption can<br>be broken if fee-bumping does not =
work as intended.<br><br>The end goal for Package Relay is to consider mult=
iple transactions at the same<br>time, e.g. a transaction with its high-fee=
 child. This may help us better<br>determine whether transactions should be=
 accepted to our mempool, especially if<br>they don&#39;t meet fee requirem=
ents individually or are better RBF candidates as a<br>package. A combinati=
on of changes to mempool validation logic, policy, and<br>transaction relay=
 allows us to better propagate the transactions with the<br>highest package=
 feerates to miners, and makes fee-bumping tools more powerful<br>for users=
.<br><br>The &quot;relay&quot; part of Package Relay suggests P2P messaging=
 changes, but a large<br>part of the changes are in the mempool&#39;s packa=
ge validation logic. We call this<br>*Package Mempool Accept*.<br><br>### P=
revious Work<br><br>* Given that mempool validation is DoS-sensitive and co=
mplex, it would be<br>=C2=A0 dangerous to haphazardly tack on package valid=
ation 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 capabilities for package validation, test accepts on=
ly<br>=C2=A0 (no submission to mempool).<br>* [#21800][9] Implemented packa=
ge ancestor/descendant limit 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 mast=
er as introduced in [#20833][8] and [#21800][9]. I&#39;ll consider<br>them =
as &quot;given&quot; in the rest of this document, though they can be chang=
ed, since<br>package validation is test-accept only right now.<br><br>1. A =
package cannot exceed `MAX_PACKAGE_COUNT=3D25` count and<br>`MAX_PACKAGE_SI=
ZE=3D101KvB` total size [8]<br><br>=C2=A0 =C2=A0*Rationale*: This is alread=
y enforced as mempool ancestor/descendant limits.<br>Presumably, transactio=
ns in a package are all related, so exceeding this limit<br>would mean that=
 the package can either be split up or it wouldn&#39;t pass this<br>mempool=
 policy.<br><br>2. Packages must be topologically sorted: if any dependenci=
es exist between<br>transactions, parents must appear somewhere before chil=
dren. [8]<br><br>3. A package cannot have conflicting transactions, i.e. no=
ne 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 eva=
luated against ancestor/descendant limits in a test<br>accept, the union of=
 all of their descendants and ancestors is considered. This<br>is essential=
ly a &quot;worst case&quot; heuristic where every transaction in the packag=
e<br>is treated as each other&#39;s ancestor and descendant.  [8]<br>Packag=
es for which ancestor/descendant limits are accurately captured by this<br>=
<div>heuristic: [19]</div><br>There are also limitations such as the fact t=
hat CPFP carve out is not applied<br>to package transactions. #20833 also d=
isables RBF in package validation; this<br>proposal overrides that to allow=
 packages to use RBF.<br><br>## Proposed Changes<br><br>The next step in th=
e Package Mempool Accept project is to implement submission<br>to mempool, =
initially through RPC only. 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 transactions.<br>- Packages are 2 generations, Multi-Pa=
rent-1-Child.<br>- Fee-related checks use the package feerate. This means t=
hat wallets can<br>create a package that utilizes CPFP.<br>- Parents are al=
lowed to RBF mempool transactions with a set of rules similar<br>=C2=A0 to =
BIP125. This enables a combination of CPFP and RBF, where a<br>transaction&=
#39;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>### Details<br><br>#### Packages May Contain Already-in-Me=
mpool Transactions<br><br>A package may contain transactions that are alrea=
dy in the mempool. We remove<br>(&quot;deduplicate&quot;) those transaction=
s from the package for the purposes of package<br>mempool acceptance. If a =
package is empty after deduplication, we do nothing.<br><br>*Rationale*: Me=
mpools vary across the network. It&#39;s possible for a parent to be<br>acc=
epted to the mempool of a peer on its own due to differences in policy and<=
br>fee market fluctuations. We should not reject or penalize the entire pac=
kage 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 sp=
ecific topology are permitted. Namely, a package is exactly<br>1 child with=
 all of its unconfirmed parents. After deduplication, the package<br>may be=
 exactly the same, empty, 1 child, 1 child with just some of its<br>unconfi=
rmed parents, etc. Note that it&#39;s possible for the parents to be indire=
ct<br>descendants/ancestors of one another, or for parent and child to shar=
e a parent,<br>so we cannot make any other topology assumptions.<br><br>*Ra=
tionale*: This allows for fee-bumping by CPFP. Allowing multiple parents<br=
>makes it possible to fee-bump a batch of transactions. Restricting package=
s to a<br>defined topology is also easier to reason about and simplifies th=
e validation<br>logic greatly. Multi-parent-1-child allows us to think of t=
he package as one big<br>transaction, where:<br><br>- Inputs =3D all the in=
puts of parents + inputs of the child that come from<br>=C2=A0 confirmed UT=
XOs<br>- Outputs =3D all the outputs of the child + all outputs of the pare=
nts 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 sh=
ow some<br>possibilities after deduplication): ![image][15]<br><br>#### Fee=
-Related Checks Use Package Feerate<br><br>Package Feerate =3D the total mo=
dified fees divided by the total virtual size of<br>all transactions in the=
 package.<br><br>To meet the two feerate requirements of a mempool, i.e., t=
he pre-configured<br>minimum relay feerate (`minRelayTxFee`) and dynamic me=
mpool minimum feerate, the<br>total package feerate is used instead of the =
individual feerate. The individual<br>transactions are allowed to be below =
feerate requirements if the 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>*Rationale*: This can be thought of as &quot;CPFP within=
 a package,&quot; solving the<br>issue of a parent not meeting minimum fees=
 on its own. This allows L2<br>applications to adjust their fees at broadca=
st time instead of overshooting or<br>risking getting stuck/pinned.<br><br>=
We use the package feerate of the package *after deduplication*.<br><br>*Ra=
tionale*: =C2=A0It would be incorrect to use the fees of transactions that =
are<br>already in the mempool, as we do not want a transaction&#39;s fees t=
o be<br>double-counted for both its individual RBF and package RBF.<br><br>=
Examples F and G [14] show the same package, but P1 is submitted individual=
ly before<br>the package in example G. In example F, we can see that the 30=
0vB package pays<br>an additional 200sat in fees, which is not enough to pa=
y for its own bandwidth<br>(BIP125#4). In example G, we can see that P1 pay=
s enough to replace M1, but<br>using P1&#39;s fees again during package sub=
mission would make it look like a 300sat<br>increase for a 200vB package. E=
ven including its fees and size would not be<br>sufficient in this example,=
 since the 300sat looks like enough for the 300vB<br>package. The calculcat=
ion after deduplication is 100sat increase for a package<br>of size 200vB, =
which correctly fails BIP125#4. Assume all transactions have a<br>size of 1=
00vB.<br><br>#### Package RBF<br><br>If a package meets feerate requirement=
s as a package, the parents in the<br>transaction are allowed to replace-by=
-fee mempool transactions. The child cannot<br>replace mempool transactions=
. Multiple transactions can replace the same<br>transaction, but in order t=
o be valid, none of the transactions can try to<br>replace an ancestor of a=
nother transaction in the same package (which would thus<br>make its inputs=
 unavailable).<br><br>*Rationale*: Even if we are using package feerate, a =
package will not propagate<br>as intended if RBF still requires each indivi=
dual transaction to meet the<br>feerate requirements.<br><br>We use a set o=
f rules slightly modified from BIP125 as follows:<br><br>##### Signaling (R=
ule #1)<br><br>All mempool transactions to be replaced must signal replacea=
bility.<br><br>*Rationale*: Package RBF signaling logic should be the same =
for package RBF and<br>single transaction acceptance. This would be updated=
 if single transaction<br>validation moves to full RBF.<br><br>##### New Un=
confirmed Inputs (Rule #2)<br><br>A package may include new unconfirmed inp=
uts, but the ancestor feerate of the<br>child must be at least as high as t=
he ancestor feerates of every transaction<br>being replaced. This is contra=
ry to BIP125#2, which states &quot;The replacement<br>transaction may only =
include an unconfirmed input if that input was included in<br>one of the or=
iginal transactions. (An unconfirmed input spends an output from a<br>curre=
ntly-unconfirmed transaction.)&quot;<br><br>*Rationale*: The purpose of BIP=
125#2 is to ensure that the replacement<br>transaction has a higher ancesto=
r score than the original transaction(s) (see<br>[comment][13]). Example H =
[16] shows how adding a new unconfirmed input can lower the<br>ancestor sco=
re of the replacement transaction. P1 is trying to replace M1, and<br>spend=
s an unconfirmed output of M2. P1 pays 800sat, M1 pays 600sat, and M2 pays<=
br>100sat. Assume all transactions have a size of 100vB. While, in isolatio=
n, P1<br>looks like a better mining candidate than M1, it must be mined wit=
h M2, so its<br>ancestor feerate is actually 4.5sat/vB.=C2=A0 This is lower=
 than M1&#39;s ancestor<br>feerate, which is 6sat/vB.<br><br>In package RBF=
, the rule analogous to BIP125#2 would be &quot;none of the<br>transactions=
 in the package can spend new unconfirmed inputs.&quot; Example J [17] show=
s<br>why, if any of the package transactions have ancestors, package feerat=
e is no<br>longer accurate. Even though M2 and M3 are not ancestors of P1 (=
which is the<br>replacement transaction in an RBF), we&#39;re actually inte=
rested in the entire<br>package. A miner should mine M1 which is 5sat/vB in=
stead of M2, M3, P1, P2, and<br>P3, which is only 4sat/vB. The Package RBF =
rule cannot be loosened to only allow<br>the child to have new unconfirmed =
inputs, either, because it can still cause us<br>to overestimate the packag=
e&#39;s ancestor score.<br><br>However, enforcing a rule analogous to BIP12=
5#2 would not only make Package RBF<br>less useful, but would also break Pa=
ckage RBF for packages with parents already<br>in the mempool: if a package=
 parent has already been submitted, it would look<br>like the child is spen=
ding a &quot;new&quot; unconfirmed input. In example K [18], we&#39;re<br>l=
ooking to replace M1 with the entire package including P1, P2, and P3. We m=
ust<br>consider the case where one of the parents is already in the mempool=
 (in this<br>case, P2), which means we must allow P3 to have new unconfirme=
d inputs. However,<br>M2 lowers the ancestor score of P3 to 4.3sat/vB, so w=
e should not replace M1<br>with this package.<br><br>Thus, the package RBF =
rule regarding new unconfirmed inputs is less strict than<br>BIP125#2. Howe=
ver, we still achieve the same goal of requiring the replacement<br>transac=
tions to have a ancestor score at least as high as the original ones. As<br=
>a result, the entire package is required to be a higher feerate mining can=
didate<br>than each of the replaced transactions.<br><br>Another note: the =
[comment][13] above the BIP125#2 code in the original RBF<br>implementation=
 suggests that the rule was intended to be temporary.<br><br>##### Absolute=
 Fee (Rule #3)<br><br>The package must increase the absolute fee of the mem=
pool, i.e. the total fees<br>of the package must be higher than the absolut=
e fees of the mempool transactions<br>it replaces. Combined with the CPFP r=
ule above, this differs from BIP125 Rule #3<br>- an individual transaction =
in the package may have lower fees than the<br>=C2=A0 transaction(s) it is =
replacing. In fact, it may have 0 fees, and the child<br>pays for RBF.<br><=
br>##### Feerate (Rule #4)<br><br>The package must pay for its own bandwidt=
h; the package feerate must be higher<br>than the replaced transactions by =
at least minimum relay feerate<br>(`incrementalRelayFee`). Combined with th=
e CPFP rule above, this differs from<br>BIP125 Rule #4 - an individual tran=
saction in the package can 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 Number of Replaced Transactions (Rule #5)<br><br>The p=
ackage cannot replace more than 100 mempool transactions. This is identical=
<br>to BIP125 Rule #5.<br><br>### Expected FAQs<br><br>1. Is it possible fo=
r only some of the package to make it into the mempool?<br><br>=C2=A0 =C2=
=A0Yes, it is. However, since we evict transactions from the mempool by<br>=
descendant score and the package child is supposed to be sponsoring the fee=
s of<br>its parents, the most common scenario would be all-or-nothing. This=
 is<br>incentive-compatible. In fact, to be conservative, package validatio=
n should<br>begin by trying to submit all of the transactions individually,=
 and only use the<br>package mempool acceptance logic if the parents fail d=
ue to low feerate.<br><br>2. Should we allow packages to contain already-co=
nfirmed transactions?<br><br>=C2=A0 =C2=A0 No, for practical reasons. In me=
mpool validation, we actually aren&#39;t able to<br>tell with 100% confiden=
ce if we are looking at a transaction that has already<br>confirmed, becaus=
e we look up inputs using a UTXO set. If we have historical<br>block data, =
it&#39;s possible to look for it, but this is inefficient, not always<br>po=
ssible for pruning nodes, and unnecessary because we&#39;re not going to do=
<br>anything with the transaction anyway. As such, we already have the expe=
ctation<br>that transaction relay is somewhat &quot;stateful&quot; i.e. nob=
ody should be relaying<br>transactions that have already been confirmed. Si=
milarly, we shouldn&#39;t be<br>relaying packages that contain already-conf=
irmed transactions.<br><br>[1]: <a href=3D"https://github.com/bitcoin/bitco=
in/pull/22290" target=3D"_blank">https://github.com/bitcoin/bitcoin/pull/22=
290</a><br>[2]: <a href=3D"https://github.com/bitcoin/bips/blob/1f0b5637381=
99ca60d32b4ba779797fc97d040fe/bip-0141.mediawiki#transaction-size-calculati=
ons" target=3D"_blank">https://github.com/bitcoin/bips/blob/1f0b563738199ca=
60d32b4ba779797fc97d040fe/bip-0141.mediawiki#transaction-size-calculations<=
/a><br>[3]: <a href=3D"https://github.com/bitcoin/bitcoin/blob/94f83534e4b7=
71944af7d9ed0f40746f392eb75e/src/policy/policy.cpp#L282" target=3D"_blank">=
https://github.com/bitcoin/bitcoin/blob/94f83534e4b771944af7d9ed0f40746f392=
eb75e/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/bi=
tcoin/pull/16400</a><br>[5]: <a href=3D"https://github.com/bitcoin/bitcoin/=
pull/21062" target=3D"_blank">https://github.com/bitcoin/bitcoin/pull/21062=
</a><br>[6]: <a href=3D"https://github.com/bitcoin/bitcoin/pull/22675" targ=
et=3D"_blank">https://github.com/bitcoin/bitcoin/pull/22675</a><br>[7]: <a =
href=3D"https://github.com/bitcoin/bitcoin/pull/22796" target=3D"_blank">ht=
tps://github.com/bitcoin/bitcoin/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/bitco=
in/bitcoin/pull/21800" target=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">https://github.com/bitcoin/bitcoin/pull/16401</a>=
<br>[11]: <a href=3D"https://github.com/bitcoin/bitcoin/pull/19621" target=
=3D"_blank">https://github.com/bitcoin/bitcoin/pull/19621</a><br>[12]: <a h=
ref=3D"https://github.com/bitcoin/bips/blob/master/bip-0125.mediawiki" targ=
et=3D"_blank">https://github.com/bitcoin/bips/blob/master/bip-0125.mediawik=
i</a><br>[13]: <a href=3D"https://github.com/bitcoin/bitcoin/pull/6871/file=
s#diff-34d21af3c614ea3cee120df276c9c4ae95053830d7f1d3deaf009a4625409ad2R110=
1-R1104" target=3D"_blank">https://github.com/bitcoin/bitcoin/pull/6871/fil=
es#diff-34d21af3c614ea3cee120df276c9c4ae95053830d7f1d3deaf009a4625409ad2R11=
01-R1104</a><br>[14]: <a href=3D"https://user-images.githubusercontent.com/=
25183001/133567078-075a971c-0619-4339-9168-b41fd2b90c28.png" target=3D"_bla=
nk">https://user-images.githubusercontent.com/25183001/133567078-075a971c-0=
619-4339-9168-b41fd2b90c28.png</a><br>[15]: <a href=3D"https://user-images.=
githubusercontent.com/25183001/132856734-fc17da75-f875-44bb-b954-cb7a1725cc=
0d.png" target=3D"_blank">https://user-images.githubusercontent.com/2518300=
1/132856734-fc17da75-f875-44bb-b954-cb7a1725cc0d.png</a><br>[16]: <a href=
=3D"https://user-images.githubusercontent.com/25183001/133567347-a3e2e4a8-a=
e9c-49f8-abb9-81e8e0aba224.png" target=3D"_blank">https://user-images.githu=
busercontent.com/25183001/133567347-a3e2e4a8-ae9c-49f8-abb9-81e8e0aba224.pn=
g</a><br>[17]: <a href=3D"https://user-images.githubusercontent.com/2518300=
1/133567370-21566d0e-36c8-4831-b1a8-706634540af3.png" target=3D"_blank">htt=
ps://user-images.githubusercontent.com/25183001/133567370-21566d0e-36c8-483=
1-b1a8-706634540af3.png</a><br>[18]: <a href=3D"https://user-images.githubu=
sercontent.com/25183001/133567444-bfff1142-439f-4547-800a-2ba2b0242bcb.png"=
 target=3D"_blank">https://user-images.githubusercontent.com/25183001/13356=
7444-bfff1142-439f-4547-800a-2ba2b0242bcb.png</a><br>[19]: <a href=3D"https=
://user-images.githubusercontent.com/25183001/133456219-0bb447cb-dcb4-4a31-=
b9c1-7d86205b68bc.png" target=3D"_blank">https://user-images.githubusercont=
ent.com/25183001/133456219-0bb447cb-dcb4-4a31-b9c1-7d86205b68bc.png</a><br>=
[20]: <a href=3D"https://user-images.githubusercontent.com/25183001/1328577=
87-7b7c6f56-af96-44c8-8d78-983719888c19.png" target=3D"_blank">https://user=
-images.githubusercontent.com/25183001/132857787-7b7c6f56-af96-44c8-8d78-98=
3719888c19.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>

--0000000000008b953905cc82e937--