9

There seems to be a chicken and egg problem when it comes to creating a transaction that has a specific fee rate (sat/kW).

In order to set a specific fee rate, you need to know what the total weight of a transaction will be. But in order to calculate the total weight, you'd presumably need to have the complete transaction, including some kind of temporary value for the fee.

I can imagine there are some edge cases where the input only has enough to cover a small fee, meaning that setting a high fee would require adding another input to the tx, complicating the tx size estimation.

Are there any efficient solutions for this situation?

13

Yes! The trick is to count each input with its effective value rather than its nominal value.

Transactions are composed of three parts: the overhead, the inputs and the outputs.

  • Outputs:
    The size of the output scripts is determined by the recipient addresses, so their size is given by the transaction instructions. We do not know whether we will need a change output yet, but we know what size it would be if we created one.

  • Overhead:
    The transaction overhead is 10 bytes for non-segwit transactions, or 42 WU for segwit transactions. You can probably guess which one you'll need, but in the worst case you overestimate by 0.5 vB. We can therefore consider the overhead size also to be fixed.

  • Inputs:
    The tricky part is the transaction inputs. You do not know how many you will need, and might not know what input script sizes they'll have if you have inputs of various address formats. Additionally, signatures are not always the same size. However, we do know the maximum size of the signature, and the size of the input script for each UTXO. Together with the target fee rate, we can calculate the effective value:

    effectiveValue = utxo.value − feePerByte × bytesPerInput¹

The selection target starts out as the sum of the recipient amounts. We simplify the coin selection problem by adding the fixed costs to the selection target. We then perform the selection via counting effective values rather than nominal values. Since each input has paid for itself already when it is selected, we no longer need to worry about an input's fee impact after selection; instead each effective value goes fully towards the selection target.

In regard to the change output, there are two strategies. One, if you are aiming to build a transaction that avoids creating change, e.g. by using Branch and Bound selection, you keep the target as is: target = recipient amounts + fees for fixed transaction parts. Two, if you are using a strategy that will create change, you add a buffer to the selection target that is large enough to cover the fee of the change output and leave enough for a good-sized change output: target = recipient amounts + fees for fixed tx parts + change output cost + minChange.

For the signatures, you estimate using the maximum signature length. Since the signatures are part of the witness for segwit inputs, this results only in a small size overestimation which will lead to minutely overshooting the target fee rate.² Alternatively, you can use signature grinding to save an expected 0.5 bytes per signature and estimate the fee rate more precisely.

¹ Effective value was proposed in section 5.3 of An Evaluation of Coin Selection Strategies, Erhardt 2016, disclosure: authored by yours truly.
² Overshooting the target fee rate is preferable; it costs only a few satoshis and slightly increases the priority of the transaction. Undershooting the target fee rate is problematic, since some payment processors require a minimum fee rate to accept a payment and falling below the default minRelayTxFeeRate can prevent a transaction from relaying altogether.

| improve this answer | |
5

Kind of, but coin selection is hard in general. The idea is that inputs pay for themselves. It is easy to compute how much in fees you will need to pay for an input at a given fee rate. So when you do coin selection, instead of selecting on the actual value of the input, you use the value of the input minus the fees it will pay. This is known as the effective value.

Then for your selection target, you want to include the fees that will be paid for the outputs and the transaction overhead (i.e. version and locktime fields). So the overall target is the intended amount plus the fees of the non-input parts of the transaction.

Now you can select up to the selection target using the effective values and this should cover the transaction fees for the transaction at a given fee rate.


However there is a minor issue here with change outputs. The inclusion of a change output is going to effect the end fee rate. The strategy that Bitcoin Core employs to deal with this is to use two different coin selection algorithms. The first algorithm searches for an exact match with a bit of buffer. This allows us to ignore the change output for this algorithm. If a solution is found, then there will not be a change output.

If the exact match algorithm fails, then we can assume that a change output will be created. So now we include the change output in the transaction and its fees in the selection target. We are basically guaranteed to have a change output, so it is unlikely that we will overpay by including the fees for a change output in the selection target.

| improve this answer | |
0

I found these links when I was doing research about creating spending transaction of a multisig address

Maybe it helps

https://jlopp.github.io/bitcoin-transaction-size-calculator/

https://bitzuma.com/posts/making-sense-of-bitcoin-transaction-fees/

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.