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?
1 Answer
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/…– alcioCommented Dec 1, 2017 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.– relGCommented Dec 2, 2017 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.– Ava Chow ♦Commented Dec 2, 2017 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.– relGCommented Dec 2, 2017 at 20:24