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
|
Received: from sog-mx-1.v43.ch3.sourceforge.com ([172.29.43.191]
helo=mx.sourceforge.net)
by sfs-ml-2.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
(envelope-from <tim.ruffing@mmci.uni-saarland.de>)
id 1XG3WM-0003go-MQ for bitcoin-development@lists.sourceforge.net;
Sat, 09 Aug 2014 10:05:06 +0000
Received-SPF: pass (sog-mx-1.v43.ch3.sourceforge.com: domain of
mmci.uni-saarland.de designates 139.19.1.49 as permitted
sender) client-ip=139.19.1.49;
envelope-from=tim.ruffing@mmci.uni-saarland.de;
helo=hera.mpi-klsb.mpg.de;
Received: from infao0809.mpi-klsb.mpg.de ([139.19.1.49]
helo=hera.mpi-klsb.mpg.de)
by sog-mx-1.v43.ch3.sourceforge.com with esmtps (TLSv1:AES128-SHA:128)
(Exim 4.76) id 1XG3WK-0007pQ-Ar
for bitcoin-development@lists.sourceforge.net;
Sat, 09 Aug 2014 10:05:06 +0000
Received: from zak.mpi-klsb.mpg.de ([139.19.1.29]:55288)
by hera.mpi-klsb.mpg.de (envelope-from
<tim.ruffing@mmci.uni-saarland.de>)
with esmtp (Exim 4.80) id 1XG3WB-0007Ng-94
for bitcoin-development@lists.sourceforge.net;
Sat, 09 Aug 2014 12:04:57 +0200
Received: from [141.70.80.5] (port=29311 helo=calzone.localnet)
by zak.mpi-klsb.mpg.de (envelope-from
<tim.ruffing@mmci.uni-saarland.de>)
with esmtpsa (TLS1.2:DHE_RSA_AES_256_CBC_SHA256:256)
(Exim 4.80) id 1XG3WA-0007u2-VZ
for bitcoin-development@lists.sourceforge.net;
Sat, 09 Aug 2014 12:04:55 +0200
From: Tim Ruffing <tim.ruffing@mmci.uni-saarland.de>
To: bitcoin-development@lists.sourceforge.net
Date: Sat, 09 Aug 2014 12:04:51 +0200
Message-ID: <5456835.U3gAI91RM4@calzone>
User-Agent: KMail/4.13.3 (Linux/3.15.8-1-ARCH; KDE/4.13.3; x86_64; ; )
In-Reply-To: <1530801.palqu9XdN4@1337h4x0r>
References: <8137823.B0x87S28xY@calzone> <1530801.palqu9XdN4@1337h4x0r>
MIME-Version: 1.0
Content-Type: multipart/signed; boundary="nextPart2588564.XKcU0yCBmf";
micalg="pgp-sha1"; protocol="application/pgp-signature"
X-MPI-Local-Sender: true
X-Spam-Score: 0.7 (/)
X-Spam-Report: Spam Filtering performed by mx.sourceforge.net.
See http://spamassassin.org/tag/ for more details.
-1.5 SPF_CHECK_PASS SPF reports sender host as permitted sender for
sender-domain
-0.0 SPF_PASS SPF: sender matches SPF record
2.3 URI_NO_WWW_INFO_CGI URI: CGI in .info TLD other than third-level
"www"
-0.1 DKIM_VALID_AU Message has a valid DKIM or DK signature from
author's domain
0.1 DKIM_SIGNED Message has a DKIM or DK signature,
not necessarily valid
-0.1 DKIM_VALID Message has at least one valid DKIM or DK signature
X-Headers-End: 1XG3WK-0007pQ-Ar
Subject: Re: [Bitcoin-development] CoinShuffle: decentralized CoinJoin
without trusted third parties
X-BeenThere: bitcoin-development@lists.sourceforge.net
X-Mailman-Version: 2.1.9
Precedence: list
List-Id: <bitcoin-development.lists.sourceforge.net>
List-Unsubscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
<mailto:bitcoin-development-request@lists.sourceforge.net?subject=unsubscribe>
List-Archive: <http://sourceforge.net/mailarchive/forum.php?forum_name=bitcoin-development>
List-Post: <mailto:bitcoin-development@lists.sourceforge.net>
List-Help: <mailto:bitcoin-development-request@lists.sourceforge.net?subject=help>
List-Subscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
<mailto:bitcoin-development-request@lists.sourceforge.net?subject=subscribe>
X-List-Received-Date: Sat, 09 Aug 2014 10:05:06 -0000
--nextPart2588564.XKcU0yCBmf
Content-Transfer-Encoding: 7Bit
Content-Type: text/plain; charset="us-ascii"
You are raising valid questions and one goal of our posting here is indeed to
discuss exactly these system issues.
On Thursday 07 August 2014 15:00:11 you wrote:
> I think the description at your website leaves out the truly interesting
> part: How do you decentralize this securely?
> - How do Alice, Bob, Charlie and Dave communicate, i.e. which network is
> used for communication and how?
The simplest approach is obviously to use direct connections to a randomly
elected leader, who is also responsible for the broadcasts.
One advantage of CoinShuffle is that the unlinkability between input and
output addresses is guaranteed, no matter which underlying network you use.
(Still, it is a good idea in general to hide your IP address but we can let
the user decide here.)
Of course, there would be other possibilities, such as overlay networks.
Coinmux, a CoinJoin prototype by Michael Pearce (http://coinmux.com/) uses
TomP2P, a distributed hash table, for communication.
Do you have any hints regarding this point?
> - How does Alice know that Bob, Charlie and Dave are not the same person?
> (= how do you prevent a Sybil attack?)
>
> Because thats the real problem with mixing it seems - ensuring that your
> mixing partners are actually 100 people and not just 1 attacker. There are
> probably many mixing algorithms which work if you solve that problem, but I
> don't see how you offer a solution for it :(
It's true that there are a few proposals for mixing protocols which all have
their advantages and disadvantages. However, it's not true that the mixing
itself becomes simple if you solve the problem of Sybil attacks. Still, mixing
is difficult to get right: Even if there are no Sybil attacks, you have to
ensure that the participants (or a server) cannot break unlinkability or steal
money. Actually that's why there are several proposals for mixing protocols,
because there is no obvious perfect solution.
Regarding your question:
It is indeed very important to get this right. Fundamentally, there is nothing
that prevents the attacker from creating a lot of identities participating in
a lot of CoinJoins. However, there are ways that make it hard for the attacker
to put an honest user together only with malicious users.
For a moment, assume that you can reliably establish a pool of users that
would like to participate in the protocol. (I will discuss this later.)
You have to divide the users to individual groups, i.e., CoinJoins runs. If
the assignment cannot be influenced by the attacker, then the probability that
there are also honest users in a run is quite high. Of course, the attacker is
able to reduce your anonymity set but they cannot just put you together only
with their malicious identities.
Note that the attacker has to pay transaction fees for joining many
transaction. One could even increase the required fee depending on the number
of users in the pool (enforced by honest CoinShuffle participants that would
not accept CoinJoins that pay a lower transaction fee).
And making sure that the attacker cannot influence the assignment is simple:
One can use the hash of all users' public keys in the pool to determine the
assignment for example.
For the initial setup step, i.e., creating the pool of participants, you need
some kind of "bulletin board".
One possibility is to use an underlying peer-to-peer network. Bitcoin itself
is the first that comes to the mind but it does not allow arbitrary messages.
So if we do not want to change the Bitcoin protocol, chans in Bitmessage are a
very promising possibility. Bitmessage relies basically on the same broadcast
mechanism as Bitcoin. If you as a peer use enough outgoing connections to
other peers, it's very difficult for an attacker to ensure that your message
will not be spread among the network. (Btw, people have used this to do
CoinJoin manually already
https://forum.namecoin.info/viewtopic.php?f=2&t=1694 .)
Solutions like distributed hashtables (TomP2P again) are another possibility.
We are not sure which of those approaches provides the best robustness against
malicious nodes that try to stop single participants from reaching the
network. For the setup step, latency is not an issue, so Bitmessage is indeed
a promising candidate here.
I think that in general, P2P is the way to go here, but there are other
approaches as well:
- A possibility is to have a lot of servers acting as bulletin
boards. The user sends his announcement message to all of the servers and
the user waits until at some of the servers send back a guarantee to
include the user. After some time, the servers agree on the pool of the users
just by taking all the users that have registered with at least one of the
servers. There are well-understood protocols to achieve this goal or similar
goals, because essentially the same problem arises in e-voting (see
http://arxiv.org/pdf/1401.4151 for just one example. this paper provides also
a detailed discussion of related protocols in section 9).
Of course, the disadvantage of this approach is that the protocol is not
really decentralized anymore.
- If you really want to be on the safe side, you can include your
announcement messages in the Bitcoin blockchain, e.g., by adding your
announcement message to an unspendable output, at the cost of an additional
transaction. I know that putting data to the blockchain is discouraged but let
me explain why it is useful here: If you want to do several CoinJoins in a
row, you can include your announcement message for the second CoinJoin in the
transaction of the first CoinJoin, so your announcement is very robust but you
do not need an additional transaction, because you can piggy-back on the frist
transaction.
Additionally, it is possible to combine these approaches by joining several
pools.
Another interesting point that my co-author Aniket Kate mentioned is that you
can look at that problem as a social issue: You could combine this with
information from your friends. You can participate in a CoinJoin only if your
friends tell you that they also participate in the same run. They do not even
have to reveal their input address, they just have to reveal that their
address is in a particular run. Of course, this is not yet a technical
solution but a very interesting idea.
Don't get me wrong. We don't think that there is a perfect solution the
two issues that you mentioned but we are pretty sure there are several that
work well enough in practice if they are implemented correctly.
Tim
--nextPart2588564.XKcU0yCBmf
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: This is a digitally signed message part.
Content-Transfer-Encoding: 7Bit
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2
iQGcBAABAgAGBQJT5fJHAAoJEKAmVAtPJmh7d4AMANbGUoMjgCuoMU7jb6UfeKm/
e7stEW0IleP7NKyhlGV1XHmT06goj6m8RNkuorTeKGdPjtIU8sRBKbaqWJfjMC3U
t+K4UY7VvcEPHrWuQkrk9fzZNcUhHaS68iePHJ/yQtqbmwG7ozRxf/jUar41hj26
GifILpFu2o3Q96pOLUtBOlA4CO6L78QEpJkgJYOu8I/hxPSGv+4WnwqEjb77e3l5
IbYY3ZCRyNoPlRhEnR3/nqyz0qs7v+CnSFJL61yp8G5rRHGYGQnLzYvjBVV25TuU
EuWRjwGX8KXAfqLtUi2ZpyfwVvh9n6Xv+Q+vzWQo7IwrL/u5m0MQrfDm2rthz9o2
k1vHau32pCnbvAT4ArxV5dHc5djtgNGP/dZ2PM1tXgvIFS3yGVyzzI5rJ72EirAW
oFZlStPTnycmrh/CKErJ5idOOfWrV2E6kscBX2vnCxf6zC0JY4f5M65E5XVj4SWv
JSGQFP4h/SIkF5yhm2Z+IrhGgwGZOUodgkn0Do4L2Q==
=+0fG
-----END PGP SIGNATURE-----
--nextPart2588564.XKcU0yCBmf--
|
