fee: Round up fee calculation to avoid a lower than expected feerate #22949

achow101 · 2021-09-11T00:33:10Z

When calculating the fee for a feerate, it is possible that the final calculation will have fractional satoshis. Currently those are ignored via truncation which results in the absolute fee being rounded down. Rounding down is problematic because it results in a feerate that is slightly lower than the feerate represented by the CFeeRate object. A slightly lower feerate particularly causes issues for coin selection as it can trigger an assertion error. To avoid potentially underpaying the feerate (and the assertion), always round up the calculated fee.

A test is added for the assertion, along with a comment explaining what happens.

It is unlikely that a user can trigger this as it requires a very specific set of rounding errors to occur as well as the transaction not needing any change and being right on the lower bound of the exact match window. However I was able to trigger the assertion while running coin selection simulations, albeit after thousands of transactions and with some weird feerates.

darosior

Modifying CFeeRate::GetFee is a policy change. Increasing its return value (for some input) is potentially a policy rule tightening which may have security implications for applications with pre-signed transactions.

On the top of my head, i don't know of of an application for which it would be fatal. But could we instead go the safer path of containing the roundup in the wallet code rather than modifying CFeeRate::GetFee?

achow101 · 2021-09-12T00:01:15Z

It seems odd to me that the wallet and policy should have different fee calculation results for the same transaction.

In terms of pre-signed transactions, what security implications do you imagine? I don't think it is possible for this to cause a transaction's feerate to fall below the default minimum relay fee because the result of the fee calculation at the minimum relay fee is always an integer since the minimum relay fee is an integer. I believe the same is true for the incremental relay fee and how that calculation works.

darosior · 2021-09-12T14:12:15Z

I believe the same is true for the incremental relay fee and how that calculation works.

I don't think it's true in all cases. Take clawback tx A with fee such as it would be rounded up after this PR, not before. The application wants to replace it with clawback tx B with fee equal to A's fee + incremental relay fee such as it would not be rounded up.
Before this PR tx B would be accepted, after it would be refused.

Of course it'd be reckless for such an application to not take some leeway in addition to the incremental fee here, but still this PR would be a behaviour change for this edge case.

achow101 · 2021-09-12T16:45:28Z

I don't think it's true in all cases. Take clawback tx A with fee such as it would be rounded up after this PR, not before. The application wants to replace it with clawback tx B with fee equal to A's fee + incremental relay fee such as it would not be rounded up.
Before this PR tx B would be accepted, after it would be refused.

How so? Can you provide a example? I can't think of how that would happen. CFeeRate::GetFee is never called on the original feerate in validation, and the calculation of a feerate for a transaction is not changed by this PR.

Consider the example I give in the test: tx A is a 1-in-1-out 110 vbyte tx that pays a feerate of 1.85 sat/vbyte for an absolute fee if 203.5 sats. With rounding down, A will pay 203 sats. We replace this with tx B where the only thing different is the output, but it is of the same type so the size remains the same. Paying the incremental relay fee should be enough for B to replace A. The incremental feerate is 1 sat/vbyte, so regardless of rounding, it is always 110 sats. So B pays 313 sats.

When validating whether B is allowed to replace A, it needs to pass two fee related checks: PaysMoreThanConflicts (called here) and PaysForRBF (called here). PaysMoreThanConflicts computes the feerates for A and B and just checks that B's feerate is greater than A's. The rounding of computing the feerate given the fee paid and size did not change, so both before and after this PR, the calculation for A is 203 * 1000 / 110 = 1845. The calculation for B is 313 * 1000 / 110 = 2845. B's feerate is greater than A's, so this check passes, both before and after this PR. PaysForRBF checks that the fees for B is greater than A. Then it checks that the difference is not less than the incremental relay fee. Because the incremental relay fee is an integer, the calculation before and after this PR is the same - 110 sats.

At no point in this checking process is the original feerate of 1.85 sats/vbyte used because validation does not know that was the original targeted feerate. The only times where validation calls CFeeRate::GetFee is to calculate the fee at the minimum relay feerate and the incremental relay feerate, both of which have integers as their default, so their calculations do not change. So I don't see how this change would have any effect on whether transactions are accepted.

darosior · 2021-09-15T07:36:16Z

You are right. I also can't think of how this change would be a policy rule tightening.

jonatack

Tentative concept ACK after looking at the callers of GetFee() (not GetFeePerK, which should be a pass-through). The new functional tests fail where expected on master.

