Impact of Quantum Computers

The two major cryptographic primitives used in Bitcoin, namely Proof-of-Work and digital signatures, are affected by quantum algorithms. In this lesson, we’ll show the consequences of Grover’s and Shor’s algorithms for Bitcoin’s security.

Grover’s algorithm

As already discussed in this section:Grovers_Algorithm, a quantum computer using Grover’s algorithm enables a quadratic speedup in solving the PoW problem compared to classical hardware. Given a target value $T$, a quantum miner needs only to do an expected number of $\sqrt{2^{256} / T}$ hash computations instead of $2^{256} / T$ hash computations, which are needed with conventional computers. This weakens the security requirements of the hash functions SHA256 and RIPEMD160 such that the attacks on the hash functions we have outlined in this lesson become more feasible. However, this could easily be overcome by doubling the message digest. This can be achieved by replacing SHA256 with SHA3. Therefore, we can’t assume that Grover’s algorithm will be an advantage for preimage, second preimage, or collision attacks.

However, it’s more likely that Grover’s algorithm could allow an attacker to gain an unfair advantage in the mining process on which Bitcoin’s consensus mechanism is based. Since the block creation process is coupled to the PoW problem, there’s a risk that a single attacker who is in possession of a quantum computer could mine blocks faster than other competitors who only own conventional computers. Thus, a single quantum miner could dominate the generations of new blocks and hence dominate the whole blockchain. They would have several attack possibilities.

For example, they could only integrate desired transactions into the blockchain and thus control the content of the blockchain (Brandon Rodenburg (2017)Brandon Rodenburg and Stephen P Pappas. Blockchain and quantum computing. Technical Report. Publisher: MITRE Corporation. Bedford, Massachusetts. 2017. available at https://www.mitre.org/sites/default/files/publications/17-4039blockchain-and-quantum-computing.pdf.). Consequently, unwanted transactions would never appear in a block and would therefore never be confirmed, hence staying zero confirmed transactions, which are known to be unsafe. Furthermore, they would be able to rewrite the transaction’s history since they could start to mine a competing chain that grows faster than the main chain. Since the longest chain is conventionally chosen as to be the valid one, the attacker could easily launch double-spending attacks from any block.

However, even if quantum computers with enough qubits to perform Grover’s algorithm could one day become a reality, an attack on the mining system would be unlikely. This is because other practical factors aren’t taken into account in this scenario. In fact, the quantum advantage is limited to the factor $\sqrt{2^{256} / T}$ in terms of complexity, regardless of the number of qubits the quantum computer has.

However, the mining performance isn’t only tied to the complexity but also to the hashing rate. So, although there’s a quantum advantage in complexity, it’s probably not big enough not to be beaten by classic hardware as parallelization of classic hardware allows a very large hash rate and thus will outpace any quantum computer. Consequently, Tessler and Byrnes (2017)Louis Tessler and Tim Byrnes. Bitcoin and quantum computing. CoRR, abs/1711. 04235,2017. argue that profitable quantum mining will need “rather a fast quantum hash rate, and/or a much more significant quantum speed-up” and hence assume that classical mining is very difficult to beat.

Aggarwal et al. (2018)Divesh Aggarwal, Gavin Brennen, Troy Lee, Miklos Santha, and Marco Tomamichel. Quantum attacks on bitcoin, and how to protect against them. Ledger, 3(0), 2018. came to the same conclusion, as they estimate that current specialized ASICASICs (Application-Specific Integrated Circuits) are integrated circuits, i.e., customized microchips, which are specially designed for a particular use and hence allow high-efficiency hardware architectures. Such devices enable significantly higher hashing rates than traditional computer hardware. hardware with very large hashing rates would outpace any quantum computer, despite the quantum advantage in the form of a quadratic speed-up in terms of complexity. Consequently, they argue that “the extreme speed of current specialized ASIC hardware for performing the hashcash PoW, coupled with much slower projected gate speeds for current quantum architectures, essentially negates this quadratic speed up, at the current difficulty level, giving quantum computers no advantage.”

Based on their prediction model, they estimate that before 2028, there will be no existing quantum computer with enough qubits to implement Grover’s algorithm. According to their most optimistic estimations, there will then be a quantum computer capable of achieving a hashing rate of $13.8 \mathrm{GH} / \mathrm{s}$, which is still 1000 times slower than a single current conventional ASIC device that achieves a hash rate of $14 \mathrm{TH} / \mathrm{s}$.

So, we can’t expect that there will be a single quantum computer that could dominate Bitcoin’s consensus mechanism in the next decade. And even if this would become practical once, this would not have such a direct dramatic impact as we would expect since an attacker can neither steal foreign coins nor reverse foreign transactions since they’re protected by the ECC key pair. Consequently, they could only use their advantage in mining to double-spend their own coins. However, due to the financial incentive system, it would be more likely that the quantum computational effort would be invested in normal block generation, as this is the most lucrative from a financial perspective.

Other concerns regarding the mining process are expressed by Sattath (2018)Or Sattath. On the insecurity of quantum bitcoin mining. CoRR, abs/1804.08118, 2018 ., who predicts a rise in forks due to Grover’s quantum algorithm if many miners perform quantum mining. According to his statement, this is caused by the nature of Grover’s quantum algorithm, which repeatedly applies a Grover iteration, whereas we don’t have to decide how many Grover’s iterations to apply in advance. Currently, a miner immediately accepts a new received block that was proposed by another miner, as shown in this lesson.

Consequently, they immediately stop solving the current PoW and start mining on top of the new block. Sattath argues that a quantum miner will behave differently when they receive a new block. Instead of accepting the new block, they will immediately stop applying Grover’s algorithm and measure its quantum state. They could be lucky and get a valid block, which they also immediately propagate to the network. If many miners are using Grover’s algorithm, most of them will follow this strategy such that many miners will measure their state roughly at the same time. This increases the probability that multiple miners will simultaneously find a new valid block, resulting in a higher rate of forks or even multi-forks in the quantum setting. However, this problem can be overcome by redefining the mining rules.