Received-SPF: pass (sog-mx-2.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; 
From: Tim Ruffing <tim.ruffing@mmci.uni-saarland.de>
To: bitcoin-development@lists.sourceforge.net
Date: Thu, 07 Aug 2014 00:22:31 +0200
Message-ID: <8137823.B0x87S28xY@calzone>
User-Agent: KMail/4.13.3 (Linux/3.15.8-1-ARCH; KDE/4.13.3; x86_64; ; )
MIME-Version: 1.0
Content-Type: multipart/signed; boundary="nextPart1984975.ukO2rNCWy2";
	micalg="pgp-sha1"; protocol="application/pgp-signature"
Subject: [Bitcoin-development] CoinShuffle: decentralized CoinJoin without
	trusted third parties
Precedence: list


--nextPart1984975.ukO2rNCWy2
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain; charset="us-ascii"

Hey,

We (a group of researchers in Germany) propose a decentralized protocol=
 for=20
CoinJoin, a way to mix coins among users to improve anonymity. Our prot=
ocol is=20
called CoinShuffle. We believe that CoinShuffle is a way to implement C=
oinJoin=20
in the original spirit of Bitcoin, i.e., decentralized and without trus=
ted=20
third parties. (If you are not familiar with CoinJoin, the idea is expl=
ained=20
here: https://bitcointalk.org/index.php?topic=3D279249.0 )

The protocol is essentially a clever way to create a CoinJoin transacti=
on.=20
Recall that the idea of CoinJoin is mixing with one SINGLE transaction =
that=20
has multiple input addresses and multiple fresh output addresses (i.e.,=
 one=20
pair of addresses per user). The advantage of CoinJoin over mixing with=
 a=20
server or trusted party is that nobody can steal coins. Each user can c=
heck if=20
the single transaction sends enough coins to his fresh output address. =
If this=20
is not the case, the user can just refuse to sign the transaction and n=
othing=20
(bad) happens.

The difficulty in CoinJoin is to let the participants announce their fr=
esh=20
output addresses without breaking anonymity: Of course, if a participan=
t of=20
the protocol just announces "I have 1 BTC at address X now" and "I woul=
d like=20
to have it back at address Y", then everybody can link X and Y and mixi=
ng is=20
useless. A naive approach is to send these two messages via a secure ch=
annel=20
to a server that organizes the whole mixing. While the server cannot st=
eal=20
coins, the server still has to be trusted for anonymity, because it kno=
ws=20
which input addresses belong to which output addresses.

We present the list of CoinShuffle's features at the end of this e-mail=
. An=20
overview over the technical details can be found on the project page:
http://crypsys.mmci.uni-saarland.de/projects/CoinShuffle/

Moreover, for the full details, have a look at the research paper on=20=

CoinShuffle that can be found here:
http://crypsys.mmci.uni-saarland.de/projects/CoinShuffle/coinshuffle.pd=
f

The paper has been accepted at a major European academic conference on=20=

security (ESORICS). We will present the idea there.=20

Our Proof-of-concept Implementation
=2D----------------------------------
There is a proof-of-concept implementation (written in Python) availabl=
e on=20
our project page. It is really only a proof-of-concept and it implement=
s only=20
the announcement of the addresses, not the creation of the transaction.=
=20
Moreover, the code is CERTAINLY INSECURE and not well-written; our only=
 goal=20
was to demonstrate feasibility and estimate the performance of our appr=
oach.


Our Future Plans
=2D---------------
Now we are planning a full, open-source implementation of the protocol.=
 Of=20
course, we would like to build on top of an existing wide-spread client=
. Since=20
we do not have much experience in the design of existing Bitcoin client=
s, we=20
would appreciate any help in the process. In particular, we did not dec=
ide=20
which of the existing clients we would like to extend. Any hints toward=
s this=20
decisions would very helpful. Help in design and coding would be great =
but we=20
also would like to hear your comments, criticism, and improvements for =
the=20
protocol itself.

CoinShuffle Features
=2D-------------------
CoinShuffle has the following features:

 - Decentralization / no third party:
There is no (trusted or untrusted) third party in a run of the protocol=
.=20
(Still, as in all mixing solutions, users need some way to gather toget=
her=20
before they can run the protocol. This can be done via a P2P protocol i=
f a=20
decentralized solution is desired also for this step.)

  =20
 - Unlinkability of input and output addresses:
Nobody, in particular no server (there is none!), can link input and ou=
tput=20
addresses of a mixing transaction, as long as there are at least two ho=
nest=20
participants in run of the protocol.
  =20
(This is not a weakness: If there is only one honest participant, meani=
ngful=20
mixing is just impossible, no matter how it is organized. If all the ot=
her=20
participants collude, they know all their input and output addresses an=
d can=20
immediately determine the output address of the honest participant.)

 - Security against thefts:
As explained above, nobody can steal coins during the mixing because of=
 the=20
CoinJoin principle. =20
Every participant can verify that his money will not be stolen. Otherwi=
se, he=20
refuses to sign the transaction and nothing will happen.

 - Robustness against denial-of-service:
In CoinJoin, a single malicious (or malfunctioning) client suffices to =
stop=20
the whole protocol (e.g., by just refusing to sing the transaction with=
out a=20
proper reason.) This can easily lead to DoS attacks but these can be co=
untered=20
in CoinShuffle.
  =20
While in case of disruption, the current run of the protocol has to sto=
p,=20
CoinShuffle addresses this problem as follows:  In case of active disru=
ption,=20
i.e., some participant sends wrong messages, the protocol provides a pr=
oof of=20
this misbehavior. Then the honest protocol parties can start a new run =
of the=20
protocol without the misbehaving participant. Also in case of passive=20=

disruption, i.e., some participant does not respond (for whatever reaso=
n), the=20
remaining participants can agree on starting a new run without this=20
participant. This ensures that the protocol will finally succeed even i=
n the=20
presence of malicious participant (although this can take quite a while=
 then).

 - Only public-key encryption and signatures:
The protocol requires only well-established cryptographic primitives. B=
esides=20
signatures and hash functions (that are already used by Bitcoin), only=20=

standard public-key encryption is necessary.
 =20
 - Efficiency:
A run of the protocol with 30 participants takes less than 100 seconds =
(in a=20
setting with reasonable bandwidth and delay). This is not much, given t=
hat 10=20
min (on average) are required to confirm the mixing transaction anyway.=

  =20
The costs are almost completely caused by communication. The computatio=
n=20
overhead is minimal. (This is the main achievement actually. In theory,=
 it is=20
clear that a protocol with all the properties can be built. However, ge=
neric=20
constructions cannot be used in practice yet, because the computation a=
nd=20
communication costs are huge.)

=2D Compatibility:
As CoinShuffle works on top of Bitcoin, it is fully compatible with the=
=20
current Bitcoin system. No changes to the Bitcoin protocol are required=
.


By the way: The NXT cryptocurrency picked up our idea and an implementa=
tion of=20
CoinShuffle for a part of NXT is under way. (=20
https://twitter.com/comefrombeyond/status/485429369268350977 )

 =20
TL,DR:
Mixing is the way to improve anonymity in Bitcoin now, as it does not r=
equire=20
changes to the Bitcoin protocol. We propose CoinShuffle, a decentralize=
d=20
protocol to perform mixing in a secure way without trusted third partie=
s, see=20
http://crypsys.mmci.uni-saarland.de/projects/CoinShuffle/ for a technic=
al=20
overview. Our next step is to implement the protocol. Help in design an=
d=20
coding would be great but we also would like to hear your comments, cri=
ticism,=20
and improvements for the protocol itself.=20

Best,
Tim Ruffing, Pedro Moreno-Sanchez, Aniket Kate

--nextPart1984975.ukO2rNCWy2
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

iQGcBAABAgAGBQJT4qquAAoJEKAmVAtPJmh7gkgL/3JWrkCWsNfxaulOggoFq5v9
esRFrQigKXtrmTl79lGtSQWmvjkrra7Nladr+VTWfXOJhcOlZIBxWYUMw/A7J7DP
z7siF+pKbl+XeSUjgPKB49FOJi7LiUHLaFeTVXaNebf64w3cC9etYIiNxmLx1c5D
j7ysYnLmD8/3Cpr4VbIaqylVSqIV7n6czjVAyo7UeQxUFu/Ry8zXA7xEJXwG9VRO
9SIWFjfQkjiwFfh2OvGiH11qGI3mR0YFE0ExkUdjm/6oGkxhNXFbVgNAsjlO2HHr
Qxcoq51a3gfb3de7IiUoy9fWxo4D/c72nJRUYIk23wJvaKeRFqcHkNHvk47rsPjG
XJm25z8PIbPdYQ64n4o6vVrdLYqwjs5lQDkmCgpGK7ZgTumhieSzG7tDW1tXkuau
uPV3LW34salJhVC11DSOJY4TEyAPOWDeymLy4l6nvOD7vHqVlxKZJasykpzp7jGJ
euFakyZekXmZCPnAxG7mISIxa48BF41GFX+XkCxaXQ==
=Vj03
-----END PGP SIGNATURE-----

--nextPart1984975.ukO2rNCWy2--