Document Open Access Logo

Tailstorm: A Secure and Fair Blockchain for Cash Transactions

Authors Patrik Keller, Ben Glickenhaus, George Bissias, Gregory Griffith

PDF
Thumbnail PDF

File

LIPIcs.AFT.2023.6.pdf
  • Filesize: 1.84 MB
  • 26 pages

Document Identifiers

Author Details

Patrik Keller
  • Universität Innsbruck, Austria
Ben Glickenhaus
  • University of Massachusetts Amherst, MA, USA
George Bissias
  • University of Massachusetts Amherst, MA, USA
Gregory Griffith
  • Bitcoin Unlimited

Funding

  • Bissias, George: Bitcoin Unlimited

Acknowledgements

We wish to thank Bitcoin Unlimited for their financial and technical support as well as Michael Fröwis for his review of this work and for the helpful suggestions he provided.

Cite As Get BibTex

Patrik Keller, Ben Glickenhaus, George Bissias, and Gregory Griffith. Tailstorm: A Secure and Fair Blockchain for Cash Transactions. In 5th Conference on Advances in Financial Technologies (AFT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 282, pp. 6:1-6:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.AFT.2023.6

Abstract

Proof-of-work (PoW) cryptocurrencies rely on a balance of security and fairness in order to maintain a sustainable ecosystem of miners and users. Users demand fast and consistent transaction confirmation, and in exchange drive the adoption and valuation of the cryptocurrency. Miners provide the confirmations, however, they primarily seek rewards. In unfair systems, miners can amplify their rewards by consolidating mining power. Centralization however, undermines the security guarantees of the system and might discourage users.
In this paper we present Tailstorm, a cryptocurrency that strikes this balance. Tailstorm merges multiple recent protocol improvements addressing security, confirmation latency, and throughput with a novel incentive mechanism improving fairness. We implement a parallel proof-of-work consensus mechanism with k PoWs per block to obtain state-of-the-art consistency guarantees [Patrik Keller and Rainer Böhme, 2022]. Inspired by Bobtail [George Bissias and Brian Neil Levine, 2020] and Storm [awemany, 2019], we structure the individual PoWs in a tree which, by including a list of transactions with each PoW, reduces confirmation latency and improves throughput. Our proposed incentive mechanism discounts rewards based on the depth of this tree. Thereby, it effectively punishes information withholding, the core attack strategy used to reap an unfair share of rewards.
We back our claims with a comprehensive analysis. We present a generic system model which allows us to specify Bitcoin, B_k [Patrik Keller and Rainer Böhme, 2022], and Tailstorm from a joint set of assumptions. We provide an analytical bound for the fairness of Tailstorm and Bitcoin in honest networks and we confirm the results through simulation. We evaluate the effectiveness of dishonest behaviour through reinforcement learning. Our attack search reproduces known optimal strategies against Bitcoin, uncovers new ones against B_k, and confirms that Tailstorm’s reward discounting makes it more resilient to incentive layer attacks. Our results are reproducible with the material provided online [Keller and Glickenhaus, 2023].
Lastly, we have implemented a prototype of the Tailstorm cryptocurrency as a fork of Bitcoin Cash. The client software is ready for testnet deployment and we also publish its source online [Griffith and Bissias, 2023].

Subject Classification

ACM Subject Classification
  • Security and privacy → Distributed systems security
Keywords
  • Proof-of-Work
  • Blockchain
  • Cryptocurrency
  • Mining Rewards
  • Fairness

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

Supplementary Materials

References

  1. Mohamed Alzayat, Johnnatan Messias, Balakrishnan Chandrasekaran, Krishna P. Gummadi, and Patrick Loiseau. Modeling coordinated vs. P2P mining: An analysis of inefficiency and inequality in proof-of-work blockchains. CoRR, abs/2106.02970, 2021. URL: https://arxiv.org/abs/2106.02970.
  2. Ignacio Amores-Sesar, Christian Cachin, and Anna Parker. Generalizing weighted trees: a bridge from bitcoin to GHOST. In Foteini Baldimtsi and Tim Roughgarden, editors, AFT '21: 3rd ACM Conference on Advances in Financial Technologies, Arlington, Virginia, USA, September 26 - 28, 2021, pages 156-169. ACM, 2021. URL: https://doi.org/10.1145/3479722.3480995.
  3. Nick Arnosti and S. Matthew Weinberg. Bitcoin: A natural oligopoly. Manag. Sci., 68(7):4755-4771, 2022. URL: https://doi.org/10.1287/mnsc.2021.4095.
  4. awemany. Storm. https://github.com/awemany/storm-sim/blob/master/whitepaper/, 2019.
  5. Vivek Kumar Bagaria, Sreeram Kannan, David Tse, Giulia Fanti, and Pramod Viswanath. Prism: Deconstructing the blockchain to approach physical limits. In Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz, editors, Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, CCS 2019, London, UK, November 11-15, 2019, pages 585-602. ACM, 2019. URL: https://doi.org/10.1145/3319535.3363213.
  6. Shehar Bano, Alberto Sonnino, Mustafa Al-Bassam, Sarah Azouvi, Patrick McCorry, Sarah Meiklejohn, and George Danezis. Sok: Consensus in the age of blockchains. In Proceedings of the 1st ACM Conference on Advances in Financial Technologies, AFT 2019, Zurich, Switzerland, October 21-23, 2019, pages 183-198. ACM, 2019. URL: https://doi.org/10.1145/3318041.3355458.
  7. Georgios Birmpas, Elias Koutsoupias, Philip Lazos, and Francisco J. Marmolejo Cossío. Fairness and efficiency in dag-based cryptocurrencies. In Joseph Bonneau and Nadia Heninger, editors, Financial Cryptography and Data Security - 24th International Conference, FC 2020, Kota Kinabalu, Malaysia, February 10-14, 2020 Revised Selected Papers, volume 12059 of Lecture Notes in Computer Science, pages 79-96. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-51280-4_6.
  8. George Bissias. Radium: Improving dynamic pow targeting. In Joaquín García-Alfaro, Guillermo Navarro-Arribas, and Jordi Herrera-Joancomartí, editors, Data Privacy Management, Cryptocurrencies and Blockchain Technology - ESORICS 2020 International Workshops, DPM 2020 and CBT 2020, Guildford, UK, September 17-18, 2020, Revised Selected Papers, volume 12484 of Lecture Notes in Computer Science, pages 374-389. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-66172-4_24.
  9. George Bissias and Brian Neil Levine. Bobtail: Improved blockchain security with low-variance mining. In 27th Annual Network and Distributed System Security Symposium, NDSS 2020, San Diego, California, USA, February 23-26, 2020. The Internet Society, 2020. URL: https://www.ndss-symposium.org/ndss-paper/bobtail-improved-blockchain-security-with-low-variance-mining/.
  10. Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. CoRR, abs/1606.01540, 2016. URL: https://arxiv.org/abs/1606.01540.
  11. Miles Carlsten, Harry A. Kalodner, S. Matthew Weinberg, and Arvind Narayanan. On the instability of bitcoin without the block reward. In Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi, editors, Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, October 24-28, 2016, pages 154-167. ACM, 2016. URL: https://doi.org/10.1145/2976749.2978408.
  12. Matt Corallo. BIP152: Compact Block Relay. https://github.com/bitcoin/ bips/blob/master/bip-0152.mediawiki, 2016. Google Scholar
  13. Francisco J. Marmolejo Cossío, Eric Brigham, Benjamin Sela, and Jonathan Katz. Competing (semi-)selfish miners in bitcoin. In Proceedings of the 1st ACM Conference on Advances in Financial Technologies, AFT 2019, Zurich, Switzerland, October 21-23, 2019, pages 89-109. ACM, 2019. URL: https://doi.org/10.1145/3318041.3355471.
  14. Sergi Delgado-Segura, Surya Bakshi, Cristina Pérez-Solà, James Litton, Andrew Pachulski, Andrew Miller, and Bobby Bhattacharjee. Txprobe: Discovering bitcoin’s network topology using orphan transactions. In Ian Goldberg and Tyler Moore, editors, Financial Cryptography and Data Security - 23rd International Conference, FC 2019, Frigate Bay, St. Kitts and Nevis, February 18-22, 2019, Revised Selected Papers, volume 11598 of Lecture Notes in Computer Science, pages 550-566. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-32101-7_32.
  15. Amir Dembo, Sreeram Kannan, Ertem Nusret Tas, David Tse, Pramod Viswanath, Xuechao Wang, and Ofer Zeitouni. Everything is a race and nakamoto always wins. In Jay Ligatti, Xinming Ou, Jonathan Katz, and Giovanni Vigna, editors, CCS '20: 2020 ACM SIGSAC Conference on Computer and Communications Security, Virtual Event, USA, November 9-13, 2020, pages 859-878. ACM, 2020. URL: https://doi.org/10.1145/3372297.3417290.
  16. Ittay Eyal and Emin Gün Sirer. Majority is not enough: Bitcoin mining is vulnerable. In Nicolas Christin and Reihaneh Safavi-Naini, editors, Financial Cryptography and Data Security - 18th International Conference, FC 2014, Christ Church, Barbados, March 3-7, 2014, Revised Selected Papers, volume 8437 of Lecture Notes in Computer Science, pages 436-454. Springer, 2014. URL: https://doi.org/10.1007/978-3-662-45472-5_28.
  17. Chen Feng and Jianyu Niu. Selfish mining in ethereum. In 39th IEEE International Conference on Distributed Computing Systems, ICDCS 2019, Dallas, TX, USA, July 7-10, 2019, pages 1306-1316. IEEE, 2019. URL: https://doi.org/10.1109/ICDCS.2019.00131.
  18. Daniel Fullmer and A. Stephen Morse. Analysis of difficulty control in bitcoin and proof-of-work blockchains. In 57th IEEE Conference on Decision and Control, CDC 2018, Miami, FL, USA, December 17-19, 2018, pages 5988-5992. IEEE, 2018. URL: https://doi.org/10.1109/CDC.2018.8619082.
  19. Juan A. Garay and Aggelos Kiayias. Sok: A consensus taxonomy in the blockchain era. In Stanislaw Jarecki, editor, Topics in Cryptology - CT-RSA 2020 - The Cryptographers' Track at the RSA Conference 2020, San Francisco, CA, USA, February 24-28, 2020, Proceedings, volume 12006 of Lecture Notes in Computer Science, pages 284-318. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-40186-3_13.
  20. Juan A. Garay, Aggelos Kiayias, and Nikos Leonardos. The bitcoin backbone protocol: Analysis and applications. In Elisabeth Oswald and Marc Fischlin, editors, Advances in Cryptology - EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26-30, 2015, Proceedings, Part II, volume 9057 of Lecture Notes in Computer Science, pages 281-310. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-46803-6_10.
  21. Arthur Gervais, Ghassan O. Karame, Karl Wüst, Vasileios Glykantzis, Hubert Ritzdorf, and Srdjan Capkun. On the security and performance of proof of work blockchains. In Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi, editors, Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, October 24-28, 2016, pages 3-16. ACM, 2016. URL: https://doi.org/10.1145/2976749.2978341.
  22. Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos, and Nickolai Zeldovich. Algorand: Scaling byzantine agreements for cryptocurrencies. In Proceedings of the 26th Symposium on Operating Systems Principles, Shanghai, China, October 28-31, 2017, pages 51-68. ACM, 2017. URL: https://doi.org/10.1145/3132747.3132757.
  23. Greg Griffith and George Bissias. Tailstorm node implementation. https://gitlab.com/georgebissias/BCHUnlimited/-/tree/tailstorm_prototype, 2023.
  24. Dongning Guo and Ling Ren. Bitcoin’s latency-security analysis made simple. In Maurice Herlihy and Neha Narula, editors, Proceedings of the 4th ACM Conference on Advances in Financial Technologies, AFT 2022, Cambridge, MA, USA, September 19-21, 2022, pages 244-253. ACM, 2022. URL: https://doi.org/10.1145/3558535.3559791.
  25. Thomas M. Harding. Real-time block rate targeting. Ledger, 5, 2020. URL: https://doi.org/10.5195/ledger.2020.195.
  26. Charlie Hou, Mingxun Zhou, Yan Ji, Phil Daian, Florian Tramèr, Giulia Fanti, and Ari Juels. Squirrl: Automating attack analysis on blockchain incentive mechanisms with deep reinforcement learning. In 28th Annual Network and Distributed System Security Symposium, NDSS 2021, virtually, February 21-25, 2021. The Internet Society, 2021. URL: https://www.ndss-symposium.org/ndss-paper/squirrl-automating-attack-analysis-on-blockchain-incentive-mechanisms-with-deep-reinforcement-learning/.
  27. Geir Hovland and Jan Kucera. Nonlinear feedback control and stability analysis of a proof-of-work blockchain. Modeling, Identification and Control, 38(4):157-168, 2017. URL: https://doi.org/10.4173/mic.2017.4.1.
  28. Patrik Keller. PyPI release of our reinforcement learning environment as OpenAI Gym. https://pypi.org/project/cpr-gym/0.7.0/, 2023.
  29. Patrik Keller and Rainer Böhme. Parallel proof-of-work with concrete bounds. In Maurice Herlihy and Neha Narula, editors, Proceedings of the 4th ACM Conference on Advances in Financial Technologies, AFT 2022, Cambridge, MA, USA, September 19-21, 2022, pages 1-15. ACM, 2022. URL: https://doi.org/10.1145/3558535.3559773.
  30. Patrik Keller and Ben Glickenhaus. Source code for our simulator, evaluations, and attack search. https://github.com/pkel/cpr/tree/aft23, 2023.
  31. Aggelos Kiayias, Elias Koutsoupias, Maria Kyropoulou, and Yiannis Tselekounis. Blockchain mining games. In Vincent Conitzer, Dirk Bergemann, and Yiling Chen, editors, Proceedings of the 2016 ACM Conference on Economics and Computation, EC '16, Maastricht, The Netherlands, July 24-28, 2016, pages 365-382. ACM, 2016. URL: https://doi.org/10.1145/2940716.2940773.
  32. Aggelos Kiayias, Alexander Russell, Bernardo David, and Roman Oliynykov. Ouroboros: A provably secure proof-of-stake blockchain protocol. In Jonathan Katz and Hovav Shacham, editors, Advances in Cryptology - CRYPTO 2017 - 37th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 20-24, 2017, Proceedings, Part I, volume 10401 of Lecture Notes in Computer Science, pages 357-388. Springer, 2017. URL: https://doi.org/10.1007/978-3-319-63688-7_12.
  33. Lucianna Kiffer and Rajmohan Rajaraman. Happy-mine: Designing a mining reward function. In Nikita Borisov and Claudia Díaz, editors, Financial Cryptography and Data Security - 25th International Conference, FC 2021, Virtual Event, March 1-5, 2021, Revised Selected Papers, Part II, volume 12675 of Lecture Notes in Computer Science, pages 250-268. Springer, 2021. URL: https://doi.org/10.1007/978-3-662-64331-0_13.
  34. Lucianna Kiffer, Rajmohan Rajaraman, and Abhi Shelat. A better method to analyze blockchain consistency. In David Lie, Mohammad Mannan, Michael Backes, and XiaoFeng Wang, editors, Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, CCS 2018, Toronto, ON, Canada, October 15-19, 2018, pages 729-744. ACM, 2018. URL: https://doi.org/10.1145/3243734.3243814.
  35. Daniel Kraft. Difficulty control for blockchain-based consensus systems. Peer-to-Peer Netw. Appl., 9(2):397-413, 2016. URL: https://doi.org/10.1007/s12083-015-0347-x.
  36. Yujin Kwon, Jian Liu, Minjeong Kim, Dawn Song, and Yongdae Kim. Impossibility of full decentralization in permissionless blockchains. In Proceedings of the 1st ACM Conference on Advances in Financial Technologies, AFT 2019, Zurich, Switzerland, October 21-23, 2019, pages 110-123. ACM, 2019. URL: https://doi.org/10.1145/3318041.3355463.
  37. Jing Li, Dongning Guo, and Ling Ren. Close latency-security trade-off for the nakamoto consensus. In Foteini Baldimtsi and Tim Roughgarden, editors, AFT '21: 3rd ACM Conference on Advances in Financial Technologies, Arlington, Virginia, USA, September 26 - 28, 2021, pages 100-113. ACM, 2021. URL: https://doi.org/10.1145/3479722.3480992.
  38. Sami Ben Mariem, Pedro Casas, Matteo Romiti, Benoit Donnet, Rainer Stütz, and Bernhard Haslhofer. All that glitters is not bitcoin - unveiling the centralized nature of the BTC (IP) network. In NOMS 2020 - IEEE/IFIP Network Operations and Management Symposium, Budapest, Hungary, April 20-24, 2020, pages 1-9. IEEE, 2020. URL: https://doi.org/10.1109/NOMS47738.2020.9110354.
  39. Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system. https://bitcoin.org/bitcoin.pdf, 2008.
  40. Kevin Alarcón Negy, Peter R. Rizun, and Emin Gün Sirer. Selfish mining re-examined. In Joseph Bonneau and Nadia Heninger, editors, Financial Cryptography and Data Security - 24th International Conference, FC 2020, Kota Kinabalu, Malaysia, February 10-14, 2020 Revised Selected Papers, volume 12059 of Lecture Notes in Computer Science, pages 61-78. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-51280-4_5.
  41. A. Pinar Ozisik, Gavin Andresen, Brian Neil Levine, Darren Tapp, George Bissias, and Sunny Katkuri. Graphene: efficient interactive set reconciliation applied to blockchain propagation. In Jianping Wu and Wendy Hall, editors, Proceedings of the ACM Special Interest Group on Data Communication, SIGCOMM 2019, Beijing, China, August 19-23, 2019, pages 303-317. ACM, 2019. URL: https://doi.org/10.1145/3341302.3342082.
  42. Rafael Pass and Elaine Shi. Fruitchains: A fair blockchain. In Elad Michael Schiller and Alexander A. Schwarzmann, editors, Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2017, Washington, DC, USA, July 25-27, 2017, pages 315-324. ACM, 2017. URL: https://doi.org/10.1145/3087801.3087809.
  43. Peter R. Rizun. Subchains: A technique to scale bitcoin and improve the user experience. Ledger, 1:38-52, 2016. URL: https://ledgerjournal.org/ojs/index.php/ledger/article/view/40.
  44. Elias Rohrer and Florian Tschorsch. Kadcast: A structured approach to broadcast in blockchain networks. In Proceedings of the 1st ACM Conference on Advances in Financial Technologies, AFT 2019, Zurich, Switzerland, October 21-23, 2019, pages 199-213. ACM, 2019. URL: https://doi.org/10.1145/3318041.3355469.
  45. Elias Rohrer and Florian Tschorsch. Blockchain layer zero: Characterizing the bitcoin network through measurements, models, and simulations. In 46th IEEE Conference on Local Computer Networks, LCN 2021, Edmonton, AB, Canada, October 4-7, 2021, pages 9-16. IEEE, 2021. URL: https://doi.org/10.1109/LCN52139.2021.9524930.
  46. Sheldon M. Ross. Introduction to Probability Models. Elsevier, 2014. URL: https://doi.org/10.1016/C2012-0-03564-8.
  47. Ayelet Sapirshtein, Yonatan Sompolinsky, and Aviv Zohar. Optimal selfish mining strategies in bitcoin. In Jens Grossklags and Bart Preneel, editors, Financial Cryptography and Data Security - 20th International Conference, FC 2016, Christ Church, Barbados, February 22-26, 2016, Revised Selected Papers, volume 9603 of Lecture Notes in Computer Science, pages 515-532. Springer, 2016. URL: https://doi.org/10.1007/978-3-662-54970-4_30.
  48. John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. CoRR, abs/1707.06347, 2017. URL: https://arxiv.org/abs/1707.06347.
  49. Jakub Sliwinski and Roger Wattenhofer. Asynchronous proof-of-stake. In Colette Johnen, Elad Michael Schiller, and Stefan Schmid, editors, Stabilization, Safety, and Security of Distributed Systems - 23rd International Symposium, SSS 2021, Virtual Event, November 17-20, 2021, Proceedings, volume 13046 of Lecture Notes in Computer Science, pages 194-208. Springer, 2021. URL: https://doi.org/10.1007/978-3-030-91081-5_13.
  50. Yonatan Sompolinsky, Shai Wyborski, and Aviv Zohar. PHANTOM GHOSTDAG: a scalable generalization of nakamoto consensus: September 2, 2021. In Foteini Baldimtsi and Tim Roughgarden, editors, AFT '21: 3rd ACM Conference on Advances in Financial Technologies, Arlington, Virginia, USA, September 26 - 28, 2021, pages 57-70. ACM, 2021. URL: https://doi.org/10.1145/3479722.3480990.
  51. Yonatan Sompolinsky and Aviv Zohar. Secure high-rate transaction processing in bitcoin. In Rainer Böhme and Tatsuaki Okamoto, editors, Financial Cryptography and Data Security - 19th International Conference, FC 2015, San Juan, Puerto Rico, January 26-30, 2015, Revised Selected Papers, volume 8975 of Lecture Notes in Computer Science, pages 507-527. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-47854-7_32.
  52. Aviv Yaish and Aviv Zohar. Pricing ASICs for cryptocurrency mining. In Proceedings of the 5th ACM Conference on Advances in Financial Technologies, AFT 2022, Princeton, NJ, USA, October 21-25, 2023. LIPIcs, 2023. Google Scholar
  53. Haifeng Yu, Ivica Nikolic, Ruomu Hou, and Prateek Saxena. OHIE: blockchain scaling made simple. In 2020 IEEE Symposium on Security and Privacy, SP 2020, San Francisco, CA, USA, May 18-21, 2020, pages 90-105. IEEE, 2020. URL: https://doi.org/10.1109/SP40000.2020.00008.
  54. Ren Zhang and Bart Preneel. Lay down the common metrics: Evaluating proof-of-work consensus protocols' security. In 2019 IEEE Symposium on Security and Privacy, SP 2019, San Francisco, CA, USA, May 19-23, 2019, pages 175-192. IEEE, 2019. URL: https://doi.org/10.1109/SP.2019.00086.
  55. Roi Bar Zur, Ittay Eyal, and Aviv Tamar. Efficient MDP analysis for selfish-mining in blockchains. In AFT '20: 2nd ACM Conference on Advances in Financial Technologies, New York, NY, USA, October 21-23, 2020, pages 113-131. ACM, 2020. URL: https://doi.org/10.1145/3419614.3423264.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact