If P=NP, does Bitcoin fall apart?

What if there was a way to break Bitcoin? To hack it apart? To tear apart its foundation? Is there such a way? Yes… if P=NP.

To begin, the world of Bitcoin and other cryptocurrencies is largely based on the exploitation of algorithmic and computational asymmetries. The decentralization characteristics that Bitcoin achieves is actually powered by these asymmetries, specifically two types of asymmetries:

1. Algorithmic Asymmetry

2. Computational Asymmetry

To break Bitcoin, or any other cryptocurrency, one must be able to break apart its asymmetries. So what is an asymmetry and how does this all relate to this equation P=NP?

(You may even ask: what does P and NP even mean?)

To understand what I mean by asymmetry, let’s first understand the basic concept of symmetry. Symmetry is something that most people learn about in grade school. For example, if you map, reflect, or flip an object across a line or a plane (also called the axis of symmetry or plane of symmetry) and it maintains it structure, then you’ve achieved symmetry. If you know a little simple mathematics, you can establish that f(x) = f(-x) represents a symmetry along the y-axis. If symmetry can be described as an invariance to transformation, then asymmetry represents the opposite fact: it means that one side does not look like the other side; one side does not match the other.

So how does this all relate back to Bitcoin and our digital world? The premise of the digital world, including Bitcoin, is founded on manufacturing elements of trust — trust that a transaction will be free from nefarious actions, and trust that the information sent between two parties is intact, whole, and tamper-proof. In the world of Bitcoin, this trust is established via leveraging two asymmetries:

1. Algorithmic Asymmetry: Public Key Cryptography

2. Computational Asymmetry: Proof of Work

This isn’t supposed to be a math lesson — but advanced caliber mathematics do play a heavy role in making Bitcoin possible. Furthermore, you cannot really understand how Bitcoin works if you don’t have a grasp of the underpinning asymmetries. So to make the topic a bit more tangible, let’s describe exactly what’s meant by an algorithmic asymmetry and a computational asymmetry.

Algorithmic Asymmetry

An algorithm asymmetry arises when the level-of-effort required to solve a problem is vastly greater than the level-of-effort required to check the solution. For example, factoring is a notoriously good example where an algorithmic asymmetry exists. Determining the solution of a quadratic equation can be done by factoring. Over time, one gets progressively better and better at factoring (hopefully), but it does involve an element of trial-and-error: i.e. in the below example: what are two numbers that will multiply to give 3, but add to the number 2.

Problem: x^2 + 2x - 3 = 0

Factoring: (x -1)(x + 3) = 0

Solution: x = 1 and x = -3

However, once we know that x = 1 and -3, it’s easy to plug them back into x^2 + 2x - 3 to determine that the result is indeed 0. In this case, it’s easier to check the solution then it is to solve the problem itself. You can most definitely argue there isn’t that big of a disparity between level-of-effort to solve the problem versus level-of-effort to check the solution for simple quadratic factoring, so imagine a far far greater mathematically complex algorithm.

Let’s try extending this idea to creating codes or keys. In the digital world, creating a secure electronic lock-and-key system is ultimately the backbone of all Internet communications, including the transaction pathways of Bitcoin. A secure digital lock-and-key system provides the means and methods to manufacture trust. Without being able to manufacture trust, Bitcoin would simply not exist.

Public Key Cryptography, also called Asymmetric Cryptography, and the generation of public key-secret key pairs are used in Bitcoin to sign and secure the Unspent Transaction Outputs (UTXOs) that form the pathways to exchange value between one trustless party to another. Public key cryptography relies most heavily on the fact that the level-of-effort to check if the public key matches the secret key is low, but the level-of-effort to find or resolve the secret key only knowing the public key — is almost darn-right impossible (the level of effort required to use brute force to solve the problem is enormous)! In fact, to break the asymmetric Elliptic Curve Digital Signature Algorithm (ECDSA) which Bitcoin uses would take the world’s fastest computational network (cluster) billions upon billions of years. Therefore, it is enough to say that on human time-scales, reversibility does not exist. Bitcoin derives it most powerful advantages from asymmetries in lock-and-key algorithms to generate public key-secret key pairs. Public keys can be used to communicate, exchange, and transact in the public domain — but unlike a traditional login and password (where a password or passphrase can be potentially hacked) — the same thing cannot be said about a secret key.

In the end, Bitcoin facilitates the a trustless P2P network for the exchange of value through the asymmetry between the level-of-effort to solve a problem versus the level-of-effort to check the solution.

Algorithmic Asymmetry in Bitcoin 
Level-of-Effort to Solve a Problem = High 
Level-of-Effort to Check the Solution = Low

But that’s not all.

Computational Asymmetries

