Bitcoin Is Close to Cutting Fees with Better Coin Selection

One of the technical mechanisms that has helped earn bitcoin comparisons to cash is on the verge of a major update.

Called “coin selection,” the term refers to the algorithm that today decides which bits of data come together to create a user’s transaction. Essentially, the coin selection code replicates the process of giving, say, a $10 bill to a cashier for a $7 item and the consumer receiving $3 in change.

But if that doesn’t sound particularly complex, remember bitcoin is experimental software, and this function, while working, isn’t altogether optimized. Making matters worse, the part that perhaps needs tweaking has a direct impact on user costs.

“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,” Bitcoin Core contributor Andrew Chow told CoinDesk.

Mark Erhardt an engineer at wallet provider BitGo agrees, going so far as to call the algorithm “convoluted” during a recent interview on the podcast Noded.

As such, developers have been working on a new algorithm, dubbed “branch and bound” or “BnB,” which forges together data in a more efficient way, resulting in a small scaling bump and lower transaction fees.

Erhardt first proposed some optimizations nearly two years ago, while Chow was the first developer to code up the changes.

And recently the change was deemed ready to be added to bitcoin’s most popular software implementation, Bitcoin Core, and so was merged into the codebase. Even better for users, the feature should be available for widespread use with the release of the 17th version of the software in the next year or so.

Speaking to the benefits of the changes, Chow said:

“This will let us tidy up the coin selection code a lot and actually make it possible for one person to understand exactly what the coin selection algorithm is doing.”

No change needed

Stepping back, as mentioned, each bitcoin transaction a user sends is made up of different smaller amounts of bitcoin.

That’s because, say you have one bitcoin in your wallet, this bitcoin is usually not just one piece of data. Rather, it’s often made up of a number of chunks of data pieced together. You might have one, two or dozens of little transaction chunks – each called “unspent transaction outputs” (UTXOs).

For instance, tied to your bitcoin wallet address might be one piece of data worth 0.1 BTC, another worth 0.3 BTC, another of 0.1 BTC and a last one, worth 0.5 BTC, to make up a whole bitcoin.

These pieces are based on the transactions that came before them and how they were initially split up to send to your wallet.

So, if you need to send 0.2 BTC, the Bitcoin Core “coin selection” algorithm might decide to put the piece of data worth 0.3 BTC in what’s called the “input,” creating the transaction. There will then be two outputs: 0.2 BTC, which will be sent to the recipient, and 0.1 BTC, which will be put back into your wallet as the “change output.”

Yet, according to the developers, the algorithm isn’t all that good at deciding how to select coins for transactions.

The algorithm almost always automatically creates “change outputs,” which often aren’t necessary and waste space on the blockchain, Erhardt explained. In the example above, the algorithm could avoid this by picking the two pieces of data worth 0.1 BTC and not have to send “change” back to the sender at all.

He continued, speaking to another unfortunate side effect:

“You don’t want transactions to be ground up to dust.”

“Dust” are pieces of bitcoin that are so small they’re almost not worth spending, since the fees could be more than the transaction itself. They’re perhaps analogous to pennies, in that a penny actually costs more to make than it’s actually worth in purchasing goods.

How to choose?

The new algorithm, BnB, avoids these issuers by trying to eliminate as many change output scenarios as possible. In short, it looks at all the inputs to see if there’s a way to reach exactly the number of bitcoins a user wants to send in a transaction.

“This helps shrink the UTXO set a little more,” Chow said. “Additionally, transactions, where an exact match was found, will generally be smaller than ones where there is change, so this will also save on transaction fees for the user and free up a few more bytes of block space to fit in other transactions.”

And there’s evidence this works. In a simulation, Erkhardt found that, in approximately 40 percent of transactions that would normally have change outputs, the new algorithm was able to get rid of the unnecessary data.

In addition to these user benefits, the code change also helps developers, since the new algorithm is much easier to understand for a technical standpoint.

Still, developers aren’t done tweaking the coin selection process. Chow and others plan to take the algorithm further, by adding a so-called “simple random draw.”

When the BnB algorithm goes through all a bitcoin user’s UTXOs and simply can’t avoid creating a change output, it then falls back on the original coin selection process. But with simple random draw, the algorithm will choose random UTXOs until it reaches the amount of money required.

Interestingly, developers find randomly choosing coins is a better method than the more deliberate algorithm Bitcoin Core uses today.

It’s the culmination of years of work, but according to Erhardt, the process couldn’t have been much quicker. Coin selection is a “sensitive part” of the code and changing it has “global consequences,” he said.

As such, “no one wanted to fiddle with it for too long,” Erhardt explained, adding:

“Now we’ve put in a lot of the plumbing for further changes.”

Binary code image via Shutterstock

The leader in blockchain news, CoinDesk is a media outlet that strives for the highest journalistic standards and abides by a strict set of editorial policies. CoinDesk is an independent operating subsidiary of Digital Currency Group, which invests in cryptocurrencies and blockchain startups.