summaryrefslogtreecommitdiff
path: root/af/6d8634d5d09dcf6f2fa43cae4c7627dba6ef0a
blob: 1dd766a05a2407b5b197dc646820a10426b564e1 (plain)
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
292
293
294
295
296
297
298
299
300
301
302
303
304
305
Return-Path: <ZmnSCPxj@protonmail.com>
Received: from silver.osuosl.org (smtp3.osuosl.org [140.211.166.136])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 61155C016F
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Thu, 30 Apr 2020 08:54:39 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by silver.osuosl.org (Postfix) with ESMTP id 3B5C320380
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Thu, 30 Apr 2020 08:54:39 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
Received: from silver.osuosl.org ([127.0.0.1])
 by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id dzAeLS4FFzgU
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Thu, 30 Apr 2020 08:54:35 +0000 (UTC)
X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6
Received: from mail-40130.protonmail.ch (mail-40130.protonmail.ch
 [185.70.40.130])
 by silver.osuosl.org (Postfix) with ESMTPS id 87D3820002
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Thu, 30 Apr 2020 08:54:35 +0000 (UTC)
Date: Thu, 30 Apr 2020 08:54:28 +0000
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=protonmail.com;
 s=protonmail; t=1588236872;
 bh=iUWbQjCLxMqDq8F0Lp27Y40awCiSLXKMomX4OH9f86M=;
 h=Date:To:From:Cc:Reply-To:Subject:In-Reply-To:References:From;
 b=b7u3LPi7JRJRk83q0mYaVg1CsXNXGTOGuYauUbKvkDWOl9Z64N30jJfpv+bgn4qPI
 I2xTRCO5IENILBxDb9oMg4z9pzfejErby+7hVkKi4k0s9uqEqEp739aT6oyrSx9ipz
 16EJD1H8w339MBFNq0v3AmT8tOWeNCGGdjKSozNU=
To: Chris Belcher <belcher@riseup.net>
From: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Reply-To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Message-ID: <gAyc5MFCEkCjjdLSx_fKF-9MVnI4Zl6-BQ7Y-Q2_JNFYE2tQbCC1Js5YfE9RnPE_RPoVx57H0tWA-dpJ5SM7KP52DxTzHRdx6IF_pWjIh7A=@protonmail.com>
In-Reply-To: <ed482ed6-a79b-e20c-5356-8be4345333f5@riseup.net>
References: <CALmj_sWCA6S_4bnmLetvLuzNhv=PfQvLnX3zVEZwsRtgzA=yqw@mail.gmail.com>
 <CALmj_sVwLG82_pCEnc-mdT-Cf+cPitpL59AruBbvyYLjaYoZ2Q@mail.gmail.com>
 <mRCFEsXTvivO-I7sBdoTbqV0RsnX9vdGGORqzJBGYWXd1Xqis-oBNtEFaCEWIt3g9ARrvNeqH3l6sWSH4uQdcj5ps5WAmaEbEUvb9Znk9Rw=@protonmail.com>
 <CALmj_sUuw8JkodDemnq4qkapWD28vpojKD3bmkiVYm3Cp76+NQ@mail.gmail.com>
 <-_xRcjb8H_0Bck71k4VkeukEBgHT-03ikLTIdyTG2P0rt0T_mvN4b4FejmWobwnAUCGNaDpFQlPc3TMwlml1gjnZ1lwSumeEYQpXSyijND0=@protonmail.com>
 <0e1c0287-617c-976c-9fd4-16683881d5d5@riseup.net>
 <muQZ5QzVScvrjDkpZg1pWQMPFekgn_yqaro1i-JBZWCowA4HhybWFi3e5clygh5EIeLIa7jlykipA5nAxpiuLXK0-5SE3wEXXOTVwMlPAVU=@protonmail.com>
 <ed482ed6-a79b-e20c-5356-8be4345333f5@riseup.net>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Fwd: (Semi)Traceless 2-party coinjoin off-chain
	protocol using schnorr signatures
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: Thu, 30 Apr 2020 08:54:39 -0000

Good morning CB,


> Equal-output-coinjoins and JoinMarket also have a version of the
> common-input-ownership-heuristic (CIOH), because its often possible to
> separate the inputs into sets of their owners of a equal-output-coinjoin
> using the input amounts. CoinSwap can be combined with something like
> PayJoin or CoinJoinXT, which would genuinely break the CIOH, so such a
> system wouldn't have this flaw either.
>
> For those reasons I've been thinking a CoinSwap system wouldn't need as
> many mixdepths, maybe it could use two or even just one.

Would the ZeroLink proposal of separating a receiving (pre-mix) wallet from=
 a sending (post-mix) wallet apply, thus having two implicit mixdepths (the=
 receiving mixdepth and the sending mixdepth)?
Or would imposing the rule "all sends must be via CoinSwap" be sufficient (=
and follow the ZeroLink rule in spirit)?

> If so, then it follows that multi-transaction CoinSwaps can be done by
> having UTXOs come from the same mixdepth, as long as the inputs that
> should be separate are not co-spent in the same transaction.

