📅 Original date posted:2016-10-21
📝 Original 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
Am 23.09.2016 um 11:11 schrieb Murch via bitcoin-dev:
> 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 at lists.linuxfoundation.org
>>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>>
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev at lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
Murch [ARCHIVE] /
npub148…ftkk4
2023-06-07 17:54:09
in reply to nevent1q…c47h
Author Public Key
npub148nv6ef02rzspkm4wszntt77m9k80plvtgaxwrg9amxch2cmge0qxftkk4Published at
2023-06-07 17:54:09Event JSON
{
"id": "49d5aa65edfade9e95aa37bcebc0d5ff5d25ffb10da15fecadc8e080b251497a",
"pubkey": "a9e6cd652f50c500db75740535afded96c7787ec5a3a670d05eecd8bab1b465e",
"created_at": 1686160449,
"kind": 1,
"tags": [
[
"e",
"1bcbde40ed9d00edfd9977763b821d520450ea8d63eea18aade7f4168c277ff3",
"",
"reply"
],
[
"p",
"a23dbf6c6cc83e14cc3df4e56cc71845f611908084cfe620e83e40c06ccdd3d0"
]
],
"content": "📅 Original date posted:2016-10-21\n📝 Original message:Hello Daniel and others,\n\nA recent version of my Coin Selection Simulator is now available on my\nGitHub repository:\n\nhttps://github.com/Xekyo/CoinSelectionSimulator\n\nPlease feel free to write an email or open an issue on GitHub, if you\nhappen to find errors, have questions about using the simulator, or\n(especially!) have interesting results running the simulation on your\nown data.\n\nNote that a log and a csv-table with results are posted to the console\nby the simulator, so you might want to pipe that somewhere. ;)\nThere are probably some inefficiency issues, and user experience\nimprovement opportunities left as I'm currently focusing on my thesis,\nyet, I've come to the conclusion that some people might be interested in\ntaking a look nonetheless even though I haven't gotten around to\npolishing the code repository up yet.\n\nRegards\nMurch\n\nAm 23.09.2016 um 11:11 schrieb Murch via bitcoin-dev:\n\u003e Hi Daniel,\n\u003e \n\u003e Thank you for your mail.\n\u003e My simulation of the Mycelium coin selection does add small change\n\u003e outputs to the fee, but I did get your boundary wrong.\n\u003e Instead of the 5460, I dropped at the dust boundary which calculates to\n\u003e 4440 in my simulation. Therefore, I think that the results in the table\n\u003e might be slightly too big, but likely indicative of the actual Mycelium\n\u003e behavior.\n\u003e I've corrected the boundary in my simulation now and will update my\n\u003e simulation results before Scaling Bitcoin. Thank you very much for your\n\u003e correction.\n\u003e \n\u003e Sorry, the simulation code has not been published yet, I plan to do that\n\u003e around Scaling Bitcoin or after I turn in my thesis (End of October). I\n\u003e will let you know when I do.\n\u003e \n\u003e It is my understanding that Mycelium doesn't create small change outputs\n\u003e but rather hardly ever spends them when received.\n\u003e \n\u003e You're probably more familiar with the code base (I think you work for\n\u003e Mycelium?), so please correct me when I'm wrong:\n\u003e Mycelium appears to select UTXO in a FIFO approach, but, after the\n\u003e selection, prunes by removing the smallest selected UTXO until the\n\u003e excess beyond the spending target is minimized. This post-selection step\n\u003e seems the likely reason for Mycelium's small UTXO build-up. (Bitcoin\n\u003e Core intermittenly used post-selection pruning also, and apparently this\n\u003e did cause a similar increase in UTXO set size then.)\n\u003e \n\u003e I assume that this will also cause Mycelium to create a huge transaction\n\u003e every once in a while when this build-up is enough to fund a transaction\n\u003e without a bigger UTXO being selected.\n\u003e \n\u003e As to how it may be mitigated: BreadWallet uses a very similar FIFO\n\u003e approach, but doesn't prune. My simulation result indicates that their\n\u003e average UTXO set is much smaller. This has the downside that users could\n\u003e be spammed with small transaction outputs that they then would pay for\n\u003e spending.\n\u003e A balanced approach between these two approaches might be that instead\n\u003e of pruning all small inputs, a few of the small inputs could be allowed\n\u003e to be selected to slowly drain low-value UTXO out of the wallet by\n\u003e spending them over time. In order to avoid the privacy issues such as\n\u003e e.g. always spending the oldest UTXO, it would for example be possible\n\u003e to implement this as a 75% probability to prune an unnecessary output.\n\u003e \n\u003e Regards\n\u003e Murch\n\u003e \n\u003e Am 22.09.2016 um 11:33 schrieb Daniel Weigl via bitcoin-dev:\n\u003e\u003e Hi,\n\u003e\u003e\n\u003e\u003e Is your simulation code available somewhere?\n\u003e\u003e\n\u003e\u003e I was just wondering why mycelium generates a very big UTXO set for \u003c1000sat, because change outputs will never be smaller than \n\u003e\u003e 5460sat (=TransactionUtils.MINIMUM_OUTPUT_VALUE). If the change would be lower, it simply is skipped and added to the miner fee:\n\u003e\u003e \t-\u003e https://github.com/mycelium-com/wallet/blob/master/public/bitlib/src/main/java/com/mrd/bitlib/StandardTransactionBuilder.java#L334\n\u003e\u003e\n\u003e\u003e Does your simulation account for that?\n\u003e\u003e\n\u003e\u003e 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.\n\u003e\u003e\n\u003e\u003e Cheers,\n\u003e\u003e Daniel\n\u003e\u003e\n\u003e\u003e On 2016-09-21 14:58, Murch via bitcoin-dev wrote:\n\u003e\u003e\u003e Hi,\n\u003e\u003e\u003e\n\u003e\u003e\u003e I'm currently compiling my Master's thesis about Coin Selection and my\n\u003e\u003e\u003e presentation proposal to Scaling Bitcoin has been accepted.\n\u003e\u003e\u003e\n\u003e\u003e\u003e For my thesis, I have analyzed the Coin Selection problem, created a\n\u003e\u003e\u003e framework to simulate wallet behavior on basis of a sequence of\n\u003e\u003e\u003e payments, and have re-implemented multiple coin selection strategies of\n\u003e\u003e\u003e prominent Bitcoin wallets (Bitcoin Core, Mycelium, Breadwallet, and\n\u003e\u003e\u003e Android Wallet for Bitcoin).\n\u003e\u003e\u003e\n\u003e\u003e\u003e As the Scaling Bitcoin site suggests that research should be made\n\u003e\u003e\u003e available to this mailing list, I would like to invite you to have a\n\u003e\u003e\u003e look at:\n\u003e\u003e\u003e\n\u003e\u003e\u003e http://murch.one/wp-content/uploads/2016/09/CoinSelection.pdf\n\u003e\u003e\u003e\n\u003e\u003e\u003e The PDF (176 kB) contains a two page description of my on-going work,\n\u003e\u003e\u003e including preliminary simulation results, and three figures showing the\n\u003e\u003e\u003e simulated wallets' UTXO compositions at the end of the simulation.\n\u003e\u003e\u003e\n\u003e\u003e\u003e I can provide further information as requested, and would welcome any\n\u003e\u003e\u003e feedback.\n\u003e\u003e\u003e\n\u003e\u003e\u003e →→ If anyone has another sequence of incoming and outgoing payment\n\u003e\u003e\u003e amounts at hand that I could run my simulation on, I'd love to hear\n\u003e\u003e\u003e about it.\n\u003e\u003e\u003e\n\u003e\u003e\u003e Regards\n\u003e\u003e\u003e\n\u003e\u003e\u003e Murch\n\u003e\u003e\u003e\n\u003e\u003e\u003e\n\u003e\u003e\u003e\n\u003e\u003e\u003e\n\u003e\u003e\u003e _______________________________________________\n\u003e\u003e\u003e bitcoin-dev mailing list\n\u003e\u003e\u003e bitcoin-dev at lists.linuxfoundation.org\n\u003e\u003e\u003e https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev\n\u003e\u003e\u003e\n\u003e\u003e _______________________________________________\n\u003e\u003e bitcoin-dev mailing list\n\u003e\u003e bitcoin-dev at lists.linuxfoundation.org\n\u003e\u003e https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev\n\u003e\u003e\n\u003e _______________________________________________\n\u003e bitcoin-dev mailing list\n\u003e bitcoin-dev at lists.linuxfoundation.org\n\u003e https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev\n\u003e",
"sig": "47c119a5408d0eee90b57a1b9e76e76e70e8ebb42e4427df30b6935f5a07c017cf48f290dbfd7cf13d4fbe24b7a98841fc863066a897f3ab4910fbe069eb6998"
}