Package-aware fee estimation #23074
Package-aware fee estimation #23074
Conversation
|
CI failure seems completely unrelated (
Random `feature_asmap` failure logs |
5448e48 to
e3705b9
Compare
|
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers. ConflictsReviewers, this pull request conflicts with the following ones:
If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first. |
|
concept ACK |
e3705b9 to
4aac9cc
Compare
|
Removed the commit asserting |
|
Concept ACK, planning to review but as I have very little background on the fee estimator it may take me a bit of time :) |
|
Unrelated CI error: Windows socket error (the use of UNIX-only |
We'll need to check if the tx is tracked in the caller, processBlock. Signed-off-by: Antoine Poinsot <darosior@protonmail.com>
Signed-off-by: Antoine Poinsot <darosior@protonmail.com>
… pointer We'll need to lookup in the set whether a descendant of an entry was actually confirmed. Signed-off-by: Antoine Poinsot <darosior@protonmail.com>
The fee estimation logic would previously assume a miner was incentivized to include a given transaction only by this transaction's fee. This isn't true anymore since c82a4e9. CPFP is actively used on the network today [FIXME provide numbers], and the usage can be expected to increase a lot with the adoption of CPFP-based fee bumping for L2 protocols such as the Lightning Network (see the anchor outputs proposal). The more CPFP is used, the more the fee estimator will *underestimate* the fee required to get into a target number of blocks. This may become at best a nuisance for onchain transaction users and at worst a security issue for protocol requiring timely confirmation of pre-sign transactions. Signed-off-by: Antoine Poinsot <darosior@protonmail.com>
Let's not have run_test get into a giant function as we add more tests Signed-off-by: Antoine Poinsot <darosior@protonmail.com>
Signed-off-by: Antoine Poinsot <darosior@protonmail.com>
4aac9cc to
18399e5
Compare
|
Concept ACK. Seems like a well-justified improvement. Do you think this PR could degrade the prediction performance in certain cases? For example, if someone RBFs their package with 1 tx. I actually think we get an improvement here in that case, but yeah, that's just an example. |
|
I don't think this can degrade estimation in any case, it should be a strict improvement (/fix?).
For now the replacement transaction would not be considered. Assuming we have both #22539 and this PR this would give a much more correct estimation: taking the entire package feerate instead of ignoring it (#22539), or wrongly assuming the feerate of the parent transaction alone was enough to get it confirmed (this PR). |
There was a problem hiding this comment.
IIUC, our fee estimator is tracking feerate + time to confirm so that we can estimate the probability of a transaction confirming within n blocks when offered at feerate f. I definitely agree it's incorrect to use base feerates, as CPFP transactions cause us underestimate feerates. So, again, strong concept ACK.
However, I'm not sure about the approach. Looking at a block transaction and its descendants can tell us the feerate at which it was mined, but not the feerate it was offered at. We wouldn't know when it was fee-bumped and how long it took to mine after the high-fee descendant(s) were broadcast (which imo is what we're actually interested in).
In our code, we essentially think of "miner attractiveness" as the ancestor feerate of a transaction (not saying this is the perfect or only way to think about it, just going off of BlockAssembler).
I also don't think it's necessarily bad to include transactions in fee estimation when they have mempool ancestors, as long as everybody's feerates are accurately accounted for.
If I might propose a different approach: for every transaction added to mempool, add it to the fee estimator by ancestor feerate (EDIT: update for the mining score of any transaction each time it changes), and update height and feerate of its ancestors' entries if it improves them. This captures our intent: the transaction is being re-offered at a higher feerate. (Same thing for RBF in #22539, which is already implemented this way - new feerate and new time).
When the transaction is included in a block, we can use blocksToConfirm = nBlockHeight - offerHeight where offerHeight is not the time it first entered the mempool, but the time it was "offered" to a miner at its best feerate.
| // How many blocks did it take for miners to include this transaction? | ||
| // blocksToConfirm is 1-based, so a transaction included in the earliest | ||
| // possible block has confirmation count of 1 | ||
| int blocksToConfirm = nBlockHeight - entry->GetHeight(); | ||
| int blocksToConfirm = nBlockHeight - entry.GetHeight(); |
There was a problem hiding this comment.
I think this approach may overestimate the number of blocks it takes to a tx at a certain feerate to confirm: if a transaction is first accepted at time t with a feerate of 1sat/vB, sits in the mempool for a long time, and then is fee-bumped to 10sat/vB and included in a block at time t+500, this will record that the transaction had a feerate of 10sat/vB but took 500 blocks to confirm. That would be inaccurate, since it was 1sat/vB for most of that time.
| @@ -10,6 +10,7 @@ | |||
| #include <uint256.h> | |||
| #include <random.h> | |||
| #include <sync.h> | |||
| #include <txmempool.h> | |||
There was a problem hiding this comment.
You can remove the txmempool forward declarations below if including the header.
Right, this would be the accurate approach. I chose to go with the current hack because i found the "right approach" would make it really hard to think about edge cases. Now -and given the overestimation would not be fixed without further hacks- i can't give any good argument for not tracking by ancestor. Will give this approach a go, hopefully in the coming weeks! |
|
🐙 This pull request conflicts with the target branch and needs rebase. Want to unsubscribe from rebase notifications on this pull request? Just convert this pull request to a "draft". |
60ae116 qa: replace assert with test framework assertion helpers in fee estimation test (Antoine Poinsot) e502139 qa: fee estimation with RBF test cleanups (Antoine Poinsot) 15f5fd6 qa: don't mine non standard txs in fee estimation test (Antoine Poinsot) eae52dd qa: pass scriptsig directly to txins constructor in fee estimation test (Antoine Poinsot) 1fc0315 qa: split coins in a single tx in fee estimation test (Antoine Poinsot) cc204b8 qa: use a single p2sh script in fee estimation test (Antoine Poinsot) 19dd91a qa: remove a redundant condition in fee estimation test (Antoine Poinsot) Pull request description: Some cleanups that i noticed would be desirable while working on #23074 and #22539, which are intentionally not based on it. Mainly simplifications and a slight speedup. - Use a single tx to create the `2**9` coins instead of creating `2**8` 2-outputs transactions - Use a single P2SH script - Avoid the use of non-standard transactions - Misc style nits (happy to take more) ACKs for top commit: pg156: I ACK all commits up to 60ae116 (except 1fc0315, where I have a question more for my own learning than actually questioning the PR). I built and ran the test successfully. I agree after the changes, the behavior is kept the same and the code is shorter and easier to reason. glozow: utACK 60ae116 Tree-SHA512: 57ae2294eb68961ced30f32448c4a530ba1cdee17881594eecb97e1b9ba8927d58c25022b847eb07fb67d676bf436108c416c2f2174864d258fcca5b528b8bbd
There hasn't been much activity lately and the patch still needs rebase. What is the status here?
|
|
Hello Drahbot. I have not forgotten about this PR and i plan to rebase it asap.
…------- Original Message -------
Le mardi 22 février 2022 à 11:49 AM, DrahtBot ***@***.***> a écrit :
There hasn't been much activity lately and the patch still needs rebase. What is the status here?
- Is it still relevant? ➡️ Please solve the conflicts to make it ready for review and to ensure the CI passes.
- Is it no longer relevant? ➡️ Please close.
- Did the author lose interest or time to work on this? ➡️ Please close it and mark it 'Up for grabs' with the label, so that it can be picked up in the future.
—
Reply to this email directly, [view it on GitHub](#23074 (comment)), or [unsubscribe](https://github.com/notifications/unsubscribe-auth/AFLK3F2C3KDHGU2TSJ6A573U4NS3HANCNFSM5ET2B5MQ).
Triage notifications on the go with GitHub Mobile for [iOS](https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675) or [Android](https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub).
You are receiving this because you authored the thread.Message ID: ***@***.***>
|
|
Finally got back to give this some thought, and i'm going to close it for now. It sticked around for too long and unfortunately i don't expect to be able to invest the necessary time anytime soon. (It's more complicated than just tracking per ancestor feerate.) I'm still happy to discuss different approaches if people are still interested. I still believe it's very much needed. |
|
One thing we could do at least is to ignore transactions with child. This would reduce our number of data points but better have less rather than wrong ones. |
The fee estimator would previously assume that a miner was only
incentivized by the fees of a transaction in isolation, completely
disregarding its descendants. For instance, upon confirmation of a
package {A, B} where A is 1sat/vb and B 20sat/vb, the fee estimator
would assume that 1sat/vb was sufficient for getting this transaction
confirmed.
This can lead to significantly underestimated fees as CPFP gets more
usage on the network. It is currently actively used by many wallets, and
will get more adoption along with L2s that rely on it for fee bumping
(for instance the Lightning Network with anchor outputs).
I previously attempted a boutique accounting of child feerates [0], but a
decent tracking of ancestor scores as new child come in and parts of
packages get confirmed will require significantly more work. In the
meantime just detect transactions that were likely confirmed because of
their descendants' feerate and don't take them into account for fee
estimation. It's not perfect but should prevent the mistake in most
cases (and for the very unlikely edge cases the current algorithm is pretty
resistent to outliers anyways).
[0] bitcoin#23074
The fee estimator would previously assume that a miner was only
incentivized by the fees of a transaction in isolation, completely
disregarding its descendants. For instance, upon confirmation of a
package {A, B} where A is 1sat/vb and B 20sat/vb, the fee estimator
would assume that 1sat/vb was sufficient for getting this transaction
confirmed.
This can lead to significantly underestimated fees as CPFP gets more
usage on the network. It is currently actively used by many wallets, and
will get more adoption along with L2s that rely on it for fee bumping
(for instance the Lightning Network with anchor outputs).
I previously attempted a boutique accounting of child feerates [0], but a
decent tracking of ancestor scores as new child come in and parts of
packages get confirmed will require significantly more work. In the
meantime just detect transactions that were likely confirmed because of
their descendants' feerate and don't take them into account for fee
estimation. It's not perfect but should prevent the mistake in most
cases (and for the very unlikely edge cases the current algorithm is pretty
resistent to outliers anyways).
[0] bitcoin#23074
The fee estimator would previously assume that a miner was only
incentivized by the fees of a transaction in isolation, completely
disregarding its descendants. For instance, upon confirmation of a
package {A, B} where A is 1sat/vb and B 20sat/vb, the fee estimator
would assume that 1sat/vb was sufficient for getting this transaction
confirmed.
This can lead to significantly underestimated fees as CPFP gets more
usage on the network. It is currently actively used by many wallets, and
will get more adoption along with L2s that rely on it for fee bumping
(for instance the Lightning Network with anchor outputs).
I previously attempted a boutique accounting of child feerates [0], but a
decent tracking of ancestor scores as new child come in and parts of
packages get confirmed will require significantly more work. In the
meantime just detect transactions that were likely confirmed because of
their descendants' feerate and don't take them into account for fee
estimation. It's not perfect but should prevent the mistake in most
cases (and for the very unlikely edge cases the current algorithm is pretty
resistent to outliers anyways).
[0] bitcoin#23074
|
Removing "Up for grabs" given #30079. cc @ismaelsadeeq. |
The block policy estimator currently assumes that a miner is incentivized to include a transaction only by its own fee. That is if a tracked transaction
Awith a feerate of1sat/vbis confirmed because it was CPFP'd by a child transactionBwith a feerate of20sat/vbit will happily fill its 1ksat/kvb bucket with a success confirmation. Note thatBisn't tracked as it has in-mempool ancestors.This is concerning as it would not only miss part of the data necessary to provide a correct (higher) estimate (as it's the case for RBF, cf #22539) but it would wrongly assume an incorrect (lower) estimate was right. It is even more concerning if we take into account that estimating a too low fee could have security implications for protocols requiring timely confirmation of transactions.
Of course, the estimation would only get worse as CPFP is increasingly used on the network. But it is actively used currently [0] on the network, many applications allow for this functionality directly [1] or indirectly [2]. And with the increasing usage of L2s such as the Lightning Network, we can expect the CPFP usage to increase even more as fee bumping methods get more common. Interestingly, with the current estimator the more anchor output-based fee bumping (shifting the fees from the parent to a child transaction) are used on the network the less the estimation will be reliable for everyone.
This PR proposes a naive implementation for accounting for child transaction(s) feerates when a parent transaction gets confirmed in
CBlockPolicyEstimator'sprocessBlock. It would fail to split the feerate if multiple parents share the same child and assign the whole package (but the other parent(s)) feerate to the first seen parent. Accurate tracking would introduce way more complexity.[0] TODO: Provide some raw data about historical usage of CPFP
[1] For instance Bluewallet, LND, Mycelium and SparrowWallet do. And Lightning implems recommend to do a CPFP if the funding transaction doesn't confirm in a timely manner until we have an upgrade of the funding protocol allow for RBF.
[2] For lots of wallets include the Bitcoin Core one during a fee spike users continue to transact using unconfirmed UTxOs with transactions of increasing feerate (and even sometimes open an issue because they hit the descendants limit).