Bitcoin, as many crypto enthusiasts and crypto evangelists believe, is an immutable system that cannot be altered or destroyed. Computer scientists do not fully agree with this statement, however, because if one of the seven Millennium Programming Goals is solved, then Bitcoin will . . . What will become of the main digital coin after the solution of P = NP?

Why Is This Equation so Important for Cryptography?

The problem of enumeration, or the question of the equality of the complexity classes P and NP, where P is a problem of a simpler level, and NP is a difficult one, has excited all researchers engaged in the theory of computational complexity for more than three decades. In this section of The Theory of Algorithms, we will study such common concepts as time (how many steps to take) and memory (its volume for the task). The problem of equality P = NP lies in the question that if the answer to some problem can be checked quickly enough within the framework of polynomial time (class P), is it true that the answer to this question can be found quite quickly? Does this mean that the solution to the problem is not easier to verify than to find? If someone gives the right answer to this millennium-old problem, then he will change the digital world, because in theory, all algorithmic problems, including those related to the crypto industry, will be solved much faster than they are now, and that someone will receive $1 million from the American Clay Mathematics Institute. For example, NP tasks include cracking ciphers, and today, they can only be solved by searching all possible combinations and selecting the correct code. And if this equation is not equal, then the asymmetry on which Bitcoin is based will remain unsolved.

Graphical representation of the question P and NP. At the moment, the two parts of the system do not intersect and do not unite. They are not equal. But this is only for the time being and is not guaranteed for eternity.

To Break Asymmetry Is to Destroy Bitcoin

The entire crypto ecosystem consists of algorithmic and computational asymmetries because they provide the desired decentralization of the network. Therefore, in order to destroy Bitcoin or altcoins, it is necessary to break these asymmetries. Asymmetry is an inconsistency of one side or the other and does not fulfill the symmetry function f (x) = f (x) along the y-axis. This is directly related to the digital world, because it is based on the production elements of trust, which are established using public-key cryptography, asymmetric cryptography (algorithmic asymmetry), and work proofs, such as the algorithm Proof of Work (computational asymmetry).

Asymmetric cryptography is a system of encryption and electronic signatures in which the public key is transmitted to an observable channel. It occurs when the level of effort to solve the problem significantly exceeds the actions needed to verify the solution of the problem. For example, if we calculate the discriminant of the quadratic equation x^2 + 2x + 3 = 0, then there will be two solutions in the answer, where x = 1 and x = 3. After obtaining this data, you can substitute numbers into the equation and verify that everything is done correctly. That is, in this case, it is easier to check the solution, and then the problem itself. In a more complex mathematical algorithm, it is not so easy to substitute the numbers obtained.

Digitalization involves the creation of a secure electronic lock-and-key system for transactions of Bitcoin and other coins which are based on the Proof of Work consensus algorithm. A secure digital locking system creates the desired result that the whole industry strives for—the security of the network. Without this, there would not be Bitcoin, and the blockchain system would be another unreliable system.

Public key cryptography is used in Bitcoin to sign and protect the UTXO (Unspent Transaction Output) array, since it is almost impossible to verify that a public key belongs to a secret key, knowing only the public key. To break up the asymmetric algorithm for the ECDSA (Elliptic Curve Digital Signature Algorithm), billions of years and the most powerful computing equipment are needed. Therefore, we can say with confidence that human timescales will not allow algorithmic asymmetry to destroy Bitcoin, since the level of effort to solve the problem is high, and the level needed to test the solution is low. But do not forget that public key cryptography is based on one-way functions that do not have scientific evidence to support their security.

One-Way Functions in Bitcoin

Any blockchain system is based on the hypothesis that there is a one-way function for the solution of the problem, which, from the point of view of the theory of computational complexity, is easily calculated for any input value, but it is difficult to find an argument for a given value of the function.

Surprisingly, the existence of unilateral functions has not yet been proven. Because if the assumed function f is one-sided, then it will be almost impossible to find it by definition, but it is fairly easy to verify by calculating f. It follows that P ≠ NP, though no one can prove and understand whether P ≠ NP entails the existence of unilateral functions. Their presence in the blockchain system is an important condition for the robustness of many cryptographic schemes.

In the textbook "Cryptography" by programmer and researcher Nigel Smart, it is said that the one-way function retains its length in the event that the bit length of the value of the function is equal to the bit length of the argument. If this value length is always equal to any length of the argument, then it is called a hash function, which is used to store passwords. That is, no outside user should be able to compute the element x from the set of values ​​of the hash function computationally for an element x such that h (x) = Y. The hash function is the contender for the name of a one-way function, but at the moment, researchers are not completely sure of this.

It is difficult to build a cryptographic scheme from one-way functions, since it has only one secret key, and only the sender and recipient of the encrypted message know about it. This works in the case of Bitcoin and other coins that use the Proof of Work consensus algorithm, where it is necessary to solve a difficult task for verification, which requires a lot of time to calculate, and the verification of the reliability of the answer is not enough. The result must also be quickly verified.

It turns out that one-sidedness is necessary to exclude the fabrication of the message. Bitcoin requires that the computed hash function is less than a special parameter, this requires repeated recalculation with the selection of arbitrary values ​​of the additional parameter. Computing this function is the job of the miners, and the decision of one function takes about 10 minutes. Cryptographic hash functions, such as SHA-256, are computed quickly, without difficulties in terms of computational complexity theory, and to verify the correctness of an already-created block, only a single computation of the hash is necessary.

Computational asymmetry is aimed at preventing double-spending attacks and the continuity of blocks in the Bitcoin network Proof of Work. For the solution, you must successfully complete the task and output a nonce one-time value. In this case, the level of effort in solving the puzzle is large, and the level of effort to verify is low, and again creates an asymmetry that hinders the process and makes it more expensive.

If They Prove That P = NP . . .

Scientists have been trying to find an answer to the equality of classes P and NP since the 80s when Stephen Cook and Leonid Levin independently raised this issue.

The researcher from the Eindhoven University of Technology keeps a diary for the sake of fun, where he writes down all the unsuccessful attempts to prove this question. At the beginning of the 2000s, as a survey of 100 scientists showed, 61 percent of them were sure that these classes are unequal. Nine scientists assumed that they were equal, twenty-two found it difficult to answer, and eight believed that the hypothesis was not deducible from the current system of axioms, and therefore could not be proven nor disproven.

At the moment, since there is no evidence to the contrary, P is not equal to NP. Otherwise, hackers would have used this equation to their advantage long ago, since anyone could pick the correct cipher to the Bitcoin blockchain with the help of a long analysis of all possible options. If two parameters were equal, the asymmetries disappear from the computation of algorithms (the proof by Proof of Work's consensus algorithm is exact). Protocols would be simplified thousands of times, which means that the safety of Bitcoins and other similar coins would be destroyed, the Internet would become a free walking ground as stated by the professor of mathematics at Imperial College London Kevin Buzzard and many of his colleagues who are studying the issue.

"If P = NP, then in one fell swoop we will lose the whole digital world in the usual sense. Without asymmetry, Bitcoin will be lost. It will disappear because the cipher to the solution of the big secret passwords will be found. The degrees of the solution are leveled, and they will become the same because the algorithms will calculate even the most difficult problems," Buzzard says.

Thus, if they prove that P = NP, then the safety of Bitcoin will collapse.