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
|
Return-Path: <belcher@riseup.net>
Received: from hemlock.osuosl.org (smtp2.osuosl.org [140.211.166.133])
by lists.linuxfoundation.org (Postfix) with ESMTP id EE6A5C0172
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 28 Apr 2020 13:03:43 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by hemlock.osuosl.org (Postfix) with ESMTP id D9BBE87ED9
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 28 Apr 2020 13:03:43 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
Received: from hemlock.osuosl.org ([127.0.0.1])
by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id 8vIwYQZTRJW9
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 28 Apr 2020 13:03:42 +0000 (UTC)
X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6
Received: from mx1.riseup.net (mx1.riseup.net [198.252.153.129])
by hemlock.osuosl.org (Postfix) with ESMTPS id 347A788026
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 28 Apr 2020 13:03:42 +0000 (UTC)
Received: from capuchin.riseup.net (unknown [10.0.1.176])
(using TLSv1 with cipher ECDHE-RSA-AES256-SHA (256/256 bits))
(Client CN "*.riseup.net",
Issuer "Sectigo RSA Domain Validation Secure Server CA" (not verified))
by mx1.riseup.net (Postfix) with ESMTPS id 49BMK96VtWzFfB2
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 28 Apr 2020 06:03:41 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=riseup.net; s=squak;
t=1588079021; bh=NiIRjM/Aw0Wjrk81lsXTGvF5neHButrcioxf+0TwI+Q=;
h=Subject:To:References:From:Date:In-Reply-To:From;
b=KYHJ5q65DpUjjmopAAQ8HRCkY0GYMAjhFTZOLnOIV37lRin855wjC1MBLfyykOB5d
mCodpMvDj8TKSxlTxrpX0qda95W10e6fU1DSCL9TfeJ/38sJEkBiSP3VNsfaMGfZhU
TyAM98AfgZ+0C5XhQWN33Hxq4f5vFd8eu9D9nNaI=
X-Riseup-User-ID: 72DA326C3C145CD52C7502C48CEB0665FBD092A95CBF13BC0DEA9A9714E40CF1
Received: from [127.0.0.1] (localhost [127.0.0.1])
by capuchin.riseup.net (Postfix) with ESMTPSA id 49BMK85sh6z8vWC
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 28 Apr 2020 06:03:40 -0700 (PDT)
To: bitcoin-dev@lists.linuxfoundation.org
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>
From: Chris Belcher <belcher@riseup.net>
Autocrypt: addr=belcher@riseup.net; prefer-encrypt=mutual; keydata=
xsFNBFPk74oBEACzBLjd+Z5z7eimqPuObFTaJCTXP7fgZjgVwt+q94VQ2wM0ctk/Ft9w2A92
f14T7PiHaVDjHxrcW+6sw2VI2f60T8Tjf+b4701hIybluWL8DntG9BW19bZLmjAj7zkgektl
YNDUrlYcQq2OEHm/MGk6Ajt2RA56aRKqoz22e+4ZA89gDgamxUAadul7AETSsgqOEUDI0FKR
FODzoH65w1ien/DLkG1f76jd0XA6AxrESJVO0JzvkTnJGElBcA37rYaMmDi4DhG2MY4u63VE
8h6DyUXcRhmTZIAj+r+Ht+KMDiuiyQcKywCzzF/7Ui7YxqeAgjm5aPDU2E8X9Qd7cqHQzFM7
ZCqc9P6ENAk5a0JjHw0d0knApboSvkIJUB0j1xDIS0HaRlfHM4TPdOoDgnaXb7BvDfE+0zSz
WkvAns9oJV6uWdnz5kllVCjgB/FXO4plyFCHhXikXjm1XuQyL8xV88OqgDFXwVhKrDL9Pknu
sTchYm3BS2b5Xq1HQqToT3I2gRGTtDzZVZV0izCefJaDp1mf49k2cokDEfw9MroEj4A0Wfht
0J64pzlBYn/9zor5cZp/EAblLRDK6HKhSZArIiDR1RC7a6s7oTzmfn0suhKDdTzkbTAnDsPi
Dokl58xoxz+JdYKjzVh98lpcvMPlbZ+LwIsgbdH4KZj7mVOsJwARAQABzR9DaHJpcyBCZWxj
aGVyIDxmYWxzZUBlbWFpbC5jb20+wsF+BBMBAgAoBQJT5O+KAhsDBQkSzAMABgsJCAcDAgYV
CAIJCgsEFgIDAQIeAQIXgAAKCRDvc06md/MRKS8jD/9P9fSYSIVjltL9brAMfIu7wJn0H0lX
TbcuCM2uQitJ3BNxI3c7aq5dEby27u5Ud54otncDJuRPQVDKs6H7t1rInitgJ1MTQ9/aQGFA
btKcgtVIMFbeClzTTfWr4W7fE45NI7E9EANgk5JfmWh3U+KINYLF5RtqynYocrsP6zOV+G9A
HCpBemd9TN60CoMLMyMzTHEW1oQffaVAXY8DgthEYO/odWYIod7VTmEm0zU1aSysPqMwPWNm
8XIl0f8SfKQyZlAU8e1eCFVCenkE44FKC5qQNYc2UxexEYtfCWChTGc4oHKxIyYmTCCefsQF
LvgwtvlNHRXHSDKSPSNcRcpl8DFpNEKrmMlkJ8Mx+YR05CydlTQ0bI3FBohJC+UHrjD5I3hA
wJUC1o+yVSOEd+zN3cG1EECIwkEQSmBgG5t/le2RdzfXOdpf9ku2/zoBpq00R54JxUKlfRM7
OPTv7X+1AKHkxOySdCZwGgvdh2Whuqs4kTvtco00gCFM9fBd5oi1RJuHtxHsj8+/XU15UItb
jeo96CIlM5YUeoRLPT5mxZYWgYAARFeSFReNq/Tuwq9d8EokUrtAyrPayznliy53UJfWDVzl
925c0Cz0HWaP2fWj+uFcj/8K0bhptuWJQy0Poht1z3aJC1UjEgr1Xz8I7jeSJmIlA9plcJw2
k4dhWc7BTQRT5O+KARAAyFxAM28EQwLctr0CrQhYWZfMKzAhCw+EyrUJ+/e4uiAQ4OyXifRr
ZV6kLRul3WbTB1kpA6wgCShO0N3vw8fFG2Cs6QphVagEH8yfQUroaVxgADYOTLHMOb7INS8r
KI/uRNmE6bXTX27oaqCEXLMycqYlufad7hr42S/T8zNh5m2vl6T/1Poj2/ormViKwAxM+8qf
xd8FNI4UKmq2zZE9mZ5PiSIX0qRgM0yCvxV39ex/nhxzouTBvv4Lb1ntplR/bMLrHxsCzhyM
KDgcX7ApGm+y6YEsOvzw9rRCRuJpE4lth8ShgjTtNTHfklBD6Ztymc7q7bdPWpKOEvO5lDQ6
q8+KfENv862cOLlWLk7YR2+mHZ1PXGhWC7ggwEkfGJoXo0x8X+zgUKe2+9Jj4yEhfL0IbFYC
z2J5d+cWVIBktI3xqkwLUZWuAbE3vgYA4h8ztR6l18NTPkiAvpNQEaL4ZRnAx22WdsQ8GlEW
dyKZBWbLUdNcMmPfGi5FCw2nNvCyN6ktv5mTZE12EqgvpzYcuUGQPIMV9KTlSPum3NLDq8QI
6grbG8iNNpEBxmCQOKz2/BuYApU2hwt2E44fL8e6CRK3ridcRdqpueg75my6KkOqm8nSiMEc
/pVIHwdJ9/quiuRaeC/tZWlYPIwDWgb8ZE/g66z35WAguMQ+EwfvgAUAEQEAAcLBZQQYAQIA
DwUCU+TvigIbDAUJEswDAAAKCRDvc06md/MRKaZwD/9OI3o3gVmst/mGx6hVQry++ht8dFWN
IiASPBvD3E5EWbqWi6mmqSIOS6CxjU0PncxTBPCXtzxo/WzuHGQg/xtNeQ0T8b2lBScZAw93
qm1IcHXLUe5w/Tap6YaDmSYCIZAdtbHzYfPW4JK7cmvcjvF8jhTFOBEOFVQkTi19G7caVot0
+wL1e2DRHDXAe5CinEpaLBlwHeEu/5j6wc3erohUZlK9IbAclj4iZTQbaq3EyqUXl59dBOON
xmL5edJxzVishIYQGIyA9WP1SylXt+kO82NEqZG2OxdXAlzjuJ8C2pAG+nbLtDo4hcsiN/MA
aX9/JB7MXclT5ioerF4yNgKEdfq7LmynsTUd8w/Ilyp7AD+BWoujyO94i8h9eKvjf9PvSwxQ
uAjRpxne7ZJD8vCsMNXBHSbeEK2LiwStHL/w473viXpDD53J6OLxX6a5RummR+rixbMH7dgK
MJQ7FlyDphm3or6CSkGEir1KA0y1vqQNFtHhguFapAWMDKaJjQQNgvZUmOo6hbZqmvUF1OWc
d6GA6j3WOUe3fDJXfbq6P9Jmxq64op887dYKsg7xjQq/7KM7wyRcqXXcbBdgvNtVDP+EnzBN
HyYY/3ms4YIHE5JHxQ9LV4yPcWkYTvb1XpNIFVbrSXAeyGHVNT+SO6olFovbWIC3Az9yesaM
1aSoTg==
Message-ID: <0e1c0287-617c-976c-9fd4-16683881d5d5@riseup.net>
Date: Tue, 28 Apr 2020 14:03:36 +0100
MIME-Version: 1.0
In-Reply-To: <-_xRcjb8H_0Bck71k4VkeukEBgHT-03ikLTIdyTG2P0rt0T_mvN4b4FejmWobwnAUCGNaDpFQlPc3TMwlml1gjnZ1lwSumeEYQpXSyijND0=@protonmail.com>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 8bit
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: Tue, 28 Apr 2020 13:03:44 -0000
On 24/04/2020 02:34, ZmnSCPxj via bitcoin-dev wrote:
> Good morning Germán,
>
>
>> With regards to trying to tackle the problem of value-based correlations, wouldn't it be possible to try to model the solution after the equal-sum-subset problem (np complete problem)( https://www.cs.mcgill.ca/~lyepre/pdf/assignment2-solutions/subsetSumNPCompleteness.pdf )?
>> That is, a pair of individuals with a set of UTXOs that both add up to similar if not equal value perform a swap of similar-(total)value sets. In this way the values of the UTXOs can be broken up essentially at random (following some nominal distribution so that it doesn't stand out; e.g. https://en.wikipedia.org/wiki/Benford%27s_law), but swapped in conjunction and decorrelated by using different keys + randomized locktimes.
>
> There are a number of issues to simply modeling this to the subset-sum problem.
>
> * There is a practical limit to the number of UTXOs you would be willing to receive in the swap.
> * Every UTXO you receive increases the potential fee you have to pay to spend them, meaning you would strongly dislike receiving 100 UTXOs that sum up to 1mBTC.
> * Thus, a practical blockchain analyst can bound the size of the sets involved, and the problem becomes less than NP in practice.
> * If you have a single UTXO and split it, then swap, anyone looking at the history can conjecture that the split involved is part of a CoinSwap.
> * The split is now a hint on how the subset sums can be tried.
> * If after the CoinSwap you spend the UTXOs you received in a single transaction, then you just published the solution to the subset sum for your adversary.
> * This ties in even further to the "practical limit on the number of UTXOs".
> * Because it is not safe to spend the UTXOs from a single CoinSwap together, you want to have fewer, larger UTXOs for more flexibility in spending later.
>
> I believe belcher and waxwing and nopara73 have been working far longer on privacy tech, and you should try to get in contact with them as well, they may know of other issues (or solutions to the above problems).
>
> Regards,
> ZmnSCPxj
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
Hello list,
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 back
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)
This kind of thing could also be used for consolidation of many UTXOs
without necessarily leaking information that the same person owns them.
For example, if Alice owns 5 UTXOs:
Alice TXO1 ----> Coinswap Protocol ----> Alice TXO
Alice TXO2 ---->
Alice TXO3 ---->
Alice TXO4 ---->
Alice TXO5 ---->
* 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 of
users inadvertently co-spending all their coinswap outputs in the same
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).
* 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 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 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 much
due to the huge number of false positives.
Regards
CB
|
