Communications of the ACM

actions that “announce” their mutual pairing interest in a way that does not link their identities to outside observers. If that occurs, the two parties proceed to perform a single-transaction mixing, using a fair exchange protocol. If Bob backs down and does not post his transaction, Alice can simply announce she is looking for a new partner (without losing any funds) and if Alice backs down, Bob can post her signed attestation that confirms she changed her mind, “damaging” her reputation. Due to its interaction structure, Xim can achieve large anonymity sets, similar to the ones achieved by centralized mixers, assuming many participants are choosing to use it. The main downside is that it requires a significant blow-up in the end-to-end mixing time. A large portion of the communication happens sequentially over the chain itself therefore the waiting time for transactions to be collected by miners, added to blocks, posted to the chain, and substantially validated (by extending the chain) will typically be in the order of hours.

Alternative Privacy-Preserving
Cryptocurrencies

Here, we review some suggestions for alternative cryptocurrencies designed with the goal of providing stronger privacy guarantees than Bitcoin.

Privacy via ring signatures: CryptoNote. One of the first attempts to make transactions more private without additional interaction from the client (for example, using a mixing service or protocol) is CryptoNote, 38 the core idea of which has subsequently been refined and adopted in other currencies, for example, Bytecoin,f and Monero. 29 Like Bitcoin, every CryptoNote user has a public and a private key. Unlike Bitcoin however, the destination address of a transaction is a one-time public key, which is derived from the recipient’s public key and some randomness chosen by the sender.

In particular, when Alice wants to
send an amount m to Bob, she first
establishes a one-time public key pkB,r
with Bob using fresh randomness
r and Bob’s public key B. Then she
posts a transaction on the blockchain
that contains m, pkB,r and some pub-
f https://bytecoin.org
in the blockchain. CoinShuffle++ 34 is
an extension that uses a P2P network
for traffic mixing while significantly re-
ducing the performance and commu-
nication bandwidth.

Decentralized mixing with large anonymity sets. One issue with the peer-to-peer approaches is that their anonymity set is upper bounded by the number of participants in the mixing protocol, which is likely to be much smaller than that achieved by a “popular” centralized mixer (as we will discuss). One of the reasons is that typically the produced mixing transaction will have to carry a signature by each of the participants (for example, see figures 2 and 3). The total length of all these signatures blows up the size of the posted transaction significantly for larger sets, to the point that it may grow past the limits specified by Bitcoin (100KB for standard transactions). For example, Ruffing34 is limited to 538 participants due to this.

In order to avoid this limitation,
CoinParty39 uses secure multiparty
computation protocols that allow a
set parties to collectively compute
over their inputs in a way that does
not reveal each party’s input to oth-
er participating parties. Using such
a protocol, the mixing participants
collectively set up a single shared
address (with off-chain communi-
cation) that is then used to transfer
coins to fresh addresses. This means
that the resulting transaction will
only carry a single signature under
this shared address. One major dis-
advantage of CoinParty is it requires
at least 2/3 of the participants to be
honest (which is an artifact of the se-
cure multiparty protocol it uses), in
order to guarantee no misbehavior
with respect to the output signature.

Xim6 can achieve large anonymity sets by an entirely different approach. Xim is a two-party mixing protocol that works as follows. First, during a pairing phase a party Alice that is interested in mixing her coins “advertises” this on the blockchain by posting a transaction that states she can be reached in a specific anonymous location (for example, a bulletin board maintained at a .onion Tor address she controls). An interested mixing partner Bob accesses the location expressing his interest by sending an anonymous location of his own (note that this communication takes place off the chain). After a specified amount of time, Alice chooses one of the interested partners that reached out to her (for example, Bob) and commits to proceeding by posting on her location a signed attestation of this. Within a fixed amount of time the two parties should post two trans-

Figure 4. Overview of Zerocoin.

( 1–2) Alice places a coin with (hidden) serial number S and (visible) commitment c to escrow, by posting a corresponding transaction to the blockchain. ( 3–4) To pay Bob, Alice publishes a transaction with Bob as the receiver but no explicit sender. Instead of the sender, the transaction reveals S and a proof that it matches some coin in escrow. Everyone can check the validity of π but nobody can link the transaction to Alice.