The Greedy Miner’s Dilemma: Flaws in DAG-Based Consensus Protocols

Table of Links

Abstract and I. Introduction

II. Background

III. Problem Definition

IV. DAG-Oriented Solutions

V. Game Theoretical Analysis

VI. Simulation Model

VII. Evaluation

VIII. Countermeasures

IX. Discussion and Future Work

X. Related Work

XI. Conclusion and References

XI. CONCLUSION

In this work, we started with an overview of DAG-oriented consensus protocols for Proof-of-Work blockchains, which promise to increase the transaction throughput by using random transaction selection strategy. We formulated a hypothesis that DAG protocols using the random strategy can be exploited by attackers not respecting such a strategy and instead selecting transaction based on the fees (i.e., greedy strategy), which can lead to deterioration of the overall transaction throughput. We made a game theoretical analysis of concerned DAG-oriented protocols and concluded that the random strategy, as proposed in these protocols, does not constitute a Nash equilibrium since honest players enable the greedy player to “parasite” on the system. This is contradictory result to Inclusive paper [26], which does not assume that multiple greedy miners can form a mining pool.

We conducted several experiments on simplified network topology as well as complex network using an abstracted DAG-PROTOCOL. In our experiments, we analyzed the impact of greedy miners who deviated from the modeled DAG protocol by selecting transactions based on the highest fee. We demonstrated that greedy miners have a significant advantage over honest miners in terms of profit maximization. Moreover, we showed that greedy miners have a detrimental impact on transaction throughput and have the incentive to form a mining pool, exacerbating the decentralization of the assumed consensus protocols.

REFERENCES

[1] Maher Alharby and Aad van Moorsel. Blocksim: A simulation framework for blockchain systems. SIGMETRICS Perform. Eval. Rev., 46(3):135–138, January 2019.

[2] Emmanuelle Anceaume, Antoine Guellier, Romaric Ludinard, and Bruno Sericola. Sycomore: A permissionless distributed ledger that self-adapts to transactions demand. In 2018 IEEE 17th International Symposium on Network Computing and Applications (NCA), pages 1–8. IEEE, 2018.

[3] Anton Churyumov. Byteball: A decentralized system for storage and transfer of value. https://byteball.org/Byteball.pdf, 2016.

[4] Yusuke Aoki, Kai Otsuki, Takeshi Kaneko, Ryohei Banno, and Kazuyuki Shudo. Simblock: A blockchain network simulator. In IEEE INFOCOM 2019 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), pages 325–329. IEEE, 2019.

[5] Robert J. Aumann. Agreeing to disagree. The Annals of Statistics, 4(6):1236–1239, 1976.

[6] 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. ACM New York, NY, USA, 2019.

[7] Beman Dawes and David Abrahams. Boost C++ libraries. https://www. boost.org, 2001.

[8] Georgios Birmpas, Elias Koutsoupias, Philip Lazos, and Francisco J. Marmolejo-Coss´ıo. Fairness and efficiency in dag-based cryptocurrencies. In Financial Cryptography and Data Security: 24th International Conference, FC 2020 , Kota Kinabalu, Malaysia, February 10-14, 2020 Revised Selected Papers, pages 79–96, Berlin, Heidelberg, 2020. Springer-Verlag.

[9] R. Bowden, H. P. Keeler, A. E. Krzesinski, and P. G. Taylor. Block arrivals in the bitcoin blockchain, 2018.

[10] Bin Cao, Zhenghui Zhang, Daquan Feng, Shengli Zhang, Lei Zhang, Mugen Peng, and Yun Li. Performance analysis and comparison of pow, pos and dag based blockchains. Digital Communications and Networks, 6(4):480–485, 2020.

[11] Christian Decker and Roger Wattenhofer. Information propagation in the bitcoin network. In IEEE P2P 2013 Proceedings, pages 1–10. IEEE, 2013.

[12] Aimen Djari, Emmanuelle Anceaume, and Sara Tucci-Piergiovanni. Simulation study of sycomore++, a self-adapting graph-based permissionless distributed ledger. In 2022 4th Conference on Blockchain Research & Applications for Innovative Networks and Services (BRAINS), pages 103–110. IEEE, 2022.

