From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from sog-mx-4.v43.ch3.sourceforge.com ([172.29.43.194] helo=mx.sourceforge.net) by sfs-ml-3.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1XGj7f-00014k-Pv for bitcoin-development@lists.sourceforge.net; Mon, 11 Aug 2014 06:30:23 +0000 Received-SPF: pass (sog-mx-4.v43.ch3.sourceforge.com: domain of gmail.com designates 209.85.214.174 as permitted sender) client-ip=209.85.214.174; envelope-from=ctpacia@gmail.com; helo=mail-ob0-f174.google.com; Received: from mail-ob0-f174.google.com ([209.85.214.174]) by sog-mx-4.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128) (Exim 4.76) id 1XGj7e-0003HB-2G for bitcoin-development@lists.sourceforge.net; Mon, 11 Aug 2014 06:30:23 +0000 Received: by mail-ob0-f174.google.com with SMTP id vb8so5691019obc.19 for ; Sun, 10 Aug 2014 23:30:16 -0700 (PDT) MIME-Version: 1.0 X-Received: by 10.60.45.234 with SMTP id q10mr47562024oem.25.1407738616595; Sun, 10 Aug 2014 23:30:16 -0700 (PDT) Received: by 10.202.107.7 with HTTP; Sun, 10 Aug 2014 23:30:16 -0700 (PDT) Received: by 10.202.107.7 with HTTP; Sun, 10 Aug 2014 23:30:16 -0700 (PDT) In-Reply-To: References: <8137823.B0x87S28xY@calzone> Date: Mon, 11 Aug 2014 02:30:16 -0400 Message-ID: From: Chris Pacia To: Tim Ruffing Content-Type: multipart/alternative; boundary=001a11c21b062dcb48050054b00d X-Spam-Score: -0.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 FREEMAIL_FROM Sender email is commonly abused enduser mail provider (ctpacia[at]gmail.com) -0.0 SPF_PASS SPF: sender matches SPF record 0.0 T_TVD_FUZZY_SECURITIES BODY: T_TVD_FUZZY_SECURITIES 1.0 HTML_MESSAGE BODY: HTML included in message -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: 1XGj7e-0003HB-2G Cc: Bitcoin Dev 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: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 11 Aug 2014 06:30:24 -0000 --001a11c21b062dcb48050054b00d Content-Type: text/plain; charset=UTF-8 Actually getUTXO would probably work here as well. It isn't authenticated but it should be good enough for this purpose. The worst that would happen is the tx doesn't confirm. On Aug 11, 2014 2:25 AM, "Chris Pacia" wrote: > One issue I do see is the protocol requires participants to check the > inputs submitted by others are valid. Lite clients (at least of the p2p > variety) cannot perform this check. > > You could skip the verification part and if the inputs turn out to be > invalid then you'll find out when it doesn't confirm. This would problem > open the protocol up to dos attacks and prevent part of the "blame" phase > from working properly. > > Alternatively you can have the participants submit the merkle proof for > the input. This would require inputs to have at least one confirmation, > however. > On Aug 6, 2014 6:42 PM, "Tim Ruffing" > wrote: > >> Hey, >> >> We (a group of researchers in Germany) propose a decentralized protocol >> for >> CoinJoin, a way to mix coins among users to improve anonymity. Our >> protocol is >> called CoinShuffle. We believe that CoinShuffle is a way to implement >> CoinJoin >> in the original spirit of Bitcoin, i.e., decentralized and without trusted >> third parties. (If you are not familiar with CoinJoin, the idea is >> explained >> here: https://bitcointalk.org/index.php?topic=279249.0 ) >> >> The protocol is essentially a clever way to create a CoinJoin transaction. >> Recall that the idea of CoinJoin is mixing with one SINGLE transaction >> that >> has multiple input addresses and multiple fresh output addresses (i.e., >> one >> pair of addresses per user). The advantage of CoinJoin over mixing with a >> server or trusted party is that nobody can steal coins. Each user can >> check if >> the single transaction sends enough coins to his fresh output address. If >> this >> is not the case, the user can just refuse to sign the transaction and >> nothing >> (bad) happens. >> >> The difficulty in CoinJoin is to let the participants announce their fresh >> output addresses without breaking anonymity: Of course, if a participant >> of >> the protocol just announces "I have 1 BTC at address X now" and "I would >> like >> to have it back at address Y", then everybody can link X and Y and mixing >> is >> useless. A naive approach is to send these two messages via a secure >> channel >> to a server that organizes the whole mixing. While the server cannot steal >> coins, the server still has to be trusted for anonymity, because it knows >> which input addresses belong to which output addresses. >> >> We present the list of CoinShuffle's features at the end of this e-mail. >> An >> 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 >> CoinShuffle that can be found here: >> http://crypsys.mmci.uni-saarland.de/projects/CoinShuffle/coinshuffle.pdf >> >> The paper has been accepted at a major European academic conference on >> security (ESORICS). We will present the idea there. >> >> Our Proof-of-concept Implementation >> ----------------------------------- >> There is a proof-of-concept implementation (written in Python) available >> on >> our project page. It is really only a proof-of-concept and it implements >> only >> the announcement of the addresses, not the creation of the transaction. >> Moreover, the code is CERTAINLY INSECURE and not well-written; our only >> goal >> was to demonstrate feasibility and estimate the performance of our >> approach. >> >> >> Our Future Plans >> ---------------- >> Now we are planning a full, open-source implementation of the protocol. Of >> course, we would like to build on top of an existing wide-spread client. >> Since >> we do not have much experience in the design of existing Bitcoin clients, >> we >> would appreciate any help in the process. In particular, we did not decide >> which of the existing clients we would like to extend. Any hints towards >> this >> decisions would very helpful. Help in design and coding would be great >> but we >> also would like to hear your comments, criticism, and improvements for the >> protocol itself. >> >> CoinShuffle Features >> -------------------- >> CoinShuffle has the following features: >> >> - Decentralization / no third party: >> There is no (trusted or untrusted) third party in a run of the protocol. >> (Still, as in all mixing solutions, users need some way to gather together >> before they can run the protocol. This can be done via a P2P protocol if a >> decentralized solution is desired also for this step.) >> >> >> - Unlinkability of input and output addresses: >> Nobody, in particular no server (there is none!), can link input and >> output >> addresses of a mixing transaction, as long as there are at least two >> honest >> participants in run of the protocol. >> >> (This is not a weakness: If there is only one honest participant, >> meaningful >> mixing is just impossible, no matter how it is organized. If all the other >> participants collude, they know all their input and output addresses and >> can >> 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 >> CoinJoin principle. >> Every participant can verify that his money will not be stolen. >> Otherwise, he >> 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 >> the whole protocol (e.g., by just refusing to sing the transaction >> without a >> proper reason.) This can easily lead to DoS attacks but these can be >> countered >> in CoinShuffle. >> >> While in case of disruption, the current run of the protocol has to stop, >> CoinShuffle addresses this problem as follows: In case of active >> disruption, >> i.e., some participant sends wrong messages, the protocol provides a >> proof of >> this misbehavior. Then the honest protocol parties can start a new run of >> the >> protocol without the misbehaving participant. Also in case of passive >> disruption, i.e., some participant does not respond (for whatever >> reason), the >> remaining participants can agree on starting a new run without this >> participant. This ensures that the protocol will finally succeed even in >> the >> 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. >> Besides >> signatures and hash functions (that are already used by Bitcoin), only >> standard public-key encryption is necessary. >> >> - Efficiency: >> A run of the protocol with 30 participants takes less than 100 seconds >> (in a >> setting with reasonable bandwidth and delay). This is not much, given >> that 10 >> min (on average) are required to confirm the mixing transaction anyway. >> >> The costs are almost completely caused by communication. The computation >> overhead is minimal. (This is the main achievement actually. In theory, >> it is >> clear that a protocol with all the properties can be built. However, >> generic >> constructions cannot be used in practice yet, because the computation and >> communication costs are huge.) >> >> - Compatibility: >> As CoinShuffle works on top of Bitcoin, it is fully compatible with the >> current Bitcoin system. No changes to the Bitcoin protocol are required. >> >> >> By the way: The NXT cryptocurrency picked up our idea and an >> implementation of >> CoinShuffle for a part of NXT is under way. ( >> https://twitter.com/comefrombeyond/status/485429369268350977 ) >> >> >> TL,DR: >> Mixing is the way to improve anonymity in Bitcoin now, as it does not >> require >> changes to the Bitcoin protocol. We propose CoinShuffle, a decentralized >> protocol to perform mixing in a secure way without trusted third parties, >> see >> http://crypsys.mmci.uni-saarland.de/projects/CoinShuffle/ for a technical >> overview. Our next step is to implement the protocol. Help in design and >> coding would be great but we also would like to hear your comments, >> criticism, >> and improvements for the protocol itself. >> >> Best, >> Tim Ruffing, Pedro Moreno-Sanchez, Aniket Kate >> >> >> ------------------------------------------------------------------------------ >> Infragistics Professional >> Build stunning WinForms apps today! >> Reboot your WinForms applications with our WinForms controls. >> Build a bridge from your legacy apps to the future. >> >> http://pubads.g.doubleclick.net/gampad/clk?id=153845071&iu=/4140/ostg.clktrk >> _______________________________________________ >> Bitcoin-development mailing list >> Bitcoin-development@lists.sourceforge.net >> https://lists.sourceforge.net/lists/listinfo/bitcoin-development >> >> --001a11c21b062dcb48050054b00d Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable

Actually getUTXO would probably work here as well. It isn= 9;t authenticated but it should be good enough for this purpose. The worst = that would happen is the tx doesn't confirm.

On Aug 11, 2014 2:25 AM, "Chris Pacia"= <ctpacia@gmail.com> wrote:<= br type=3D"attribution">

One issue I do see is the protocol requires participants to = check the inputs submitted by others are valid. Lite clients (at least of t= he p2p variety) cannot perform this check.=C2=A0

You could skip the verification part and if the inputs turn = out to be invalid then you'll find out when it doesn't confirm. Thi= s would problem open the protocol up to dos attacks and prevent part of the= "blame" phase from working properly.

Alternatively you can have the participants submit the merkl= e proof for the input. This would require inputs to have at least one confi= rmation, however.

On Aug 6, 2014 6:42 PM, "Tim Ruffing" = <t= im.ruffing@mmci.uni-saarland.de> wrote:
Hey,

We (a group of researchers in Germany) propose a decentralized protocol for=
CoinJoin, a way to mix coins among users to improve anonymity. Our protocol= is
called CoinShuffle. We believe that CoinShuffle is a way to implement CoinJ= oin
in the original spirit of Bitcoin, i.e., decentralized and without trusted<= br> third parties. (If you are not familiar with CoinJoin, the idea is explaine= d
here: https://bitcointalk.org/index.php?topic=3D279249.0 )

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

The difficulty in CoinJoin is to let the participants announce their fresh<= br> output addresses without breaking anonymity: Of course, if a participant of=
the protocol just announces "I have 1 BTC at address X now" and &= quot;I would like
to have it back at address Y", then everybody can link X and Y and mix= ing is
useless. A naive approach is to send these two messages via a secure channe= l
to a server that organizes the whole mixing. While the server cannot steal<= br> coins, the server still has to be trusted for anonymity, because it knows which input addresses belong to which output addresses.

We present the list of CoinShuffle's features at the end of this e-mail= . An
overview over the technical details can be found on the project page:
http://crypsys.mmci.uni-saarland.de/projects/CoinShuffle/<= br>
Moreover, for the full details, have a look at the research paper on
CoinShuffle that can be found here:
http://crypsys.mmci.uni-saarland.de/projects/Co= inShuffle/coinshuffle.pdf

The paper has been accepted at a major European academic conference on
security (ESORICS). We will present the idea there.

Our Proof-of-concept Implementation
-----------------------------------
There is a proof-of-concept implementation (written in Python) available on=
our project page. It is really only a proof-of-concept and it implements on= ly
the announcement of the addresses, not the creation of the transaction.
Moreover, the code is CERTAINLY INSECURE and not well-written; our only goa= l
was to demonstrate feasibility and estimate the performance of our approach= .


Our Future Plans
----------------
Now we are planning a full, open-source implementation of the protocol. Of<= br> course, we would like to build on top of an existing wide-spread client. Si= nce
we do not have much experience in the design of existing Bitcoin clients, w= e
would appreciate any help in the process. In particular, we did not decide<= br> which of the existing clients we would like to extend. Any hints towards th= is
decisions would very helpful. Help in design and coding would be great but = we
also would like to hear your comments, criticism, and improvements for the<= br> protocol itself.

CoinShuffle Features
--------------------
CoinShuffle has the following features:

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


=C2=A0- Unlinkability of input and output addresses:
Nobody, in particular no server (there is none!), can link input and output=
addresses of a mixing transaction, as long as there are at least two honest=
participants in run of the protocol.

(This is not a weakness: If there is only one honest participant, meaningfu= l
mixing is just impossible, no matter how it is organized. If all the other<= br> participants collude, they know all their input and output addresses and ca= n
immediately determine the output address of the honest participant.)

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

=C2=A0- Robustness against denial-of-service:
In CoinJoin, a single malicious (or malfunctioning) client suffices to stop=
the whole protocol (e.g., by just refusing to sing the transaction without = a
proper reason.) This can easily lead to DoS attacks but these can be counte= red
in CoinShuffle.

While in case of disruption, the current run of the protocol has to stop, CoinShuffle addresses this problem as follows: =C2=A0In case of active disr= uption,
i.e., some participant sends wrong messages, the protocol provides a proof = of
this misbehavior. Then the honest protocol parties can start a new run of t= he
protocol without the misbehaving participant. Also in case of passive
disruption, i.e., some participant does not respond (for whatever reason), = the
remaining participants can agree on starting a new run without this
participant. This ensures that the protocol will finally succeed even in th= e
presence of malicious participant (although this can take quite a while the= n).

=C2=A0- Only public-key encryption and signatures:
The protocol requires only well-established cryptographic primitives. Besid= es
signatures and hash functions (that are already used by Bitcoin), only
standard public-key encryption is necessary.

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

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

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

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


TL,DR:
Mixing is the way to improve anonymity in Bitcoin now, as it does not requi= re
changes to the Bitcoin protocol. We propose CoinShuffle, a decentralized protocol to perform mixing in a secure way without trusted third parties, s= ee
http://crypsys.mmci.uni-saarland.de/projects/CoinShuffle/ = for a technical
overview. Our next step is to implement the protocol. Help in design and coding would be great but we also would like to hear your comments, critici= sm,
and improvements for the protocol itself.

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

-----------------------------------------------------------------------= -------
Infragistics Professional
Build stunning WinForms apps today!
Reboot your WinForms applications with our WinForms controls.
Build a bridge from your legacy apps to the future.
http://pubads.g.doubleclick.net/gam= pad/clk?id=3D153845071&iu=3D/4140/ostg.clktrk
__________________= _____________________________
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-de= velopment

--001a11c21b062dcb48050054b00d--