The Consequences of Scalable Blockchains

  1. Describe some thing a scalable blockchain could do.
  2. Prove that thing is NP-Complete.
  3. Show how, if you have such a blockchain, you can right now break hash functions and public-key cryptography and constructively prove P=NP.

The Thing

For a decentralized, permissionless system we don’t want negative balances. Bitcoin’s big innovation was solving the “double spending” problem in a decentralized way. For our purposes here we generalize that to: no balance can ever be negative in the system. Any proposed trade which would generate a negative balance gets rejected.

The Proof

We are going to prove this property is NP-Complete using the standard technique of “reduction.” And, as is pretty common, we are going to reduce from 3-SAT. 3-SAT is NP-Complete and that result goes back to the early 70s alongside the definitions of P, NP and all that.

An Example

The problem we consider here is similar to the one in this paper. They look at a more challenging problem and prove bounds on how hard theirs is even for approximate solutions. To help with intuition here is their example problem — (x or -y or z) and (-x or y or -z) — run through the above algorithm:

There is no way to get anything into both c1 and c2. So we can never get two things into g.

The Implication

If we can solve this problem efficiently it means we can solve 3-SAT efficiently. If we can solve 3-SAT efficiently then we can solve all of these problems efficiently.

How to Break Hash Functions, RSA etc

Now the fun part. If we have such a system we can do many interesting things.

What Does This Mean?

First, it means any blockchain which has this property is almost certainly insecure (because it can break whatever cryptography secures the keys). But more broadly it means any such blockchain would resolve perhaps the most famous open question in mathematics.

Minimal 3-variable non-satisfiable example. That’s why it’s at the end.



Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store