soon as M provides a solution to the
puzzle, he receives the information he
needs to claim A’s escrow. Finally, the
properties of the fair exchange protocol also guarantee that this will only
happen if M provides the correct solution which implies B is able to claim
the escrow set up by M (note that A is
always motivated to send the solution
to B as the bitcoins she escrowed will
be claimed by M even if she does not).
Peer-to-peer mixing solutions. Next
we turn our attention to alternative approaches that obviate the need for an
intermediate party. One obvious benefit of this approach is that it eliminates
the need for mixing fees. Moreover, it
is closer in spirit to the decentralized
principle behind Bitcoin; if the participants can themselves perform this
service, why rely on a central provider?
Mixing with a single transaction. Each
Bitcoin transaction can contain multiple input and output addresses. This
allows a user to join inputs from multiple addresses she owns in order to
match the cost of a particular goal. For
example, if Alice is required to transfer
5BTC to Bob as part of a purchase, Alice
can combine 2BTC from one address
she owns and 3BTC from another, as
inputs to a transaction that transfers
5BTC to an address owned by Bob.
However, the Bitcoin protocol does not
explicitly require that all input addresses belong to the same party. Multiple
parties can, in principle, contribute input addresses to the same transaction
(as shown in Figure 2). CoinJoin20 is a
mixing approach proposed by Maxwell
that takes advantage of this liberty that
Bitcoin offers. A set of k users can agree
to jointly create a transaction with k input addresses that transfers its inputs
to k output addresses. Each party individually observes the transaction; if her
own output address appears in the list
of recipients, she signs the transaction
as a payer with her private key. Eventually, the transaction carries k different
signatures. This simple idea has served
as the core of multiple subsequent implementations and optimizations.
Internal Unlinkability. While CoinJoin hides the shuffling of the coins
from an outsider (thus providing
external unlikability), participants trivially learn the mapping from input
to output addresses (that is, it lacks
internal unlikability). CoinShuffle33
avoids this by utilizing an anonymous
group communication protocol that
can hide the participants’ identities
from each other. This is achieved with
the simple trick of layered encryption,
as shown in Figure 3 (for four parties).
Assume three parties A, B, and C,
with corresponding public keys pkA,
pkB, pkC, that want to mix the same
amount of bitcoins each by transferring them to addresses A′, B′, and C′,
respectively. A then encrypts A′, in a
layered manner, first under pkC and
then under pkB, that is, computes
EncpkB (EncpkC(A′)). Likewise, B encrypts
B′ under pkC to get EncpkC (B′). Then, A
sends the encryption of A′ to B who
proceeds to remove the outer encryption layer (using her own decryption
key), randomly shuffles the resulting
encryption with her own encryption
of B’, and forwards both to C. At this
point C receives A′, B′ encrypted under
pkC and has no way of guessing which
belongs to whom. She simply decrypts
these values, appends C′, shuffles all of
them and writes the transaction which
is broadcast to all participants. Each
one checks that her recipient address
is in the receivers list and, if so, signs
the transaction. Once all signatures are
gathered, the transaction is published
Figure 2. Example of decentralized mixing with four participants. Only the parties learn the
mapping from input to output addresses.
Mixing
Protocol
A
B
C
D
B′
D′
A′
C′
Sign: A
Sign: B
Sign: C
Sign: D
IN: A 1
B 1
C 1
D 1
OU T: B′ 1
D′ 1
A′ 1
C′ 1
Figure 3. Decentralized mixing with CoinShuffle.
Each party encrypts her recipient address, in a layered manner, under the keys of all
parties to her right and sends the shuffled vector of all addresses she sees to the next
party who then removes the outermost layer (a colored rectangle denotes encryption
with the key of the party with the corresponding color). The final party compiles the Bitcoin transaction and posts it on the blockchain. Everyone checks their recipient address
is included and signs the transaction.
ABCD
B′
D′
A′
C′
Sign: D
Sign: C
Sign: B
Sign: A
IN: A 1
B 1
C 1
D 1
OUT: B′ 1
D′ 1
A′ 1
C′ 1
A′ B′
A′
A′ B′
D′
A′
C′
B′
C′