Protocol

This chapter provides an overview of the protocol used by the Coin Shuffle with diagrams and explanations about communication algorithms.

Introduction

The Coin Shuffle protocol tries to solve the problem of privacy in the decentralized network by providing a trustless way to shuffle tokens between multiple addresses in a way that the history of the shuffling is untraceable.

Protocol is based on the UTXO (unspent transaction output) model (which is used, for example, in Bitcoin). In this model, each token is represented by a transaction output - proof that a certain amount of tokens was sent to a certain address (usually, a hash of the transaction in which UTXO was created).

The Coin Shuffle protocol enables a group of users to combine their unspent transaction outputs (UTXOs) and shuffle them in a manner that ensures the resulting tokens are sent to different addresses in batch while keeping the association between the original inputs and the new outputs confidential.

Overview

For further explanation, we will use the following terms:

  • Participant - a user that wants to shuffle his UTXOs.
  • Input - a UTXO that the participant wants to shuffle, spent.
  • Output - an address that will receive a UTXO after shuffling.
  • Encrypted Outputs - a list of outputs encrypted by RSA secret key.
  • Service - a service that provides coordination logic for participants without any ability to reveal output addresses or steal UTXOs.
  • Room - a group of participants that are currently shuffling their UTXOs.

The shuffling process is done in the following steps:

  1. Participants Registration. Participants register in the service by providing their ownership proof of UTXOs that they want to spend.
  2. Shuffle start. Service waits for enough participants to register and then starts the shuffling process.
  3. Participants connection. Participants send their RSA public keys to the service to notify service that they are ready for shuffling.
  4. Keys distribution - service defines order of shuffling and sends RSA public keys that are required for participants to decrypt encrypted outputs.
  5. Shuffling.
    1. First participant encrypts his output with the RSA public keys of the next participants, in order, that each next participant will be able to decrypt its upper "layer" of encryption. Then, the participant sends encrypted output to the service.
    2. Next participant decrypts encrypted outputs of the previous participant and encrypts his output with RSA public keys of next participants and sends new encrypted outputs to the service.
    3. This process continues until the last participant will get a list of outputs without any encryption.
  6. Transaction distribution. After the last participant sends a fully decrypted outputs to the service, service forms a transaction, that each the participant should sign.
  7. Transaction signing. Each participant verifies a transaction, sees that has input and output are included, signs it, and sends signature to the service.
  8. Transaction sending. Service gathers all signatures and sends transaction to the network.

Practical Example

Assume we have 5 participants that want to shuffle their UTXOs. Each participant has a UTXO with the same ERC20 tokens and amount, for example 5 USDT tokens, and they want to shuffle them to 5 unknown addresses.

Lets name them Alice, Bob, Charlie, David, and Eve:

flowchart TB
    Alice
    Bob
    Charlie
    David
    Eve

Alice, Bob, Charlie, David, and Eve want to send their UTXOs to some 5 addresses, and they don't want to reveal receivers of that UTXOs to anybody. So, for coordination, they will use a service which implements Coin Shuffle protocol.

flowchart TB
    Alice --- Service
    Bob --- Service
    Charlie --- Service
    David --- Service
    Eve --- Service

Alice, Bob, Charlie, David, and Eve will register in the service by providing their UTXOs with proof of ownership.

Service will organize them into queue until enough participants will be registered.

In this example, we will assume that 5 participants are enough to shuffle.

flowchart TB
    Alice --> alice_utxo(5$A + Alice's signature)
    Bob --> bob_utxo(5$B + Bob's signature)
    Charlie --> charlie_utxo(5$C + Charlie's signature)
    David --> david_utxo(5$D + David's signature)
    Eve --> eve_utxo(5$E + Eve's signature)
    alice_utxo --> Service
    bob_utxo --> Service
    charlie_utxo --> Service
    david_utxo --> Service
    eve_utxo --> Service
    
    Service --> queue[[Queue: E, A, D, B, C]]

Then, when enough participants will be registered, service will form a room, and notify the participants, so they can send their RSA public keys.

flowchart TB
    Service --> room[[Room: A, B, C, D, E]]

As a response, participants will send their RSA public keys to the service:

flowchart TB
    Alice --> alice_pk(Alice's RSA public key)
    Bob --> bob_pk(Bob's RSA public key)
    Charlie --> charlie_pk(Charlie's RSA public key)
    David --> david_pk(David's RSA public key)
    Eve --> eve_pk(Eve's RSA public key)
    alice_pk --> Service
    bob_pk --> Service
    charlie_pk --> Service
    david_pk --> Service
    eve_pk --> Service

Service will define the order of shuffling and send RSA public keys that are required for outputs encoding and decoding to each participant:

flowchart TB
    Service --> alice_keys[[Alice's keys: B, C, D, E]]
    Service --> bob_keys[[Bob's keys: C, D, E]]
    Service --> charlie_keys[[Charlie's keys: D, E]]
    Service --> david_keys[[David's keys: E]]
    Service --> eve_keys[[Eve's keys:]]
    alice_keys --> Alice
    bob_keys --> Bob
    charlie_keys --> Charlie
    david_keys --> David
    eve_keys --> Eve

Note, that each participant already knows his public key.

Table of keys that each participant has:

Key / ParticipantAliceBobCharlieDavidEve
Alice✅✅✅✅✅
Bob❌✅✅✅✅
Charlie❌❌✅✅✅
David❌❌❌✅✅
Eve❌❌❌❌✅

Then service will send encrypted outputs to each participant, starting with Alice:

Alice is the first participant in the room, so she will receive list of empty encrypted inputs, and encrypt her output.

Firstly, Alice will encrypt her output with her public keys:

flowchart LR
    alice_output["@A"]-- Eve's key -->alice_output1["E[ @A ]"]
    alice_output1-- David's key -->alice_output2["D[ E[ @A ] ]"]
    alice_output2-- Charlie's key -->alice_output3["C[ D[ E[ @A ] ] ]"]
    alice_output3-- Bob's key -->alice_output4["B[ C[ D[ E[ @A ] ] ] ]"]

Then, Alice will send encrypted output to Bob through service. Bob knows, that received encrypted output is encrypted with his RSA the public key, so he will decrypt it using his secret key:

flowchart LR
    alice_output3["B[ C[ D[ E[ @A ] ] ] ]"]-- Bob's secret key -->bob_output1["C[ D[ E[ @A ] ] ]"]

Then Bob will encrypt his output with his public keys:

flowchart LR
    bob_output["@B"] -- Eve's key -->bob_output1["E[ @B ]"]
    bob_output1 -- David's key -->bob_output2["D[ E[ @B ] ]"]
    bob_output2 -- Charlie's key -->bob_output3["C[ D[ E[ @B ] ] ]"]

Then, Bob will shuffle them, and send encrypted outputs to Charlie through service.

flowchart LR
    Bob --- bobs_outputs[["C[ D[ E[ @B ] ] ] <br> C[ D[ E[ @A ] ] ]"]]
    bobs_outputs --> Service
    Service --> Charlie

Charlie will decrypt its upper layers with her secret key:

flowchart LR
    bobs_outputs["C[ D[ E[ @A ] ] ]<br> C[ D[ E[ @B ] ] ]"]-- Charlie's secret key -->charlie_output1["D[ E[ @A ] ]<br> D[ E[ @B ] ]"]

Then Charlie will encrypt her output with her public keys:

flowchart LR
    charlie_output["@C"] -- Eve's key -->charlie_output1["E[ @C ]"]
    charlie_output1 -- David's key -->charlie_output2["D[ E[ @C ] ]"]

Shuffle them, and send them to David:

flowchart LR
    Charlie --- charlies_outputs[["D[ E[ @A ] ] <br> D[ E[ @C ] ] <br> D[ E[ @B ] ]"]]
    charlies_outputs --> Service
    Service --> David

The process will continue until Eve will receive encrypted outputs from David. Eve will finally get fully decrypted outputs from all participants:

flowchart LR
    davids_outputs["E[ @C ]<br> E[ @D ]<br> E[ @A ]<br> E[ @B ]"]-- Eve's secret key -->eve_output1["@C<br> @D<br> @A<br> @B"]

Eve will send that outputs to service, service will form transaction with all inputs and outputs, and send it to all participants for signing.

flowchart TB
    Service --> transaction[["Transaction. <br> Inputs: $5D, $5C, $5B, $5A, $5E <br> Outputs: @C, @D, @A, @B, @E"]]
    transaction --> Alice
    transaction --> Bob
    transaction --> Charlie
    transaction --> David
    transaction --> Eve

Each participant will see, that transaction is valid and at least contains their input and output, so they will sign it and send it back to service.

The service will gather all required signatures, and then send them to the network.

Drawbacks

Coordinator

In this implementation, service is a trusted server, that coordinates participants. Although the coordinator is not able to reveal the private information of the participants, it can still prevent the protocol from starting or completing.

A possible solution is to make an open, decentralized implementation of service, that can be run and trusted by anyone.

Sybil attack

Participants can collaborate in the room, to reveal the identities of other participants.

For example, if 4 of 5 participants are malicious, they can reveal the identity of the last participant, by revealing their outputs to each other.

A possible solution is to make a much larger number of participants in shuffling process, so that the probability of a such attack is very low.

The other solution is to make an unpredictable, random algorithm that will distribute participants into smaller "rooms" which will shuffle separately.

Timing attacks

The protocol implementation relies on network communication with its latencies and possible disconnections during the protocol execution. That's why one of the participants can repeatably disrupt the protocol execution, by disconnecting.

Sudoku analysis

While Coin Shuffle provides a reasonable level of privacy, users still need to be careful about not revealing their identity through their actions. For example, if the user will send his tokens to the same address from different shuffling processes, some external viewers can easily analyze the history of the transactions and participants of the recent shuffling, and reveal the identity of the user by Sudoku analysis or even just intercept inputs' and outputs' addresses of the transactions.

The only solution is to use new separate output addresses for each shuffling process.