This "as long as the inputs that should be separate are not co-spent" is pr=
ecisely what mixdepths protect against, which is why I think *some* kind of=
 mixdepth facility will still matter in CoinSwap.

Still, you have convinced me that, for the purpose of multi-transaction Coi=
nSwap where you do not merge any of your coins, it is immaterial if the sub=
-transactions come from the same mixdepth or not.
And if you have to merge your coins (for instance, if you are a maker and y=
our customer wants to get a UTXO that is larger than any you have on hand, =
you have to merge your coins), you just have to ensure they are in the same=
 mixdepth.

Of course, you *could* be proposing some other construct --- perhaps you ha=
ve some relational entry which says "you cannot merge coin A and coin B" wh=
ich allows you to merge A C D or B C E, but not A B?
(I imagine this would make coin selection even harder, but I am not a mathe=
matician and there may be some trivial solution to this.)

Now --- if you have two coins that cannot be merged in the same onchain tx,=
 what happens when you swap them in a multi-tx CoinSwap with somebody else?
That somebody else does not know that information.
Instead, that somebody else must always assume that any coins it got from t=
he same CoinSwap operation must not be safely mergeable (though they can st=
ill be used in the same swap together).

Coins received via receive addresses would also not be mergeable with any o=
ther coins, except coins to the same address (because coins in the same add=
ress already leak that they are owned by the same owner).

>
> Remember that a passive surveillor of the blockchain doesn't see
> mixdepths at all, they see addresses and transactions, and must use
> heuristics to try to cluster them together. We can break these heuristics=
.
>
> > Attempting to completely detach a market-for-CoinSwap from JoinMarket s=
eems to be impossible to my mind: the protocols are known, implementations =
open, and someone will inevitably write code for a single piece of software=
 that can operate as both a JoinMarket maker and a maker for a market-for-C=
oinSwap (to increase their market, so to speak), so it might be better to j=
ust add CoinSwap to JoinMarket in the first place.
>
> Someone who has the ability to write such code should also have the
> awareness to realize that mixing equal-output-coinjoins with coinswaps
> damages the privacy because it breaks the steganography of coinswaps.
>
> Also, because CoinSwap is better than equal-output CoinJoin in almost
> every way, we can expect users (who are takers) to stop using JoinMarket
> and switch over to CoinSwap if the software becomes mature. So such a
> JoinMarket maker won't get many customers, and so there wouldn't be much
> point writing such maker code.

An unscrupulous possible maker might not value the privacy of its customers=
 (indeed makers are a privacy attack vector, which requires something like =
fidelity bonds like you suggested before to protect against), and takers mi=
ght not want to do possibly-computationally-expensive blockchain analysis t=
o evaluate whether a particular maker values privacy.
An unscrupulous maker might thus earn more than a more scrupulous maker can=
, at least during the transition from JoinMarket to SwapMarket, and get a g=
reater share of the future SwapMarket available liquidity due to their incr=
eased earnings during the transition.

Against this we should remember that software that does two things is four =
times as complicated as software that does one thing, so hopefully your pro=
jected transition from JoinMarket to SwapMarket will be fast enough that su=
ch a combined Join/SwapMarket maker software does not arise fast enough to =
matter.


> But for sure it would be good to reuse code in any eventual
> implementation. Indeed Waxwing's implementation did:
> https://github.com/AdamISZ/CoinSwapCS
>
> > Assuming Alice is the taker, and Bob is the maker, then Alice might wan=
t a specific coin value (or set of such) that Bob does not have.
> > In that case, Bob will have to split a UTXO it owns.
> > We could constrain it so that Bob at least is not allowed to use the ch=
ange from splitting for the same CoinSwap, e.g. if Bob has only 9 BTC and 1=
 BTC coins and Alice wants a 6 BTC / 3 BTC / 1 BTC split, then Bob cannot s=
plit its own 9 BTC coin then swap.
> > Or in terms of mixdepths, Bob can split within a mixdepth but each outg=
oing UTXO in the same swap should be from different mixdepths.
>
> A good way to do it could be for Alice to tell Bob that she wants 10 BTC
> and let Bob figure out on his own how to get that amount, based on the
> amounts he already has. If Alice is making a payment she can provide
> that amount too, but all the other output amounts can be up to Bob.

This leaks to Bob whether Alice is making a payment or not; it would be bet=
ter for the privacy of Alice for Alice to *always* mention *some* "payment =
amount", even if this is not actually a payment and Alice is just mixing fo=
r herself prior to storing in cold storage.
And if Alice wants to use a single swap to pay to multiple targets at once,=
 that implies Alice has to have the ability to indicate the outputs it want=
s to Bob, and it would imply as well that Alice has to obfuscate which of t=
hose outputs have amounts that actually *matter* (by always insisting on wh=
at the output amounts must be, rather than insisting on N output amounts an=
d letting Bob handle the rest).
(We *could* constrain it such that Alice can make only one payment per Coin=
Swap, so that Alice only gives one "target" amount and one "total" amount, =
but that implies even bigger blockspace utilization, sigh.)

Otherwise, Bob can get information:

* "Oh, Alice did not specify any of the outputs, just the total amount, all=
 of my old coins are owned by Alice now."
