On quantum computing and blockchain security
Quantum Computing; it’s one of those notions that tend to make people uncomfortable since it’s so hard to grasp. Most of us don’t know what it is and how it works, but we tend to associate it with hackers using it to break all modern applications of cryptography and cybersecurity. This is especially true for the blockchain space, where most consensus protocols — the element that secures a blockchain platform — fully rely on cryptographic algorithms.
Through this article, I hope to break the negative associations that we have with quantum computing by explaining the core concepts and its possible impact on modern encryption schemes used by blockchain platforms.
Computers and on-/off switches
Before we dive deep into the world of qubits, superposition and quantum gates, let’s examine the inner workings of today’s computers. In essence, a computer chip consists of a multitude of transistors. A transistor works like a simple on/off switch, which — combined in large numbers — can perform calculations. Today, a transistor can be as small as 7 nanometers, the size of around 60 atoms(!) Big players, the likes of Intel and AMD, are rushing to further decrease the size of these transistors, in order to fit more of them within a confined space and produce faster computers.
One could wonder; is it even physically possible to further decrease transistor size and where does it end? For now, it’s still possible, but there is a certain threshold. When a transistor is too small, the simple on/off mechanism wouldn’t be able to function properly. Because of quantum mechanics, electrons might be able to pass through the transistor — even when it’s in offstate — which would result in grave calculation errors. To further advance in processing power, we need to explore different methods. The most probable and promising field of research is the notion of quantum computing.
To further advance in computer processing power, we need to explore different methods.
The biggest change that quantum computing brings, is the use of qubits. In contrast to the 0 and 1 state that bits can be in, a qubit can be in superposition (which means being in both states simultaneously).
To understand what this encompasses, let’s consider the notion of fixed stateversus potential state. One bit can represent one value at any given point in time, being either 0 or 1. A qubit can hold both these values simultaneously; only when measured it will be observed as either one of them.
This property enables a quantum computer to execute complex computations with a relatively small amount of qubits, whereas a traditional computer would require billions of bits.
Kurtzgesagt made a great video on quantum computing, check it out!
In addition, certain quantum algorithms would be infeasible to run on a traditional computer, but would be relatively easy to run on a quantum computer. Some of these algorithms can be leveraged to break modern encryption schemes, embedded in all the devices and platforms we use.
Why is this significant?
Most cryptographic schemes we know and use today weren’t built to be impossible to crack, but extremely infeasible to crack. It would take today’s most powerful computer millions of years to crack Public Key Encryption, which makes for its security. A quantum computer, using qubits instead of bits, can break such an encryption scheme within mere minutes, which essentially deems them unusable for the near future. It is for this reason that researchers are frantically exploring new encryption techniques for the post-quantum era of computing.
Notable blockchain platforms like Ethereum are built upon the encryption schemes mentioned earlier and their security heavily rely on the rigidity of these encryption schemes. As a case study, let’s analyze the Ethereum blockchain platform and examine its quantum-proofness.
Vulnerability 1: Address generation
In order to participate in the Ethereum network, one needs an address and a private key. First, a public-private key pair is generated with the Elliptic Curve Digital Signature Algorithm (ECDSA). The Ethereum address is then derived from the hash of the Public Key. It is impossible to derive the full public key or private key from just the Ethereum address, so exposing it to a bad actor with a quantum computer would not pose a risk. This is not true for the public key and private key, which are cryptographically linked and can — in theory — be derived from one another.
When a bad actor with a very, very powerful computer is provided with a signed transaction, he is able to retrieve the full public key used when signing the transaction. Upon retrieving the public key, the corresponding private key can be generated by performing a sequence of mathematical equations, starting with generating two secret prime numbers. On a traditional computer, it would be nearly impossible to find these two numbers by guessing. However, a quantum computer using Shor’s algorithm (a quantum algorithm) could — in theory — calculate them with relative ease. Upon finding the two secret numbers, generating the private key is a piece of cake.
Luckily, today’s quantum computers aren’t up to speed just yet. The largest factored number to date is not even close to the number of possible values of a public key on Ethereum (consisting of 64 digits). It’s merely a matter of time before the current methods of cryptographic key generation will be compromised. This vulnerability is not an unknown for the blockchain space and the NIST (National Institute of Standards and Technology) is working on a quantum-proof method for cryptographic key generation, which could be implemented in a future Ethereum protocol upgrade.
Vulnerability 2: Consensus
The Ethereum blockchain is running a PoW (Proof-of-Work) consensus algorithm called Ethash, which is an essential part of the security of a blockchain. For every newly proposed block, the solution to a very complex mathematical problem is attached. Verifying its correctness takes almost no effort and can be done by everyone on the network. In essence, the mathematical problem can be solved by repeatedly guessing a number and hashing that number together with the hash of the new block’s contents. The first computer on the network to solve the problem gets awarded with the mining reward (newly minted Ether) and transaction fees. To find a solution to the problem, a traditional computer would take at most 2^(n) steps. A quantum computer could solve such a mathematical problem much faster by utilizing Grover’s algorithm (a quantum algorithm), which would bring the amounts of computational steps down to 2^(n/2). This is an incredible advancement, but it would still take an unfeasible amount of time to find a solution to Ethash’s mathematical problem. In theory, future advancements in hardware might change this.
Luckily, the Ethereum Foundation is aiming to have replaced PoW with PoS (Proof-of-Stake) by 2020. The protocol upgrade called Serenity will introduce this change, which would prevent quantum computing from damaging the network by leveraging Grover’s algorithm. Ethereum’s implementation of PoS — called Casper — achieves consensus by requiring users to stake an amount of their cryptocurrency in order to propose new blocks and no longer involves this mathematical problem mentioned earlier. This removes the notion of power from those with a lot of computational power, which strongly benefits the degree of decentralization within the network and solves the quantum computing problem before it even arises.
Conclusion
Quantum computing poses a significant risk but isn’t likely to disrupt the security of public blockchain platforms if we’re prepared for its uprise. At the time of writing, the Ethereum network’s consensus protocol is theoretically vulnerable to attacks involving quantum computers, but this vulnerability is likely to be solved in the short term. A big unsolved hurdle is the method currently used for cryptographic key pair generation, which is at risk of being cracked by quantum computing.
As long as you stay informed, you probably won’t ever lose your crypto funds to quantum attacks. ¯\_(ツ)_/¯
Should you be worried? Probably not. A lot of smart people and scientific institutions are working on cryptographic schemes for the post-quantum era and the advancements in quantum computing hardware are slow. What you should do is stay informed on the advancements of these developments in quantum computing and quantum-proof cryptography. In addition; make sure you stay informed on protocol upgrades of the blockchain platforms you use, which might require you to take action such as generating a new key pair using a newly introduced encryption scheme.
A bit about me: I’m a Blockchain Engineer at Kryha and I study computer science at the University of Amsterdam. I’m very interested in the notion of quantum computing and its potential impact on security of decentralized platforms.
Kryha is a blockchain studio, where we help organizations understand and engage with blockchain technology. We’re a multidisciplinary team of young blockchain enthusiasts, working closely together with our clients in order to guide them through the process of ideation to development.
We co-design viable and feasible blockchain concepts, then turn them into reality by building working prototypes.
Want to explore the possibilities of blockchain for your business? Visit our website and get in touch!
