Is quantum computing threat to Bitcoin ?

[Ix]

What is the biggest quantum bounty in bitcoin?
I.e. what is the single largest output that is Pay to Public Key?
Is it one of Satoshi's early addresses?
The advent of feasible quantum computing may well be heralded by the claiming of such a bounty.

Bitcoin did not pay to hash until some time after the start of the network - I think 1-2 years. I have seen stats somewhere that something like 40-50% of all bitcoins are stored with public keys, but a big chunk of that is probably active exchange accounts.

Yes quantum computers pose a threat to bitcoin in the future, but first, we need to even learn how to program software for quantum computers that would be able to decrypt the algorithm... so it's not an immediate threat but in the future it could pose a threat.

The algorithm to solve the discrete log problem - the security basis for ECDSA - is already known for quantum computers, it is called Shor's algorithm. https://en.wikipedia.org/wiki/Shor's_algorithm It means given a quantum computer with enough qubits, a private key can be derived from a public key in polynomial time (fast).

[1714689964]

1714689964

[1714689964]

1714689964

[rogerjordan07]

Well, yes quantum computing is very risky for bitcoin. It can definitely create a negative impact on bitcoin. So I will tell that it is a threat.

[zinson01]

Quantum computing is so complex in its nature. But I believe that it would not be possible to break the system of bitcoin.

[tromp]

What is the biggest quantum bounty in bitcoin?
I.e. what is the single largest output that is Pay to Public Key?
Is it one of Satoshi's early addresses?
The advent of feasible quantum computing may well be heralded by the claiming of such a bounty.

Bitcoin did not pay to hash until some time after the start of the network - I think 1-2 years. I have seen stats somewhere that something like 40-50% of all bitcoins are stored with public keys, but a big chunk of that is probably active exchange accounts.

All modern outputs, including those used by exchanges, are protected by Pay to Public Key Hash, and are relatively immune from quantum attacks (a quantum computer cannot find hash pre-images in polynomial time).

Unspent outputs from the very early years of bitcoin, that expose the public key, will be the prime targets of attack.

[Ix]

All modern outputs, including those used by exchanges, are protected by Pay to Public Key Hash, and are relatively immune from quantum attacks (a quantum computer cannot find hash pre-images in polynomial time).

Right but there is no enforcement against address reuse. I mentioned exchanges because I assume they are a large part of address reuse, and would be very quick to switch to a quantum resistant DSA should it be publicly known that quantum computers are near solving 128-bit DLPs.

I'm curious what order of magnitude of polynomial time quantum computers will be able to solve the DLP - I haven't seen any research delving into it exactly and I'm not smart enough to figure it out myself. Will P2H transactions have time to be accepted into blocks before their private keys are derived? Or will every transaction be contested? Does a ~256-bit security level DSA offer additional protection? Or is it that once someone has enough stable qubits to derive a 128-bit security level imply that doubling it (squaring it?) is trivial? 128 byte sigs vs 64 byte sigs would be preferable to ~3kbyte sigs of XMSS.

Unspent outputs from the very early years of bitcoin, that expose the public key, will be the prime targets of attack.

Of which there are at least 1-2 million bitcoins available. Very disruptive.

[etherixdevs]

Hi,
I found this article interesting about a solution to the problem
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-February/015758.html

[r1s2g3]

I do not find it threat to bitcoin.

First , Quantum Computers are not fully developed for any practical purpose.
Second, Even if they are developed, I do not think they will be available to common people. (The cost of quantum computer might be too high.)
Third, Instead of breaking the codes, might be they can be used to create more sophisticated and secure codes.

[aplistir]

What is the biggest quantum bounty in bitcoin?
I.e. what is the single largest output that is Pay to Public Key?

Bitcoin did not pay to hash until some time after the start of the network - I think 1-2 years. I have seen stats somewhere that something like 40-50% of all bitcoins are stored with public keys, but a big chunk of that is probably active exchange accounts.

All modern outputs, including those used by exchanges, are protected by Pay to Public Key Hash, and are relatively immune from quantum attacks (a quantum computer cannot find hash pre-images in polynomial time).

Exchanges do indeed use Pay to Public Key Hash, but and it is a big BUT. Most exchanges reuse their addresses and so their public key is visible, and hence they are NOT safe from quantum computers.  

