Popular Science | The Cryptography of Bitcoin System and the Impact of Quantum Computing

In 2008, a person under the pseudonym Satoshi Nakamoto published a peerless paper entitled "Bitcoin: A Peer-to-Peer Electronic Cash System", creating a virtual digital currency called Bitcoin. Speaking of blockchain.

First, the cryptographic technology of the Bitcoin system

1. Image representation of the Bitcoin system

Visual representation of the Bitcoin system

As shown in the figure above, each node in the Bitcoin system is a separate computer, each block is a storage space on the corresponding computer, and each block records a bitcoin transaction record for a period of time. Between blocks, a timestamp and a one-way function called a "hash function" are used to ensure that the recorded data stored on the relevant nodes cannot be tampered with. The Bitcoin system distributes transaction record data through a point-to-point network, that is, a P2P peer-to-peer network, and stores it on all nodes in the entire network. Through this high degree of data redundancy, the entire network consistency of data is guaranteed from another level.

• Japanese financial giant SBI teamed up with Germany's second largest stock exchange, hoping to "create global digital asset demand"
• Where will the blockchain go in 2020? Outlier Ventures shared 12 predictions
• Panoramic scan security incidents in 2019: 28 exchange cases involving 1.3 billion U.S. dollars

The Bitcoin system is a distributed system. This distributed system can solve problems such as the failure of a central node that may exist in traditional centralized information systems, the tampering of recorded data, and insufficient trust of other nodes in the central node. The Bitcoin system can be regarded as a distributed linked ledger, and each block is a ledger. This system is based on a distributed consensus algorithm to decide who will keep the books. The consensus algorithm in the Bitcoin system is POW, which is the proof of work, and the node that obtains the right to book will get a certain amount of Bitcoin given by the system. The ledger is linked according to the rules determined by the consensus algorithm. The current ledger contains the hash value of the previous ledger. All transactions are traceable in this ledger.

2. Blockchain and cryptography

Cryptography is the core technology of the Bitcoin system and the cornerstone of the secure operation of the blockchain system. Once the relevant cryptographic algorithms are cracked, the system security of the blockchain will no longer exist, and its data will not be tampered with and will disappear.

Cryptographic algorithms are used in multiple links in the Bitcoin system, including various commonly used encoding algorithms, hash algorithms, and signature algorithms. These algorithms play an important role in constructing the Bitcoin system and ensuring the normal operation of the Bitcoin system. The two most important cryptographic algorithms for constructing the Bitcoin system include hash functions and asymmetric cryptographic algorithms.

3. Cryptography used in the Bitcoin system

The Bitcoin system or blockchain technology is not a single technology. Even at the level of cryptography, it also includes a variety of technologies such as asymmetric cryptographic algorithms, hash functions, and secure multiparty computing.

(1) Asymmetric cryptographic algorithm

Schematic diagram of asymmetric password encryption process

Traditional symmetric cryptographic algorithms need to share the same session key when transmitting secret information. The sender of the secret information uses this session key to encrypt the information for transmission, and the receiver of the secret information also needs to use the session key to decrypt the received secret information and restore the plaintext. This session key also needs to be transmitted confidentially through a secret channel in advance, which is difficult or even impossible in many cases.

Asymmetric cryptography is also called public key cryptography. It refers to the existence of a pair of mathematically related keys. One of the keys is used to encrypt the data, and the other key can be used to decrypt the data. Among these keys, the public key is called the public key, and the private key is called the private key. The public key is like a bank account, and the private key is like the password of the account or the signature of the account owner.

A and B use asymmetric cryptographic algorithms for information transmission. If this information is secret, A can use B's public key to encrypt the information and then send it. Anyone can receive the encrypted information, but only B can decrypt this information with his private key and restore the plaintext.

If A sends a message to B, before sending, the message is encrypted with A's private key, and anyone can decrypt it with A's public key. This behavior proves that this message was sent by A, not by others. This action is called digital signature in cryptography.

