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
|
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 217B4C0172
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 29 Apr 2020 07:56:29 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by silver.osuosl.org (Postfix) with ESMTP id 0C91822D55
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 29 Apr 2020 07:56:29 +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 u7xCYKHIyq6d
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 29 Apr 2020 07:56:26 +0000 (UTC)
X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6
Received: from mail-40135.protonmail.ch (mail-40135.protonmail.ch
[185.70.40.135])
by silver.osuosl.org (Postfix) with ESMTPS id F0FCE227E1
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 29 Apr 2020 07:56:25 +0000 (UTC)
Date: Wed, 29 Apr 2020 07:56:16 +0000
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=protonmail.com;
s=protonmail; t=1588146983;
bh=5FKj4SkEfCJE2LVizeu/Wdamn7gVkyQhCwIYUqMs6cE=;
h=Date:To:From:Reply-To:Subject:In-Reply-To:References:From;
b=UwVM0coeh0xYNPpuzdW/lkKiKVgVGKUKwckgXqA8Ut1R4njipYnvAF4rtlar6vOn+
cZVDQZlrTnUNzH+Tih2Nl5QqCMWP40g1xfnYBy+FFjcTRjOP+TPP/8v7qYcTCjSMRd
wYtmApUuMwwtgLKsaE03T4rMyL+VotTs7Na921Hg=
To: Chris Belcher <belcher@riseup.net>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
From: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Reply-To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Message-ID: <muQZ5QzVScvrjDkpZg1pWQMPFekgn_yqaro1i-JBZWCowA4HhybWFi3e5clygh5EIeLIa7jlykipA5nAxpiuLXK0-5SE3wEXXOTVwMlPAVU=@protonmail.com>
In-Reply-To: <0e1c0287-617c-976c-9fd4-16683881d5d5@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>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
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: Wed, 29 Apr 2020 07:56:29 -0000
Good morning CB,
I have been thinking about CoinSwap for a good while as well.
Here are some very unorganized thoughts.
It wold be nice to interoperate with JoinMarket, i.e. have a JoinMarket mak=
er that also provides CoinSwap services using the same UTXOs.
However, this requires us to retain compatibility with the JoinMarket walle=
t structure, which is divided into mixdepths, with the rule that UTXOs in d=
ifferent mixdepths cannot be spent together in the same onchain UTXO (to mo=
ve across mixdepths you have to do a send, and sending out is always done b=
y a single CoinJoin round with multiple makers).
I am uncertain what is the best way to handle multitransaction when conside=
ring the mixdepth system.
My instinct is that if you are doing multitransaction (whether as taker or =
maker) then each transaction in the swap *has to* come from a different mix=
depth.
The issue here is:
* If all the UTXOs in the multitransaction swap come from the same mixdepth=
, then a surveillor who is monitoring that mixdepth gets a good hint in sol=
ving the sparse subset sum problem.
* On the other hand, if all the UTXOs in the multitransaction swap come fro=
m different mixdepths, then a surveillor who has solved the sparse subset s=
um problem now has the hint that the different mixdepths are really owned b=
y the same JoinMarket user.
I am uncertain which tradeoff is better here, though I am inclined to think=
the latter is better.
Attempting to completely detach a market-for-CoinSwap from JoinMarket seems=
to be impossible to my mind: the protocols are known, implementations open=
, and someone will inevitably write code for a single piece of software tha=
t can operate as both a JoinMarket maker *and* a maker for a market-for-Coi=
nSwap (to increase their market, so to speak), so it might be better to jus=
t add CoinSwap to JoinMarket in the first place.
> A couple of thoughts on multi-transaction coinswaps:
>
> - Users should never split up a single UTXO before doing a coinswap,
> instead they should send the one UTXO to a coinswap address and get b=
ack
> multiple UTXOs.
>
> For example, this 1-to-3 TXO coinswap (The symbol ----> means bitcoin
>
>
> transaction).
>
> AliceA (10 BTC) ----> CoinSwap AddressA ----> BobA (10 BTC)
>
> BobB (3 BTC) ----> CoinSwap AddressB ----> AliceB (6 BTC)
>
> BobC (2 BTC) ----> CoinSwap AddressC ----> AliceC (3 BTC)
>
> BobD (5 BTC) ----> CoinSwap AddressD ----> AliceD (1 BTC)
>
>
> Note that the Bob-to-Alice set of transactions add up to 10 BTC, the
> entire CoinSwap is swapping the same amount.
>
> Or written another way:
>
> Alice TXO (10 BTC) ----> Coinswap Protocol ----> Alice TXO1 (6 BTC)
>
> ----> Alice TXO2 (3 BTC)
>
> ----> Alice TXO3 (1 BTC)
>
Assuming Alice is the taker, and Bob is the maker, then Alice might want 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 change=
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 split=
its own 9 BTC coin then swap.
Or in terms of mixdepths, Bob can split within a mixdepth but each outgoing=
UTXO in the same swap should be from different mixdepths.
> - It's helpful if any CoinSwap app is actually used for spending rather
> than just mixing back to yourself. That will help avoid the problem o=
f
> users inadvertently co-spending all their coinswap outputs in the sam=
e
> transaction.
> An example of Alice paying for a VPN anonymously:
>
> Alice TXO (10 BTC) ---> Coinswap Protocol ---> VPN Payment (0.1 BTC)
>
> ---> Change1 (6 BTC)
>
> ---> Change2 (3 BTC)
>
> ---> Change3 (0.9 BTC)
>
>
>
> In this case Alice will never accidentally merge all her TXOs together,
> because the VPN Payment TXO doesn't belong to her. Also this could
> improve privacy because unlike in normal transaction the VPN provider
> might not be able to figure out the lower bound of Alice's balance (10
> BTC in this case).
This is a good idea, akin to the rule in JoinMarket that all outgoing spend=
s are done through a CoinJoin.
Of course, if a surveillor ***does*** solve the sparse subset sum, then the=
CoinSwap Protocol part looks exactly like a Bitcoin transaction, with a "m=
ain" paying output and a "change" output, and the same techniques that work=
with current Bitcoin txes work with "CoinSwap Protocol" virtual transactio=
ns.
It seems to me that, in a system of makers and takers, even if the maker 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, so th=
at the maker at least does not differentiate between the case that the take=
r 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* ta=
rget desired amount, regardless of whether the taker wants to pay a specifi=
c value, or the taker wants to just mix its coins.
> - Multi-transaction CoinSwaps aren't truly an example of a subset-sum
> problem, but "sparse subset sum", a related and easier problem.
>
> The way its normally formulated, subset sum is about finding a subset
> 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 the t=
arget.
>
> 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 where =
an
> adversary would find a huge amount of false positives which are very
> close the amount being sent. So even if the adversary has enough
> computational power to iterate all the amounts it won't help them muc=
h
> 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 standard 1=
00mBTC mixing bin of Wasabi.
As well, one could randomly select some existing 1-input 1-output txes in t=
he mempool and/or recent blocks, sum them, and swap for the same sum, to fo=
rce at least one false positive, but the surveillor could protect against t=
his by removing the earliest match (the one it saw in the mempool first, or=
onchain).
Regards,
ZmnSCPxj
|