All top 5 bitcoin addresses with the largest balances have reused their addresses and hence their public keys are visible. That is more than 600 000 bitcoins. 3 of them are multisig addresses, but even those can be cracked by quantum computer if the public keys are visible.

I would d prefer that exchanges would not re-use their addresses.

[Artisanal Miner]

I do not find it threat to bitcoin.

First , Quantum Computers are not fully developed for any practical purpose.
Second, Even if they are developed, I do not think they will be available to common people. (The cost of quantum computer might be too high.)
Third, Instead of breaking the codes, might be they can be used to create more sophisticated and secure codes.

Well really disagree you on this point, Quantum Computing has ability to break the chain of today supercomputer in fraction of seconds and can easily surpass the block-chain too.

you can check this article : https://www.linkedin.com/pulse/how-quantum-computing-effect-block-chain-ecosystem-ankur-prasad/?lipi=urn:li:page:d_flagship3_profile_view_base_post_details;Unx%2BTs50Sw20Pg8rVDhW7A%3D%3D

[Samarkand]

...
Traditional computing reaching its physical limit is actually one of the reasons why quantum computing is being heavily researched in the first place. Accordingly we can expect more and more funding being poored into R&D for quantum computing (and other approaches such as neuromorphic computing) as improving traditional architectures becomes less and less feasible.
...

I don´t necessarily disagree with this claim, but not everything that is heavily researched also produces the desired results.
The treatment of various lethal diseases is also heavily researched and still there are various diseases that can´t be cured
using current medicine. Maybe quantum computing will run into similar problems as the traditional computer architecture and
the situation won´t be much different in a few decades than it is now.

Besides, it is likely that even if quantum computers become a reality at some point in the future that cryptography will
have also improved.

[HeRetiK]

Exchanges do indeed use Pay to Public Key Hash, but and it is a big BUT. Most exchanges reuse their addresses and so their public key is visible, and hence they are NOT safe from quantum computers.  

All top 5 bitcoin addresses with the largest balances have reused their addresses and hence their public keys are visible. That is more than 600 000 bitcoins. 3 of them are multisig addresses, but even those can be cracked by quantum computer if the public keys are visible.

I would d prefer that exchanges would not re-use their addresses.

That is indeed the biggest problem right now. I do assume that exchanges will get their shit together once Quantum computers get feasible in a big scale, but on the other hand there have been exchanges that didn't even do transaction batching until just recently. At least in theory it shouldn't be that hard to avoid address reuse though, even at the scale of nowadays exchanges.

Well really disagree you on this point, Quantum Computing has ability to break the chain of today supercomputer in fraction of seconds and can easily surpass the block-chain too.

Bullshit and misinformation. Quantum computing will be able to solve some math problems faster than traditional architectures, that still doesn't make them a magic devices that instantly derive private keys from public keys or can "break the chain of today supercomputer in fraction of seconds" whatever that may mean.

Also the article shows complete misunderstanding of how mining works:

Amount of power which is consumed to run a Crypto Miner is quite very high and the negative effect on environment is a major concern. It's a fact that electricity is the major cost while mining any minable cryptocurrency, However advance research also says that Quantum computer can reduce the electricity and consumption.

More efficient miners won't lead to a reduction of electricity consumption -- it will only lead to more miners, offsetting whatever electricity savings have been made.

...
Traditional computing reaching its physical limit is actually one of the reasons why quantum computing is being heavily researched in the first place. Accordingly we can expect more and more funding being poored into R&D for quantum computing (and other approaches such as neuromorphic computing) as improving traditional architectures becomes less and less feasible.
...

I don´t necessarily disagree with this claim, but not everything that is heavily researched also produces the desired results.
The treatment of various lethal diseases is also heavily researched and still there are various illnesses that can´t be cured
using current medicine. Maybe quantum computing will run into similar problems as the traditional computer architecture and
the situation won´t be much different in a few decades than it is now.

Oh definitely. I'm not saying that quantum computing is bound to come into fruition, I'm just saying that the same physical limits (ie. size) that affect traditional architectures don't affect quantum computers -- pretty much by definition.

Besides, it is likely that even if quantum computers become a reality at some point in the future that cryptography will
have also improved.

Candidates for quantum resistant cryptography already exist, it's mostly a matter of standardization and deployment. The latter possibly being the largest challenge.

[solarion]

I do not find it threat to bitcoin.

