path: root/c5/dcec4010b641c0510e4b606db2c0789b9089f6

Return-Path: <antoine.riard@gmail.com>
Received: from smtp1.osuosl.org (smtp1.osuosl.org [140.211.166.138])
 by lists.linuxfoundation.org (Postfix) with ESMTP id CB38DC000B
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sun, 30 Jan 2022 22:53:49 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp1.osuosl.org (Postfix) with ESMTP id A91D6813BD
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sun, 30 Jan 2022 22:53:49 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -2.098
X-Spam-Level: 
X-Spam-Status: No, score=-2.098 tagged_above=-999 required=5
 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
 DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001,
 HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001,
 SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: smtp1.osuosl.org (amavisd-new);
 dkim=pass (2048-bit key) header.d=gmail.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 gvCCv4BC78JM
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sun, 30 Jan 2022 22:53:46 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.8.0
Received: from mail-wm1-x334.google.com (mail-wm1-x334.google.com
 [IPv6:2a00:1450:4864:20::334])
 by smtp1.osuosl.org (Postfix) with ESMTPS id CFA3E813A5
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sun, 30 Jan 2022 22:53:45 +0000 (UTC)
Received: by mail-wm1-x334.google.com with SMTP id r7so8958346wmq.5
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sun, 30 Jan 2022 14:53:45 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112;
 h=mime-version:references:in-reply-to:from:date:message-id:subject:to;
 bh=/M5NgqXFaMM9TAV8R4Scvo/2Uv60KhiW89XvW8syAiQ=;
 b=NGL7Z4Pne7BAm6PfXYis0bKCaOSVJFnEszjM+xD6XTtKcqx6Qk/Rvj/KSohVItOmMK
 6uXvdMw0kimyqDa4geXnvJrFqILiTh8t4iLbxD76u8VA80hY28CiBKRA+0azErV6unYt
 HAIntRR2iuM5kbDhWyEcr8h173O/fYq6hcJC47mI7o164/ZXaVRvM3AWXglQDcu1ZANZ
 fwUdmGhWO8MIAGUbpQfukurzXX1pr0B05UEr2LohGIuO+7QpBUXQ6VxyxSO2QnVFaUVz
 45vcG6w7CcTQ2z3Avbze8jJhBvIOnFPb+Sp6MsLhlnpf9JrThSM0B+5JQwiFCEnjYXuP
 W8Lw==
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;
 bh=/M5NgqXFaMM9TAV8R4Scvo/2Uv60KhiW89XvW8syAiQ=;
 b=pGW/u5zJvgxPZyMjN6L7SeJ3mUNaSSzzkuI4A1KSbLWHvwYkxKCMJRB1w2KWV9YFp+
 OrlWKZEPpUoGqZc+lidjQYo2IWGy13mD82QtH6osUAqM/51LMPxo7pXA4S0jK2/c4ehw
 yoRBsx/uV1qZcp9ThV9PVeoKVXGHUbKuEreQbBp9ETM8mDO507njLbhKKM+aq1h+oS8y
 YyYKRqHleQwqLTJGf2+XTCNRJa+ogDFfYyIBUAgLQO5Wyh2o9po8zgMpU/yozMY20O2R
 Rw3TFMRBdY61MvI8R1tVzFfqM+PCb4W/c0DNaNEKZoPyYQAkVsrclBdlK1Ww1WtAbLqz
 GcsQ==
X-Gm-Message-State: AOAM532gm7+QmBdMlA5SlgOVmu1xkCaP2Z37HE3WZSfKxeriX1Nqj1as
 b8KrZ9jFonJ15ANcklThI8anf86rn+qtDBSlg//XTseY0ZU=
X-Google-Smtp-Source: ABdhPJwl7xADn3Qaz09twN4m33vupX98KLnn89kE3wzhUYgfLvHFbAXtNt2Y3x4IHLqehwUR5vD2v+Ri0alJnoTaskU=
X-Received: by 2002:a05:600c:38a:: with SMTP id
 w10mr19425395wmd.12.1643583223867; 
 Sun, 30 Jan 2022 14:53:43 -0800 (PST)
MIME-Version: 1.0
References: <CAFXO6=LGbaur6XQrE+6a6mAAHXduOCXoWPTgPosxAG59ZkK6Gg@mail.gmail.com>
In-Reply-To: <CAFXO6=LGbaur6XQrE+6a6mAAHXduOCXoWPTgPosxAG59ZkK6Gg@mail.gmail.com>
From: Antoine Riard <antoine.riard@gmail.com>
Date: Sun, 30 Jan 2022 17:53:32 -0500
Message-ID: <CALZpt+EjqKbhnN_5jy3kvYpMvjN8=iwRzMLSM7yS8_j-WzLrBQ@mail.gmail.com>
To: Gloria Zhao <gloriajzhao@gmail.com>, 
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="00000000000037ab2605d6d48a18"
X-Mailman-Approved-At: Sun, 30 Jan 2022 23:11:33 +0000
Subject: Re: [bitcoin-dev] Improving RBF Policy
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: Sun, 30 Jan 2022 22:53:49 -0000

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

Hi Gloria,

Thanks for this RBF sum up. Few thoughts and more context comments if it
can help other readers.

