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

achow101 commented at 0:33 am on September 11, 2021: member

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.

achow101 force-pushed on Sep 11, 2021

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

achow101 force-pushed on Sep 11, 2021

fanquake deleted a comment on Sep 11, 2021

darosior commented at 1:25 pm on September 11, 2021: member

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?

MarcoFalke deleted a comment on Sep 11, 2021

achow101 commented at 0:01 am on September 12, 2021: member

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 commented at 2:12 pm on September 12, 2021: member

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 commented at 4:45 pm on September 12, 2021: member

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 commented at 7:36 am on September 15, 2021: member

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

fanquake deleted a comment on Sep 15, 2021

in src/policy/feerate.cpp:27 in 053ec2b901 outdated

23@@ -22,7 +24,7 @@ CAmount CFeeRate::GetFee(uint32_t num_bytes) const
24 {
25     const int64_t nSize{num_bytes};
26 
27-    CAmount nFee = nSatoshisPerK * nSize / 1000;
28+    CAmount nFee = std::ceil(nSatoshisPerK * nSize / 1000.0);

jonatack commented at 10:58 am on September 17, 2021:

ee9a74d a couple of ideas

make the double-to-long conversion explicit

0    // Be explicit that we're converting from double to long (CAmount) here.
1    // We've previously had bugs creep in from silent double->int conversion.
2    CAmount nFee{static_cast<CAmount>(std::ceil(nSatoshisPerK * nSize / 1000.0))};

bypass this calculation in the frequent GetFeePerK() case

0    CAmount nFee{static_cast<CAmount>(
1            nSize == 1000 ? nSatoshisPerK : std::ceil(nSatoshisPerK * nSize / 1000.0))};

achow101 commented at 4:25 pm on September 20, 2021:

I added the explicit casting but not the bypass for now.

in test/functional/rpc_fundrawtransaction.py:1054 in 053ec2b901 outdated

1049+        # If rounding down (which is the incorrect behavior), then the calculated fee will be 125 + 77 = 202.
1050+        # If rounding up, then the calculated fee will be 126 + 78 = 204.
1051+        # In the former case, the calculated needed fee is higher than the actual fee being paid, so an assertion is reached
1052+        # To test this does not happen, we subtract 202 sats from the input value. If working correctly, this should
1053+        # fail with insufficient funds rather than bitcoind asserting.
1054+        rawtx = w.createrawtransaction([], [{self.nodes[0].getnewaddress(address_type="bech32"): 1 - 0.00000202}])

jonatack commented at 10:59 am on September 17, 2021:

053ec2b nit

0        rawtx = w.createrawtransaction(inputs=[], outputs=[{self.nodes[0].getnewaddress(address_type="bech32"): 1 - 0.00000201}])

achow101 commented at 4:25 pm on September 20, 2021:

Done

jonatack commented at 11:31 am on September 17, 2021: member

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.

0$ test/functional/rpc_fundrawtransaction.py 
1
2  File "/home/jon/projects/bitcoin/bitcoin/test/functional/rpc_fundrawtransaction.py", line 1055, in test_feerate_rounding
3    assert_raises_rpc_error(-4, "Insufficient funds", w.fundrawtransaction, rawtx, {"fee_rate": 1.85})
4AssertionError: 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. !=

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

in src/policy/feerate.cpp:24 in 053ec2b901 outdated

23@@ -22,7 +24,7 @@ CAmount CFeeRate::GetFee(uint32_t num_bytes) const
24 {

MarcoFalke commented at 1:58 pm on September 20, 2021:

Wouldn’t it make sense to rename this from GetFee to RoundFee to clarify that this is not a getter, but a calculation?

At the very least the doxygen should be updated.

achow101 commented at 4:26 pm on September 20, 2021:

Updated doxygen. I think keeping it GetFee is fine.

MarcoFalke added the label Wallet on Sep 20, 2021

MarcoFalke commented at 2:01 pm on September 20, 2021: member

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)

achow101 force-pushed on Sep 20, 2021

jonatack commented at 5:20 pm on September 20, 2021: member

Code review ACK d9ac0cdd5b7829dd45e1dab46fa349d2ce04d5cd 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 commented at 0:40 am on September 23, 2021: member

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 commented at 11:31 pm on September 28, 2021: contributor

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

0 test  2021-09-28T17:50:42.592000Z TestFramework (ERROR): Assertion failed 
1                                   Traceback (most recent call last):
2                                     File "/tmp/cirrus-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/test/functional/test_framework/test_framework.py", line 131, in main
3                                       self.run_test()
4                                     File "/tmp/cirrus-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/test/functional/wallet_basic.py", line 500, in run_test
5                                       assert_fee_amount(fee, tx_size, Decimal(fee_rate_btc_kvb))
6                                     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
7                                       raise AssertionError("Fee of %s BTC too low! (Should be %s BTC)" % (str(fee), str(target_fee)))
8                                   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.

MarcoFalke commented at 8:53 am on October 1, 2021: member

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:

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

achow101 commented at 5:40 pm on October 1, 2021: member

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

satoshi_round doesn’t need any changes afaict.

MarcoFalke commented at 6:29 am on October 2, 2021: member

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.

MarcoFalke commented at 5:20 pm on October 6, 2021: member

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.

fees: Always round up fee calculated from a feerate

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.

0fbaef9676

tests: Test for assertion when feerate is rounded down

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.

ce2cc44afd

achow101 force-pushed on Oct 8, 2021

achow101 commented at 5:58 pm on October 8, 2021: member

I added a commit which changes assert_fee_amount to round up the calculated fee.

achow101 force-pushed on Oct 8, 2021

in test/functional/test_framework/util.py:228 in 5a93378253 outdated

217@@ -218,6 +218,13 @@ def str_to_b64str(string):
218     return b64encode(string.encode('utf-8')).decode('ascii')
219 
220 
221+def get_fee(tx_size, feerate_btc_kvb):
222+    """Calculate the fee in BTC given a feerate is BTC/kvB. Reflects CFeeRate::GetFee"""
223+    feerate_sat_kvb = int(feerate_btc_kvb * Decimal(1e8)) # Fee in sat/kvb as an int to avoid float precision errors

MarcoFalke commented at 2:33 pm on October 11, 2021:

It seems a bug to silently accept sub-decimal feerates (Bitcoin Core doesn’t accept them either). I think this can be fixed (and the whole conversion avoided) by simply changing all call sites to provide the value in feerate_sat_vB. I can create a pull for that, if this is too unrelated to this pull request.

ryanofsky commented at 3:22 pm on October 11, 2021:

It seems a bug to silently accept sub-decimal feerates

This doesn’t seem like bug conceptually. Fees are discrete values, so a fixed precision decimal representation makes sense for absolute fees. Feerates are continuous values (ratio of the discrete values, rational numbers) so any floating or fractional representation makes sense and while error feedback about being out of range would be useful, error feedback about being too precise would be strange.

Also, this is just a drive-by review comment so feel free to ignore, but the math here converting between '0.00000001' string literals and 1e8 floating point literals, and decimal objects, long integer objects plus use of a satoshi_round function that is rounding down when you are trying to round up seems overcomplicated even if it is correct. If I were trying to write this in the most readable way I would probably do all the math with python long integers and a ceildiv helper, and just return a Decimal object at the end.

0def ceildiv(a, b):
1    return -(-a // b)

A ceildiv function would probably also simplify the c++ code, though the implementation in c++ would be different (something like (a + b - 1) / b)

MarcoFalke commented at 3:53 pm on October 11, 2021:

This doesn’t seem like bug conceptually.

Sure, feerates in theory are rational numbers. However, this function is there to replicate the behavior of Bitcoin Core when it comes to feerates. And Bitcoin Core doesn’t accept rational numbers as feerates. Only natural numbers, which represent a sat/vB ratio.

achow101 commented at 4:14 pm on October 11, 2021:

CFeeRates are BTC/kvb so we actually can get sub-decimal sat/vb feerates, to 4 decimal places of precision.

achow101 commented at 4:32 pm on October 11, 2021:

I’ve added a ceildiv function as suggested.

I think any broader feerate changes to the tests should be done in another PR. The goal of the test changes here is to just make sure that the calculation is the same.

ryanofsky commented at 1:57 pm on October 13, 2021:

I think this can be fixed (and the whole conversion avoided) by simply changing all call sites to provide the value in feerate_sat_vB. I can create a pull for that, if this is too unrelated to this pull request.

I think this could be a nice simplification for another PR. This function is only used by assert_fee_amount which is should be convenient for developers and make tests readable. I don’t know if it’s make tests more readable to be able to write fees as feerate_btc_kvb and have this automatic conversion, or to write fees as feerate_sat_kvb and avoid the need for this conversion. I just don’t think it’s a bug for the conversion to accept fractional feerates since they do make sense conceptually and since this line isn’t really trying to emulate anything in bitcoin core.

MarcoFalke deleted a comment on Oct 11, 2021

tests: Calculate fees more similarly to CFeeRate::GetFee

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.

80dc829be7

achow101 force-pushed on Oct 11, 2021

in test/functional/test_framework/util.py:230 in 80dc829be7

225+
226+def get_fee(tx_size, feerate_btc_kvb):
227+    """Calculate the fee in BTC given a feerate is BTC/kvB. Reflects CFeeRate::GetFee"""
228+    feerate_sat_kvb = int(feerate_btc_kvb * Decimal(1e8)) # Fee in sat/kvb as an int to avoid float precision errors
229+    target_fee_sat = ceildiv(feerate_sat_kvb * tx_size, 1000) # Round calculated fee up to nearest sat
230+    return satoshi_round(target_fee_sat / Decimal(1e8)) # Truncate BTC result to nearest sat

ryanofsky commented at 1:30 pm on October 13, 2021:

In commit “tests: Calculate fees more similarly to CFeeRate::GetFee” (80dc829be7f8c3914074b85bb4c125baba18cb2c)

I think the satoshi_round call just complicates things here and should be dropped. Just return target_fee_sat / Decimal(1e8) should already return a decimal object with the right level of precision

ryanofsky approved

ryanofsky commented at 2:02 pm on October 13, 2021: member

Code review ACK 80dc829be7f8c3914074b85bb4c125baba18cb2c

promag commented at 2:51 pm on October 16, 2021: member

Tested ACK 80dc829be7f8c3914074b85bb4c125baba18cb2c.

Funny thing, looking at the 1st commit in GH we (kind of) had round-up: https://github.com/bitcoin/bitcoin/blob/e071a3f6c06f41068ad17134189a4ac3073ef76b/main.h#L509

Later the code was refactored in c6cb21d17ab8097b6a425d37e48c955fbb0e9f0c (#3959) and the round-up was dropped.

unknown approved

lsilva01 approved

lsilva01 commented at 5:03 pm on October 25, 2021: contributor

tACK 80dc829

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

meshcollider commented at 4:21 am on November 4, 2021: contributor

utACK 80dc829be7f8c3914074b85bb4c125baba18cb2c

meshcollider merged this on Nov 4, 2021

meshcollider closed this on Nov 4, 2021

sidhujag referenced this in commit 0788a8c8ee on Nov 4, 2021

fanquake deleted a comment on Nov 12, 2021

fanquake referenced this in commit 83ea81be9c on Nov 22, 2021

fanquake referenced this in commit 5f952c6b95 on Nov 22, 2021

fanquake referenced this in commit e02e8dcf58 on Nov 22, 2021

fanquake referenced this in commit b3c908b213 on Nov 22, 2021

fanquake referenced this in commit 9ef9344f2d on Nov 22, 2021

fanquake referenced this in commit 8856c89542 on Nov 22, 2021

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

fanquake commented at 7:36 am on November 25, 2021: member

Added to #23276 for backport to 22.x

fanquake referenced this in commit 2598326460 on Feb 14, 2022

fanquake referenced this in commit b82eadf503 on Feb 14, 2022

fanquake referenced this in commit 5f82780c89 on Feb 14, 2022

fanquake referenced this in commit bd7e08e36b on Feb 15, 2022

fanquake referenced this in commit f66bc42957 on Feb 15, 2022

fanquake referenced this in commit c768bfa08a on Feb 15, 2022

fanquake referenced this in commit 9b5f674abb on Mar 1, 2022

in src/test/transaction_tests.cpp:816 in 80dc829be7

809@@ -810,10 +810,10 @@ BOOST_AUTO_TEST_CASE(test_IsStandard)
810     // nDustThreshold = 182 * 3702 / 1000
811     dustRelayFee = CFeeRate(3702);
812     // dust:
813-    t.vout[0].nValue = 673 - 1;
814+    t.vout[0].nValue = 674 - 1;
815     CheckIsNotStandard(t, "dust");
816     // not dust:
817-    t.vout[0].nValue = 673;
818+    t.vout[0].nValue = 674;

MarcoFalke commented at 12:31 pm on March 2, 2022:

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

MarcoFalke commented at 12:50 pm on March 2, 2022:

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

SmartArray referenced this in commit 344e306614 on Apr 6, 2022

SmartArray referenced this in commit 2d061fdb6f on Apr 6, 2022

luke-jr referenced this in commit 12ff15c23c on May 21, 2022

DrahtBot locked this on Mar 2, 2023

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