First , Quantum Computers are not fully developed for any practical purpose.
Second, Even if they are developed, I do not think they will be available to common people. (The cost of quantum computer might be too high.)
Third, Instead of breaking the codes, might be they can be used to create more sophisticated and secure codes.

Well really disagree you on this point, Quantum Computing has ability to break the chain of today supercomputer in fraction of seconds and can easily surpass the block-chain too.

you can check this article : https://www.linkedin.com/pulse/how-quantum-computing-effect-block-chain-ecosystem-ankur-prasad/?lipi=urn:li:page:d_flagship3_profile_view_base_post_details;Unx%2BTs50Sw20Pg8rVDhW7A%3D%3D

If you own blogger account even you can article about it bro. Do not believe these kind of quantum computers to hack the blockchain platform. You can find the news like quantum computer can break blockchain security and private keys.
But if you ask the wallet developers and blockchain experts they will says 1000 number of quantum computers cannot hack the one wallet without private key bro.  Even it is not used by big in so far.

[Julia Wilson]

A very big threat, indeed.

I had read an article a few weeks ago concerning quantum computing and Bitcoin — if just one quantum processor mins away at Bitcoin, it could mine thousands and thousands of dollars in just one day before the difficulty explodes and Bitcoin drops like a brick in the sky.

Bitcoin is vulnerable, but only big corps have quantum processors. And with the huge sum of money they have, why would they spend the time to direct a quantum processor just to earn, maybe $50,000 for a day at the very most? To you that may be a lot, but to them, that's quite insignificant.

Of course, there are new cryptos that are defended from quantum processors mining the coins, but those cryptos are quite relatively unknown.

[janhllr]

As far as I understand it, bitcoin is currently vulnerable to quantum computers, in theory.
The problem isn’t best solved by mining using quantum computers, I’d say, but to change the mining algorithm so that quantum computers have no upper hand. Quantum computers are only good at some kinds of things.
This has been done by some crypto currencies, for example Quantum Resistant Ledger (QRL).

[tromp]

Quantum computers cause a problem with bitcoin, and from what I’ve read we need to move to a larger elliptic curve to be able to protect against them.

No; a larger curve doesn't help (much), since Shor's algorithm runs in (quasi) quadratic time.
That means that doubling the number of bits only causes a fourfold slowdown, and 10x as many bits only a factor 100x slowdown.

You'll need to move to some new post-quantum signature scheme to get the needed exponential lower bound on running time.

[tromp]

A very big threat, indeed.

I had read an article a few weeks ago concerning quantum computing and Bitcoin — if just one quantum processor mins away at Bitcoin, it could mine thousands and thousands of dollars in just one day before the difficulty explodes and Bitcoin drops like a brick in the sky.

Using quantum computers to mine doesn't make much sense, when they are WAY more efficient at just recovering private keys from public keys and stealing a good fraction of all BTC.

[HopeStillFlies]

hi everybody!

[tromp]

As far as I understand it, bitcoin is currently vulnerable to quantum computers, in theory.
The problem isn’t best solved by mining using quantum computers, I’d say, but to change the mining algorithm so that quantum computers have no upper hand. Quantum computers are only good at some kinds of things.

Bitcoin will have to move to a new post-quantum signature scheme long before they need to change to a post-quantum PoW.

    problem      quantum algorithm     rough speedup
    signatures   Shor's                       2^240
    PoW            Grover's                    2^40

[Traxo]

As far as I understand it, bitcoin is currently vulnerable to quantum computers, in theory.
The problem isn’t best solved by mining using quantum computers, I’d say, but to change the mining algorithm so that quantum computers have no upper hand. Quantum computers are only good at some kinds of things.

Bitcoin will have to move to a new post-quantum signature scheme long before they need to change to a post-quantum PoW.

    problem      quantum algorithm     rough speedup
    signatures   Shor's                       2^240
    PoW            Grover's                    2^40

@anonymint sent me a message in private chat stating that he doesn’t think you are analyzing the vulnerability of Nakamoto proof-of-work correctly and it’s much more vulnerable than the signature scheme and this appears to be an intentionally designed vulnerability:

http://iotatoken.com/IOTA_Whitepaper.pdf#page=26

Also he elaborates in the Decentralization section of the following blog:

https://steemit.com/cryptocurrency/@anonymint/scaling-decentralization-security-of-distributed-ledgers

Note @anonymint will not be able to discuss it with you here because he is perma-banned from bitcointalk.org.

[Ix]

Hi anonymint