{"id":22371,"date":"2022-04-04T22:22:51","date_gmt":"2022-04-04T22:22:51","guid":{"rendered":"https:\/\/davidgerard.co.uk\/blockchain\/?p=22371"},"modified":"2023-05-27T21:25:26","modified_gmt":"2023-05-27T21:25:26","slug":"if-you-want-a-scalable-ethereum-blockchain-then-pnp","status":"publish","type":"post","link":"https:\/\/davidgerard.co.uk\/blockchain\/2022\/04\/04\/if-you-want-a-scalable-ethereum-blockchain-then-pnp\/","title":{"rendered":"If you want a scalable Ethereum blockchain, then P=NP"},"content":{"rendered":"

The Ethereum project has an unfortunate tendency to propose six impossible things before breakfast \u2014 ideas that would win a Fields Medal<\/a> for mathematical genius if they could possibly work.<\/p>\n

If you want a horizontally scalable blockchain … then P=NP. If you want transaction sharding to work, then P=NP.<\/p>\n

You could bodge either of these, of course. Do you feel lucky?<\/p>\n

But maybe it doesn’t matter \u2014 and maybe it was never meant to matter.<\/p>\n

 <\/p>\n

\"\"<\/p>\n

 <\/p>\n

NP-completeness and P=NP<\/h3>\n

NP-complete<\/a> problems are one particular class of mathematical problem where it’s easy to check a result is correct, but hard to calculate the result in the first place.<\/p>\n

NP-completeness is a big deal, because a lot of NP-complete problems would be near-magically useful to solve. And all NP-complete problems<\/a> are mathematically equivalent \u2014 so if you can analytically solve one, you\u2019ve\u00a0 solved them all.<\/p>\n

We don\u2019t know<\/i> if NP-complete problems can be solved. We do know that if we could solve them, it would turn the world upside down. The shorthand for this is \u201cP=NP\u201d<\/a> \u2014 that NP-complete problems could be solved in polynomial time.<\/p>\n

Problems of interest to the cryptocurrency field that P=NP could solve include quickly factoring integers to break public-key cryptography, or reversing hashes.<\/p>\n

The Golden Ticket: P, NP, and the Search for the Impossible<\/em> by Lance Fortnow [Amazon<\/em><\/a>] is a good non-technical introduction to just how many amazing things you could do if P=NP.<\/p>\n

But we’ve never found how to do any of those amazing things. So we presume that if a problem is NP-complete, there isn\u2019t an analytical solution.<\/p>\n

There might<\/em> be a solution! But the burden of proof is firmly on the claimant.<\/p>\n

Mathematicians have gotten pretty good at spotting NP-completeness in exciting new ideas in the past few decades. It\u2019s not a good sign.<\/p>\n

Data Finnovation: let’s construct some proofs<\/h3>\n

Let\u2019s look at some requirements for a scalable blockchain. Scalability like this was first posited by Ethereum, then the promises were copied into the white papers for other blockchain projects. If the fabulous future promises come true, your blockchain will need to do these:<\/p>\n