Quantum computers are considered a threat to Bitcoin. Two scientists have done the math: Do quantum miners really have an advantage over classical miners? And if so – does this pose a threat to Bitcoin?
Bitcoin and quantum computers: We’ve had this topic a time or two, and it’s actually been haunting Bitcoin since the beginning.
Do quantum computers threaten Bitcoin? Will a quantum computer one day arrive and, through its superior computing power, empty all wallets and mine away all Bitcoins? Some say yes, in the long run this could happen, others say no, there won’t be an ounce of worry for a very long time.
We have already written about quantum computers, Bitcoin and the ECDSA signature algorithm. Today we take a look at a paper in which two Canadian computer science professors analyse whether quantum miners pose a danger, and if so, what kind of danger.
The topic is not trivial, especially for mathematical laymen. But because it’s exciting for anyone interested in Bitcoin and the future of computing, I’ll try to present the paper as simply as possible.
The Leaping Progress
The basic framework on which the authors build their question is the following theory: If a miner becomes too powerful, he can threaten the network. If he has an absolute majority, he can drive 51 per cent attacks, but even below that he can cause damage through “aggressive” or “selfish” mining.
Now what if a miner gains such an advantage through quantum computing that his share of the hashrate grows disproportionately?
Basically, we’ve been through all this before, and it’s pretty trivial: technological progress accelerates mining. It doesn’t happen gradually, but often by leaps and bounds. From 2011, graphics cards displaced main processors, from 2013, Asics displaced graphics cards. At such moments, efficiency no longer increases linearly, but quadratically or exponentially. Now that Ascis seem to have largely exhausted the potential of classical chips, quantum computers could usher in the next big leap.
In itself, this should not pose a problem. Bitcoin’s game-theoretic mechanics motivate rational players to be honest and keep each other in check. Still, a technological leap can be bumpy, and perhaps it becomes a gateway for hostile powers acting irrationally to harm Bitcoin.
Therefore, it makes sense to know when it might happen. What has to happen for quantum computers to displace classic Asics from Bitcoin mining?
Searching unsorted databases
You can think of bitcoin mining as miners generating lots with their computing power. They generate random hashes, and if a hash meets certain very rare requirements, the miner finds a block. You could also call it a brute force attack against the SHA256 hash function.
The two professors put it this way: “The miners try to partially invert a cryptographic hash function”. This “partial inversion of a hash function” is “equivalent to searching for a marked item in an unordered list of items (an unstructured search)”. Sounds like a minor point, but it is fundamental to everything else.
For there is not much that quantum computers have been proven to be able to do. One of the few tasks where quantum computers are known to outshine classical computers is searching for a particular item in an unordered list.
A classical computer, when searching an unsorted database – or a brute force attack – has to work through one entry at a time. You can think of it as a two-dimensional pointer that moves from item to item. When it has seen half of the entries, the chance of landing a hit exceeds 50 per cent. Therefore, a classical computer needs on average N/2 operations, where N is the total number of possible items.
Quantum computers now have an advantage: a qubit can be 0 and 1 at the same time, which is why a series of qubits can simultaneously represent all conceivable variants. You can think of it as a pointer pointing in N dimensions. When the qubits are in this “superposition”, the solution is already in them. It is there.
But as soon as you measure, you destroy the solution. This is the famous quantum dilemma: if you measure, you force the quanta to assume a certain but random state. So the quantum computer knows the solution, but in a tragic twist, it devalues it when you go to pick it up.
Grover’s algorithm: square practically accelerated
This is where Grover’s algorithm comes in. Developed by Lov Grover in 1996, Grover’s algorithm is a method of checking the result. By combining different “quantum gates” – these are the operations in quantum computers – the qubits detect false results and suppress them. With each repetition – the so-called Grover iteration – the probability of getting the correct result thus increases.
The whole thing is crazy complicated in detail. But one thing is clear: with the right number of iterations, the Grover algorithm can dramatically speed up such searches. Because to find an item in an unsorted list, Grover only needs √n attempts. So it is almost quadratically faster.
Two examples: If there are 4 items, classical computers and quantum computers need 2 attempts. With 5,198,400 items, on the other hand, a quantum computer is found after 2280 attempts, while a conventional computer has to operate more than two million times.
Especially in tasks with an extreme difficulty or an extremely high N, such as bitcoin mining, this difference – the so-called quantum advantage – is enormous. It is one of those leaps that shake entire ecosystems. At least in theory.
The quantum advantage is melting
In practice, a quantum miner encounters a very specific problem: He can only find a block when he measures the result – and thus aborts the process. So he has to know beforehand how many iterations he will perform.
The question is tricky. Because both too many and too few have disadvantages. More iterations increase the chance of finding a correct solution – but also the danger that another miner will be faster. Fewer iterations, on the other hand, lower the probability of a valid result – and thus the quantum advantage.
If a quantum computer had endless time, it could exploit the full quantum advantage. But this is not possible with mining. It has to find a compromise between too few and too many iterations.
To calculate the optimal trade-off, the researchers formed a Markov chain with the possible scenarios. A Markov chain is a mathematical formulation of sequences of possible, usually random or partially random events. Such a chain indicates which paths through the jungle of probabilities lead on average to the best results: which setting of the Grover algorithm would be ideal.
Amazingly, this would be 16 minutes.
Two remarkable findings
If a quantum miner waits 16 minutes to read the result of Grover’s algorithm, its advantage over classical miners reaches the maximum in relation to the disadvantages that arise from the long time span. According to the scientists, this advantage exists regardless of the difficulty.
The result is very remarkable because it can be transferred into practice. Here one can see two serious consequences:
First, the miner with such a tactic disqualifies himself from about 80 per cent of the blocks. Because these are found in less than 16 minutes. He maximises his chances of success with the remaining 20 percent. This should be the maximum total mining power that quantum computers can achieve without sacrificing efficiency.
Second, most cryptocurrencies have shorter intervals between blocks. Dogecoin and Litecoin have about a few minutes, Ethereum and Ripple only a few seconds. Quantum miners get a bloody nose with these blockchains because the quantum advantage does not apply here. They are already quantum-safe – at least in mining.
The parallelisation of quantum computers also seems to be a dead end. Although this is possible with the Grover algorithm, it only improves performance by a factor of √m according to the authors’ calculations. With classical computers, the factor is m, i.e. it is quadratically larger. This makes it questionable whether quantum computers will ever be relevant for mining.
78 Megahashes
These calculations defuse the danger of quantum computers considerably. But the crucial question still remains unanswered: What has to happen for quantum miners to actually have an advantage over classical miners? At what point will it become cheaper to find a block with a quantum computer – if ever?
Two factors are decisive for this: the costs per grover iteration and the ratio of the number of hashes necessary for a block to the number of grover iterations required. The authors calculate this using the example of a currently common quantum computer with a “gate speed” of 66.7 megahertz. The gates are the quantum operations. The scientists calculate that this quantum computer would manage 224 grover iterations per second.
Meaning? 224 Grover iterations correspond to a hash rate of 78 megahashes per second. That is an absolutely microscopic proportion of the Bitcoin hashrate, indeed, only a tiny fraction of what modern Asics achieve. It would be ridiculous to smell danger here.
Likely to be more power efficient in the future
But if quantum miners pose no threat – are they at least more efficient? So, can there be, at least gradually, a conversion to quantum mining? And at what point?
To be more efficient, the energy cost of a Grover iteration should be at most 3.49 x 105 times the cost of a classical hash. Compared to classical miners, which have an energy efficiency of 10-10 Jules per hash, a quantum computer would need an efficiency better than 3.49 x 105 x 10-10, or about 10 μJ per Grover iteration. Or 2240 μJ per second.
That sounds extremely low. But quantum computers are very energy-efficient. As soon as the system is cooled down to 15 millikalvin, i.e. close to absolute zero, the quantum bits become a superconductor: they need virtually no electricity and produce virtually no heat. At present, cooling in relation to power still makes a quantum computer uneconomical. But this is likely to change as technology advances.
So all in all, as Bitcoiners, we can sleep soundly and a bit wiser and dream without terror of a future of quantum computers.
