TECH REPORT
Could a sufficiently powerful computer bring down Bitcoin?
Anyone who is not heartily sick of the words ‘blockchain’, ‘crypto’, and ‘NFT’ (and, indeed, mentions of quantum computing in these pages) may be interested to hear that, in a few years’ time, the whole thing might go away.
It’ll probably be replaced by something worse, of course, but the argument over the subject is interesting. Could a sufficiently powerful quantum computer, one that’s not been invented as yet, bring the whole blockchain network down around our ankles?
It’s easy, and often fun, to attribute remarkable powers to inventions of the future. Imagining VR that links itself directly to your visual cortex does not make it a reality, but quantum computers exist in the same way VR helmets do: The ones we know about are very early models that could all do with some improvement. And the ones we don’t know about? Well, who knows what the world’s governments are up to?
Wild speculation aside, the problem here is asymmetric cryptography. Two keys are generated, and they have a mathematical relationship—the public key can be derived from the private key, but not the other way around. The public key is just that—public. It’s used by anyone who wants to encrypt information that only you can read. The asymmetric bit means that running the encrypted data through the public key backwards (as you would with something like Enigma, for example) doesn’t decrypt it: For that you need the private key which you don’t tell anyone, even your psychiatrist. From this system the blockchain, Bitcoin, NFTs and a market worth over $100 billion were born.
Now, far be it for us to suggest a system in which miners can screw up both the environment and the supply of GPUs to gamers, and which can see a single grey pixel sell for $1.36 million at Sotheby’s, might be a bit silly. We’d just point out that this magazine costs a mere $9.99 yet contains many more pixels, some of them not grey. Enough, we’d estimate, for more than one per reader. But then we’re not selling PC Gamer as an NFT. Yet…
BLOCKED
For those still stumbling around in the dark about how a blockchain works, here’s a summary. When a transaction is requested, a ‘block’ containing that transaction is created. This is then sent to every ‘node’, or participant, on the particular network (that can be Bitcoin, Etherium, Dogecoin, whatever). The nodes work to validate the transaction, using the SHA256 algorithm (in the case of Bitcoin) to ‘hash’ the block into a 256bit hexadecimal number that uniquely identifies it. This is ‘mining’, and the first miner to validate the transaction in this way is rewarded with some Bitcoin (6.25 at the time of writing) depending on the difficulty.
That difficulty is altered depending on how fast blocks are added to the chain, as the Bitcoin protocol aims for six new blocks an hour. Difficulty is measured by the number of leading zeroes on an acceptable hash result. Each block, along with everything we’ve measured so far, contains a ‘nonce’ (a Number Only used oNCE). This is a number that can be varied to get the desired result, as changing it alters the hash. So if the difficulty is 15, you alter the nonce until your hash comes out with 15 leading zeroes. Once validated, the new block is added to a chain, with each block’s header containing the hash of the one before it, and distributed across the network again. Only then is the transaction done.
Blockchain is secure because making even the smallest change to a transaction that’s been validated changes the hash produced, so everyone on the network would notice. There’s also an additional security feature known as ‘pay to public key hash’ that hashes public keys and only reveals them when a transaction is initiated. Also, in a perfect world, each address would only be used once. Address reuse is rife, however, and a study by Deloitte found that around 25% of all Bitcoins are vulnerable in this way, along with the many, many cryptocoins whose owners have lost their private keys, and therefore cannot transfer them out of vulnerable wallets.
Still, the system seems to work pretty well as long as no one has a sufficiently powerful computer. To derive a private key from a public one involves tackling an elliptic curve discrete logarithm problem that would take a regular computer somewhere in the range of 65 million billion years to solve. An unencrypted public key is included with every
Bitcoin transaction—it acts as the address of the recipient— and left unprotected for the time it takes for the network to confirm the block, which is around ten minutes. Theoretically, that’s enough time for a powerful enough quantum computer to calculate the private key and replace the recipient’s address with someone else’s before the hash is generated. Miners are changing the nonce all the time, so a change to a different part of the block could go unnoticed.
And then there’s another thing. You could use a quantum computer to mine much, much faster than everybody else, inserting your own blocks into the chain for potentially nefarious purposes or to bring the whole system down.
So, the big question is, how many qubits would a theoretical quantum computer need to take a tin-opener to Bitcoin? 4,000, according to Miruna Rosca, a PhD student in post-quantum cryptography, in an interview with Decrypt. How many are there in the current most powerful known quantum computer? 72 (Google). Or maybe 10 (Honeywell). Or perhaps 32 (IonQ). The Chinese Jiuzhang computer doesn’t give a qubit figure, but its operators claim it’s 10 billion times faster than Google’s. IBM is promising a 1,000-qubit machine by 2023. It took 14 years for X86 CPUs to go from 1GHz to 4GHz, so could 4,000 qubits be here by 2037? We wouldn’t bet our Bitcoins against it, so it’s now up to blockchain architects to evolve quantum-secure cryptography before their secrets are opened up for the world to see.
Ian Evenden
YOU COULD USE A QUANTUM COMPUTER TO MINE MUCH, MUCH FASTER THAN EVERYBODY ELSE