How Big a Problem Is Dust for Bitcoin?

This is a transcript of Sergi Delgado-Segura’s presentation at Master Workshop: Layer 1 solutions, which took place at Primalbase AMS.

Today, I’m going to talk to you about fees and dust. This is part of a shared work at the Autonomous University of Barcelona where I did my PhD. Here, I am going to focus on dust, but if you want to get a bigger picture of the analysis and so on, you can check the paper online.

I would like to start the talk by asking you a question. What comes to your mind when you think about scalability issues within blockchain? What comes to my mind are transactions per second — how many transactions a currency is able to process. Another important issue is how much data we have to keep in order to run these blockchains. For example, with Bitcoin we are talking around 200 GB, and there are other things we have to take into account. This is basically what we are going to talk about today.

As we’re talking about dust, we need to talk about fees first. First, what are fees? Fees in transactions are the difference between the sum of all inputs and all outputs. They can be collected by miners when they are including the transactions in the new blocks. In the meantime, all those transactions will sit in the mempool of the nodes waiting to be included. So, if there are more transactions in the mempool than a block can fit, who will decide the order of the inclusion of those transactions?

As you know, it is miners. Therefore, fees can be seen as an incentive for miners to include our transactions first instead of other ones. Then, since the block size is limited, the ‘better’ the fee, the more likely your transaction is to be included. But here comes another question: does better mean higher? As we will see in this talk, the actual answer is ‘not always’.

What Do We Need to Calculate the Fees of a Transaction?

There are basically two factors that matter here. The first is the transaction size — the bigger the size, the bigger the fees. Then we have the fee rate at the moment of creating the transaction.

Speaking of transaction size, here we have a high-level representation of a transaction. Don’t worry, we are going to come back to this later, so you don’t need to learn everything about it. What I would like you to note here for now is that there are some fixed-size parameters that are always going to be the same size, and there are others that will depend on the transaction that we are creating. Depending on the type of the transaction we create, the size will be different.

Regarding the fee rate, this is also a highly valuable factor. It depends on the transaction by luck. This is the number of transactions that are sitting in the mempool waiting to be included. So, what we need to know here is that the two factors that matter when we are talking about fees are highly valuable and will depend on the state of the network.

At this point, you may think ‘alright, but what will happen if the value of a transaction is really low compared to the size of it. Or what will happen if the fees for a transaction at a certain point are too high. Here is where dust comes into play.

What is Dust?

Dust is a definition coined by the Bitcoin core, as far as I know. It is computed in terms of output instead of in terms of transactions. Basically, what the definition says is that an output will be seen as dust if the value the output is holding is lower than the fees required to spend it. Therefore, again, dust depends on the state of the network.

You may ask here, ‘If I have a dust transaction or a transaction without dust output, does it mean that the transaction is invalid?’ Well, there is a lot of misunderstanding here, or misconception. The answer to this question is no, that’s not how it is. How it works is that if a node sees a transaction as being dust, they will not propagate those transactions — Bitcoin core nodes, so we are talking about a specific implementation of a node. This doesn’t mean that a transaction is invalid.

If a miner receives this transaction and decides to include it in a block, it will be completely good, there is no problem with it. The block will not be invalid. The thing is that there is a big difference between what are relay roles and what are consensus roles. However, they were half way right, because the actual suspects for dust are really low value outputs.

Can We Flag Uneconomical Outputs?

At this point, we know what fees and dust are, so can we flag uneconomical outputs? The answer is yes, we can. We can do it by analysing the Unspent Transaction Outputs (UTXO) set. Every single Bitcoin full node or Bitcoin core node needs to store this set and every UTXO will be an entry in the set. This means the more UTXOs, the bigger the set.

The thing here is that the value doesn’t have anything to do with the size. So, a bigger value doesn’t imply a bigger size. In general terms, the bigger the script the output is holding, the bigger the size of the entry, and therefore the bigger the set. Knowing this, we can analyse a set, and by doing so we can mark which outputs will be uneconomical and which ones will be worth spending. The other positive thing here is that, since there are a lot of Bitcoin forks (in terms of software), by sticking to the representation of the UTXO set followed by the core, we can use the same tool to analyse all of them.

So we did. We created a tool called status, which stands for Statistical Analysis Tool for UTXO Set. It’s an open source tool — you’ll find it on Github. It’s coded in Python and it provides an easy way to access, decode and analyse data from the UTXO set.

How Many UTXOs Are Actually Worth Spending?

Ok, so we have our tool, we have our definitions, what are the questions we are trying to answer here? The first one is, how many UTXOs are actually worth spending? And the other one, an important one, is how much space is wasted by outputs that are not worth it? How much space is every single node wasting just because they have to store this kind of output.

We are going to use two metrics here. The first one we have already been into a little bit, which is dust, and the other one will be unprofitable. Both are metrics that are defined in terms of output, but are computed using different approaches. So, here comes the maths. It’s going to be quick and it’s going to be fairly easy so don’t panic. In order to compute dust, the core uses the output we are checking, and they take that into account. They also use an input from a P2PKH. So, an output can be seen as dust if the value the output is holding is lower than the fee rate multiplied by the input.

