It says here https://github.com/bitcoin/bitcoin/blob/master/src/wallet/wallet.cpp#L2458 that to choose coins for a transactions we need to solve subset sum. But subset sum is when you're not allowed to go over a certain amount; whereas in bitcoin you can go over the amount and give change. So why is this necessary?


There are a few goals of coin selection.

Firstly, we want to select enough coins for the user. Secondly, we want to minimize transaction fees. Lastly we want to reduce the UTXO set.

Reducing the UTXO set requires creating less outputs than there are inputs in a transaction. By solving the subset sum problem, we can avoid making a change output and thus help to reduce the UTXO set.

  • For those wanting to go deeper in coin selection algorithms, I can recommend reading murch.one/wp-content/uploads/2016/11/…
    – alcio
    Dec 1 '17 at 20:15
  • that may be the reason they did it. Though it doesn't make sense to me to do a much more computationally heavy procedure to maybe reduce one output.
    – relG
    Dec 2 '17 at 11:11
  • @relG It's not just that though. The coin selection algorithm used by Bitcoin Core also results in larger change outputs. A lot of other algorithms end up breaking down the user's inputs into smaller and smaller outputs, which makes it harder and harder to spend those outputs. I highly recommend that you read the paper linked in the above comment as it explains the performance characteristics of various algorithms.
    – Andrew Chow
    Dec 2 '17 at 17:45
  • I'm reading Section 3.4 and it talks about finding the closest thing to the target value if exact solution is not found, which would result in small change.
    – relG
    Dec 2 '17 at 20:24

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.