Skip to main content
Top

2014 | OriginalPaper | Chapter

Mixcoin: Anonymity for Bitcoin with Accountable Mixes

Authors : Joseph Bonneau, Arvind Narayanan, Andrew Miller, Jeremy Clark, Joshua A. Kroll, Edward W. Felten

Published in: Financial Cryptography and Data Security

Publisher: Springer Berlin Heidelberg

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We propose Mixcoin, a protocol to facilitate anonymous payments in Bitcoin and similar cryptocurrencies. We build on the emergent phenomenon of currency mixes, adding an accountability mechanism to expose theft. We demonstrate that incentives of mixes and clients can be aligned to ensure that rational mixes will not steal. Our scheme is efficient and fully compatible with Bitcoin. Against a passive attacker, our scheme provides an anonymity set of all other users mixing coins contemporaneously. This is an interesting new property with no clear analog in better-studied communication mixes. Against active attackers our scheme offers similar anonymity to traditional communication mixes.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Appendix
Available only for authorised users
Footnotes
1
Bitcoin transactions may feature multiple inputs and outputs. Bitcoin also features a limited scripting language allowing more complicated transactions.
 
2
Some mixing services are only accessible as Tor hidden services.
 
3
Receiving one’s own coins back from a mix is not necessarily a vulnerability. This will happen with probability \(\frac{1}{N}\) in a random permutation of \(N\) participant’s coins.
 
4
Deadlines are specified as block numbers in the Bitcoin block chain, rather than clock times, to enable unambiguous auditing.
 
5
There is no way in Bitcoin to guarantee a transaction will be included in any specific block. Therefore in practice mixes will likely require a safety margin of several blocks to \(t_2\) to ensure they can include the transaction before that time.
 
6
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.
 
7
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.
 
8
Though in practice \(w=6\) is a common standard, we include \(w\) as a negotiable parameter in the warranty to enable flexibility.
 
9
Some transactions are accepted today without fees, though miners may change this at any time, which may occur as the minting rate decreases.
 
10
In pipelined sequential mixing, which we will discuss in Sect. 5, most mixes will need only pay one transaction fee.
 
11
Unlike in traditional communication networks, an onion routing approach doesn’t seem possible due to the interactivity required in Mixcoin.
 
12
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 and therefore use its current market price in calculating the net present value.
 
13
This equivalence ignores the effects of compounding interest, though \(r\) and \(\bar{t}\) are both low enough that \((1+r)^{\bar{t}} \sim 1+r \bar{t}\).
 
14
In practice, absconding may be slightly more appealing due to super-exponential time discounting by the mix or the risk that business may decline.
 
15
Tor is notably not designed to withstand attack by a global passive adversary, as Tor relays provide no mixing of traffic [11].
 
16
Allowing different delays per client would open the possibility of free-riding and make anonymity analysis much more complex [12].
 
17
Non-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.
 
18
Because Alice must have already negotiated her mixing warranty for the next round, each warranty must be delayed by the maximum \(\delta _\text {max}\) blocks.
 
19
Note that the mixing fee rate \(\rho \) is unobservable and hence should have no impact on anonymity and can be chosen independently by different mixes.
 
20
For example, if chunk sizes \(\alpha \) and \(\beta \) are common, a user mixing \(x = k_1\alpha + k_2\beta \) will have her anonymity set limited to other users mixing at least \(k_1\) chunks of size \(\alpha \) and at least \(k_2\) of size \(\beta \), instead of all users mixing at least \(x\).
 
21
Additionally, with randomized mixing fees (see Sect. 4.4) users owning only a small multiple of \(v\) may face unacceptably high variance in their fee rate.
 
22
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.
 
23
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.
 
24
This is analogous to a packet counting attack in communication mixes.
 
25
This is analogous to an intersection attack in the mixing literature.
 
