Bitcoin Forum
November 22, 2017, 06:23:55 AM *
News: Latest stable version of Bitcoin Core: 0.15.1  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: CoinShuffle++, a fast peer-to-peer coin mixing protocol  (Read 4026 times)
TimRuffing
Newbie
*
Offline Offline

Activity: 14


View Profile
June 03, 2016, 11:41:39 AM
 #1

Hello,

we are Tim Ruffing (Saarland University - Germany), Pedro Moreno-Sanchez and Aniket Kate (both Purdue University - USA). In April 2014, we presented CoinShuffle, a practical peer-to-peer coin mixing protocol to improve users' anonymity in Bitcoin (website, forum thread).
Continuing our research, we now are ready to present CoinShuffle++, a much more efficient protocol for peer-to-peer coin mixing.

CoinShuffle++ basically offers the same security and privacy properties as CoinShuffle but is significantly faster. Even though the protocol does not rely on external anonymity services such as Tor, users are not required to trust a mixing server for privacy or security. (A server is just used to facilitate communication and broadcasts, e.g., a public IRC server.) As we continue to use CoinJoin, theft of coins is excluded and the protocol is fully compatible to the current Bitcoin system; not even a soft-fork is necessary. For privacy, noone (not even a user in the protocol) learns which of the new addresses belongs to which of the users. Additionally, malicious users that just want to disrupt the protocol can be detected and excluded.

The key innovation of CoinShuffle++ is the use of a more efficient mechanism for anonymity: CoinShuffle++ uses Dining Cryptographers Networks (DC-nets) instead of mix-nets. A mix-net requires sequential processing. Thus, the original CoinShuffle needs a number of communication rounds linear in the number of users, even if everybody is honest. CoinShuffle++ instead uses DC-nets and thus allows users to process mixing in parallel. As a result, CoinShuffle++ requires only a constant number of communication rounds independently of the number of users in this case.

We have prototyped CoinShuffle++ in Python and tested it in the same network configuration as we did for CoinShuffle. As a preliminary result, our (very unoptimized and not-ready-to-show) implementation of CoinShuffle++ requires only about 15 seconds for a CoinJoin with 50 users. In comparison, the original CoinShuffle needs about 3 min in a comparable setting. So our protocol provides a huge improvement in terms of running time. And we think CoinShuffle can be made even faster with a nice implementation, which we plan to work on soon.

For all the technical details, see the preprint of our paper, which actually presents a general mixing primitive that can be used not only for crypto-currencies but also for credit networks such as Ripple. We made a lot of effort to make the protocol "ready for implementation" by providing detailed pseudocode including a lot of details that were not made explicit in the CoinShuffle proposal (e.g., exact code for handling offline participants).

We would be glad to hear your feedback and suggestions on our proposal.  Talk to us if you're interested in contributing to the development!
1511331835
Hero Member
*
Offline Offline

Posts: 1511331835

View Profile Personal Message (Offline)

Ignore
1511331835
Reply with quote  #2

1511331835
Report to moderator
1511331835
Hero Member
*
Offline Offline

Posts: 1511331835

View Profile Personal Message (Offline)

Ignore
1511331835
Reply with quote  #2

1511331835
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1511331835
Hero Member
*
Offline Offline

Posts: 1511331835

View Profile Personal Message (Offline)

Ignore
1511331835
Reply with quote  #2

1511331835
Report to moderator
1511331835
Hero Member
*
Offline Offline

Posts: 1511331835

View Profile Personal Message (Offline)

Ignore
1511331835
Reply with quote  #2

1511331835
Report to moderator
btcsql
Sr. Member
****
Offline Offline

Activity: 292


View Profile
June 03, 2016, 04:49:44 PM
 #2

Very nice. PHP / Javascript developer here. How can I help contribute?
waxwing
Sr. Member
****
Offline Offline

Activity: 469


View Profile
June 03, 2016, 04:52:27 PM
 #3

Looks really interesting, thanks.

Re:

"Moreover, although CoinShuffle++ does not prevent malicious peers from disrupting the protocol, it provides a mechanism to identify the misbehaving peer so that it can be excluded and termination is ensured"

(this is the blame part of the protocol, right, iirc) .. my concern with this is that such identification is not helpful if participants coordinate to make join transactions anonymously. Would you agree?

There are some ideas to impose costs in advance (ideally without additional bitcoin transactions) so as to ameliorate this sybil attack vector (in the case where there is no persistent identity), but they seem to be orthogonal to coinshuffle(++).

PGP fingerprint 4668 9728 A9F6 4B39 1FA8 71B7 B3AE 09F1 E9A3 197A (use email to contact)
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2338



View Profile
June 03, 2016, 05:07:44 PM
 #4

(this is the blame part of the protocol, right, iirc) .. my concern with this is that such identification is not helpful if participants coordinate to make join transactions anonymously. Would you agree?
Blacklist the txout, no? That is a basic level of protection.


Bitcoin will not be compromised
waxwing
Sr. Member
****
Offline Offline

Activity: 469


View Profile
June 03, 2016, 05:12:34 PM
 #5

I see now that I hadn't understood the idea; the protocol is going to complete for all the honest participants, right. In a likely scenario of 1 miscreant out of 3<N<10 say, that may be good enough.

gmaxwell: yeah i was vaguely alluding to the various schemes we discussed before. But anyway I had misunderstood what this is achieving, at least somewhat.

PGP fingerprint 4668 9728 A9F6 4B39 1FA8 71B7 B3AE 09F1 E9A3 197A (use email to contact)
iamnotback
Sr. Member
****
Offline Offline

Activity: 336



View Profile
June 03, 2016, 08:03:02 PM
 #6

jl777 was working on something similar many months ago. My critique at that time I think remains. Although I haven't read your paper, I note "and 4 + 2f rounds in the worst case of f malicious peers.".

Afair, my critique of DC-nets for a CoinJoin were:

1. It can be effectively jammed by many malicious Sybil peers.

2. It can't scale, because it has a simultaneity requirement that all the peers to the join successfully communicate in unison.

The only way I have found to resolve this conceptually fundamental weakness of CoinJoin, is to introduce some trusted nodes (a la Dash masternodes which were btw a forum documented result of my input) yet probabilistically remove the reliance on that trust.
somacoin
Sr. Member
****
Offline Offline

Activity: 364



View Profile WWW
June 03, 2016, 08:44:15 PM
 #7

jl777 was working on something similar many months ago. My critique at that time I think remains. Although I haven't read your paper, I note "and 4 + 2f rounds in the worst case of f malicious peers.".

Afair, my critique of DC-nets for a CoinJoin were:

1. It can be effectively jammed by many malicious Sybil peers.

2. It can't scale, because it has a simultaneity requirement that all the peers to the join successfully communicate in unison.

The only way I have found to resolve this conceptually fundamental weakness of CoinJoin, is to introduce some trusted nodes (a la Dash masternodes which were btw a forum documented result of my input) yet probabilistically remove the reliance on that trust.

These are some important points!!
CohibAA
Full Member
***
Offline Offline

Activity: 217



View Profile WWW
June 04, 2016, 06:42:48 AM
 #8

Following.  Thank you for working on this important topic (privacy).

spartacusrex
Hero Member
*****
Offline Offline

Activity: 604



View Profile
June 10, 2016, 11:29:12 AM
 #9

Just thinking out loud here.. but.. can we do this ...

The problem is that a malicious node can hold up the entire procedure.

So if there are 5 of you trying to do a coinjoin/coinshuffle, you set of, and one of you plays 'silly bugger' and boom, you can't complete.

Why not try and complete EVERY combination of the five users, so you would actually be doing more like 20 different coinjoins, say all the combinations of minimum 3 from 5, and then just pick the one with the most valid users at the end ?

You would be sending multiple messages at a time to each other, so I don't think it would require the same amount of steps as just doing 20 coinjoins in a row. But definitely more..

And since you would not sign a txn that didn't have your inputs/outputs, you wouldn't risk losing your coins. Whichever was the eventual successful txn. (In this case the 4 valid minus the malicious node.)

Let's call it - CoinBomb!


 

waxwing
Sr. Member
****
Offline Offline

Activity: 469


View Profile
June 11, 2016, 07:49:22 AM
 #10

Just thinking out loud here.. but.. can we do this ...

The problem is that a malicious node can hold up the entire procedure.

So if there are 5 of you trying to do a coinjoin/coinshuffle, you set of, and one of you plays 'silly bugger' and boom, you can't complete.

That's exactly what the protocol is designed to handle. With 5 total and 1 not acting "honestly" (just means, not following the protocol), the remaining 4 will complete successfully with a few extra rounds of communication.

