<p><sub>Disclosure: I’m describing my own work: the Branch and Bound coin selection algorithm was first described in my own <a href="https://murch.one/erhardt2016coinselection.pdf" rel="nofollow noreferrer">Master thesis</a>.</sub></p>
<p>The Branch and Bound algorithm searches for the <em>least wasteful</em> input set that produces a changeless transaction. To that end it deterministically searches all possible relevant combinations of the wallet’s UTXO pool. Since the powerset of a collection grows exponentially in the size of the collection, Branch and Bound bounds its search in a number of ways whenever an area in the search tree cannot yield any better solutions.</p>
<p>The gist of the algorithm is as follows:</p>
<ol>
<li>Calculate the <em>effective value</em> of each UTXO: <code>effective_value = amount - input_weight × feerate</code></li>
<li>Sort the UTXOs descendingly by effective value</li>
<li>In order of the sorted UTXOs, keep adding the next UTXO until the <code>total_selected_effective_value</code> exceeds the <code>selection_target</code></li>
<li>If <code>total_selected_effective_value</code> is also smaller than <code>selection_target + cost_of_change_output</code>, we have found an input set that would produce a changeless transaction. Keep this input set if it has a better waste score than the prior best input set.</li>
<li>Whenever you exceed the target, backtrack by deselecting the last selected UTXO and omitting it instead.</li>
</ol>
<p>Let’s assume we have three UTXOs with effective values of 0.1 ₿, 0.09 ₿, and 0.05 ₿. We are searching for an input set that raises 0.14 ₿. Our search would look like this:</p>
<p><a href="https://i.sstatic.net/ZWx6P.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/ZWx6P.png" alt="Example search graph from the Master thesis" /></a></p>
<p><sup>via <a href="https://murch.one/erhardt2016coinselection.pdf" rel="nofollow noreferrer">Erhardt: An Evaluation of Coin Selection Strategies (2016) [PDF]</a></sup></p>
<ol>
<li>{0.1}: We have insufficient funds and continue.</li>
<li>{0.1, 0.09}: We select 0.1 ₿, then select 0.09  for a total of 0.19 ₿. We have overshot above the target window. We backtrack.</li>
<li>{0.1, <s>0.09</s>, 0.05}: We deselect 0.09 ₿, then select 0.05 ₿ for a total of 0.15 ₿. We have overshot above the target window and backtrack.<br />
{0.1, <s>0.09</s>, <s>0.05</s>}: The omission branch of 0.05 ₿ leaves us with insufficient funds. We have completely searched the subtree that starts by selecting the 0.1 UTXO and continue by skipping the 0.1 ₿ UTXO.</li>
<li>{<s>0.1</s>, 0.09}: We have insufficient funds and continue.</li>
<li>{<s>0.1</s>, 0.09, 0.05}: With a total of 0.14 ₿, we have found an input set that produces a changeless transaction. This is our new best input set.<br />
{<s>0.1</s>, 0.09, <s>0.05</s>}: The omission branch of 0.05 ₿ has insufficient funds.<br />
{<s>0.1</s>, <s>0.09</s>}: The omission branch of 0.09 ₿ also has at most 0.05 ₿, so we cannot find any solution there.</li>
</ol>
<p>For a wallet with a larger UTXO pool, this search would likely yield multiple solutions. In that case, we would compare the input set candidates on basis of the <a href="https://bitcoin.stackexchange.com/q/113622/5406">waste metric</a> and keep the input set with the best (i.e. lowest) waste score.</p>
<p>So far this just generates all possible combinations of inputs, skipping just input sets for which a prefix already exceeded the target.
The <a href="https://github.com/bitcoin/bitcoin/blob/cf553e3ab7b3827c9c1b91fcc50082856f761913/src/wallet/coinselection.cpp#L76" rel="nofollow noreferrer">implementation in Bitcoin Core</a> limits the number of attempts to 100,000 and has a number of optimizations to skip parts of the search tree that cannot yield better solutions:</p>
<ul>
<li>more wasteful: if our current selection already has a worse waste score than the best solution, and we are in the high-feerate mode, we can exit early as adding more inputs can never produce a better solution</li>
<li>lookahead: by keeping track of the total available effective value in the remaining UTXOs, we can exit subtrees early when there are insufficient funds to reach the target (i.e. when <code>selected + lookahead &lt; target</code>)</li>
<li>max_weight exceeded: if our current selection would lead to the inputs set being bigger than the limit for standard transactions, we can exit a subtree early, because it cannot yield solutions</li>
<li>skipping clones: if the previous UTXO matches the current UTXO in weight and effective value but is not selected, selecting this UTXO would recreate equivalent input sets to ones created prior. We can therefore skip selection of such a “clone UTXO”.</li>
</ul>

