Topic: Mixing is practical: economic analysis and design guidelines [academic paper] (Read 13272 times)

Just want to thank you all for your work and criticism.  We've listened and are working to implement your theoretical work in the real world. 

Check out our work here.

Thanks,

DeepMix

Won't the large number of "chunks" cause too much strain on the network if people start doing it en masse?

I understand that by mixing you mean depositing funds with a third party, and then later withdrawing funds from that third party? That's bitbanks by another term, so if you're going to do that, just do it properly and support maintaining balances and off-chain transactions. Both features help with the transaction size problem by allowing the incoming transactions to have completely different amounts than outgoing - IE I deposit once and use that deposit to make n outgoing transactions, or destroy that information entirely by transferring funds to another user's balance without ever touching the blockchain at all.

Of course, if you're operating one of these mixers/bitbanks there's no reason not to use CoinJoin yourself for outgoing transactions. It's a particularly good use-case too because lots of users of mixers already expect to have delayed payments for privacy, so your CoinJoin implementation can act as the non-time-critical participants in CoinJoins, making it easier to find counterparties with similar (or identical) requested output amounts.

And speaking of output amounts, for some reason people seem to assume that they inevitably make CoinJoin's easy to trace; the model I proposed months ago with two-party mixes is to take advantage of the fact that many users do not need to have exact txout value amounts for many of their transactions. For instance if I'm depositing funds at an exchange I don't care about the exact amount. Or I may be willing to split a change output into two, or am using merge avoidance. Or I might just want to create a pool of unlinked Bitcoins to use later. Either way, it's very simple to copy your counterparty(s) txout value amounts, either single or in combination. Solutions like power-of-two amounts are work too, but they're much more restrictive and result in much more bulky transactions - ironically transactions that have worse privacy properties because they're more obviously CoinJoin mixes!

Incidentally, I noticed you refer to fidelity bonds; please add appropriate citations for them, either my post first using that name, https://bitcointalksearch.org/topic/purchasing-fidelity-bonds-by-provably-throwing-away-bitcoins-134827, or my earlier post on the bitcoin-development list. (http://www.mail-archive.com/[email protected]/msg01005.html) If you find an even earlier reference to the concept I'd be interested in knowing. My fidelity-bonded banking proposal is also apropos: https://bitcointalksearch.org/topic/fidelity-bonded-banks-decentralized-auditable-private-off-chain-payments-146307

Very interesting work, thanks for the paper. Provably fair mixing will likely be the next major step.

As for fees, I would recommend that we just go ahead and standardize 2^k satoshis for all k as mixing sizes. This also might optionally be used to remove the need for fee randomness, since we can just ask a user to provide 51 return addresses (or, perhaps more appropriately, a bip32 pubkey) and return the precise amount sans fees in the standard-sized chunks.

Andrew, I don't think that is an issue for wallets that natively support mixing. Let's say you measure effective mixing by the logorithm (bits) of the estimated anonymity set size, and within your wallet outputs are tagged with this value. If you use an input with anonymity set size N on a mix that is estimated to add M bits, then the mixed output has N + M bits of anonymity, and the change output keeps the original N bits. Does this make sense? There are some assumptions about independence and randomness in selection of join partners here, but those are assumptions that can be kept through proper engineering.

Sticking to a few common coin sizes should improve anonymity in fewer rounds, even when using CoinJoin, and even if your wallet helps keeps track. The simple reason is that if your coins are already in typical denominations, you can participate in another mixing round immediately without having to make change. On the other hand if every mixing round uses a different size, you will always need to make change, and then would need to mix the change as well.

Can you explain this one? I don't think it follows. A given transaction should have common sizes, yes (see: CoinJoin), but I don't think it follows that all transactions need to have that same transaction size. Each join can use a facilitator-chosen size so long as the wallet is capable of tracking the anonymity-set implications for each of its outputs.

Just my opinion, but I believe one of the key things that is making bitcoin gain acceptance is that it is *not* anonymous, and governments can work with it. If you want an anonymous coin, fine, but do it as a separate coin, don't attempt to make bitcoin anonymous. Just my 2 satoshis

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 Zerocoin
Existing 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.