The valid transaction data on the blockchain includes the private key signature of the transaction initiator, and the signature of the transaction can be verified with the public key of the transaction initiator. The public key can be calculated from the private key by an algorithm, but the private key cannot be derived from the public key.

(2) Hash function

Hash function diagram

Hash functions are a class of one-way functions that can convert input data of any length into a set of fixed-length output data through this algorithm. This function is easy to verify, but difficult to crack. Under normal circumstances, given any x as input, it is very easy to calculate the output hash value y, but it is difficult to calculate x from y in reverse. In addition, with a small change to x, the change in y will be extremely obvious.

In addition to the original data or transaction records, the data on each block in the Bitcoin system also includes the hash function value of all data on the previous block. The Bitcoin system uses a double SHA256 hash function, that is, all data on the previous block is calculated twice using the SHA256 hash function, and then the binary number with an output length of 256 bits is stored in the next blockchain area Block header.

(3) Secure Multiparty Computing

Secure multi-party computing is used to solve the collaboration problem of a group of distrusting parties in protecting their privacy. For secure multi-party calculations, it is necessary to ensure the independence of the inputs of the participants and the correctness of the calculation, while not disclosing the input values ​​to other members participating in the calculation. In layman's terms, secure multi-party computing means that in a distributed network, multiple users each hold some data input. They hope to complete the calculation of these data together. At the same time, each user cannot know other users except the calculation results Any input information.

Smart contracts based on Ethereum have been able to implement on-chain computing. But Ethereum's on-chain data are all open and transparent, and anyone can get this data, which is why Ethereum has been slow to enter the enterprise and personal financial application fields. The essence is that Ethereum lacks support for multi-party secure computing and cannot protect the privacy of multi-party data computing.

4.Mining Principles of the Bitcoin System

In order to keep the system running, the Bitcoin system will give bookkeepers a certain amount of Bitcoin as a reward. In order to get bitcoin rewards, many people will participate in the bookkeeping contest. Therefore, whoever keeps books needs to compete. Those who participate in the Bitcoin bookkeeping competition are called miners.

The mining of the Bitcoin system is simply that all miners do the same hash operation on the current block. Once the hash value that meets specific requirements is calculated, it can be broadcast to the entire network. After other people have verified that this person's operation is correct, they believe that this person has obtained the bookkeeping right of the current block.

The block header data structure of each block in the Bitcoin system is as follows.

Structure and size of the block header

Most of the information in the block header is fixed or calculable before mining.

• version number. Depending on the Bitcoin client, it will not change for a period of time.

• The hash value of the previous block. It is the result of calculation on the previous block.

• Merkle_root. A hash value obtained by performing a hierarchical hash operation on all transactions in the current block in a binary tree manner.

• time block generation time. It is also the current time at the time of packing. The specific number refers to the time from 00:00:00 on January 1, 1970, GMT, and it does not need to be precise.

• Target-bits. It is determined by reference to the average generation time of blocks generated in the last two weeks, which is adjusted by the system, and is generally about 10 minutes.

• nonce random number. A number that can be adjusted by mining, a 32-bit binary number.

• With a message. Refers to the postscript after each transaction in the block. This postscript can also change the merkle root, so there are more possibilities to find the results that meet the requirements.

The algorithm for Bitcoin mining can be expressed as:

Bitcoin mining algorithm

In this algorithm, the previous part defines the data structure of the blockchain, and the latter part is to traverse the random numbers until a qualified hash value is found.

Blockchains are actually linked together through block headers. The bitcoin block header diagram below explains the composition of the blockchain and blocks.

Schematic diagram of the relationship between the Bitcoin blockchain and the block header

Bitcoin's mining process can be summarized as:

The miner first verifies the transaction, removes the problematic transaction, and then chooses which transactions are packaged into the block through a set of custom criteria. For example, if the ratio of the transaction cost to the byte size occupied by the transaction exceeds a certain threshold as a judgment criterion, eligible transactions are considered profitable. Of course, miners can also choose to specifically join a transaction, or deliberately ignore certain transactions.

If mining is performed through a mining pool, the mining server will screen transactions and assign an independent task to each participating mining machine. The difficulty of this task is less than the total mining difficulty, and the calculation of the small difficulty is completed, that is, the workload of the participation is confirmed. The calculation problem of each different miner will not be repeated. When one of the miners successfully mines, the other miners will get the total revenue according to the workload distribution.

Once the transaction data is screened, sorted in time, hashed one by one, and reduced by layers. Through these transactions, a Merkle tree can be calculated, and a unique hash value can be determined. This is the root of the Merkle tree. Changes in any node in the Merkle tree will cause changes in the Merkle root. This value can be used to verify whether the transaction data in the block has been changed.

Merkle tree diagram

Second, quantum computing and quantum algorithms

Quantum computing and quantum algorithms

Quantum computing is a new computing model based on the principles of quantum mechanics for efficient computing. It can use the superposition, entanglement and coherence of quantum to realize parallel computing of quantum.

In 1982, American physicist Feynman proposed the concept of quantum computing. However, due to the uncertainty principle of quantum states and the susceptibility of quantum systems to noise, quantum operations are prone to errors. In 1994, American computer expert Shor demonstrated that quantum computers can quickly decompose large factors and realize the first set of quantum algorithm coding. Quantum computing and quantum computer research only entered the experimental era. In 2009, the National Institute of Standards and Technology developed the world's first universally programmed quantum computer.

Classic bits have two states, 0 and 1. The difference between qubits and classic bits is that a qubit can be in a state other than 0 and 1 like a classic bit. It can also be in neither 0 nor 1. This state is called the superposition state. The quantum superposition state is one of the key characteristics that determines that quantum computing is different from classical computing. It is also the theoretical basis of quantum parallel computing. With the same number of registers, the amount of information that a quantum computer can record is exponentially more than that of a traditional computer. In terms of computing speed and information processing capabilities, traditional computers cannot match. Quantum parallel computing embodies the most important advantages of quantum computing.

Quantum algorithms are an important part of quantum computing science. In 1989, Deutsch first proposed the Deutsch quantum algorithm, which first demonstrated the parallel characteristics of quantum computers. In 1994, Shor proposed a large number prime factorization quantum algorithm and implemented the algorithm's quantum coding. Later, the Grover database search algorithm and quantum intelligent algorithm One after another was proposed. The quantum search algorithm based on Grover and the quantum Fourier transform algorithm based on Shor are currently more mature quantum algorithms.

2. The security of quantum cryptography

The theoretical basis of quantum cryptography is quantum mechanics. Information is encrypted and protected using physics principles to create a secure communication channel.

Compared with traditional mathematics-based cryptography, quantum cryptography has unconditional security and detectability to eavesdroppers, and has great development prospects.

The security of quantum cryptography is based on the following three basic laws of quantum mechanics.

The first is Heisenberg's uncertainty principle. Due to the volatile nature of the quantum, the position and momentum of microscopic particles at the same time cannot be measured with the same accuracy at the same time, only one of them can be accurately measured.

The second is the quantum unclonable theorem. Any unknown quantum state of a quantum system cannot be cloned into another quantum system without being destroyed. That is, the measurement must change the quantum state, so that both parties to the communication can detect whether the communication has been eavesdropped.

The third is the principle of uncertainty or the principle of measuring collapse. If the quantum state of a particle is a superposition state, the measurement of the quantum state of the particle will affect the quantum state itself, causing it to collapse to one of its eigenstates, and the superposition state of the particle cannot be measured, so the measurement will Leave traces.

The security of quantum confidential communication does not depend on the difficulty of mathematical calculations, but on the laws of physics, and the basic principles of uncertainty and non-cloning of quantum mechanics. Therefore, it is theoretically impossible to crack and is more reliable.

Quantum cryptography is very different from traditional cryptography. First, traditional cryptographic algorithms are based on a difficult mathematical problem that is limited by current computing capabilities. Quantum cryptography is based on quantum mechanics and is more secure through physics principles rather than mathematical problems. With the rapid development of quantum computing, quantum computing capabilities have made a qualitative leap. It is only a matter of time before traditional passwords are cracked, and their security will be greatly threatened. Second, it is difficult for traditional cryptosystems to prove that keys have not been stolen by eavesdroppers during transmission and distribution. Quantum cryptography can effectively identify the existence of an attacker during the distribution process, thereby ensuring the security of the communication process.

3. The impact of quantum computing on current general encryption algorithms

Although mainstream cryptosystems can still run safely at present, under the potential impact of quantum computing technology, almost all encryption algorithms need to be improved or even reconstructed. In April 2016, the US National Bureau of Standards and Technology predicted that the current major cryptographic technologies will be affected by quantum computing capabilities, as shown in the following table.

Prediction of the impact of major cryptographic technologies on quantum computing capabilities (2016)

 

4. The latest developments in quantum computing

Over the past 30 years, physicists have made tremendous progress in building practical quantum computers.

On October 23, 2019, Google published the experimental results of "quantum supremacy using programmable superconducting processors" in the journal Nature. Google's artificial intelligence quantum team has developed a new 54-bit processor called "Sycamore" that can complete target calculations in 200 seconds. It takes 10,000 years for the world's fastest supercomputer to accomplish the same goal calculations.

Rival IBM immediately responded to Google's "declaration." In a blog, IBM said that Google overestimated the difficulty of computing projects. What Google claims to be a classic computer requires 10,000 years to perform, but it can be completed in 2.5 days. However, 2.5 days and 200 seconds are not the same order of magnitude after all.

Blockchain security is based on the security of cryptographic algorithms, such as the security of hash functions and the security of elliptic curve cryptographic algorithms. The emergence of quantum computers will seriously threaten the security of the blockchain at the level of the underlying cryptographic algorithm, and many blockchain systems such as Bitcoin and Ethereum will be impacted.

The impact of quantum computing on blockchain

The blockchain security protocol represented by Bitcoin involves two types of cryptographic technologies. One is the hash function used in Bitcoin's "mining" process, and the other is an asymmetric password that provides a digital signature on the blockchain. The algorithms used are SHA-256 hashing algorithm and Elliptic Curve Digital Signature Algorithm (ECDSA). SHA-256 is mainly used to generate wallet addresses from public keys and proof of work (PoW) during mining. ECDSA is mainly used to generate private keys and public keys, and to sign and verify signatures.

1. The threat of quantum computing to mining

In the Bitcoin system, new Bitcoins are generated through "mining." The mining process is the process by which miners use computers to calculate mathematical problems in the Bitcoin network. The first miner to solve the problem published its answer, which was recorded in the ledger and simultaneously counted in all nodes in the Bitcoin network. After successful mining, the system rewards miners with a certain amount of Bitcoin.

The hash function used in Bitcoin mining is SHA-256. Use SHA-256 to calculate a random number for each block. Although the results are easy to verify, the search process is very difficult. The usual approach is to use brute force search, which means trying different inputs until you find a satisfactory answer.

Grover search in quantum mechanics can theoretically solve this problem. The Grover algorithm has a unique advantage in solving the problem of searching for a specific data from an unordered database. The Grover algorithm makes it relatively easy to find the collision of Hash functions, which means that it will reduce the security of cracking cryptographic hash functions. level.

So, in turn, is it possible to mine using a quantum algorithm? If you use a quantum algorithm to mine, you need a relatively fast quantum hash operation speed and stronger quantum acceleration, but the current level of technology is still difficult to achieve. Researchers at Divesh Aggarwal and the National University of Singapore (NUS) conducted in-depth research on the threat of quantum computers to mining, and published a paper on it in October 2017. They believe that mining ASICs will be faster than quantum computers for at least the next 10 years, but 10 years later, the mining speed of quantum computers will increase rapidly.

2. The threat of quantum computing to asymmetric cryptographic algorithms

Asymmetric cryptography is used to authorize transactions in the Bitcoin system. Asymmetric cryptography assigns a public key and a private key to all users in the system. The public key can be widely shared, and the private key is only known to the key owner. With a given private key, it is easy to deduce the corresponding public key, but it is very difficult to deduce the private key from the public key.

The asymmetric cryptographic algorithm used by Bitcoin is the Elliptic Curve Digital Signature Algorithm (ECDSA), which uses secp256k1 to generate keys. The algorithm guarantees that Bitcoin can only be used by legitimate owners.

Elliptic curve cryptography is vulnerable to attack in quantum computing. The Shor algorithm can theoretically be easily modified to decrypt messages with elliptic curves. There are already several research cases in the world that use the Shor algorithm to attack ECC, both theoretically and practically. Some experts predict that by 2027, quantum computers will be able to crack the keys, and the time required for a quantum computer to crack an encrypted signature is estimated to be 10 minutes. But at present, in order to realize the quantum computing attack on ECDSA, a certain number of qubits are required. Some foreign media reported that it is 4,000. The current quantum computer is far below this level.

3. The impact of Google's quantum computer on cryptographic algorithms

The current level of Google's quantum computer can basically be judged from the following aspects.

(1) Google's quantum computer is not yet a true quantum computer, and it cannot achieve all quantum transformations. Only those transformations in cracking cryptographic algorithms can have an effect on cryptographic algorithms.

(2) The number of qubits that Google Quantum Computer can achieve is still very small. The tasks it accomplishes can also be done on large traditional computers.

(3) After the practical application of quantum computers, it is possible to threaten public key algorithms based on discrete logarithm and large composite factorization design.

(4) Quantum computers have no fatal threat to symmetric cryptographic algorithms. From the perspective of time complexity, as long as the key length is doubled, the time complexity of symmetric cryptographic algorithms against quantum computers is the same as that of electronic computers.

In the long run, practical quantum computers running Shor's algorithm can crack asymmetric cryptographic algorithms such as RSA and ECC. Google's 53-qubit quantum computer, for a problem that has no application value, has verified that the quantum computer is more powerful than existing classical computers. However, at present, Google's quantum computer cannot pose a threat to the security of classic passwords (including asymmetric passwords). In order to decipher the current RSA algorithm, it is currently estimated that it needs to be able to manipulate thousands of logical qubits stably, and correspondingly to manipulate millions of physical qubits. There is still a long way to go to achieve this goal.

4. Application of post-quantum cryptography in blockchain systems

Although the current local encryption algorithms used in blockchain applications are secure, this does not mean that blockchain practitioners can rest easy. It is important to study cryptographic algorithms that are still secure for blockchain systems after the advent of quantum computers. Post-quantum cryptography, as a cryptographic technology that will gradually replace current public key cryptographic algorithms such as RSA, Diffie-Hellman, and elliptic curve in the next 5-10 years, is being valued by more and more people.

Post-quantum cryptography, also known as quantum-resistant cryptography, is a cryptographic algorithm considered to be resistant to quantum computer attacks. The development of this type of encryption technology adopts the traditional method, that is, based on the difficult problems in specific mathematical fields, it can be applied to network communication through research and development of algorithms to achieve the purpose of protecting data security.

The application of post-quantum cryptography does not rely on any quantum theoretical phenomenon, but its computational security is believed to withstand any form of quantum attack currently known. Post-quantum cryptography is applied in the blockchain system to ensure that the blockchain is still secure after the advent of quantum computers.

Asymmetric cryptography is a key area for the development of post-quantum cryptography. For example, with the introduction of the Shor algorithm, asymmetric cryptographic algorithms including RSA, ECC, and DH key exchange technologies have been theoretically proven to completely lose security. Compared with symmetric cryptosystems, upgrade measures can be taken to cope with quantum threats. Asymmetric cryptography must be reconstructed by a new method, which has become the focus of post-quantum cryptographic technology development.

The current international post-quantum cryptography research mainly focuses on lattice-based cryptography, code-based cryptosystems, multivariate cryptography, and hash-based signatures. And other cryptographic algorithms. Of all the computational problems considered to have the potential to resist quantum threats, lattice-based cryptosystems have received the most widespread attention in the past decade.

We will continue to update Blocking; if you have any questions or suggestions, please contact us!