* "Oh, Alice specified an exact value for one of the outputs, that one is n=
o longer owned by Alice but the rest are owned by Alice."
* "Oh, Alice specified exact values for two of the outputs, those two are d=
efinitely no longer owned by Alice but the rest are owned by Alice."

The conclusion here is either Alice never specifies any of the outputs --- =
in which case Alice cannot use a CoinSwap to pay directly to somebody else =
--- or Alice specifies all of them.

Again, the maker might be an active surveillor, thus we should reduce infor=
mation leaks to the maker as much as we can.

>
> Bob would often still have to split a UTXO he owns, but see below about
> breaking change address heuristics.
>
> > Of course, if a surveillor does solve the sparse subset sum, then the C=
oinSwap Protocol part looks exactly like a Bitcoin transaction, with a "mai=
n" paying output and a "change" output, and the same techniques that work w=
ith current Bitcoin txes work with "CoinSwap Protocol" virtual transactions=
.
> > It seems to me that, in a system of makers and takers, even if the make=
r is really just paying the taker(s) to do CoinSwaps to mix back to itself,=
 it should still "require" some output amount that really goes to itself, s=
o that the maker at least does not differentiate between the case that the =
taker is paying to itself vs the case that the taker is paying someone else=
 via a CoinSwap.
> > That is, the protocol should still require that the taker specify some =
target desired amount, regardless of whether the taker wants to pay a speci=
fic value, or the taker wants to just mix its coins.
>
> If Bob needs to split a UTXO he'd do that with a change output. And
> because we understand change detection heuristics we can intentionally
> break them, for example if Bob's UTXO is on a p2sh-p2wpkh address and
> the CoinSwap address is of that type too (because ECDSA-2P is being
> used) then Bob could make his change output p2wpkh or p2pkh. Then anyone
> using the script-type-heuristic would think that the CoinSwap address is
> actually change and still belongs to Bob, and that the real change
> address is actually the payment or CoinSwap address. i.e. the adversary
> would assume that wallet software only uses one script type, in this
> case it assumes that Bob's wallet is exclusively p2sh-p2wpkh.
>
> > > -   Multi-transaction CoinSwaps aren't truly an example of a subset-s=
um
> > >     problem, but "sparse subset sum", a related and easier problem.
> > >     The way its normally formulated, subset sum is about finding a su=
bset
> > >     that adds up to a target value. But in multi-transaction coinswap
> > >     there'd only be three or four CoinSwap outputs, so the problem is
> > >     finding just three or four integers in a big set that add up to t=
he target.
> > >     You could think of it mathematically that the n-choose-k function=
 is
> > >     near-polynomial when k is near 0 or near n, and the function is
> > >     exponential when k is near n/2.
> > >     A more promising way to build privacy is to create a situation wh=
ere an
> > >     adversary would find a huge amount of false positives which are v=
ery
> > >     close the amount being sent. So even if the adversary has enough
> > >     computational power to iterate all the amounts it won't help them=
 much
> > >     due to the huge number of false positives.
> > >
> >
> > What are your thoughts on creating such possible situations?
> > An idea is to require standard swap amounts, i.e. similar to the standa=
rd 100mBTC mixing bin of Wasabi.
> > As well, one could randomly select some existing 1-input 1-output txes =
in the mempool and/or recent blocks, sum them, and swap for the same sum, t=
o force at least one false positive, but the surveillor could protect again=
st this by removing the earliest match (the one it saw in the mempool first=
, or onchain).
>
> I think we can get the false positive count up because the n-choose-k
> function still gets quite large as k increases.
>
> We can make a simplified reasonable assumption that outputs on the
> blockchain follow a lognormal distribution. An adversary trying to unmix
> a 3-transaction CoinSwap would have to find the sum of every
> 3-combination of the relevant outputs. For our case, the sum of three
> lognormal distributions is another lognormal distribution with different
> parameters, it's corresponding frequency distribution would get scaled
> by n-choose-3. This frequency distribution is what the adversary would
> find when searching, and that distribution would be quite tall because
> of the scaling by n-choose-k. Suppose our CoinSwap is for 4 BTC then the
> adversary would look at their frequency distribution at 4 BTC and find a
> pretty big number, i.e. many other combinations of 3 outputs would add
> up to 4 BTC just by chance. That is the false positive rate, and is our
> anonymity set with respect to this attack.
>
> To work this out precisely we'd need to study the distribution of output
> values on the blockchain today, and see how it behaves when summed
> together. But the lognormal distribution assumption is probably not too
> far from the truth, as it appears all the time in economics and finance,
> and there is a clear justification for why. And the scaling by
> n-choose-k would still hold.

Okay, from what little I understand it seems that "even if sparse subset su=
m is easier than subset sum, it is still hard, so it probably will not matt=
er in practice", would that be a fair takeaway?

>
> Along with that, some output amounts have very few significant figures
> (e.g. 1 BTC, 0.1 BTC, 0.01 BTC), presumably because the user types just
> one number on their keyboard when creating a transaction. We can use
> that fact to add a bit of privacy by occasionally making one of our
> outputs also be rounded like that.

I agree.

Regards,
ZmnSCPxj