$ test/functional/rpc_fundrawtransaction.py 

  File "/home/jon/projects/bitcoin/bitcoin/test/functional/rpc_fundrawtransaction.py", line 1055, in test_feerate_rounding
    assert_raises_rpc_error(-4, "Insufficient funds", w.fundrawtransaction, rawtx, {"fee_rate": 1.85})
AssertionError: Unexpected stderr bitcoind: wallet/spend.cpp:814: bool CreateTransactionInternal(CWallet &, const std::vector<CRecipient> &, CTransactionRef &, CAmount &, int &, bilingual_str &, const CCoinControl &, FeeCalculation &, bool): Assertion `coin_selection_params.m_subtract_fee_outputs || fee_needed <= change_and_fee - change_amount' failed. !=

$ test/functional/wallet_keypool.py

  File "/home/jon/projects/bitcoin/bitcoin/test/functional/wallet_keypool.py", line 184, in run_test
    assert_equal(res["fee"], Decimal("0.00009706"))
  File "/home/jon/projects/bitcoin/bitcoin/test/functional/test_framework/util.py", line 49, in assert_equal
    raise AssertionError("not(%s)" % " == ".join(str(arg) for arg in (thing1, thing2) + args))
AssertionError: not(0.00009705 == 0.00009706)

src/policy/feerate.cpp

test/functional/rpc_fundrawtransaction.py

src/policy/feerate.cpp

maflcko · 2021-09-20T14:01:19Z

You are right. I also can't think of how this change would be a policy rule tightening.

This changes policy for non-default fee rate settings. (Probably no one uses those, but wanted to mention it)

jonatack · 2021-09-20T17:20:15Z

Code review ACK d9ac0cd modulo policy considerations, per git diff 053ec2b d9ac0cd, previously checked at 053ec2b that the new functional tests fail where expected on master, changes since are a named cast, documentation, and named args in the test

ariard · 2021-09-23T00:40:20Z

I agree, I don't think this change qualifies as a policy rule tightening.

IIUC, previously we had transaction A with absolute fee 203.5 sats. Currently, it's rounded down to 203 sats. After this PR, it will be rounded up to 204 sats.

Note, I think GetFee is called in few subsystems beyond mempool acceptance and wallet. Such as for block construction (addPackageTxs) or transaction announcement selection (L4802, in src/net_processing). As the pair of transactions is equally affected, I don't think the comparison is altered. I.e if transaction A was 203.5 sats and transaction B was 204.5 sats, respectivelly rounded down to 203 sats and 204 sats, now they will be rounded up to 204 sats and 205 sats ? The comparison should hold. AFAICT, the proposed change doesn't have positive or negative impacts on transaction propagation or block building.

(Though if it's change the displayed absolute fee at the interface-level, I think a release note would be appropriate, a user could consume the now-rounded up result and do a comparison with a still-rounded down result from another software than Core in a way which is obscure to us ?)

meshcollider · 2021-09-28T23:31:13Z

This should also fix test failures like this: https://cirrus-ci.com/task/5800722060017664?logs=ci#L3900

 test  2021-09-28T17:50:42.592000Z TestFramework (ERROR): Assertion failed 
                                   Traceback (most recent call last):
                                     File "/tmp/cirrus-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/test/functional/test_framework/test_framework.py", line 131, in main
                                       self.run_test()
                                     File "/tmp/cirrus-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/test/functional/wallet_basic.py", line 500, in run_test
                                       assert_fee_amount(fee, tx_size, Decimal(fee_rate_btc_kvb))
                                     File "/tmp/cirrus-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/test/functional/test_framework/util.py", line 41, in assert_fee_amount
                                       raise AssertionError("Fee of %s BTC too low! (Should be %s BTC)" % (str(fee), str(target_fee)))
                                   AssertionError: Fee of 0.00000255 BTC too low! (Should be 0.00000256 BTC)

Otherwise, the round in assert_fee_amount will round up rather than truncate.

maflcko · 2021-10-01T08:53:15Z

Concept ACK. If someone requests a feerate of 1.23 sat/vB, with a tx vsize of 208, it shouldn't result in 255 fee, but 256. Otherwise, the feerate will be 1.2259... sat/vB.

I think you'll also need to adjust the test, otherwise they won't check this:

test/functional/test_framework/util.py:def satoshi_round(amount):

achow101 · 2021-10-01T17:40:39Z

@MarcoFalke Not quite sure what you want me to adjust.

satoshi_round doesn't need any changes afaict.

maflcko · 2021-10-02T06:29:54Z

assert_fee_amount, which uses satoshi_round is used in the tests to replicate GetFee and check that it gives the same result.

You are changing GetFee (in my previous example #22949 (comment)) to return 256 instead of 255, so the tests also needs to be adjusted to do the same.

maflcko · 2021-10-06T17:20:46Z

If you don't want to change satoshi_round (because it is used by more than just assert_fee_amount), you can first inline it into assert_fee_amount and then fix it.

When calculating the fee for a given tx size from a fee rate, we should always round up to the next satoshi. Otherwise, if we round down (via truncation), the calculated fee may result in a fee with a feerate slightly less than targeted. This is particularly important for coin selection as a slightly lower feerate than expected can result in a variety of issues.

When calculating a txs absolute fee, if the fee is rounded down to the nearest satoshi, it is possible for the coin selection algorithms to undercalculate the fee needed. This can lead to an assertion error in some situations. One such scenario is added to rpc_fundrawtransaction.py.

meshcollider

utACK 80dc829

…han exp…

When calculating the fee for a given tx size from a fee rate, we should always round up to the next satoshi. Otherwise, if we round down (via truncation), the calculated fee may result in a fee with a feerate slightly less than targeted. This is particularly important for coin selection as a slightly lower feerate than expected can result in a variety of issues. Github-Pull: bitcoin#22949 Rebased-From: 0fbaef9

When calculating a txs absolute fee, if the fee is rounded down to the nearest satoshi, it is possible for the coin selection algorithms to undercalculate the fee needed. This can lead to an assertion error in some situations. One such scenario is added to rpc_fundrawtransaction.py. Github-Pull: bitcoin#22949 Rebased-From: ce2cc44

Because of floating point precision issues, not all of the rounding done is always correct. To fix this, the fee calculation for assert_fee_amount is changed to better reflect how CFeeRate::GetFee does it. First the feerate is converted to an int representing sat/kvb. Then this is multiplied by the transaction size, divivided by 1000, and rounded up to the nearest sat. The result is then converted back to BTC (divided by 1e8) and then rounded down to the nearest sat to avoid precision errors. Github-Pull: bitcoin#22949 Rebased-From: 80dc829

When calculating the fee for a given tx size from a fee rate, we should always round up to the next satoshi. Otherwise, if we round down (via truncation), the calculated fee may result in a fee with a feerate slightly less than targeted. This is particularly important for coin selection as a slightly lower feerate than expected can result in a variety of issues. Github-Pull: bitcoin#22949 Rebased-From: 0fbaef9

When calculating a txs absolute fee, if the fee is rounded down to the nearest satoshi, it is possible for the coin selection algorithms to undercalculate the fee needed. This can lead to an assertion error in some situations. One such scenario is added to rpc_fundrawtransaction.py. Github-Pull: bitcoin#22949 Rebased-From: ce2cc44

Because of floating point precision issues, not all of the rounding done is always correct. To fix this, the fee calculation for assert_fee_amount is changed to better reflect how CFeeRate::GetFee does it. First the feerate is converted to an int representing sat/kvb. Then this is multiplied by the transaction size, divivided by 1000, and rounded up to the nearest sat. The result is then converted back to BTC (divided by 1e8) and then rounded down to the nearest sat to avoid precision errors. Github-Pull: bitcoin#22949 Rebased-From: 80dc829

fanquake · 2021-11-25T07:36:51Z

Added to #23276 for backport to 22.x

When calculating the fee for a given tx size from a fee rate, we should always round up to the next satoshi. Otherwise, if we round down (via truncation), the calculated fee may result in a fee with a feerate slightly less than targeted. This is particularly important for coin selection as a slightly lower feerate than expected can result in a variety of issues. Github-Pull: bitcoin#22949 Rebased-From: 0fbaef9

When calculating a txs absolute fee, if the fee is rounded down to the nearest satoshi, it is possible for the coin selection algorithms to undercalculate the fee needed. This can lead to an assertion error in some situations. One such scenario is added to rpc_fundrawtransaction.py. Github-Pull: bitcoin#22949 Rebased-From: ce2cc44

Because of floating point precision issues, not all of the rounding done is always correct. To fix this, the fee calculation for assert_fee_amount is changed to better reflect how CFeeRate::GetFee does it. First the feerate is converted to an int representing sat/kvb. Then this is multiplied by the transaction size, divivided by 1000, and rounded up to the nearest sat. The result is then converted back to BTC (divided by 1e8) and then rounded down to the nearest sat to avoid precision errors. Github-Pull: bitcoin#22949 Rebased-From: 80dc829

When calculating the fee for a given tx size from a fee rate, we should always round up to the next satoshi. Otherwise, if we round down (via truncation), the calculated fee may result in a fee with a feerate slightly less than targeted. This is particularly important for coin selection as a slightly lower feerate than expected can result in a variety of issues. Github-Pull: bitcoin#22949 Rebased-From: 0fbaef9

When calculating a txs absolute fee, if the fee is rounded down to the nearest satoshi, it is possible for the coin selection algorithms to undercalculate the fee needed. This can lead to an assertion error in some situations. One such scenario is added to rpc_fundrawtransaction.py. Github-Pull: bitcoin#22949 Rebased-From: ce2cc44

Because of floating point precision issues, not all of the rounding done is always correct. To fix this, the fee calculation for assert_fee_amount is changed to better reflect how CFeeRate::GetFee does it. First the feerate is converted to an int representing sat/kvb. Then this is multiplied by the transaction size, divivided by 1000, and rounded up to the nearest sat. The result is then converted back to BTC (divided by 1e8) and then rounded down to the nearest sat to avoid precision errors. Github-Pull: bitcoin#22949 Rebased-From: 80dc829

269553f test: Call ceildiv helper with integer (Martin Zumsande) 2f60fc6 ci: Replace soon EOL hirsute with jammy (MarcoFalke) 801b0f0 build: patch qt to explicitly define previously implicit header include (Kittywhiskers Van Gogh) c768bfa tests: Calculate fees more similarly to CFeeRate::GetFee (Andrew Chow) f66bc42 tests: Test for assertion when feerate is rounded down (Andrew Chow) bd7e08e fees: Always round up fee calculated from a feerate (Andrew Chow) 227ae65 wallet: fix segfault by avoiding invalid default-ctored `external_spk_managers` entry (Sebastian Falbesoner) 282863a refactor: include a missing <limits> header in fs.cpp (Joan Karadimov) 7febe4f consensus: don't call GetBlockPos in ReadBlockFromDisk without lock (Jon Atack) c671c6f the result of CWallet::IsHDEnabled() was initialized with true. (Saibato) a5a1538 build, qt: Fix typo in QtInputSupport check (Hennadii Stepanov) c95b188 system: skip trying to set the locale on NetBSD (fanquake) c1cdedd guix: Fix powerpc64(le) dynamic linker name (Carl Dong) 92d44ff doc: Add 23061 release notes (MarcoFalke) db76db7 Fix (inverse) meaning of -persistmempool (MarcoFalke) 85c78e0 build: Restrict check for CRC32C intrinsic to aarch64 (W. J. van der Laan) Pull request description: Collecting backports for the 22.1 release. Currently: * #23045 * #23061 * #23148 * #22390 * #22820 * #22781 * #22895 * #23335 * #23333 * #22949 * #23580 * #23504 * #24239 ACKs for top commit: achow101: ACK 269553f Tree-SHA512: b3a57ea241be7a83488eeb032276f4cf82a0987aada906a82f94a20c4acf9f2397708249dcecbe1c7575e70d09c60b835233d4718af4013c7bc58896c618274c

maflcko · 2022-03-02T12:31:40Z

src/test/transaction_tests.cpp

    CheckIsNotStandard(t, "dust");
    // not dust:
-    t.vout[0].nValue = 673;
+    t.vout[0].nValue = 674;


Looks like this changes behaviour between releases if the user changed the default dust rate.

Same for -blockmintxfee, and -incrementalRelayFee, sendrawtransaction/testmempoolaccept feerate RPC arg, checks in CheckFeeRate.

…g correctly Caution: This implementation is for a post-bitcoin#22949 codebase

achow101 force-pushed the feerate-round branch 2 times, most recently from 9f2fa20 to 387ed1b Compare September 11, 2021 00:35

fanquake added the TX fees and policy label Sep 11, 2021

achow101 force-pushed the feerate-round branch from 387ed1b to 053ec2b Compare September 11, 2021 01:13

bitcoin deleted a comment Sep 11, 2021

darosior reviewed Sep 11, 2021

View reviewed changes

bitcoin deleted a comment Sep 11, 2021

bitcoin deleted a comment from ccr781 Sep 15, 2021

jonatack reviewed Sep 17, 2021

View reviewed changes

src/policy/feerate.cpp Outdated Show resolved Hide resolved

test/functional/rpc_fundrawtransaction.py Outdated Show resolved Hide resolved

maflcko reviewed Sep 20, 2021

View reviewed changes

src/policy/feerate.cpp Show resolved Hide resolved

maflcko added the Wallet label Sep 20, 2021

achow101 force-pushed the feerate-round branch from 053ec2b to d9ac0cd Compare September 20, 2021 16:25

meshcollider mentioned this pull request Sep 30, 2021

test: Fix intermitent failure in wallet_basic.py #23141

Closed

maflcko mentioned this pull request Oct 1, 2021

test: update fee rate assertion helper in the functional test framework #23136

Merged

maflcko mentioned this pull request Oct 7, 2021

test: Replace satoshi_round with int() or Decimal() #23210

Merged

achow101 added 2 commits October 8, 2021 13:53

fanquake added the Needs backport (22.x) label Oct 26, 2021

S3RK mentioned this pull request Nov 1, 2021

Optimize coin selection by dropping BnB upper limit #23367

Closed

meshcollider reviewed Nov 4, 2021

View reviewed changes

meshcollider merged commit 24abd83 into bitcoin:master Nov 4, 2021

sidhujag pushed a commit to syscoin/syscoin that referenced this pull request Nov 4, 2021

Merge bitcoin#22949: fee: Round up fee calculation to avoid a lower t…

0788a8c

…han exp…

bitcoin deleted a comment Nov 12, 2021

lukaszsamson mentioned this pull request Nov 19, 2021

[22.x] Backports for 22.x #23276

Merged

fanquake removed the Needs backport (22.x) label Nov 25, 2021

ryanofsky mentioned this pull request Feb 4, 2022

test: fix ceildiv division by using integers #24239

Merged

maflcko reviewed Mar 2, 2022

View reviewed changes

SmartArray pushed a commit to SmartArray/digibyte that referenced this pull request Apr 6, 2022

fix: rounding issues: bitcoin/bitcoin#22949

344e306

SmartArray pushed a commit to SmartArray/digibyte that referenced this pull request Apr 6, 2022

fix: rounding issues: bitcoin/bitcoin#22949

2d061fd

luke-jr added a commit to luke-jr/bitcoin that referenced this pull request May 21, 2022

Bugfix: QA: Ensure mempool_fee_histogram can adapt to feerate roundin…

12ff15c

…g correctly Caution: This implementation is for a post-bitcoin#22949 codebase

reddink mentioned this pull request May 26, 2022

[4.22.x] Backports for 4.22.x reddcoin-project/reddcoin#20

Merged

fanquake mentioned this pull request Oct 3, 2022

wallet/spend.cpp assertion error #26232

Closed

bitcoin locked and limited conversation to collaborators Mar 2, 2023

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

fee: Round up fee calculation to avoid a lower than expected feerate #22949

fee: Round up fee calculation to avoid a lower than expected feerate #22949

achow101 commented Sep 11, 2021 •

edited

Loading

darosior left a comment

achow101 commented Sep 12, 2021

darosior commented Sep 12, 2021

achow101 commented Sep 12, 2021

darosior commented Sep 15, 2021

jonatack left a comment

maflcko commented Sep 20, 2021 •

edited

Loading

jonatack commented Sep 20, 2021

ariard commented Sep 23, 2021 •

edited

Loading

meshcollider commented Sep 28, 2021 •

edited

Loading

maflcko commented Oct 1, 2021

achow101 commented Oct 1, 2021

maflcko commented Oct 2, 2021

maflcko commented Oct 6, 2021

meshcollider left a comment

fanquake commented Nov 25, 2021

maflcko Mar 2, 2022

maflcko Mar 2, 2022

fee: Round up fee calculation to avoid a lower than expected feerate #22949

fee: Round up fee calculation to avoid a lower than expected feerate #22949

Conversation

achow101 commented Sep 11, 2021 • edited Loading

darosior left a comment

Choose a reason for hiding this comment

achow101 commented Sep 12, 2021

darosior commented Sep 12, 2021

achow101 commented Sep 12, 2021

darosior commented Sep 15, 2021

jonatack left a comment

Choose a reason for hiding this comment

maflcko commented Sep 20, 2021 • edited Loading

jonatack commented Sep 20, 2021

ariard commented Sep 23, 2021 • edited Loading

meshcollider commented Sep 28, 2021 • edited Loading

maflcko commented Oct 1, 2021

achow101 commented Oct 1, 2021

maflcko commented Oct 2, 2021

maflcko commented Oct 6, 2021

meshcollider left a comment

Choose a reason for hiding this comment

fanquake commented Nov 25, 2021

maflcko Mar 2, 2022

Choose a reason for hiding this comment

maflcko Mar 2, 2022

Choose a reason for hiding this comment

achow101 commented Sep 11, 2021 •

edited

Loading

maflcko commented Sep 20, 2021 •

edited

Loading

ariard commented Sep 23, 2021 •

edited

Loading

meshcollider commented Sep 28, 2021 •

edited

Loading