* [Bitcoin-development] CoinShuffle: decentralized CoinJoin without trusted third parties
@ 2014-08-06 22:22 Tim Ruffing
2014-08-07 13:00 ` xor
2014-08-11 6:25 ` Chris Pacia
0 siblings, 2 replies; 10+ messages in thread
From: Tim Ruffing @ 2014-08-06 22:22 UTC (permalink / raw)
To: bitcoin-development
[-- Attachment #1: Type: text/plain, Size: 7272 bytes --]
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
[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 648 bytes --]
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [Bitcoin-development] CoinShuffle: decentralized CoinJoin without trusted third parties
2014-08-06 22:22 [Bitcoin-development] CoinShuffle: decentralized CoinJoin without trusted third parties Tim Ruffing
@ 2014-08-07 13:00 ` xor
2014-08-09 10:04 ` Tim Ruffing
2014-08-11 6:25 ` Chris Pacia
1 sibling, 1 reply; 10+ messages in thread
From: xor @ 2014-08-07 13:00 UTC (permalink / raw)
To: bitcoin-development
[-- Attachment #1: Type: text/plain, Size: 1111 bytes --]
On Thursday, August 07, 2014 12:22:31 AM Tim Ruffing wrote:
> - 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.)
[...]
> http://crypsys.mmci.uni-saarland.de/projects/CoinShuffle/ for a technical
> overview.
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?
- 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 :(
[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 836 bytes --]
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [Bitcoin-development] CoinShuffle: decentralized CoinJoin without trusted third parties
2014-08-07 13:00 ` xor
@ 2014-08-09 10:04 ` Tim Ruffing
2014-08-09 13:10 ` Sergio Lerner
0 siblings, 1 reply; 10+ messages in thread
From: Tim Ruffing @ 2014-08-09 10:04 UTC (permalink / raw)
To: bitcoin-development
[-- Attachment #1: Type: text/plain, Size: 6579 bytes --]
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
[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 648 bytes --]
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [Bitcoin-development] CoinShuffle: decentralized CoinJoin without trusted third parties
2014-08-09 10:04 ` Tim Ruffing
@ 2014-08-09 13:10 ` Sergio Lerner
2014-08-09 20:17 ` Mark Friedenbach
0 siblings, 1 reply; 10+ messages in thread
From: Sergio Lerner @ 2014-08-09 13:10 UTC (permalink / raw)
To: bitcoin-development
[-- Attachment #1: Type: text/plain, Size: 7674 bytes --]
Hi Tim,
It's clear from the paper that the second party in the protocol can
de-anonymize the first party. So it's seems that dishonest shufflers
would prefer to be in that position in the queue.
There are two possible solutions to this:
1. Derive the first order of parties in the shuffle from the hash of all
inputs provided (as a seed for a pseudo-random number generator).
2. Repeat the shuffle several times with an different party order (e.g.
an order that is deterministically derived from the hash of all the outputs)
Best regards,
Sergio/
On 09/08/2014 07:04 a.m., Tim Ruffing wrote:
> 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
>
>
> ------------------------------------------------------------------------------
>
>
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists•sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
[-- Attachment #2: Type: text/html, Size: 8765 bytes --]
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [Bitcoin-development] CoinShuffle: decentralized CoinJoin without trusted third parties
2014-08-09 13:10 ` Sergio Lerner
@ 2014-08-09 20:17 ` Mark Friedenbach
0 siblings, 0 replies; 10+ messages in thread
From: Mark Friedenbach @ 2014-08-09 20:17 UTC (permalink / raw)
To: Sergio Lerner; +Cc: bitcoin-development
[-- Attachment #1: Type: text/plain, Size: 444 bytes --]
On Sat, Aug 9, 2014 at 6:10 AM, Sergio Lerner <sergiolerner@certimix•com>
wrote:
> Hi Tim,
> It's clear from the paper that the second party in the protocol can
> de-anonymize the first party. So it's seems that dishonest shufflers would
> prefer to be in that position in the queue.
>
That's not clear to me. The 2nd party doesn't know how the 3rd, 4th, 5th,
etc. parties shuffled the outputs, since it doesn't have their decryption
keys.
[-- Attachment #2: Type: text/html, Size: 879 bytes --]
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [Bitcoin-development] CoinShuffle: decentralized CoinJoin without trusted third parties
2014-08-06 22:22 [Bitcoin-development] CoinShuffle: decentralized CoinJoin without trusted third parties Tim Ruffing
2014-08-07 13:00 ` xor
@ 2014-08-11 6:25 ` Chris Pacia
2014-08-11 6:30 ` Chris Pacia
1 sibling, 1 reply; 10+ messages in thread
From: Chris Pacia @ 2014-08-11 6:25 UTC (permalink / raw)
To: Tim Ruffing; +Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 8569 bytes --]
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" <tim.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
> 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
>
>
[-- Attachment #2: Type: text/html, Size: 10034 bytes --]
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [Bitcoin-development] CoinShuffle: decentralized CoinJoin without trusted third parties
2014-08-11 6:25 ` Chris Pacia
@ 2014-08-11 6:30 ` Chris Pacia
2014-08-11 11:38 ` Tim Ruffing
0 siblings, 1 reply; 10+ messages in thread
From: Chris Pacia @ 2014-08-11 6:30 UTC (permalink / raw)
To: Tim Ruffing; +Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 9058 bytes --]
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" <ctpacia@gmail•com> 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" <tim.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
>> 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
>>
>>
[-- Attachment #2: Type: text/html, Size: 10568 bytes --]
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [Bitcoin-development] CoinShuffle: decentralized CoinJoin without trusted third parties
2014-08-11 6:30 ` Chris Pacia
@ 2014-08-11 11:38 ` Tim Ruffing
2014-08-11 12:08 ` Mike Hearn
2014-08-11 17:06 ` Mark Friedenbach
0 siblings, 2 replies; 10+ messages in thread
From: Tim Ruffing @ 2014-08-11 11:38 UTC (permalink / raw)
To: Chris Pacia; +Cc: bitcoin-development
[-- Attachment #1: Type: text/plain, Size: 1988 bytes --]
Hmm, you are right. Lightweight clients are an interesting point, we have to
think about a policy for them.
As you said, the worst case is that the tx will not confirm. So the only
possible attack is DoS. For clients that rely on servers it's reasonable to
trust their servers not to perform DoS. (Anyway, the servers could do worse
attacks.)
For SPV-clients (without servers), I'm not sure at the moment. Something like
getUTXO seems to be a possibility. I think even SPV-clients can verify the
validity of the tx that created the input that is designated for mixing. Then
the only remaining reason why it could be invalid is that the input could have
been spent already otherwise. But in this case, only one honest client with
full information would suffice: a signed transaction that spends the money
would convince even SPV-clients that the participant with this inputs tries to
cheat. This transaction could even be provided by lightweight client that got
if from a server; the transaction is signed by the cheating participant
anyway.
Tim
On Monday 11 August 2014 02:30:16 Chris Pacia wrote:
> 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" <ctpacia@gmail•com> 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.
[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 648 bytes --]
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [Bitcoin-development] CoinShuffle: decentralized CoinJoin without trusted third parties
2014-08-11 11:38 ` Tim Ruffing
@ 2014-08-11 12:08 ` Mike Hearn
2014-08-11 17:06 ` Mark Friedenbach
1 sibling, 0 replies; 10+ messages in thread
From: Mike Hearn @ 2014-08-11 12:08 UTC (permalink / raw)
To: Tim Ruffing; +Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 1203 bytes --]
Putting the efficacy of coinjoin to one side:
On Mon, Aug 11, 2014 at 1:38 PM, Tim Ruffing <
tim.ruffing@mmci•uni-saarland.de> wrote:
> Then the only remaining reason why it could be invalid is that the input
> could have
> been spent already otherwise. But in this case, only one honest client with
> full information would suffice: a signed transaction that spends the money
> would convince even SPV-clients that the participant with this inputs
> tries to
> cheat.
Bear in mind that getutxo does not return the spending transaction - it
can't because the UTXO set doesn't record this information (a spent txo is
deleted).
However, if you have sufficient peers and one is honest, the divergence can
be detected and the operation stopped/the user alerted. If all peers are
lying i.e. your internet connection is controlled by an attacker, it
doesn't really make much difference because they could swallow the
transaction you're trying to broadcast anyway. Ultimately if your peers
think a TXO is spent and refuse to relay transactions that spend them, you
can't do much about it even in the non-SPV context: you *must* be able to
reach at least one peer who believes in the same world as you do.
[-- Attachment #2: Type: text/html, Size: 1607 bytes --]
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [Bitcoin-development] CoinShuffle: decentralized CoinJoin without trusted third parties
2014-08-11 11:38 ` Tim Ruffing
2014-08-11 12:08 ` Mike Hearn
@ 2014-08-11 17:06 ` Mark Friedenbach
1 sibling, 0 replies; 10+ messages in thread
From: Mark Friedenbach @ 2014-08-11 17:06 UTC (permalink / raw)
To: Tim Ruffing; +Cc: bitcoin-development
[-- Attachment #1: Type: text/plain, Size: 3193 bytes --]
There should not be a requirement at this level to ensure validity. That
would too constrain use cases of implementations of your protocol. It is
not difficult to imagine use cases where parties generate chained
transactions on top of unconfimed transactions. Although malleability
currently makes this difficult to do safely in general, it is not
inconceivable that there are circumstances where it would nevertheless be
safe or otherwise desireable.
It is a good security recommendation that clients validate the inputs to a
shuffle they are participating in. What this means depends on the client --
checking the UTXO set for a full node, making some getutxos queries for a
SPV client. But this should remain a recommendation, not a requirement.
On Mon, Aug 11, 2014 at 4:38 AM, Tim Ruffing <
tim.ruffing@mmci•uni-saarland.de> wrote:
> Hmm, you are right. Lightweight clients are an interesting point, we have
> to
> think about a policy for them.
>
> As you said, the worst case is that the tx will not confirm. So the only
> possible attack is DoS. For clients that rely on servers it's reasonable to
> trust their servers not to perform DoS. (Anyway, the servers could do worse
> attacks.)
>
> For SPV-clients (without servers), I'm not sure at the moment. Something
> like
> getUTXO seems to be a possibility. I think even SPV-clients can verify the
> validity of the tx that created the input that is designated for mixing.
> Then
> the only remaining reason why it could be invalid is that the input could
> have
> been spent already otherwise. But in this case, only one honest client with
> full information would suffice: a signed transaction that spends the money
> would convince even SPV-clients that the participant with this inputs
> tries to
> cheat. This transaction could even be provided by lightweight client that
> got
> if from a server; the transaction is signed by the cheating participant
> anyway.
>
> Tim
>
> On Monday 11 August 2014 02:30:16 Chris Pacia wrote:
> > 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" <ctpacia@gmail•com> 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.
>
>
> ------------------------------------------------------------------------------
>
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists•sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>
>
[-- Attachment #2: Type: text/html, Size: 4082 bytes --]
^ permalink raw reply [flat|nested] 10+ messages in thread
end of thread, other threads:[~2014-08-11 17:06 UTC | newest]
Thread overview: 10+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2014-08-06 22:22 [Bitcoin-development] CoinShuffle: decentralized CoinJoin without trusted third parties Tim Ruffing
2014-08-07 13:00 ` xor
2014-08-09 10:04 ` Tim Ruffing
2014-08-09 13:10 ` Sergio Lerner
2014-08-09 20:17 ` Mark Friedenbach
2014-08-11 6:25 ` Chris Pacia
2014-08-11 6:30 ` Chris Pacia
2014-08-11 11:38 ` Tim Ruffing
2014-08-11 12:08 ` Mike Hearn
2014-08-11 17:06 ` Mark Friedenbach
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox