The Consequences of Scalable Blockchains
(with apologies to Paolo Sorrentino)
What we are going to do here is pretty simple:
- Describe some thing a scalable blockchain could do.
- Prove that thing is NP-Complete.
- Show how, if you have such a blockchain, you can right now break hash functions and public-key cryptography and constructively prove P=NP.
If you build this thing you can break nearly all the major protocols out there — blockchains, banks, SSL, RSA, nearly everything — right now.
It’s worth stating that part #2 — the only part of this blog that is technical — would fly as a homework assignment in any “Intro to the Theory of Computation” class. The one I took looks to now be this class and we used this textbook. You can skip the proof and still get the implications. Obviously those who can check the proof should — and everyone with a CS degree has done this kind of thing before.
The trick here is in defining the property not in doing the proof. This result should help clarify questions around what people mean by a “scalable blockchain.” This doesn’t mean you cannot build one with a different definition — but it puts down a marker for the consequences of anything with this particular property.
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.
We are going to call something “scalable” when it can process more transactions per unit time than a single node on the network. If you always need to wait for some designated leader/verifier/miner/whatever to finalize transactions then you’re never going to run faster, in the worst-case, than that node.
The property we are going to look at is: reshuffling lists of ok-on-their-own transactions with a no-negative-balance requirement into a single merged list where the maximum number of possible transactions go through. And doing this reordering “efficiently.” We take “efficiently” to mean “in polynomial time.”
If your product can do that, it’s subject to these results. If it can’t — if that isn’t an expected behavior — then this post doesn’t apply to you. But note that if you cannot mix transactions together like this then your finality must come from one node at a time and throughput, in the worst-case, cannot exceed that node. There are likely many ways to skirt this issue but they are all going to involve some kind of compromise on generality.
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.
Here is the reduction algorithm:
Say the 3-SAT instance has c clauses and v variables.
Create a set of v starting wallets, one for each variable, called start_i. For each variable count the number of times it is referenced as true and false and call these usedTrue_i and usedFalse_i.
Then compute max_i = max(usedTrue_i, usedFalse_i). Initialize the balance of start_i with max_i. All other wallets start empty.
Now, for each variable, create two wallets true_i and false_i. Add to the list of candidate trades, from start_i, usedTrue_i units to true_i and usedFalse_i units to false_i. At most one of these trades can be executed for a total of v.
Now for each clause create three wallets clause_i,(1,2,3). Add a trade for 1 unit into clause_i,j from the appropriate true_i or false_i for j=(1,2,3).
For each clause create clause_i and add 3 trades into it for 1 unit each from clause_i,(1,2,3).
Create a gather and add a trade for 1 unit into it from each clause_i. c of these trades can be executed. Then add an end wallet and a trade from gather into end for c units.
As we can have more then v trades on each layer above gather — as more than one element of each clause can be true — we should extend a chain of 2v trades for c units beyond end.
Call the trade ordering function and get back an ordered, no-negative-balance, list of trades. Then run those trades. Running the trades takes time linear in the number of trades.
If, after running them, there are c units at the bottom of the end chain, or if the list itself is long enough, then the expression is satisfiable and we can read the variable assignments from the trade list.
This is the standard sort of reduction algorithm as one usually finds in these sorts of proofs.
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:
We’ve chosen to use this example so readers can go to that paper and note the similarities. The assumption is that many people reading this blog are unfamiliar with this sort of argument and the similarities should engender acceptance. A two-clause single-variable non-satisfiable example is here:
A three-variable version is at the end. When you see it you’ll understand why.
It is normal for reductions from 3-SAT to all look reasonably similar. The famous textbook Computers and Intractability is full of such similar-looking reductions. As is Karp’s original paper. The whole point of NP-Completeness is that they are all really the same problem so conversions among them all have the same flavor.
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.
In particular it means we have the world’s fastest SAT Solver. And by an exponential margin.
Oh, and we’ve also solved the famous P vs NP problem by proving P=NP. And we’ve done so in the strongest and most useful possible way: with a constructive proof. This result would be staggering. Read that Wikipedia link.
How to Break Hash Functions, RSA etc
Now the fun part. If we have such a system we can do many interesting things.
This paper from Microsoft Research shows an approach for attacking hash functions using a SAT solver. Remember: if we have this sort of blockchain we have the world’s fastest SAT solver — ours is exponentially faster than anything which exists today. So things those authors consider hard are a breeze for us. Other techniques exist as well.
And what about public key cryptography? This paper shows us how to factor integers quickly with our blockchain. The RSA algorithm? If we have a fast SAT solver that’s so easy it is left as an exercise for the reader here. Elliptic curve algorithms and discrete log in general? Yup that’s covered in this one.
So our scalable blockchain could pull off this trick from Silicon Valley and is equivalent to “the box” from the 1992 movie Sneakers. Neat.
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.
In practice, it probably means this particular flavour of scalable blockchain is impossible. Bitcoin provided a novel solution to the double-spending problem by reframing the issue a little. This would immediately provide long-sought solutions to hundreds, if not thousands, of important problems with massive day-to-day implications.
This says nothing about narrower definitions of scalable — and it says nothing whatsoever about “fast on one node” or “fast on average” algorithms. This also has obvious implications for the necessity of fee markets in systems which turn out to have capacity limits.
Further, NP-Completeness is notoriously resistant to small changes in the problem statement. Scalable blockchain designers should skim the section of Computers and Intractability where they enumerate such problems. As a warning: that section alone is ~100 pages long with about half a dozen examples per page. And that book is from 1979. Nobody would have guessed those problems were all really the same until it was proven. And a modern version of that list would be dramatically longer.
We end with a non-satisfiable example with 3 variables. It get worse from here — but these graphs are still polynomial in size and the trade sorter can handle them all.