We have also coined the definition of the ‘unprofitable outputs’. It’s similar but different. Here, we are only using the input that will spend the output we are checking. So, basically, since we need to create an input for every kind of output, what matters for us is the input we are going to create. In order to do so, we are checking more of the same, so if the output value is lower than the fee rate multiplied by the predicted input, then we will see that the input is unprofitable. Otherwise, we will say that it’s not.

As you may see here, we need a way of predicting this input size. How can we do it? Well, if you recall the transaction structure I was talking about earlier, we have some fixed sized parameters and we have some variable ones.

Since we are only looking at the input, we have the outpoint which counts previous transaction ID at the output, and then the nSequence. All those are going to be 40 bytes, it doesn’t matter about the type of input. Then, we have the variable size, which will account for the input script and the size of the script. This will highly depend on the type of input we are creating, on the UTXO type.

There are two approaches here. The first one talks about non-SegWit inputs and the other one about SegWit. If we check the non-SegWit, the traditional ones, we have Pay-to-PubKey, in which we have to take into account a data PUSH, which is one byte, and the signature, which can be between 71 and 73 bytes long. Then we have Pay-to-PubKeyHash (P2PKH) — which has two data PUSHs, the signature again and then the public key, which can be either compressed or uncompressed. If it’s compressed it will be 33 bytes and if it is uncompressed it’ll be 65.

Pay-to-multisig (P2MS) is more or less the same. Op_0, then we have the PUSH, then the signature, times the number of signatures we have here. If we have three, it will be multiplied by three and so on. Finally, we have Pay-to-ScriptHash (P2SH). Here we have an issue. When we check a P2SH script, we don’t know exactly what is going on in there. We know what the hash of the script is but we don’t know what the script was that created this hash. So, there’s no way we can know how long the input is which spends that output.

Regarding SegWit, this is quite similar. We have the Pay-to-Witness-Public-Key-Hash (P2WPKH), in which again we have a PUSH, the signature and a public key. In this case, the public key has to always be compressed. And, regarding Pay-to-Witness-ScriptHash (P2WSH), it’s exactly the same as with P2SH.

Seeing this, we decided to split the non-profitable metric in two. The first one, what we will do is to take a minimum number of signatures, which will be 71, and then for the data we don’t know, we will simply not count it. So, for Pay-to-ScriptHash scripts, we will only count the fixed part and count the variable part as 0. Then, we will have a different one, which is definitely better in this case, because we will try to predict as well as possible how long the size will be. Basically, we will take 72 bytes here, because it’s the most likely signature length, and for the data we don’t know, we will take data from the blockchain.

Here (below), you can see some charts of the size of the public keys. We can see how, at the beginning, it was uncompressed, then it goes down. So, what we do when we are analysing one output, we check the height of the block at which it was included, then we check what the average of that size was and we count that.

Now, we have all the definitions, all the methods, so it’s the right time to talk about results. In this chart (below), we can see the three metrics: dust in blue, non-profitable estimation in green, and then the lower bound in dotted orange. What we have in the axis are the portions of UTXOs that are dust or non-profitable, and then in the X we have the fee rate. We’ve tried to use a wide fee range in order to see what will happen depending on which fee it used at the current time.

This data is from around February this year, when we performed the analysis. We can see how, for around 50% of the UTXOs in the set, at 0.5, we are around 115 on the X axis. What this means, is that for around 115 satoshis onwards, more than 50% of the UTXOs are dust or non-profitable. If we check which values these account for, of all the Bitcoins in circulation at the time, we can see that 115 is a tiny, tiny amount, around 0.00015% of the total value of the coin — almost nothing.

What This Means for Bitcoin

What are the implications of this? The implications are that more or less than half of the UTXOs in the set are dust for around 100–125 Satoshis per byte — around three million UTXOs. In terms of size, we are talking about 1.7 GB of data which are dust for this range. In terms of value, we are talking almost nothing. So, basically, the whole picture here is that almost nothing in value is occupying half of the size of the UTXO set. Don’t get me wrong, this is a lot of money. We’re talking about 252,000 Bitcoin. In terms of money, it’s big, but in terms of every singe Bitcoin in circulation at the time it’s not that much.

If you think that, ‘alright, that was just one snapshot’, so it could be better, this is just one example. The bad news is that it’s not. If we check the evolution, that’s been going on for quite a while. The thing is that now, we are getting to a point at which this can actually be a problem. It could be worse — if we check the 400k snapshot (below), we can see that there was way more dust in the lower bounds. This was really bad and it was corrected, so at that point we are not as bad as we could be.

However, this could be a lot worse. If you don’t believe me, one of the analyses we have also performed has been done in Litecoin. Litecoin is definitely the extreme case because there, around 75% of the UTXOs in the set are dust for around 1 Litoshi per byte. This is because around 50% of the UTXOs in the set are actually worth exactly 1 Litoshi, due to a spam attack that happened around 2011/2012.

