Bitcoin Forum
September 26, 2017, 07:37:20 AM *
News: Latest stable version of Bitcoin Core: 0.15.0.1  [Torrent]. (New!)
 
   Home   Help Search Donate Login Register  
Pages: « 1 [2] 3 4 »  All
  Print  
Author Topic: CoinShuffle: Practical Decentralized Coin Mixing for Bitcoin  (Read 21951 times)
saamxx
Hero Member
*****
Offline Offline

Activity: 532


View Profile
July 05, 2014, 05:23:11 PM
 #21

Funny that a "non-bitcoin"-coin will be the first(probably) to implement this: https://twitter.com/comefrombeyond/status/485429369268350977

#NXT!
.... if NXT doesn't have inputs and outputs?

#Vaporware!

-bm

Give me back my stolen NXT which i payed for works,you were not going to do at all, first.
Fucking theoretician Cheesy
1506411440
Hero Member
*
Offline Offline

Posts: 1506411440

View Profile Personal Message (Offline)

Ignore
1506411440
Reply with quote  #2

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

Posts: 1506411440

View Profile Personal Message (Offline)

Ignore
1506411440
Reply with quote  #2

1506411440
Report to moderator
TwinWinNerD
Legendary
*
Offline Offline

Activity: 1456


CEO BitPanda.com


View Profile WWW
July 05, 2014, 06:08:48 PM
 #22

Funny that a "non-bitcoin"-coin will be the first(probably) to implement this: https://twitter.com/comefrombeyond/status/485429369268350977

#NXT!

How is Come From Beyond going to implement Coinshuffle if NXT doesn't have inputs and outputs?

#Vaporware!

-bm


Unlike you, he can program and is a creative person. He will deliver, unlike other persons we know, that rather take the easy road and just steal 1,000,000 NXT.


bluemeanie1
Sr. Member
****
Offline Offline

Activity: 280


bluemeanie


View Profile WWW
July 05, 2014, 06:37:39 PM
 #23


The participants create fresh addresses A', B', C', D' but do not show them to each other. The goal of CoinJoin-based mixing is to create a mixing transaction with input addresses A, B, C, D and output addresses A', B', C', D' to hide the relation between the coins and their owners. (If it is not clear to you why such transactions are possible, I recommend reading the thread about CoinJoin). However, if we would stick to that particular order A', B', C', D' of output addresses, everybody would learn that A belongs to A', B belongs to B', and so on. So we need to shuffle the list of output addresses to make sure that the linkage of input and output addresses remains hidden. But just shuffling the output addresses in the created transaction does not suffice: For example, if everybody just announced his output addresses during the protocol in plain, i.e., Alice announces A', everybody would learn that A' belongs to Alice. So we have to make sure that the messages that are sent during the protocol do not break the anonymity. CoinShuffle solves exactly this problem.



a shortcoming of Dissent is that anonymity can be compromised if all the protocol round participants collude.  Does Coinshuffle have this same drawback?

-bm

Just who IS bluemeanie?    On NXTautoDAC and a Million Stolen NXT

feel like your voice isn't being heard? PM me.   |   stole 1M NXT?
wladston
Full Member
***
Offline Offline

Activity: 150


Always remember to be awesome.


View Profile WWW
July 05, 2014, 06:42:32 PM
 #24

@bluemeanie1, yes, every kind of mixing anonymization strategy will inevitably have this drawback.

Love programming? Checkout my book at http://code.energy/book
bluemeanie1
Sr. Member
****
Offline Offline

Activity: 280


bluemeanie


View Profile WWW
July 05, 2014, 06:48:26 PM
 #25

@bluemeanie1, yes, every kind of mixing anonymization strategy will inevitably have this drawback.

@wladston: thanks.

The obvious attack vector here is I operate many anonymity nodes, do all the mixing pretending as though I were many people(sybil attack).  Then I possess all the identity credentials and can de-anonymize the transactions.  One way to prevent this occurrence is some kind of rating system for the nodes, but this would be difficult to impose.  It seems this system is a step up from CoinJoin though.

-bm

Just who IS bluemeanie?    On NXTautoDAC and a Million Stolen NXT

feel like your voice isn't being heard? PM me.   |   stole 1M NXT?
piotr_n
Legendary
*
Offline Offline

Activity: 1736


aka tonikt


View Profile WWW
July 06, 2014, 01:08:15 PM
 #26

As suggested by some readers, to illustrate our idea better, let me give a small example with (say) four participants Alice, Bob, Charlie, Dave. The participants have exactly 1 BTC at each of their respective addresses A, B, C, D. Assume the participants already know that they would like to run the protocol with each other and they know the addresses of each other. (Finding other participants can be done via a P2P protocol, for example.)

