Mixcoin
Anonymity for Bitcoin with accountable mixes(abridged pre-proceedings version)
Joseph Bonneau1 , Arvind Narayanan1 , Andrew Miller2 , Jeremy Clark3 , andJoshua A. Kroll1 and Edward W. Felten112Princeton University
University of Maryland
3
Concordia University

Abstract. We propose Mixcoin, a protocol to facilitate anonymous payments using the Bitcoin currency system. We build on the emergent phenomenon of currency mixes, adding an accountability mechanism to expose theft. Unlike other proposals to improve anonymity in Bitcoin, ourscheme can be deployed immediately with no changes to Bitcoin itself.
We demonstrate that incentives of mixes and clients can be aligned toensure that rational mixes will not steal from clients. We contrast mixing for financial anonymity with better-studied communication mixes,
demonstrating important and subtle new attacks.

1

Introduction

Protecting the privacy of financial transactions has long been a goal of the cryptography community, dating at least to Chaum’s work on anonymous digital
cash using blind signatures [4]. Despite initial excitement, anonymous digital
payments have not seen mass adoption. One reason is that traditional electronic
cash requires a central, trusted entity, typically called a bank.
By contrast, Bitcoin is a relatively young decentralized currency that has
rocketed to popularity with a market capitalization of over US$10 billion inearly 2014. Bitcoin can be thought of as a public, distributed ledger that logs
all transactions in order to prevent double spending. Using a proof-of-work system, the integrity of the ledger is maintained as long as a super-majority of thecomputing power is contributed by honest participants [18].
Bitcoin does not provide true anonymity: transactions involve pseudonymous
addresses, meaning a user’s transactions can often be easily linked together.
Further, if any one of those transactions is linked to the user’s identity, all of hertransactions may be exposed. A small but growing body of academic literature
has found that Bitcoin offers only weak anonymity in practice (see Section 2.1).
This has led to the rise of mixing services (or tumblers) which promise to takea user’s coins and randomly exchange them for other users’ coins to obfuscate
their ownership, though these come with no protection from theft.

2

The Bitcoin community is well aware of this issue, leading to much interestin the provision of stronger anonymity. One proposal, Zerocoin [16], provides
strong cryptographic anonymity but cannot be deployed without modification
to miners’ transaction validation process. CoinJoin [14] allows a group of Bitcoin
users to randomly permute their coins without entrusting them to a third party,
but it is complex for participants to protect their anonymity from each otherand the protocol can be easily stalled by a malicious entity. We provide moredetail of these solutions in Section 2.2, but note that Bitcoin still lacks a robust
protocol with strong anonymity properties that can be deployed immediately,
which is the problem we seek to address. Our strategy is to build on the existing
phenomenon of mixes, but to add an independent cryptographic accountability
layer. Our main contributions include the following:
Accountability. Mixcoin mixes issue signed warranties (Section 4) to users whichroughly state: “if Alice sends me v coins by time t1 , I will send v coins back to
her by time t2 .” A user can then confidently send funds to the mix, knowingthat if the mix misbehaves she can publish this warranty, damaging the mix’s
reputation and (presumably) its business model.
Randomized mixing fees. We show how paying mixes for their services incentivizes honest behavior (Section 6), yet fixed fees undermine anonymity whencoins are mixed multiple times. Instead we apply randomized, all-or-nothing feesin which mixes retain the entire value from a small percentage of transactions.
We show how to generate the requisite randomness in a fair and accountablemanner using the unpredictability of the Bitcoin block chain itself.
Mix networks for Bitcoin. Similar to experience from anonymous communication networks, we show how chaining multiple mixes together both improvesanonymity and guards against an adversary in control of some of the mixes.
There are important differences from communication mixes, however, introducing subtle new attacks (Section 7). Mixcoin offers strong anonymity against an
adversary who, in addition to being able to analyze the Bitcoin block chain,controls some mixes and can engage in transactions with the honest mixes.
Our design philosophy is a very general core protocol, allowing clients and mixes
to specify a variety of free parameters. Yet we expect that, because anonymity
loves company [8], these parameters will converge to global values (Section 7.6).
In particular, we expect mixing to complete in a few hours with mixing fees ofless than 1% (Section 6). Given this modest overhead and the fact that Mixcoin
can be deployed immediately with no changes to Bitcoin itself, it is our hopethat Bitcoin users may eventually mix their funds as a matter of course, finallymaking an anonymous, decentralized digital currency a reality.

2

Background and related work

In this section we provide a basic model of Bitcoin. We focus on the properties
required for Mixcoin, which could be implemented on top of any distributed

3

currency system similar to Bitcoin in these basic respects. We then model today’s
nascent Bitcoin mixes and the attacks they are vulnerable to.
2.1

Bitcoin

Bitcoin can be thought of as a decentralized system which tracks a mapping
between addresses and monetary value denominated in coins. An address, which
we denote κ, is simply a public key. Addresses are pseudonymous: anybody cancreate an arbitrary number of addresses for free with no verification. Control
of an address’s private key provides “ownership” of all coins mapped to that
address. The simplest4 Bitcoin transaction is essentially a statement that anaddress κin would like to transfer some value v to an address κout , signed by κin .
A distributed consensus protocol maintains a global history of all transactions
to prevent double spending. Transactions are grouped into blocks for efficiency,
which are chained in a linear structure called the block chain. The chain represents (probabilistic) consensus; at present most Bitcoin users will consider atransaction confirmed if it appears in a block with at least w = 6 blocks following
it. New blocks are generated roughly once every ten minutes.
Creating new addresses is trivial, but this does not make Bitcoin anonymousas all transfers are globally (and permanently) visible in the block chain. Several
recent papers have studied ways to link a user’s addresses to each other and to
an external identity [15,20,22,2].
2.2

Anonymity technologies for Bitcoin

There have been two prominent attempts to provide stronger anonymity in Bitcoin. One is an academic proposal called Zerocoin [16] which uses cryptographic
techniques (specifically, an accumulator with a zero-knowledge proof of inclusion) to break the link between individual Bitcoin transactions without adding
trusted parties. Unfortunately, deployment of Zerocoin (or related proposals,
such as Pinocchio Coin [7]) would require modifications to Bitcoin which appear
unlikely due to the computational overhead. Additionally, the cryptographic
constructions proposed require a trusted setup phase, where knowledge of the
trapdoor created during setup would allow an attacker to forge coins.
A second approach, arising organically from the Bitcoin community, is mixing, directly analogous to the concept in communication networks. In the common implementation a mixing address receives coins from multiple clients andforwards them randomly to a fresh address for each client. Several such services
have arisen, typically charging commissions in the 1–3% range and requiring
manual interaction through a website5 to arrange transactions. A small-scale
study of three mixing services found that in one case, taint analysis was immediately sufficient to link the input and output [17]. In the other two cases, taint4

Bitcoin transactions may feature multiple inputs and outputs. Bitcoin also features
a limited scripting language allowing more complicated transactions.
5
Some mixing services are only accessible as Tor hidden services.

4

analysis did not succeed but the transaction graph showed rich structure, leaving open the question of more sophisticated linking attacks. Anecdotal evidence
from user forums include complaints slow mixing times of up to 48 hours andlow transaction volumes leading to users frequently receiving their own coinsin return.6 Reports of theft by mixes are also a significant concern, with the
popular Bitcoin Wiki warning:. . . if the mixing output fails to be delivered or access to funds is denied there
is no recourse. Use at your own discretion.
In contrast to dedicated mixing services, some services with a high preexisting
trust requirement have deployed implicit mixing successfully. For example, theSilk Road marketplace mediated and mixed all transactions between buyers andsellers, while some “eWallet” services promise that when users withdraw funds
they will receive random coins from the provider’s reserves.
Finally, a proposal called CoinJoin [14] enables n users to atomically transfer
funds from their n input addresses to their n output addresses in a single transaction, signed by each key corresponding to the inputs, which is possible without
modification to Bitcoin. Since no entity will sign the transaction if its own output
address is not specified correctly, there is no risk of theft. However arranging theoutput addresses in a way that prevents the participants from learning the correspondence to input addresses (necessary for anonymity) introduces complexity,with most designs relying on external cryptographic protocols [6] and/or a thirdparty facilitator. An attacker can easily block the transaction by participating
initially to form the transaction, but failing to sign the finalized transaction.
Despite these problems, enthusiasm and interest in mixing is high. The recent
press on “dark wallets” for Bitcoin using Coinjoin is an example [12]. There has
also been vigorous discussion in the Bitcoin community on ideas for making
mixing secure and viable. However, to the best of our knowledge, the ideas we
introduce have not been explored previously.
2.3

Mix networks for anonymous communication

Mix networks were introduced by Chaum in 1981 for anonymous communication [3]. Significant research has analyzed the relationship between design parameters, such as route selection and flushing policies, and the resulting anonymity(see [19] for a survey), much of which is broadly applicable to financial mixing.
Verifiable mixing, beginning with Sako and Killian [23], aims to provide accountability by mixes issuing a proof that their output is a permutation of their
input, particularly important when users cannot trace their own input throughthe mix. In reputable mixing, beginning with [11], each mix provides proof thateach output corresponds to some input, as opposed to the mix itself originating
the message. Unfortunately these lines of research are largely orthogonal to therisk of theft in a financial mix. In communication mixes, messages can be resent,
which is not possible in Bitcoin as transactions are irreversible.
6

Receiving one’s own coins back from a mix is not necessarily a vulnerability. This
will happen with probability N1 with in a random permutation of N participant’s
coins.

5

3

A simple model of mixing

We start with a client Alice (A) who owns some number of Bitcoins at an address
κin which we assume is linkable to her real world identity. Alice wishes to transfer
some of her funds to a fresh address κout in such a way that it is difficult to linkκout to κin (and hence Alice herself), in exchange for a mixing fee.
Alice will send some of her coins to a mix M , a for-profit entity which will hold
Alice’s funds in escrow for an agreed time period before sending an equal value
to κout . We don’t require M to have any real-world reputation or assets, only
to maintain the same digital identity long enough to build a virtual reputation.
Alice is exposed to two major threats:
Theft Because mixes routinely send funds to fresh addresses with no transaction
history, it is possible for a malicious mix to send Alice’s funds to its own secretaddress κM instead of κout as requested. Though Alice can publicly complain
about the theft and attempt to undermine M ’s reputation, there is no way forobservers to determine which of A or M owns κM so Alice’s claim could be
libelous. For-profit mixes may rationally attempt to undermine trust in theircompetitors through false accusations of theft. Because allegations of theft cannot be proven, it is difficult to determine which mixes are honest.
Deanonymization Because the mix learns that the same party owns both addresses (κin , κout ), Alice’s anonymity depends on the mix keeping this pairing
secret forever. A mix which is malicious, compromised or subpoenaed mightshare its records and undermine Alice’s anonymity. Alternately, the mix could
send coins in a non-random manner which reveals the connection to observers.

4

The Mixcoin protocol

Our goal with Mixcoin is to provide a protocol for mixing with accountability.
Prior to mixing, the mix gives Alice a signed warranty which will enable her tounambiguously prove if the mix has misbehaved. Dishonest mixes will quickly
have their reputation destroyed and lose business. Security against theft thus
reduces to properly aligning economic incentives of mixes and clients.
However, there is no way to prove that a mix is not storing records sufficient
to deanonymize its clients. Similarly to mix networks for communication, Alicecan mitigate this risk by relaying coins through a series of mixes which must all
collude in order to deanonymize her final output address.
4.1

Assumptions

We assume the availability of multiple mixes Mi , each represented by a warrantysigning key KMi . As for-profit enterprises, mixes are motivated to build andmaintain a reputation in KMi , so it must be used consistently. Unlike mixes, Alice
does not need to maintain any long-term public key nor any public reputation.

6

Alice must be able to negotiate with the mix over an anonymous and confidential
channel. In practice this will likely be realized by mixes running a dedicated Tor
hidden service, but this is out of scope of the Mixcoin protocol itself.
4.2

Core protocol

We outline the core Mixcoin protocol in Construction 1 which mixes a single“chunk” v of Alice’s funds. For effective anonymity, chunk sizes should be standardized, as discussed in Section 7.6. While the core protocol can stand on its
own, typically Alice will need to split her funds into multiple chunks and perform
multiple sequential rounds of mixing for each.
The key accountability mechanism is Alice’s receipt of a signed warranty
prior to mixing. In Step 1 Alice contacts the mix over an anonymous channel
and proposes a set of mixing parameters:
v
t1
t2
κout
ρ
n
w

the value (chunk size) to be mixed
the deadline7 by which Alice must send funds to the mix
the deadline by which the mix must return funds to Alicethe address where Alice wishes to transfer her funds
the mixing fee rate Alice will pay
a nonce, used to paying randomixed mixing fees
the number of blocks the mix requires to confirm Alice’s payment

If the mix accepts these terms (Step 2a) it generates a fresh escrow address κesc
and sends back a warranty containing all of Alice’s parameters plus κesc , signed
using KM . The mix may also reject Alice’s request for any reason (Step 2b),though in practice we expect that a reputable mix will abide by a public policy
for acceptable terms. Alice similarly has no obligation to transfer funds after
receiving a warranty. If Alice declines (or forgets) to do so by the deadline t1 themix may delete its records and move on.
If Alice does transfer the agreed value v to κesc by the deadline t1 (Step 3),
then the mix is obligated to transfer an equal value to κout by time t2 (unlessthe funds are retained as a mixing fee—see Section 4.4). If the mix does sofaithfully (Step 4a), then both parties should destroy their records to ensure
forward anonymity against future data breaches. If the mix fails to transfer thevalue v to κout by time t2 (Step 4b),8 then Alice publishes her warranty (Step 5).
Because the warranty is signed by the mix’s long-term key KM and all Bitcointransactions are publicly logged, anybody can verify that the mix cheated.
4.3

Freshness of addresses

Both the mix’s escrow address κesc and Alice’s output address κout should be
fresh addresses created specifically for mixing. This is required because warranties include neither κin nor κ0esc , so they will appear to be satisfied as long
8

There is no way in Bitcoin to guarantee a transaction will be included in any specificblock. Therefore in practice mixes will likely require a safety margin of several blocks
to t2 to ensure they can include the transaction before that time.

7

The Mixcoin protocol
anon1) A −→ M :hv, t1 , t2 , w, κout , ρ, ni

M accepts terms,
specifies κesc

M rejects termsanon2b) A ←− M :⊥anon2a) A ←− M :{v, t1 , t2 , w, κesc , κout , ρ, n}KM
A pays on time(from any address)

A destroys κout
A doesn’t pay
M aborts protocol

3) A (by time t1 ):Transfer (v, κin , κesc )X = Beacon(t1 , w, n)X≤ρ

M retains funds

X>ρ
M steals funds

M acts honestly4a) M : (by time t2 )Transfer (v, κ0esc , κout )4b) No transfer toκout by time t2
A detects theft (after t2 )Protocol successful
A, M destroy records5) A publicizes:{v, t1 , t2 , w, κesc , κout , ρ, n}KM

Construction 1: A single mixing round between client A and mix M . A owns theRaddresses κin and κout and M owns κesc and κ0esc . The random value X ← (0, 1)
is computed using Beacon, a pseudorandom function using the Bitcoin block
t1 + w plus the nonce n, and compared to the fee rate ρ. Times t1 and t2 areblocks in the block chain. Curly brackets ({}) indicate a digital signature.

8

as v is transferred on time to κesc and then κout from any address. Thus bothparties should pick addresses with no other possible source of income so that theother party must themselves pay to fulfill the contract.
4.4

Mixing fees

A simple approach is to specify a fixed mixing fee rate ρ and have the mix return(1−ρ)·v to κout instead of the full v . However, this is problematic for sequential
mixing, as the smaller output value (1−ρ)·v cannot be the input to a subsequent
round of mixing with the same v. This could be addressed by using diminishingtransaction sizes vi = (1 − ρ)i · v for each round i, but this would undermine thegoal (Section 7.6) of indistinguishable transfers and limit the anonymity set ineach round to only other transactions at the same round of mixing.
Our solution is randomized mixing fees, whereby with probability ρ the mix
retains the entire value v as a fee, and with probability (1 − ρ) takes no fee atall. This produces an expected mixing fee rate of ρ and leaves κout with either
nothing or a full v which can be directly re-mixed. This solution is related tothe idea of electronic lottery tickets [21] used in some micropayment systems.9
The mix must use a publicly verifiable mechanism to randomly choose whichchunks to retain as mixing fees. Specifically, the mix must generate a (ρ, 1 − ρ)random bit which neither party can predict but can be audited afterwards forfairness. This can be done with a public source of randomness called a beacon.
If the beacon is external to Bitcoin (e.g., NIST’s beacon [1] or financial
data [5]), warranties would need to be synchronized to real-world time to enable
auditing. Alternatively, randomness can be extracted from future Bitcoin blocks,
assuming the exact set of future transactions included in each block (as well as
the random nonce used to solve the proof-of-work puzzle) is unknown.10 Because
each block includes the value of the previous block, every transaction during a
confirmation period of w blocks adds randomness.11 The warranty also includes
a nonce n specified by Alice to ensure that the mix will compute an independent
value for all transactions it is managing. Specifically, the mix computes X =Beacon(t1 , w, n) = PRNG (n||Bt1 +w ), where Bi is the Merkle root of block i in
the block chain and PRNG is a cryptographic pseudorandom number generator
which outputs a value uniformly drawn from the range (0, 1).
The mix retains Alice’s funds only if X ≤ ρ. Because this computation canbe performed by anybody if Alice’s warranty is published, cheating by the mix is
detectable. Furthermore, in normal operation Alice’s warranty (containing n) is
kept secret so observers can’t tell which transactions were retained by the mix.
9

Our motivation to use randomized fees is different from the case of micropayment
systems, which do so to avoid transaction costs from many low-valued payments.
10
A mix might also be a miner, in which case it may attempt to influence the block.
However, such an attack is highly uneconomical given the high reward for mining a
block compared to mixing fees.
11
Though in practice w = 6 is a common standard, we include w as a negotiable
parameter in the warranty to enable flexibility.

9

A drawback of randomized fees is that variance in the effective mixing fee
rate increases for users mixing a small number of chunks. To address this, v
should be kept as low as possible so that most users can mixing at least vρ coins.
4.5

Transaction fees

In addition to mixing fees, Alice may have to pay transaction fees to Bitcoinminers to ensure her transactions are included in the block chain.12 Fixed transaction fees pose the same problem for anonymity that fixed mixing fees would,
but paying miners randomly would require changes to Bitcoin itself.
Given a source of anonymous coins, Alice could address the problem of decreasing chunk sizes by “topping up” each chunk after it is mixed using herpool of anonynmized coins. However, it doesn’t work for Alice to simply mix
one chunk perfectly and then use it top up many other chunks, as this would
publicly link each of those topped up chunks as belonging to the same party.
Thus Alice would need a large number of mutually unlinkable addresses holding
transaction-fee sized values useful for topping up. Acquiring these through mixing becomes a recursive problem though, as they themselves would require aneven greater number of unlinkable addresses for their mixing!
Instead, mixes can effectively pay transaction fees both13 for both the transferfrom κin to κesc and from κ0esc to κout . Assuming miners require a minimumtransaction fee τ (with τ  v), Alice can transfer v from κin of which the mix
will receive v − τ at address κesc . The mix can then form an output transaction
with v − τ from some κ0esc and 2τ from a third address κ∗esc which the mix
previously retained as a mixing fee, ensuring that κout receives a full v while theminers still collect a fee of τ . Of course, the mixing fee rate ρ must be increased
to cover the mix’s expected outlays on transaction fees.
This poses a problem for mix indistinguishability, which we’ll discuss further
in Section 7.2, as at the mix must use the same κ∗esc to cover transaction fees for
multiple chunks which will then all clearly come from the same mix. It is also
possible for mixes to collaborate and mix their reserves available for transaction
fees using CoinJoin, which may be far more practical for mixes to organize
without being subject to denial-of-service issues.

5

Sequential mixing

Given the above Mixcoin protocol for interacting with a single mix, Alice will
most likely want to send her funds through N independent mixes to protect
her anonymity against the compromise of an individual mix. To do so, Alice canchoose a sequence of N mixes M1 , . . . MN and execute the Mixcoin protocol witheach of them in reverse order, instructing each mix Mi to forward her funds to12

Some transactions are accepted today without fees, though miners may change thisat any time, which may become occur as the minting rate decreases.
13
In pipelined sequential mixing, which we will discuss in Section5, most mixes willneed only pay one transaction fee.

10

the escrow address κesci+1 which she previously received from mix Mi+1 . Afterobtaining N signed warranties,14 Alice then transfers her chunk to κesc1 and if
any mix in the sequence fails to transfer it she can prove it with the appropriate
warranty. One subtlety is that each mix can likely determine which number it isin the sequence based on timing information, as the later mixes will be contacted
further in advance from when mixing will actually take place.
In practice, Alice most likely wants to transfer some value kv split into kseparate chunks. This means she will need to negotiate a total of kN warranties with mixes. An important consideration is that each chunk should travel
through an independently-chosen random sequence of mixes. Otherwise, Alice’s
chunks would be exchanged for each other more frequently than would happen
via chance, which would leak information to a potential attacker.

6

Mix incentives and mixing fees

Establishing the mixing fee rate ρ requires considering the dual roles of mixing
fees. First, they can cover direct expenses for mixes such as Bitcoin transaction
fees and electricity bills. Second and most importantly, they provide a mechanism
for mixes to profit from honest behavior and disincentivize mixes from ceasing
operations and absconding with users’ funds. Because higher fees more strongly
incentivize honesty, an interesting property arises that users should avoid mixes
charging less than some minimum acceptable value of ρ.
In a steady-state model, the mix has two choices for any given block in time:
continue to operate honestly until the next block, or abscond and retain all user
funds it holds in escrow. The expected value of either choice scales linearly with
Q, the average amount of money flowing into (and out of) the mix during any one
block. If t̄ is the average time period (in blocks) that the mix holds funds duringa mixing round, then the expected payoff of absconding is E[abscond] = Qt̄.
The expected payoff from choosing to continue would properly be definedrecursively, since the mix is able to play the same game again. However, understeady state conditions the optimal decision will be the same in every round, so
if the mix initially chooses to continue it will do so indefinitely. Assuming themix is exponentially discounting future earnings15 at a rate r (per block), thenet present value of indefinite honest behavior with a fee rate ρ is:E[continue] = ρQ + (1 − r)E[continue]ρ= Qr
Incentivizing honest behavior therefore requires that ρr > t̄. With the interpretation that r for a rational mix is equivalent to the highest available risk-free
14

Unlike in traditional communication networks, an onion routing approach doesn’t
seem possible due to the interactivity required in Mixcoin.
15
The exchange rate of bitcoins may of course be drastically different in the future.
We assume mixes have no private information about the future value of bitcoins andtherefore use its current market price in calculating the net present value.

11

rate of return available, this condition is simply that the expected value of feescollected by a mix during the time it holds funds is greater than the amountthose funds would yield during the same time period if invested.16 This can be
explained by considering that we want an honest mix to continually decided to“invest” its potential earnings Qt̄ from absconding into continuing to serve as amix, earning a return of ρQ during every block.
We can estimate that relatively low mixing fees should suffice to incentivize
honest behavior. Assuming a very attractive rate of return of r ≈ 20% annually isavailable to the mix, a mix time of t̄ ≈ 1 hour gives a lower bound of ρmin ≈ 2−15 .
Even considering a chunk taking a path through 10 consecutive mixes, this stillleaves only an effective fee rate of ≈ 2−12 necessary to discourage absconding.
This suggests that very low mixing fees may be sufficient to cover the risk oftheft.17 Still, Actual mixing fees will be dominated by operating costs, suggestingthat any mix which has been operating for a non-trivial period of time is turninga profit and is unlikely to abscond.

7

Anonymity properties

Given the large number of negotiable parameters in Mixcoin, our anonymity
analysis is theoretical. The actual anonymity guarantees will depend on how themixing ecosystem evolves. However, we can describe a threat model, quantify
anonymity under a simplified model, discuss optimal strategies for mixes andclients, enumerate some attacks and how to avoid them. We draw many connections to the extensive literature on mix networks for communication, dating
to the initial proposal of communication mixes in 1981 [3]. That said, financial
mixing also differs from communication networks in important ways.
7.1

Threat model

We focus on an attacker who wants to gain as much information as possible
about the anonymity set of possible pre-mixing input addresses which may havebeen the source of the funds held by a final output address κout .
Because the Bitcoin block chain is a permanent, public record of all transactions, every attacker is trivially a global passive adversary, a common attack
model studied for communication mixes.18 Mixing literature also considers extended attacker capabilities, such as compromising mixes, delaying or blocking
messages, replaying old messages, or flooding the network with dummy messages [24]. Replay should be impossible in Mixcoin due to the double spending
prevention in Bitcoin, but flooding and delaying may be possible.
16

This equivalence ignores the effects of compounding interest, though r and t̄ areboth low enough that (1 + r)t̄ ∼ 1 + rt̄.
17
In practice, absconding may be slightly more appealing due to super-exponential
time discounting by the mix or the risk that business may decline.
18
Tor is notably not designed to withstand attack by a global passive adversary, as
Tor relays provide no mixing of traffic [9].

12

7.2

The passive adversary’s view with mix indistinguishability

The best-case scenario for Mixcoin is a passive adversary. We assume this adversary can reliably determine with high probability which Bitcoin transactions are
mix traffic, given their size v and their use of one-time escrow addresses. However, due to their one-time nature, this simple adversary may be unable to link
escrow addresses to specific mixes, a novel property with no apparent precedentin communication mixes which we call mix indistinguishability.
If this is the case, the adversary is left to observe a sea of apparently identical escrow addresses and the system appears to function as one universal mix
consisting of all participants using the chunk size v. There are several scenarios
in which mix indisinguishability may fail (which we will discuss in Section 7.3)
but the anonymity offered is quite strong in this case.
7.3

Active adversaries and distinguishable mixes

There are several ways that an active attacker might be able to distinguish which
escrow addresses correspond to which mix and hence which mixes are involved ina chunk’s mixing path. Observe that when Alice sends a chunk from κin to M via
κesc , the client who ultimately receives this chunk will learn that κin interactedwith M . Similarly, the client who sends the chunk to κ0esc which is eventuallysent to κout will also learn that Alice interacted with M . An active adversary can
exploit this in a flooding attack, learning up to two other addresses interactingwith the same mix for each chunk sent through that mix.
A second attack vector, if mixes are forced pay transaction fees, is that whena user’s chunk is retained as a mixing fee by mix M it may might be used by
M to pay transaction fees on many other transactions, all of which can then belinked to M . The effectiveness of this attack depends on the ratio of transaction
fees per chunk τ to average mixing fees per chunk ρv. Mixes will have to spend aτof their mixing fee revenue on transaction fees, so if mixes allocate
proportion ρv
a constant proportion of each retained chunk to transaction fees each retainedτchunk will pay fees on ρ1 · ρv
other transactions. Since each chunk is retainedwith probability ρ, the expected number of transactions identifiable by a givenτ
input transaction is just ρv, which is maximized at 1 if mixing fees are only highenough to cover transaction fees.
Thus for each mixing transaction an active attacker performs with M , sheτother transactions to M . Observing the majority
can link up to (1 − ρ) · 2 + ρv
of links therefore appears to require an attacker generate a large portion of themix’s traffic. Even against an implausibly strong active attacker who can link
every escrow address to its originating mix, the anonymity set still snowballs
quickly with each mixing round as in traditional communication mixes.
7.4

Anonymity sets and mix delay

Regardless of mix distinguishability, there is a trade-off between mixing chunkswith many mixes for a short escrow period each or few mixes with a longer escrow13

period. The escrow period is limited by t2 and t1 as specified in the warranty,
with a maximum delay of δmax = t2 −t1 . Mixes will also require a minimum delayof δmin = w (typically 6 blocks) to protect against double spending. Picking thesmallest possible t2 = t1 + w allows Alice to afford more rounds of mixing in agiven time period. But this also means that Alice’s anonymity set for the roundconsists only of other chunks that were mixed at time exactly t1 .
We assume that individual mixes will only issue warranties with a specificδmax as a matter of policy,19 and will then uniformly at random choose a delay δ ∈R [w, δmax ] before forwarding Alice’s chunk.20 Thus each mixing step
adds lg (Q(δmax − w + 1)) bits of entropy to Alice’s anonymity set, at a delayof δmax blocks.21 In other words, the entropy of her anonymity set grows bylg(Q(δmax −w+1))
per block. It turns out that for w = 6 this expression is maxiδmax
mized for δmax = 6 for Q ≥ 128 (and δmax = 7 for 13 ≤ Q < 128) so it appears
minimal delays and longer mixing chains are preferable.
7.5

Mixing multiple chunks

So far we have considered each chunk individually. However, if Alice combines
many mixed chunks to make a payment, her anonymity set will be reduced
to the intersection of the anonymity sets of all chunks. As long as she mixed
those chunks sufficiently at the same time, then those chunks will have the sameanonymity sets, and her payment is still unlinkable.
However, if even one of the chunks travels through a path consisting entirelyof compromised mixes, Alice’s entire payment completely loses anonymity. If
each chunk is routed independently, then with say 25% of mixes compromised,
there is a 2−20 chance of routing a chunk through a chain of 10 compromised
mixes, which may be acceptably low. However this probability increases rapidly
if a greater fraction of mixes compromised. One way to avoid this would be torandomly pick a set of mixes for each batch of funds to mix, and to use a random
permutation of that set for each chunks in the batch. In Tor, there is a similarargument for why building circuits improves anonymity as opposed to routing
each packet independently.
7.6

Convergence of free parameters

Our design intentionally left many parameters free, such as the chunk size v,
the time delay t2 − t1 and the number of rounds N . Our philosophy is to avoid
embedding these into the protocol as the optimal choices may drift over time as
the mixing ecosystem evolves and the underlying parameters of Bitcoin change.
19

Allowing different delays per client would open the possibility of free-riding andmake anonymity analysis much more complex [10].
20Non-uniform distributions such as an exponential distribution are possible, but they
make it difficult to provide a firm bound on the delay as required by the warranty.
21
Because Alice must have already negotiated her mixing warranty for the next round,each warranty must be delayed by the maximum δmax blocks.

14

Yet it is critical for anonymity that a large number of users choose the samevalues22 to avoid splitting their anonymity sets based on parameter choices.
As a case study, consider the effect of two different common values of v.
Each will be clearly identifiable in the block chain and hence the anonymity set
for each chunk is limited in the best case to those users who mixed a chunkof identical size in the same time period. We could attempt to ameliorate thisslightly by hoping that all users mix chunks of both sizes regularly, but thisis quite fragile.23 The best-case scenario for anonymity is if all users choose thesame chunk size. Yet there is an inherent trade-off: setting v too high will exclude
users owning less than v coins,24 while decreasing v will require proportionately
more runs of the protocol and more transactions in the block chain.25
Still, we expect v and other parameters to converge in practice to a common
value (or a small set) for two reasons. First, like with Bitcoin itself most clients
will likely use one of a small number of software implementations which include
reasonable parameters and a popular mix reputation list.
Second and more importantly, all clients have an incentive to choose the mostpopular parameters in an application of the “anonymity loves company” principle [8]. Unilateral variation in a user’s transaction sizes, for example, could leakinformation which would help Eve deanonymize Alice’s coins. Thus we expect
Mixcoin users to relatively quickly converge on a global set of parameters, or possibly a small number of different “flavors” of Mixcoin, to maximize anonymity.
7.7

Side channels

Financial mixing introduces several subtle side channels.26 The most obvious ispayment sizes: If Alice receives a very specific amount of Bitcoins at her longterm address, is observed mixing them, and a day later an equal quantity of
mixed chunks are combined to make a payment, the adversary might plausiblyinfer that Alice made the payment. This can be addressed if Alice mixes her
incoming funds as soon as she receives them and not immediately prior to making
a payment. Of course, this requires Alice to always carry a balance of mixed funds
and never pay them all out at once.
More subtle issues arise becaues mixed chunks carry an implicit timestampof when they were last mixed. Suppose Alice immediately mixes three large,
equal-sized quantities of income on three specific dates and then later combines
22

Note that the mixing fee rate ρ is unobservable and hence should have no impact onanonymity and can be chosen independently by different mixes.
23
For example, if chunk sizes α and β are common, a user mixing x = k1 α + k2 β will
have her anonymity set limited to other users mixing at least k1 chunks of size α
and at least k2 of size β, instead of all users mixing at least x.
24
Additionally, with randomized mixing fees (see Section 4.4) users owning only asmall multiple of v may face unacceptably high variance in their fee rate.
25
The Bitcoin community frowns on creating large numbers of low-value transactions(referred to as dust) because it places a higher verification burden on miners.
26
Network-level side channels are out of scope. As noted earlier, we assume that Mixcoin clients always communicate using a secure anonymity network such as Tor.

15

a random subet of her mixed chunks to make a payment. Eve can trace theoutgoing payment to Alice if it contains a mix of chunks from these times andAlice was the only person mixing at each of them.27 The attack might work even
if Alice wasn’t the only person mixing: if Alice picks a random set of her mixed
chunks, then the proportion of chunks from each time period in the outgoingpayment will correspond to the amount Alice mixed in each time period.
Thus, even perfect mixing can leave Alice’s transactions linkable without
further obfuscation. One defense is for Alice to only make payments using chunks
that were mixed contemporaneously. This works if payments are small enough.
Second, Alice could re-mix all of her chunks every time she receives income. This
destroys the timing information, but is expensive. Third, if Alice has advancenotice before needing to make a payment, she can employ input/output mixing.
Alice mixes her funds as soon as she receives income. When she needs to make apayment, she mixes a set of (already mixed) chunks totaling the amount she owes.
It introduces a delay in payment equivalent to mixing time, which is why Alicemust have advance notice. Finally, in Appendix A we introduce continual mixing,a more complex approach which can provide stronger guarantees of anonymity.

8

Conclusion

Despite significant interest in providing strong anonymity for Bitcoin, the designof a robust protocol with that can be deployed without modifications to Bitcoin
has remained an open question. In this paper we proposed Mixcoin, which we
believe meets these goals. Our key innovations are cryptographic accountability,
randomized mixing fees, and an adaptation of mix networks to Bitcoin. We lookforward to engaging with the academic community and the Bitcoin community tofurther refine the design and to progress toward implementation and deployment.
We also provide an initial treatment of mixing for financial privacy, a researcharea which we expect will be as deep and challenging as mixing for communication privacy. Many basic properties of communication mixes, such as the ability
to pad or replay messages, don’t exist in a financial setting. Yet interesting newproperties, such as the possibility of indistinguishable mixes, arise. We expectthat ensuring financial privacy, regardless of the underlying mixing protocol,
will require careful consideration of some of the higher-level sidechannels wehave only briefly explored here.
Acknowledgements. We thank our anonymous referees and all who read drafts
and contributed valuable suggestions to this work, especially Aaron Johnson, Ian
Miers, Roger Dingledine, George Danezis, Peter Eckersley and Eran Tromer.

27

This is analogous to an intersection attack in the mixing literature.

16

References
1. NIST Randomness Beacon. http://www.nist.gov/itl/csd/ct/nist_beacon.cfm
2. Androulaki, E., Karame, G.O., Roeschlin, M., Scherer, T., Capkun, S.: Evaluating
User Privacy in Bitcoin. In: FC (2013)
3. Chaum, D.: Untraceable electronic mail, return addresses, and digital pseudonyms.
Communications of the ACM 24(2), 84–90 (1981)
4. Chaum, D.: Blind signatures for untraceable payments. In: CRYPTO (1982)
5. Clark, J., Hengartner, U.: On the Use of Financial Data as a Random Beacon.
Usenix EVT/WOTE (2010)
6. Coutu, O.: Decentralized Mixers in Bitcoin. In: Bitcoin Conference (2013)
7. Danezis, G., Fournet, C., Kohlweiss, M., Parno, B.: Pinocchio Coin: Building Zerocoin from a Succinct Pairing-Based Proof System. In: Language Support forPrivacy-Enhancing Technologies (PETShop) (2013)
8. Dingledine, R., Mathewson, N.: Anonymity Loves Company: Usability and the
Network Effect. In: WEIS (2006)
9. Dingledine, R., Mathewson, N., Syverson, P.: Tor: The second-generation onion
router. In: USENIX Security (2004)
10. Dingledine, R., Serjantov, A., Syverson, P.: Blending different latency traffic withalpha-mixing. In: PET. pp. 245–257. Springer (2006)
11. Golle, P.: Reputable mix networks. In: PETS (2004)
12. Greenberg, A.: DarkWallet Aims To Be The Anarchist’s Bitcoin App Of Choice.
http://www.forbes.com/sites/andygreenberg/2013/10/31/darkwallet-aimsto-be-the-anarchists-bitcoin-app-of-choice/ (2013)
13. Jolly, G.M.: Explicit estimates from capture-recapture data with both death andimmigration-stochastic model. Biometrika 52(1/2), 225–247 (1965)
14. Maxwell, G.: CoinJoin: Bitcoin privacy for the real world. https://bitcointalk.
org/index.php?topic=279249.0 (August 2013)
15. Meiklejohn, S., Pomarole, M., Jordan, G., Levchenko, K., McCoy, D., Voelker,
G.M., Savage, S.: A fistful of bitcoins: characterizing payments among men withno names. In: IMC (2013)
16. Miers, I., Garman, C., Green, M., Rubin, A.D.: Zerocoin: Anonymous Distributed
E-Cash from Bitcoin. IEEE Symposium on Security and Privacy (2013)
17. Möser, M.: Anonymity of Bitcoin Transactions: An Analysis of Mixing Services.
In: Proceedings of Münster Bitcoin Conference (2013)
18. Nakamoto, S.: Bitcoin: A peer-to-peer electionic cash system (2008)
19. Raymond, J.: Traffic analysis: protocols, attacks, design issues, and open problems.
In: PETS (2001)
20. Reid, F., Harrigan, M.: An analysis of anonymity in the bitcoin system. In: Security
and Privacy in Social Networks (2013)
21. Rivest, R.: Electronic Lottery Tickets as Micropayments. In: FC (1997)
22. Ron, D., Shamir, A.: Quantitative Analysis of the Full Bitcoin Transaction Graph.
FC (2012)
23. Sako, K., Kilian, J.: Receipt-Free Mix-Type Voting Scheme - A Practical Solution
to the Implementation of a Voting Booth. In: EUROCRYPT (1995)
24. Serjantov, A., Dingledine, R., Syverson, P.: From a trickle to a flood: Active attacks
on several mix types. In: Information Hiding (2003)

17

A

Continual mixing

A more in-depth defense against some of the side-channel attacks introducedin Section 7.7 is continual mixing, which does not require advance notice of
payments. In addition to avoiding the timing side channel, it actually increases
Alice’s anonymity set. The core idea is that Alice continues mixing her coins until
she is ready to spend them, but at a greatly reduced rate (e.g., one round permonth). Let ∆A be a time period such that Alice is prepared to keep her coins
for time ∆A between receiving them and spending them. Then the continual
mixing algorithm for a chunk c for which initial mixing completes at time t0 is
as follows:• generate ∆A,c = U [0, ∆A ]• mix c at time ∆A,c and thereafter at ∆A intervals• mark c as spendable after the first continual mix round
It is easy to verify that regardless of the timings of the payments received
by Alice, the distribution last mixing times for each of her spendable chunks
is always U [0, ∆A ]. This nullifies the timing channel, except for the matter ofpicking ∆A . If Alice makes a payment with a random subset of her spendable
chunks, Eve can infer ∆A with high accuracy.
Picking ∆ involves a trade-off. From the point of view of a business, if ∆ is
too high, it adds latency to the operating cycle and decreases cash flow. If ∆is too low, it leads to a higher depreciation rate of long-term assets due to themixing fees incurred by continual mixing. Further, clients must consider eachothers’ choices in picking ∆, since anonymity loves company and highly unusual
values of ∆ will help Eve.
Given these constraints, we propose several globally fixed values of ∆: for
instance, a day, a week, a month, and a quarter; each client is free to pickthe value that best suits their operating patterns. Alice can now expect her
anonymity set to be the set of all Mixcoin clients who have the same value of ∆.
Some inference attacks are hard to prevent with any mixing system. For
example, if Alice owes Bob a highly unique amount of money, and neither Alicenor Bob transacts with any other users, this information is sufficient to link
Alice’s outflow with Bob’s inflow. Unlikely as such situations are for most users
in the real world, they pose a problem for analysis of anonymity of our system.

B

Improving mix trustworthiness

If a mix cheats, the cheated client can ensure that the mix gets a poor reputation.
But how can a mix build a reputation for trustworthiness? Even if there are notheft reports against it, it might simply be because the mix doesn’t have muchvolume yet. Further, to the extent that more popular mixes may offer better
anonymity (Section 7.3), clients would like to estimate mix transaction volumes.
In this section we discuss ways to better measure, as well as prove, mix trustworthiness, and even a mechanism for recourse against cheating mixes. These
are all “out-of-band” and do not require modifications to the Mixcoin protocol.

18

B.1

External reputation

While some mix operators may choose to be anonymous, others may be comfortable revealing their real-world identity. A bank or trusted community member
could leverage their external reputation to increase trust in their mix service.
B.2

Throttling

Throttling, or rate limiting by the client, lets Alice limit her exposure to a given
mix at any given time. If Alice wants her maximum exposure to M to be E,E
per block, where δmax is theshe transacts with M at the average rate of δmax
maximum mix delay that she picks for M . If she stops transacting with M assoon as she detects misbehavior, then M can steal at most E of her coins.
B.3

User reports

To estimate volume, client users could publish through out-of-band channels,
such as forums, logs containing aggregate statistics about their usage of various
mixes (e.g., “Alice mixed 10,000 chunks through mix M1 in August”). If these
are reputable members of the community (for example, with longstanding active
accounts), observers can be reasonably confident that they are not sybils. Such
reports provide lower bounds on mix volume.
B.4

Mark and recapture

The mark-and-recapture method for estimating wildlife populations (e.g., [13])
could be used to estimate a mix’s escrow reserves and hence its volume. The
method involves engaging the mix in n transactions over a short period, andobserving what fraction of these get forwarded among the set of corresponding
return transactions. If the transaction volume of the mix is Q, then at any timethe escrow pool contains Q transactions, and the expected number of corresponding returns is approximately n/Q when n is much smaller than Q. The mix may
attempt to inflate this measurement by simulating transactions of sybil clientsand contributing its own funds to the escrow pool. To defeat sybil detection bytransacting with other mixes would incur fees proportional to the inflated volume. Thus, to inflate the apparent volume to twice the actual amount, the mix
would have to forego its entire profits.