Discussion:
On-going work: Coin Selection Simulation
(too old to reply)
Murch via bitcoin-dev
2016-09-21 12:58:25 UTC
Permalink
Raw Message
Hi,

I'm currently compiling my Master's thesis about Coin Selection and my
presentation proposal to Scaling Bitcoin has been accepted.

For my thesis, I have analyzed the Coin Selection problem, created a
framework to simulate wallet behavior on basis of a sequence of
payments, and have re-implemented multiple coin selection strategies of
prominent Bitcoin wallets (Bitcoin Core, Mycelium, Breadwallet, and
Android Wallet for Bitcoin).

As the Scaling Bitcoin site suggests that research should be made
available to this mailing list, I would like to invite you to have a
look at:

http://murch.one/wp-content/uploads/2016/09/CoinSelection.pdf

The PDF (176 kB) contains a two page description of my on-going work,
including preliminary simulation results, and three figures showing the
simulated wallets' UTXO compositions at the end of the simulation.

I can provide further information as requested, and would welcome any
feedback.

→→ If anyone has another sequence of incoming and outgoing payment
amounts at hand that I could run my simulation on, I'd love to hear
about it.

Regards

Murch
Andreas Schildbach via bitcoin-dev
2016-09-21 15:02:56 UTC
Permalink
Raw Message
Post by Murch via bitcoin-dev
Android Wallet for Bitcoin
The correct name is Bitcoin Wallet, or Bitcoin Wallet for Android (if
you want to refer to the Android version).
Chris Priest via bitcoin-dev
2016-09-21 22:40:57 UTC
Permalink
Raw Message
From my experience working with coin selection algorithms, there are
three "goals" to it:

1. Minimize cost
2. Maximize privacy
3. Minimize UTXO footprint

You can build a coin selection algorithm that achieves 1 and 3, but
will sacrifice 2. If you want coin selectin to maximize your privacy,
it will happen at the expense of UTXO footprint and fees. Minimizing
cost usually also minimizes UTXO footprint but not always. To
completely minimize UTXO footprint, you sacrifice a bit on cost, and a
lot on privacy.

On 9/21/16, Andreas Schildbach via bitcoin-dev
Post by Andreas Schildbach via bitcoin-dev
Post by Murch via bitcoin-dev
Android Wallet for Bitcoin
The correct name is Bitcoin Wallet, or Bitcoin Wallet for Android (if
you want to refer to the Android version).
_______________________________________________
bitcoin-dev mailing list
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Daniel Weigl via bitcoin-dev
2016-09-22 09:33:18 UTC
Permalink
Raw Message
Hi,

Is your simulation code available somewhere?

I was just wondering why mycelium generates a very big UTXO set for <1000sat, because change outputs will never be smaller than
5460sat (=TransactionUtils.MINIMUM_OUTPUT_VALUE). If the change would be lower, it simply is skipped and added to the miner fee:
-> https://github.com/mycelium-com/wallet/blob/master/public/bitlib/src/main/java/com/mrd/bitlib/StandardTransactionBuilder.java#L334

Does your simulation account for that?

It might also be that the small UTXO came from external tx and we never spend them, bec. of pruning/privacy. Not sure how we could optimize that.

Cheers,
Daniel
Post by Murch via bitcoin-dev
Hi,
I'm currently compiling my Master's thesis about Coin Selection and my
presentation proposal to Scaling Bitcoin has been accepted.
For my thesis, I have analyzed the Coin Selection problem, created a
framework to simulate wallet behavior on basis of a sequence of
payments, and have re-implemented multiple coin selection strategies of
prominent Bitcoin wallets (Bitcoin Core, Mycelium, Breadwallet, and
Android Wallet for Bitcoin).
As the Scaling Bitcoin site suggests that research should be made
available to this mailing list, I would like to invite you to have a
http://murch.one/wp-content/uploads/2016/09/CoinSelection.pdf
The PDF (176 kB) contains a two page description of my on-going work,
including preliminary simulation results, and three figures showing the
simulated wallets' UTXO compositions at the end of the simulation.
I can provide further information as requested, and would welcome any
feedback.
→→ If anyone has another sequence of incoming and outgoing payment
amounts at hand that I could run my simulation on, I'd love to hear
about it.
Regards
Murch
_______________________________________________
bitcoin-dev mailing list
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Daniel Weigl via bitcoin-dev
2016-09-23 09:35:22 UTC
Permalink
Raw Message
Hello Murch,
I've corrected the boundary in my simulation now and will update my
simulation results before Scaling Bitcoin. Thank you very much for your
correction.
Okay, if you already had included this logic I guess it wont change the
result that much if the cut off is 4440 or 5460sat.
But Im curious to see the new results.
It is my understanding that Mycelium doesn't create small change outputs
but rather hardly ever spends them when received.
..
Mycelium appears to select UTXO in a FIFO approach, but, after the
selection, prunes by removing the smallest selected UTXO until the
excess beyond the spending target is minimized. This post-selection step
seems the likely reason for Mycelium's small UTXO build-up. (Bitcoin
Core intermittenly used post-selection pruning also, and apparently this
did cause a similar increase in UTXO set size then.)
Yes, you are correct - we added this pruning step about 2y ago to
improve privacy for the user on average. Every transaction
only links only so much inputs together as really necessary to fund
the transaction.