PGP fingerprint 4668 9728 A9F6 4B39 1FA8 71B7 B3AE 09F1 E9A3 197A (use email to contact)
spartacusrex
Hero Member
*****
Offline Offline

Activity: 604



View Profile
June 11, 2016, 09:53:03 AM
 #11

Just thinking out loud here.. but.. can we do this ...

The problem is that a malicious node can hold up the entire procedure.

So if there are 5 of you trying to do a coinjoin/coinshuffle, you set of, and one of you plays 'silly bugger' and boom, you can't complete.

That's exactly what the protocol is designed to handle. With 5 total and 1 not acting "honestly" (just means, not following the protocol), the remaining 4 will complete successfully with a few extra rounds of communication.

.. excellent.

Decoded
Legendary
*
Offline Offline

Activity: 910


Crypto-News.net: News from Crypto World


View Profile WWW
June 12, 2016, 10:38:42 AM
 #12

Just thinking out loud here.. but.. can we do this ...

The problem is that a malicious node can hold up the entire procedure.

So if there are 5 of you trying to do a coinjoin/coinshuffle, you set of, and one of you plays 'silly bugger' and boom, you can't complete.

That's exactly what the protocol is designed to handle. With 5 total and 1 not acting "honestly" (just means, not following the protocol), the remaining 4 will complete successfully with a few extra rounds of communication.

Really nice. May I ask, I've heard and looked at coinshuffle before, but not in depth. Is it now defunct, or something? Is that why you're making this?



              ▄▄▄██████▄▄▄
          ▄██████████████████▄
       ▄████████████████████████▄
 ▄▄  ▄████████████████████████████▄
███████████████████████████████████▄
 ▀▀█████████████████████████████████▄
   ██████████████████████████████████
   ██████████████████████████████████
   ██████████████████████████████████
   ██████████████████████████████████
   ▀████████████████████████████████▀
    ▀██████████████████████████████▀
     ▀▀██████████████████████████▀
        ▀██████████████████████▀
           ▀▀▀████████████▀▀▀
.
.....
.....
.....
.....
.....
.....





waxwing
Sr. Member
****
Offline Offline

Activity: 469


View Profile
June 12, 2016, 01:03:05 PM
 #13


Really nice. May I ask, I've heard and looked at coinshuffle before, but not in depth. Is it now defunct, or something? Is that why you're making this?

Check the usernames, I'm not the author Smiley Actually I only spent a couple of hours looking at it, want to come back to it later. The author of this thread is (one of the) author(s) of both the original and the ++ The paper discusses the differences a bit.

PGP fingerprint 4668 9728 A9F6 4B39 1FA8 71B7 B3AE 09F1 E9A3 197A (use email to contact)
hhanh00
Sr. Member
****
Offline Offline

Activity: 464


View Profile
June 12, 2016, 07:54:07 PM
 #14

In step KE,
sidH = H((sid, sid, P ∪ {my}, NPK[ ], run))

How is NPK[] determined prior to receiving NPK[p] from p?

Thanks,
--h

TimRuffing
Newbie
*
Offline Offline

Activity: 14


View Profile
June 13, 2016, 09:30:18 PM
 #15

In step KE,
sidH = H((sid, sid, P ∪ {my}, NPK[ ], run))

How is NPK[] determined prior to receiving NPK[p] from p?
Good catch! You're right, this is a small mistake. NPK[] is not determined yet. This should be VK[], not NPK[]...

We try to include the whole view of the peers in the hash to make sure they cannot continue if something is weird. (Even though some inputs of the hash function may not be necessary it cannot be wrong to include them in the hash.)

 
hhanh00
Sr. Member
****
Offline Offline

Activity: 464


View Profile
June 14, 2016, 09:37:10 AM
 #16

