We (
Joseph Bonneau,
Arvind Narayanan,
Andrew Miller,
Jeremy Clark,
Joshua Kroll) are a group of cryptographers spread across a few universities (mostly Princeton, also UMD and Concordia) who have being doing research on Bitcoin. Some of our past and on-going projects include
anonymity in Bitcoin, discussion of the “Bitcoin is Broken” paper (
1,
2,
3),
distributed prediction markets,
authenticated data structures,
Bitcoin as a consensus game, and
CommitCoin.
We have recently written a
paper about Bitcoin mixing that will appear at Financial Cryptography 2014, and wanted to present it to the Bitcoin community here in this thread.
Our broad research goal is to analyze Bitcoin with an eye towards improvements that will help cryptocurrencies gain more adoption and acceptance. We believe there are benefits to financial privacy and improving this would be in the interests of the Bitcoin community and society at large.
Our method has been to design a protocol for third-party mixing services, and then analyze it in an economic model involving competing rational mixes and a population of users. We describe a potential design strategy which we call “Mixcoin” in
our full paper. To be clear,
we are not proposing an altcoin but providing suggestions for a mixing layer which can be implemented immediately, incrementally, and without any modifications to Bitcoin. While we aren’t providing a complete system with running code, existing mix services can incorporate our design, as we elaborate below.
There’s a well-known principle in anonymity research
“anonymity loves company”. This means any anonymity service requires a large population of participating users, ideally with different adversaries, so that one can’t simply assume all coins passing out of the mixing service are “tainted” (implicated as having participated in the mix). So it’s important that mixing is sufficiently automated, fast, low-cost, and safe that a large population of users is willing to participate. Our economic analysis is about a world with multiple independent mixes that compete economically, but also operate a mutually-compatible service. Our analysis includes the incentives of the mixes; for example, we’re interested in understanding whether utility-maximizing mixes are likely to behave correctly and provide a sufficient volume of service. Overall, the conclusion of our analysis is that a world with competing for-profit mixes can sustain itself and provide sufficient anonymity.
The functionality we have had to design for our mixes in order to arrive at this result can thus be seen as
good design guidelines for mixes. It is our hope that implementers of mix projects (like CoinJoin or DarkWallet), will be informed by our analysis and evaluation framework, and can benefit from our particular design suggestions. We’d appreciate feedback from the community on our proposals, and we will be happy to discuss our insights and perspectives gained from our research.
We have made the following specific suggestions for mixes:- First, users will want to use multiple mixes, and mixes should make this easy. Primarily, they should have standardized APIs for initiating a run of the mixing protocol. Some of our other suggestions depend to a degree on users being able to automate their interactions with mixes.
- Second, all mixing transactions should appear indistinguishable in the blockchain. Otherwise, an adversary can try to separately deanonymize different subsets of users who mix in distinguishably different ways. This means primarily that
all mixing transactions should be of the same value (which we call a “chunk size”), just like Tor packets have a constant size.
- Third, automation of the client-side is necessary to achieve meaningful anonymity. This is not just because funds to be mixed have to be split into a large number of chunks, but also because mixing opens up way too many side channels. Our protocol has logic built-in to it that minimizes these side channels. In particular, participation in rounds of mixing should happen periodically, at intervals chosen randomly from a memoryless (exponential) distribution. This distribution should be mostly standardized among client software implementations.
Nonetheless, there are limits to how well you can hide side channels in a mixing-based anonymity system. High-level flows could still be identifying. For example, if Alice receives 43.12312 BTC per week as salary/income and always transfers these payments to Bob, we suspect that this pattern can at best be obfuscated, not obliterated. There are still some open questions in quantifying side channels.
These parameters should be left free to change in the future, but defaults are important. If most users use one of a small number of client implementations then we expect they’ll converge on constant parameters including a constant chunk size.
- Fourth,
mixing fees should be all-or-nothing, that is, for every chunk of money the mix should either retain all of it or none. This might sound strange, but it greatly improves anonymity against clever analysis of the blockchain. If every time a user mixes a chunk the mix takes a constant 2% cut (or a randomized 1–3% cut) as a fee, then a chunk passing through multiple mixes in a row will have its value decrease in a traceable way. We can avoid this with all-or-nothing fees.
There are two consequences of this. First, the chunks should be small enough (say 0.01 BTC at the current exchange rate) that most mix users will accept the variance associated with random transaction fees. Second, this will mean that to mix realistic volumes, users will necessarily have to automate their interactions with mixes.
How will users (or their client software) verify that mixes that aren’t taking more than their cut? In the paper, we provide a cryptographically secure way to do this. But that’s not strictly necessary — since these chunks are quite small and most users will have significant numbers of chunks that they’ll move through each mix, clients can statistically verify if the mix deviates from it’s posted policy on the transaction fee.
- Finally, from the cryptographic perspective,
the key innovation in our paper is a “warranty” mechanism that allows users to provably expose cheating mixes. This is what allows us to prove, in a certain economic model, that rational mixes will choose to stay in business rather than defect with users’ funds. In practice, it’s plausible that if mixes incorporate our other suggestions and see a lot of volume as a result, then reports by community members of cheating vs. honest mixes should be sufficient to act as a reputation mechanism. Still, should consider the warranty mechanism that we propose as a further guarantee of service.
Comparisons to CoinJoin and ZerocoinExisting proposals for coin mixing fall into 3 basic models: mixing using a third party (e.g., Mixcoin), mixing arranged through peer-to-peer interactions (e.g., CoinJoin), and protocol-level integration of anonymity where anonymization is handled by the miners (e.g., Zerocoin).
CoinJoin is a technique for peer-to-peer mixing that requires users to coordinate through some rendezvous mechanism. Implementations to date have entrusted a third party matchmaker to fulfill this role. Although CoinJoin has the benefit that there is never a risk of losing coins, it is susceptible to Denial of Service since parties can withdraw after the second interaction required for the transaction to complete. As with mixes, anonymity may also be compromised, even if blinded tokens are used (as suggested by gmaxwell), by matching up real users with sock-puppets. In short, both third-party and peer-to-peer mixing seem to offer features that the other doesn’t.
Zerocoin (including the improved variant, Zerocash) requires a substantial change to the existing protocol, and so seems unlikely to catch on unless it is introduced as an altcoin (as its authors have recently proposed to do). Zerocoin also relies on an implicit trusted third party for a setup phase - a party who learns the trapdoor created during the setup phase can silently forge coins and increase the money supply.
Nonetheless, much of our analysis is independent of exactly how anonymity is achieved, and applies to CoinJoin and Zerocoin as well. As one example, if a matchmaker service for Coinjoin were to charge service fees, our analysis suggests a way to do it without the fee amounts compromising anonymity; another is defeating timing side-channels by sampling from a memoryless-distribution to decide when to participate in a mix. The paper goes into detail on this and other issues. We don’t consider Mixcoin to be the final word, and some combination of these techniques may lead to the best design.
tl;dr: We wrote a paper about Bitcoin mixes, in which we proposed techniques to keep mixes accountable and mutually-compatible, and argued they're economically viable.