Our idea is to have the user the option (either global or per account or
per transaction) to choose between "maximize privacy" or "minimize fees"
(or even maybe "minimize UTXO", if the become more expensive in the future)
That will the change the behaviour of the coin selector.

Thx for your work, also looking forward to see the code and maybe play with
it a bit to test for different payment behaviours and coin selections.

Cheers,
Daniel
Hi Daniel,
Thank you for your mail.
My simulation of the Mycelium coin selection does add small change
outputs to the fee, but I did get your boundary wrong.
Instead of the 5460, I dropped at the dust boundary which calculates to
4440 in my simulation. Therefore, I think that the results in the table
might be slightly too big, but likely indicative of the actual Mycelium
behavior.
I've corrected the boundary in my simulation now and will update my
simulation results before Scaling Bitcoin. Thank you very much for your
correction.
Sorry, the simulation code has not been published yet, I plan to do that
around Scaling Bitcoin or after I turn in my thesis (End of October). I
will let you know when I do.
It is my understanding that Mycelium doesn't create small change outputs
but rather hardly ever spends them when received.
You're probably more familiar with the code base (I think you work for
Mycelium appears to select UTXO in a FIFO approach, but, after the
selection, prunes by removing the smallest selected UTXO until the
excess beyond the spending target is minimized. This post-selection step
seems the likely reason for Mycelium's small UTXO build-up. (Bitcoin
Core intermittenly used post-selection pruning also, and apparently this
did cause a similar increase in UTXO set size then.)
I assume that this will also cause Mycelium to create a huge transaction
every once in a while when this build-up is enough to fund a transaction
without a bigger UTXO being selected.
As to how it may be mitigated: BreadWallet uses a very similar FIFO
approach, but doesn't prune. My simulation result indicates that their
average UTXO set is much smaller. This has the downside that users could
be spammed with small transaction outputs that they then would pay for
spending.
A balanced approach between these two approaches might be that instead
of pruning all small inputs, a few of the small inputs could be allowed
to be selected to slowly drain low-value UTXO out of the wallet by
spending them over time. In order to avoid the privacy issues such as
e.g. always spending the oldest UTXO, it would for example be possible
to implement this as a 75% probability to prune an unnecessary output.
Regards
Murch
Post by Daniel Weigl via bitcoin-dev
Hi,
Is your simulation code available somewhere?
I was just wondering why mycelium generates a very big UTXO set for <1000sat, because change outputs will never be smaller than
-> https://github.com/mycelium-com/wallet/blob/master/public/bitlib/src/main/java/com/mrd/bitlib/StandardTransactionBuilder.java#L334
Does your simulation account for that?
It might also be that the small UTXO came from external tx and we never spend them, bec. of pruning/privacy. Not sure how we could optimize that.
Cheers,
Daniel
Post by Murch via bitcoin-dev
Hi,
I'm currently compiling my Master's thesis about Coin Selection and my
presentation proposal to Scaling Bitcoin has been accepted.
For my thesis, I have analyzed the Coin Selection problem, created a
framework to simulate wallet behavior on basis of a sequence of
payments, and have re-implemented multiple coin selection strategies of
prominent Bitcoin wallets (Bitcoin Core, Mycelium, Breadwallet, and
Android Wallet for Bitcoin).
As the Scaling Bitcoin site suggests that research should be made
available to this mailing list, I would like to invite you to have a
http://murch.one/wp-content/uploads/2016/09/CoinSelection.pdf
The PDF (176 kB) contains a two page description of my on-going work,
including preliminary simulation results, and three figures showing the
simulated wallets' UTXO compositions at the end of the simulation.
I can provide further information as requested, and would welcome any
feedback.
→→ If anyone has another sequence of incoming and outgoing payment
amounts at hand that I could run my simulation on, I'd love to hear
about it.
Regards
Murch
_______________________________________________
bitcoin-dev mailing list
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
_______________________________________________
bitcoin-dev mailing list
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Murch via bitcoin-dev
2016-10-21 14:09:57 UTC
Permalink
Raw Message
Hello Daniel and others,

