Is quantum computing threat to Bitcoin ?

[tromp]

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

How are the above speedup numbers not accurate?
I rounded up the latter from sqrt(2^74) (iota paper's estimate of 2^68 is obsolete) to a multiple of 2^10.
Note that hese numbers are ignoring potentially FAR slower cycle times for quantum computers.

[Traxo]

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

How are the above speedup numbers not accurate?
I rounded up the latter from sqrt(2^74) (iota paper's estimate of 2^68 is obsolete) to a multiple of 2^10.
Note that hese numbers are ignoring potentially FAR slower cycle times for quantum computers.

@anonymint replied to me in private chat and asked you to please kindly note that it's the ratio in speedup that is relevant in proof-of-work, not the security of breaking the preimage of the hash.
Note that to break a Bitcoin public address requires also breaking the preimage of a hash, not just breaking the elliptic curve cryptography.
Thus your ratio comparison is incorrect.
Actually Grover's algorithm applies to breaking the preimage of the hash for a Bitcoin public-key address, which is not sufficient speed-up.
Yet the speed-up of the proof-of-work is 17 billion times faster which is sufficient to replace the entire chain in a nanosecond!

He asks if you could also look at the "Decentralization" section of his recent blog which goes into more detail on the theory and limited evidence that Satoshi did this intentionally:

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

So thus Satoshi designed Bitcoin addresses to be secure against quantum computing by wrapping them in a hash.
But he (intentionally) left proof-of-work mining vulnerable (allegedly so the global elite would have a way to take control if need be).
Iota shows that other designs might have been capable of patching the vulnerability in proof-of-work.
Or at least Satoshi should have mentioned the vulnerability but he was silent on the issue.


I discussed more about the intentional centralized design of Bitcoin here and here.

[Ix]

So thus Satoshi designed Bitcoin addresses to be secure against quantum computing by wrapping them in a hash.

Occam's razor, Satoshi designed bitcoin addresses to use hashing because payments are not made to public keys, but to scripts which are of an undefined and unbound length and would make horrible addresses. It had nothing to do with quantum computers which I don't believe he considered at all.

[Traxo]

Hi anonymint

I live in Europe, and @anonymint lives in the Philippines.
Please note that I'm not @anonymint.
And mods can verify this because I'm not using a VPN.

So thus Satoshi designed Bitcoin addresses to be secure against quantum computing by wrapping them in a hash.

Occam's razor, Satoshi designed bitcoin addresses to use hashing because payments are not made to public keys, but to scripts which are of an undefined and unbound length and would make horrible addresses. It had nothing to do with quantum computers which I don't believe he considered at all.

@anonymint says he was wondering where the original creator of Decrits had disappeared.
He remembers the intensive discussions with you in these forums back in 2013.
He said he will look at your whitepaper.

He does not think Satoshi would be so haphazard, footloose, and unpremeditated as you presume him to be.
Scripts could contain bare addresses then if your argument was valid. But instead he always made addresses hashed. And he put a lot of thought into making sure that the cryptography couldn’t be cracked by for example his paranoid use of double-hashing.

[Ix]

I live in Europe, and @anonymint lives in the Philippines.
Please note that I'm not @anonymint.
And mods can verify this because I'm not using a VPN.

I'm just saying hi because he's obviously reading the thread.

Scripts could contain bare addresses then if your argument was valid.

They can and do. For all his purported insight, Satoshi left all of his bitcoin in exposed coinbase to public key transactions. Over a million bitcoins just waiting to be stolen by a quantum computer.

And he put a lot of thought into making sure that the cryptography couldn’t be cracked by for example his paranoid use of double-hashing.

Double hashing was due to the known SHA2 length extension attacks.

[Traxo]

Scripts could contain bare addresses then if your argument was valid.

They can and do.

@anonymint recapitulated his point is that only idiots would leave their public keys bare.
And certainly the person who invented Bitcoin is not an idiot and would certainly realize no worthy person would opt to leave addresses bare.
So to presume that he only added hashing because scripts need to be cryptographically compressed when referenced is not really an application of Occam’s Razor.
Occam’s Razor would not presume that Satoshi was so sophisticated as to become ignorant just so that he could fulfill your theory.
Occam’s Razor assumes the simplest and most natural reason.

For all his purported insight, Satoshi left all of his bitcoin in exposed coinbase to public key transactions. Over a million bitcoins just waiting to be stolen by a quantum computer.

Nice deception isn’t it.
So the elite can steal the BTC from themselves and make it look like they stole from this inept Japanese dude who created Bitcoin in his garage next to a kabota.

Double hashing was due to the known SHA2 length extension attacks.

As @anonymint stated, he was very meticulous about cryptographic security. So why would you assume he became non-meticulous in other cases of Bitcoin’s design?

Why is it that you think the anonymous person (or group) who created the technology that is disrupting the entire world was only capable of very limited thoughts compartmentalized to the convenient areas where you would like them to be?
Is it because you really want to believe Satoshi was inept?

You presume Satoshi is compartmentalized in just the areas you need him/her/it/them to be, but that is a very complex proposition.
The simplest assumption is that Satoshi was not perfectly compartmentalized in just the precise areas we need him/her/it/them to be.
For example, to presume he/she/it/them would be too dumb to not put hashing on addresses unintentionally is a very complex assumption in light of someone of Satoshi’s meticulous attention to detail w.r.t. cryptographic security.

[Ix]

Ahh still such a troll.

[tromp]

Yet the speed-up of the proof-of-work is 17 billion times faster which is sufficient to replace the entire chain in a nanosecond!

Even a quantum computer takes over 2^45 operations to rewrite the chain which has accumulated work of 2^89 hashes. Even at a generous single cycle double SHA computation and 1 Ghz quantum cycle time this will take 2^15 seconds. That's about 10 hours rather than a nanosecond.

[Raja_MBZ]

When we're real close to perfection in quantum computing, and it starts looking like a big threat to bitcoin, we (the bitcoin community developers) can:

-hardfork bitcoin and create a tangle (like that of IOTA or a better form of DAG) based coin.
-airdrop it to bitcoin addresses with 1:1.

It does look like a possible solution to me.

Comments on it?

[Traxo]

Yet the speed-up of the proof-of-work is 17 billion times faster which is sufficient to replace the entire chain in a nanosecond!

Even a quantum computer takes over 2^45 operations to rewrite the chain which has accumulated work of 2^89 hashes. Even at a generous single cycle double SHA computation and 1 Ghz quantum cycle time this will take 2^15 seconds. That's about 10 hours rather than a nanosecond.

I presume @anonymint was speaking figuratively for the dramatic effect.
Thanks for the more plausible estimate.
Probably the quantum computer would be even slower than 1 Ghz, but I think his point about the potential threat remains valid.

When we're real close to perfection in quantum computing, and it starts looking like a big threat to bitcoin, we (the bitcoin community developers) can:

What if we don’t know we're real close? What if quantum computers become a state secret?
Also what if the extant miners at the juncture refuse to change the protocol because they're complicit?

-hardfork bitcoin and create a tangle (like that of IOTA or a better form of DAG) based coin.

Are they better? See this:
https://steemit.com/cryptocurrency/@anonymint/scaling-decentralization-security-of-distributed-ledgers-part-2

[bones261]

Yet the speed-up of the proof-of-work is 17 billion times faster which is sufficient to replace the entire chain in a nanosecond!

Even a quantum computer takes over 2^45 operations to rewrite the chain which has accumulated work of 2^89 hashes. Even at a generous single cycle double SHA computation and 1 Ghz quantum cycle time this will take 2^15 seconds. That's about 10 hours rather than a nanosecond.

Well, let's hope there are at least two white hats building on top of the BTC blockchain with their Quantum rig before 1 black hat decides to rewrite the entire chain in 10 hours. Also, wouldn't it take longer since every 2016 blocks, the difficulty of the clandestine network would go up 4x until it took them approximately 10 minutes to mine a block? I would think they would have to make sure not to run full blast, so that the difficulty wouldn't climb so dramatically. According to my calculations, if they ran full blast, by the time they get to block 46369, it would take their rig the 10 full minutes on average to find a block.

[tromp]

Even a quantum computer takes over 2^45 operations to rewrite the chain which has accumulated work of 2^89 hashes. Even at a generous single cycle double SHA computation and 1 Ghz quantum cycle time this will take 2^15 seconds. That's about 10 hours rather than a nanosecond.

Well, let's hope there are at least two white hats building on top of the BTC blockchain with their Quantum rig before 1 black hat decides to rewrite the entire chain in 10 hours. Also, wouldn't it take longer since every 2016 blocks, the difficulty of the clandestine network would go up 4x until it took them approximately 10 minutes to mine a block?

Oops; I had forgotten about the need to mine 2016 blocks at current difficulty before allowing it to quadruple (and I thought it could at most double). So correcting for both errors, the 10 hours becomes 10000 hours, or well over a year. Throw in more realistic quantum cycle times, constant factor overheads in Grover's algorithm, and quantum error correction slowdowns, and you're looking at many years...

[bones261]

Even a quantum computer takes over 2^45 operations to rewrite the chain which has accumulated work of 2^89 hashes. Even at a generous single cycle double SHA computation and 1 Ghz quantum cycle time this will take 2^15 seconds. That's about 10 hours rather than a nanosecond.

Well, let's hope there are at least two white hats building on top of the BTC blockchain with their Quantum rig before 1 black hat decides to rewrite the entire chain in 10 hours. Also, wouldn't it take longer since every 2016 blocks, the difficulty of the clandestine network would go up 4x until it took them approximately 10 minutes to mine a block?

Oops; I had forgotten about the need to mine 2016 blocks at current difficulty before allowing it to quadruple (and I thought it could at most double). So correcting for both errors, the 10 hours becomes 10000 hours, or well over a year. Throw in more realistic quantum cycle times, constant factor overheads in Grover's algorithm, and quantum error correction slowdowns, and you're looking at many years...

Perhaps there is a way to modify the BTC code or the clock on the rig to spoof the time in the blockheaders. That way, your could make your clandestine chain think it's solving a block about every 10 minutes when it is really mining a block every few seconds. Or is this something that just can't be spoofed?

[Ix]

Oops; I had forgotten about the need to mine 2016 blocks at current difficulty before allowing it to quadruple (and I thought it could at most double). So correcting for both errors, the 10 hours becomes 10000 hours, or well over a year. Throw in more realistic quantum cycle times, constant factor overheads in Grover's algorithm, and quantum error correction slowdowns, and you're looking at many years...

I don't think the 2016 blocks and difficulty adjustments matter for trying to rewrite the history as the attacker will just mimic the existing history. The amount of hashes you calculated would still stand the same to beat the cumulative difficulty of the existing chain. But really, all they need to do is rewrite recent history to perform double spends at will, and the developer checkpoints will prevent very deep history rewriting.

But this line of arguing is pretty pedantic if they can just steal all unprotected funds and funds as they are spent from scripts. (anonymint is very good at sending discussions off course.)

[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.

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 read your quoted article again, you will find they are strengthening the points that I  made.

1. " how and why it will took a decade and a lot of source and hard-work to build a Successful Quantum Computer. He said “This is really, really hard, way harder than building a classical computer,”.  "   ==> This excerpts from article strengthen my "first" point.

2.  NSA announced in 2015 that it is going to develop a anti Quantum Cryptographic System.  ==> A vague hint to my Third point that we can be still secure

3.But it is said that when the Quantum computer is available for everyone it will cost you millions of dollars. For example : D-Wave 2000Q cost around 15 Million USD   ==> Directly strengthening my second point.

In short , this article strength my belief that we are not in any kind of immediate danger and if some danger come, we will have some alternatives then
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

[tromp]

Perhaps there is a way to modify the BTC code or the clock on the rig to spoof the time in the blockheaders. That way, your could make your clandestine chain think it's solving a block about every 10 minutes when it is really mining a block every few seconds. Or is this something that just can't be spoofed?

Of course you can spoof timestamps at will, but difficulty adjustment still only happens once every 2016 blocks, and can then at most quadruple. So you still need to find PoW for 2016 blocks at diff 1, 2016 blocks at diff 2^2, .... , 2016 blocks at diff 2^44, and 2016 blocks at diff 2^46,
which takes the quantum computer 2016 * (2^16 + 2^17 + ... + 2^38 + 2^39) = about 2^51 steps.
Timestamps will just need to be close enough to force the maximum diff increase of 4x at each retargetting.

[CRYPTOWOLF_BOT]

Quantum computers pose a major threat to the security of our private data. So can it break bitcoin ? How vulnerable is bitcoin to it ?

The inception of quantum computer is going to signify a whole new age of computers. And they say all our data that we store online is going to be laid bare, in a manner of speaking. That is because the quantum computers are capable to perform incredibly complex calculations at speeds far exceeding those of today's machines. So all existing blockchain-based projects will have to adjust accordingly.

[Traxo]

I asked @anonymint in private Crypto.cat to respond one more time, and he was reticent because he said clearly @Ix has some vendetta and the discussion is turning nasty. He agreed to reply one more time for me for this thread, because of the technical errors that need to be corrected. Here follows verbatim the response he wrote to me in Crypto.cat...

Even a quantum computer takes over 2^45 operations to rewrite the chain which has accumulated work of 2^89 hashes. Even at a generous single cycle double SHA computation and 1 Ghz quantum cycle time this will take 2^15 seconds. That's about 10 hours rather than a nanosecond.

Also, wouldn't it take longer since every 2016 blocks, the difficulty of the clandestine network would go up 4x until it took them approximately 10 minutes to mine a block?

No. The longest chain is measured by adding up the difficulty of all blocks. So even though the blocks will be produced more slowly by the attacker, the difficulty of the chain being replaced is constant and the difficulty per unit time of the attacker is not decreasing.

Or is this something that just can't be spoofed?

With all due respect, your ideas for fixes Will not work. If you'd like to discuss this with me, you may post comments on Steemit or Medium for me to answer.

But this line of arguing is pretty pedantic if they can just steal all unprotected funds and funds as they are spent from scripts.

Hashed addresses aren't vulnerable until they're spent. After a few unfortunate users are hacked as they attempt to spend, the 99.999% of the UTXO that remains hashed will remain hashed until a fix is in place as word spreads of the attacks.

Your response belies an understanding of what was already written in this thread. As was explained to @tromp when comparing the vulnerability to the signature scheme, the proof-of-work vulnerability doesn't have the protection of  the preimage security of a hash which protects the public addresses. Thus the proof-of-work vulnerability is much more severe than the possibility of breaking the security of the private keys. That is the point I made to @tromp at the start.

But really, all they need to do is rewrite recent history to perform double spends at will, and the developer checkpoints will prevent very deep history rewriting.

Your suggested attack is the proof-of-work vulnerability that I raised. Whether the attacker deploys it long-range or short-range, my point to @tromp remains valid, that the proof-of-work is more vulnerable than the private keys.

Also, developer checkpoints are centralization and are futile if the miners refuse to adhere to them. The community would have to fork to a different proof-of-work algorithm because all of their coins would be stolen by rewriting the entire chain. Such an event would likely crater the price. The attacker could for example short the token and/or have other ulterior (externalities) profit/control motives that are achieved with the attack.

Moreover, the attacker could rewrite the chain and steal/burn only the tokens he wants, leaving the vast majority of users unaffected. Since democracy is one vote per human torso, the attacker can steal tokens from for example the Bitcoin $billionaires (that have minimal interleaving with other users´ UTXO from the time they were mined at coinbase or burn those portions of the targeted victims that intervealed) and leave the masses intact so the attacker(s) have political support for their takeover. Bitcoin transactions don’t reference the block hash where they were confirmed, so that makes this variant of a proof-of-work attack plausible.

(anonymint is very good at sending discussions off course.)

Look in the mirror to see who has been trying to drag the discussion into the gutter. First by your gross misapplication of Occam’s Razor wherein you argued that the more complex assumptions are the simpler ones, and now by making an incorrect technical argument. And then you have the audacity of injecting offtopic ad hominem inspite of your numerous errors and myopia about about how attacks can interact with externalities (and so for the 3rd time this is linked for you):

https://medium.com/@shelby_78386/the-caveat-though-is-that-when-the-attacker-can-fork-the-vested-interests-of-some-of-the-users-9340dd037a61

As for objectivity, I can only presume based on your statement quoted below that apparently you're still angry at me for discussions with you about your Decrits in 2013.

(something you went on for days about being a vulnerability - but it's not).

Is that vindictive behavior indicative of a civil and mature way to conduct a discussion? Since I started responding to posts in this thread via private chat with @Traxo, you've been trying to find a flaw in my technical argument with which you can nail me to an adhominem cross. Just stick to the points in the arguments without personalizing the argument.

It is not taking the thread offtopic to make points about Satoshi’s possible motives. Because motives are possibly relevant to how, why, and when such a quantum computing attack might be deployed.

Come on man. Please elevate your game to a civil discourse. If you want to prove something, then after 5 years finally launch your Decrits. Trying to ego battle me is the affliction of the incapable and isn't going to prove anything nor gain you anything.

2.  NSA announced in 2015 that it is going to develop a anti Quantum Cryptographic System.  ==> A vague hint to my Third point that we can be still secure

3.But it is said that when the Quantum computer is available for everyone it will cost you millions of dollars. For example : D-Wave 2000Q cost around 15 Million USD   ==> Directly strengthening my second point.

@anonymint remarked to me that powers-that-be will be able to afford that, and it ties directly into his point about who "Satoshi" probably really was.
Seems this argument offends people who want to believe Satoshi is some inept Japanese hacker who created Bitcoin from his garage located next to his/her/it/their extended family kabota.

[buwaytress]

You'll excuse the intrusion into the semi-troll slant of the current conversation, but here's something just published that backs an earlier paper refuting the threat of quantum computing to Bitcoin: https://www.aier.org/article/threat-bitcoin-quantum-computing

The paper referenced: https://arxiv.org/pdf/1710.10377.pdf

I personally believe that it is a threat, but probably 1 on a scale of 1 to 10. By the time QC catches up, Bitcoin will have inevitably improved. Somewhere, someone, is always working to improve it. I like this quote from the article: “If there is a known problem, there are people working on solutions, with tremendous professional awards accruing to the winner.”

[Stedsm]

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.

Probably a matter of the way one thinks. This thought came to my mind as well that the speed these computers will be possessing, can boost almost n times the mining speed as well as confirmation speeds to such levels where even these ASICs would fail. If bitcoin is so vulnerable to quantum computing (and as many of us think that this vulnerability has been stocked in intentionally), what could be the best option to stop such attacks which will have the power end up an era started to promote anonymity? Can official institutions commit such (baseless crimes) just to eat everything from everyone? But then, there comes a question of trust. Who will trade any of these things? There will just be a single dump, and then - THE END?!