public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
From: Murch <murch@murch.one>
To: Daniel Weigl <Daniel.Weigl@mycelium.com>,
	Bitcoin Protocol Discussion
	<bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] On-going work: Coin Selection Simulation
Date: Fri, 23 Sep 2016 11:11:58 +0200	[thread overview]
Message-ID: <3b7ff5e7-9803-27ab-af26-df2c743f53d0@murch.one> (raw)
In-Reply-To: <1aa41a90-2cc6-36c8-d9c5-67d52befabbe@mycelium.com>

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?), so please correct me when I'm wrong:
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

Am 22.09.2016 um 11:33 schrieb 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 
> 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
> 
> On 2016-09-21 14:58, Murch via bitcoin-dev wrote:
>> 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
>>
>>
>>
>>
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev@lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> 


  reply	other threads:[~2016-09-23  9:12 UTC|newest]

Thread overview: 7+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2016-09-21 12:58 [bitcoin-dev] On-going work: Coin Selection Simulation Murch
2016-09-21 15:02 ` Andreas Schildbach
2016-09-21 22:40   ` Chris Priest
2016-09-22  9:33 ` Daniel Weigl
2016-09-23  9:11   ` Murch [this message]
2016-09-23  9:35     ` Daniel Weigl
2016-10-21 14:09     ` Murch

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=3b7ff5e7-9803-27ab-af26-df2c743f53d0@murch.one \
    --to=murch@murch.one \
    --cc=Daniel.Weigl@mycelium.com \
    --cc=bitcoin-dev@lists.linuxfoundation.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox