From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from sog-mx-2.v43.ch3.sourceforge.com ([172.29.43.192] helo=mx.sourceforge.net) by sfs-ml-3.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1XF9s1-0001GL-TR for bitcoin-development@lists.sourceforge.net; Wed, 06 Aug 2014 22:39:46 +0000 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; Received: from infao0809.mpi-klsb.mpg.de ([139.19.1.49] helo=hera.mpi-klsb.mpg.de) by sog-mx-2.v43.ch3.sourceforge.com with esmtps (TLSv1:AES128-SHA:128) (Exim 4.76) id 1XF9rz-0002bX-L8 for bitcoin-development@lists.sourceforge.net; Wed, 06 Aug 2014 22:39:45 +0000 Received: from srv-00-126.mpi-klsb.mpg.de ([139.19.1.29]:57867 helo=zak.mpi-klsb.mpg.de) by hera.mpi-klsb.mpg.de (envelope-from ) with esmtp (Exim 4.80) id 1XF9bb-0005XD-B9 for bitcoin-development@lists.sourceforge.net; Thu, 07 Aug 2014 00:22:50 +0200 Received: from 55d423fd.access.ecotel.net ([85.212.35.253]:43361 helo=calzone.localnet) by zak.mpi-klsb.mpg.de (envelope-from ) with esmtpsa (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:256) (Exim 4.80) id 1XF9bb-0003XG-12 for bitcoin-development@lists.sourceforge.net; Thu, 07 Aug 2014 00:22:47 +0200 From: Tim Ruffing 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" X-MPI-Local-Sender: true X-Spam-Score: -1.6 (-) 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 0.0 T_TVD_FUZZY_SECURITIES BODY: T_TVD_FUZZY_SECURITIES -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: 1XF9rz-0002bX-L8 Subject: [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: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 06 Aug 2014 22:39:46 -0000 --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--