An analysis of dust in
UTXO based cryptocurrencies
Cristina Pérez-Solà, Sergi Delgado-Segura, Guillermo
Navarro-Arribas, Jordi Herrera-Joancomartı́
Departament d’Enginyeria de la Informació i les Comunicacions
Universitat Autònoma de Barcelona

October 6th, 2018

Introduction

1

Introduction

2

Definitions

3

Results

4

Conclusions

Definitions

Results

Conclusions

Introduction

Definitions

IntroductionA UTXO is a transaction output
that has not been spent yet.
When we talk about bitcoins weare actually referring to UTXOs.
The UTXO set is where all
UTXOs are stored. We can see it
as a wallet that includes allunspent bitcoins. No matter
their type, owner nor value.

Results

Conclusions

Introduction

Definitions

Results

Conclusions

Properties of the UTXO set

It is part of every full node.
The Bitcoin value of a UTXO does not affect its size (biggervalue != bigger size).
In general, the larger the output script of a UTXO, the more
space it occupies in the set.

Introduction

Definitions

Results

Goals and Motivation

Goals

How many unspent outputs are actually worth spending?
How much space is every full not devoting to store
not-worth-spending outputs?

Conclusions

Introduction

1

Introduction

2

Definitions
Dust
Unprofitable

3

Results

4

Conclusions

Definitions

Results

Conclusions

Introduction

Definitions

Results

Outputs worth spending

How do we know if an output is worth spending?

Conclusions

Introduction

Definitions

Results

Conclusions

Outputs worth spending

It depends on two factors:
How much data such output contributes to a new transaction
What is the fee rate we need (or want) to payIntroduction

Definitions

Results

Conclusions

Dust

Bitcoin Core dust definition

Dust
Bitcoin Core defines dust as an output that costs more in fees tospend than the value of the output.
To compute the cost of spending an output, both its size and thesize of the input are considered.
(1, outv < f ∗ (41 + 107/α + outs )is dust(out) =0, otherwise
where α is 1 for non-segwit outputs and 4 otherwise.

Introduction

Definitions

Results

Conclusions

Unprofitable

Our definition: unprofitable outputs
Unprofitable
We define an unprofitable output as the output of a transactionthat holds less value than the fee necessary to be spent, taking
into account only the size of the input that will be needed tospend it.
(1, outv < f ∗ pred ins /α
is unprofitable(out) =0, otherwise
where:
pred ins is the predicted size of the input that will spend output out.
α is 1 for non-segwit outputs and 4 otherwise.

Introduction

Definitions

Results

Conclusions

Unprofitable

Our definition: unprofitable outputs...but how do we know the size of an input before we see it?

version#inputs#outputs

nLockTime

4-bytevar size

var size

4-byteprev_tx_id

prev_out_index

scriptSig length

scriptSig

nSequence

32-byte4-bytevar size

var size

4-bytevalue

scriptPubKey length

scriptPubKey

8-bytevar size

var size

inputsoutputs

Figure: Generic transaction structureIntroduction

Definitions

Results

Conclusions

Unprofitable

Our definition: computing the minimum size

min size = f ixed size + variable size
f ixed size = outpoint + nSequence = 40 bytes
variable size = scriptSig len + scriptSig
depends on the UTXO type

Introduction

Definitions

Results

Conclusions

Unprofitable

Our definition: unprofitable outputs

Two different metrics for unprofitability:
A lower bound on unprofitability, that will take into accountthe minimum size of the input;
An estimation of unprofitability, that tries to estimate thereal unprofitable rates taking into account data available inthe blockchain.

Introduction

Definitions

Results

Conclusions

Unprofitable

Variable size: non-SegWit
Pay-to-PubKey (P2PK) outputs:
PUSH sig (1 byte) + sig (71 bytes)
Pay-to-PubkeyHash (P2PKH) outputs:
PUSH sig (1) + sig (71) + PUSH pk (1) + pk (33-65)
Pay-to-multisig (P2MS) outputs:
OP_0 (1) +(PUSH

sig (1) + sig (71)) * req_sigs (1-20)

Pay-to-ScriptHash (P2SH) outputs:∅Introduction

Definitions

Results

Unprofitable

Variable size: SegWit

Pay-to-Witness-Public-Key-Hash (P2WPKH) outputs:
PUSH sig (1) + sig (72) + PUSH pk (1) + pk (33)
Pay-to-Witness-Script-Hash (P2WSH) outputs:∅Witness scripts discounted α = 1/4

Conclusions

Introduction

Definitions

Results

Conclusions

Unprofitable

Public key sizes in the Bitcoin blockchain

Average PK size per block (P2PKH outputs)

65
60
55
Bytes

5045
40
35
0

100000200000300000
Output Height

400000500000Introduction

Definitions

Results

Unprofitable

P2SH redeem scripts in the Bitcoin blockchain

Redeem script
Number of inputs Average input size
Multisig
80,839,329
241.6
P2WPKH
7,961,073
23
P2WSH
5,544,793
35
Nonstd112,354169.98P2PK
23,557108.01
P2PKH
448
132
P2SH (Hash puzzle)
82
28.73
Total
94,481,636
210.93Conclusions

Introduction

Definitions

Results

Conclusions

Unprofitable

P2SH sizes in the Bitcoin blockchain

Avg. P2SH input script size

600500Bytes

400300200
100
0200000250000300000350000
Input Height

400000450000500000Introduction

1

Introduction

2

Definitions

3

Results

4

Conclusions

Definitions

Results

Conclusions

Introduction

Definitions

Results

Portion of UTXOs

Dust UTXOs

Fee rate (sat/byte)

Conclusions

Introduction

Definitions

Results

Port. of coins in circulation

Dust value

Fee rate (sat/byte)

Conclusions

Introduction

Definitions

Portion of UTXOs

Unprofitability evolution (Bitcoin)

Fee rate (sat/byte)

Results

Conclusions

Introduction

Definitions

Is this really that bad?

Results

Conclusions

Introduction

Definitions

Portion of UTXOs

Unprofitability evolution (Litecoin)

Fee rate (lit/byte)

Results

Conclusions

Introduction

1

Introduction

2

Definitions

3

Results

4

Conclusions

Definitions

Results

Conclusions

Introduction

Definitions

Results

Conclusions

There is a fairly big percentage of dust in the UTXO set
The current implementation of the UTXO set can growunbounded
The bigger the set gets, the less suitable it is to run a fullnode in low resource devices
Dust attacks can be performed to make the set grow

Conclusions

Introduction

Definitions

Results

ConclusionsSolutions?

There has been proposals to mitigate this (TXO commitmentsby Peter Todd)
Output consolidation when fees are low
A good coin selection algorithm is important, specially forexchanges

An analysis of dust in
UTXO based cryptocurrencies
Cristina Pérez-Solà, Sergi Delgado-Segura, Guillermo
Navarro-Arribas, Jordi Herrera-Joancomartı́
Departament d’Enginyeria de la Informació i les Comunicacions
Universitat Autònoma de Barcelona

October 6th, 2018