‘Coin Selection’ is the technical term used to talk about the algorithm that allows Bitcoin to decide which bits of data are to be used to create a user's transaction. This is the digital equivalent of a person giving the cashier $5 for a $2 item and getting back $3 in change. This particular algorithm will be receiving a major update in Bitcoin code very soon.
While this may not sound like a major breakthrough it will result in a massive improvement because this particular algorithm is not fully optimized in the core code. The most significant impact resulting from the change in the ‘Coin Selection‘ algorithm is that it will see a potential change in transaction fees.
In a statement, Andrew Chow, Bitcoin Core contributor said
Bitcoin Core's original coin selection algorithm actually needs a lot of reworking, especially with regards to transaction fees. It's inefficient and it ends up doing a weird loop to try to guess the amount of transaction fees that are needed
This is why the people behind Bitcoin have been working hard on developing this new algorithm that is being labeled as ‘branch and bound’ or ‘BnB’. This new algorithm will carry out calculations in a more efficient way – resulting in a small bump in processing speed and lower transaction fees.
This change was proposed two years ago but has only recently been deemed ready to be added to Bitcoin Core. This feature should be ready for general use by the time the 17th version of the core software is released which will most likely be in 2019.
How Coin Selection Works
The new coin selection algorithm is a big step up from how it used to be. When Bitcoin is in your wallet, it is not just one piece of data. It is divided into several chunks. There could be several transaction chunks in your wallet. These are technically called ‘unspent transaction outputs’ or UTXOs.
As an example, a customer might have a UTXO worth 0.3 BTC, some 0.2 BTC UTXOs and a few other denominations. The chunking of UTXO’s are based on previous transactions and how they were sent to the person.
If a customer needs to pay for 0.2 BTC, the old algorithm might select the 0.3 BTC chunk as the input of the transaction. There will then be two outputs: the 0.2 BTC that receives the payment, and the 0.1 BTC which is the customer’s change. However, the inefficiency in the old algorithm means that it was not good at picking the right data chunks and always ended up creating ‘change outputs’ instead of just selecting the exact data chunk. The inefficient process also created ‘dust’ the small pieces of Bitcoin that are not worth spending because of transaction fees.
Thanks to the new algorithm, Bitcoin can now avoid both of these issues. BnB looks at the payment needed and looks for the exact UTXO needed. This has a knock-on effect on transaction fees since if an exact match can be found; the transaction data is smaller and easier to process. The process is still being tweaked, but developers are optimistic about its future use.