We are discovering a new reality. Things that were once unimaginable are becoming real and part of our world. Achieving quantum supremacy is one of the monumental breakthroughs that will revolutionize history. But, what effect will it have on Ethereum? Cryptographer and blockchain researcher Amira Bouguera explains in the following article.
“Science offers the boldest metaphysics of our age. It is a thoroughly human construct, driven by the faith that if we dream, press to discover, explain, and dream again, the world will somehow come clearer and we will grasp the true strangeness of the universe.”
TL;DR:
Quantum computing has the ability to simulate quantum physics on a computer.
Researchers at Google claimed to have reached Quantum Supremacy.
Yet, there are many years ahead until Ethereum would experience a threat to current cryptographic signatures.
The ECDSA scheme for signing transactions is under threat, but will be replaced during Ethereum 2.0 Serenity update.
Developers are testing various quantum-resistant signature options like XMSS, hash ladder signatures, and SPHINCS to replace ECDSA.
No one knows when the quantum power will strike, but when it does, Ethereum will be prepared.
Our journey to quantum computing begins in 1981 when the brilliant Nobel prize winner Feynman raised the following question at an MIT conference on physics and computation:
“Can we simulate physics on a computer?”
At that time, no one thought it could be possible. This comes back to the definition of physics and the limits of classical computers. Physics is the study of energy, matter, and the interaction between them. Our world, and reality in itself is quantum in nature; electrons exist in multiple states at once, and we can’t model that properly with classical computers. Calculating every possibility is just too much for them, for example:
Molecule with 10 electrons = 1000 possible statesMolecule with 20 electrons = over 1 million possible states
Feynman’s speech and accompanying paper in 1982 is the first work that explicitly discusses the construction of a machine that would operate on quantum mechanical principles. He discussed the idea of a universal quantum simulator, i.e., a machine that would use quantum effects to explore other quantum effects and run simulations.
Tech giants are racing to build the first quantum computer, a device with millions of times more processing strength than all the computers currently on Earth combined. Recently, in an article published in the scientific journal, Nature, Google announced that it has realised what was once thought to be impossible: achieving quantum supremacy.
What is Quantum Supremacy?
To explain quantum supremacy, it’s worth describing how quantum computers work.
In a quantum computer, we have quantum bits (qubits), which can be in state 0 or 1 or both at once while classical computers are being represented by bits, which can be either in the state 0 or 1.
Qubits can be anything that exhibits quantum behavior: an electron, an atom, or a molecule.
Two key aspects of quantum mechanics are superposition and entanglement. These two concepts are the secret behind the quantum computer’s superpower.
Superposition is an extraordinary phenomenon in quantum physics that quantum computers leverage. It allows a particle to exist in two separate states at once, as the result of being linked to a random subatomic event that may or may not occur.
A cat, with a Geiger counter, and a bit of poison in a sealed box. Quantum mechanics says that after a while, the cat is both alive and dead. `
Can a cat be dead and alive at the same time?
We don’t know whether the cat is dead or alive until we look, and when we do, it is either dead or alive, but if we repeat the same experiment with enough cats, we see that half the time, the cat survives and half the time he dies.
When does a quantum system stop existing as a superposition of states and become one or the other?
In quantum physics, the entanglement of particles describes a relationship between their fundamental properties that can't have happened by chance. This could refer to states such as their momentum, position, or polarisation.
Knowing something about one of these characteristics for one particle tells you something about the same characteristic for the other. This means that the person who opened the box in the previous experience is entangled or linked with the cat and that the "observation of the cat's state" and the "cat's state" correspond with each other.
The State of Quantum Computers Today
Today, the use of the term “quantum computers” is no longer limited to scientific journals and physics conferences. Many players are engaged in a battle over who can build the first powerful quantum computer. These include commercial entities such as Google, Rigetti, IBM, Intel, D-Wave, IonQ, and Microsoft. Additionally, virtually all major nation-states are currently spending billions of dollars on quantum computing development and research.
The Race for Quantum Supremacy
Quantum supremacy is the notion of a quantum computer doing something that classical computers simply can not reasonably do. In this instance, the reported Google paper claimed it was able to perform a task (a particular random number generation) on its QC in 200 seconds (3 minutes 20 seconds) versus what would take 10,000 years on a supercomputer.
Google has used Sycamore, its newly developed 53-qubit quantum processor, to achieve quantum supremacy. The purpose of this gate-based superconducting system is to provide a testbed for research into system error rates and scalability of their qubit technology, as well as applications in quantum simulation, optimization, and machine learning.
Although Google’s achievement was a huge step forward into the advancement of quantum computers, significant milestones remain ahead before a commercially viable quantum computer that can be used to solve real-world problems can exist.
Is quantum computing a cybersecurity threat?
Quantum computing is an unleashed power with two sides. On the one hand, it represents a significant breakthrough in fields like science, life-saving medical advances, and financial strategies. On the other hand, it has the power to break our current encryption systems used to protect information.
The security of most cryptographic methods currently in use, whether for encryption or digital signature, is based upon the hardness of solving some mathematical problems.
Let’s take the following examples:
RSA is an algorithm used for encryption and based upon the hardness of solving the factorisation problem (finding the factors of a large composite number is difficult: when the integers are prime numbers)
ECDSA: Is a signature scheme based upon the hardness of solving the discrete logarithm problem.
While computing discrete logarithms and factoring integers are distinct problems, they both are solvable using quantum computers.
In 1994, American mathematician Peter Shor invented a quantum algorithm that cracks the RSA algorithm in polynomial time versus 300 trillion years on a classical computer for RSA with 2048-bit.
ECDSA has shown to be vulnerable to a modified version of Shor's algorithm and is even easier to solve than RSA using quantum computers because of the smaller key space.
A 160-bit elliptic curve cryptographic key could be broken on a quantum computer using around 1000 qubits while factoring the security-wise equivalent 1024-bit RSA modulus would require about 2000 qubits.
How would this affect Ethereum?
Ethereum currently uses elliptic curve based schemes like the ECDSA scheme for signing transactions and BLS for signature aggregation; however, as mentioned above, the elliptic curve cryptography in which security is based upon the difficulty of solving the discrete logarithm is vulnerable to quantum computing and must be replaced with a quantum-resistant scheme.
The hash function SHA-256 is quantum-safe, which means that there is no efficient known algorithm, classical or quantum, which can invert it.
While there is a known quantum algorithm, Grover’s algorithm, which performs “quantum search” over a black-box function, SHA-256 has proven to be secure against both collision and preimage attacks. In fact, Grover’s algorithm can only reduce 𝑁 queries of the black-box function, SHA in this case, to √N, so instead of searching 2^256 possibilities, we only have to search 2^128, which is even slower than algorithms like van Oorschot–Wiener algorithm for generic collision search and Oechslin's rainbow tables for generic pre-image search on classical computers.
Ethereum 2.0 Will be Quantum Resistant
In the Ethereum 2.0 Serenity upgrade, accounts will be able to specify their own scheme for validating transactions, including the option to switch to a quantum-safe signature scheme.
Hash-based signature schemes like the Lamport signature are believed to be quantum-resistant, faster, and less complex than ECDSA. Unfortunately, this scheme suffers from size issues. The size of Lamport public key and signature together is 231 times (106 bytes vs. 24KB) more than the ECDSA public key and signature. So, the use of the Lamport Signature scheme will need 231x more storage than ECDSA, which is unfortunately too large to be practical at this time.
Ethereum developers are testing other quantum-resistant signature options like XMSS (eXtended Merkle signature scheme) signatures used by The Quantum Resistant Ledger blockchain, hash ladder signatures, and SPHINCS.
There are many reasons to switch to hash-based signature schemes like XMSS, as they are fast and yield small signatures. One major drawback is that XMSS signature schemes are stateful, due to their Merkle trees with many one-time signatures. This means the state has to be stored in order to remember which one-time key pairs were already used to create a signature. On the other hand, SPHINCS signatures are stateless as they use few time signatures with Merkle trees, which means no need to store the state anymore since one signature could be used multiple times.
Hash-based RANDAO functions, which are used for random number generation in the beacon chain in Ethereum 2.0, are already believed to be post-quantum.
A Vision for a More Robust Post-Quantum Ethereum 3.0
During Ethereal, Justin Drake from the Ethereum Foundation revealed the 2027 Ethereum 3.0 plan to move from the zk-SNARKs to zk-STARKs protocol. Both techniques allow the prover to convince a verifier about a particular claim by sharing only a proof that backs up the prover’s claim, without sharing any private information. These techniques are normally used as a privacy and scalability method to send confidential transactions on Ethereum or as a replacement of BLS signatures for signature aggregation. However, zk-SNARKS relies on pairings that are not quantum-resistant. zk-SNARKS uses a trusted setup, which runs the risk of being compromised, compromising the entire system, and allowing the generation of false proofs. ZK-STARKs, on the other hand, are quantum-secure as they are based on hash and not pairings. They improve upon this technology by removing the need for a trusted setup.
Conclusion
Google has accomplished a great achievement. This technology will harness the unusual laws of quantum mechanics to bring unimaginable advances in fields like materials science and medicine. Simultaneously, it could also pose the greatest threat to cybersecurity yet. Fortunately, the threat is not yet here. No one knows when the quantum power will strike, but when it does, Ethereum will be prepared.
Developers from the Ethereum community have begun working on alternative cryptographic signature schemes to replace those vulnerable and build a secure, resilient post-quantum Ethereum protocol. Additionally, the National Institute of Standards and Technology (NIST) initiated a process to solicit, evaluate, and standardize one or more quantum-resistant public-key cryptographic algorithms. At the time of this posting, NIST has short-listed 26 algorithms for post-quantum cryptography standardization to advance to the next round of testing.
Amira Bouguera is a cryptographer and security engineer at Consensys Paris. She teaches cryptography Université Paris 8.
Want to learn more about Ethereum 2.0?
Check out our roadmap to Serenity →
Learn more about the Ethereum 2.0 design goals.Words from Ben Edgington →