Simulation-based Evaluation of Coin Selection
Strategies
Scaling Bitcoin: Retarget
Mark Erhardt | October 9, 2016

INSTITUTE OF TELEMATICS

KIT – The Research University in the Helmholtz Associationwww.kit.edu

Outline

1Motivation

2

Coin Selection

3

Framework

4

Simulation

5

Conclusion

Motivation

Coin Selection

Mark Erhardt – Coin Selection Simulation

Framework

Simulation
October 9, 2016

Conclusion
2/16

UTXO Set Growth[Wuille, 2016]

What’s the issue with the growth?
UTXO set kept in RAM by miners
average UTXO value:
0.97 BTC (2014), 0.44 BTC (2015), 0.38 BTC (2016)
MotivationCoin Selection

Mark Erhardt – Coin Selection Simulation

Framework

Simulation
October 9, 2016

Conclusion
3/16

UTXO Set Growth×2 since last year

[Wuille, 2016]

What’s the issue with the growth?
UTXO set kept in RAM by miners
average UTXO value:
0.97 BTC (2014), 0.44 BTC (2015), 0.38 BTC (2016)
Motivation

Coin Selection

Mark Erhardt – Coin Selection Simulation

Framework

Simulation
October 9, 2016

Conclusion
3/16

UTXO Set Growth×2 since last year
×7 in three years[Wuille, 2016]

What’s the issue with the growth?
UTXO set kept in RAM by miners
average UTXO value:
0.97 BTC (2014), 0.44 BTC (2015), 0.38 BTC (2016)
Motivation

Coin Selection

Mark Erhardt – Coin Selection Simulation

Framework

Simulation
October 9, 2016

Conclusion
3/16

UTXO Set Growth×2 since last year
×7 in three years[Wuille, 2016]

What’s the issue with the growth?
UTXO set kept in RAM by miners
average UTXO value:
0.97 BTC (2014), 0.44 BTC (2015), 0.38 BTC (2016)
Motivation

Coin Selection

Mark Erhardt – Coin Selection Simulation

Framework

Simulation
October 9, 2016

Conclusion
3/16

UTXO Set Growth×2 since last year
×7 in three years[Wuille, 2016]

What’s the issue with the growth?
UTXO set kept in RAM by miners
average UTXO value:
0.97 BTC (2014), 0.44 BTC (2015), 0.38 BTC (2016)
Motivation

Coin Selection

Mark Erhardt – Coin Selection Simulation

Framework

Simulation
October 9, 2016

Conclusion
3/16

Coin Selection

How to choose which outputs to spend?

Motivation

Coin Selection

Mark Erhardt – Coin Selection Simulation

Framework

Simulation
October 9, 2016

Conclusion
4/16

Coin Selection

How to choose which outputs to spend?
Hypothesis: Improved Coin Selection can reduce UTXO Set.

Motivation

Coin Selection

Mark Erhardt – Coin Selection Simulation

Framework

Simulation
October 9, 2016

Conclusion
4/16

Hard Constraints and Goals

Constraints for Coin Selection
available UTXO poolprovide sufficient funds for payment and fee
no dust outputs

Goals
Minimize fees
Reduce UTXO set
Privacy

Motivation

Coin Selection

Mark Erhardt – Coin Selection Simulation

Framework

Simulation
October 9, 2016

Conclusion
5/16

Hard Constraints and Goals

Constraints for Coin Selection
available UTXO poolprovide sufficient funds for payment and fee
no dust outputs

Goals
Minimize fees
Reduce UTXO set
Privacy

Motivation

Coin Selection

Mark Erhardt – Coin Selection Simulation

Framework

Simulation
October 9, 2016

Conclusion
5/16

Conditions and Factors

Changing Conditions
Priority → fee-market
Blockspace demand

Influential Factors
Payment sizes
Short-term fees vs long-term fees
Ratio of incoming and outgoing payments
Size of newly generated changes

Motivation

Coin Selection

Mark Erhardt – Coin Selection Simulation

Framework

Simulation
October 9, 2016

Conclusion
6/16

Conditions and Factors

Changing Conditions
Priority → fee-market
Blockspace demand

Influential Factors
Payment sizes
Short-term fees vs long-term fees
Ratio of incoming and outgoing payments
Size of newly generated changes

Motivation

Coin Selection

Mark Erhardt – Coin Selection Simulation

Framework

Simulation
October 9, 2016

Conclusion
6/16