The other asymmetry that Bitcoin exploits is related to a computational asymmetry which is used to prevent attacks on the Bitcoin network from creating double-spend scenarios, and to ensure that the blockchain remains unbroken — i.e. Proof of Work. Proof of Work is Bitcoin’s hash mining puzzle, or the piece of computation that miners need to successfully solve before submitting a block to extend the overall blockchain. This piece of computation provides an output which is called the nonce value (nonce: number that is only used once). The primary purpose of this computation is that while the level-of-effort required to solve the computational hash mining puzzle is tremendous, the level-of-effort to check for the solution is trivial — again, an asymmetry exists. In Bitcoin, it is this computational asymmetry that makes it difficult (and computationally expensive) to go back in time to attempt to fork the blockchain, create double-spends, and attempt to create a parallel consensus blockchain in hopes that it will eventually be the longest.

To create an immutable, indelible, single instance of truth ledger like the Bitcoin blockchain requires computational asymmetries to secure the blockchain and leverages the vast disparity between the level-of-effort to solve a problem versus the level-of-effort to check the solution.

Computational Asymmetry in Bitcoin
Level-of-Effort to Solve a Problem = High
Level-of-Effort to Check the Solution = Low

So what is P=NP?

P=NP is actually a very famous problem. So famous that if you can find a valid solution to this problem, first postulated in sorts by Alan Turing and later formulated by Stephen Cook and Leonid Levin, the Clay Mathematics Institute (CMI) will award you $1million dollars. P=NP is one legendarily stubborn problem in computer science to solve, so much so, it’s called one of the seven “Millennium Prize Puzzles”. Ultimately, P=NP relates back to algorithmic and computational asymmetries that exist between level-of-effort to solve a problem versus the level-of-effort to check a solution. P and NP are nothing more than sets, sets that represent two distinct classes or problems (in this case, computer programs):

P represents the set of all problems where:
Level-of-Effort to Solve a Problem = Low
(i.e. Easy to find the solution to a problem)

NP represents the set of all problems where: 
Level-of-Effort to Check the Solution = Low
(i.e. Easy to check the solution to a problem)

The P=NP problem can be summarized in the following way: “Is it true that all problems for which the level-of-effort to check the solution is low, the level-of-effort to solve the problem is also low?” Or in more precise language: “If the solution to a problem can be checked in polynomial time (a term used in computer science, i.e. the solution to a problem can be checked very easily, quickly, efficiently), can it also be found or solved in polynomial time (i.e. found very easily, quickly, efficiently)?” Bitcoin only works because P≠NP.

Bitcoin
P
= Level-of-Effort to Solve a Problem = High
NP = Level-of-Effort to Check the Solution = Low

But what if one day, someone did come along, and was able to prove that P=NP? What if someone was able to show that there were indeed algorithmic and computational methods that could be used to easily solve a problem, just as easily as the solution is checked. What would this mean for cryptography, for hash puzzles, for all the constructs that Bitcoin and other cryptocurrencies use to secure themselves and to manufacture decentralized trust among trustless peers? Would Bitcoin fall apart?

Kevin Buzzard, Professor of Pure Mathematics at Imperial College London does a wonderful job at illustrating the history of P=NP.

If someone was able to prove P=NP, in one fell swoop, you’d lose the backbone of what makes the Internet secure since almost all communication and encryption protocols use asymmetries. If P=NP, you’d lose Bitcoin. However, practically speaking, knowing that P=NP and actually being able to create computer programs that exploit P=NP is another question. One may know that the level-of-effort to solve a problem can be equally matched to the level-of-effort to check the solution (and both level-of-efforts are low), but someone would still need to create dedicated algorithmic and computational methods to solve the problem with low level-of-effort. Easier said than done.

In 2017, computer scientist Norbert Blum proposed a solution to P=NP, but inevitably sometime later, acknowledged that his proof was indeed incorrect. Many have tried, many have failed. So much so, that there exists a website to determine if P=NP has been solved: http://haspvsnpbeensolved.com/

The more interesting problem that P=NP unearths is the fact that our digital world is nearly entirely supported and secured by asymmetries that are deemed unbreakable: i.e. various Internet protocols like SSH (Secure Socket Shell), TLS (Transport Layer Security), PGP (Pretty Good Privacy), S/MIME (Secure Multi-Purpose Internet Mail Extensions), etc. All these leveraged asymmetries are based on hairy mathematics and exploiting the fact that the level-of-effort to solve a problem is tremendously greater than the level-of-effort to check the solution. So is there really no other way to provide security, verifiability, and tamper-proof properties without asymmetries?

What P=NP uncovers is that new, novel, and interesting methods of replicating undeniable and unbreakable digital lock-and-key mechanisms are needed. Whether that’s future advances in Quantum Cryptography, or DNA Cryptography, or something else entirely — each and every key-stroke, transaction, and message in our digital lives depends upon manufactured trust. Right now P≠NP is what makes the Internet, Bitcoin, and everything in between possible — but that may not always be the case.