A recent version of my Coin Selection Simulator is now available on my
GitHub repository:

https://github.com/Xekyo/CoinSelectionSimulator

Please feel free to write an email or open an issue on GitHub, if you
happen to find errors, have questions about using the simulator, or
(especially!) have interesting results running the simulation on your
own data.

Note that a log and a csv-table with results are posted to the console
by the simulator, so you might want to pipe that somewhere. ;)
There are probably some inefficiency issues, and user experience
improvement opportunities left as I'm currently focusing on my thesis,
yet, I've come to the conclusion that some people might be interested in
taking a look nonetheless even though I haven't gotten around to
polishing the code repository up yet.

Regards
Murch
Hi Daniel,
Thank you for your mail.
My simulation of the Mycelium coin selection does add small change
outputs to the fee, but I did get your boundary wrong.
Instead of the 5460, I dropped at the dust boundary which calculates to
4440 in my simulation. Therefore, I think that the results in the table
might be slightly too big, but likely indicative of the actual Mycelium
behavior.
I've corrected the boundary in my simulation now and will update my
simulation results before Scaling Bitcoin. Thank you very much for your
correction.
Sorry, the simulation code has not been published yet, I plan to do that
around Scaling Bitcoin or after I turn in my thesis (End of October). I
will let you know when I do.
It is my understanding that Mycelium doesn't create small change outputs
but rather hardly ever spends them when received.
You're probably more familiar with the code base (I think you work for
Mycelium appears to select UTXO in a FIFO approach, but, after the
selection, prunes by removing the smallest selected UTXO until the
excess beyond the spending target is minimized. This post-selection step
seems the likely reason for Mycelium's small UTXO build-up. (Bitcoin
Core intermittenly used post-selection pruning also, and apparently this
did cause a similar increase in UTXO set size then.)
I assume that this will also cause Mycelium to create a huge transaction
every once in a while when this build-up is enough to fund a transaction
without a bigger UTXO being selected.
As to how it may be mitigated: BreadWallet uses a very similar FIFO
approach, but doesn't prune. My simulation result indicates that their
average UTXO set is much smaller. This has the downside that users could
be spammed with small transaction outputs that they then would pay for
spending.
A balanced approach between these two approaches might be that instead
of pruning all small inputs, a few of the small inputs could be allowed
to be selected to slowly drain low-value UTXO out of the wallet by
spending them over time. In order to avoid the privacy issues such as
e.g. always spending the oldest UTXO, it would for example be possible
to implement this as a 75% probability to prune an unnecessary output.
Regards
Murch
Post by Daniel Weigl via bitcoin-dev
Hi,
Is your simulation code available somewhere?
I was just wondering why mycelium generates a very big UTXO set for <1000sat, because change outputs will never be smaller than
-> https://github.com/mycelium-com/wallet/blob/master/public/bitlib/src/main/java/com/mrd/bitlib/StandardTransactionBuilder.java#L334
Does your simulation account for that?
It might also be that the small UTXO came from external tx and we never spend them, bec. of pruning/privacy. Not sure how we could optimize that.
Cheers,
Daniel
Post by Murch via bitcoin-dev
Hi,
I'm currently compiling my Master's thesis about Coin Selection and my
presentation proposal to Scaling Bitcoin has been accepted.
For my thesis, I have analyzed the Coin Selection problem, created a
framework to simulate wallet behavior on basis of a sequence of
payments, and have re-implemented multiple coin selection strategies of
prominent Bitcoin wallets (Bitcoin Core, Mycelium, Breadwallet, and
Android Wallet for Bitcoin).
As the Scaling Bitcoin site suggests that research should be made
available to this mailing list, I would like to invite you to have a
http://murch.one/wp-content/uploads/2016/09/CoinSelection.pdf
The PDF (176 kB) contains a two page description of my on-going work,
including preliminary simulation results, and three figures showing the
simulated wallets' UTXO compositions at the end of the simulation.
I can provide further information as requested, and would welcome any
feedback.
→→ If anyone has another sequence of incoming and outgoing payment
amounts at hand that I could run my simulation on, I'd love to hear
about it.
Regards
Murch
_______________________________________________
bitcoin-dev mailing list
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
_______________________________________________
bitcoin-dev mailing list
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
_______________________________________________
bitcoin-dev mailing list
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Loading...