Literature
2.
go back to reference Androulaki, E., Karame, G.O., Roeschlin, M., Scherer, T., Capkun, S.: Evaluating user privacy in bitcoin. In: Sadeghi, A.-R. (ed.) FC 2013. LNCS, vol. 7859, pp. 34–51. Springer, Heidelberg (2013)CrossRef Androulaki, E., Karame, G.O., Roeschlin, M., Scherer, T., Capkun, S.: Evaluating user privacy in bitcoin. In: Sadeghi, A.-R. (ed.) FC 2013. LNCS, vol. 7859, pp. 34–51. Springer, Heidelberg (2013)CrossRef
3.
go back to reference Barber, S., Boyen, X., Shi, E., Uzun, E.: Bitter to better — how to make bitcoin a better currency. In: Keromytis, A.D. (ed.) FC 2012. LNCS, vol. 7397, pp. 399–414. Springer, Heidelberg (2012)CrossRef Barber, S., Boyen, X., Shi, E., Uzun, E.: Bitter to better — how to make bitcoin a better currency. In: Keromytis, A.D. (ed.) FC 2012. LNCS, vol. 7397, pp. 399–414. Springer, Heidelberg (2012)CrossRef
4.
go back to reference Ben-Sasson, E., Chiesa, A., Garman, C., Green, M., Miers, I., Tromer, E., Virza, M.: Zerocash: decentralized anonymous payments from Bitcoin. In: IEEE Symposium on Security and Privacy (SP), 2014. IEEE (2014) Ben-Sasson, E., Chiesa, A., Garman, C., Green, M., Miers, I., Tromer, E., Virza, M.: Zerocash: decentralized anonymous payments from Bitcoin. In: IEEE Symposium on Security and Privacy (SP), 2014. IEEE (2014)
5.
go back to reference Chaum, D.: Untraceable electronic mail, return addresses, and digital pseudonyms. Commun. ACM 24(2), 84–90 (1981)CrossRef Chaum, D.: Untraceable electronic mail, return addresses, and digital pseudonyms. Commun. ACM 24(2), 84–90 (1981)CrossRef
6.
go back to reference Chaum, D.: Blind signatures for untraceable payments. In: Chaum, D., Rivest, R.L., Sherman, A.T. (eds.) CRYPTO 1982, pp. 199–203. Springer, New York (1983)CrossRef Chaum, D.: Blind signatures for untraceable payments. In: Chaum, D., Rivest, R.L., Sherman, A.T. (eds.) CRYPTO 1982, pp. 199–203. Springer, New York (1983)CrossRef
7.
go back to reference Christin, N.: Traveling the silk road: a measurement analysis of a large anonymous online marketplace. In: Proceedings of the 22nd International Conference on World Wide Web, pp. 213–224. International World Wide Web Conferences Steering Committee (2013) Christin, N.: Traveling the silk road: a measurement analysis of a large anonymous online marketplace. In: Proceedings of the 22nd International Conference on World Wide Web, pp. 213–224. International World Wide Web Conferences Steering Committee (2013)
8.
go back to reference Clark, J., Hengartner, U.: On the use of financial data as a random beacon. In: Usenix EVT/WOTE (2010) Clark, J., Hengartner, U.: On the use of financial data as a random beacon. In: Usenix EVT/WOTE (2010)
9.
go back to reference Danezis, G., Fournet, C., Kohlweiss, M., Parno, B.: Pinocchio coin: building zerocoin from a succinct pairing-based proof system. In: Language Support for Privacy-Enhancing Technologies (PETShop) (2013) Danezis, G., Fournet, C., Kohlweiss, M., Parno, B.: Pinocchio coin: building zerocoin from a succinct pairing-based proof system. In: Language Support for Privacy-Enhancing Technologies (PETShop) (2013)
10.
go back to reference Dingledine, R., Mathewson, N.: Anonymity loves company: usability and the network effect. In: WEIS (2006) Dingledine, R., Mathewson, N.: Anonymity loves company: usability and the network effect. In: WEIS (2006)
11.
go back to reference Dingledine, R., Mathewson, N., Syverson, P.: Tor: The second-generation onion router. In: USENIX Security (2004) Dingledine, R., Mathewson, N., Syverson, P.: Tor: The second-generation onion router. In: USENIX Security (2004)
12.
go back to reference Dingledine, R., Serjantov, A., Syverson, P.F.: Blending different latency traffic with alpha-mixing. In: Danezis, G., Golle, P. (eds.) PET 2006. LNCS, vol. 4258, pp. 245–257. Springer, Heidelberg (2006)CrossRef Dingledine, R., Serjantov, A., Syverson, P.F.: Blending different latency traffic with alpha-mixing. In: Danezis, G., Golle, P. (eds.) PET 2006. LNCS, vol. 4258, pp. 245–257. Springer, Heidelberg (2006)CrossRef
13.
go back to reference Golle, P.: Reputable mix networks. In: Martin, D., Serjantov, A. (eds.) PET 2004. LNCS, vol. 3424, pp. 51–62. Springer, Heidelberg (2005)CrossRef Golle, P.: Reputable mix networks. In: Martin, D., Serjantov, A. (eds.) PET 2004. LNCS, vol. 3424, pp. 51–62. Springer, Heidelberg (2005)CrossRef
14.
go back to reference Jolly, G.M.: Explicit estimates from capture-recapture data with both death and immigration-stochastic model. Biometrika 52(1/2), 225–247 (1965)CrossRefMATHMathSciNet Jolly, G.M.: Explicit estimates from capture-recapture data with both death and immigration-stochastic model. Biometrika 52(1/2), 225–247 (1965)CrossRefMATHMathSciNet
15.
go back to reference Kesdogan, D., Egner, J., Büschkes, R.: Stop-and-go-mixes providing probabilistic anonymity in an open system. In: Aucsmith, D. (ed.) IH 1998. LNCS, vol. 1525, pp. 83–98. Springer, Heidelberg (1998)CrossRef Kesdogan, D., Egner, J., Büschkes, R.: Stop-and-go-mixes providing probabilistic anonymity in an open system. In: Aucsmith, D. (ed.) IH 1998. LNCS, vol. 1525, pp. 83–98. Springer, Heidelberg (1998)CrossRef
16.
go back to reference Kroll, J.A., Davey, I.C., Felten, E.W.: The economics of bitcoin mining, or bitcoin in the presence of adversaries. In: WEIS, June 2013 Kroll, J.A., Davey, I.C., Felten, E.W.: The economics of bitcoin mining, or bitcoin in the presence of adversaries. In: WEIS, June 2013
18.
go back to reference Maxwell, G.: CoinSwap: transaction graph disjoint trustless trading. CoinSwap:Transactiongraphdisjointtrustlesstrading (2013) Maxwell, G.: CoinSwap: transaction graph disjoint trustless trading. CoinSwap:Transactiongraphdisjointtrustlesstrading (2013)
19.
go back to reference Meiklejohn, S., Pomarole, M., Jordan, G., Levchenko, K., McCoy, D., Voelker, G.M., Savage, S.: A fistful of bitcoins: characterizing payments among men with no names. In: IMC (2013) Meiklejohn, S., Pomarole, M., Jordan, G., Levchenko, K., McCoy, D., Voelker, G.M., Savage, S.: A fistful of bitcoins: characterizing payments among men with no names. In: IMC (2013)
20.
go back to reference Miers, I., Garman, C., Green, M., Rubin, A.D.: Zerocoin: anonymous distributed e-cash from bitcoin. In: IEEE Symposium on Security and Privacy (2013) Miers, I., Garman, C., Green, M., Rubin, A.D.: Zerocoin: anonymous distributed e-cash from bitcoin. In: IEEE Symposium on Security and Privacy (2013)
21.
go back to reference Möser, M.: Anonymity of bitcoin transactions: an analysis of mixing services. In: Proceedings of Münster Bitcoin Conference (2013) Möser, M.: Anonymity of bitcoin transactions: an analysis of mixing services. In: Proceedings of Münster Bitcoin Conference (2013)
22.
go back to reference Nakamoto, S.: Bitcoin: a peer-to-peer electionic cash system (2008) Nakamoto, S.: Bitcoin: a peer-to-peer electionic cash system (2008)
23.
go back to reference Raymond, J.-F.: Traffic analysis: protocols, attacks, design issues, and open problems. In: Federrath, H. (ed.) Designing Privacy Enhancing Technologies. LNCS, vol. 2009, pp. 10–29. Springer, Heidelberg (2001)CrossRef Raymond, J.-F.: Traffic analysis: protocols, attacks, design issues, and open problems. In: Federrath, H. (ed.) Designing Privacy Enhancing Technologies. LNCS, vol. 2009, pp. 10–29. Springer, Heidelberg (2001)CrossRef
24.
go back to reference Reid, F., Harrigan, M.: An analysis of anonymity in the bitcoin system. In: Altshuler, Y., Elovici, Y., Cremers, A.B., Aharony, N., Pentland, A. (eds.) Security and Privacy in Social Networks, pp. 197–223. Springer, New York (2013)CrossRef Reid, F., Harrigan, M.: An analysis of anonymity in the bitcoin system. In: Altshuler, Y., Elovici, Y., Cremers, A.B., Aharony, N., Pentland, A. (eds.) Security and Privacy in Social Networks, pp. 197–223. Springer, New York (2013)CrossRef
25.
go back to reference Rivest, R.: Electronic lottery tickets as micropayments. In: Hirschfeld, R. (ed.) FC 1997. LNCS, vol. 1318, pp. 307–314. Springer, Heidelberg (1997)CrossRef Rivest, R.: Electronic lottery tickets as micropayments. In: Hirschfeld, R. (ed.) FC 1997. LNCS, vol. 1318, pp. 307–314. Springer, Heidelberg (1997)CrossRef
26.
go back to reference Ron, D., Shamir, A.: Quantitative analysis of the full bitcoin transaction graph. In: Sadeghi, A.-R. (ed.) FC 2013. LNCS, vol. 7859, pp. 6–24. Springer, Heidelberg (2013)CrossRef Ron, D., Shamir, A.: Quantitative analysis of the full bitcoin transaction graph. In: Sadeghi, A.-R. (ed.) FC 2013. LNCS, vol. 7859, pp. 6–24. Springer, Heidelberg (2013)CrossRef
27.
go back to reference Sako, K., Kilian, J.: Receipt-free mix-type voting scheme. In: Guillou, L.C., Quisquater, J.-J. (eds.) EUROCRYPT 1995. LNCS, vol. 921, pp. 393–403. Springer, Heidelberg (1995)CrossRef Sako, K., Kilian, J.: Receipt-free mix-type voting scheme. In: Guillou, L.C., Quisquater, J.-J. (eds.) EUROCRYPT 1995. LNCS, vol. 921, pp. 393–403. Springer, Heidelberg (1995)CrossRef
28.
go back to reference Serjantov, A., Dingledine, R., Syverson, P.: From a trickle to a flood: active attacks on several mix types. In: Petitcolas, F.A.P. (ed.) IH 2002. LNCS, vol. 2578, pp. 36–52. Springer, Heidelberg (2003)CrossRef Serjantov, A., Dingledine, R., Syverson, P.: From a trickle to a flood: active attacks on several mix types. In: Petitcolas, F.A.P. (ed.) IH 2002. LNCS, vol. 2578, pp. 36–52. Springer, Heidelberg (2003)CrossRef
Metadata
Title
Mixcoin: Anonymity for Bitcoin with Accountable Mixes
Authors
Joseph Bonneau
Arvind Narayanan
Andrew Miller
Jeremy Clark
Joshua A. Kroll
Edward W. Felten
Copyright Year
2014
Publisher
Springer Berlin Heidelberg
DOI
https://doi.org/10.1007/978-3-662-45472-5_31

Premium Partner