Proof-of-Work (PoW) is a fundamental underlying technology behind most major blockchain cryptocurrencies. It has been previously pointed out that quantum devices provide a computational advantage in performing PoW in the context of Bitcoin. Here we make the case that this quantum advantage extends not only to all existing PoW mechanisms, but to any possible PoW as well. This has strong consequences regarding both quantum-based attacks on the integrity of the entirety of the blockchain, as well as more legitimate uses of quantum computation for the purpose of mining Bitcoin and other cryptocurrencies. For the first case, we estimate when these quantum attacks will become feasible, for various cryptocurrencies, and discuss the impact of such attacks. For the latter, we derive a precise formula to calculate the economic incentive for switching to quantum-based cryptocurrency miners. Using this formula, we analyze several test scenarios, and conclude that investing in quantum hardware for cryptocurrency mining has the potential to pay off immensely.Proof-of-Work (PoW) is a fundamental underlying technology behind most major blockchain cryptocurrencies. It has been previously pointed out that quantum devices provide a computational advantage in performing PoW in the context of Bitcoin. Here we make the case that this quantum advantage extends not only to all existing PoW mechanisms, but to any possible PoW as well. This has strong consequences regarding both quantum-based attacks on the integrity of the entirety of the blockchain, as well as more legitimate uses of quantum computation for the purpose of mining Bitcoin and other cryptocurrencies. For the first case, we estimate when these quantum attacks will become feasible, for various cryptocurrencies, and discuss the impact of such attacks. For the latter, we derive a precise formula to calculate the economic incentive for switching to quantum-based cryptocurrency miners. Using this formula, we analyze several test scenarios, and conclude that investing in quantum hardware for cryptocurrency mining has the potential to pay off immensely.

arXiv:2105.01821May 5, 20212 citations

Strategies for quantum-enabled Bitcoin miners

Zach Manson, Barry C. Sanders

We study the impact that two miners equipped with quantum computers purpose-built for quantum Bitcoin mining will have on the 51% attack threshold of the Bitcoin network, given that the miners are playing a competitive game against each other to be the first to mine a block. We extend an existing game-theoretic framework for Bitcoin mining and compute the resultant payoff matrices. From these payoff matrices, we determine optimal quantum mining strategies for two non-colluding and aggressive quantum miners with multiple opportunities at finding a valid block in an otherwise classical Bitcoin network. We show that these optimal quantum mining strategies have a negligible effect on the 51% attack threshold. The novelty of our work is the inclusion of the Aggressive Quantum Mining Strategy and the realistic approach of allowing the quantum miners to restart their search if their measurements do not yield a valid block when determining the optimal quantum mining strategies. Our result is important for evaluating quantum-mining threats on cryptocurrencies based on Proof-of-Work, e.g. BitcoinWe study the impact that two miners equipped with quantum computers purpose-built for quantum Bitcoin mining will have on the 51% attack threshold of the Bitcoin network, given that the miners are playing a competitive game against each other to be the first to mine a block. We extend an existing game-theoretic framework for Bitcoin mining and compute the resultant payoff matrices. From these payoff matrices, we determine optimal quantum mining strategies for two non-colluding and aggressive quantum miners with multiple opportunities at finding a valid block in an otherwise classical Bitcoin network. We show that these optimal quantum mining strategies have a negligible effect on the 51% attack threshold. The novelty of our work is the inclusion of the Aggressive Quantum Mining Strategy and the realistic approach of allowing the quantum miners to restart their search if their measurements do not yield a valid block when determining the optimal quantum mining strategies. Our result is important for evaluating quantum-mining threats on cryptocurrencies based on Proof-of-Work, e.g. Bitcoin

quant-pharXiv:2607.23952Jul 28, 20260 citations

Quantum Attacks on Bitcoin, and How to Protect Against Them

Divesh Aggarwal, Gavin K. Brennen, Troy Lee +2 more

The key cryptographic protocols used to secure the internet and financial transactions of today are all susceptible to attack by the development of a sufficiently large quantum computer. One particular area at risk is cryptocurrencies, a market currently worth over 100 billion USD. We investigate the risk posed to Bitcoin, and other cryptocurrencies, by attacks using quantum computers. We find that the proof-of-work used by Bitcoin is relatively resistant to substantial speedup by quantum computers in the next 10 years, mainly because specialized ASIC miners are extremely fast compared to the estimated clock speed of near-term quantum computers. On the other hand, the elliptic curve signature scheme used by Bitcoin is much more at risk, and could be completely broken by a quantum computer as early as 2027, by the most optimistic estimates. We analyze an alternative proof-of-work called Momentum, based on finding collisions in a hash function, that is even more resistant to speedup by a quantum computer. We also review the available post-quantum signature schemes to see which one would best meet the security and efficiency requirements of blockchain applications.The key cryptographic protocols used to secure the internet and financial transactions of today are all susceptible to attack by the development of a sufficiently large quantum computer. One particular area at risk is cryptocurrencies, a market currently worth over 100 billion USD. We investigate the risk posed to Bitcoin, and other cryptocurrencies, by attacks using quantum computers. We find that the proof-of-work used by Bitcoin is relatively resistant to substantial speedup by quantum computers in the next 10 years, mainly because specialized ASIC miners are extremely fast compared to the estimated clock speed of near-term quantum computers. On the other hand, the elliptic curve signature scheme used by Bitcoin is much more at risk, and could be completely broken by a quantum computer as early as 2027, by the most optimistic estimates. We analyze an alternative proof-of-work called Momentum, based on finding collisions in a hash function, that is even more resistant to speedup by a quantum computer. We also review the available post-quantum signature schemes to see which one would best meet the security and efficiency requirements of blockchain applications.

