12
$\begingroup$

As per Wikipedia, blockchains are a way to maintain "a continuously growing list of records, called blocks, which are linked and secured using cryptography [... and] inherently resistant to modification of the data."

Blockchains are in current practical use, for example in the cryptocurrency bitcoin. These implementations must make use of some particular approach to cryptography, which will involve assumptions intended to underwrite their security.

Are the current implementations of blockchain resistant to attacks using quantum computation?

$\endgroup$
  • $\begingroup$ Welcome to Quantum Computing SE! Asking about modifications to blockchain has already been asked before, so I agree that this is a duplicate question. However, asking about how/if it is/is not resistant hasn't been asked before, so if you want to edit your question to ask only that, it should be on topic $\endgroup$ – Mithrandir24601 Apr 11 '18 at 12:33
  • 2
    $\begingroup$ I think that, at the time of closing, it's fairly clear that the question is no longer a duplicate, and is also on-topic and answerable. While it is true that the linked post appears to answer the question, that other post has been closed as "too broad". This does not seem the ideal state of affairs: I propose that the question be re-opened, and the answer duplicated here, where it would be adequate and more appropriate. $\endgroup$ – Niel de Beaudrap Apr 12 '18 at 0:55
  • $\begingroup$ @NieldeBeaudrap Currently, this question does have a few reopen votes, however, a couple of people have also voted to leave it closed, which is what's making me reluctant to hammer it open. I would like to see questions actually be edited and reopened once closed if possible (although duplicates fall into a slightly different category of closed, so this doesn't necessarily apply in that/this case). What this question could do with is more detail, so if someone were to edit this question to add a good amount more detail, this could be transformed into a really good addition to the site $\endgroup$ – Mithrandir24601 May 15 '18 at 21:12
  • $\begingroup$ @Mithrandir24601: done. :-) $\endgroup$ – Niel de Beaudrap May 17 '18 at 10:23
  • $\begingroup$ @NieldeBeaudrap Thanks! I've reopened based on 1. Your edit and 2. The question this was originally duplicate of is itself closed $\endgroup$ – Mithrandir24601 May 17 '18 at 13:05
4
$\begingroup$

Are the current implementations of blockchain resistant to attacks using quantum computation?

Quick answers:

  1. Resistant against near-term technology? Sure.

  2. Reliably secure in the long term? Probably not.

  3. Will this pose a major problem? Very likely not.

  4. Is this risk unique to blockchains? Nope.

Because even if quantum computers would become a major threat to current implementations, the community could just elect to do a hard fork to post-quantum cryptography.

Not to say that blockchain technology developers and researchers don't need to worry about working on this issue, though I'd imagine that the average user needn't be concerned with this particular threat.

Also worth noting that other financial institutions, including banks, would be prone to a similar risk in some weird hypothetical world in which people inexplicably elected against upgrading their crypto. For example, hackers could use quantum computers to crack a financial institution's TLS/SSL certificate, allowing them to man-in-the-middle attack (random 2015 paper).


Long answer

Here's a 2017 paper that projects that Bitcoin could potentially become vulnerable by 2027, using generous assumptions:

The key cryptographic protocols used to secure the internet and financial transactions of today are all susceptible to attack by the development of a sufficiently large quantum computer. One particular area at risk are cryptocurrencies, a market currently worth over 150 billion USD. We investigate the risk of Bitcoin, and other cryptocurrencies, to attacks by quantum computers. We find that the proof-of-work used by Bitcoin is relatively resistant to substantial speedup by quantum computers in the next 10 years, mainly because specialized ASIC miners are extremely fast compared to the estimated clock speed of near-term quantum computers. On the other hand, the elliptic curve signature scheme used by Bitcoin is much more at risk, and could be completely broken by a quantum computer as early as 2027, by the most optimistic estimates. We analyze an alternative proof-of-work called Momentum, based on finding collisions in a hash function, that is even more resistant to speedup by a quantum computer. We also review the available post-quantum signature schemes to see which one would best meet the security and efficiency requirements of blockchain applications.

"Quantum attacks on Bitcoin, and how to protect against them" (2017-10-28)

That said, I'm not too sure how relevant a concern this might be in practice as it seems like that the situation'll change before that point. Even if Bitcoin's still around and going strong by the time it could be attacked, various mitigation techniques might go into effect.

The "Weakness" article on Bitcoin's wiki doesn't even mention quantum stuff, though their article on "Myths" does:

Quantum computers would break Bitcoin's security


While ECDSA is indeed not secure under quantum computing, quantum computers don't yet exist and probably won't for a while. The DWAVE system often written about in the press is, even if all their claims are true, not a quantum computer of a kind that could be used for cryptography. Bitcoin's security, when used properly with a new address on each transaction, depends on more than just ECDSA: Cryptographic hashes are much stronger than ECDSA under QC.

Bitcoin's security was designed to be upgraded in a forward compatible way and could be upgraded if this were considered an imminent threat (cf. Aggarwal et al. 2017, "Quantum attacks on Bitcoin, and how to protect against them").

See the implications of quantum computers on public key cryptography.

The risk of quantum computers is also there for financial institutions, like banks, because they heavily rely on cryptography when doing transactions.

"Myths", bitcoinwiki

Regarding the point about updating mentioned above, it's that while Bitcoin and other blockchains do tend to require standard algorithms that may be foreseeably attacked by quantum computers, before that's an issue, they can basically just do a hard fork, which is basically an update that everyone in the network migrates to, enabling stuff like algorithm changes.

What is 'Hard Fork'
A hard fork (or sometimes hardfork), as it relates to blockchain technology, is a radical change to the protocol that makes previously invalid blocks/transactions valid (or vice-versa). This requires all nodes or users to upgrade to the latest version of the protocol software. Put differently, a hard fork is a permanent divergence from the previous version of the blockchain, and nodes running previous versions will no longer be accepted by the newest version. This essentially creates a fork in the blockchain: one path follows the new, upgraded blockchain, and the other path continues along the old path. Generally, after a short period of time, those on the old chain will realize that their version of the blockchain is outdated or irrelevant and quickly upgrade to the latest version.

"Hard Fork", Investopedia

Of course, pushing a hard fork requires getting much of the community to accept it, though since pretty much all members of a cryptocurrency network wouldn't want to get hacked/scammed/etc., a hard fork pushed to avert a foreseeable risk of attack by quantum computers would almost certainly be uncontroversial.

$\endgroup$
  • $\begingroup$ It's generally helpful to know why stuff gets downvoted. For example, did someone disagree with the above, find it confusing, didn't feel it answered the question, etc.? $\endgroup$ – Nat May 17 '18 at 23:40
  • $\begingroup$ I'm wondering the same thing. I got downvoted TEN times today, including for my answer to this question --- and what is wrong with my answer? $\endgroup$ – user1271772 May 18 '18 at 1:06
2
$\begingroup$

In addition to the security of the digital signatures used in cryptocurrencies, which, as mentioned, is susceptible to an attack with a quantum computer capable of executing Shor's algorithm, cryptocurrencies use other cryptographic primitives in the "proof-of-work." Or Sattath describes a weakness of Bitcoin's currently implemented proof-of-work. Sattath proposes an easily-implementable countermeasure for this security flaw, but the current implementation of Bitcoin has Sattath's weakness.


In more detail, a cryptocurrency with a blockchain employing Nakamoto-style consensus requires miners who perform a proof-of-work, in order to determine the consensus ledger. In Bitcoin, the proof-of-work entails finding a partial preimage of a particular hash function - that is, at height $n$, miner $i$ generating her merkle root $R_i$ representing the ledger, and finding a nonce $c$ such that a cryptographic hash $H(B_{n-1}\Vert c\Vert R_i)=B_n\le d$ for target $d$.

As has been noted, such a proof-of-work is weakened by a quantum computer capable of executing Grover's algorithm - by running amplitude amplification on all states that hash to less than the target, a quadratic speedup may be achieved, and the nonce $c$ may be found more easily. A naive way to improve security, then, is to reduce the target $d$ polynomially - that is, make the difficulty be quadratically harder.

Further, a key requirement of such proofs-of-work is that they are progress-free, meaning that after a miner has spent $t$ minutes working on finding a nonce $c$, then she would be no closer to finding the winning block than if she spent $t+1$ minutes. The hope is that the race goes not the fastest, but to the ones with the most hash power. This leads to a lack of correlation between the time separate miners find a block.

However, Grover's algorithm is famously not progress-free. That is, each iteration of Grover's algorithm quadratically improves a miners' chance of finding the block. Or Sattath noted that this will likely lead to miners stopping their work immediately upon receiving a mined block, and hopefully winning a fork.

Sattath states:

Suppose Alice devoted $2$ minutes of applying Grover’s algorithm, and now receives a new block, mined by Bob. She could discard her computation, and start mining on top of Bob’s block, but that amounts to wasting $2$ minutes of computational resources. Instead, she could immediately stop Grover’s algorithm, and measure her quantum state. If she is lucky and her block is valid, and she also propagates her block to most other miners before Bob does, these other miners will mine on top of her block, and she, rather than Bob, will get the block reward.

Sattath supposes that if enough miners are Grover-capable, then all miners will be motivated to measure for their block whenever someone announces a nonce. This leads to forks that destroy the security of the blockchain.

$\endgroup$
1
$\begingroup$

That Wikipedia article you mention says "Blockchain security methods include the use of public-key cryptography." The most widely used pubic-key cryptography methods are RSA and some elliptic curve methods. Quantum computers are a threat to both RSA and elliptic curve methods because they rely on it being difficult to factor large number or to calculate difficult discrete logarithms, and Peter Shor showed in 1994 that a quantum computer can perform both these tasks with exponentially fewer arithmetic operations than a classical computer.

If it is possible to build a big enough quantum computer, most if not all blockchain implementations will be at threat because of relying on public-key cryptography implementations which are not safe against quantum computing.

$\endgroup$
  • $\begingroup$ Presumably this potential problem is avoided by the adoption of post-quantum cryptographic protocols? Unless the use of RSA, etc. is hard-coded into the blockchain's architecture, surely this can be easily updated? $\endgroup$ – SLesslyTall Jun 14 '18 at 12:55

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.