Quantum Computing & Blockchain: All is Not Lost
Picture this: somewhere high in the Hollywood Hills a group of screenwriters are meeting with an influential LA movie producer on an action film. Their pitch, hijacking of the first ‘quantum supreme’ computer en route from Australia’s University of New South Wales to Washington and the NSA.
Our hero’s mission impossible, find and recover the stolen quantum computer before it is used to decode the world’s trove of encrypted blockchains, wreaking economic havoc.
The producer says, ‘Quantum computers, quantum supreme evil geniuses, technology gone crazy and world domination. How much will it cost, and will it do CGI?’
Action movies aside, the challenges to blockchain technology and cryptography posed by an accelerating development of large, working quantum computers are very real. Quantum computing calls into question the core mathematics foundational to modern crypto algorithms, attacking their viability.
A quick review, Neha Narula of MIT’s Digital Currency Initiative says: “Cryptography is the study of how to secure communication, and it’s about two really important things: masking information so it can be hidden in plain sight, and verifying a piece of information’s source.”
Digging deeper, three major cryptographic algorithms, RSA, DSA and ECDSA derive their ‘hardness’ or ‘hiding’ property from computationally infeasible problems. Extremely infeasible, like the factorisation of very large integers, the discrete logarithm problem or the elliptic-curve discrete logarithm problem. Resistance to brute-force attacks against 256-bit hash signatures underpins the blockchain for the decentralised digital currency BitCoin which depends on the elliptic-curve discrete logarithm problem. Concurrently, as a cryptographic game the ‘puzzle friendly’ nature of the BitCoin hash signature function makes it impossible for any coin ‘mining’ strategy to be any better than trying possibilities at random. All these ‘trapdoor’ functions have a critical property in common. For ‘classical’ bit manipulating machines they are easy to compute in one direction, but next to impossible in the opposite one.
The idea is that BitCoin holders, or participants in blockchain transactions use a crypto-hash function to create a pair of linked 256-bit numbers: a secret (SK or ‘private’) and public (PK) key. PKs are generated from SKs, and hash signatures along with their associated public keys are used to prove without revealing, ownership of the secret ones. Equipped with crypto-hash functions and public-private keys, the source of a piece of information, its ‘owner,’ like a blockchain transaction can be verified without debate.
To put into perspective how hard it is to solve BitCoin’s SHA-256 ‘proof of work puzzles’ (PoW), it is much, much easier to find a single grain of sand from all the sands on Earth then to examine PoW solutions until a correct ‘answer’ is found. For grains of sand the problem is on order around 2 to the power 60 compared to 2 to the power 256 for PoW, an insanely large number. Proof of Work is the backbone of BitCoin’s ‘consensus’ algorithm with which blockchain becomes a self-sustaining system of distributed ledger transactions.
This is key: solving a PoW signature puzzle is extremely hard, but not impossible and BitCoin miners are no better off using any particular algorithmic strategy for finding a solution than by trying each at random.
That is what ‘mining pools’ do, figuratively they look at grains of sand for just the right one. Using specialised ASIC (Application Specific Integrated Circuit) hardware, racks of energy eating boxes churn upwards of 10 terra (trillion)-hashes per second to compete for the prize of ‘signing’ a ‘block’ on the ‘chain’. The winner rewarded with a number of bitcoin for their effort.
Physically based mainly in China because of ultra-cheap energy costs, but with competing operations on-going around the world, the total market cap of the 2018 coin mining industry securing associated blockchains is in the hundreds of billions of dollars. Put another way, the electricity consumption is approximately equivalent to that of Ireland.
Potentially, quantum computing renders all this processing power into nothing more than expensive, over-heating electronics.
Why? Because of the nature of quantum computing, in replacing bits with ‘quantum bits’ or ‘qubits’ rigs the game for blockchain. Cryptographic standards all made obsolete. Whether using entangled photons, ion traps or superconducting circuits, in reasonably finite (polynomial) time quantum computers make possible the calculation of private keys from public ones. The superposition property of qubits, in contrast to encoding either a 0 or 1 classical bit exploits the physics of the very small to perform calculations exponentially faster than ever before. Billions of pieces of information processed in a single compute cycle.
So, quantum computing destroys BitCoin, and blockchain applications are never to emerge from the Gartner ‘hype cycle trough of disillusionment’? All is lost?
Not necessarily, as an important caveat is revealed when the relative speeds of quantum computers expected to emerge near-term are compared to the existing capabilities of ASIC-based compute farms. That is where Divesh Aggarwal and colleagues from Singapore, France and Australia come in. For our action movie Aggarwal plays the pragmatic scientist who helps the hero save the day.
Saving the day turns out to be a quantitative and comprehensive analysis of projected quantum computer clock speeds over the next two decades. What the Aggarwal team finds is that despite the expected exponential speed-up, BitCoin and associated cryptocurrencies are, relatively speaking, resistant to dominance by quantum computers because of the current and extremely fast performance of ASICs. But, that relief comes with a warning, as PoW elliptic curve hash signature schemes could be broken by single quantum computers as early as 2027. They may we
ll succeed in attacking public, and returning private keys in less than 10 minutes.
What about ‘quantum resistant’ ledgers and post-quantum cryptography? Time to on-board and leave ‘classical’ methods behind? Maybe it is, and maybe not according to mathematician Daniel Bernstein. As he reports there are a number of existing cryptographic systems beyond RSA, DSA and ECDSA including: hash-based, code-based, lattice-based, and multivariate quadratic equations-based cryptography, each seen as resistant to attack from both classical and quantum-based computers.
So why not switch now and not worry when quantum supreme computers actually arrive? Again, Bernstein provides some thoughts, around how cryptographic systems are a collaborative science, played out between cryptographers who design systems to scramble and unscramble data, and cryptanalysts busy developing the best, most effective attacks to break these very same systems.
To be prepared for a post-quantum future he gives three answers for why it is not too early to start today, rather than waiting until the announcement of a large quantum computer. Starting with identifying the interesting ideas:
1. We need time to improve the efficiency of post-quantum cryptographic algorithms
2. We need time to build confidence in the robustness of these systems, and
3. We need time to build up their usability
Any forward thinking blockchain company will be doing just that, building the right kind of flexibility into their platform and infrastructure to deliver systems that can migrate from a classical to post-quantum future with a minimum of upset.
The prospects of incredibly powerful quantum computers dominating our digital lives makes for good action movies. So now fast forward to 2027, and our hero once again has to save the world from technology gone off the rails. This time, from a sentient quantum computer bent on replacing the human race with its own simulation.
Call it, ‘Buckaroo Blockchain’. Wait, maybe the human race in a computer simulation idea has been done before. Watch this space.
References
1. “ASCR Report on a Quantum Computing Testbed for Science”, Sponsored by U.S. Department of Energy, Office of Science, Advanced Scientific Computing Research Program, 2017
4. “Bitcoin Mining the Hard Way: the Algorithms, Protocols, and Bytes”, Ken Shirrif’s Blog, 2018
5. “A Quantum Boost for a Different Kind of Computer”, MIT Technology Review 2017
6. “Could Quantum Computing Kill Blockchain?”, Invest in Blockchain 2018
7. “Bitcoin and Cryptocurrency Technologies”, Arvind Narayanan et.al. Princeton Univ. 2016
8. “Introduction to the SHA-256 hash function”, steemit blog 2017
9. “What is an ASIC miner?”, digitaltrends.com 2018
10. “How Quantum Computing Threatens Blockchain”, National Review 2018
11. “Quantum Computers Pose Imminent Threat to BitCoin Security”, MIT Technology Review 2018
12. “How Blockchain is an Execution Layer in the Cloud”, Hacker Noon 2017
13. “Consensus in Blockchain Systems. In Short.”, Chris Hammerschmidt 2017
14. “An introduction to understanding attacks and dishonesty on proof-of-work blockchains”, Chris Hammerschmidt 2017
15. “Introduction to Proof of Work or Stake in the Blockchain”, Tibert van der Loop 2016
16. “Why Bitcoin fears Quantum Computers — and IOTA doesn’t”, Hacker Noon 2018
17. “Quantum attacks on Bitcoin, and how to protect against them ”, Divesh Aggarwal, et.al. 2017
18. “Post-Quantum Cryptography”, Editors: Bernstein, Daniel J., Buchmann, Johannes, Dahmen, Erik (Eds.) 2009
“Post-Quantum Cryptography”, Bernstein, DJ and Lange T., Nature 2017
