Bitcoin Is Close to Cutting Fees with Better Coin Selection

3. April 2018.

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 a $10 bill to a cashier for a $7 item and the cashier giving the consumer back $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 a “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.

Actually, Erhardt first proposed some optimizations nearly two years ago, whereas 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 seventeenth 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

Backing up some, 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 bitcoin, another worth 0.3 bitcoin, another one worth 0.1 and the last one worth 0.5 to make up the whole one bitcoin.

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

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

According to 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 (in the example above, the algorithm could instead pick the two pieces of data worth 0.1 bitcoin and not have to send “change” back to the sender, and as such, wastes space in the blockchain, Erhardt argued.

He continued, speaking to another unfortunate side effect:

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

“Dust” are pieces of bitcoin that are so small they’re almost not worth spending since the fees associated with spending that would 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 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 it needs to reach.

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, there might not have been any other way. Coin selection is a “sensitive part” of the code and changing it has “global consequences.”

As such, “no one wanted to fiddle with it for too long,” he said, 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.

Published at Mon, 02 Apr 2018 09:00:22 +0000

We will be happy to hear your thoughts

Leave a reply

Register New Account
Login to
Reset Password