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
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
|
Return-Path: <max@towardsliberty.com>
Received: from smtp2.osuosl.org (smtp2.osuosl.org [IPv6:2605:bc80:3010::133])
by lists.linuxfoundation.org (Postfix) with ESMTP id 14E9BC0012
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 6 Apr 2022 16:06:09 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by smtp2.osuosl.org (Postfix) with ESMTP id E1E4940517
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 6 Apr 2022 16:06:08 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -0.351
X-Spam-Level:
X-Spam-Status: No, score=-0.351 tagged_above=-999 required=5
tests=[BAYES_00=-1.9, DKIM_INVALID=0.1, DKIM_SIGNED=0.1,
RCVD_IN_BL_SPAMCOP_NET=1.347, SPF_HELO_NONE=0.001, SPF_NONE=0.001]
autolearn=no autolearn_force=no
Authentication-Results: smtp2.osuosl.org (amavisd-new); dkim=neutral
reason="invalid (public key: not available)"
header.d=towardsliberty.com
Received: from smtp2.osuosl.org ([127.0.0.1])
by localhost (smtp2.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id rcTsvZpu-4Wm
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 6 Apr 2022 16:06:04 +0000 (UTC)
X-Greylist: from auto-whitelisted by SQLgrey-1.8.0
Received: from subsea-epitome.host4coins.net (subsea-epitome.host4coins.net
[185.150.162.112])
by smtp2.osuosl.org (Postfix) with ESMTPS id 9666740141
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 6 Apr 2022 16:06:04 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by subsea-epitome.host4coins.net (Postfix) with ESMTP id 6579981951
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 6 Apr 2022 16:06:00 +0000 (UTC)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=
towardsliberty.com; h=content-transfer-encoding:content-type
:content-type:content-language:subject:subject:from:from
:user-agent:mime-version:date:date:message-id; s=default; t=
1649261110; x=1651075511; bh=8UtxEFZ7oDGo0xg/u8g3LESpROAjIFN8Dv7
0KpMzn44=; b=tuLGpMbhYw/59Yq0CBIkjn9owpxjADkAsL4ZmkaVvSobRG8ZFoL
HW4bP2EkASMbwI9UTiyi70t2gKbtbtKTkYJVwc95mK1ukfgs3tAd/AenvAAhApwP
SWs607eSGLjXh5dnYcim9UuDKmR5ECnT9MxgzVeywzDciiJzOKZoSTQA=
X-Virus-Scanned: Debian amavisd-new at subsea-epitome.host4coins.net
Received: from subsea-epitome.host4coins.net ([127.0.0.1])
by localhost (subsea-epitome.host4coins.net [127.0.0.1]) (amavisd-new,
port 10026)
with LMTP id 5_9sPKzLzWKC for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 6 Apr 2022 16:05:10 +0000 (UTC)
Received: from [10.137.0.32] (tor-exit-4.zbau.f3netze.de [185.220.100.255])
(Authenticated sender: max@towardsliberty.com)
by subsea-epitome.host4coins.net (Postfix) with ESMTPSA id 7D1688196A
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 6 Apr 2022 16:05:10 +0000 (UTC)
Message-ID: <81da2108-1aed-6117-0723-0acbf41c4506@towardsliberty.com>
Date: Wed, 6 Apr 2022 18:05:08 +0200
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101
Thunderbird/91.7.0
From: Max Hillebrand <max@towardsliberty.com>
Content-Language: en-US
To: bitcoin-dev@lists.linuxfoundation.org
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
X-Mailman-Approved-At: Wed, 06 Apr 2022 16:20:11 +0000
Subject: [bitcoin-dev] Client side coinjoin amount organization with WabiSabi
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.15
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: Wed, 06 Apr 2022 16:06:09 -0000
Hello list,
tl;dr: client side coinjoin amount organization is bloody difficult. Our
current approach: pick random number of inputs based on wallet utxo
count; pick that group of inputs which result in the lowest anonscore
consolidation penalty; generate deterministic frequency table as
Schelling point; brute force decompose input sum into likely
denominations and pick randomly one of the good ones.
In previous coinjoin implementations, round parameters like the equal
denomination are dictated by the coordinator. This is in part because of
the design constraints of the Chaumian blind signature coordination
protocol. Given knowledge of the input sum of a user, an adversary can
find out which denominations the user received, even though it is more
difficult to find out exactly which equal amount output coin was
received. Furthermore, this leads to a worse usability as well as more
blockspace consumption. However, the coordinator can enforce for
example, that every user ends up in the same denomination, and thus a
very large anonymity set is achieved.
This can be improved by using a coinjoin coordination protocol like
WabiSabi with less constraints, specifically no input-input linkage, and
arbitrary input/output amount registration. Now the coordinator does not
dictates round parameters like minimum equal amount denomination nor the
decomposition algorithm used. The idea is to make more decisions client
side, without substantially sacrificing the privacy guarantees and
anonymity set size of outputs.
This turns out to be a quite difficult problem. I will try my best to
explain the approach that is currently implemented in Wasabi Wallet's
third release candidate. The code is linked below, sorry in advance for
any discrepancy or confusion in my explanation. Even though the results
seem to be alright, this is probably not the optimal approach, so I
kindly ask you grey-bearded Bitcoin wizards to review, break and improve it.
## Input Selection
First, the client finds out how many coins to select in this round. This
is a random choice between the numbers 1 and 10. However, if the wallet
currently has less than 35 utxos, there is a preference of choosing 1.
If the wallet has more than 125 utxos, there is a preference of choosing
10. With a gradient in between. This is to control the utxo count of the
wallet. Noticeably this does not take into account the sats amount in
the utxo set, so a user with 0.1 btc will behave the same as one with
1000 btc. Maybe the target utxo count should be adjusted based on value.
Next, the question of which coins to register: Ideally, those coins
which result in the least anonscore loss possible. Shuffle all suitable
utxos [i.e. confirmed, below max anonscore target etc], and sort them
ascending by anonscore, then descending by amount. Now create groups
with the size of the previously established input count X. The first
coin until the X coin of the sorted list are the first group, then shift
one down, so the second group is the second coin until the X+1 coin. Do
these "rolling groups" all the way to the bottom of the list. This way,
coins which have a anonscore close to each other are selected.
Remove those groups which have many coins coming from the same transaction.
For each group, calculate the anonscore cost of input consolidation
weighted by amount. If the selected coins have anonscore 3, 5 and 10,
then the group has a anonscore of 3. The input with 10 anonscore thus
has a 7 anonscore cost. Now weight this to the input value of the
relevant coin in the group, so that a loss of anonscore in a high value
coin is more costly than if it were a low value coin.
Pick that input group with the lowest weighted anonscore cost.
There is randomness in the number of inputs chosen, but the selection of
the best coin group is deterministic. Maybe there can be some randomness
in the final group selection, without suffering from too much anonscore
consolidation penalty.
One additional idea [which is not yet implemented] is that the
coordinator suggests [not dictates] a maximum input value, which changes
across different rounds. Large value inputs are not considered suitable,
if the maximum suggested input value of the current round is smaller.
It is important to note that currently users choose their inputs without
knowing the inputs that other users have already registered. It should
be possible to design the protocol in a way to share the inputs that
were already registered, even if input registration is not yet complete.
There are however some privacy concerns, like timing attacks, or
de-registration of an input after it was announced to other users.
## Output Selection
The coordinator collects all input registrations, and forwards them to
all users. At this point, all clients knows all inputs of this
transaction. The goal now is to get a Schelling point among users of
which output denominations to choose, so that the anonset size of each
denomination is sufficiently large.
First of all, it's a good idea to limit the denominations that the
client will register. Some simulations confirmed that low Hemming weight
numbers are efficient, thus clients generate a list of standard
denominations which are: powers of two; powers of three; two times
powers of three; powers of ten; two times powers of ten; and five times
powers of ten. However, remove some of those denominations which are
very close to each other, more so for larger values. Notice that this
list of standard denominations is the same across all rounds, it does
not depend on specific inputs.
We can further decrease the list of potential denominations that the
client chooses, but specifically for every round. This is a further
Schelling point of which denominations the client prefers to choose.
This is done with a deterministic frequency table, based on the inputs
of the proposed transaction.
Take each input and greedily decompose it into the standard
denominations, meaning every input has precisely one decomposition. [45
decomposes greedily into 32+10+3] Count the occurrences of every
standard denomination into a frequency table. All those standard
denominations, which have a count of 2 or larger, are considered likely
denominations.
Notice that currently we remove the largest input from this frequency
table calculation. This is so that the whale does not mix alone by
himself. Also notice that individual inputs, and not input sums are
decomposed. This is because we found that generating the frequency table
based on only one input leads to a more accurate Schelling point, which
increases anonset count of the finally chosen denominations. Finally,
notice that we only calculate one single decomposition for each input,
the greedy one, but we could also calculate multiple different [or all
possible] decompositions for each input, thus generate a larger
frequency table and more likely denominations.
Whereas the frequency table should be deterministic as a Schelling
point, the actual user's input sum must not be deterministically
decomposed, otherwise an adversary who knows the input sum would find
out which denominations the client chose. [but not which of the equal
outputs he got]
The client takes his input sum [minus fees] and brute-force decomposes
into all possible groups of the likely denominations [those with high
count in this rounds' frequency table]. We found that in most cases,
even with this reduced list of likely denominations, any input sum can
be decomposed into up to eight outputs. [Sometimes the wealthiest user
gets a non-standard change amount] However, each decomposition has some
small amount of sats left over, which is is not put into an output
value, but instead pays miner fees.
Sort this list of all possible output groups ascending by leftover
amount, and remove those groups which have a leftover amount 1.3x larger
than the best option. Further, remove a group if it has a similar
largest denomination as another one. [So far everything deterministic,
given all coinjoin inputs and the users' input sum]
Out of this shorter list of output amount groups, shuffle and pick
randomly one of them. These are non-deterministic denominations which
will be registered for the actual coinjoin outputs. If there were no
shuffle, but a selection of the amount group with the lowest loss, users
would save sats. But arguably having this randomness here increases
privacy sufficiently to justify the slight increase in leftover amount cost.
Again, while choosing their own outputs, clients do not know which
outputs other clients registered. If the client would have this
information, it could possibly increase the quality of it's own output
registration substantially.
Notice there is a different decomposition strategies for the frequency
table [greedy] and the input sum [brute-force all]. Maybe, having the
same decomposition strategy here would lead to better results.
Notice further that there is no rank ordering of the possible
denominations based on some ambiguity score or entropy score. Rather,
the choice is random, and in some cases, this might result in not
optimal outcomes.
Here are some results of our simulation of the current algorithm:
50 inputs 15 users
Median output count: 98
Median change count: 4
Median change percent: 3.2
Median out anonsets: 3.5
Median leftovers: 481
300 inputs 70 users
Median output count: 442
Median change count: 0.5
Median change percent: 0.3
Median out anonsets: 9.6
Median leftovers: 394
Thank you for your consideration to review!
Skol
Max
Third Wasabi 2.0 Release Candidate:
https://github.com/zkSNACKs/WalletWasabi/releases/tag/v1.98.2.0
Input selection code:
https://github.com/zkSNACKs/WalletWasabi/blob/master/WalletWasabi/WabiSabi/Client/CoinJoinClient.cs#L366-L492
Amount decomposer code:
https://github.com/zkSNACKs/WalletWasabi/blob/master/WalletWasabi/WabiSabi/Client/AmountDecomposer.cs
https://github.com/zkSNACKs/WalletWasabi/blob/master/WalletWasabi/WabiSabi/Client/Decomposer.cs
Decomposition simulation: https://github.com/nopara73/sake
|