Mining scripts on quantum computers

[release]

Just wandering if quantum computers can be used for mining? In theory they could calculate significantly faster?

[1715560656]

1715560656

[j2002ba2]

If quantum computers ever work, then by using Groover's algorithm mining difficulty would be square root of the usual one.

Let's say that mining difficulty is 80 bits. Then QC difficulty would be equivalent to 40 bits. Usual miners would do 2⁸⁰ operations, while QC would do 2⁴⁰ quantum operations.

But, IMO, unfortunately QC wouldn't work for any task other than generating enormous amounts of noise.

[release]

Noise?

Yeah I figured as much in regard to the 2 to the 40. I am talking theoritical, assuming QC function at optimal level.

[NotATether]

If quantum computers ever work, then by using Groover's algorithm mining difficulty would be square root of the usual one.

It's just taking away only one bit of difficulty. Since quantum computers still have to iterate through extremely large numbers of inputs in order to find one below some nonce N, The worst case running time is still 2^(256-1-log2(nonce) <-- number of nonce bits) * SHA256_speed*2 [as you perform a SHA256 twice for each input].

It's still far too early to try to throw QCs at the problem and expect them to finish in a reasonable amount of time. Also we can't really claim anything specific about how fast QCs can do any algorithm until someone actually designs an instruction set for them like ARM or x86 (or CUDA/OpenCL, in the case of GPUs). If we expect there to be an industry around QCs they all have to be able to run the same kind of programs. Even ASIC miners are to some extent configurable.

[Cnut237]

But, IMO, unfortunately QC wouldn't work for any task other than generating enormous amounts of noise.

If you had a viable and sufficiently powerful QC, then mining isn't your best angle of attack. As others have suggested, the QC attack on mining would use Grover's algorithm, which makes mining only slightly easier.

QCs are vastly better than classical computers at certain types of task, specifically where the combination of quantum state superposition (in a single qubit) and quantum entanglement (multiple 'linked' qubits) can be exploited. A classical bit can be 0 or 1, either/or. A qubit, because of quantum superposition, is in a sense partially both values, a probability smear across the two, until it is measured, when it resolves to a definite classical 0 or 1 outcome. In a system with multiple entangled qubits, the number of values covered increases 2^n. Two entangled qubits cover 2^2=4 possibilities, 00, 01, 10, 11. Three entangled qubits cover 2^3=8, 000, 001, 010, 011, 100, 101, 110, 111. And so on. A QC will assess the probabilities associated with all possible classical values, and will do so simultaneously. The number of outcomes it can assess simultaneously (2^n) being limited by the total number of qubits (n). Whereas a classical computer, no matter how fast, still proceeds one step at a time.

The quantum Shor algorithm is a much more powerful approach than Grover, and can be used to destroy public-key cryptography. And the easiest target here is reused addresses, as below:

Mining can potentially be much quicker with QCs.
The current PoW difficulty system can be exploited by a Quantum Computer using Grover’s algorithm to drastically reduce the number of computational steps required to solve the problem. The theorised advantage that a quantum computer (or parallelised QCs) have over classical computers is a couple of orders of magnitude, so ~x100 easier to mine. This isn’t necessarily a game-changer, as this QC speed advantage is likely to be some years away, by which time classical computers will surely have increased speed to reduce the QC advantage significantly. It is worth remembering that QCs aren’t going up against run-of-the-mill standard equipment here, but rather against the very fast ASICs that have been set up specifically for mining.

Re-used BTC addresses are 100% vulnerable to QCs.
Address Re-Use. Simply, any address that is re-used is 100% vulnerable because a QC can use Shor’s algorithm to break public-key cryptography. This is a quantum algorithm designed specifically to solve for prime factors. As with Grover’s algorithm, the key is in dramatically reducing the number of computational steps required to solve the problem. The upshot is that for any known public key, a QC can use Shor’s approach to derive the private key. The vulnerability cannot be overstated here. Any re-used address is utterly insecure.

Processed (accepted) transactions are theoretically somewhat vulnerable to QCs.
Theoretically possible because the QC can derive private keys from used addresses. In practice however processed transactions are likely to be quite secure as QCs would need to out-hash the network to double spend.

Unprocessed (pending) transactions are extremely vulnerable to QCs.
As above, a QC can derive a private key from a public key. So for any unprocessed transaction, a QC attacker can obtain the private key and then create their own transaction whilst offering a much higher fee, so that the attacker’s transaction gets onto the blockchain first, ahead of the genuine transaction. So block interval and QC speed are both crucial here – it all depends on whether or not the a QC can hack the key more quickly than the block is processed.

[NotATether]

The quantum Shor algorithm is a much more powerful approach than Grover, and can be used to destroy public-key cryptography.
~snip

This only works on RSA keypairs (and any other cryptosystem that uses prime factoring) and it is inapplicable to the elliptic curve cryptography that Bitcoin uses.

Elliptic curves take their private key as an extremely large number and multiply that by a curve point to get the public key. It's completely different from getting two primes and multiplying together to derive the private key, public key and other parameters, which is what Shor's algorithm applies to.

[Cnut237]

The quantum Shor algorithm is a much more powerful approach than Grover, and can be used to destroy public-key cryptography.
~snip

This only works on RSA keypairs (and any other cryptosystem that uses prime factoring) and it is inapplicable to the elliptic curve cryptography that Bitcoin uses.

Elliptic curves take their private key as an extremely large number and multiply that by a curve point to get the public key. It's completely different from getting two primes and multiplying together to derive the private key, public key and other parameters, which is what Shor's algorithm applies to.