Some Ideas for Improvement
Strategy Ideas
Changes of average target size (proposed by Luke-Jr in IRC)
Add tiny change outputs to fee
Target sized change outputs
Random inputs

Motivation

Coin Selection

Mark Erhardt – Coin Selection Simulation

Framework

Simulation
October 9, 2016

Conclusion
7/16

Some Ideas for Improvement
Strategy Ideas
Changes of average target size (proposed by Luke-Jr in IRC)
Add tiny change outputs to fee
Target sized change outputs
Random inputs

Motivation

Coin Selection

Mark Erhardt – Coin Selection Simulation

Framework

Simulation
October 9, 2016

Conclusion
7/16

Some Ideas for Improvement
Strategy Ideas
Changes of average target size (proposed by Luke-Jr in IRC)
Add tiny change outputs to fee
Target sized change outputs
Random inputs

Motivation

Coin Selection

Mark Erhardt – Coin Selection Simulation

Framework

Simulation
October 9, 2016

Conclusion
7/16

Some Ideas for Improvement
Strategy Ideas
Changes of average target size (proposed by Luke-Jr in IRC)
Add tiny change outputs to fee
Target sized change outputs
Random inputs

Motivation

Coin Selection

Mark Erhardt – Coin Selection Simulation

Framework

Simulation
October 9, 2016

Conclusion
7/16

Some Ideas for Improvement
Strategy Ideas
Changes of average target size (proposed by Luke-Jr in IRC)
Add tiny change outputs to fee
Target sized change outputs
Random inputs
How to evaluate?

Motivation

Coin Selection

Mark Erhardt – Coin Selection Simulation

Framework

Simulation
October 9, 2016

Conclusion
7/16

CoinSelectionSimulator

Considers:
Selection policy
FeesTransaction format(P2PKH or P2WPKH)
Block height
Doesn’t consider (yet):Addresses

Motivation

Coin Selection

Mark Erhardt – Coin Selection Simulation

Framework

Simulation
October 9, 2016

Conclusion
8/16

Some Policies In Use (1/3)
Oldest First
FIFO
Add change outputs below DustLimit to fee
BreadWallet, Electrum

Pruned Oldest First
FIFO
Post-selection pruning of smallest inputs
Add change outputs below 5460 satoshis to fee
Mycelium

Motivation

Coin Selection

Mark Erhardt – Coin Selection Simulation

Framework

Simulation
October 9, 2016

Conclusion
9/16

Some Policies In Use (1/3)
Oldest First
FIFO
Add change outputs below DustLimit to fee
BreadWallet, Electrum

Pruned Oldest First
FIFO
Post-selection pruning of smallest inputs
Add change outputs below 5460 satoshis to fee
Mycelium

Motivation

Coin Selection

Mark Erhardt – Coin Selection Simulation

Framework

Simulation
October 9, 2016

Conclusion
9/16

More Policies in Use (2/3)

Highest Priority First
Sorted by priority (age×value)
BitcoinJ, Bitcoin Wallet for AndroidTarget Sized Changen randomly drawn buckets of inputs
Select bucket that minimizes δ(change, target )Electrum Private Mode (not implemented yet in Simulation)

Motivation

Coin Selection

Mark Erhardt – Coin Selection Simulation

Framework

Simulation
October 9, 2016

Conclusion
10/16

More Policies in Use (2/3)

Highest Priority First
Sorted by priority (age×value)
BitcoinJ, Bitcoin Wallet for Android

Target Sized Changen randomly drawn buckets of inputs
Select bucket that minimizes δ(change, target )Electrum Private Mode (not implemented yet in Simulation)

Motivation

Coin SelectionMark Erhardt – Coin Selection Simulation

Framework

Simulation
October 9, 2016

Conclusion
10/16

Bitcoin Core’s Policy (3/3)

Avoid Change or Large
Changeattempts direct match
pseudo-random
knapsack algorithm
minimum change of
0.01 BTC
Bitcoin Core

Motivation

Coin Selection

Mark Erhardt – Coin Selection Simulation

Framework

Simulation
October 9, 2016

Conclusion
11/16

Simulation Scenario

Transaction data from moneypot.com[Havar, 2015]
24,388 incoming payments
11,860 outgoing payments
Other experiments:
moneypot.com incoming
condensed
Gaussian generated payments

Motivation

Coin SelectionMark Erhardt – Coin Selection Simulation

Framework

Simulation
October 9, 2016

