Document Open Access Logo

Colordag: An Incentive-Compatible Blockchain

Authors Ittai Abraham, Danny Dolev, Ittay Eyal, Joseph Y. Halpern

PDF

File

Thumbnail PDF
PDF
LIPIcs.DISC.2023.1.pdf
  • Filesize: 0.71 MB
  • 22 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Computing methodologies → Distributed computing methodologies
  • Theory of computation → Solution concepts in game theory
  • Security and privacy → Distributed systems security
Keywords
  • Game theory
  • incentives
  • blockchain

Metrics

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

Abstract

We present Colordag, a blockchain protocol where following the prescribed strategy is, with high probability, a best response as long as all miners have less than 1/2 of the mining power. We prove the correctness of Colordag even if there is an extremely powerful adversary who knows future actions of the scheduler: specifically, when agents will generate blocks and when messages will arrive. The state-of-the-art protocol, Fruitchain, is an ε-Nash equilibrium as long as all miners have less than 1/2 of the mining power. However, there is a simple deviation that guarantees that deviators are never worse off than they would be by following Fruitchain, and can sometimes do better. Thus, agents are motivated to deviate. Colordag implements a solution concept that we call ε-sure Nash equilibrium and does not suffer from this problem. Because it is an ε-sure Nash equilibrium, Colordag is an ε-Nash equilibrium and with probability 1-ε is a best response.

Cite As Get BibTex

Ittai Abraham, Danny Dolev, Ittay Eyal, and Joseph Y. Halpern. Colordag: An Incentive-Compatible Blockchain. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 1:1-1:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.DISC.2023.1

Author Details

Ittai Abraham
  • Intel Labs, Haifa, Israel
Danny Dolev
  • The Hebrew University of Jerusalem, Israel
Ittay Eyal
  • Technion, Haifa, Israel
Joseph Y. Halpern
  • Cornell University, Ithaca, NY, USA

Funding

  • Dolev, Danny: Supported by the Federmann Cyber-Security Center in conjunction with the Israel National Cyber Directorate.
  • Eyal, Ittay: Supported by the Israel Science Foundation (grant No. 1641/18), Avalanche Foundation, and IC3.
  • Halpern, Joseph Y.: Supported in part by AFOSR grant FA23862114029, MURI grant W911NF-19-1-0217, ARO grant W911NF-22-1-0061, and a grant from the Algorand Centers of Excellence program managed by the Algorand Foundation.

Acknowledgements

We thank Roi Bar-Zur for comments on an early version of this manuscript, and the reviewers of the paper for their helpful comments.

References

  1. Adam Back. Hashcash - a denial of service counter-measure. http://www.cypherspace.org/hashcash/hashcash.pdf, 2002.
  2. Vivek Bagaria, Sreeram Kannan, David Tse, Giulia Fanti, and Pramod Viswanath. Prism: Deconstructing the blockchain to approach physical limits. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, pages 585-602, 2019. Google Scholar
  3. Roi Bar-Zur, Ameer Abu-Hanna, Ittay Eyal, and Aviv Tamar. Werlman: To tackle whale (transactions), go deep (RL). In IEEE Symposium on Security and Privacy (SP), 2022. Google Scholar
  4. Roi Bar-Zur, Danielle Dori, Sharon Vardi, Ittay Eyal, and Aviv Tamar. Deep bribe: Predicting the rise of bribery in blockchain mining with deep RL. In 6th workshop on Deep Learning Security and Privacy (DLSP), 2023. Google Scholar
  5. Roi Bar Zur, Ittay Eyal, and Aviv Tamar. Efficient MDP analysis for selfish-mining in blockchains. In 2nd ACM Conference on Advances in Financial Technologies (AFT), 2020. Google Scholar
  6. Reinhard Diestel. Graph Theory. Springer Graduate Texts in Mathematics. Springer-Verlag, 5th edition, 2017. Google Scholar
  7. Cynthia Dwork and Moni Naor. Pricing via processing or combatting junk mail. In Proceedings CRYPTO '92: 12th International Cryptology Conference, pages 139-147. Springer, 1992. Google Scholar
  8. Ittay Eyal and Emin Gün Sirer. Majority is not enough: Bitcoin mining is vulnerable. In Financial Cryptography and Data Security, 2014. Google Scholar
  9. Matheus V. X. Ferreira and S. Matthew Weinberg. Proof-of-stake mining games with perfect randomness. In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 433-453, 2021. Google Scholar
  10. Juan A. Garay, Aggelos Kiayias, and Nikos Leonardos. The Bitcoin backbone protocol: Analysis and applications. In Advances in Cryptology - EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 281-310, 2015. URL: https://doi.org/10.1007/978-3-662-46803-6_10.
  11. Charlie Hou, Mingxun Zhou, Yan Ji, Phil Daian, Florian Tramer, Giulia Fanti, and Ari Juels. Squirrl: Automating attack discovery on blockchain incentive mechanisms with deep reinforcement learning. arXiv:1912.01798, 2019. Google Scholar
  12. Markus Jakobsson and Ari Juels. Proofs of work and bread pudding protocols. In Secure Information Networks, pages 258-272. Springer, 1999. Google Scholar
  13. Lucianna Kiffer, Rajmohan Rajaraman, and Abhi Shelat. A better method to analyze blockchain consistency. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pages 729-744, 2018. Google Scholar
  14. Yoad Lewenberg, Yonatan Sompolinsky, and Aviv Zohar. Inclusive block chain protocols. In Financial Cryptography, Puerto Rico, 2015. Google Scholar
  15. Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system. http://www.bitcoin.org/bitcoin.pdf, 2008.
  16. Kartik Nayak, Srijan Kumar, Andrew Miller, and Elaine Shi. Stubborn mining: Generalizing selfish mining and combining with an eclipse attack. IACR Cryptology ePrint Archive, 2015:796, 2015. URL: http://eprint.iacr.org/2015/796.
  17. Rafael Pass, Lior Seeman, and Abhi Shelat. Analysis of the blockchain protocol in asynchronous networks. Technical report, Cryptology ePrint Archive, Report 2016/454, 2016. Google Scholar
  18. Rafael Pass and Elaine Shi. Fruitchains: A fair blockchain. In Proceedings of the ACM Symposium on Principles of Distributed Computing, pages 315-324, 2017. Google Scholar
  19. Ayelet Sapirshtein, Yonatan Sompolinsky, and Aviv Zohar. Optimal selfish mining strategies in Bitcoin. In Financial Cryptography and Data Security, 2016. Google Scholar
  20. R. Sedgewick and K. Wayne. Algorithms. Addison-Wesley, fourth edition, 2011. Google Scholar
  21. Jakub Sliwinski and Roger Wattenhofer. Blockchains cannot rely on honesty. https://disco.ethz.ch/courses/distsys/lnotes/rational%20blockchain%20paper.pdf, 2019.
  22. Yonatan Sompolinsky, Shai Wyborski, and Aviv Zohar. Phantom ghostdag: a scalable generalization of nakamoto consensus. In Proceedings of the 3rd ACM Conference on Advances in Financial Technologies, pages 57-70, 2021. Google Scholar
  23. Gavin Wood. Ethereum yellow paper. https://web.archive.org/web/20160820211734/http://gavwood.com/Paper.pdf, 2015.
  24. H. Yu, Nikolić I., R. Hou, and P. Saxena. Ohie: Blockchain scaling made simple. In 2020 IEEE Symposium on Security and Privacy (SOSP), 2020. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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