Dry goods | Can quantum computers really destroy blockchain networks?
Author: Neo Ge
Check: Junkai Zeng
Recently, many friends asked me questions about quantum computers. One of the biggest concerns is that quantum computing will rely on strong computing power to make cryptocurrencies no longer encrypted and even destroy the blockchain network. First answer: No. But to understand this, you need to understand what is quantum computing and blockchain cryptographic algorithms.
This article is particularly grateful to Junkai Zeng for the technical support he provided. He is not only my old classmate, but also a PhD in physics from Virginia Tech. His research direction is quantum computing. He currently works for a quantum company invested by Sequoia in LA.
To understand quantum computing, we need to understand what classical computing is. We need to know that a bottleneck encountered in the development of classic computers is Moore's Law, which means that the number of transistors that can be accommodated on an integrated circuit doubles every two years. This has led to a smaller and smaller transistor. When it is as small as about 2 nm, since a transistor on the 2 nm level can only hold 10 atoms, the behavior of electrons will no longer obey traditional semiconductor theory, but will follow quantum mechanics . With the increase of transistor integration, the heat generated by the chip will become higher and higher. These negative effects have severely hindered the development of classical computers. With this concern, people have come up with solutions such as photonic computers, biological computers, quantum computers, and so on. Moore's Law-Number of transistors on integrated circuit chips (1971-2018)
Why do people think of baryon computers so much?
First of all, we need to know that the operations of classical computers are performed by logic circuits. Binary ones and zeros represent logical operations in computers, also known as Boolean algebra. 1 means true (high level), 0 means false (low level). The most common logic operations are AND, OR, NOT. For example, true and true results are true, true and false results are false; non-true is false, non-false is true. These operations are performed by logic gates, which are reversible and irreversible. For example, the NOT gate inputs a 1 (bit true) and the output is a 0 (bit false), so the NOT gate is a reversible gate, because we can invert the input 1 (bit true) by outputting 0 (bit false). But if the output of an AND gate is 0 (bit is false), then there are three possibilities for the input bits, which are 00, 01, and 10, and we cannot explicitly map back to the input one by one, so the AND gate is an irreversible gate. Originally, two bits of information became one bit of information after passing through the AND gate, and one bit of information was dropped here.
Landauer principle
Rolf Landauer
In 1961, IBM engineer Rolf Landauer discovered that every bit of information erased required a thermodynamic cost, that is, at least kTln2 of heat was generated, and no thermodynamic cost was required to write the information. Where k is the Boltzmann constant and T is the ambient temperature. This is the famous Landauer principle, through which we know that information also has physical properties. Classic computers are basically irreversible, so classic computers will generate more and more heat. This is Landauer's conclusion on thinking about Maxwell's demon: Because processing information has to pay a price, and the memory of the demon cannot be infinite, it always deletes some memory and causes entropy increase, so the demon cannot exist .
So people thought that if the irreversible operation in the classical computer was converted into a reversible operation, then the problem would not be solved. Theoretically, an operation called unitary transformation-a processing method for quantum states, placed on a classical computer just to solve the problem of heat dissipation. However, although classical computers are good at problems of differential equations, that is, to simulate classical physical systems. However, if differential equations are still used to describe quantum physical systems, classical computers can hardly shoulder this task. Therefore, physicists such as Feynman proposed to directly convert classical bits into qubits, and directly use quantum to simulate quantum systems. (What we heard in the video at the beginning of the article was Richard Feynman's voice)
The Natural Advantage of Quantum-Parallel Computing
In classical computers, we use binary to increase computational efficiency. If you want a classic computer to calculate 100 + 100, first convert the decimal 100 to the binary 1100100. In a classic computer, 7 different states of transistors are needed to represent the binary 1100100. In simple terms, a transistor is a bit, and can only represent 1 or 0 (high or low). Quantum computers are different. A quantum two-state system is a bit, called a qubit. A two-state system is like the spin of an electron and the polarization of a photon. The most popular explanation is Schrödinger's cat. When Schrödinger's cat did not observe, from the perspective of quantum mechanics, it was both dead and alive, in a superimposed state of dead and alive. This state follows the principle of quantum state superposition. If we replaced the transistor in a classic computer with a Schrödinger's cat, a Schrödinger's cat could represent 1 and 0 at the same time, instead of 1 or 0 in a classic computer. Two Schrödinger's cats can represent the four states of 00, 01, 10, and 11, whereas the two bits in a classic computer can only take one of these four states.
So for n bits, classical bits can only represent one number, while qubits can theoretically represent 2 ^ n power numbers at the same time. This is the biggest difference between classical computers and quantum computers. 2 ^ n This exponentially increasing crushing temptation has led to so much interest in quantum computers-the benefits of natural parallel computing.
Schrodinger's cat
How to implement a quantum computer
Difficult point 1: What do you use for qubits?
From a physicist's perspective, two-level quantum systems can theoretically be used as qubits. For example, the spin of an electron is in a superimposed state when it is not measured. Once measured, an eigenstate that is either up or down will appear.
Electron spin
Difficult point 2: Algorithm of quantum computer? Because the algorithm is the soul of the computer, and the classic algorithm is only suitable for classic bits, even if the quantum chip is well made, the classic algorithm cannot be used on the quantum chip. In 1994, Peter Sauer of Bell Labs published the Sauer algorithm that can perform prime factorization of large numbers.
Peter Sauer
The prime factorization problem is an NP problem, that is, its complexity cannot be completed in polynomial time in the classical algorithm. The complexity of the prime factorization of a general algorithm is O, that is, e ^ n, where n refers to the number of bits in which this number is represented in binary. At present, it takes about 150,000 years to perform a 300-digit (decimal) prime factorization using the fastest classical supercomputing. This is why the prime factorization of large numbers can be used for encryption, because it is almost impossible to calculate which two prime numbers are multiplied by classical computers to decrypt. But the Sauer algorithm can reduce the complexity to (logN) ^ 3, which means that the Sauer algorithm turns a NP problem into a P-type problem. Using the Sauer algorithm to perform a 300-digit prime factorization also takes less than one minute in theory.
In addition, Sauer also solved a problem that has puzzled physicists for more than a decade. If the Sauer algorithm uses qubits for calculations, the result is still a bunch of qubits. We need to measure the results. However, Schrödinger's cat told us that the probability of measuring cats' lives is 50% each, so theoretically the results are random.
Sauer tells us that by using the Sauer algorithm, the required data will be coherent and coherent, and the unwanted data will be coherently destructive. The probability of the final measurement being correct is one. Since the confidential data of banks and governments are now encrypted based on the prime RSA algorithm, since the Sauer algorithm was published in 1994, quantum computing has aroused strong interest from governments around the world. Even the United States Defense Advanced Research Projects Agency DARPA has joined the battle (DARPA has proposed and invested in the Internet, Unix systems, Global Positioning System GPS, etc.).
In 2001, Chinese researcher Isaac Zhuang of IBM and their research team demonstrated the Sauer algorithm through nuclear magnetic resonance, that is, a molecule composed of 5 fluorine atoms and two carbon atoms, using the nuclear spin of each atom to As a qubit, 7 qubits are equivalent to 2 ^ 7, which is 128 classic bits. Using this mini quantum computer to perform the prime factorization of 15 using the Sauer algorithm, the results given are 3 and 5, which successfully proved that the Sauer algorithm is feasible. It was later proved that the Sauer algorithm can also be used to solve discrete logarithm problems. Quantum computer algorithms include Grover, QAOA, and VQE algorithms in addition to the Sauer algorithm. We will mention the Grover algorithm again later.
Difficult point 3: How to maintain quantum coherence? The coherence of the quantum is difficult to maintain. Even if the quantum in the superposition state is not measured, it will entangle with the surrounding environment and then become a certain state, that is, it will become a classic, which is commonly known as the collapse of the wave function. The process is called quantum decoherence. In order to resist the effects of quantum decoherence, we mainly have two methods: Quantum entanglement
Quantum error correction ; similar to a classic computer, at the expense of resources, such as using 8 qubits as one, one or two decoherences does not matter, and correct a few decoherent quanta. There are two problems with the use of error correction codes: one is that the operation of each step of quantum computing must be lower than a certain ratio so that errors can be corrected, for example, the error rate is less than 1%; the other is that error correction codes require a lot of physical layers To encode a qubit at the logical level, these have brought great obstacles to the realization of quantum computing at the hardware level.
Better technology to manipulate quantum systems : Because of some properties of quantum mechanics, even if the same operation is implemented, controlling qubits in different ways on the physical level will bring very different fidelity. By using better ways to optimize these operations, the error rate can be controlled below the threshold for quantum error correction, paving the way for more general quantum error correction.
At this point, there is no problem in theory for quantum computers. As for the physical level, how and what do quantum chips do. This is the main research direction of the major institutions at present, to ensure that qubits are integrated while maintaining coherence. Typical hardware implementation solutions for qubits include optical systems, semiconductor quantum dots, superconducting circuits, cold atoms, ion wells, and so on. Industry research institutes such as Google, IBM, and the Ali Dharma Institute are dedicated to the realization of quantum chips through superconducting circuits. In September this year, Google announced that it had successfully implemented "Quantum Supremacy" with a processor containing 53 effective qubits. It should be pointed out that "quantum hegemony" refers to the realization of quantum computing that can not be done with classic computers on certain issues, and the realization of "quantum" over "classic" hegemony, which is a new technology Hegemony over old technology, rather than an enterprise or research institution leading the world, has created hegemony over other enterprises and research institutions.
Blockchain encryption algorithm
Here, we take Bitcoin as an example to introduce the encryption algorithm of the blockchain. There are two types of Bitcoin's encryption algorithms: elliptic curve algorithm, SHA256 hash algorithm, and RIPEMD160 hash algorithm. The general process is as follows: Private Key-> Elliptic Curve Algorithm-> Public Key-> SHA256-> RIPEMD-> SHA256-> SHA256-> Address The one-way arrow means that the algorithm cannot be reversed in the classic calculation. The public key cannot be reversed from the address, and the private key cannot be reversed. Since quantum computing is the irreversibility of classical computing to be reversible, for the convenience of explanation, we push backward from the address.
Hash Algorithm Among the two hash algorithms used by Bitcoin, SHA256 is an algorithm subdivided under SHA-2. It is a cryptographic hash function algorithm standard developed by the US National Security Agency; RIPEMD (RIPE Message Digest) is also a hash function. For symmetric encryption and hash functions, there is a quantum attack, but it is less dangerous. The Grover algorithm can only reduce the difficulty of 2 ^ 256 under classic calculations to 2 ^ 128 which is still astronomical. However, from the public key to the address requires 1 RIPEMD and 3 SHA256 hash operations, so it is disruptive for symmetric encryption. Before quantum algorithms are born, we don't have to worry too much.
Because bitcoin mining uses the SHA256 algorithm, if a quantum algorithm far superior to the Grover algorithm is born in the future, and as time goes by, quantum computers will become faster and cheaper, and then quantum computers will become cheaper. It will indeed surpass classic computers in Bitcoin mining. But this process is like going from CPU mining to GPU mining to ASIC mining, we don't have to worry about it at all.
The elliptic curve algorithm has only one barrier to push back the private key from the public key—Elliptic curve cryptography, or ECC for short, is an algorithm for establishing public key encryption, that is, asymmetric encryption. From a mathematical perspective, an elliptic curve can be represented as:
One of elliptic curve is Bitcoin's elliptic curve digital signature algorithm (ECDSA) based on secp256k1 curve. Since the elliptic curve algorithm relies on the discrete logarithm problem, and the above-mentioned Sauer algorithm can be used to solve the discrete logarithm, a quantum computer with a certain effective qubit theoretically can solve the elliptic curve of Bitcoin. Algorithms pose a threat. However, the security of the secp256k1 curve is 2 ^ 128, so even if the Sauer algorithm reduces its complexity to 128 ^ 3, theoretically, a quantum computer that attacks the secp256k1 curve must have at least 1500 logical qubits. Considering the use of quantum error correction, the physical qubits actually required will be much higher than this number.
In September this year, Google announced the largest general-purpose quantum computer to date with only 53 physical qubits. It has an extremely high error rate, and it can only operate in laboratory conditions near absolute zero. At the same time, the superconducting chip used by Google naturally has many problems in scalability, so how to add more qubits while maintaining controllability will be a very big challenge in the foreseeable future. Although it cannot be fully predicted how fast quantum computing will evolve, Bitcoin's 256-bit ECDSA key is expected to be secure until at least 2040.
Bitcoin itself already has some built-in anti-quantum properties. If you have a good Bitcoin usage habit, that is, a wallet address is used only once, then your public key will only be broadcast to the entire network when you spend Bitcoin. . At this time, the quantum computer will only have a very short time to crack your private key, that is, the time from when the transaction is sent to when the transaction information is added to the block.
Let's assume that you don't have a good bitcoin usage habit, the quantum computer development is advancing by leaps and bounds, and all the common public key algorithms are broken. Another killer bitcoin is to upgrade its encryption algorithm. As we all know, if technical means can crack a kind of password, it will inevitably produce a kind of password that cannot be cracked. Currently, among the public-key encryption algorithms for quantum security, Bitcoin experts tend to prefer encryption systems based on Lampport signatures. Although the calculation of Lamport signature is very fast, it also has two main disadvantages:
The signature will be very large, at least a few kB (40-170 times larger than now), which will be very detrimental to the overall scalability of Bitcoin.
When creating each key pair, you need to set a valid maximum number that can be signed with this key. Signing beyond this number will no longer be secure. But if you only use each address once, this is not a big problem.
In addition, in the study of post-quantum cryptography by cryptographers, the supersingular elliptic curve homology key exchange (SIDH) is also expected to replace the current conventional elliptic curve key exchange (ECDH). Cryptography based on high-dimensional vector space, that is, lattice cryptography will also increase the difficulty of deciphering by another cosmic order, which is enough to counter quantum computing. The new public key algorithm will be added to Bitcoin as a soft fork, and Bitcoin users only need to send their Bitcoins to the newly created address to achieve quantum security.
Cryptography and computer science When we study the challenges of quantum computers for blockchain, it is difficult not to think repeatedly about the relationship between cryptography and computer science. Historical facts are always amazingly entangled and similar. Deciphering a code was originally the driving force behind the birth of computers. During World War II, Ellen Turing, the father of computer science and artificial intelligence, was employed by the Royal Navy to decipher German secret military codes. The Nazi military at the time had a sophisticated and sophisticated communications security system-the Enigma cryptographic machine. It consists of a series of rotors that are constantly changing randomly, and its complexity is as high as 100 million yuan, which is extremely difficult to overcome by means of deciphering at the time. Turing used his deciphering machine bombe to first decode Enigma, and then decode almost all levels of communication encryption systems used by the Nazi military at the time, including the Tun password. This allowed the Allies to know German military command and planning, and helped the Allies defeat the Nazi Germans at least two years in advance, ending the Second World War.
Alan Turing
Turing proposed a mathematical logic machine that abstracts human computing behavior, that is, Turing machine. Later, the father of modern computers, Feng Neumann, completed the realization of the Turing machine using the Feng Neumann structure. The Turing test named after him is widely used as a test method to determine whether a machine is intelligent. Turing's brilliant achievements in mathematics and logic also set a grand blueprint for the development of computers and the entire digital age. In recognition of his pioneering contributions, the Nobel Prize in the computer world named after him-the Turing Award was formally established in 1966 as the highest award in the field. For the upcoming quantum era, as blockchain practitioners, we should welcome it with awe and anticipation. The value of quantum computers lies in solving typical NPC problems and other problems such as trisomy, seven bridges, protein folding, earthquake prediction, and weather forecasting. Quantum computers are not a panacea. They cannot replace classical computers.
References [1] Martin Roetteler, Michael Naehrig, Krysta M. Svore, and Kristin Lauter. “Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms” Microsoft Research, USA (2017): 1706.06752
[2] Matthew Amy, Olivia Di Matteo, Vlad Gheorghiu, Michele Mosca, Alex Parent, and John Schanck. “Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3” Quantum Physics (2016): 1603.09383
[3] Changchang Sun, Haitao Quan. "Physical Limits of Maxwell's Demon and Information Processing" Physics · 42 Vol.11 (2013): 10.7693
[4] Craig Gentry. “Fully Homomorphic Encryption Using Ideal Lattices” Stanford University and IBM Watson (2009): cs.cmu.edu
[5] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends et al. “Quantum supremacy using a programmable superconducting processor” Nature 574, no. 7779 (2019): 505-510
[6] I. Stewart, D. Ilie, A. Zamyatin, S. Werner, MF Torshizi and WJ Knottenbelt. “Committing to quantum resistance: a slow defence for Bitcoin against a fast quantum computing attack” Royal Society Open Science 5, no . 6 (2018): 180410
[7] Divesh Aggarwal, Gavin K. Brennen, Troy Lee, Miklos Santha, and Marco Tomamichel. “Quantum attacks on Bitcoin, and how to protect against them” Quantum Physics (2017): 1710.10377
Moore's Law-Number of transistors on integrated circuit chips (1971-2018) 
Quantum entanglement 
