Coin Selection Algorithms
Speakers: Andrew Chow
Date: November 5, 2021
Transcript By: alexanderwiederin via review.btctranscripts.com
Tags: Coin selection, Wallet
Category: Conference
Media: https://www.youtube.com/watch?v=m-HiVEFqFZk
Introduction
Hi, I’m Andrew Chow. I’m an engineer at Blockstream and I work on Bitcoin Core in the wallet and on various things in the wallet. So, today I’m going to be talking about coin selection and generally how you can pick your inputs better for when you’re making a transaction. To start off, what happens when you make a transaction? Well, first, you type in, you copy and paste in your address, you type in the amount that you want to send and you click the send button and your wallet does some stuff in the background and out comes a transaction, right? So what’s it really doing? Well, first it takes your address and value. It turns those into transaction outputs and it sticks them into a transaction. Then it picks some inputs, chooses some UTXOs, calls them inputs, and it puts those in the transaction. Wrap it all up, make a change output if necessary, and send that transaction off to the network. Seems pretty simple. Except choosing some inputs, right? How does a computer choose inputs? What does a computer do to just choose inputs? I mean, it’s not like you or me where I can point and say, I want that one. Although I guess you can do that if you’re doing it manually, but most people don’t really want to do that. A computer to choose some inputs, there are some algorithms that us wallet developers have designed. And one of the related problems to coin selection, or related computer science problem, are the subset sum problems and the knapsack problems. You may have heard of these. They’re relatively famous. We can actually adapt algorithms used for solving them to work on coin selection. Although coin selection does have a few major differences that need to be considered when modifying these algorithms. The first thing is the transaction fee. So, the transaction fee is actually kind of a floating value, at least initially. It will change depending on how many inputs you have. It changes on whether you have a change output. It changes on what kinds of inputs you have. So, determining the transaction fee can actually end up being a somewhat complicated issue, at least on the surface. Of course, there is a change output, right? Before you choose the inputs, you don’t know if you need to make a change output, and that presents a completely different problem. Also there is a question of how big is your change output, although that can be determined beforehand. And the last part is that there’s not just one solution. I can write a really poor coin selection algorithm that finds a solution, but that’s a solution that maybe you don’t want. Maybe it spends all of your coins and sends half of it to fees, right? No one wants that. So what is a good input set and how can we define good? Start off, we’re going to talk about the transaction fee. How do we determine a transaction fee during coin selection?
Naive Algorithm
Now there is a relatively naive algorithm, and I’ve seen this algorithm show up in many places, including in Bitcoin Core and on stack exchange posts from new wallet developers. It goes something like choose some inputs, figure out how much that would cost in transaction fees, increase the target that you want to select for, and then choose again. You just keep choosing inputs. Eventually you will have enough inputs to cover everything if your wallet had enough money in the first place. This sounds okay, but it kind of doesn’t work when you have a lot of inputs and there are many possible solutions. Because for example, if on the first try I chose 10 inputs and then the second try I choose two inputs, well now I have a much lower transaction fee that I actually need to pay than the fee that I was targeting originally. So there are workarounds for this. You can reduce the number of inputs afterwards, you can send things to change, but it generally becomes pretty messy. This leads me into the first major innovation that we came up with for coin selection called the “effective value”.
Effective Value
The main premise of the effective value is that inputs pay for themselves. An input has a fixed size. We know how big an input is going to be when we spend it. This means that we can calculate the transaction fee for that input. So we can compute this thing we call the effective value by subtracting its fee from its actual value. It’s called the effective value because that is the value the input is effectively providing to the transaction. And for the rest of the transaction, all the outputs and the transaction overhead, those are actually fixed size. We know how big they are, we know how big the outputs are, except for that change output, which I will get to in a moment. But the nice thing about the effective value is that we don’t have this loop, we can determine the fee beforehand. So, that change output, that adds a little bit of complication. How do we know we need a change output and how do we account for a transaction fee? Well, we can actually divide coin selection algorithms into two classes. Ones that find exact matches and ones that don’t.
Exact Match
So the ones that find exact matches, they find a set of UTXOs that sum to exactly the amount we want to send. This has the nice property of we don’t need to make change, because we know we have chosen exactly the amount we want to send. Without change, we can predict the fees and that’s no longer a problem. Not making change is also better for privacy because you’re not making another output that could be linked back to you. And as Poelstra mentioned on our panel earlier today, it is also better for block size. But unfortunately, finding exact match doesn’t really work because it’s unlikely to find a solution. What are the odds that I’m going to have exactly the right UTXOs to send 0.1997 something something Bitcoin? That’s very unlikely. So we need to do a little bit better than an exact match. And that’s the second innovation.
Exact Match Window
The idea of an exact match window. So, instead of matching down exactly to the Satoshi, we have a range that we would consider the exact match. And within that range, we make changeless transactions. So obviously, the lower bound is the target we want. We don’t want to send less money than we want to send. That would piss off our receivers. But for the upper bound, it’s a little bit harder. What we’ve decided to do is this idea of the “cost of change”. So if you consider a change output, there’s going to be a cost associated with creating it. You have to pay transaction fees to create it. But there’s also another cost. When you create a change output, there’s an expectation that you will be spending that change output at some point in the future. So creating a change output not only costs fees now, but it also costs fees in the future when that change output is going to be spent. So if we think about this exact match window, if we choose to throw away up to this cost of change, we’re actually spending less money on fees than if we had made a change output and spent it later. So this idea allows us to expand our exact match to our changeless solutions to include targets that include this cost of change. And so we don’t have a change output when we use the exact match window. And the only downside is that we’re throwing away a little bit of Bitcoin to fees that may not have been necessary to do in the first place. So that’s if we don’t want to make change. But maybe your wallet’s small, maybe your wallet just doesn’t have a right distribution of UTXOs, and you don’t find an exact match.
Change Output
So, what if we actually have to make a change output? Well, if we have to make a change output, yeah, the alternative to never making changes, we always make change. We shouldn’t really have an idea of maybe this algorithm might make change because that introduces back our fee estimation issue. If we never make change and then we always make change, then we know there’s going to be a change output. We know what the fee is for that. We don’t have any fee estimation problems for this transaction. And another property of combining an exact match and not exact match algorithm is that the change we create will almost will never be dust because our exact match window includes a cost to spend it later. If we make a change output, it will always never be dust. But sometimes it might be almost dust. If you’re one satoshi over dust, your effective value is one satoshi, that input is not particularly useful even though technically you didn’t lose money to spend it. So that’s an idea of a change target or a minimum change value. When you make change, you would want to make sure that your change output is big enough. So the algorithm should try to hit this change target. Bu if it can’t, then so be it, we’ll make a tiny change so that we can still make the transaction. So that’s fees and change. So the last part is, what is good? How do we determine a good input set? And of course, good is subjective.
Good
For most users, good is the smallest fees possible. You don’t want to waste any money. You want to minimize your transaction fees. That’s what most users would consider good. Some other users might also consider privacy. They want the most private transactions, maybe even at the cost of paying additional transaction fees. They don’t want to have certain inputs linked together or they want to make sure all UTXOs for a certain address are spent at the same time. But for developers, we also have a couple other considerations that most people did not think of, such as the effect on future transactions. If you spend a UTXO, you spend UTXOs, your wallet will no longer have those UTXOs to spend and that will have an effect on what UTXOs are available in the future. Likewise, if we don’t make change, that will have an effect on what UTXOs are available in the future. So the coin selection algorithm can have a major impact on the composition of UTXOs in your wallet and that will have an impact on how that coin selection algorithm performs later. Another important thing is the effect on the network, which is similar to the effect on future transactions, but every node has to maintain the UTXO set. And if the coin selection algorithm makes unnecessary UTXOs or makes a lot of dust, that’s not good for the network because those are UTXOs that all nodes on the network have to maintain. Likewise, if it cleans up dust, if it doesn’t make change and it’s really consolidated and it reduces the size of the UTXO set, that is also an effect on the network. Every node now has to maintain fewer UTXOs. So I’ll be going through these briefly.
Privacy
The first thing I want to talk about is privacy. Privacy is not something that we can really handle algorithmically, at least not at the level I’m going to be talking about, because privacy is hard to quantify. It’s relatively hard to quantify without… You need heuristics and further research. It’s harder to assign a number to privacy that we can use to measure. For the algorithms, the best that we can do, at least so far, is to just avoid making change because we know that that’s pretty good for privacy. However, at a higher level, at user level or just generally how UTXOs are stored and tracked, you can do things like grouping together UTXOs that should be sent together and spend them together. This is actually really easy because the algorithms really only deal with numbers, so you could tell an algorithm: “hey, these five UTXOs, just treat them as one input and we will spend them all at the same time”. Another thing to do is to separate UTXOs. If you have some UTXOs that should never be spent together, then don’t keep them in the same wallet, actually. It’s really easy to separate UTXOs by having multiple wallets.
Transaction Fees
On to transaction fees. Most people want fewer transaction fees, but actually it seems like this is only really true when fees are really high. If you have 100 satoshis per byte as the minimum fee rate, you really want small transactions to keep your fees down. But when fees are really low, when the fee rates are low, people actually like to make consolidation transactions. They like to make transactions that are big and consume all of their smaller inputs so that they have one larger input that they can use in the future. And it would actually be really nice if this behavior could be automated. So, to get to that automation, our third major innovation is the idea of the opportunity cost of an input.
Opportunity Cost
When a future fee rate might be low and it’s more expensive to spend today, the, you don’t want to spend inputs. And there is a cost associated with spending an input now versus in the future. On the other hand, if fee rates today are low and they are higher in the future, it’s less expensive to spend them now. So you want to spend inputs now. There is kind of a negative opportunity cost for spending an input. So if we were to say some future fee rate was like 10 satoshis per byte, this could actually become a threshold where at less than 10 satoshis per byte, I am comfortable with spending lots of inputs and consolidating. And when we’re above that fee rate, I’m not comfortable doing that and I really want to minimize everything. And so this future fee rate idea now is actually more of a consolidation fee rate. It’s the highest fee rate I’m comfortable with consolidating inputs.
Waste Metric
This finally leads us into the fourth innovation, which is the waste metric. The waste metric combines the previous ideas. So we have waste due to opportunity cost. So this is just the opportunity cost we discussed. It could be negative. It can also be positive. Negative being we want to consolidate. Positive being try to minimize fees. And then there is waste due to exceeding the target. So if we had a changeless solution, we made some excess value that we’re spending to fees, that is waste. And that is waste due to exceeding our target. Likewise, if we made a change output, then our waste is making the cost of making that change. So we combine these two things and we have now our final waste metric. So this is a convenient number that we can use to measure and to compare coin selection, compare input sets. So we can use this to compare coin selection algorithms. We can run simulations and see how much waste each algorithm produces over the course of the simulation. We can also do things like run multiple coin selection algorithms at the same time and choose the algorithm or choose a result that had the least waste. This is nice because we can have different algorithms that are tuned to perform differently and behave differently under different situations. And we always choose the best one according to our waste metric.
Bitcoin Core Waste Metric
So how is the waste metric being used today? We use it in Bitcoin Core. It was actually introduced in 0.17 with the Branch and Bound algorithm. So Branch and Bound is an exact match algorithm. It uses the exact match window. That’s actually where the idea came from. And part of what branch and bound does is it calculates waste and it just finds every solution that it can that fits within the exact match window and chooses the one with the least waste. In the next major release of Bitcoin Core, which is 23.0, we will be doing the comparison between multiple solutions. So that will compare between Branch and Bound for our exact matches, just random selection, randomly choosing inputs, and then the old thing that Bitcoin Core used to do, which we call the knapsack solver. But it’s really just the old algorithm. So we run all three of them and see what the waste of their results are and just choose the one that has the least waste. So in summary, how can you pick your inputs better?
Summary
Well, for privacy, you can make sure that UTXOs are grouped together, that should be spent together. You can make sure UTXOs are separated if you want them to be separated. That is more on the user and less on wallet developers. But also, wall developers can use effective values. You can consider the cost of spending and creating UTXOs in the future. And lastly, you can compare the results of multiple coin selection algorithms, whether that’s through the waste metric or through some new novel metric that someone may come up with. And so hopefully that is useful for any other wall developers out there. Or if you’re one of the people who likes to choose their coins manually, these are some things that you should consider when you are choosing your coins. Thanks.
Questions
Andrew: Time for questions. Yeah. There’s a mic over there.
Audience: Hi, is there any consideration around how old the UTXO is? Is there any preference for older UTXOs versus newer UTXOs - that time dimension when you’re choosing UTXOs?
Andrew: No, not currently. So there are some algorithms that can do that, such as the oldest first selection algorithm. But there isn’t really a benefit for choosing older or younger UTXOs. There used to be with the whole “Bitcoin Days Destroyed” thing, but that’s long since been removed. So, there isn’t any consideration for UTXO age.
Audience: Hey, I kind of had a newbie question. At what point, and sorry if you already covered this earlier, at what point do you just say, hey, we’re going to make this minor fee and not actually create a UTXO? Is there a certain amount of sats? I was just curious if there’s a discrete amount.
Andrew: So that’s what the cost of change thing is. And it’s entirely dependent on the fee rate. So, we calculate the cost in fees to make the change output at whatever the current fee rate is. And then we calculate the cost to spend that change output at a later fee rate, which we’re using just 10 satoshis per byte. So, if the current fees are really high, then that cost of change ends up being really big and you have a fairly large exact matching window. When fees are small, then the opposite is true.
Audience: So it looks like your waste metric is a pure function of the transaction. It doesn’t require any extra wallet knowledge. So you could, in principle, look at the waste of transactions on the blockchain or something. I have two questions. One is, would you add that to analyze PSBT or something like that so users can look at it if they might be doing manual selection? And the other is, has anyone looked at the historic blockchain to see if there’s any trends in terms of waste?
Andrew: So I think it’s a little bit hard to see waste for other transactions, because it’s dependent on what you want the fee rate to be because it changes what the actual fee rate is. So if you took the actual fee rate, the waste would never be like that opportunity cost value. So it’s a little bit hard to do that kind of analysis. I guess you could do something like rounding fee rates because people like nice round numbers, but automatic fee estimation will not produce nice round numbers.
Audience: So, after you roll out with 23.0 that multiple coin selection algorithms get compared, what are the next improvements that you’re going to work on?
Andrew: So, there will be some investigation of other coin selection algorithms that can be used. So, there are a lot of algorithms and there are a lot that I haven’t investigated yet. So, there will be probably just adding a few more algorithms because this metric allows us to just throw algorithms in there and choose the best one.
Audience: I had a question about cost to spend change. So, if you have multiple spending paths for that change output, how do you, if it’s not a deterministic size, how do you determine it?
Andrew: There is an assumption that the wallet knows the path it’s going to use to spend the change output. In complicated contracts where you have multiple branches, the wallet usually has one branch for it. So then that is what we assume. The wallet is also not very well structured for dealing with multi-party contracts. So this is something that can and will be improved in the future. We can also assume the worst case; so there will always be a worst case branch and we can just assume that.
Audience: So, you’re talking about using the effective, sorry, the waste metric as effectively how you rank solutions from different algorithms. I wonder, is adding just more algorithms and comparing them and picking the one with the best metric, is there any risk that that happens to still exhibit some undesirable behavior, like grinding outputs to dust or something? I assume not that. But, I guess my question is, to what extent are we sure that the waste metric actually corresponds to what we want from a coin selection algorithm?
Andrew: There has been some analysis done on it, I think. But personally, I find trying to figure out the numbers really difficult, so I just run simulations. And so, the way for me to tell is to run a lot of simulations and see and measure a lot of things including waste, but other things like minimum change and like the smallest change output, number of UTXOs and all that stuff just to see how it behaves and compares to existing algorithms. So, this is what was done to examine the waste metric change when we implemented it.
Audience: Right, and I guess the expectation is when you add more algorithms you run simulations again to see it doesn’t. Thanks.
Audience: Unless I misunderstood the consolidation fee rate, is that a constant? Are you picking that?
Andrew: It’s a user configurable value. We picked 10 because it seemed nice. But that’s the default value. It can be changed through various settings.
Audience: So I can set it to 5, compare all these algorithms and I might end up with a different result to someone who set it to 20 or something.
Andrew: Yeah, so the general idea is it’s going to be the fee rate that the user is comfortable with consolidating at. And from past experience with users, 10 seemed like a good number, but everyone’s different.
I think that’s it.