CC BY-SA 4.0
2023-10-05T21:25:10.677Z
2023-10-25T14:22:20.107Z
2023-10-25T14:22:20.107Z
Murch
<p>Murch described in his <a href="https://murch.one/erhardt2016coinselection.pdf" rel="noreferrer">Master thesis [PDF]</a> an algorithm for coin selection called &quot;Branch and Bound&quot; or &quot;BnB&quot;. It subsequently got implemented into multiple bitcoin wallet implementations. How does it work?</p>

<coin-selection>
How does the Branch and Bound coin selection algorithm work?
Murch
# How does the Branch and Bound coin selection algorithm work?

(Asked by: username_0 on 2023-10-05)

username_0 described in his [Master thesis [PDF]](https://username_0.one/erhardt2016coinselection.pdf) an algorithm for coin selection called "Branch and Bound" or "BnB". It subsequently got implemented into multiple bitcoin wallet implementations. How does it work?

**Tags:** coin-selection


---

## 1 answers

### Answer by username_0 on 2023-10-05. Score: 5

Disclosure: I’m describing my own work: the Branch and Bound coin selection algorithm was first described in my own [Master thesis](https://username_0.one/erhardt2016coinselection.pdf).

The Branch and Bound algorithm searches for the *least wasteful* input set that produces a changeless transaction. To that end it deterministically searches all possible relevant combinations of the wallet’s UTXO pool. Since the powerset of a collection grows exponentially in the size of the collection, Branch and Bound bounds its search in a number of ways whenever an area in the search tree cannot yield any better solutions.

The gist of the algorithm is as follows:

1. Calculate the *effective value* of each UTXO: `effective_value = amount - input_weight × feerate`
2. Sort the UTXOs descendingly by effective value
3. In order of the sorted UTXOs, keep adding the next UTXO until the `total_selected_effective_value` exceeds the `selection_target`
4. If `total_selected_effective_value` is also smaller than `selection_target + cost_of_change_output`, we have found an input set that would produce a changeless transaction. Keep this input set if it has a better waste score than the prior best input set.
5. Whenever you exceed the target, backtrack by deselecting the last selected UTXO and omitting it instead.

Let’s assume we have three UTXOs with effective values of 0.1 ₿, 0.09 ₿, and 0.05 ₿. We are searching for an input set that raises 0.14 ₿. Our search would look like this:

[![Example search graph from the Master thesis](https://i.sstatic.net/ZWx6P.png)](https://i.sstatic.net/ZWx6P.png)

via [Erhardt: An Evaluation of Coin Selection Strategies (2016) [PDF]](https://username_0.one/erhardt2016coinselection.pdf)

1. {0.1}: We have insufficient funds and continue.
2. {0.1, 0.09}: We select 0.1 ₿, then select 0.09  for a total of 0.19 ₿. We have overshot above the target window. We backtrack.
3. {0.1, ~~0.09~~, 0.05}: We deselect 0.09 ₿, then select 0.05 ₿ for a total of 0.15 ₿. We have overshot above the target window and backtrack.  
   {0.1, ~~0.09~~, ~~0.05~~}: The omission branch of 0.05 ₿ leaves us with insufficient funds. We have completely searched the subtree that starts by selecting the 0.1 UTXO and continue by skipping the 0.1 ₿ UTXO.
4. {~~0.1~~, 0.09}: We have insufficient funds and continue.
5. {~~0.1~~, 0.09, 0.05}: With a total of 0.14 ₿, we have found an input set that produces a changeless transaction. This is our new best input set.  
   {~~0.1~~, 0.09, ~~0.05~~}: The omission branch of 0.05 ₿ has insufficient funds.  
   {~~0.1~~, ~~0.09~~}: The omission branch of 0.09 ₿ also has at most 0.05 ₿, so we cannot find any solution there.

For a wallet with a larger UTXO pool, this search would likely yield multiple solutions. In that case, we would compare the input set candidates on basis of the [waste metric](https://bitcoin.stackexchange.com/q/113622/5406) and keep the input set with the best (i.e. lowest) waste score.

So far this just generates all possible combinations of inputs, skipping just input sets for which a prefix already exceeded the target.
The [implementation in Bitcoin Core](https://github.com/bitcoin/bitcoin/blob/cf553e3ab7b3827c9c1b91fcc50082856f761913/src/wallet/coinselection.cpp#L76) limits the number of attempts to 100,000 and has a number of optimizations to skip parts of the search tree that cannot yield better solutions:

* more wasteful: if our current selection already has a worse waste score than the best solution, and we are in the high-feerate mode, we can exit early as adding more inputs can never produce a better solution
* lookahead: by keeping track of the total available effective value in the remaining UTXOs, we can exit subtrees early when there are insufficient funds to reach the target (i.e. when `selected + lookahead < target`)
* max\_weight exceeded: if our current selection would lead to the inputs set being bigger than the limit for standard transactions, we can exit a subtree early, because it cannot yield solutions
* skipping clones: if the previous UTXO matches the current UTXO in weight and effective value but is not selected, selecting this UTXO would recreate equivalent input sets to ones created prior. We can therefore skip selection of such a “clone UTXO”.


---