arXiv:1710.10377LedgerOct 17, 2018231 citations

Analytical Exploration of the Effects and Implications of Quantum Computing on Cryptocurrency Systems

Yuanyi Zhang

Cryptocurrencies have gained significant importance in the financial market, and the emergence of quantum computers has raised concerns about their impact on cryptocurrency systems.This article aims to analyze these impacts, focusing primarily on the effects on the mining process, threats to blockchain security, and potential solutions to mitigate these effects.Through an extensive review of articles and theoretical research, this article uncovers significant potential effects on cryptocurrency systems resulting from quantum computing.The article highlights that the advent of quantum computing could lead to a drastic acceleration of the mining process, operating in quadratic time.Additionally, it raises concerns about the security vulnerabilities that quantum attacks pose to blockchain systems, as Shor's algorithm poses a considerable threat to the cryptographic mechanisms upon which cryptocurrencies rely.Grover's algorithm, on the other hand, has the potential to significantly reduce the time and energy consumption involved in mining.Although new cryptographic methods, such as Post-Quantum Cryptography, have been proposed to withstand quantum attacks, their effectiveness can only be theoretically evaluated until practical quantum computers become available.At present, the impact of quantum computing on the real world remains limited due to the nascent state of quantum technology.However, with IBM's plan to develop a 100,000-qubit system by 2033, the potential threats to cryptocurrency systems cannot be disregarded.Cryptocurrencies have gained significant importance in the financial market, and the emergence of quantum computers has raised concerns about their impact on cryptocurrency systems.This article aims to analyze these impacts, focusing primarily on the effects on the mining process, threats to blockchain security, and potential solutions to mitigate these effects.Through an extensive review of articles and theoretical research, this article uncovers significant potential effects on cryptocurrency systems resulting from quantum computing.The article highlights that the advent of quantum computing could lead to a drastic acceleration of the mining process, operating in quadratic time.Additionally, it raises concerns about the security vulnerabilities that quantum attacks pose to blockchain systems, as Shor's algorithm poses a considerable threat to the cryptographic mechanisms upon which cryptocurrencies rely.Grover's algorithm, on the other hand, has the potential to significantly reduce the time and energy consumption involved in mining.Although new cryptographic methods, such as Post-Quantum Cryptography, have been proposed to withstand quantum attacks, their effectiveness can only be theoretically evaluated until practical quantum computers become available.At present, the impact of quantum computing on the real world remains limited due to the nascent state of quantum technology.However, with IBM's plan to develop a 100,000-qubit system by 2033, the potential threats to cryptocurrency systems cannot be disregarded.

Advances in computer science researchJan 1, 20230 citations

Post-Quantum Blockchain Proofs of Work.

Alexandru Cojocaru, Juan A. Garay, Aggelos Kiayias +2 more

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 due to Zhandry (Crypto 2019). In addition, we revisit the formal treatment of security of the core of the Bitcoin consensus protocol, called the Bitcoin backbone (Eurocrypt 2015), against quantum adversaries and show that its security holds under a quantum analogue of the ``honest majority'' assumption that we formulate. Our analysis indicates that security of the Bitcoin backbone protocol is guaranteed provided that 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 probability of success 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.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 due to Zhandry (Crypto 2019). In addition, we revisit the formal treatment of security of the core of the Bitcoin consensus protocol, called the Bitcoin backbone (Eurocrypt 2015), against quantum adversaries and show that its security holds under a quantum analogue of the ``honest majority'' assumption that we formulate. Our analysis indicates that security of the Bitcoin backbone protocol is guaranteed provided that 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 probability of success 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.

Dec 1, 20210 citations

Vulnerability of blockchain technologies to quantum attacks

Joseph J. Kearney, Carlos A. Pérez-Delgado

Quantum computation represents a threat to many cryptographic protocols in operation today. It has been estimated that by 2035, there will exist a quantum computer capable of breaking the vital cryptographic scheme RSA2048. Blockchain technologies rely on cryptographic protocols for many of their essential sub-routines. Some of these protocols, but not all, are open to quantum attacks. Here we analyze the major blockchain-based cryptocurrencies deployed today—including Bitcoin, Ethereum, Litecoin and ZCash, and determine their risk exposure to quantum attacks. We finish with a comparative analysis of the studied cryptocurrencies and their underlying blockchain technologies and their relative levels of vulnerability to quantum attacks.Quantum computation represents a threat to many cryptographic protocols in operation today. It has been estimated that by 2035, there will exist a quantum computer capable of breaking the vital cryptographic scheme RSA2048. Blockchain technologies rely on cryptographic protocols for many of their essential sub-routines. Some of these protocols, but not all, are open to quantum attacks. Here we analyze the major blockchain-based cryptocurrencies deployed today—including Bitcoin, Ethereum, Litecoin and ZCash, and determine their risk exposure to quantum attacks. We finish with a comparative analysis of the studied cryptocurrencies and their underlying blockchain technologies and their relative levels of vulnerability to quantum attacks.

arXiv:2105.01815ArrayApr 23, 2021106 citations

O(p^{-1/2})

classical ones, where

p

is the probability of success 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.