Package-aware fee estimation

darosior commented at 2:23 pm on September 23, 2021: member

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 A with a feerate of 1sat/vb is confirmed because it was CPFP’d by a child transaction B with a feerate of 20sat/vb it will happily fill its 1ksat/kvb bucket with a success confirmation. Note that B isn’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’s processBlock. 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).

laanwj added the label Mempool on Sep 23, 2021

darosior commented at 5:03 pm on September 23, 2021: member

CI failure seems completely unrelated (feature_asmap failure on a Addrman log line figuring 3 instead of 2). Here is the log trace, “just in case”.

 02021-09-23T14:53:38.217000Z TestFramework (INFO): Initializing test directory /tmp/cirrus-ci-build/ci/scratch/test_runner/test_runner_₿_🏃_20210923_145026/feature_asmap_26
 12021-09-23T14:53:39.000000Z TestFramework (INFO): Test bitcoind with no -asmap arg passed
 22021-09-23T14:53:39.442000Z TestFramework (INFO): Test bitcoind -asmap=<absolute path>
 32021-09-23T14:53:40.286000Z TestFramework (INFO): Test bitcoind -asmap=<relative path>
 42021-09-23T14:53:40.859000Z TestFramework (INFO): Test bitcoind -asmap (using default map file)
 52021-09-23T14:53:41.404000Z TestFramework (INFO): Test bitcoind -asmap= (using default map file)
 62021-09-23T14:53:42.007000Z TestFramework (INFO): Test bitcoind -asmap restart with addrman containing new and tried entries
 72021-09-23T14:55:03.894000Z TestFramework (ERROR): Assertion failed
 8Traceback (most recent call last):
 9  File "/tmp/cirrus-ci-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/test/functional/test_framework/test_framework.py", line 131, in main
10    self.run_test()
11  File "/tmp/cirrus-ci-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/test/functional/feature_asmap.py", line 124, in run_test
12    self.test_asmap_interaction_with_addrman_containing_entries()
13  File "/tmp/cirrus-ci-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/test/functional/feature_asmap.py", line 96, in test_asmap_interaction_with_addrman_containing_entries
14    self.node.getnodeaddresses()  # getnodeaddresses re-runs the addrman checks
15  File "/usr/lib/python3.6/contextlib.py", line 88, in __exit__
16    next(self.gen)
17  File "/tmp/cirrus-ci-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/test/functional/test_framework/test_node.py", line 400, in assert_debug_log
18    self._raise_assertion_error('Expected messages "{}" does not partially match log:\n\n{}\n\n'.format(str(expected_msgs), print_log))
19  File "/tmp/cirrus-ci-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/test/functional/test_framework/test_node.py", line 166, in _raise_assertion_error
20    raise AssertionError(self._node_msg(msg))
21AssertionError: [node 0] Expected messages "['Addrman checks started: new 2, tried 2, total 4', 'Addrman checks completed successfully']" does not partially match log:
22 - 2021-09-23T14:53:43.886617Z [http] [httpserver.cpp:237] [http_request_cb] Received a POST request for / from 127.0.0.1:52652
23 - 2021-09-23T14:53:43.886733Z [httpworker.3] [rpc/request.cpp:174] [parse] ThreadRPCServer method=getnodeaddresses user=__cookie__
24 - 2021-09-23T14:53:43.886809Z [httpworker.3] [addrman.cpp:770] [ForceCheckAddrman] Addrman checks started: new 3, tried 1, total 4
25 - 2021-09-23T14:53:43.886870Z [httpworker.3] [addrman.cpp:48] [GetTriedBucket] IP 101.0.0.0 mapped to AS1 belongs to tried bucket 113
26 - 2021-09-23T14:53:43.886980Z [httpworker.3] [addrman.cpp:850] [ForceCheckAddrman] Addrman checks completed successfully
27 - 2021-09-23T14:53:43.886991Z [httpworker.3] [addrman.cpp:770] [ForceCheckAddrman] Addrman checks started: new 3, tried 1, total 4
28 - 2021-09-23T14:53:43.887016Z [httpworker.3] [addrman.cpp:48] [GetTriedBucket] IP 101.0.0.0 mapped to AS1 belongs to tried bucket 113
29 - 2021-09-23T14:53:43.887102Z [httpworker.3] [addrman.cpp:850] [ForceCheckAddrman] Addrman checks completed successfully
30 - 2021-09-23T14:54:28.662861Z [scheduler] [net.h:865] [StartExtraBlockRelayPeers] net: enabling extra block-relay-only peers
31 - 2021-09-23T14:54:43.321822Z [scheduler] [random.cpp:523] [SeedPeriodic] Feeding 33048 bytes of dynamic environment data into RNG

darosior force-pushed on Sep 23, 2021

DrahtBot commented at 10:15 pm on September 23, 2021: contributor

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#23075 (refactoring: Fee estimation functional test cleanups by darosior)
#22919 (fees: skip pointless fee parameter calculation during IBD by RohitRanjangit)
#22722 (rpc: update estimatesmartfee to return max of CBlockPolicyEstimator::estimateSmartFee, mempoolMinFee and minRelayTxFee by pranabp-bit)
#22539 (Re-include RBF replacement txs in fee estimation by darosior)
#22014 (refactor: Make m_cs_fee_estimator non-recursive by hebasto)
#17786 (refactor: Nuke policy/fees->mempool circular dependencies by hebasto)

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.

fanquake requested review from glozow on Sep 24, 2021

instagibbs commented at 3:11 am on September 24, 2021: member

concept ACK

darosior force-pushed on Sep 24, 2021

darosior commented at 9:58 am on September 24, 2021: member

Removed the commit asserting blocksToConfirm > 0, it would cause more issues with fuzzing targets than i want to deal with in this PR :)

glozow commented at 2:01 pm on September 24, 2021: member

Concept ACK, planning to review but as I have very little background on the fee estimator it may take me a bit of time :)

darosior commented at 3:54 pm on September 24, 2021: member

Unrelated CI error: Windows socket error (the use of UNIX-only os.killpg was just a symptom, not the cause)

 02021-09-24T10:29:15.111000Z TestFramework (ERROR): Unexpected exception caught during testing 
 1                                   Traceback (most recent call last):
 2                                     File "C:\Users\ContainerAdministrator\AppData\Local\Temp\cirrus-ci-build\test\functional\test_framework\test_framework.py", line 131, in main
 3                                       self.run_test()
 4                                     File "C:\Users\ContainerAdministrator\AppData\Local\Temp\cirrus-ci-build\test\functional\feature_taproot.py", line 1465, in run_test
 5                                       self.test_spenders(self.nodes[1], spenders_taproot_active(), input_counts=[1, 2, 2, 2, 2, 3])
 6                                     File "C:\Users\ContainerAdministrator\AppData\Local\Temp\cirrus-ci-build\test\functional\feature_taproot.py", line 1451, in test_spenders
 7                                       self.block_submit(node, [tx], msg, witness=True, accept=fail_input is None, cb_pubkey=cb_pubkey, fees=fee, sigops_weight=sigops_weight, err_msg=expected_fail_msg)
 8                                     File "C:\Users\ContainerAdministrator\AppData\Local\Temp\cirrus-ci-build\test\functional\feature_taproot.py", line 1244, in block_submit
 9                                       block_response = node.submitblock(block.serialize().hex())
