0.16 Min relay fee issue caused by vsize miscalculation

[alexandrupele]

In the latest 0.16 version, the fee is calculated at a "per virtual kilobyte" rate which is great, but the actual vsize value seems to be off by 1 vbyte (less than it should be). The problem seems to be in Wallet#estimateVirtualBytesForSigning

vsize += (script.getNumberOfBytesRequiredToSpend(key, redeemScript) + 3) / 4; // round up

The value is not actually rounded up! There is a comment about it but I think the implementation was forgotten.

What this means in practice is that given a minimum fee rate of 1000 sats/vbyte, the transaction will most likely be ignored or not even relayed by most applications because it's not passing the min relay fee filter.

[schildbach]

I can attest that if I pay exactly 1 sat per 1 vbyte, that sometimes a tiny bit less is paid, and the transaction becomes stuck. However, this is not always the case. I also had cases where the fee was exact.

I assume this comes from the fact that the encoding of signatures is not always exactly 32 bytes (pre-taproot, afaicr this has been fixed). Sorry I may be stating the obvious, but I'd like to make sure we're on the same page here.

[alexandrupele]

To me it looks like a math problem, since the original author actually expected the need to round up - hence the comment. I've actually tested a few transactions and if the value would have been rounded up, it would have been the exact fee. I've created a PR for the rounding up issue: #2236

[schildbach]

As I just mentioned in #2236, I had another look and think that (x + 3) / 4 is actually a round-up-division by 4. Btw. there is another instance of this code in Transaction.getVsize().

[alexandrupele]

@schildbach I see. Interestingly enough, Transaction.getVsize() seems to return the right value. However, when calculating the fee, this estimation is off by 1.

final int vsize = tx.getVsize() + estimateVirtualBytesForSigning(selection);

[alexandrupele]

However, you can try on a few examples and you'll see that the (x + 3) / 4 expression is not rounding up when you are using integers. TBH I think Transaction.getVsize() needs to be fixed as well and it may be that sometimes it returns the right value even without the fix because maybe after signing the division is exact.

[schildbach]

However, you can try on a few examples and you'll see that the (x + 3) / 4 expression is not rounding up when you are using integers.

I did just that, and I think it behaves the right way:

(0+3)/4 = 0
(1+3)/4 = 1
(2+3)/4 = 1
(3+3)/4 = 1
(4+3)/4 = 1
(5+3)/4 = 2
(6+3)/4 = 2
(7+3)/4 = 2
(8+3)/4 = 2
(9+3)/4 = 3
(10+3)/4 = 3
(11+3)/4 = 3
(12+3)/4 = 3

[alexandrupele]

For i.e (12+3)/4 => 15/4 = 3,75. Rounding up it should be 4, not 3.
Same as for the other ones. Or am I missing something?

From BIP0141 (the docs): Virtual transaction size is defined as Transaction weight / 4 (rounded up to the next integer).

[schildbach]

final int vsize = tx.getVsize() + estimateVirtualBytesForSigning(selection);

I think that line is a bit inexact, but it should lead only to overpaying not to underpaying. Both raw vbytes and sig vbytes are rounded up, rather than adding them as bytes and convert/round to vbytes afterwards.

[schildbach]

For i.e (12+3)/4 => 15/4 = 3,75. Rounding up it should be 4, not 3. Same as for the other ones. Or am I missing something?

The actual division is 12/4 = 3 (without remainer). So 3 is correct, there is nothing to round up.

[schildbach]

To make this clearer, here is the sentence from the spec:

Virtual transaction size is defined as Transaction weight / 4 (rounded up to the next integer).

[schildbach]

I think that explains why you don't see the issue with Transaction.getVbyte(): It's probably implemented correctly.

However, I'm beginning to think that in Wallet.estimateVirtualBytesForSigning() we're missing the conversion of script.getNumberOfBytesRequiredToSpend()'s bytes to weight…

[alexandrupele]

Ah wow, I see what you mean. So you are saying that Math.ceil(x/4) should be always equal to (int) (x + 3) / 4. Got it now, clever trick! But the estimation is still off. And the big problem is if you are using the minimum fee rate of 1 sat/vbyte it won't make it pass the min relay filter of most Bitcoin miner nodes. Some services won't even relay the transaction.

Edit: I've closed the PR, you are right about the rounding part, but there is a problem somewhere with the estimation.
Edit 2: Good point. Maybe script.getNumberOfBytesRequiredToSpend is indeed not a "weight".

[schildbach]

I'll look into it in a couple of hours, but if you beat me at it, let me know.

[schildbach]

@alexandrupele see #2239

[alexandrupele]

@schildbach great news! Thank you for your prompt response. For now, to avoid our issue with stuck transactions, we'll just set a slightly higher fee. Do you know when we can expect the next minor release or patch that will contain this improvement?

[schildbach]

The fix is merged to master and I've already backported it to the 0.16 branch. We can do a minor release soon if there is demand for it.

[schildbach]

I went ahead and actually released 0.16.1, containing this fix.

[alexandrupele]

That's great @schildbach! I'll give it a spin tomorrow and I let you know if we still encounter the issue. Thanks!

[alexandrupele]

So far so good. I can confirm that the issue we had went away and now we can do 1 sat / vbyte transactions on testnet without issues. Thank you again for the support and for the quick fix @schildbach, you are the best!

[schildbach]

Thanks again for reporting and testing this.