diff options
| author | Murch <murch@murch.one> | 2016-09-23 11:11:58 +0200 |
|---|---|---|
| committer | bitcoindev <bitcoindev@gnusha.org> | 2016-09-23 09:12:04 +0000 |
| commit | 2e75ee045d01856678b22a110e52d204d22f5d85 (patch) | |
| tree | 8aba19bf81bc2f72cde02eb191e372d02c8472b0 | |
| parent | 3ba8b8726e3bf50b0111feeae94435aac79912b9 (diff) | |
| download | pi-bitcoindev-2e75ee045d01856678b22a110e52d204d22f5d85.tar.gz pi-bitcoindev-2e75ee045d01856678b22a110e52d204d22f5d85.zip | |
Re: [bitcoin-dev] On-going work: Coin Selection Simulation
| -rw-r--r-- | 8e/ce279228c1eb368c8449d40a3e2ad459811892 | 157 |
1 files changed, 157 insertions, 0 deletions
diff --git a/8e/ce279228c1eb368c8449d40a3e2ad459811892 b/8e/ce279228c1eb368c8449d40a3e2ad459811892 new file mode 100644 index 000000000..2e197bb6e --- /dev/null +++ b/8e/ce279228c1eb368c8449d40a3e2ad459811892 @@ -0,0 +1,157 @@ +Return-Path: <murch@murch.one> +Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org + [172.17.192.35]) + by mail.linuxfoundation.org (Postfix) with ESMTPS id 9FA7CCCE + for <bitcoin-dev@lists.linuxfoundation.org>; + Fri, 23 Sep 2016 09:12:04 +0000 (UTC) +X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 +Received: from ankaa.uberspace.de (ankaa.uberspace.de [185.26.156.54]) + by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 687AE139 + for <bitcoin-dev@lists.linuxfoundation.org>; + Fri, 23 Sep 2016 09:12:02 +0000 (UTC) +Received: (qmail 13112 invoked from network); 23 Sep 2016 09:12:00 -0000 +Received: from localhost (HELO ?192.168.178.20?) (127.0.0.1) + by ankaa.uberspace.de with SMTP; 23 Sep 2016 09:12:00 -0000 +To: Daniel Weigl <Daniel.Weigl@mycelium.com>, + Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org> +References: <358752cc-48f6-eef8-ae9a-e17a0651ed52@murch.one> + <1aa41a90-2cc6-36c8-d9c5-67d52befabbe@mycelium.com> +From: Murch <murch@murch.one> +Message-ID: <3b7ff5e7-9803-27ab-af26-df2c743f53d0@murch.one> +Date: Fri, 23 Sep 2016 11:11:58 +0200 +User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 + Thunderbird/45.2.0 +MIME-Version: 1.0 +In-Reply-To: <1aa41a90-2cc6-36c8-d9c5-67d52befabbe@mycelium.com> +Content-Type: text/plain; charset=utf-8 +Content-Transfer-Encoding: 8bit +X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham + version=3.3.1 +X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on + smtp1.linux-foundation.org +X-Mailman-Approved-At: Fri, 23 Sep 2016 13:21:05 +0000 +Subject: Re: [bitcoin-dev] On-going work: Coin Selection Simulation +X-BeenThere: bitcoin-dev@lists.linuxfoundation.org +X-Mailman-Version: 2.1.12 +Precedence: list +List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org> +List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, + <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe> +List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/> +List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org> +List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help> +List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, + <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe> +X-List-Received-Date: Fri, 23 Sep 2016 09:12:04 -0000 + +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 +> + |