2

I'm writing an algorithm for calculating fee based on fee rate and amount to be sent (requested amount) in order to propose the fee to user;

  1. Sorting UTXOs ascending based on value
  2. Take enough UTXOs so sum is larger than requested amount
  3. Calculate change, add to outputs
  4. Build tx
  5. Calculate fee based on tx byte size times fee rate
  6. Is Change larger than calculated fee? (can we "fit" fee into change)
  7. If no: go back to step 2 and add more UTXOs to get to fee
  8. If yes: reduce the Change for fee and build final transaction

This works well in most cases, but if you have large number of UTXOs with small values and fee rate is large (e.g. 88 sat/byte), you can end up with very large transaction, i.e. very large fee for sending very small amount of coins.

I have tried to make a change in algorithm where after X number of iterations, I would give up and try to take enough UTXOs for requested amount and deduct fee from that amount and send what ever is left. But I ended up in long loop again, as UTXOs were small, transaction large and in every iteration I didn't had enough to pay the fee.

As this is obviously bad implementation, is there any other way to calculate fee bases on fee rate?

2 Answers 2

3

There are some improvements that you can make to this algorithm.

The first is to select UTXOs based on their effective value. The effective value is the value of the UTXO with the amount in fees required to spend it subtracted from it. In this way, each UTXO you spend pays for itself. This is called the effective value because that is the value that actually affects the outputs. You do this by calculating how large spending that UTXO will be, then multiplying by your fee rate to get its fee. This fee is then subtracted from the UTXO amount.

Then you can calculate the fees for the rest of the transaction, i.e. the fixed overhead (tx version, locktime, etc.) and the outputs. Since these are all determined before you choose the UTXOs to spend, it's fine to calculate this value before you choose UTXOs. The UTXOs you choose won't have an effect on this fee. This amount in fees can then be added to the amount you are trying to select for, i.e. add it to the amount being sent.

By using the effective values of inputs (so inputs pay for themselves) and then increasing the amount that you are trying select (so the cost of the rest of the transaction is covered), you can remove the need to loop (step 7) in order to choose the UTXOs you want. Now when you choose the UTXOs, you know that each input has paid for itself, and that you have chosen enough value to cover the outputs and their cost.

Another improvement is to not sort the UTXOs. In fact, it is better to choose UTXOs randomly. You can achieve this by shuffling the list of UTXOs instead of sorting them. Sorting UTXOs has several longer term effects that will negatively impact you in the future. Notably, by sorting UTXOs, you will end up creating very small change, which means that future transactions will have many UTXOs with small values, which increases their fee. Sorting by smallest first will see this effect sooner. Sorting by largest first will see this effect over time.

2
  • "and the outputs" -- I guess initially we assume there will be a change output. But if that turns out to be unneeded after UTXO selection, and so then we don't include a change output, will our feerate be a bit too high? Do we just go ahead anyway, or do we try to lower the feerate (go back to UTXO selection)? Aug 11, 2022 at 16:35
  • 1
    @LarryRuane You would just have a slightly higher feerate. Consider it this way: you were willing to pay that fee to have a change output, but it turns out you don't need one. It's still the same amount spent in fees, but your transaction now gets a small bonus of a higher feerate. If you go back and try to select a changeless solution, it may be completely different from the first one and may not actually be better. Selections with different parameters are independent of each other and it's really not that useful to use a previous selection to try to inform another one.
    – Ava Chow
    Aug 11, 2022 at 20:07
2

If you don't account for the fees of the inputs until after selecting the inputs, your target is shifting while you're selecting with each input you add. Since your transaction building starts with a known target feerate, and you know the size of the transaction header data and outputs, you can calculate their fees in advance.

Then, since you know the feerate and you can predict the input weight for every UTXO before picking it, instead of counting UTXOs with their full value towards your selection target, only count them with their effective value: eff_value = value - feerate×input_weight

That way, every input that you pick has already paid its own fee and your target does not shift while you're picking inputs.

Smallest-first is one of the most consolidatory approaches you can take to UTXO management: it always maximizes the input count for the current UTXO pool and transaction building request. That way, you keep your UTXO count lean, but in almost every attempt you're using more UTXOs than necessary at that time.

You can be more thrifty by being selective when to use that strategy—e.g. at low feerates use smallest-first and at high feerates use random selection or largest-first. That way, you spend a greater portion of your UTXOs at lower feerates decreasing your overall cost.

If you're spending a lot of time thinking about coin selection and UTXO management, you may find other questions with the tag , the topic What are the trade-offs between the different algorithms for deciding which UTXOs to spend?, and my Master thesis, “An Evaluation of Coin Selection Strategies [PDF] (2016)” interesting.

2
  • I've heard the term "negative effective value" but it always confused me. Your answer makes it make sense. If our (exogenous) feerate is high, a particular UTXO may have a negative effective value, so we shouldn't use it. But later, our feerate may be sufficiently lower such that this UTXO has a positive effective value. If a UTXO's effective feerate is negative at minrelayfee, does that make it dust? Aug 12, 2022 at 22:45
  • 1
    @LarryRuane: If a UXTO has a negative effective value at minRelayTxFee it would be dust, but the dust limit is even higher: bitcoin.stackexchange.com/a/41082/5406
    – Murch
    Aug 14, 2022 at 14:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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