CoinShuffle is an extension to the CoinJoin protocol.

Summary

CoinShuffle is a decentralized Bitcoin mixing protocol, inspired by the accountable anonymous group communication protocol Dissent, that extends the CoinJoin protocol. Whereas the original CoinJoin proposal required peers to connect to a third party who would orchestrate the protocol, CoinShuffle peers connect directly with one another, eliminating that third party. By use of ephemeral public key encryption and random shuffling, peers are blinded from knowing the mapping between one another's input and output addresses. In the case of a Denial of Service attack by one or more participants, the protocol includes a blame phase that can identify attackers and remove them for subsequent re-tries of the protocol.

Origin

CoinShuffle was proposed in an academic paper by a team from the Cluster of Excellence Multimodal Computing and Interaction (MMCI) at Saarland University. The authors of the paper included Tim Ruffing, Pedro Moreno-Sanchez, and Aniket Kate. The paper was entitled: "CoinShuffle: Practical Decentralized Coin Mixing for Bitcoin." An initial version of the paper was published in the 19th European Symposium on Research in Computer Security (ESORICS’14), and a second version (revision 2014-08-14) was published on the MMCI website.

Goals

From the paper:

1. No Third Party: CoinShuffle preserves Bitcoin’s decentralized trust ideology: it is executed exclusively by the Bitcoin users interested in unlinkability for their Bitcoin transactions, and it does not require any trusted, accountable, or untrusted third party. The unlinkability of transactions is protected as long as at least any two participants in a run of the protocol are honest.
2. Compatibility: CoinShuffle is fully compatible with the existing Bitcoin network. Unlike other decentralized solutions, it works immediately on top of the Bitcoin network without requiring any change to the Bitcoin rules or scripts.
3. No Mixing Fee: In absence of a third party that acts as a service provider, CoinShuffle does not charge its users any additional mixing fees. It also performs well in terms of Bitcoin transaction fees, because the participants are only charged the fee for a single mixing transaction.
4. Small Overhead: Our performance analysis demonstrates that CoinShuffle introduces only a small communication overhead for a participant (less than a minute for an execution with 20 participants), while the computation overhead remains close to negligible. Finally, CoinShuffle introduces only minimal additional overhead for the rest of the Bitcoin network.

Contributions to CoinJoin

CoinShuffle offers two primary contributions to the CoinJoin protocol specification:

1. Cryptographic Blinding and Peer-to-Peer: CoinShuffle removes the need for a facilitator to orchestrate the CoinJoin, meaning that there is one less party to the protocol to potentially spy on the interaction, and removing a point of failure. Additionally, the parties mixing coins are cryptographically blinded, making them unable to trace the input and output of coins without launching a successful Sybil attack to identify ownership by virtue of the process of elimination.
2. Denial of Service Resistance: CoinShuffle features a "blame phase" that parties enter into as soon as they identify that one parties attempting to game the interaction or break the process through non-cooperation. Once a malicious party is identified during the blame phase, the parties can then ostracize the malicious party and re-try the protocol without him.

Weaknesses

Because the designers of the protocol developed it with a lack of fees in mind, it is not possible for CoinShuffle participants to charge fees for their participation. As a result, this eliminates economic incentives for participation, compared to other CoinJoin variants such as JoinMarket.

^ TODO: This should be verified through additional analysis.

Example

The following example demonstrates the CoinShuffle protocol using concrete numbers. Some of the variables have been changed from the original paper in order to simplify the explanation.

Scenario

Alice, Bob, and Charlie want to use the CoinShuffle protocol to mix their coins.

Phase 0: Bootstrapping

Alice has 1 bitcoin (Ƀ1) in an address we'll abbreviate as "1AliceIn…". The Bitcoin private key she uses to sign transactions in order to spend from that address is signing key (a.k.a. private key) sk^IN_Alice. The corresponding Bitcoin verification key (a.k.a. public key) for this address is vk^IN_Alice. (Note: The superscript "IN" indicates this is an input address to the transaction; later we'll also have output addresses denoted by superscript "OUT".)

Bob also has Ƀ1 in address "1BobIn…" with corresponding keys sk^IN_Bob and vk^IN_Bob.

Charlie also has Ƀ1 in address "1CharlieIn…" with corresponding keys sk^IN_Charlie and vk^IN_Charlie.

Through some "bootstrapping" method not specified in the CoinShuffle paper, Alice, Bob, and Charlie have matched up with each other, they have agreed on a unique session identifier τ (let's say τ=42), and they have exchanged Bitcoin verification keys with each other: vk^IN_Alice, vk^IN_Bob, and vk^IN_Charlie.

Alice, Bob, and Charlie by virtue of the protocol implicitly agree on an ordering between them for the entire protocol: Their input Bitcoin addresses are lexicographically (alphabetically) sorted, so Alice comes first, Bob second, and Charlie last. The first and last parties in a CoinShuffle are treated specially, as will become evident as we go through the protocol.

Phase 1: Announcement

The primary purpose of Phase 1 is to set up and communicate cryptographic keys that will be used for shuffling.

Phase 1A: Generation of ephemeral keys

All parties except for the first party, Alice, will generate fresh ephemeral keys for the purpose of this CoinShuffle. They are a public/private keypair which we will call their encryption key (ek) and decryption key (dk). They are never to be used again in future iterations of the protocol. The decryption key (dk) should be kept secret (TODO: Or else what?).

Bob generates keypair: (ek_Bob, dk_Bob)
Charlie generates keypair: (ek_Charlie, dk_Charlie)

Phase 1B: Signing of Ephemeral Keys

All parties that created an ephemeral key (everyone except Alice) need to communicate those keys to the other parties. They need to sign that value cryptographically in order to ensure the integrity of the data. First: Bob. Bob will sign that key, along with a clear indication of what phase he is in (phase 1) and the session identifier. He will then send this information along with the cryptographic signature to the other two parties. The signature is computed as follows.

Notation: σ_Bob,1 is a computation of a cryptographic signature done by Bob during Phase 1.

Note: A message is signed using a secret signing key "sk" and a function Sign(sk, message). The signature can be verified using a verification key "vk" and a function Verify(vk, signature).

σ_Bob,1 = Sign( sk^IN_Bob, (ek_Bob, Phase=1, τ=42))

During sub-phase 1C Bob sends the message containing (ek_Bob, Phase=1, τ=42) and the cryptographic signature σ,,Bob,1 to Alice and Bob.

Charlie computes his own signature:

σ_Charlie,1 = Sign( sk^IN_Charlie, (ek_Charlie, Phase=1, τ=42))

Phase 1C: Broadcasting of Ephemeral Keys

Bob and Charlie will broadcast their keys and the computed signatures to each other, and to Alice.

Phase 1D: Balance Confirmation

When Alice receives σ_Bob,1, she will verify that the Bitcoin verification key she received from Bob earlier, vk^IN_Bob corresponds to a Bitcoin address with at least Ƀ1 funds. If it doesn't, Alice will enter the blame phase. When Alice receives σ_Charlie,1, she will do the same kind of check on Charlie's address.

Charlie will do the same check on Bob's address when he receives σ_Bob,1. Lastly, (TODO: this is not mentioned in the paper, verify?) when Bob and Charlie send their signatures to Alice, they will also perform the check on Alice's address corresponding to vk^IN_Alice that they received during bootstrapping.

These lookups can either be performed based on a local copy of the blockchain if the party doing the lookup is running a full node, or by querying some third party. Note: There are some privacy challenges related to balance lookups for light clients. It is also worth noting that light clients may also wish to do a balance lookup on their own address as not to tip off to a network observer which address belongs to them by process of elimination.

Phase 2: Shuffling

Phase 2 puts the "shuffle" in "CoinShuffle."

Phase 2A: Output Generation

Alice chooses a new output address. We'll write that as "1AliceOut…". The corresponding Bitcoin verification (public) key is vk^OUT_Alice and the corresponding Bitcoin signing (private) key is sk^OUT_Alice. Likewise, Bob will choose an output address we'll write as "1BobOut…" corresponding to (vk^OUT_Bob, sk^OUT_Bob), and Charlie chooses "1CharlieOut…" corresponding to (vk^OUT_Charlie, sk^OUT_Charlie).

Phase 2B: Encrypted List Initialization