> For starters, the absolute fee pinning attack is especially
> problematic if we apply the same rules (i.e. Rule #3 and #4) in
> Package RBF. Imagine that Alice (honest) and Bob (adversary) share a
> LN channel. The mempool is rather full, so their pre-negotiated
> commitment transactions' feerates would not be considered high
> priority by miners.  Bob broadcasts his commitment transaction and
> attaches a very large child (100KvB with 100,000sat in fees) to his
> anchor output. Alice broadcasts her commitment transaction with a
> fee-bumping child (200vB with 50,000sat fees which is a generous
> 250sat/vB), but this does not meet the absolute fee requirement. She
> would need to add another 50,000sat to replace Bob's commitment
> transaction.

Solving LN pinning attacks, what we're aiming for is enabling a fair
feerate bid between the  counterparties, thus either forcing the adversary
to overbid or to disengage from the confirmation competition. If the
replace-by-feerate rule is adopted, there shouldn't be an incentive for Bob
to
pick up the first option. Though if he does, that's a winning outcome for
Alice, as one of the commitment transactions confirms and her
time-sensitive second-stage HTLC can be subsequently confirmed.

> It's unclear to me if
> we have a very strong reason to change this, but noting it as a
> limitation of our current replacement policy. See [#24007][12].

Deployment of Taproot opens interesting possibilities in the vaults/payment
channels design space, where the tapscripts can commit to different set of
timelocks/quorum of keys. Even if the pre-signed states stay symmetric,
whoever is the publisher, the feerate cost to spend can fluctuate.

> While this isn't completely broken, and the user interface is
> secondary to the safety of the mempool policy

I think with L2s transaction broadcast backend, the stability and clarity
of the RBF user interface is primary. What we could be worried about is a
too-much complex interface easing the way for an attacker to trigger your
L2 node to issue policy-invalid chain of transactions. Especially, when we
consider that an attacker might have leverage on chain of transactions
composition ("force broadcast of commitment A then commitment B, knowing
they will share a CPFP") or even transactions size ("overload commitment A
with HTLCs").

> * If the original transaction is in the top {0.75MvB, 1MvB} of the
>   mempool, apply the current rules (absolute fees must increase and
> pay for the replacement transaction's new bandwidth). Otherwise, use a
> feerate-only rule.

How this new replacement rule would behave if you have a parent in the
"replace-by-feerate" half but the child is in the "replace-by-fee" one ?

If we allow the replacement of the parent based on the feerate, we might
decrease the top block absolute fees.

If we block the replacement of the parent based on the feerate because the
replacement absolute fees aren't above the replaced package, we still
preclude a pinning vector. The child might be low-feerate junk and even
attached to a low ancestor-score branch.

If I'm correct on this limitation, maybe we could turn off the
"replace-by-fee" behavior as soon as the mempool is fulfilled with a few
blocks ?

> * Rate-limit how many replacements we allow per prevout.

Depending on how it is implemented, though I would be concerned it
introduces a new pinning vector in the context of shared-utxo. If it's a
hardcoded constant, it could be exhausted by an adversary starting at the
lowest acceptable feerate then slowly increasing while still not reaching
the top of the mempool. Same if it's time-based or block-based, no
guarantee the replacement slot is honestly used by your counterparty.

Further, an above-the-average replacement frequency might just be the
reflection of your confirmation strategy reacting to block schedule or
mempools historical data. As long as the feerate penalty is paid, I lean to
allow replacement.

(One solution could be to associate per-user "tag" to the LN transactions,
where each "tag" would have its own replacement slots, but privacy?)

> * Rate-limit transaction validation in general, per peer.

I think we could improve on the Core's new transaction requester logic.
Maybe we could bind the peer announced flow based on the feerate score
(modulo validation time) of the previously validated transactions from that
peer ? That said, while related to RBF, it sounds to me that enhancing
Core's rate-limiting transaction strategy is a whole discussion in itself
[0]. Especially ensuring it's tolerant to the specific requirements of LN &
consorts.

> What should they be? We can do some arithmetic to see what happens if
> you start with the biggest/lowest feerate transaction and do a bunch
> of replacements. Maybe we end up with values that are high enough to
> prevent abuse and make sense for applications/users that do RBF.

That's a good question.

One observation is that the attacker can always renew the set of DoSy utxos
to pursue the attack. So maybe we could pick up constants scaled on the
block size ? That way an attacker would have to burn fees, thus deterring
them from launching an attack. Even if the attackers are miners, they have
to renounce their income to acquire new DoSy utxos. If a low-fee period, we
could scale up the constants ?


Overall, I think there is the deployment issue to warn of. Moving to a new
set of RBF rules implies for a lot of Bitcoin applications to rewrite their
RBF logics. We might have a more-or-less long transition period during
which we support both...

Cheers,
Antoine

[0] https://github.com/bitcoin/bitcoin/pull/21224

Le jeu. 27 janv. 2022 =C3=A0 09:10, Gloria Zhao via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> a =C3=A9crit :

> Hi everyone,
>
> This post discusses limitations of current Bitcoin Core RBF policy and
> attempts to start a conversation about how we can improve it,
> summarizing some ideas that have been discussed. Please reply if you
> have any new input on issues to be solved and ideas for improvement!
>
> Just in case I've screwed up the text wrapping again, another copy can be
> found here:
> https://gist.github.com/glozow/25d9662c52453bd08b4b4b1d3783b9ff
>
> ## Background
>
> Please feel free to skip this section if you are already familiar
> with RBF.
>
> Nodes may receive *conflicting* unconfirmed transactions, aka
> "double spends" of the same inputs. Instead of always keeping the
> first transaction, since v0.12, Bitcoin Core mempool policy has
> included a set of Replace-by-Fee (RBF) criteria that allows the second
> transaction to replace the first one and any descendants it may have.
>
> Bitcoin Core RBF policy was previously documented as BIP 125.
> The current RBF policy is documented [here][1]. In summary:
>
> 1. The directly conflicting transactions all signal replaceability
>    explicitly.
>
> 2. The replacement transaction only includes an unconfirmed input if
>    that input was included in one of the directly conflicting
> transactions.
>
> 3. The replacement transaction pays an absolute fee of at least the
>    sum paid by the original transactions.
>
> 4. The additional fees pays for the replacement transaction's
>    bandwidth at or above the rate set by the node's *incremental relay
> feerate*.
>
> 5. The sum of all directly conflicting transactions' descendant counts
>    (number of transactions inclusive of itself and its descendants)
> does not exceed 100.
>
> We can split these rules into 3 categories/goals:
>
> - **Allow Opting Out**: Some applications/businesses are unable to
>   handle transactions that are replaceable (e.g. merchants that use
> zero-confirmation transactions). We (try to) help these businesses by
> honoring BIP125 signaling; we won't replace transactions that have not
> opted in.
>
> - **Incentive Compatibility**: Ensure that our RBF policy would not
>   accept replacement transactions which would decrease fee profits
>   of a miner. In general, if our mempool policy deviates from what is
> economically rational, it's likely that the transactions in our
> mempool will not match the ones in miners' mempools, making our
> fee estimation, compact block relay, and other mempool-dependent
> functions unreliable. Incentive-incompatible policy may also
> encourage transaction submission through routes other than the p2p
> network, harming censorship-resistance and privacy of Bitcoin payments.
>
> - **DoS Protection**: Limit two types of DoS attacks on the node's
>   mempool: (1) the number of times a transaction can be replaced and
> (2) the volume of transactions that can be evicted during a
> replacement.
>
> Even more abstract: our goal is to make a replacement policy that
> results in a useful interface for users and safe policy for
> node operators.
>
> ## Motivation
>
> There are a number of known problems with the current RBF policy.
> Many of these shortcomings exist due to mempool limitations at the
> time RBF was implemented or result from new types of Bitcoin usage;
> they are not criticisms of the original design.
>
> ### Pinning Attacks
>
> The most pressing concern is that attackers may take advantage of
> limitations in RBF policy to prevent other users' transactions from
> being mined or getting accepted as a replacement.
>
> #### SIGHASH_ANYONECANPAY Pinning
>
> BIP125#2 can be bypassed by creating intermediary transactions to be
> replaced together. Anyone can simply split a 1-input 1-output
> transaction off from the replacement transaction, then broadcast the
> transaction as is. This can always be done, and quite cheaply. More
> details in [this comment][2].
>
> In general, if a transaction is signed with SIGHASH\_ANYONECANPAY,
> anybody can just attach a low feerate parent to this transaction and
> lower its ancestor feerate.  Even if you require SIGHASH\_ALL which
> prevents an attacker from changing any outputs, the input can be a
> very low amount (e.g. just above the dust limit) from a low-fee
> ancestor and still bring down the ancestor feerate of the transaction.
>
> TLDR: if your transaction is signed with SIGHASH\_ANYONECANPAY and
> signals replaceability, regardless of the feerate you broadcast at, an
> attacker can lower its mining priority by adding an ancestor.
>
> #### Absolute Fee
>
> The restriction of requiring replacement transactions to increase the
> absolute fee of the mempool has been described as "bonkers." If the
> original transaction has a very large descendant that pays a large
> amount of fees, even if it has a low feerate, the replacement
> transaction must now pay those fees in order to meet Rule #3.
>
> #### Package RBF
>
> There are a number of reasons why, in order to enable Package RBF, we
> cannot use the same criteria.
>
> For starters, the absolute fee pinning attack is especially
> problematic if we apply the same rules (i.e. Rule #3 and #4) in
> Package RBF. Imagine that Alice (honest) and Bob (adversary) share a
> LN channel. The mempool is rather full, so their pre-negotiated
> commitment transactions' feerates would not be considered high
> priority by miners.  Bob broadcasts his commitment transaction and
> attaches a very large child (100KvB with 100,000sat in fees) to his
> anchor output. Alice broadcasts her commitment transaction with a
> fee-bumping child (200vB with 50,000sat fees which is a generous
> 250sat/vB), but this does not meet the absolute fee requirement. She
> would need to add another 50,000sat to replace Bob's commitment
> transaction.
>
> Disallowing new unconfirmed inputs (Rule #2) in Package RBF would be
> broken for packages containing transactions already in the mempool,
> explained [here][7].
>
> Note: I originally [proposed][6] Package RBF using the same Rule #3
> and #4 before I realized how significant this pinning attack is. I'm
> retracting that proposal, and a new set of Package RBF rules would
> follow from whatever the new individual RBF rules end up being.
>
> #### Same Txid Different Witness
>
> Two transactions with the same non-witness data but different
> witnesses have the same txid but different wtxid, and the same fee but
> not necessarily the same feerate. Currently, if we see a transaction
> that has the same txid as one in the mempool, we reject it as a
> duplicate, even if the feerate is much higher. It's unclear to me if
> we have a very strong reason to change this, but noting it as a
> limitation of our current replacement policy. See [#24007][12].
>
> ### User Interface
>
> #### Using Unconfirmed UTXOs to Fund Replacements
>
> The restriction of only allowing confirmed UTXOs for funding a
> fee-bump (Rule #2) can hurt users trying to fee-bump their
> transactions and complicate wallet implementations. If the original
> transaction's output value isn't sufficient to fund a fee-bump and/or
> all of the user's other UTXOs are unconfirmed, they might not be able
> to fund a replacement transaction. Wallet developers also need to
> treat self-owned unconfirmed UTXOs as unusable for fee-bumping, which
> adds complexity to wallet logic. For example, see BDK issues [#144][4]
> and [#414][5].
>
> #### Interface Not Suitable for Coin Selection
>
> Currently, a user cannot simply create a replacement transaction
> targeting a specific feerate or meeting a minimum fee amount and
> expect to meet the RBF criteria. The fee amount depends on the size of
> the replacement transaction, and feerate is almost irrelevant.
>
> Bitcoin Core's `bumpfee` doesn't use the RBF rules when funding the
> replacement. It [estimates][13] a feerate which is "wallet incremental
> relay fee" (a conservative overestimation of the node's incremental
> relay fee) higher than the original transaction, selects coins for
> that feerate, and hopes that it meets the RBF rules. It never fails
> Rule #3 and #4 because it uses all original inputs and refuses to
> bump a transaction with mempool descendants.
>
> This is suboptimal, but is designed to work with the coin selection
> engine: select a feerate first, and then add fees to cover it.
> Following the exact RBF rules would require working the other way
> around: based on how much fees we've added to the transaction and its
> current size, calculate the feerate to see if we meet Rule #4.
>
> While this isn't completely broken, and the user interface is
> secondary to the safety of the mempool policy, we can do much better.
> A much more user-friendly interface would depend *only* on the
> fee and size of the original transactions.
>
> ### Updates to Mempool and Mining
>
> Since RBF was first implemented, a number of improvements have been
> made to mempool and mining logic. For example, we now use ancestor
> feerates in mining (allowing CPFP), and keep track of ancestor
> packages in the mempool.
>
> ## Ideas for Improvements
>
> ### Goals
>
> To summarize, these seem to be desired changes, in order of priority:
>
> 1. Remove Rule #3. The replacement should not be *required* to pay
> higher absolute fees.
>
> 2. Make it impossible for a replacement transaction to have a lower
> mining score than the original transaction(s). This would eliminate
> the `SIGHASH\_ANYONECANPAY` pinning attack.
>
> 3. Remove Rule #2. Adding new unconfirmed inputs should be allowed.
>
> 4. Create a more helpful interface that helps wallet fund replacement
> transactions that aim for a feerate and fee.
>
> ### A Different Model for Fees
>
> For incentive compatibility, I believe there are different
> formulations we should consider.  Most importantly, if we want to get
> rid of the absolute fee rule, we can no longer think of it as "the
> transaction needs to pay for its own bandwidth," since we won't always
> be getting additional fees. That means we need a new method of
> rate-limiting replacements that doesn't require additional fees every
> time.
>
> While it makes sense to think about monetary costs when launching a
> specific type of attack, given that the fees are paid to the miner and
> not to the mempool operators, maybe it doesn't make much sense to
> think about "paying for bandwidth". Maybe we should implement
> transaction validation rate-limiting differently, e.g. building it
> into the P2P layer instead of the mempool policy layer.
>
> Recently, Suhas gave a [formulation][8] for incentive compatibility
> that made sense to me: "are the fees expected to be paid in the next
> (N?) blocks higher or lower if we process this transaction?"
>
> I started by thinking about this where N=3D1 or `1 + p`.
> Here, a rational miner is looking at what fees they would
> collect in the next block, and then some proportion `p` of the rest of
> the blocks based on their hashrate. We're assuming `p` isn't *so high*
> that they would be okay with lower absolute fees in the next 1 block.
> We're also assuming `p` isn't *so low* that the miner doesn't care
> about what's left of the mempool after this block.
>
> A tweak to this formulation is "if we process this transaction, would
> the fees in the next 1 block higher or lower, and is the feerate
> density of the rest of the mempool higher or lower?" This is pretty
> similar, where N=3D1, but we consider the rest of the mempool by feerate
> rather than fees.
>
> ### Mining Score of a Mempool Transaction
>
> We are often interested in finding out what
> the "mining score" of a transaction in the mempool is. That is, when
> the transaction is considered in block template building, what is the
> feerate it is considered at?
>
> Obviously, it's not the transaction's individual feerate. Bitcoin Core
> [mining code sorts][14] transactions by their ancestor feerate and
> includes them packages at a time, keeping track of how this affects the
> package feerates of remaining transactions in the mempool.
>
> *ancestor feerate*: Ancestor feerate is easily accessible information,
> but it's not accurate either, because it doesn't take into account the
> fact that subsets of a transaction's ancestor set can be included
> without it. For example, ancestors may have high feerates on their own
> or we may have [high feerate siblings][8].
>
> TLDR: *Looking at the current ancestor feerate of a transaction is
> insufficient to tell us what feerate it will be considered at when
> building a block template in the future.*
>
> *min(individual feerate, ancestor feerate)*: Another
> heuristic that is simple to calculate based on current mempool tooling
> is to use the [minimum of a transaction's individual score and its
> ancestor score][10] as a conservative measure.  But this can
> overestimate as well (see the example below).
>
> *min ancestor feerate(tx + possible ancestor subsets)* We can also
> take the minimum of every possible ancestor subset, but this can be
> computationally expensive since there can be lots and lots of ancestor
> subsets.
>
> *max ancestor feerate(tx + possible descendant subsets)*: Another idea
> is to use the [maximum ancestor score of the transaction + each of its
> descendants][9]. This doesn't work either; it has the same blindspot
> of ancestor subsets being mined on their own.
>
> #### Mining Score Example
>
> Here's an example illustrating why mining score is tricky to
> efficiently calculate for mempool transactions:
>
> Let's say you have same-size transactions A (21sat/vB), B (1sat/vB),
> C(9sat/vB), D(5sat/vB).
> The layout is: grandparent A, parent B, and two children C and D.
>
> ```
>     A
>     ^
>     B
>    ^ ^
>    C D
> ```
>
> A miner using ancestor packages to build block templates will first
> include A with a mining score of 21. Next, the miner will include B and
> C with a mining score of 6. This leaves D, with a mining score of 5.
>
> Note: in this case, mining by ancestor feerate results in the most
> rational decisions, but [a candidate set-based approach][10] which
> makes ancestor feerate much less relevant could
> be more advantageous in other situations.
>
> Here is a chart showing the "true" mining score alongside the values
> calculating using imperfect heuristics described above. All of them
> can overestimate or underestimate.
>
> ```
>    A     B       C     D
> mining score |   21   |   6   |   6   |   5   |
> ancestor feerate   |   21   |  11   | 10.3  |   9   |
> min(individual, ancestor) |   21   |   1   |   9   |   5   |
> min(tx + ancestor subsets)      |   21   |   1   |   5   |   3   |
> max(tx + descendants subsets) |   21   |   9   |   9   |   5   |
>
> ```
>
> Possibly the best solution for finding the "mining score" of a
> transaction is to build a block template, see what feerate each
> package is included at. Perhaps at some cutoff, remaining mempool
> transactions can be estimated using some heuristic that leans
> {overestimating, underestimating} depending on the situation.
>
> Mining score seems to be relevant in multiple places: Murch and I
> recently [found][3] that it would be very important in
> "ancestor-aware" funding of transactions (the wallet doesn't
> incorporate ancestor fees when using unconfirmed transactions in coin
> selection, which is a bug we want to fix).
>
> In general, it would be nice to know the exact mining priority of
> one's unconfirmed transaction is.  I can think of a few block/mempool
> explorers who might want to display this information for users.
>
> ### RBF Improvement Proposals
>
> After speaking to quite a few people, here are some suggestions
> for improvements that I have heard:
>
> * The ancestor score of the replacement must be {5, 10, N}% higher
>   than that of every original transaction.
>
> * The ancestor score of the replacement must be 1sat/vB higher than
>   that of every original transaction.
>
> * If the original transaction is in the top {0.75MvB, 1MvB} of the
>   mempool, apply the current rules (absolute fees must increase and
> pay for the replacement transaction's new bandwidth). Otherwise, use a
> feerate-only rule.
>
> * If fees don't increase, the size of the replacement transaction must
>   decrease by at least N%.
>
> * Rate-limit how many replacements we allow per prevout.
>
> * Rate-limit transaction validation in general, per peer.
>
> Perhaps some others on the mailing list can chime in to throw other
> ideas into the ring and/or combine some of these rules into a sensible
> policy.
>
> #### Replace by Feerate Only
>
> I don't think there's going to be a single-line feerate-based
> rule that can incorporate everything we need.
> On one hand, a feerate-only approach helps eliminate the issues
> associated with Rule #3. On the other hand, I believe the main concern
> with a feerate-only approach is how to rate limit replacements. We
> don't want to enable an attack such as:
>
> 1. Attacker broadcasts large, low-feerate transaction, and attaches a
> chain of descendants.
>
> 2. The attacker replaces the transaction with a smaller but higher
> feerate transaction, attaching a new chain of descendants.
>
> 3. Repeat 1000 times.
>
> #### Fees in Next Block and Feerate for the Rest of the Mempool
>
> Perhaps we can look at replacements like this:
>
> 1. Calculate the directly conflicting transactions and, with their
> descendants, the original transactions. Check signaling. Limit the
> total volume (e.g. can't be more than 100 total or 1MvB or something).
>
> 2. Find which original transactions would be in the next ~1 block. The
> replacement must pay at least this amount + X% in absolute fees. This
> guarantees that the fees of the next block doesn't decrease.
>
> 3. Find which transactions would be left in the mempool after that ~1
> block. The replacement's feerate must be Y% higher than the maximum
> mining score of these transactions. This guarantees that you now have
> only *better* candidates in your after-this-block mempool than you did
> before, even if the size and fees the transactions decrease.
>
> 4. Now you have two numbers: a minimum absolute fee amount and a
> minimum feerate. Check to see if the replacement(s) meet these
> minimums. Also, a wallet would be able to ask the node "What fee and
> feerate would I need to put on a transaction replacing this?" and use
> this information to fund a replacement transaction, without needing to
> guess or overshoot.
>
> Obviously, there are some magic numbers missing here. X and Y are
> TBD constants to ensure we have some kind of rate limiting for the
> number of replacements allowed using some set of fees.
>
> What should they be? We can do some arithmetic to see what happens if
> you start with the biggest/lowest feerate transaction and do a bunch
> of replacements. Maybe we end up with values that are high enough to
> prevent abuse and make sense for applications/users that do RBF.
>
> ### Mempool Changes Need for Implementation
>
> As described in the mining score section above,
> we may want additional tooling to more accurately assess
> the economic gain of replacing transactions in our mempool.
>
> A few options have been discussed:
>
> * Calculate block templates on the fly when we need to consider a
>   replacement. However, since replacements are [quite common][11]
>   and the information might be useful for other things as well,
>   it may be worth it to cache a block template.
>
> * Keep a persistent block template so that we know what transactions
>   we would put in the next block. We need to remember the feerate
> at which each transaction was included in the template, because an
> ancestor package may be included in the same block template in
> multiple subsets. Transactions included earlier alter the ancestor
> feerate of the remaining transactions in the package. We also need
> to keep track of the new feerates of transactions left over.
>
> * Divide the mempool into two layers, "high feerate" and "low
>   feerate." The high feerate layer contains ~1 block of packages with
> the highest ancestor feerates, and the low feerate layer contains
> everything else. At the edge of a block, we have a Knapsacky problem
> where the next highest ancestor feerate package might not fit, so we
> would probably want the high feerate layer ~2MvB or something to avoid
> underestimating the fees.
>
> ## Acknowledgements
>
> Thank you to everyone whose RBF-related suggestions, grievances,
> criticisms and ideas were incorporated in this document:
> Andrew Chow, Matt Corallo, Suhas Daftuar, Christian Decker,
> Mark Erhardt, Lloyd Fournier, Lisa Neigut, John Newbery,
> Antoine Poinsot, Antoine Riard, Larry Ruane,
> S3RK and Bastien Teinturier.
>
> Thanks for reading!
>
> Best,
> Gloria
>
> [1]:
> https://github.com/bitcoin/bitcoin/blob/master/doc/policy/mempool-replace=
ments.md
> [2]: https://github.com/bitcoin/bitcoin/pull/23121#issuecomment-929475999
> [3]:
> https://github.com/Xekyo/bitcoin/commit/d754b0242ec69d42c570418aebf9c1335=
af0b8ea
> [4]: https://github.com/bitcoindevkit/bdk/issues/144
> [5]: https://github.com/bitcoindevkit/bdk/issues/414
> [6]:
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-September/01=
9464.html
> [7]:
> https://gist.github.com/glozow/dc4e9d5c5b14ade7cdfac40f43adb18a#new-uncon=
firmed-inputs-rule-2
> [8]: https://github.com/bitcoin/bitcoin/pull/23121#discussion_r777131366
> [9]: https://github.com/bitcoin/bitcoin/pull/22290#issuecomment-865887922
> [10]:
> https://gist.github.com/Xekyo/5cb413fe9f26dbce57abfd344ebbfaf2#file-candi=
date-set-based-block-building-md
> [11]: https://github.com/bitcoin/bitcoin/pull/22539#issuecomment-88576367=
0
> [12]: https://github.com/bitcoin/bitcoin/pull/24007
> [13]:
> https://github.com/bitcoin/bitcoin/blob/1a369f006fd0bec373b95001ed84b480e=
852f191/src/wallet/feebumper.cpp#L114
> [14]:
> https://github.com/bitcoin/bitcoin/blob/cf5bb048e80d4cde8828787b266b7f5f2=
e3b6d7b/src/node/miner.cpp#L310-L320
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

<div dir=3D"ltr"><div>Hi Gloria,<br><br>Thanks for this RBF sum up. Few tho=
ughts and more context comments if it can help other readers.<br><br>&gt; F=
or starters, the absolute fee pinning attack is especially<br>&gt; problema=
tic if we apply the same rules (i.e. Rule #3 and #4) in<br>&gt; Package RBF=
. Imagine that Alice (honest) and Bob (adversary) share a<br>&gt; LN channe=
l. The mempool is rather full, so their pre-negotiated<br>&gt; commitment t=
ransactions&#39; feerates would not be considered high<br>&gt; priority by =
miners.=C2=A0 Bob broadcasts his commitment transaction and<br>&gt; attache=
s a very large child (100KvB with 100,000sat in fees) to his<br>&gt; anchor=
 output. Alice broadcasts her commitment transaction with a<br>&gt; fee-bum=
ping child (200vB with 50,000sat fees which is a generous<br>&gt; 250sat/vB=
), but this does not meet the absolute fee requirement. She<br>&gt; would n=
eed to add another 50,000sat to replace Bob&#39;s commitment<br>&gt; transa=
ction.<br><br>Solving LN pinning attacks, what we&#39;re aiming for is enab=
ling a fair feerate bid between the=C2=A0 counterparties, thus either forci=
ng the adversary to overbid or to disengage from the confirmation competiti=
on. If the replace-by-feerate rule is adopted, there shouldn&#39;t be an in=
centive for Bob to<br>pick up the first option. Though if he does, that&#39=
;s a winning outcome for Alice, as one of the commitment transactions confi=
rms and her time-sensitive second-stage HTLC can be subsequently confirmed.=
<br><br>&gt; It&#39;s unclear to me if<br>&gt; we have a very strong reason=
 to change this, but noting it as a<br>&gt; limitation of our current repla=
cement policy. See [#24007][12].<br><br>Deployment of Taproot opens interes=
ting possibilities in the vaults/payment channels design space, where the t=
apscripts can commit to different set of timelocks/quorum of keys. Even if =
the pre-signed states stay symmetric, whoever is the publisher, the feerate=
 cost to spend can fluctuate.<br><br>&gt; While this isn&#39;t completely b=
roken, and the user interface is<br>&gt; secondary to the safety of the mem=
pool policy<br><br>I think with L2s transaction broadcast backend, the stab=
ility and clarity of the RBF user interface is primary. What we could be wo=
rried about is a too-much complex interface easing the way for an attacker =
to trigger your L2 node to issue policy-invalid chain of transactions. Espe=
cially, when we consider that an attacker might have leverage on chain of t=
ransactions composition (&quot;force broadcast of commitment A then commitm=
ent B, knowing they will share a CPFP&quot;) or even transactions size (&qu=
ot;overload commitment A with HTLCs&quot;).<br><br>&gt; * If the original t=
ransaction is in the top {0.75MvB, 1MvB} of the<br>&gt; =C2=A0 mempool, app=
ly the current rules (absolute fees must increase and<br>&gt; pay for the r=
eplacement transaction&#39;s new bandwidth). Otherwise, use a<br>&gt; feera=
te-only rule.<br><br>How this new replacement rule would behave if you have=
 a parent in the &quot;replace-by-feerate&quot; half but the child is in th=
e &quot;replace-by-fee&quot; one ?<br><br>If we allow the replacement of th=
e parent based on the feerate, we might decrease the top block absolute fee=
s.<br><br>If we block the replacement of the parent based on the feerate be=
cause the replacement absolute fees aren&#39;t above the replaced package, =
we still preclude a pinning vector. The child might be low-feerate junk and=
 even attached to a low ancestor-score branch.<br><br>If I&#39;m correct on=
 this limitation, maybe we could turn off the &quot;replace-by-fee&quot; be=
havior as soon as the mempool is fulfilled with a few blocks ?<br><br>&gt; =
* Rate-limit how many replacements we allow per prevout.<br><br>Depending o=
n how it is implemented, though I would be concerned it introduces a new pi=
nning vector in the context of shared-utxo. If it&#39;s a hardcoded constan=
t, it could be exhausted by an adversary starting at the lowest acceptable =
feerate then slowly increasing while still not reaching<br>the top of the m=
empool. Same if it&#39;s time-based or block-based, no guarantee the replac=
ement slot is honestly used by your counterparty.<br><br>Further, an above-=
the-average replacement frequency might just be the reflection of your conf=
irmation strategy reacting to block schedule or mempools historical data. A=
s long as the feerate penalty is paid, I lean to allow replacement.<br><br>=
</div>(One solution could be to associate per-user &quot;tag&quot; to the L=
N transactions, where each &quot;tag&quot; would have its own replacement s=
lots, but privacy?)<br><div><br>&gt; * Rate-limit transaction validation in=
 general, per peer.<br><br>I think we could improve on the Core&#39;s new t=
ransaction requester logic. Maybe we could bind the peer announced flow bas=
ed on the feerate score (modulo validation time) of the previously validate=
d transactions from that peer ? That said, while related to RBF, it sounds =
to me that enhancing Core&#39;s rate-limiting transaction strategy is a who=
le discussion in itself [0]. Especially ensuring it&#39;s tolerant to the s=
pecific requirements of LN &amp; consorts.<br><br>&gt; What should they be?=
 We can do some arithmetic to see what happens if<br>&gt; you start with th=
e biggest/lowest feerate transaction and do a bunch<br>&gt; of replacements=
. Maybe we end up with values that are high enough to<br>&gt; prevent abuse=
 and make sense for applications/users that do RBF.<br><br>That&#39;s a goo=
d question. <br><br>One observation is that the attacker can always renew t=
he set of DoSy utxos to pursue the attack. So maybe we could pick up consta=
nts scaled on the block size ? That way an attacker would have to burn fees=
, thus deterring them from launching an attack. Even if the attackers are m=
iners, they have to renounce their income to acquire new DoSy utxos. If a l=
ow-fee period, we could scale up the constants ?<br><br><br>Overall, I thin=
k there is the deployment issue to warn of. Moving to a new set of RBF rule=
s implies for a lot of Bitcoin applications to rewrite their RBF logics. We=
 might have a more-or-less long transition period during which we support b=
oth...<br><br>Cheers,<br>Antoine<br><br>[0] <a href=3D"https://github.com/b=
itcoin/bitcoin/pull/21224">https://github.com/bitcoin/bitcoin/pull/21224</a=
><br></div></div><br><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"g=
mail_attr">Le=C2=A0jeu. 27 janv. 2022 =C3=A0=C2=A009:10, Gloria Zhao via bi=
tcoin-dev &lt;<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitc=
oin-dev@lists.linuxfoundation.org</a>&gt; a =C3=A9crit=C2=A0:<br></div><blo=
ckquote 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 everyone,=
<br><br>This post discusses limitations of current Bitcoin Core RBF policy =
and<br>attempts to start a conversation about how we can improve it,<br>sum=
marizing some ideas that have been discussed. Please reply if you<br>have a=
ny new input on issues to be solved and ideas for improvement!<br><br>Just =
in case I&#39;ve screwed up the text wrapping again, another copy can be<br=
>found here: <a href=3D"https://gist.github.com/glozow/25d9662c52453bd08b4b=
4b1d3783b9ff" target=3D"_blank">https://gist.github.com/glozow/25d9662c5245=
3bd08b4b4b1d3783b9ff</a><br><br>## Background<br><br>Please feel free to sk=
ip this section if you are already familiar<br>with RBF.<br><br>Nodes may r=
eceive *conflicting* unconfirmed transactions, aka<br>&quot;double spends&q=
uot; of the same inputs. Instead of always keeping the<br>first transaction=
, since v0.12, Bitcoin Core mempool policy has<br>included a set of Replace=
-by-Fee (RBF) criteria that allows the second<br>transaction to replace the=
 first one and any descendants it may have.<br><br>Bitcoin Core RBF policy =
was previously documented as BIP 125.<br>The current RBF policy is document=
ed [here][1]. In summary:<br><br>1. The directly conflicting transactions a=
ll signal replaceability<br>=C2=A0 =C2=A0explicitly.<br><br>2. The replacem=
ent transaction only includes an unconfirmed input if<br>=C2=A0 =C2=A0that =
input was included in one of the directly conflicting<br>transactions.<br><=
br>3. The replacement transaction pays an absolute fee of at least the<br>=
=C2=A0 =C2=A0sum paid by the original transactions.<br><br>4. The additiona=
l fees pays for the replacement transaction&#39;s<br>=C2=A0 =C2=A0bandwidth=
 at or above the rate set by the node&#39;s *incremental relay<br>feerate*.=
<br><br>5. The sum of all directly conflicting transactions&#39; descendant=
 counts<br>=C2=A0 =C2=A0(number of transactions inclusive of itself and its=
 descendants)<br>does not exceed 100.<br><br>We can split these rules into =
3 categories/goals:<br><br>- **Allow Opting Out**: Some applications/busine=
sses are unable to<br>=C2=A0 handle transactions that are replaceable (e.g.=
 merchants that use<br>zero-confirmation transactions). We (try to) help th=
ese businesses by<br>honoring BIP125 signaling; we won&#39;t replace transa=
ctions that have not<br>opted in.<br><br>- **Incentive Compatibility**: Ens=
ure that our RBF policy would not<br>=C2=A0 accept replacement transactions=
 which would decrease fee profits<br>=C2=A0 of a miner. In general, if our =
mempool policy deviates from what is<br>economically rational, it&#39;s lik=
ely that the transactions in our<br>mempool will not match the ones in mine=
rs&#39; mempools, making our<br>fee estimation, compact block relay, and ot=
her mempool-dependent<br>functions unreliable. Incentive-incompatible polic=
y may also<br>encourage transaction submission through routes other than th=
e p2p<br>network, harming censorship-resistance and privacy of Bitcoin paym=
ents.<br><br>- **DoS Protection**: Limit two types of DoS attacks on the no=
de&#39;s<br>=C2=A0 mempool: (1) the number of times a transaction can be re=
placed and<br>(2) the volume of transactions that can be evicted during a<b=
r>replacement.<br><br>Even more abstract: our goal is to make a replacement=
 policy that<br>results in a useful interface for users and safe policy for=
<br>node operators.<br><br>## Motivation<br><br>There are a number of known=
 problems with the current RBF policy.<br>Many of these shortcomings exist =
due to mempool limitations at the<br>time RBF was implemented or result fro=
m new types of Bitcoin usage;<br>they are not criticisms of the original de=
sign.<br><br>### Pinning Attacks<br><br>The most pressing concern is that a=
ttackers may take advantage of<br>limitations in RBF policy to prevent othe=
r users&#39; transactions from<br>being mined or getting accepted as a repl=
acement.<br><br>#### SIGHASH_ANYONECANPAY Pinning<br><br>BIP125#2 can be by=
passed by creating intermediary transactions to be<br>replaced together. An=
yone can simply split a 1-input 1-output<br>transaction off from the replac=
ement transaction, then broadcast the<br>transaction as is. This can always=
 be done, and quite cheaply. More<br>details in [this comment][2].<br><br>I=
n general, if a transaction is signed with SIGHASH\_ANYONECANPAY,<br>anybod=
y can just attach a low feerate parent to this transaction and<br>lower its=
 ancestor feerate.=C2=A0 Even if you require SIGHASH\_ALL which<br>prevents=
 an attacker from changing any outputs, the input can be a<br>very low amou=
nt (e.g. just above the dust limit) from a low-fee<br>ancestor and still br=
ing down the ancestor feerate of the transaction.<br><br>TLDR: if your tran=
saction is signed with SIGHASH\_ANYONECANPAY and<br>signals replaceability,=
 regardless of the feerate you broadcast at, an<br>attacker can lower its m=
ining priority by adding an ancestor.<br><br>#### Absolute Fee<br><br>The r=
estriction of requiring replacement transactions to increase the<br>absolut=
e fee of the mempool has been described as &quot;bonkers.&quot; If the<br>o=
riginal transaction has a very large descendant that pays a large<br>amount=
 of fees, even if it has a low feerate, the replacement<br>transaction must=
 now pay those fees in order to meet Rule #3.<br><br>#### Package RBF<br><b=
r>There are a number of reasons why, in order to enable Package RBF, we<br>=
cannot use the same criteria.<br><br>For starters, the absolute fee pinning=
 attack is especially<br>problematic if we apply the same rules (i.e. Rule =
#3 and #4) in<br>Package RBF. Imagine that Alice (honest) and Bob (adversar=
y) share a<br>LN channel. The mempool is rather full, so their pre-negotiat=
ed<br>commitment transactions&#39; feerates would not be considered high<br=
>priority by miners.=C2=A0 Bob broadcasts his commitment transaction and<br=
>attaches a very large child (100KvB with 100,000sat in fees) to his<br>anc=
hor output. Alice broadcasts her commitment transaction with a<br>fee-bumpi=
ng child (200vB with 50,000sat fees which is a generous<br>250sat/vB), but =
this does not meet the absolute fee requirement. She<br>would need to add a=
nother 50,000sat to replace Bob&#39;s commitment<br>transaction.<br><br>Dis=
allowing new unconfirmed inputs (Rule #2) in Package RBF would be<br>broken=
 for packages containing transactions already in the mempool,<br>explained =
[here][7].<br><br>Note: I originally [proposed][6] Package RBF using the sa=
me Rule #3<br>and #4 before I realized how significant this pinning attack =
is. I&#39;m<br>retracting that proposal, and a new set of Package RBF rules=
 would<br>follow from whatever the new individual RBF rules end up being.<b=
r><br>#### Same Txid Different Witness<br><br>Two transactions with the sam=
e non-witness data but different<br>witnesses have the same txid but differ=
ent wtxid, and the same fee but<br>not necessarily the same feerate. Curren=
tly, if we see a transaction<br>that has the same txid as one in the mempoo=
l, we reject it as a<br>duplicate, even if the feerate is much higher. It&#=
39;s unclear to me if<br>we have a very strong reason to change this, but n=
oting it as a<br>limitation of our current replacement policy. See [#24007]=
[12].<br><br>### User Interface<br><br>#### Using Unconfirmed UTXOs to Fund=
 Replacements<br><br>The restriction of only allowing confirmed UTXOs for f=
unding a<br>fee-bump (Rule #2) can hurt users trying to fee-bump their<br>t=
ransactions and complicate wallet implementations. If the original<br>trans=
action&#39;s output value isn&#39;t sufficient to fund a fee-bump and/or<br=
>all of the user&#39;s other UTXOs are unconfirmed, they might not be able<=
br>to fund a replacement transaction. Wallet developers also need to<br>tre=
at self-owned unconfirmed UTXOs as unusable for fee-bumping, which<br>adds =
complexity to wallet logic. For example, see BDK issues [#144][4]<br>and [#=
414][5].<br><br>#### Interface Not Suitable for Coin Selection<br><br>Curre=
ntly, a user cannot simply create a replacement transaction<br>targeting a =
specific feerate or meeting a minimum fee amount and<br>expect to meet the =
RBF criteria. The fee amount depends on the size of<br>the replacement tran=
saction, and feerate is almost irrelevant.<br><br>Bitcoin Core&#39;s `bumpf=
ee` doesn&#39;t use the RBF rules when funding the<br>replacement. It [esti=
mates][13] a feerate which is &quot;wallet incremental<br>relay fee&quot; (=
a conservative overestimation of the node&#39;s incremental<br>relay fee) h=
igher than the original transaction, selects coins for<br>that feerate, and=
 hopes that it meets the RBF rules. It never fails<br>Rule #3 and #4 becaus=
e it uses all original inputs and refuses to<br>bump a transaction with mem=
pool descendants.<br><br>This is suboptimal, but is designed to work with t=
he coin selection<br>engine: select a feerate first, and then add fees to c=
over it.<br>Following the exact RBF rules would require working the other w=
ay<br>around: based on how much fees we&#39;ve added to the transaction and=
 its<br>current size, calculate the feerate to see if we meet Rule #4.<br><=
br>While this isn&#39;t completely broken, and the user interface is<br>sec=
ondary to the safety of the mempool policy, we can do much better.<br>A muc=
h more user-friendly interface would depend *only* on the<br>fee and size o=
f the original transactions.<br><br>### Updates to Mempool and Mining<br><b=
r>Since RBF was first implemented, a number of improvements have been<br>ma=
de to mempool and mining logic. For example, we now use ancestor<br>feerate=
s in mining (allowing CPFP), and keep track of ancestor<br>packages in the =
mempool.<br><br>## Ideas for Improvements<br><br>### Goals<br><br>To summar=
ize, these seem to be desired changes, in order of priority:<br><br>1. Remo=
ve Rule #3. The replacement should not be *required* to pay<br>higher absol=
ute fees.<br><br>2. Make it impossible for a replacement transaction to hav=
e a lower<br>mining score than the original transaction(s). This would elim=
inate<br>the `SIGHASH\_ANYONECANPAY` pinning attack.<br><br>3. Remove Rule =
#2. Adding new unconfirmed inputs should be allowed.<br><br>4. Create a mor=
e helpful interface that helps wallet fund replacement<br>transactions that=
 aim for a feerate and fee.<br><br>### A Different Model for Fees<br><br>Fo=
r incentive compatibility, I believe there are different<br>formulations we=
 should consider.=C2=A0 Most importantly, if we want to get<br>rid of the a=
bsolute fee rule, we can no longer think of it as &quot;the<br>transaction =
needs to pay for its own bandwidth,&quot; since we won&#39;t always<br>be g=
etting additional fees. That means we need a new method of<br>rate-limiting=
 replacements that doesn&#39;t require additional fees every<br>time.<br><b=
r>While it makes sense to think about monetary costs when launching a<br>sp=
ecific type of attack, given that the fees are paid to the miner and<br>not=
 to the mempool operators, maybe it doesn&#39;t make much sense to<br>think=
 about &quot;paying for bandwidth&quot;. Maybe we should implement<br>trans=
action validation rate-limiting differently, e.g. building it<br>into the P=
2P layer instead of the mempool policy layer.<br><br>Recently, Suhas gave a=
 [formulation][8] for incentive compatibility<br>that made sense to me: &qu=
ot;are the fees expected to be paid in the next<br>(N?) blocks higher or lo=
wer if we process this transaction?&quot;<br><br>I started by thinking abou=
t this where N=3D1 or `1 + p`.<br>Here, a rational miner is looking at what=
 fees they would<br>collect in the next block, and then some proportion `p`=
 of the rest of<br>the blocks based on their hashrate. We&#39;re assuming `=
p` isn&#39;t *so high*<br>that they would be okay with lower absolute fees =
in the next 1 block.<br>We&#39;re also assuming `p` isn&#39;t *so low* that=
 the miner doesn&#39;t care<br>about what&#39;s left of the mempool after t=
his block.<br><br>A tweak to this formulation is &quot;if we process this t=
ransaction, would<br>the fees in the next 1 block higher or lower, and is t=
he feerate<br>density of the rest of the mempool higher or lower?&quot; Thi=
s is pretty<br>similar, where N=3D1, but we consider the rest of the mempoo=
l by feerate<br>rather than fees.<br><br>### Mining Score of a Mempool Tran=
saction<br><br>We are often interested in finding out what<br>the &quot;min=
ing score&quot; of a transaction in the mempool is. That is, when<br>the tr=
ansaction is considered in block template building, what is the<br>feerate =
it is considered at?<br><br>Obviously, it&#39;s not the transaction&#39;s i=
ndividual feerate. Bitcoin Core<br>[mining code sorts][14] transactions by =
their ancestor feerate and<br>includes them packages at a time, keeping tra=
ck of how this affects the<br>package feerates of remaining transactions in=
 the mempool.<br><br>*ancestor feerate*: Ancestor feerate is easily accessi=
ble information,<br>but it&#39;s not accurate either, because it doesn&#39;=
t take into account the<br>fact that subsets of a transaction&#39;s ancesto=
r set can be included<br>without it. For example, ancestors may have high f=
eerates on their own<br>or we may have [high feerate siblings][8].<br><br>T=
LDR: *Looking at the current ancestor feerate of a transaction is<br>insuff=
icient to tell us what feerate it will be considered at when<br>building a =
block template in the future.*<br><br>*min(individual feerate, ancestor fee=
rate)*: Another<br>heuristic that is simple to calculate based on current m=
empool tooling<br>is to use the [minimum of a transaction&#39;s individual =
score and its<br>ancestor score][10] as a conservative measure.=C2=A0 But t=
his can<br>overestimate as well (see the example below). <br><br>*min ances=
tor feerate(tx + possible ancestor subsets)* We can also<br>take the minimu=
m of every possible ancestor subset, but this can be<br>computationally exp=
ensive since there can be lots and lots of ancestor<br>subsets.<br><br>*max=
 ancestor feerate(tx + possible descendant subsets)*: Another idea<br>is to=
 use the [maximum ancestor score of the transaction + each of its<br>descen=
dants][9]. This doesn&#39;t work either; it has the same blindspot<br>of an=
cestor subsets being mined on their own.<br><br>#### Mining Score Example<b=
r><br>Here&#39;s an example illustrating why mining score is tricky to<br>e=
fficiently calculate for mempool transactions:<br><br>Let&#39;s say you hav=
e same-size transactions A (21sat/vB), B (1sat/vB),<br>C(9sat/vB), D(5sat/v=
B).<br>The layout is: grandparent A, parent B, and two children C and D.<br=
><br>```<br>=C2=A0 =C2=A0 A<br>=C2=A0 =C2=A0 ^<br>=C2=A0 =C2=A0 B<br>=C2=A0=
 =C2=A0^ ^<br>=C2=A0 =C2=A0C D<br>```<br><br>A miner using ancestor package=
s to build block templates will first<br>include A with a mining score of 2=
1. Next, the miner will include B and<br>C with a mining score of 6. This l=
eaves D, with a mining score of 5.<br><br>Note: in this case, mining by anc=
estor feerate results in the most<br>rational decisions, but [a candidate s=
et-based approach][10] which<br>makes ancestor feerate much less relevant c=
ould<br>be more advantageous in other situations.<br><br>Here is a chart sh=
owing the &quot;true&quot; mining score alongside the values<br>calculating=
 using imperfect heuristics described above. All of them<br>can overestimat=
e or underestimate.<br><br>```<br>				 =C2=A0 =C2=A0A	 =C2=A0 =C2=A0 B =C2=
=A0 =C2=A0 =C2=A0 C	 =C2=A0 =C2=A0 D<br>mining score			| =C2=A0 21 =C2=A0 |=
 =C2=A0 6 =C2=A0 | =C2=A0 6 =C2=A0 | =C2=A0 5 =C2=A0 |<br>ancestor feerate	=
 =C2=A0	| =C2=A0 21 =C2=A0 | =C2=A011 =C2=A0 | 10.3 =C2=A0| =C2=A0 9 =C2=A0=
 |<br>min(individual, ancestor)	| =C2=A0 21 =C2=A0 | =C2=A0 1 =C2=A0 | =C2=
=A0 9 =C2=A0 | =C2=A0 5 =C2=A0 |<br>min(tx + ancestor subsets) =C2=A0 =C2=
=A0 =C2=A0| =C2=A0 21 =C2=A0 | =C2=A0 1 =C2=A0 | =C2=A0 5 =C2=A0 | =C2=A0 3=
 =C2=A0 |<br>max(tx + descendants subsets)	| =C2=A0 21 =C2=A0 | =C2=A0 9 =
=C2=A0 | =C2=A0 9 =C2=A0 | =C2=A0 5 =C2=A0 |<br><br>```<br><br>Possibly the=
 best solution for finding the &quot;mining score&quot; of a<br>transaction=
 is to build a block template, see what feerate each<br>package is included=
 at. Perhaps at some cutoff, remaining mempool<br>transactions can be estim=
ated using some heuristic that leans<br>{overestimating, underestimating} d=
epending on the situation.<br><br>Mining score seems to be relevant in mult=
iple places: Murch and I<br>recently [found][3] that it would be very impor=
tant in<br>&quot;ancestor-aware&quot; funding of transactions (the wallet d=
oesn&#39;t<br>incorporate ancestor fees when using unconfirmed transactions=
 in coin<br>selection, which is a bug we want to fix).<br><br>In general, i=
t would be nice to know the exact mining priority of<br>one&#39;s unconfirm=
ed transaction is.=C2=A0 I can think of a few block/mempool<br>explorers wh=
o might want to display this information for users.<br><br>### RBF Improvem=
ent Proposals<br><br>After speaking to quite a few people, here are some su=
ggestions<br>for improvements that I have heard:<br><br>* The ancestor scor=
e of the replacement must be {5, 10, N}% higher<br>=C2=A0 than that of ever=
y original transaction.<br><br>* The ancestor score of the replacement must=
 be 1sat/vB higher than<br>=C2=A0 that of every original transaction.<br><b=
r>* If the original transaction is in the top {0.75MvB, 1MvB} of the<br>=C2=
=A0 mempool, apply the current rules (absolute fees must increase and<br>pa=
y for the replacement transaction&#39;s new bandwidth). Otherwise, use a<br=
>feerate-only rule.<br><br>* If fees don&#39;t increase, the size of the re=
placement transaction must<br>=C2=A0 decrease by at least N%.<br><br>* Rate=
-limit how many replacements we allow per prevout.<br><br>* Rate-limit tran=
saction validation in general, per peer.<br><br>Perhaps some others on the =
mailing list can chime in to throw other<br>ideas into the ring and/or comb=
ine some of these rules into a sensible<br>policy.<br><br>#### Replace by F=
eerate Only<br><br>I don&#39;t think there&#39;s going to be a single-line =
feerate-based<br>rule that can incorporate everything we need.<br>On one ha=
nd, a feerate-only approach helps eliminate the issues<br>associated with R=
ule #3. On the other hand, I believe the main concern<br>with a feerate-onl=
y approach is how to rate limit replacements. We<br>don&#39;t want to enabl=
e an attack such as:<br><br>1. Attacker broadcasts large, low-feerate trans=
action, and attaches a<br>chain of descendants.<br><br>2. The attacker repl=
aces the transaction with a smaller but higher<br>feerate transaction, atta=
ching a new chain of descendants.<br><br>3. Repeat 1000 times.<br><br>#### =
Fees in Next Block and Feerate for the Rest of the Mempool<br><br>Perhaps w=
e can look at replacements like this:<br><br>1. Calculate the directly conf=
licting transactions and, with their<br>descendants, the original transacti=
ons. Check signaling. Limit the<br>total volume (e.g. can&#39;t be more tha=
n 100 total or 1MvB or something).<br><br>2. Find which original transactio=
ns would be in the next ~1 block. The<br>replacement must pay at least this=
 amount + X% in absolute fees. This<br>guarantees that the fees of the next=
 block doesn&#39;t decrease.<br><br>3. Find which transactions would be lef=
t in the mempool after that ~1<br>block. The replacement&#39;s feerate must=
 be Y% higher than the maximum<br>mining score of these transactions. This =
guarantees that you now have<br>only *better* candidates in your after-this=
-block mempool than you did<br>before, even if the size and fees the transa=
ctions decrease.<br><br>4. Now you have two numbers: a minimum absolute fee=
 amount and a<br>minimum feerate. Check to see if the replacement(s) meet t=
hese<br>minimums. Also, a wallet would be able to ask the node &quot;What f=
ee and<br>feerate would I need to put on a transaction replacing this?&quot=
; and use<br>this information to fund a replacement transaction, without ne=
eding to<br>guess or overshoot.<br><br>Obviously, there are some magic numb=
ers missing here. X and Y are<br>TBD constants to ensure we have some kind =
of rate limiting for the<br>number of replacements allowed using some set o=
f fees.<br><br>What should they be? We can do some arithmetic to see what h=
appens if<br>you start with the biggest/lowest feerate transaction and do a=
 bunch<br>of replacements. Maybe we end up with values that are high enough=
 to<br>prevent abuse and make sense for applications/users that do RBF.<br>=
<br>### Mempool Changes Need for Implementation<br><br>As described in the =
mining score section above,<br>we may want additional tooling to more accur=
ately assess<br>the economic gain of replacing transactions in our mempool.=
<br><br>A few options have been discussed:<br><br>* Calculate block templat=
es on the fly when we need to consider a<br>=C2=A0 replacement. However, si=
nce replacements are [quite common][11]<br>=C2=A0 and the information might=
 be useful for other things as well, <br>=C2=A0 it may be worth it to cache=
 a block template.<br><br>* Keep a persistent block template so that we kno=
w what transactions<br>=C2=A0 we would put in the next block. We need to re=
member the feerate<br>at which each transaction was included in the templat=
e, because an<br>ancestor package may be included in the same block templat=
e in<br>multiple subsets. Transactions included earlier alter the ancestor<=
br>feerate of the remaining transactions in the package. We also need<br>to=
 keep track of the new feerates of transactions left over. <br><br>* Divide=
 the mempool into two layers, &quot;high feerate&quot; and &quot;low<br>=C2=
=A0 feerate.&quot; The high feerate layer contains ~1 block of packages wit=
h<br>the highest ancestor feerates, and the low feerate layer contains<br>e=
verything else. At the edge of a block, we have a Knapsacky problem<br>wher=
e the next highest ancestor feerate package might not fit, so we<br>would p=
robably want the high feerate layer ~2MvB or something to avoid<br>underest=
imating the fees.<br><br>## Acknowledgements<br><br>Thank you to everyone w=
hose RBF-related suggestions, grievances,<br>criticisms and ideas were inco=
rporated in this document:<br>Andrew Chow, Matt Corallo, Suhas Daftuar, Chr=
istian Decker,<br>Mark Erhardt, Lloyd Fournier, Lisa Neigut, John Newbery,<=
br>Antoine Poinsot, Antoine Riard, Larry Ruane,<br><div>S3RK and Bastien Te=
inturier.</div><div><br></div><div>Thanks for reading!</div><div><br></div>=
<div>Best,<br></div><div>Gloria<br></div><br>[1]: <a href=3D"https://github=
.com/bitcoin/bitcoin/blob/master/doc/policy/mempool-replacements.md" target=
=3D"_blank">https://github.com/bitcoin/bitcoin/blob/master/doc/policy/mempo=
ol-replacements.md</a><br>[2]: <a href=3D"https://github.com/bitcoin/bitcoi=
n/pull/23121#issuecomment-929475999" target=3D"_blank">https://github.com/b=
itcoin/bitcoin/pull/23121#issuecomment-929475999</a><br>[3]: <a href=3D"htt=
ps://github.com/Xekyo/bitcoin/commit/d754b0242ec69d42c570418aebf9c1335af0b8=
ea" target=3D"_blank">https://github.com/Xekyo/bitcoin/commit/d754b0242ec69=
d42c570418aebf9c1335af0b8ea</a><br>[4]: <a href=3D"https://github.com/bitco=
indevkit/bdk/issues/144" target=3D"_blank">https://github.com/bitcoindevkit=
/bdk/issues/144</a><br>[5]: <a href=3D"https://github.com/bitcoindevkit/bdk=
/issues/414" target=3D"_blank">https://github.com/bitcoindevkit/bdk/issues/=
414</a><br>[6]: <a href=3D"https://lists.linuxfoundation.org/pipermail/bitc=
oin-dev/2021-September/019464.html" target=3D"_blank">https://lists.linuxfo=
undation.org/pipermail/bitcoin-dev/2021-September/019464.html</a><br>[7]: <=
a href=3D"https://gist.github.com/glozow/dc4e9d5c5b14ade7cdfac40f43adb18a#n=
ew-unconfirmed-inputs-rule-2" target=3D"_blank">https://gist.github.com/glo=
zow/dc4e9d5c5b14ade7cdfac40f43adb18a#new-unconfirmed-inputs-rule-2</a><br>[=
8]: <a href=3D"https://github.com/bitcoin/bitcoin/pull/23121#discussion_r77=
7131366" target=3D"_blank">https://github.com/bitcoin/bitcoin/pull/23121#di=
scussion_r777131366</a><br>[9]: <a href=3D"https://github.com/bitcoin/bitco=
in/pull/22290#issuecomment-865887922" target=3D"_blank">https://github.com/=
bitcoin/bitcoin/pull/22290#issuecomment-865887922</a><br>[10]: <a href=3D"h=
ttps://gist.github.com/Xekyo/5cb413fe9f26dbce57abfd344ebbfaf2#file-candidat=
e-set-based-block-building-md" target=3D"_blank">https://gist.github.com/Xe=
kyo/5cb413fe9f26dbce57abfd344ebbfaf2#file-candidate-set-based-block-buildin=
g-md</a><br>[11]: <a href=3D"https://github.com/bitcoin/bitcoin/pull/22539#=
issuecomment-885763670" target=3D"_blank">https://github.com/bitcoin/bitcoi=
n/pull/22539#issuecomment-885763670</a><br>[12]: <a href=3D"https://github.=
com/bitcoin/bitcoin/pull/24007" target=3D"_blank">https://github.com/bitcoi=
n/bitcoin/pull/24007</a><br>[13]: <a href=3D"https://github.com/bitcoin/bit=
coin/blob/1a369f006fd0bec373b95001ed84b480e852f191/src/wallet/feebumper.cpp=
#L114" target=3D"_blank">https://github.com/bitcoin/bitcoin/blob/1a369f006f=
d0bec373b95001ed84b480e852f191/src/wallet/feebumper.cpp#L114</a><br><div>[1=
4]: <a href=3D"https://github.com/bitcoin/bitcoin/blob/cf5bb048e80d4cde8828=
787b266b7f5f2e3b6d7b/src/node/miner.cpp#L310-L320" target=3D"_blank">https:=
//github.com/bitcoin/bitcoin/blob/cf5bb048e80d4cde8828787b266b7f5f2e3b6d7b/=
src/node/miner.cpp#L310-L320</a></div></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>

--00000000000037ab2605d6d48a18--