Conclusion
12/16

Simulation Results

Policy∅ #UTXO∅ change [mBTC]

total cost [mBTC]∅ #inputs

FIFO
Pruned FIFO
Highest Priority"Core"

182.87763.73
2 551.52
180.30399.62169.93789.5231.75

629.07623.39629.05819.03

3.03
2.91
2.50
3.05

Results are highly scenario dependent!

Observations
FIFO maintains almost as few UTXO as Core
Pruned FIFO and Highest Priority accumulate small UTXO
Bitcoin Core: overpays fees, computationally expensive, only ≈ 0.5%
Direct Matches (63 of 11860)
Motivation

Coin Selection

Mark Erhardt – Coin Selection Simulation

Framework

Simulation
October 9, 2016

Conclusion
13/16

Simulation Results

Policy∅ #UTXO∅ change [mBTC]

total cost [mBTC]∅ #inputs

FIFO
Pruned FIFO
Highest Priority"Core"

182.87763.73
2 551.52
180.30399.62169.93789.5231.75

629.07623.39629.05819.03

3.03
2.91
2.50
3.05

Results are highly scenario dependent!

Observations
FIFO maintains almost as few UTXO as Core
Pruned FIFO and Highest Priority accumulate small UTXO
Bitcoin Core: overpays fees, computationally expensive, only ≈ 0.5%
Direct Matches (63 of 11860)
Motivation

Coin Selection

Mark Erhardt – Coin Selection Simulation

Framework

Simulation
October 9, 2016

Conclusion
13/16

Simulation Results

Policy∅ #UTXO∅ change [mBTC]

total cost [mBTC]∅ #inputs

FIFO
Pruned FIFO
Highest Priority"Core"

182.87763.73
2 551.52
180.30399.62169.93789.5231.75

629.07623.39629.05819.03

3.03
2.91
2.50
3.05

Results are highly scenario dependent!

Observations
FIFO maintains almost as few UTXO as Core
Pruned FIFO and Highest Priority accumulate small UTXO
Bitcoin Core: overpays fees, computationally expensive, only ≈ 0.5%
Direct Matches (63 of 11860)
Motivation

Coin Selection

Mark Erhardt – Coin Selection Simulation

Framework

Simulation
October 9, 2016

Conclusion
13/16

Histogram of final UTXO pools

Motivation

Coin Selection

Mark Erhardt – Coin Selection Simulation

Framework

Simulation
October 9, 2016

Conclusion
14/16

Simulation Results other strategies

Policy∅ UTXO∅ change [mBTC]

total cost [mBTC]∅ #inputs

Average TargetWider Match Donation
Double Target
Single Random Draw (No MC)
Single Random Draw (0.01 BTC)

137.89165.24225.00185.16173.27207.3732.95
198.39384.43424.15767.08829.38832.41
629.13628.98

3.04
3.02
3.03
3.03
3.04

Core

180.3031.75

819.03

3.05

Motivation

Coin Selection

Mark Erhardt – Coin Selection Simulation

Framework

Simulation
October 9, 2016

Conclusion
15/16

Simulation Results other strategies

Policy∅ UTXO∅ change [mBTC]

total cost [mBTC]∅ #inputs

Average Target
Wider Match Donation
Double Target
Single Random Draw (No MC)Single Random Draw (0.01 BTC)

137.89165.24225.00185.16173.27207.3732.95
198.39384.43424.15767.08829.38832.41
629.13628.98

3.04
3.02
3.03
3.03
3.04

Core

180.3031.75

819.03

3.05

Average Target
Bitcoin Core’s selection
MIN_CHANGE is mean target
proposed by Luke-Jr
Motivation

Coin Selection

Mark Erhardt – Coin Selection Simulation

Framework

Simulation
October 9, 2016

Conclusion
15/16

Simulation Results other strategies

Policy∅ UTXO∅ change [mBTC]

total cost [mBTC]∅ #inputs

Average Target
Wider Match Donation
Double TargetSingle Random Draw (No MC)
Single Random Draw (0.01 BTC)

137.89165.24225.00185.16173.27207.3732.95
198.39384.43424.15767.08829.38832.41
629.13628.98

3.04
3.02
3.03
3.03
3.04

Core

180.3031.75

819.03

3.05

Wider Match Donation
Bitcoin Core’s selection
Range of +(0, DustLimit ) = Direct Match
Add change up to Dust Limit to fee
Motivation

Coin Selection