The participants create fresh addresses A', B', C', D' but do not show them to each other. The goal of CoinJoin-based mixing is to create a mixing transaction with input addresses A, B, C, D and output addresses A', B', C', D' to hide the relation between the coins and their owners. (If it is not clear to you why such transactions are possible, I recommend reading the thread about CoinJoin). However, if we would stick to that particular order A', B', C', D' of output addresses, everybody would learn that A belongs to A', B belongs to B', and so on. So we need to shuffle the list of output addresses to make sure that the linkage of input and output addresses remains hidden. But just shuffling the output addresses in the created transaction does not suffice: For example, if everybody just announced his output addresses during the protocol in plain, i.e., Alice announces A', everybody would learn that A' belongs to Alice. So we have to make sure that the messages that are sent during the protocol do not break the anonymity. CoinShuffle solves exactly this problem.

A successful run of the protocol looks as follows: (Note that the description is simplified; the full details are in the paper.)

All messages are signed using the private signing key belonging to the input address of the sender of the message. I'm omitting the signatures in the following description to simplify the presentation.

Phase 1: Key exchange
Each participant (except for Alice) creates an key pair of a public key encryption scheme, consisting of a public encryption key and a private decryption key. We call the public encryption keys ekB, ekC, and ekD. Each participant announces his public encryption key, signed with the signature key corresponding to his/her input address.

Phase 2: Shuffling
Once everybody knows the public encryption key each other, the shuffling can start:

Alice encrypts her output address A' with all the encryption keys, in a layered manner. That is, Alice encrypts A' first for Dave, obtaining enc(ekD, A'). Then this ciphertext is encrypted for Charlie, obtaining enc(ekC, enc(ekD, A')) and so on for Dave. This resulting message is sent to Bob:
Alice -> Bob: enc(ekB, enc(ekC, enc(ekD, A')))

Bob gets the message, decrypts it, obtaining enc(ekC, enc(ekD, A')).
He also creates a nested encryption of his address, obtaining enc(ekC, enc(ekD, B')).
Now Bob has a list two ciphertexts, containing A' and B'. Bob shuffles this list randomly, i.e., either exchanges the two entries or leave them. Say we are in the case that they are exchanged. Bob sends the shuffled list to Charlie:
Bob -> Charlie: enc(ekC, enc(ekD, B')) ; enc(ekC, enc(ekD, A'))

Participant C does the same: He decrypts the two entries in the list, adds his own entry and shuffles the list:
Charlie -> Dave: enc(ekD, B') ; enc(ekD, C') ; enc(ekD, A')

Dave does the same again: He decrypts all entries, obtaining B', C', A'. He adds his own address D' and
shuffles the list. The resulting shuffled list is sent to everybody:
Dave -> everybody: D', B', C', A'

Phase 3: Creating the transaction
Every participant receives the list of output addresses and can verify that his output address is indeed there. If yes, he signs the transaction. If, e.g., Bob sees that his address is not there, he would lose his coin by performing the transaction, so he obviously does not want to sign. (This is the main idea of CoinJoin.)
In the case that Bob's address is not there, somebody must have cheated during the run of the protocol. Bob complains and the participants enter an additional phase to find out who cheated. CoinShuffle makes sure that this "blame phase" always exposes at least one cheating participant (and none can be accused falsely). This cheating participant can then be excluded from a subsequent run of the protocol: Say Alice cheated. Then Bob, Charlie and Dave can run the protocol again without Alice.

The key point is that in phase 2, only the participant that performed the shuffling knows the relation between the messages in the list that he received and the messages in the list that he sent.
For example, only Charlie knows that he left the message containing B' in the first position, because the encryption ensures that nobody can relate enc(ekC, enc(ekD, B')) and enc(ekD, B'). But even Charlie does not know that this was the message with Bob's address.
In the end, all addresses of honest participants are shuffled as explained in my previous posting. Nobody knows the permutation. (A detailed argument can be found in the paper.)


An overview over a successful run of CoinShuffle. [svg] [png]

Note: The protocol works even if participants do not have exactly 1 BTC at their input addresses. It suffices that they have at least 1 BTC. In that case, they create a transaction that sends 1 BTC to each of the shuffled output addresses and the remaining coins to a change addresses that the users announce in the beginning. This can be done as for normal Bitcoin transactions. (This idea is also described in CoinJoin already.)

By the way, we managed to improve the execution time. Using our prototype implementation, a protocol run with 50 participants takes roughly 3 minutes now in the setting that we consider in the paper.

A comparison with other approaches
Mixcoin
The main innovation of Mixcoin is accountability for mixing servers (mixes): If the mix server steals coins, the user obtains a cryptographic proof of this theft and can hold the mix accountable. This is done in public: Everybody can verify this proof and the mix will hopefully lose its reputation, and nobody will use the mix in the future. The mix can still steal money but it will be caught and probably has to go out of business.
In contrast, the advantage of CoinShuffle is that it prevents stealing of coins in the first place instead of providing accountability only after the theft. Additionally, a centralized mixing server is not at all necessary in CoinShuffle.

Zerocoin / Zerocash / Anoncoin
Zerocoin (and the upcoming optimized Zerocash) are great because they provide "built-in anonymity" by using quite novel cryptography, e.g. ZK-SNAKRS. However, are their own currencies. Zerocoin and Zerocash are not compatible with Bitcoin, they need their own protocol extensions and chain. For instance, Zerocoin is being implemented in Anoncoin, an altcoin. CoinShuffle works directly on top of Bitcoin, without changing the Bitcoin protocol or forking the chain.

CoinSwap
Most important, the participants know which coins belong to which user in CoinSwap, so the anonymity is limited. Furthermore, CoinSwap needs at least 4 transactions and the corresponding fees. CoinShuffle needs only one transaction. However, CoinSwap is essentially a two party protocol, so it requires less interaction and coordination. The original CoinSwap thread provides a detailed comparison to CoinJoin, which provides the basis for CoinShuffle.


This is a very well thought and nicely described design - real pro!

If anyone would be interested in developing (and testing) a working prototype for it, I would be happy to contribute with some of my code.

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
bluemeanie1
Sr. Member
****
Offline Offline

Activity: 280


bluemeanie


View Profile WWW
July 08, 2014, 01:40:51 AM
 #27

Has anyone explored other anonymity strategies aside from input/output mixing?

-bm

Just who IS bluemeanie?    On NXTautoDAC and a Million Stolen NXT

feel like your voice isn't being heard? PM me.   |   stole 1M NXT?
bluemeanie1
Sr. Member
****
Offline Offline

Activity: 280


bluemeanie


View Profile WWW
July 08, 2014, 04:36:21 PM
 #28

the fact is, that even if you were to have 100% reliable and untraceable mixing of inputs/outputs the transactions are still temporally correlated.  As in: the transfers occur at the same time and thus are statistically related.

-bm

Just who IS bluemeanie?    On NXTautoDAC and a Million Stolen NXT

feel like your voice isn't being heard? PM me.   |   stole 1M NXT?
msin
Legendary
*
Offline Offline

Activity: 1134


View Profile
July 08, 2014, 04:46:35 PM
 #29

Has anyone explored other anonymity strategies aside from input/output mixing?

-bm


I think that's the most popular as no one is about to change BTC core to include anonymity at a protocol level.  Do you have any other projects to review?  Input/Output can always be correlated but it would take QC power to do so.
bluemeanie1
Sr. Member
****
Offline Offline

Activity: 280


bluemeanie


View Profile WWW
July 08, 2014, 04:52:17 PM
 #30

Has anyone explored other anonymity strategies aside from input/output mixing?

-bm


I think that's the most popular as no one is about to change BTC core to include anonymity at a protocol level.  Do you have any other projects to review?  Input/Output can always be correlated but it would take QC power to do so.

The fact is you can get fairly good anonymity simply by putting your coins on an exchange that doesn't require ID, and then transferring it out to an address that you have never used.  If you use Tor for all your interactions with the exchange website, then the coins are mostly untraceable.  Any exchange in the US, Singapore, most of Western Europe does not offer you anonymity.  If you issue the outgoing payment TX using Tor as well, the payment is mostly untraceable.  It's possible to automate all this in the wallet.

I don't know of any ideas that are not in this class of input/ouput mixing although it may be possible to implement something using cryptographic blinding.

-bm

Just who IS bluemeanie?    On NXTautoDAC and a Million Stolen NXT

feel like your voice isn't being heard? PM me.   |   stole 1M NXT?
dserrano5
Legendary
*
Offline Offline

Activity: 1848



View Profile
July 08, 2014, 05:03:15 PM
 #31

The fact is you can get fairly good anonymity simply by putting your coins on an exchange that doesn't require ID, and then transferring it out to an address that you have never used.

But then you're trusting the exchange not to keep logs that link your incoming tx to the outgoing one.

bluemeanie1
Sr. Member
****
Offline Offline

Activity: 280


bluemeanie


View Profile WWW
July 08, 2014, 05:06:09 PM
 #32

The fact is you can get fairly good anonymity simply by putting your coins on an exchange that doesn't require ID, and then transferring it out to an address that you have never used.

But then you're trusting the exchange not to keep logs that link your incoming tx to the outgoing one.

right, this is why if you use an exchange that lies outside of eg. US jurisdiction, they are unlikely to comply with any requests to produce such logs.

This is likely the reason why the American/European currency authorities in particular are always vilifying the Chinese exchanges.  The Chinese exchanges are a doorway in and out of Bitcoin that they don't have any control over.

-bm

Just who IS bluemeanie?    On NXTautoDAC and a Million Stolen NXT

feel like your voice isn't being heard? PM me.   |   stole 1M NXT?
msin
Legendary
*
Offline Offline

Activity: 1134


View Profile
July 08, 2014, 05:18:37 PM
 #33

The fact is you can get fairly good anonymity simply by putting your coins on an exchange that doesn't require ID, and then transferring it out to an address that you have never used.

But then you're trusting the exchange not to keep logs that link your incoming tx to the outgoing one.

right, this is why if you use an exchange that lies outside of eg. US jurisdiction, they are unlikely to comply with any requests to produce such logs.

This is likely the reason why the American/European currency authorities in particular are always vilifying the Chinese exchanges.  The Chinese exchanges are a doorway in and out of Bitcoin that they don't have any control over.

-bm


But accomplishing this within a client would be a trustless solution and a time saver, so using a 3rd party exchange wouldn't make sense when you could use an internal exchange/shuffle such as the case with Coinshuffle/Nxt.
sundance
Newbie
*
Offline Offline

Activity: 22


View Profile
August 08, 2014, 02:42:21 AM
 #34

Has anyone explored other anonymity strategies aside from input/output mixing?

-bm


BM, I have been exploring a strategy using N-way mixing, where by 'mixing' I mean the proper sense of creating separate transactions to exchange the coins. Whitepaper/ppt/git forthcoming.

The gist of the idea is:

(1) N players use a randomized Byzantine process to agree on a mixing specification, and then
(2) Execute multiple pairwise transactions atomically on the Bitcoin blockchain, ala TierNolan's atomic cross-chain transfer solution. This is an N-way, same-chain atomic transfer within Bitcoin (ie not cross chain).

Atomic Cross Chain Transfer discussion
https://bitcointalk.org/index.php?topic=193281.0
https://github.com/TierNolan/bips/blob/bip4x/bip-atom.mediawiki

Example:
Alice wants to mix 1 BTC
Bob wants to mix 2 BTC
Charlie wants to mix 3 BTC

In step 1, they decide on the following mix:
Alice --> Charlie 1BTC
Bob --> Charlie 2 BTC
Charlie --> Alice 1 BTC
Charlie --> Bob 2 BTC

In step 2, Alice executes her transfer to Charlie, Bob does his to Charlie, and Charlie does his to Alice and Bob. This is done in a way such that either all transfers succeed or they all fail.

I'm currently working on final steps of extending TierNolan's solution and a prototype.

Yes, this means the players pay for more transactions. One of the advantages is that the temporal locality of the transactions is loosened.
Sergio_Demian_Lerner
Hero Member
*****
expert
Offline Offline

Activity: 535


View Profile WWW
August 08, 2014, 12:47:39 PM
 #35

Somebody asked for some other ways for anonymization: you can check my old paper on AppeCoin at
https://bitslog.wordpress.com/2014/04/24/appecoin-anonymous-cryptocurrency-draft/

It uses universal encryption, so everyone can mix every other peoples outputs without asking for permission, and it's impossible for dishonest mixers to prevent honest mixers from mixing with high anonymity set (at least of course if 99.9% of the outputs in the blockchain are controlled by the attacker).

dansmith
Full Member
***
Offline Offline

Activity: 202


View Profile
August 09, 2014, 01:30:47 PM
 #36

Please help me better understand exactly how CoinShuffle improves upon what already can be achieved with Coinjoin

The whitepaper mentions a weakness of CoinJoin and fails to point out that a more viable solution was proposed. The whitepaper states speaking of CoinJoin:
Quote
The mixing server still needs to be trusted to ensure anonymity, because it learns which coins belong to which user.  To tackle this problem, Maxwell mentions the possibility to use secure multi-party computation (SMPC) with CoinJoin to perform the mixing in an oblivious manner.
Then you go on to describe how unviable SMPC is.
While I agree that SMPC may be unviable, you seem to fail to mention another solution from the OP in CoinJoin thread:

in FAQ
Quote
Don't the users learn which inputs match up to which outputs?
...
More complicated implementations are possible where even the server doesn't learn the mapping.
E.g. Using chaum blind signatures:


Having established the fact that a centralized CoinJoin server will not learn the input/output mappings, is my assessment correct that the only advantage of CoinShuffle over CoinJoin is that
CoinShuffle can be implemented in a fully DEcentralized manner and still identify the DOSing party,
whereas CoinJoin can identify the DOSing party only when implemented with a CEntralized server?

https://tlsnotary.org
Transferable webpage content notarization.
sundance
Newbie
*
Offline Offline

Activity: 22


View Profile
August 10, 2014, 12:51:01 AM
 #37

Another related question to help me confirm my understanding of the contribution of CoinShuffle:

Is the following algorithm be semantically equivalent to the algorithm presented in your paper?

Communication is done peer-to-peer using public-key, authenticated encryption. 'Broadcast' in this context means a player sends a message to all the players over these links.

Each player i (1 < i < N) does the following:
1 Generate a random permutation P_i of (1, 2, ..., N)
2 Broadcast H(P_i), where H is a collision resistance hash.
3 For all j != i, receive H(P_j) from player j
4 Broadcast P_i
5 For all j != i, receive P_j from player j and confirm the hash value
6 Calculate output list = P_1 (P_2 ( ...P_N (1, 2, ..., N)...)), broadcast, and agree on that value

Player 1 creates the join transaction with the output list, and the transaction is signed by all players. The transaction is broadcasted to the blockchain.
cr1776
Legendary
*
Offline Offline

Activity: 1652


View Profile
August 10, 2014, 02:31:51 PM
 #38

@bluemeanie1, yes, every kind of mixing anonymization strategy will inevitably have this drawback.

If multiple entities - e.g. US NSA, SVR (Russian CBP), Chinese MSS, any private entities etc - are all attempting to de-anonymize mixing they will end up interfering with each other and help anonymity.  So it seems beneficial to encourage more than one group to attempt to de-anonymize mixing and not cooperate with each other.

Private entities/people using large balance addresses to avoid transaction fees could enable multiple groups to take part in each mix at no cost to them while increasing the number of parties in the mix and consequently increasing anonymity for everyone involved.

:-)

TimRuffing
Newbie
*
Offline Offline

Activity: 14


View Profile
August 13, 2014, 01:49:30 PM
 #39

The whitepaper mentions a weakness of CoinJoin and fails to point out that a more viable solution was proposed. [...]
It's actually mentioned it the related work section. But I agree, it would be clearer to mention it already at this point. We will clarify this paragraph.

CoinJoin refers only to the idea to use a joint transaction with several inputs and outputs to do mixing. There are several ways to create such a transaction. CoinShuffle is one way, using a server and blind signatures is another.

The essential difference is the following:
Creating a CoinJoin with a server and blind signatures provides unlinkability (against the server) only if the participants connect to the server already in an anonymous way, e.g., by using Tor. On contrary, CoinShuffle uses more communication between the participants to provide unlikability by itself without any other third (trusted or untrusted) party, so without a central server and without relying on an anonymity network.

Having established the fact that a centralized CoinJoin server will not learn the input/output mappings, is my assessment correct that the only advantage of CoinShuffle over CoinJoin is that
CoinShuffle can be implemented in a fully DEcentralized manner and still identify the DOSing party,
whereas CoinJoin can identify the DOSing party only when implemented with a CEntralized server?
It's not really about DoS actually. A simple decentralized CoinJoin, i.e., without server but also not like CoinShuffle, would be sufficient to identify participants that want to disrupt the protocol. However, in such a approach, all participants can link input and output addresses, see "Don't the users learn which inputs match up to which outputs?" in the mentioned CoinJoin FAQ.


@ Sergio_Demian_Lerner:
I'm not sure if the required zero-knowledge proofs are efficient enough, but it is an interesting idea to allow everybody to mix addresses.

Is the following algorithm be semantically equivalent to the algorithm presented in your paper? [...]
Your algorithm provides a way to agree on a random permutation such that nobody can influence the result. However, the participants learn the the resulting random permutation. In CoinShuffle, they don't learn the permutation.
coins101
Legendary
*
Offline Offline

Activity: 1386



View Profile
September 09, 2014, 04:44:06 PM
 #40

Links to IP addresses would be broken?

Pages: « 1 [2] 3 4 »  All
  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!