[13] DSN-Research-Group. Bitcoin network monitor. online, 2015.

[14] Gavin Andresen. bitcoin miningsim. https://github.com/gavinandresen/ bitcoin miningsim, 2015.

[15] Arthur Gervais, Ghassan O. Karame, Karl Wust, Vasileios Glykantzis, Hubert Ritzdorf, and Srdjan Capkun. On the security and performance of proof of work blockchains. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, CCS ’16, pages 3–16, New York, NY, USA, 2016. Association for Computing Machinery.

[16] Robert Gibbons. A Primer in Game Theory. Prentice-Hall, London, England, jan 1992.

[17] Vasilis Glykantzis and Arthur Gervais. Bitcoin-simulator, capable of simulating any re-parametrization of bitcoin. online, april 2016.

[18] J. Gobel, H.P. Keeler, A.E. Krzesinski, and P.G. Taylor. Bitcoin blockchain dynamics: The selfish-mine strategy in the presence of propagation delay. Performance Evaluation, 104:23–41, 2016.

[19] Cyril Grunspan and Ricardo Perez-Marco. The mathematics of bitcoin, 2020.

[20] Jochen Hoenicke. Johoe’s Bitcoin Mempool Statistic, 2022.

[21] Ivan Homoliak and Pawel Szalachowski. Aquareum: A centralized ledger enhanced with blockchain and trusted computing, 2020.

[22] Joaquın M Lopez Munoz. Boost Multi-index Containers Library. https://www.boost.org/doc/libs/1770/libs/multi index/doc/index.html, 2020.

[23] Eleftherios Kokoris-Kogias, Philipp Jovanovic, Linus Gasser, Nicolas Gailly, Ewa Syta, and Bryan Ford. Omniledger: A secure, scale-out, decentralized ledger via sharding. In IEEE S&P. IEEE, 2018.

[24] Leemon Baird. The swirlds hashgraph consensus algorithm: Fair, fast, byzantine fault tolerance. https://www.swirlds.com/downloads/SWIRLDS-TR-2016-01.pdf, 2016.

[25] Colin LeMahieu. Nano : A feeless distributed cryptocurrency network. https://www.exodus.com/assets/docs/nano-whitepaper.pdf, 2018.

[26] Yoad Lewenberg, Yonatan Sompolinsky, and Aviv Zohar. Inclusive block chain protocols. In Rainer Bohme and Tatsuaki Okamoto, editors, ¨ Financial Cryptography and Data Security, pages 528–547, Berlin, Heidelberg, 2015. Springer Berlin Heidelberg.

[27] Chenxing Li, Peilun Li, Dong Zhou, Wei Xu, Fan Long, and Andrew Yao. Scaling nakamoto consensus to thousands of transactions per second, 2018.

[28] Ziyao Liu, Nguyen Cong Luong, Wenbo Wang, Dusit Niyato, Ping Wang, Ying-Chang Liang, and Dong In Kim. A survey on blockchain: A game theoretical perspective. IEEE Access, 7:47615–47643, 2019.

[29] Loi Luu, Viswesh Narayanan, Chaodong Zheng, Kunal Baweja, Seth Gilbert, and Prateek Saxena. A secure sharding protocol for open blockchains. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, CCS ’16, pages 17–30, New York, NY, USA, 2016. Association for Computing Machinery.

[30] George J. Mailath and Larry Samuelson. Repeated Games and Reputations: Long-Run Relationships. Number 9780195300796 in OUP Catalogue. Oxford University Press, November 2006.

[31] J.D. Miller. Game Theory at Work: How to Use Game Theory to Outthink and Outmaneuvar Your Competition. McGraw Hill LLC, 2003.

[32] Jelena Misic, Vojislav B Misic, Xiaolin Chang, Saeideh Gholamrezazadeh Motlagh, and M Zulfiker Ali. Modeling of bitcoin’s blockchain delivery network. IEEE Transactions on Network Science and Engineering, 7(3):1368–1381, 2019.

[33] Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system, 2008. [34] Martin J. Osborne and Ariel Rubinstein. A course in game theory. The MIT Press, Cambridge, USA, 1994. electronic edition.

