Sharding Is Also NP-Complete

  1. Define a general type of sharding that covers any such scheme
  2. Show it is NP-Complete
  3. Discuss what that means

The Sharding Problem

The general “sharding problem” is how to ensure both sides of a transaction are on the same shard. That’s because transactions settle one blockchain at a time. Proving on a different chain that you did some transaction is fine — but you still need to settle it. And per-chain settlement bandwidth is limited by the previous post.

The Reduction

Finding an efficient sharding is NP-Complete. How do we know that? We can use the same reduction as last time. There are 4 transactions between the variables at the top and the gather wallet. Take an instance of 3-SAT. Reduce it. Set up your system with r=4 and 3 shards per clause. Shard it. Run the result for 1 block. Check the balance, across all shards, in gather. If the money got there the sharding was efficient and the problem is satisfiable.

Sharding Is Not Useless

Just because sharding is hard to do in the worst-case does not mean it is useless in practice. The point of this post is not that sharding is useless. Sharding certainly helps sometimes. It might even help “on average.” But this is a hard problem. This leaves us with two choices:

  1. Scalable solutions which are prone to accidents
  2. Truly reliable scalability but P=NP etc

My name is XYZ-Chain and I have a scaling problem

One of my favorite observations about folk psychology is that acceptance is the first of the 12 steps and the last of the 5 steps. You can’t get better, or move on, until you admit you have a problem.

Adding More Features

You cannot get around this problem by adding some new feature. This setup does not require any proof system, zero-knowledge or otherwise. It does not assume any form of roll-up. It does not journal anything. There is no proof-of-anything.



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