2
$\begingroup$

This has been bothering me for a while.

Bitcoin mining involves repeatedly changing the nonce (and occasionally the timestamp and Merkle root) in a block header and hashing it repeatedly, until the resulting hash falls below the target value. Therefore, the only valid way to find a valid hash is via brute force on a classical computer.

However, quantum computers are on the rise. 8-qubit and 16-qubit systems are already somewhat accessible to the public (for example, the IBM Q experience, which allows for cloud-based quantum computing), and the biggest quantum computer ever constructed to-date is, to my knowledge, 72-qubits. Grover's algorithm, which can only be implemented on a quantum computer, is particularly suited for breaking SHA256, the encryption algorithm behind bitcoin mining.

And therefore my question is - is it possible to implement Grover’s algorithm to find the right nonce that allows the block header hash to satisfy the target value? How many qubits would be required - 8, 16, 32 or more? My understanding is that, since we only need to iterate between all possible combinations of the nonce, which is 32 bits, wouldn't it require only sqrt(2^32)=2^16 (16 qubits) to instantly find a valid block header hash if we use Grover's algorithm?

Or am I missing something? I'm not very familiar with encryption and quantum algorithms, so please correct me if I'm wrong.

$\endgroup$
1
$\begingroup$

The linked question gives most of the relevant information but I want to focus on a few aspects of :

My understanding is that, since we only need to iterate between all possible combinations of the nonce, which is 32 bits, wouldn't it require only sqrt(2^32)=2^16 (16 qubits) to instantly find a valid block header hash if we use Grover's algorithm?

  1. Grover's algorithm needs a number of iterations which is the square root of the number you would need classically, not the square root of the number of bits. In this case, an "iteration" is one computation of the hash function SHA-256.

    Grover's algorithm will need to compute the hash function in superposition, and it needs to compute the entire hash function, whatever the nonce is. This means we need at least 512 qubits (256 for the input, 256 for the input) and in practice the number would be more like 5000 qubits.

  2. Quantum computers need error correction, so each of the qubits from the first point (what we call "logical qubits") will need many thousands of "physical" qubits (e.g., the kind that IBM and Google have right now, but better). The same paper estimates 14 million physical qubits to run Grover's algorithm on SHA-256. They are considering a full pre-image search, which is harder, so maybe bitcoin mining would "only" need a few hundred thousand qubits.

  3. Grover's algorithm won't instantly find a valid block header. If the current challenge is to find a header whose hash has $b$ zero bits, Grover's algorithm needs to compute the hash function roughly $2^{b/2}$ times. Right now $b=62$ so Grover's algorithm would still need to compute SHA-256 $2^{31}$ times.

  4. Right now, the bitcoin network is massively parallel. The network as a whole computes something like $2^{60}$ hashes/second so that it can find a preimage in 10 minutes, but each individual mining processor on the network computes much less (looks like around $2^{20}$ hashes/second for a single processor). Classical preimage search parallelizes very well: if you use twice as many computers you find the preimage (on average) twice as fast. For Grover's search, to find the preimage twice as fast you need 4 times as many quantum computers. If a quantum computer could compute hashes as fast as today's classical computer, then it can only compute $2^{29}$ hashes in 10 minutes, so it would need $(2^{31}/2^{29})^2=2^{4}=16$ quantum computers to have any mining advantage.

So: if you had 16 quantum computers, each with several hundred thousand qubits, you might have a slight bitcoin mining advantage.

| improve this answer | |
$\endgroup$
0
$\begingroup$

Today's quantum computer has too much calculation error. To calculate hash, quantum error correction is required. It uses a large number of qubits.

The figure is sited from: Quantum Computing Progress and Prospects (2019) pp.163 https://www.nap.edu/catalog/25196/quantum-computing-progress-and-prospects

enter image description here

| improve this answer | |
$\endgroup$
0
$\begingroup$

Yes, of course. But there are some interesting new challenges arising, if many miners used quantum computers to mine Bitcoin: https://arxiv.org/abs/1804.08118

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.