Charlie Lee did quite a cool thing raising awareness about it to the community of Litecoin and asking their opinion about what they should do. In my opinion, the results are quite even, and there are not that many people that actually responded to the poll, but at least he talks about it. It’s like, ‘this has happened, we can do things if you like, so what’s your opinion?’ I don’t think that they will get rid of these, because that will imply all kinds of problems in terms of censorship and so on, but at least they talked about it.

Conclusion

We have seen that a fairly big percentage of the UTXO set is dust for different currencies. This is a problem since the current implementation of the UTXO set can grow unbounded. The bigger the set, the less suitable it is for nodes to run in optimal conditions. Think that when miners are trying to verify transactions, they hold the UTXO set in RAM, because it’s way faster. If you have to waste 1.7 to 3 GBs of RAM storing things that are not likely to be spent, you have a problem.

Finally, spam attacks can be performed to make the set grow. If we think about Bitcoin here, it will take a lot of money to do it, but it could happen. It only takes someone with enough incentive and willingness to spend the money to make it grow.

Solutions

There are a few solutions I know of. The first one I heard about was by Peter Todd, called TXO commitments, and it has been floating around for a while even though I think it hasn’t been implemented yet. There’s also the high-performance merkle set by Bram Cohen, which I think has been implemented in one coin but I’m not completely sure. Most recently, we have heard about RSA accumulators by Benedikt Bünz and Dan Boneh — I haven’t seen the paper yet because they talk about this at Scaling Bitcoin and I think the paper isn’t available yet, but I’m definitely looking forward to checking it. And, at Scaling Bitcoin, Tadge Dryja talked about UTXO accumulators, which was a similar construction but again, I just heard a talk, I haven’t seen the paper. There may be more, I don’t know. If I’m missing someone and you know about it, please tell me.

To conclude, what can we do about it? There are two things I think we can do. The first one is output consolidation when the fees are low, like now. If you can know your outputs and there are outputs that are likely to be dust in the near future, if the fees go up, you can do it. Then, please, if you’re from an exchange and you’re moving a lot of Bitcoins, use a good coin selection algorithm in order to avoid generating more dust.

Q&A

It sounds to me like there have been these uneconomic transactions, that are just part of the UTXO dataset, filling up space, wasting it potentially — what do you think we should do about it? Should we delete them? Can we delete them?

Not really. That’s actually part of what Charlie Lee asked in his post. I think that the actual approach will be looking to the solutions like Benedikt is creating, or Tadge is looking for. Try to have an accumulated state of the UTXO set that nodes can store, but they don’t need to select the whole thing, and they can verify everything just with proof and the accumulative state.

The thing is, if you just try to delete it, you are censoring some outputs. So, the bigger idea here is not your Bitcoin or your Litecoin — if it’s not yours and it’s in there, you just keep it, that’s how it works. If you don’t do it, if you take it out, then it was not yours, so why are you putting your hands in something that isn’t yours. That’s why I think that they are not going to change it, or just throw it out, because the implications are way worse than just wasting some space.

I remember Coinbase had this problem. They had something like 1.5 million outputs per every 265 Bitcoin, which was really criticised in the community. But there’s actually a privacy tradeoff. So, the idea is that if I have 1.5 million outputs, you don’t know they belong to me, I combine them into a single output and now you can say they all belong to the same person. So, do accumulators help with that in terms of privacy?

I really don’t know. Benedikt was talking about the accumulators and so on. He talks about the construction, and that could be applied to the current state of the UTXO set, but I don’t think he talks about the implications of it. I don’t know exactly the construction. It’s something I should read.

It would be worth finding out if it’s user-initiated or it was initiated by the network. That would obviously help with the privacy if it was done by the network.

Yes, I recall the thing that you said with Litecoin. That was actually in one of the higher peaks for the fees, so fees were very high at that time, and they had a lot of UTXOs that everyone has to sort. So they couldn’t get rid of them, because they handled the coin selection in a bad way, and they were generating a lot of dust.

So, this model is dependent on a UTXO-based model, but is it similar in Ethereum?

No, not really, because you don’t need to hold the UTXOs in that part. There are other problems in there, like having to store or keep track of the balances of accounts that aren’t used, but it’s completely different in this sense. There’s no dust in that case. Since dust is paid in terms of the output you’re using, what can happen is that when you use an output, you need to pay more than what the output is giving you. Then you’re in a situation where you keep adding money but you need to pay more money — this doesn’t happen in Ethereum, fortunately.

Is there any information whether these UTXOs are abandoned or just unfeasible?

That’s actually a really good question. The thing is that you’ll know, because just by checking the UTXOs, you can check if that database has been used recently. But, if you follow every single recommendation by Bitcoin, you shouldn’t reuse databases, right? So, there could be a lot of UTXOs that are in the set, sitting there for a long time, but you don’t know if those keys have been lost. If not, you have no information about it. If the keys have been used recently, you can know that someone had them, but if not, maybe they are just holding.