[35] Seongjoon Park, Seounghwan Oh, and Hwangnam Kim. Performance analysis of dag-based cryptocurrency. In 2019 IEEE International Conference on Communications Workshops (ICC Workshops), pages 1– 6. IEEE, 2019.

[36] Remigijus Paulavicius, Saulius Grigaitis, and Ernestas Filatovas. A ˇ systematic review and empirical analysis of blockchain simulators. IEEE Access, 9:38010–38028, 2021.

[37] Daniel Phillips. What is polygon (matic) and why it matters for ethereum. https://decrypt.co/resources/ what-is-polygon-matic-and-why-it-matters-for-ethereum, 2021.

[38] Joseph Poon and Thaddeus Dryja. The bitcoin lightning network: Scalable off-chain instant payments. https://lightning.network/ lightning-network-paper.pdf, 2016.

[39] Wellington Fernandes Silvano and Roderval Marcelino. Iota tangle: A cryptocurrency to communicate internet-of-things data. Future Generation Computer Systems, 112:307–319, 2020.

[40] Rajani Singh, Ashutosh Dhar Dwivedi, Gautam Srivastava, Agnieszka Wiszniewska-Matyszkiel, and Xiaochun Cheng. A game theoretic analysis of resource mining in blockchain. Cluster Computing, 23(3):2035– 2046, 2020.

[41] John Maynard Smith. Evolution and the Theory of Games. Cambridge University Press, 1982.

[42] Yonatan Sompolinsky. Kaspa. online, 2022. https://kaspa.org/.

[43] Yonatan Sompolinsky, Yoad Lewenberg, and Aviv Zohar. Spectre: A fast and scalable cryptocurrency protocol. Cryptology ePrint Archive, Paper 2016/1159, 2016.

[44] Yonatan Sompolinsky, Shai Wyborski, and Aviv Zohar. Phantom ghostdag: A scalable generalization of nakamoto consensus: September 2, 2021. In Proceedings of the 3rd ACM Conference on Advances in Financial Technologies, AFT ’21, pages 57–70, New York, NY, USA, 2021. Association for Computing Machinery.

[45] Yonatan Sompolinsky and Aviv Zohar. Accelerating bitcoin’s transaction processing. fast money grows on trees, not chains. Cryptology ePrint Archive, Paper 2013/881, 2013.

[46] Yonatan Sompolinsky and Aviv Zohar. Accelerating bitcoin’s transaction processing. Fast money grows on trees, not chains, 2013.

[47] Shuyang Tang. Bracing a transaction dag with a backbone chain. Cryptology ePrint Archive, Report 2020/472, 2020. https://ia.cr/2020/472.

[48] Qin Wang, Jiangshan Yu, Shiping Chen, and Yang Xiang. Sok: Diving into dag-based blockchain systems, 2020.

[49] Taotao Wang, Xiaoqian Bai, Hao Wang, Soung Chang Liew, and Shengli Zhang. Game-theoretical analysis of mining strategy for bitcoin-ng blockchain protocol. IEEE Systems Journal, 15(2):2708– 2719, 2021.

[50] Xu Wang, Guohua Gan, and Ling-Yun Wu. Framework and algorithms for identifying honest blocks in blockchain. PLOS ONE, 15(1):1–14, 01 2020.

[51] Mahdi Zamani, Mahnush Movahedi, and Mariana Raykova. Rapidchain: Scaling blockchain via full sharding. In ACM CCS. ACM New York, NY, USA, 2018.

APPENDIX - GLOSSARY

• A A block in the DAG-PROTOCOL

• G Greedy strategy, choosing transactions with the highest fees

• H Honest strategy, choosing random transactions

• γ Discount function in PHANTOM

• κ Adversarial mining power

• λ Block creation time

• G The number of greedy miners

• τ Network propagation delay of blocks

• c Gap parameter in PHANTOM

• e Euler’s number

• t Time

• RTS Random Transaction Selection

• DAG Directed Acyclic Graph

• MNE Mixed Nash Equilibrium

• PNE Pure Nash Equilibrium

• PoW Proof of Work

• SPNE Subgame Perfect Nash Equilibrium