<p>There are a few goals of coin selection.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2017-12-01T20:15:14.390Z
For those wanting to go deeper in coin selection algorithms, I can recommend reading http://murch.one/wp-content/uploads/2016/11/erhardt2016coinselection.pdf
alcio
CC BY-SA 3.0
2017-12-02T11:11:24.023Z
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
CC BY-SA 3.0
2017-12-02T17:45:15.973Z
@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
CC BY-SA 3.0
2017-12-02T20:24:47.363Z
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
CC BY-SA 3.0
2017-12-01T19:00:58.000Z
2017-12-01T19:00:58.000Z
Ava Chow
<p>It says here <a href="https://github.com/bitcoin/bitcoin/blob/master/src/wallet/wallet.cpp#L2458" rel="nofollow noreferrer">https://github.com/bitcoin/bitcoin/blob/master/src/wallet/wallet.cpp#L2458</a>
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?</p>

<bitcoin-core>
bitcoin coin selection algorithm
relG
# bitcoin coin selection algorithm

(Asked by: username_0 on 2017-12-01)

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?

**Tags:** bitcoin-core


---

## 1 answers

### Answer by username_1 on 2017-12-01. Score: 1

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.

> **Comments:**
> **username_2**: For those wanting to go deeper in coin selection algorithms, I can recommend reading http://murch.one/wp-content/uploads/2016/11/erhardt2016coinselection.pdf  
> **username_0**: 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.  
> **username_1**: @username_0 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.  
> **username_0**: 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.  

---

