The basic principles in terms of maintaining the security of, and incorporating transactions into the blockchain of any cryptocurrency, notwithstanding of the method of consensus used, is simple: A major division of users, whether by way of having the most computing power or by having the most at stake, overlook all the transactions that go through the network. Every transaction between users is unique, and that requires concocting a unique hash to each transaction. When such a transaction has been hashed, the problem can be regarded as 'verified' as opposed to, despite popular belief, 'solved.' Simply put, the difference between them is: 'is 10 the answer to 5+5' versus 'is there a solution to 5+5?'
A starkly unsolved problem in computer science, the P vs. NP, or P = NP, is whether a problem (In the case of Cryptocurrencies, a transaction) can be solved procedurally and systemically just as quickly as it can be verified with a hash. The security of the blockchain, such as Bitcoin, is wholly dependant on the assumption that transactions that P does not equal NP. However, if P = NP is proven, the Bitcoin can be breached just as quickly as it can be authenticated. Verification is quick, but attempting to solve a transaction, from the perspective of either a block miner or, more importantly, an attacker, is made an impossible task through statistical improbability. More on that later on.
This problem in general has been one of the hallmarks of computer science since being described in 1972 by Stephen Cook. Since then, major prize money upwards of a million dollars for whomever solves it. The problem is also considered the holy grail of the field. The problem will be solved when a problem has both solutions on an equal footing. Both solution and verification are required for a problem to be in P. No computational power can solve this problem just as quickly as a hashing and verifying the problem.
The difficulty of the problem
Coming onto the technical details, in many cryptographic problems, the problem is divided into two parts. The first part is called the search problem and involves solving a problem with a deterministic function F with a set of keys k. The second part is called the verification problem and involves finding one of the keys k in the set F(k). In any given cryptographic scenario, the verification problem is easy because it is assumed that the verifier already knows k. the search problem, however, is much harder, for reasons such as the verifier does not have access to k. It is detailed in the
Verification
When a person wants to prove they have a private key k, the person must provide some information proving they have possession of k, such as a private key matching the public key that belongs to that private key. For the verification problem, the private key is unknown to the verifier, so the verifier can't verify this information.
For the verification problem, the problem is easy because if the verifier wants to know if the private key k matches some public key p, the verifier can be told that the private key k is encrypted under the public key p. The fact that k was encrypted with the public key p ensures that the two have been associated with one another by the owner of the public key p. If the verifier could prove k matched p, then the person could decrypt it. So, the verification problem for the Bitcoin whitepaper is to find a way to solve the P.
Search
For the search problem, the problem is extremely hard. It would seem the way to solve the search problem is to just brute-force every possible key until the first key that matches the public key is found. In other words, find all k that match the public key. For the Bitcoin whitepaper, it is assumed that there are only 4 billion possible keys. So, the probability of finding a key that matches is at best 1 in 4 billion. This means that the expected time to search is about 4 billion times the time it takes to calculate a double whammy. In other words, the expected time to find a key is about 4 billion times the expected time to solve the P. Since this number is greater than all the computers that humans have ever built, this suggests that it should be an impossible task by way of statistical improbability: The chances of matching a private key to its corresponding public key are so small, it is not worth expending the computational power required to do so. If P = NP were to be proven, then it becomes significantly viable in terms of computational power to do so, resulting in a major breach of security.
Conclusion
This article presents a realistic scenario where, if it takes place, not only Bitcoin could plummet to $0, but the field of cryptography as a whole would be compromised to the point of obsolescence, if not posit danger to the systems that are dependant on it. Despite the problem being the center of much attention, however, there still is no proof that P indeed equals NP, but as is the case with these kinds of problems, there is no telling whether it'll be solved within a year from now, or a century down the road.
Posted Using LeoFinance Beta