Mark Erhardt – Coin Selection Simulation

Framework

Simulation
October 9, 2016

Conclusion
15/16

Simulation Results other strategies

Policy∅ UTXO∅ change [mBTC]

total cost [mBTC]∅ #inputs

Average Target
Wider Match Donation
Double Target
Single Random Draw (No MC)
Single Random Draw (0.01 BTC)

137.89165.24225.00185.16173.27207.3732.95
198.39384.43424.15767.08829.38832.41
629.13628.98

3.04
3.02
3.03
3.03
3.04

Core

180.3031.75

819.03

3.05

Double Target
Bitcoin Core’s selection
MIN_CHANGE = target

Motivation

Coin Selection

Mark Erhardt – Coin Selection Simulation

Framework

Simulation
October 9, 2016

Conclusion
15/16

Simulation Results other strategies

Policy∅ UTXO∅ change [mBTC]

total cost [mBTC]∅ #inputs

Average Target
Wider Match Donation
Double Target
Single Random Draw (No MC)
Single Random Draw (0.01 BTC)

137.89165.24225.00185.16173.27207.3732.95
198.39384.43424.15767.08829.38832.41
629.13628.98

3.04
3.02
3.03
3.03
3.04

Core

180.3031.75

819.03

3.05

Single Random Draw
Shuffle UTXO pool, pop front until sufficient once
Equi-probably selection
No MIN_CHANGE, MIN_CHANGE = 0.01 BTC
Motivation

Coin Selection

Mark Erhardt – Coin Selection Simulation

Framework

Simulation
October 9, 2016Conclusion
15/16

Conclusion
Presented:
Examined Coin Selection Strategies
Identified improvement opportunities for several prevalent strategies
Simulation Framework:https://github.com/Xekyo/CoinSelectionSimulator (late October!)
Future Work:
Addresses
Privacy
Only one Scenario: Additional scenario data welcome!

Motivation

Coin Selection

Mark Erhardt – Coin Selection Simulation

Framework

Simulation
October 9, 2016

Conclusion
16/16

Conclusion
Presented:
Examined Coin Selection Strategies
Identified improvement opportunities for several prevalent strategies
Simulation Framework:https://github.com/Xekyo/CoinSelectionSimulator (late October!)Future Work:
Addresses
Privacy
Only one Scenario: Additional scenario data welcome!
Thank you for your attention!

Motivation

Coin Selection

Mark Erhardt – Coin Selection Simulation

Framework

Simulation
October 9, 2016

Conclusion
16/16

References I

Havar, R. (2015).
Issue#1643: Coinselection prunes extraneous inputs fromApproximateBestSubset.
[Online, retrieved on 2016-08-18].
Wuille, P. (2016).
UTXO breakdown per output amount.
[Online, retrieved on 2016-07-13].

Mark Erhardt – Coin Selection Simulation

October 9, 2016

17/16

Privacy

Addresses easy to model
But:Taint or Value privacy?
How to measure privacy?
Simulation of Address behavior whole new problem

Mark Erhardt – Coin Selection Simulation

October 9, 2016

18/16

Framework Features and Limits
Features:
Queuing of Outgoing Payments when insufficient Funds
nLockTime for each Payment
Fee estimation
Multiple Wallets in parallel
Extensive statistics:
final value, mean #UTXO, final #UTXO, #received, #spent, #changes
created, smallest change, biggest change, mean change, stDev ofchange, in transit ratio, total fees, average fees, fees to spend
remaining UTXO, total cost, smallest input set, biggest input set,mean size of input set, stdev of input set size, final UTXO set
But:No Addresses
nLockTime so far only simple Gaussian interval
Results highly scenario dependent
Mark Erhardt – Coin Selection Simulation

October 9, 2016

19/16

Core Improvement Opportunities

Skip useless iteration with zero fee.
Estimate fee respective to selected set
Direct Match only occurs in 63 of 11,860 cases. (Pruned FIFO: 725)
→ Less emphasis.

Mark Erhardt – Coin Selection Simulation

October 9, 2016

20/16

Mycelium DustLimit vs 5460

PolicyPruned FIFO (5460)
Pruned FIFO (DustLimit)∅ #UTXO

Final #UTXO∅ change [mBTC]

total cost [mBTC]∅ #inputs

763.73774.30

1,013
1,097

169.93
170.44623.39633.73

2.91
2.91

Mark Erhardt – Coin Selection Simulation

October 9, 201621/16