I think address re-use is the important point. If you are using a one-time address, then the QC needs to derive the private key in the time between the transaction being sent and it being accepted. But if you are re-using an address, then Shor on a sufficiently powerful QC can derive the private key in 128^3=2,097,152 steps, compared with 2^128=340,282,366,920,938,463,463,374,607,431,768,211,456 steps on a classical computer. ECC is vulnerable to Shor, and the best defence is narrowing that window of opportunity by not re-using addresses.

[ranochigo]

This only works on RSA keypairs (and any other cryptosystem that uses prime factoring) and it is inapplicable to the elliptic curve cryptography that Bitcoin uses.

Elliptic curves take their private key as an extremely large number and multiply that by a curve point to get the public key. It's completely different from getting two primes and multiplying together to derive the private key, public key and other parameters, which is what Shor's algorithm applies to.

Shor's algorithm works on ECDSA, way easier than breaking RSA in fact[1] (I think 2x easier?). You can modify the algorithm slightly to defeat ECDSA which shouldn't be a problem.

[1] https://eprint.iacr.org/2017/598.pdf

Until a practical QC comes out, I think you can safely assume that the efficiency of our present day ASICs could be matched with the quantum computers that you'd see in a decade or so assuming that ASIC industry doesn't grow.

[Cnut237]

Returning to the issue of address re-use, it all comes down to exposed public keys. In which case, we need to consider the fact that back in the mists of time, block rewards were paid to a public key. All of these early coins, if they're still there, are vulnerable to quantum Shor. This is why the threat of QCs should be taken seriously. Whilst there are huge technical and engineering challenges to overcome, such as preventing decoherence in a sufficiently-scaled multi-qubit set-up, the fact remains that the advance of QCs is steady and remorseless. And it can't be solved trivially by simply forking bitcoin to a quantum-resistant chain, because everyone will need to move their coins to the new, Q-safe addresses, which wouldn't be possible even if everyone agreed to it... because the millions of 'lost' coins couldn't be moved, and would just sit there to be picked up by a QC that can derive the private key.

[NotATether]

Shor's algorithm works on ECDSA, way easier than breaking RSA in fact[1] (I think 2x easier?). You can modify the algorithm slightly to defeat ECDSA which shouldn't be a problem.

Now that I think about it, it's basically trying to find a number that when multiplied by itself modulo N =equals 1. ie. b^2 mod N = 1 and b^2 - 1 mod N = mN (source). That last part kind of makes it clear that for ECDSA N doesn't have to be the curve order but could be the private key, and m could be the curve point.

I don't follow how this becomes easier to crack than RSA though. Now we have to find m=some encrypted data^(an encryption key + a decryption key) and N is actually the modulus. Multiplication alone should be slower for ECDSA than RSA because it's group items are points and not plain integers.

[Cnut237]

I don't follow how this becomes easier to crack than RSA though.

AFAIK there are two separate quantum Shor algorithms, one for integer factorisation and one for discrete logs.

https://cds.cern.ch/record/602816/files/0301141.pdf

I'm not familiar with the intricacies of the algorithms, but there is also the consideration that problems that are of a similar difficulty from a classical perspective are not necessarily equal for a QC, due to the entanglement of qubits meaning that processing power scales 2^n.

But I'm not sure that for a QC the distinction between ECDSA difficulty and RSA difficulty is really much of an issue. If something is built that can break ECDSA, then RSA will not be far behind. All asymmetric cryptography is theoretically vulnerable.

[fxsniper]

about quantum
I would like to know we use quantum to bitcoin and crypto

What do you want to use quantum for?

1. use quantum to create bitcoin next generation to quantum bitcoin
That mean quantum computer when build success will can not crack bitcoin
because we made bitcoin quantum

I not yet see any bitcoin quantum project, but should be some one research and try create one in future or soon.

2. use quantum to mining bitcoin earning reward and make early full supply, so what next when have 21 million bitcoins already?
next mining alter coin and when every this full support, that happen for next?

3. use quantum to brute-force bitcoin private key
bitcoin still not solve algorithm ,but crack by brute-force private key
3.1 brute-force bitcoin Satoshi all millions bitcoin, hope so Satoshi say never mind!, use to bitcoin economy
3.2 brute-force bitcoin some one die
3.3 brute-force bitcoin loss password and loss private key
3.4 brute-force recover bitcoin was hacked give bakc to owner (with rewards)
3.5 (crime) brute-force steal some one bitcoin (same hacker)
3.6 donation and charity, help people, give food, give free vaccine free all the world
3.7 use for research quantum

4. use quantum to solve algorithm bitcoin any bitcoin can solve from address to private key complete.  (sha256, ripemd160, ECDSA)
4.1 (same 3)
id can solve algorithm level bitcoin will no value because algorithm was solve.
no more use bitcoin

3-4 will see some one sold all bitcoin that can take it, and bitcoin price will be down until zero

5. anything else


play quantum free try at google quantum playgroup and IBM quantum

https://www.quantumplayground.net/#/home

https://quantum-computing.ibm.com/

quantum code by python Qiskit

Need some one help to convert from bitcoin python to use on quantum computing
may be begin with simple job to generate bitcoin address, how fast quantum computing can do it.

[Cnut237]

~

Most of your questions are addressed in this thread. It does (in the later pages) go on to cover other aspects of quantum mechanics and elementary particle physics too, so worth a read if you're interested in those topics.

But don't believe all the breathless headlines about QCs. A lot of it is as-yet-unrealised hype. For example, 'number of qubits' is often the headline figure, but this disregards the huge and unresolved challenges in maintaining quantum coherence, which obviously scales up with number of qubits. Another point is that some of these 'quantum computers' are actually annealers (hello D-Wave), which is a different thing entirely, and more suited to resolving optimisation problems (e.g., travelling salesman) than to attacking bitcoin.