1.
sid that gets passed to RUN comes from
Code:
Run(P, my, VK[ ], sk, sid', 0)

where sid' is (sid, P, VK[ ]).

Why do you need to have sid' if you are building a hash H((sid, sid, P ∪ {my}, VK[ ], run)). At this point sid is sid'.

2.
I don't understand the commitment phase.
"it is even for a rushing malicious peer a infeasible to have committed to an ill-formed vector that
leaves mp intact".

The DC-VECTOR exchanged between peers contain a DC-PAD component that cancels out when everything is summed up. Could you explain how would a malicious peer benefit from omitting it?

Thanks,
--h


pedrorechez
Newbie
*
Offline Offline

Activity: 1


View Profile
June 15, 2016, 04:39:23 AM
 #17

1.
sid that gets passed to RUN comes from
Code:
Run(P, my, VK[ ], sk, sid', 0)

where sid' is (sid, P, VK[ ]).

Why do you need to have sid' if you are building a hash H((sid, sid, P ∪ {my}, VK[ ], run)). At this point sid is sid'.


As Tim pointed out in a previous comment, we try to include the complete view of the peers in the hash. In this manner, we ensure that  they do not continue if something is not as expected. (Even though some inputs of the hash function may not be necessary it cannot be wrong to include them in the hash.)

2.
I don't understand the commitment phase.
"it is even for a rushing malicious peer a infeasible to have committed to an ill-formed vector that
leaves mp intact".

The DC-VECTOR exchanged between peers contain a DC-PAD component that cancels out when everything is summed up. Could you explain how would a malicious peer benefit from omitting it?

The general idea of having commitments is to ensure termination. In order to understand what can we wrong if there is no commitment phase, you can imagine the following simple case: the malicious peer could wait for the DC-VECTOR from all other peers before he publishes his own (i.e., rushing malicious peer). At that point, he can locally sum them up and recover the m_p message from every other peer p.  Thus, now the malicious user have enough information to create an ill-formed DC-VECTOR that changes m_p for for a peer p but not for the rest. In this scenario, the tricked honest peer p won't sign the final output because her message m_p is not there (and she might be excluded), however she  correctly followed the protocol.

The use of commitments thus is necessary to ensure termination for the honest peers: Intuitively, since the malicious peer has to commit to his DC-VECTOR before seeing the DC-VECTOR of the other peers, he cannot create a DC-VECTOR that changes m_p for a peer p but not for the rest.
Evil-Knievel
Legendary
*
Offline Offline

Activity: 1050



View Profile
June 15, 2016, 10:05:15 PM
 #18

I have just read this here:
https://crypsys.mmci.uni-saarland.de/projects/FastDC/paper.pdf

Forgive me, if I missed those points. It's too late and I have not spent much time reading.
But I am curious how you would mitigate the two most obvious attacks here.

- Let BTC() be the function returning the sum of BTC in a set of in- or outputs. Then find all subsets A of all inputs, and subsets B of all outputs so that BTC(A) = BTC(B). In most cases there should be a unique solution. This attack could be performed even when mixing occurs via multiple steps. Timing correlations would narrow down a set of transactions to be searched: from what I understood you want to keep that thing fast so the number of possible TXs is expected to be sufficiently small for a feasible brute force attack.

- You are "broadcasting" signed spending outputs. Who prevents an attacker who participates in this system with zero knowledge to correlate which spending outputs are broadcast bundled together (or even from the same IP)? Surely, once the transaction is finally published this attack won't work. But for the inside man ... ? Does than mean you have to trust your anonymity set?
TimRuffing
Newbie
*
Offline Offline

Activity: 14


View Profile
June 29, 2016, 11:48:17 AM
 #19

- Let BTC() be the function returning the sum of BTC in a set of in- or outputs. Then find all subsets A of all inputs, and subsets B of all outputs so that BTC(A) = BTC(B). In most cases there should be a unique solution. This attack could be performed even when mixing occurs via multiple steps. Timing correlations would narrow down a set of transactions to be searched: from what I understood you want to keep that thing fast so the number of possible TXs is expected to be sufficiently small for a feasible brute force attack.
Your observation is valid. We require that each of the users contributes the same amount of money to a particular mixing to avoid this attack.
This is of course not optimal for a number of reason (e.g., if the mixing amount is 0.1 BTC but you have 0.12 BTC, you cannot mix the  remaining 0.02 BTC in this run) but this is required for security. It's a standard problem in all mixing approaches compatible with Bitcoin, no matter whether you use a central party, a CoinJoin tx or similar.

- You are "broadcasting" signed spending outputs. Who prevents an attacker who participates in this system with zero knowledge to correlate which spending outputs are broadcast bundled together (or even from the same IP)? Surely, once the transaction is finally published this attack won't work. But for the inside man ... ? Does than mean you have to trust your anonymity set?
I'm not sure if I understand the proposed attack correctly.  Which step of the protocol do you refer to?

The point is that the protocol guarantees anonymity even on the network level, i.e., against a network attacker. The attacker can observe that a broadcast originates from a certain IP but that information does not help to break anonymity. Actually, ensuring this is the whole point of the CoinShuffle(++).
Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!