Dandelion: Redesigning the Bitcoin Network for Anonymity

Abstract

Bitcoin and other cryptocurrencies have surged in popularity over the last decade. Although Bitcoin does not claim to provide anonymity for its users, it enjoys a public perception of being a privacy preserving financial system. In reality, cryptocurrencies publish users' entire transaction histories in plaintext, albeit under a pseudonym; this is required for transaction validation. Therefore, if a user's pseudonym can be linked to their human identity, the privacy fallout can be significant. Recently, researchers have demonstrated deanonymization attacks that exploit weaknesses in the Bitcoin network's peer-to-peer (P2P) networking protocols. In particular, the P2P network currently forwards content in a structured way that allows observers to deanonymize users. In this work, we redesign the P2P network from first principles with the goal of providing strong, provable anonymity guarantees. We propose a simple networking policy called Dandelion which provides quasi-optimal, network-wide anonymity, with minimal cost to the network's utility. We also discuss practical implementation challenges and propose heuristic solutions.

References

1. 2016. Bitcoin Core integration/staging tree. (2016). https://github.com/bitcoin/bitcoin.
2. 2016. ZCash. (2016). https://z.cash/.
3. Elli Androulaki, Ghassan O Karame, Marc Roeschlin, Tobias Scherer, and Srdjan Capkun. 2013. Evaluating user privacy in bitcoin. In International Conference on Financial Cryptography and Data Security. Springer, 34--51.
4. Maria Apostolaki, Aviv Zohar, and Laurent Vanbever. 2016. Hijacking Bitcoin: Large-scale Network Attacks on Cryptocurrencies. arXiv preprint arXiv:1605.07524 (2016).
5. Yossi Azar, Andrei Broder, Anna Karlin, and Eli Upfal. 1999. Balanced Allocations. SIAM Journal of Computing 29, 1 (1999), 180--200.
6. MS Bartlett. 1956. Deterministic and stochastic models for recurrent epidemics. In Proceedings of the third Berkeley symposium on mathematical statistics and probability, Vol. 4. 109.
7. Mohsen Bayati, Devavrat Shah, and Mayank Sharma. 2008. Max-product for maximum weight matching: Convergence, correctness, and LP duality. IEEE Transactions on Information Theory 54, 3 (2008), 1241--1251.
8. Alex Biryukov, Dmitry Khovratovich, and Ivan Pustogarov. 2014. Deanonymisation of clients in Bitcoin P2P network. In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security. ACM, 15--29
9. Alex Biryukov and Ivan Pustogarov. 2015. Bitcoin over Tor isn't a good idea. In 2015 IEEE Symposium on Security and Privacy. IEEE, 122--134.
10. Bitnodes. 2016. Global Bitcoin Nodes Distribution. (2016).
11. Blockchain.info. 2016. Confirmed Transactions Per Day. (2016).
12. Joseph Bonneau, Arvind Narayanan, Andrew Miller, Jeremy Clark, Joshua A Kroll, and Edward W Felten. 2014. Mixcoin: Anonymity for Bitcoin with accountable mixes. In International Conference on Financial Cryptography and Data Security. Springer, 486--504.
13. D. Chaum. 1988. The dining cryptographers problem: Unconditional sender and recipient untraceability. Journal of cryptology 1, 1 (1988).
14. CoinMarketCap. 2016. Cryptocurrency Market Capitalizations. (2016).
15. H. Corrigan-Gibbs and B. Ford. 2010. Dissent: accountable anonymous group messaging. In CCS. ACM.
16. Dancho Danchev. 2013. New underground service offers access to thousands of malware-infected hosts. (2013).
17. Christian Decker and Roger Wattenhofer. 2013. Information propagation in the bitcoin network. In IEEE P2P 2013 Proceedings. IEEE, 1--10.
18. R. Dingledine, N. Mathewson, and P. Syverson. 2004. Tor: The second-generation onion router. Technical Report. DTIC Document.
19. G. Fanti, P. Kairouz, S. Oh, and P. Viswanath. 2015. Spy vs. Spy: Rumor Source Obfuscation. In SIGMETRICS Perform. Eval. Rev., Vol. 43. 271--284. Issue 1.
20. V. Fioriti and M. Chinnici. 2012. Predicting the sources of an outbreak with a spectral technique. arXiv:1211.2333 (2012).
21. M.J. Freedman and R. Morris. 2002. Tarzan: A peer-to-peer anonymizing network layer. In Proc. CCS. ACM.
22. Zvi Galil. 1986. Efficient algorithms for finding maximum matching in graphs. ACM Computing Surveys (CSUR) 18, 1 (1986), 23--38.
23. Michael R Garey, David S. Johnson, and R Endre Tarjan. 1976. The planar Hamiltonian circuit problem is NP-complete. SIAM J. Comput. 5, 4 (1976), 704--714.
24. P. Golle and A. Juels. 2004. Dining cryptographers revisited. In Advances in Cryptology-Eurocrypt 2004.
25. Ethan Heilman, Leen Alshenibr, Foteini Baldimtsi, Alessandra Scafuro, and Sharon Goldberg. 2016. TumbleBit: An untrusted Bitcoin- compatible anonymous payment hub. Technical Report. Cryptology ePrint Archive, Report 2016/575.
26. TE Jedusor. 2016. Mimblewimble. (2016).
27. Norman Lloyd Johnson and Samuel Kotz. 1977. Urn models and their application; an approach to modern discrete probability theory. (1977).
28. David Karger, Rajeev Motwani, and GDS Ramkumar. 1997. On approximating the longest path in a graph. Algorithmica 18, 1 (1997), 82--98.
29. Joohwan Kim and R Srikant. 2012. Peer-to-peer streaming over dynamic random Hamilton cycles. In Information Theory and Applications Workshop (ITA), 2012. IEEE, 415--419.
30. Philip Koshy. 2013. CoinSeer: A Telescope Into Bitcoin. Ph.D. Dissertation. The Pennsylvania State University.
31. Philip Koshy, Diana Koshy, and Patrick McDaniel. 2014. An analysis of anonymity in bitcoin using p2p network traffic. In International Conference on Financial Cryptography and Data Security. Springer, 469--485.
32. Eythan Levy, Guy Louchard, and Jordi Petit. 2004. A Distributed Algorithm to Find Hamiltonian Cycles in G(n, p) Random Graphs. In Workshop on Combinatorial and Algorithmic aspects of networking. Springer, 63--74.
33. A. Y. Lokhov, M. Mézard, H. Ohta, and L. Zdeborová. 2013. Inferring the origin of an epidemic with dynamic message passing algorithm. arXiv preprint arXiv:1303.5315 (2013).
34. Eran Makover and Jeffrey McGowan. 2006. Regular trees in random regular graphs. arXiv preprint math/0610858 (2006).
35. Greg Maxwell. 2013. CoinJoin: Bitcoin privacy for the real world. In Post on Bitcoin Forum.
36. Sarah Meiklejohn, Marjori Pomarole, Grant Jordan, Kirill Levchenko, Damon McCoy, Geoffrey M Voelker, and Stefan Savage. 2013. A fistful of bitcoins: characterizing payments among men with no names. In Proceedings of the 2013 conference on Internet measurement conference. ACM, 127--140.
37. Ian Miers, Christina Garman, Matthew Green, and Aviel D Rubin. 2013. Zerocoin: Anonymous distributed e-cash from bitcoin. In Security and Privacy (SP), 2013 IEEE Symposium on. IEEE, 397--411.
38. Andrew Miller, James Litton, Andrew Pachulski, Neal Gupta, Dave Levin, Neil Spring, and Bobby Bhattacharjee. 2015. Discovering Bitcoin's public topology and influential nodes. (2015).
39. Michael Mitzenmacher. 2001. The power of two choices in randomized load balancing. IEEE Transactions on Parallel and Distributed Systems 12, 10 (2001), 1094--1104.
40. Satoshi Nakamoto. 2008. Bitcoin: A peer-to-peer electronic cash system. (2008).
41. Micha Ober, Stefan Katzenbeisser, and Kay Hamacher. 2013. Structure and anonymity of the bitcoin transaction graph. Future internet 5, 2 (2013), 237--250.
42. P. C. Pinto, P. Thiran, and M. Vetterli. 2012. Locating the source of diffusion in large-scale networks. Physical review letters 109, 6 (2012), 068702.
43. Daniel Plohmann and Elmar Gerhards-Padilla. 2012. Case study of the miner botnet. In 2012 4th International Conference on Cyber Conflict (CYCON 2012). IEEE, 1--16.
44. David Martin Powers. 2011. Evaluation: from precision, recall and F-measure to ROC, informedness, markedness and correlation. (2011).
45. B. A. Prakash, J. Vreeken, and C. Faloutsos. 2012. Spotting culprits in epidemics: How many and which ones?. In ICDM, Vol. 12. 11--20.
46. Fergal Reid and Martin Harrigan. 2013. An analysis of anonymity in the bitcoin system. In Security and privacy in social networks. Springer, 197--223.
47. Michael K Reiter and Aviel D Rubin. 1998. Crowds: Anonymity for web transactions. ACM Transactions on Information and System Security (TISSEC) 1, 1 (1998), 66--92.
48. Dorit Ron and Adi Shamir. 2013. Quantitative analysis of the full bitcoin transaction graph. In International Conference on Financial Cryptography and Data Security. Springer, 6--24.
49. Tim Ruffing, Pedro Moreno-Sanchez, and Aniket Kate. 2014. CoinShuffle: Practical decentralized coin mixing for Bitcoin. In European Symposium on Research in Computer Security. Springer, 345--364.
50. Eli Ben Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, and Madars Virza. 2014. Zerocash: Decentralized anonymous payments from bitcoin. In 2014 IEEE Symposium on Security and Privacy. IEEE, 459--474.
51. Fabrizio Sebastiani. 2002. Machine learning in automated text categorization. ACM computing surveys (CSUR) 34, 1 (2002), 1--47.
52. D. Shah and T. Zaman. 2011. Rumors in a Network: Who's the Culprit? Information Theory, IEEE Transactions on 57 (Aug 2011), 5163--5181. Issue 8.
53. D. Shah and T. Zaman. 2012. Rumor centrality: a universal source detector. In ACM SIGMETRICS Performance Evaluation Review, Vol. 40. ACM, 199--210. Issue 1.
54. SéRgio SC Silva, Rodrigo MP Silva, Raquel CG Pinto, and Ronaldo M Salles. 2013. Botnets: A survey. Computer Networks 57, 2 (2013), 378--403.
55. Z. Wang, W. Dong, W. Zhang, and C.W. Tan. 2014. Rumor Source Detection with Multiple Observations: Fundamental Limits and Algorithms. In ACM SIGMETRICS.
56. David Isaac Wolinsky, Henry Corrigan-Gibbs, Bryan Ford, and Aaron Johnson. 2012. Dissent in Numbers: Making Strong Anonymity Scale.. In OSDI. 179--182.
57. K. Zhu, Z. Chen, and L. Ying. 2014. Locating Contagion Sources in Networks with Partial Timestamps. arXiv preprint arXiv:1412.4141 (2014).
58. K. Zhu and L. Ying. 2013. A Robust Information Source Estimator with Sparse Observations. arXiv preprint arXiv:1309.4846 (2013).

Index Terms

• Information systems

  • World Wide Web

    • Web applications

      • Electronic commerce

        • Digital cash

• Networks

  • Network properties

    • Network privacy and anonymity

    • Network structure

      • Topology analysis and generation

  • Network protocols

    • Application layer protocols

      • Peer-to-peer protocols

  • Network types

    • Overlay and other logical network structures

      • Peer-to-peer networks