10                                     File "C:\Users\ContainerAdministrator\AppData\Local\Temp\cirrus-ci-build\test\functional\test_framework\coverage.py", line 49, in __call__
11                                       return_val = self.auth_service_proxy_instance.__call__(*args, **kwargs)
12                                     File "C:\Users\ContainerAdministrator\AppData\Local\Temp\cirrus-ci-build\test\functional\test_framework\authproxy.py", line 144, in __call__
13                                       response, status = self._request('POST', self.__url.path, postdata.encode('utf-8'))
14                                     File "C:\Users\ContainerAdministrator\AppData\Local\Temp\cirrus-ci-build\test\functional\test_framework\authproxy.py", line 107, in _request
15                                       self.__conn.request(method, path, postdata, headers)
16                                     File "C:\Python39\lib\http\client.py", line 1257, in request
17                                       self._send_request(method, url, body, headers, encode_chunked)
18                                     File "C:\Python39\lib\http\client.py", line 1303, in _send_request
19                                       self.endheaders(body, encode_chunked=encode_chunked)
20                                     File "C:\Python39\lib\http\client.py", line 1252, in endheaders
21                                       self._send_output(message_body, encode_chunked=encode_chunked)
22                                     File "C:\Python39\lib\http\client.py", line 1012, in _send_output
23                                       self.send(msg)
24                                     File "C:\Python39\lib\http\client.py", line 952, in send
25                                       self.connect()
26                                     File "C:\Python39\lib\http\client.py", line 923, in connect
27                                       self.sock = self._create_connection(
28                                     File "C:\Python39\lib\socket.py", line 843, in create_connection
29                                       raise err
30                                     File "C:\Python39\lib\socket.py", line 831, in create_connection
31                                       sock.connect(sa)
32                                   OSError: [WinError 10048] Only one usage of each socket address (protocol/network address/port) is normally permitted

policy/fees: make processBlockTx a procedure

We'll need to check if the tx is tracked in the caller, processBlock.

Signed-off-by: Antoine Poinsot <darosior@protonmail.com>

50b5506515

policy/fee: pass the feerate to processBlockTx

Signed-off-by: Antoine Poinsot <darosior@protonmail.com>

467377413c

txmempool: give to fee estimator a set of references, not a vector of 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>

8754592e36

policy: package-aware block policy estimator

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 c82a4e9a63a28fc8c482c7c8e5b7bfcc51a6805a.

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>

cb48d4569e

qa: split run_test into smaller parts

Let's not have run_test get into a giant function as we add more tests

Signed-off-by: Antoine Poinsot <darosior@protonmail.com>

bc6b0f9db3

qa: test fee estimation handling of CPFP

Signed-off-by: Antoine Poinsot <darosior@protonmail.com>

18399e5fdc

darosior force-pushed on Sep 25, 2021

naumenkogs commented at 7:00 am on September 27, 2021: member

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.

darosior commented at 7:06 am on September 27, 2021: member

I don’t think this can degrade estimation in any case, it should be a strict improvement (/fix?).

For example, if someone RBFs their package with 1 tx.

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).

in src/policy/fees.cpp:585 in 18399e5fdc

587-
588     // How many blocks did it take for miners to include this transaction?
589     // blocksToConfirm is 1-based, so a transaction included in the earliest
590     // possible block has confirmation count of 1
591-    int blocksToConfirm = nBlockHeight - entry->GetHeight();
592+    int blocksToConfirm = nBlockHeight - entry.GetHeight();

glozow commented at 2:44 pm on September 27, 2021:

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.

in src/policy/fees.h:13 in 18399e5fdc

 9@@ -10,6 +10,7 @@
10 #include <uint256.h>
11 #include <random.h>
12 #include <sync.h>
13+#include <txmempool.h>

glozow commented at 3:29 pm on September 27, 2021:

You can remove the txmempool forward declarations below if including the header.

glozow commented at 3:34 pm on September 27, 2021: member

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.

darosior commented at 8:20 am on September 28, 2021: member

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).

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!

DrahtBot commented at 10:12 pm on September 28, 2021: contributor

🐙 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”.

DrahtBot added the label Needs rebase on Sep 28, 2021

MarcoFalke referenced this in commit 799fd7a488 on Jan 6, 2022

DrahtBot commented at 10:49 am on February 22, 2022: contributor

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.

darosior commented at 11:13 am on February 22, 2022: member

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, or unsubscribe. Triage notifications on the go with GitHub Mobile for iOS or Android. You are receiving this because you authored the thread.Message ID: @.***>

darosior commented at 1:56 pm on June 10, 2022: member

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.

darosior closed this on Jun 10, 2022

darosior commented at 2:05 pm on June 10, 2022: member

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.

MarcoFalke added the label Up for grabs on Jun 10, 2022

darosior referenced this in commit 4e10dbfe37 on Jun 15, 2022

darosior referenced this in commit 5485acfe88 on Jun 22, 2022

darosior referenced this in commit f5eff0e2ce on Apr 3, 2023

bitcoin locked this on Jun 10, 2023

Package-aware fee estimation #23074

Conflicts