1University of Maryland
2Texas A&M University
3University of Edinburgh and IOHK
4Portland State University
5University of Edinburgh
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
A proof of work (PoW) is an important cryptographic construct enabling a party to convince others that they invested some effort in solving a computational task. Arguably, its main impact has been in the setting of cryptocurrencies such as Bitcoin and its underlying blockchain protocol, which received significant attention in recent years due to its potential for various applications as well as for solving fundamental distributed computing questions in novel threat models. PoWs enable the linking of blocks in the blockchain data structure and thus the problem of interest is the feasibility of obtaining a sequence (chain) of such proofs. In this work, we examine the hardness of finding such chain of PoWs against quantum strategies. We prove that the chain of PoWs problem reduces to a problem we call multi-solution Bernoulli search, for which we establish its quantum query complexity. Effectively, this is an extension of a threshold direct product theorem to an average-case unstructured search problem. Our proof, adding to active recent efforts, simplifies and generalizes the recording technique of Zhandry (Crypto’19). As an application, we revisit the formal treatment of security of the core of the Bitcoin consensus protocol, the Bitcoin backbone (Eurocrypt’15), against quantum adversaries, while honest parties are classical and show that protocol’s security holds under a quantum analogue of the classical “honest majority” assumption. Our analysis indicates that the security of Bitcoin backbone is guaranteed provided the number of adversarial quantum queries is bounded so that each quantum query is worth $O(p^{-1/2})$ classical ones, where $p$ is the success probability of a single classical query to the protocol’s underlying hash function. Somewhat surprisingly, the wait time for safe settlement in the case of quantum adversaries matches the safe settlement time in the classical case.
Popular summary
In our paper we examine how this mathematical problem, chain of PoWs, can be solved by a quantum adversary and provide bounds for their capabilities. Based on this result, we revisit the security of the Bitcoin backbone protocol (a mathematical abstraction capturing the key elements of the Bitcoin protocol), in the setting where all honest parties are classical, and there is a single quantum adversary (controlling all the quantum computational resources of the malicious parties). Our analysis shows that the security could be maintained if the total classical computational power of the honest parties in terms of queries/operations is a very large (but constant) number greater than the adversarial quantum computational power. This is a first step to the full analysis of bitcoin in the quantum era, when all parties would have quantum computational capabilities.
► BibTeX data
► References
[1] Cynthia Dwork and Moni Naor. “Pricing via processing or combatting junk mail”. In Advances in Cryptology – CRYPTO ’92, 12th Annual International Cryptology Conference, Santa Barbara, California, USA, August 16-20, 1992, Proceedings. Volume 740 of Lecture Notes in Computer Science, pages 139–147. Springer (1992).
https://doi.org/10.1007/3-540-48071-4_10
[2] Satoshi Nakamoto. “Bitcoin open source implementation of p2p currency”. (2009). http://p2pfoundation.ning.com/forum/topics/bitcoin-open-source.
http://p2pfoundation.ning.com/forum/topics/bitcoin-open-source
[3] 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. Pages 281–310. Berlin, Heidelberg (2015). Springer Berlin Heidelberg.
https://doi.org/10.1007/978-3-662-46803-6_10
[4] Rafael Pass, Lior Seeman, and Abhi Shelat. “Analysis of the blockchain protocol in asynchronous networks”. In Jean-Sébastien Coron and Jesper Buus Nielsen, editors, Advances in Cryptology – EUROCRYPT 2017. Volume 10211 of Lecture Notes in Computer Science. (2017).
https://doi.org/10.1007/978-3-319-56614-6_22
[5] Juan Garay, Aggelos Kiayias, and Nikos Leonardos. “The bitcoin backbone protocol with chains of variable difficulty”. In Jonathan Katz and Hovav Shacham, editors, Advances in Cryptology – CRYPTO 2017. Pages 291–323. Cham (2017). Springer International Publishing.
https://doi.org/10.1007/978-3-319-63688-7_10
[6] Christian Badertscher, Ueli Maurer, Daniel Tschudi, and Vassilis Zikas. “Bitcoin as a transaction ledger: A composable treatment”. In Jonathan Katz and Hovav Shacham, editors, Advances in Cryptology – CRYPTO 2017. Pages 324–356. Cham (2017). Springer International Publishing.
https://doi.org/10.1007/978-3-319-63688-7_11
[7] Mihir Bellare and Phillip Rogaway. “Random oracles are practical: A paradigm for designing efficient protocols”. In CCS ’93. Pages 62–73. (1993).
https://doi.org/10.1145/168588.168596
[8] Peter W. Shor. “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer”. SIAM J. Comput. 26, 1484–1509 (1997).
https://doi.org/10.1137/S0097539795293172
[9] Marc Kaplan, Gaëtan Leurent, Anthony Leverrier, and María Naya-Plasencia. “Breaking symmetric cryptosystems using quantum period finding”. In Matthew Robshaw and Jonathan Katz, editors, Advances in Cryptology – CRYPTO 2016. Pages 207–237. Berlin, Heidelberg (2016). Springer Berlin Heidelberg.
https://doi.org/10.1007/978-3-662-53008-5_8
[10] Thomas Santoli and Christian Schaffner. “Using simon’s algorithm to attack symmetric-key cryptographic primitives”. Quantum Information and Computation 17, 65–78 (2017).
https://doi.org/10.26421/qic17.1-2-4
[11] Jeroen Van De Graaf. “Towards a formal definition of security for quantum protocols”. PhD thesis. Universite de Montreal. CAN (1998).
[12] John Watrous. “Zero-knowledge against quantum attacks”. In Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing. Page 296–305. STOC ’06New York, NY, USA (2006). Association for Computing Machinery.
https://doi.org/10.1145/1132516.1132560
[13] Dominique Unruh. “Quantum proofs of knowledge”. In David Pointcheval and Thomas Johansson, editors, Advances in Cryptology – EUROCRYPT 2012. Pages 135–152. Berlin, Heidelberg (2012). Springer Berlin Heidelberg.
https://doi.org/10.1007/978-3-642-29011-4_10
[14] Sean Hallgren, Adam Smith, and Fang Song. “Classical cryptographic protocols in a quantum world”. In Phillip Rogaway, editor, Advances in Cryptology – CRYPTO 2011. Pages 411–428. Berlin, Heidelberg (2011). Springer Berlin Heidelberg.
https://doi.org/10.1007/978-3-642-22792-9_23
[15] Gorjan Alagic, Tommaso Gagliardoni, and Christian Majenz. “Unforgeable quantum encryption”. In Jesper Buus Nielsen and Vincent Rijmen, editors, Advances in Cryptology – EUROCRYPT 2018. Pages 489–519. Cham (2018). Springer International Publishing.
https://doi.org/10.1007/978-3-319-78372-7_16
[16] Dan Boneh and Mark Zhandry. “Quantum-secure message authentication codes”. In Thomas Johansson and Phong Q. Nguyen, editors, Advances in Cryptology – EUROCRYPT 2013. Pages 592–608. Berlin, Heidelberg (2013). Springer Berlin Heidelberg.
https://doi.org/10.1007/978-3-642-38348-9_35
[17] Dan Boneh, Özgür Dagdelen, Marc Fischlin, Anja Lehmann, Christian Schaffner, and Mark Zhandry. “Random oracles in a quantum world”. In Dong Hoon Lee and Xiaoyun Wang, editors, Advances in Cryptology – ASIACRYPT 2011. Pages 41–69. Berlin, Heidelberg (2011). Springer Berlin Heidelberg.
https://doi.org/10.1007/978-3-642-25385-0_3
[18] Mark Zhandry. “How to record quantum queries, and applications to quantum indifferentiability”. In Alexandra Boldyreva and Daniele Micciancio, editors, Advances in Cryptology – CRYPTO 2019. Pages 239–268. Cham (2019). Springer International Publishing.
https://doi.org/10.1007/978-3-030-26951-7_9
[19] Troy Lee and Jérémie Roland. “A strong direct product theorem for quantum query complexity”. computational complexity 22, 429–462 (2013).
https://doi.org/10.1007/s00037-013-0066-8
[20] Gorjan Alagic, Christian Majenz, Alexander Russell, and Fang Song. “Quantum-secure message authentication via blind-unforgeability”. In Advances in Cryptology – EUROCRYPT 2020. Springer (2020).
https://doi.org/10.1007/978-3-030-45727-3_27
[21] Yassine Hamoudi and Frédéric Magniez. “Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs”. In Min-Hsiu Hsieh, editor, 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021). Volume 197 of Leibniz International Proceedings in Informatics (LIPIcs), pages 1:1–1:21. Dagstuhl, Germany (2021). Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.TQC.2021.1
[22] Qipeng Liu and Mark Zhandry. “On finding quantum multi-collisions”. In Yuval Ishai and Vincent Rijmen, editors, Advances in Cryptology – EUROCRYPT 2019. Pages 189–218. Cham (2019). Springer International Publishing.
https://doi.org/10.1007/978-3-030-17659-4_7
[23] Falk Unger. “A probabilistic inequality with applications to threshold direct-product theorems”. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science. Pages 221–229. IEEE (2009).
https://doi.org/10.1109/FOCS.2009.62
[24] H. Klauck, R. de Wolf, and R. Špalek. “Quantum and classical strong direct product theorems and optimal time-space tradeoffs”. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science. Pages 12–21. Los Alamitos, CA, USA (2004). IEEE Computer Society.
https://doi.org/10.1109/FOCS.2004.52
[25] Alexander A Sherstov. “Strong direct product theorems for quantum communication and query complexity”. SIAM Journal on Computing 41, 1122–1165 (2012).
https://doi.org/10.1137/110842661
[26] Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. “Quantum lower bounds by polynomials”. J. ACM 48, 778–797 (2001).
https://doi.org/10.1145/502090.502097
[27] Andris Ambainis. “Quantum lower bounds by quantum arguments”. J. Comput. Syst. Sci. 64, 750–767 (2002).
https://doi.org/10.1006/jcss.2002.1826
[28] Christof Zalka. “Grover’s quantum searching algorithm is optimal”. Phys. Rev. A 60, 2746–2751 (1999).
https://doi.org/10.1103/PhysRevA.60.2746
[29] Michel Boyer, Gilles Brassard, Peter Høyer, and Alain Tapp. “Tight bounds on quantum searching”. Fortschritte der Physik 46, 493–505 (1998).
<a href="https://doi.org/10.1002/(sici)1521-3978(199806)46:4/53.0.co;2-p”>https://doi.org/10.1002/(sici)1521-3978(199806)46:4/5<493::aid-prop493>3.0.co;2-p
[30] Andris Ambainis, Robert Špalek, and Ronald de Wolf. “A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs”. Algorithmica 55, 422–461 (2009).
https://doi.org/10.1007/s00453-007-9022-9
[31] Andris Ambainis. “A new quantum lower bound method, with an application to a strong direct product theorem for quantum search”. Theory of Computing 6, 1–25 (2010).
https://doi.org/10.4086/toc.2010.v006a001
[32] Juan A. Garay, Aggelos Kiayias, Nikos Leonardos, and Giorgos Panagiotakos. “Bootstrapping the blockchain, with applications to consensus and fast pki setup”. In Michel Abdalla and Ricardo Dahab, editors, Public-Key Cryptography – PKC 2018. Pages 465–495. Cham (2018). Springer International Publishing.
https://doi.org/10.1007/978-3-319-76581-5_16
[33] Juan A. Garay, Aggelos Kiayias, and Giorgos Panagiotakos. “Iterated search problems and blockchain security under falsifiable assumptions”. Cryptology ePrint Archive, Report 2019/315 (2019). https://eprint.iacr.org/2019/315.
https://eprint.iacr.org/2019/315
[34] 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).
https://doi.org/10.1007/978-3-662-45472-5_28
[35] Divesh Aggarwal, Gavin Brennen, Troy Lee, Miklos Santha, and Marco Tomamichel. “Quantum attacks on bitcoin, and how to protect against them”. Ledger 3 (2018).
https://doi.org/10.5195/ledger.2018.127
[36] Troy Lee, Maharshi Ray, and Miklos Santha. “Strategies for Quantum Races”. In Avrim Blum, editor, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Volume 124 of Leibniz International Proceedings in Informatics (LIPIcs), pages 51:1–51:21. Dagstuhl, Germany (2018). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
https://doi.org/10.4230/LIPIcs.ITCS.2019.51
[37] Or Sattath. “On the insecurity of quantum bitcoin mining”. Int. J. Inf. Secur. 19, 291–302 (2020).
https://doi.org/10.1007/s10207-020-00493-9
[38] Andrea Coladangelo and Or Sattath. “A Quantum Money Solution to the Blockchain Scalability Problem”. Quantum 4, 297 (2020).
https://doi.org/10.22331/q-2020-07-16-297
[39] Mark Zhandry. “How to construct quantum random functions”. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science. Pages 679–687. (2012).
https://doi.org/10.1109/FOCS.2012.37
[40] Mark Zhandry. “Secure identity-based encryption in the quantum random oracle model”. In Reihaneh Safavi-Naini and Ran Canetti, editors, Advances in Cryptology – CRYPTO 2012. Pages 758–775. Berlin, Heidelberg (2012). Springer Berlin Heidelberg.
https://doi.org/10.1007/978-3-642-32009-5_44
[41] Fang Song and Aaram Yun. “Quantum security of NMAC and related constructions – PRF domain extension against quantum attacks”. 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 II. Volume 10402 of Lecture Notes in Computer Science, pages 283–309. Springer (2017).
https://doi.org/10.1007/978-3-319-63715-0_10
[42] Edward Eaton and Fang Song. “Making existential-unforgeable signatures strongly unforgeable in the quantum random-oracle model”. In Salman Beigi and Robert König, editors, 10th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2015, May 20-22, 2015, Brussels, Belgium. Volume 44 of LIPIcs, pages 147–162. Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015).
https://doi.org/10.4230/LIPIcs.TQC.2015.147
[43] Dominique Unruh. “Non-interactive zero-knowledge proofs in the quantum random oracle model”. In Elisabeth Oswald and Marc Fischlin, editors, Advances in Cryptology – EUROCRYPT 2015. Pages 755–784. Berlin, Heidelberg (2015). Springer Berlin Heidelberg.
https://doi.org/10.1007/978-3-662-46803-6_25
[44] Andreas Hülsing, Joost Rijneveld, and Fang Song. “Mitigating multi-target attacks in hash-based signatures”. In Proceedings, Part I, of the 19th IACR International Conference on Public-Key Cryptography — PKC 2016 – Volume 9614. Pages 387–416. Berlin, Heidelberg (2016). Springer-Verlag.
https://doi.org/10.1007/978-3-662-49384-7_15
[45] Marko Balogh, Edward Eaton, and Fang Song. “Quantum collision-finding in non-uniform random functions”. In Tanja Lange and Rainer Steinwandt, editors, Post-Quantum Cryptography. Pages 467–486. Cham (2018). Springer International Publishing.
https://doi.org/10.1007/978-3-319-79063-3_22
[46] Ben Hamlin and Fang Song. “Quantum security of hash functions and property-preservation of iterated hashing”. In Jintai Ding and Rainer Steinwandt, editors, Post-Quantum Cryptography. Pages 329–349. Cham (2019). Springer International Publishing.
https://doi.org/10.1007/978-3-030-25510-7_18
[47] Dennis Hofheinz, Kathrin Hövelmanns, and Eike Kiltz. “A modular analysis of the fujisaki-okamoto transformation”. In Yael Kalai and Leonid Reyzin, editors, Theory of Cryptography. Pages 341–371. Cham (2017). Springer International Publishing.
https://doi.org/10.1007/978-3-319-70500-2_12
[48] Tsunekazu Saito, Keita Xagawa, and Takashi Yamakawa. “Tightly-secure key-encapsulation mechanism in the quantum random oracle model”. In Jesper Buus Nielsen and Vincent Rijmen, editors, Advances in Cryptology – EUROCRYPT 2018. Pages 520–551. Cham (2018). Springer International Publishing.
https://doi.org/10.1007/978-3-319-78372-7_17
[49] Andris Ambainis, Mike Hamburg, and Dominique Unruh. “Quantum security proofs using semi-classical oracles”. In Alexandra Boldyreva and Daniele Micciancio, editors, Advances in Cryptology – CRYPTO 2019. Pages 269–295. Cham (2019). Springer International Publishing.
https://doi.org/10.1007/978-3-030-26951-7_10
[50] Qipeng Liu and Mark Zhandry. “Revisiting post-quantum fiat-shamir”. In Alexandra Boldyreva and Daniele Micciancio, editors, Advances in Cryptology – CRYPTO 2019. Pages 326–355. Cham (2019). Springer International Publishing.
https://doi.org/10.1007/978-3-030-26951-7_12
[51] Jelle Don, Serge Fehr, Christian Majenz, and Christian Schaffner. “Security of the fiat-shamir transformation in the quantum random-oracle model”. In Alexandra Boldyreva and Daniele Micciancio, editors, Advances in Cryptology – CRYPTO 2019. Pages 356–383. Cham (2019). Springer International Publishing.
https://doi.org/10.1007/978-3-030-26951-7_13
[52] Veronika Kuchta, Amin Sakzad, Damien Stehlé, Ron Steinfeld, and Shi-Feng Sun. “Measure-rewind-measure: Tighter quantum random oracle model proofs for one-way to hiding and cca security”. In Annual International Conference on the Theory and Applications of Cryptographic Techniques. Pages 703–728. Springer (2020).
https://doi.org/10.1007/978-3-030-45727-3_24
[53] Kai-Min Chung, Siyao Guo, Qipeng Liu, and Luowen Qian. “Tight quantum time-space tradeoffs for function inversion”. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS). Pages 673–684. IEEE (2020).
https://doi.org/10.1109/FOCS46700.2020.00068
[54] Shuichi Katsumata, Kris Kwiatkowski, Federico Pintore, and Thomas Prest. “Scalable ciphertext compression techniques for post-quantum kems and their applications”. In International Conference on the Theory and Application of Cryptology and Information Security. Pages 289–320. Springer (2020).
https://doi.org/10.1007/978-3-030-64837-4_10
[55] Jan Czajkowski. “Quantum indifferentiability of sha-3”. Cryptology ePrint Archive, Report 2021/192 (2021). https://ia.cr/2021/192.
https://ia.cr/2021/192
[56] Kai-Min Chung, Serge Fehr, Yu-Hsuan Huang, and Tai-Ning Liao. “On the compressed-oracle technique, and post-quantum security of proofs of sequential work”. In Anne Canteaut and François-Xavier Standaert, editors, Advances in Cryptology – EUROCRYPT 2021. Pages 598–629. Cham (2021). Springer International Publishing.
https://doi.org/10.1007/978-3-030-77886-6_21
[57] Jeremiah Blocki, Seunghoon Lee, and Samson Zhou. “On the Security of Proofs of Sequential Work in a Post-Quantum World”. In Stefano Tessaro, editor, 2nd Conference on Information-Theoretic Cryptography (ITC 2021). Volume 199 of Leibniz International Proceedings in Informatics (LIPIcs), pages 22:1–22:27. Dagstuhl, Germany (2021). Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.ITC.2021.22
[58] Dominique Unruh. “Compressed permutation oracles (and the collision-resistance of sponge/sha3)”. Cryptology ePrint Archive, Report 2021/062 (2021). https://eprint.iacr.org/2021/062.
https://eprint.iacr.org/2021/062
[59] Alexandru Cojocaru, Juan Garay, Aggelos Kiayias, Fang Song, and Petros Wallden. “The bitcoin backbone protocol against quantum adversaries”. Cryptology ePrint Archive, Paper 2019/1150 (2019). https://eprint.iacr.org/2019/1150.
https://eprint.iacr.org/2019/1150
[60] Ran Canetti. “Security and composition of multiparty cryptographic protocols”. J. Cryptology 13, 143–202 (2000).
https://doi.org/10.1007/s001459910006
[61] Ran Canetti. “Universally composable security: A new paradigm for cryptographic protocols”. In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA. Pages 136–145. IEEE Computer Society (2001).
https://doi.org/10.1109/SFCS.2001.959888
Cited by
[1] Marcos Allende, Diego López León, Sergio Cerón, Antonio Leal, Adrián Pareja, Marcelo Da Silva, Alejandro Pardo, Duncan Jones, David Worrall, Ben Merriman, Jonathan Gilmore, Nick Kitchener, and Salvador E. Venegas-Andraca, “Quantum-resistance in blockchain networks”, arXiv:2106.06640, (2021).
[2] Robert R. Nerem and Daya R. Gaur, “Conditions for Advantageous Quantum Bitcoin Mining”, arXiv:2110.00878, (2021).
The above citations are from SAO/NASA ADS (last updated successfully 2023-03-09 15:10:32). The list may be incomplete as not all publishers provide suitable and complete citation data.
Could not fetch Crossref cited-by data during last attempt 2023-03-09 15:10:29: Could not fetch cited-by data for 10.22331/q-2023-03-09-944 from Crossref. This is normal if the DOI was registered recently.
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.
- SEO Powered Content & PR Distribution. Get Amplified Today.
- Platoblockchain. Web3 Metaverse Intelligence. Knowledge Amplified. Access Here.
- Source: https://quantum-journal.org/papers/q-2023-03-09-944/
