Thoughts Blockchain and Blockspace Scalability

Originally published in the Polkadot forum.

While thinking about a tutorial idea about FRAME, I came up with an interesting example that showcases/categorizes the scalability issue in blockchains, which is somewhat entangled with game theory. Here it goes.

Imagine a simple validator selection system whereby:

This is an extremely simple problem in the context of more information systems, but it is a surprisingly hard problem to solve in blockchains. Let's explore why.

The answer really boils down to one root issue: Blockchains, unlike all almost many other information systems, are not sybil-resistant. When you are thinking about solving the above algorithmic problem, you must assume you are solving it for an infinitely large input size. In this case, this translates to an infinitely large number of wanna-be validators.

The first step in solving such issues is acknowledging such issues, and finding the boundaries of where your system breaks. For the above example, assume that an analysis on weight, memory or state usage could help us conclude that the system would work for as long as there are less than V_max wanna-be validators registered in the system.

In essence, the problem can be stated as sybil-irresistance -> scalability issues. In written words, blockchains are not sybil resistance, therefore face scalability issues.

We can tackle this issue in both sides of the above arrow.

To fix/improve the sybil-resistance part:

Polkadot's Staking system in fact implements a linked-list like above, you can read more about it here.

Note that neither of these solutions attempt at really solving the scalability part. They don't help increase V_max. They merely help with making the system more sybil resistance, ie. knowing that V_max is (almost) never reached.

Oftentimes, you want both. You want to be somewhat more sybil resistant, but you also want to be more scalable. Imagine you have implemented some or all of the of the above, but simply want that V_max to be larger. This translates to "more blockspace" and typically there are two ways to improve it:

Recall, all of this helps us achieve a higher V_max for the above problem, neither try and prevent spammers to fill the entire space of V_max.