1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
|
Return-Path: <Daniel.Weigl@mycelium.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 75F17DD5
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 23 Sep 2016 09:35:32 +0000 (UTC)
X-Greylist: from auto-whitelisted by SQLgrey-1.7.6
Received: from mx.mycelium.com (mx.mycelium.com [188.40.34.2])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 6E77C118
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 23 Sep 2016 09:35:30 +0000 (UTC)
Received: from 178-189-191-86.adsl.highway.telekom.at ([178.189.191.86]
helo=[10.0.0.77]) by mx.mycelium.com with esmtpsa
(TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.86_2)
(envelope-from <Daniel.Weigl@mycelium.com>)
id 1bnMt9-0002ui-GV; Fri, 23 Sep 2016 11:35:27 +0200
To: Murch <murch@murch.one>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>,
"info@mycelium.com" <info@mycelium.com>
References: <358752cc-48f6-eef8-ae9a-e17a0651ed52@murch.one>
<1aa41a90-2cc6-36c8-d9c5-67d52befabbe@mycelium.com>
<3b7ff5e7-9803-27ab-af26-df2c743f53d0@murch.one>
From: Daniel Weigl <Daniel.Weigl@mycelium.com>
Message-ID: <385cf934-931f-5035-738b-3d6f0e401436@mycelium.com>
Date: Fri, 23 Sep 2016 11:35:22 +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: <3b7ff5e7-9803-27ab-af26-df2c743f53d0@murch.one>
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
X-Spam-Score: -1.0 (-)
X-Spam-Status: No, score=-5.0 required=5.0 tests=BAYES_00,RP_MATCHES_RCVD
autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
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:35:32 -0000
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.
..
> 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.)
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
On 2016-09-23 11:11, Murch wrote:
> 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
>>
|
