Sharding, Ethereum's solution to scaling up

Scalability, or the ability to scale up, is one of the most important issues when it comes to crypto-economic protocols such as Bitcoin and Ethereum. Indeed, to remain relevant, these protocols cannot allow their respective networks to suffer too great a transactional load and thus become too centralized. The question that must be asked when we talk about scaling up is, therefore: How can the network increase its processing capacity in a secure manner while maintaining sufficient decentralization?

At the moment, the Bitcoin and Ethereum networks are struggling to keep up with demand and may experience congestion characterized by longer confirmation times and higher transaction costs. For Ethereum, perhaps the most emblematic episode of this problem is the Cryptokitties, the decentralized application for collecting and exchanging virtual chats, which monopolized the network in December 2017.

Sharding, or partitioning, is the solution conceived by Ethereum's developers to remedy the problem. This technique is not new and is used for databases: it consists of partitioning the data horizontally in order to distribute the storage in memory. For Ethereum, whose ambition is to be a global computer, sharding would consist of parallelizing both storage and the execution of autonomous contracts without losing security.

With Casper and eWASM, this partitioning is one of the main elements of Ethereum 2.0. Ethereum's evolution towards greater efficiency and scalability should come to fruition with the Serenity upgrade.

What's the problem?

Crypto-economic systems based on chains of blocks are, by design, quite inefficient systems. To function without a central authority, to resist external attacks, they need to be sufficiently distributed.

This is why they are subject to a principle known as the "trilemma of chains of blocks" formalized by Vitalik Buterin. This trilemma stipulates that a chain of blocks system can only have 2 of the 3 following properties:

• Decentralization: the system can work in the case where each participant has access to only a given amount of computing resources (such as a laptop or a small virtual server).
• Scalability: the system can process transactions in order of magnitude strictly greater than what is possible with resources owned by a single participant.
• Security: the system is secured against an attacker with fewer resources than those corresponding to the transactional level of the network.

So-called "naive" solutions have been considered to remedy the problem, but they do not completely solve it:

• Separate the activity between different chains ("altcoins"). By distributing validators over different networks, this solution lowers the overall security of the system.
• Increase the block size limit. After a certain threshold (which should be determined), this solution decreases the decentralization of the network by increasing the level of computing resources needed to maintain a node.
• Perform merged mining on different chains. For Vitalik Buterin, this is a disguised form of increasing the block size limit that decreases decentralization by requiring validators to manage other chains to remain profitable.

Other more ingenious but also more complex solutions have been devised. This is particularly the case for so-called "second layer" solutions. For Ethereum, these are the Raiden network, which is a network of state channels and is based on the same principles as the Lightning network, and Plasma, the side channel system. These solutions have their own problems, which will not be detailed here.

It is in this context that partitioning comes into play, which is the solution favored by the developers so that Ethereum can go to scale without any loss in terms of decentralization or security.

What is partitioning or sharding?

Ethereum is a decentralized global computer whose global state is updated by all the nodes of the network. This state is permanently changed through transactions (also called operations). The chain of blocks, the history which lists all these transactions since the creation of the system, allows the nodes of the network to synchronize.

Ethereum is thus characterized by two things: its state and its history. In Ethereum, the state is the mapping linking the addresses (0x...) to their balance and to their code and data if they are autonomous contracts. The report is sufficient to determine whether a transaction is valid or not.

Today, status and history weigh more than 250 GB and 3 TB, respectively. Many network nodes only store the system status (pruned mode). Only the so-called "archiver" nodes take the trouble to store the entire blockchain.

The idea behind partitioning is to break up both the history and the state of Ethereum into a multitude of independent fragments (shards). Each of these fragments is validated by a (variable) part of the network, which allows us to parallelize the operations and to distribute the total load of the system. The number of fragments depends on the ratio between the minimum computer resources required for each participant and the average number of transactions carried out on the network.

On the one hand, each fragment then behaves like a chain in its own right: it has its own local state, has its own history, and uses part of the network to be validated. On the other hand, the set of fragments must behave in the same way as the global system, which makes the application of the idea quite difficult, as we will see in the next part.

Other proposals resembling the partitioning proposed by the Ethereum development teams exist. In particular, Zilliqa has implemented a form of partitioning that distributes computing tasks between several subnets but keeps a single state. Similarly, the use of a Merklix tree (also called Merkle-Patricia tree), present on the Bitcoin Cash roadmap, should allow in the future to partition block validation.

How does it work?

Partitioning is based first of all on the creation of the main chain called "beacon chain" which allows managing the distribution of tasks in Ethereum. On this chain, validators are randomly chosen to have the right to create blocks on a given fragment. In the same way, for each fragment, a hundred validators are chosen to certify the validity of the block: for the block to be valid and for the reward to be distributed, at least 67 of them must publish their signature on the beacon chain. The tag chain thus has here a role of intermediary between the fragments and the global system.

Moreover, the partitioning of the Ethereum chain requires a shift to proof of the issue. In particular, it needs proof of the stakes algorithm currently under development called Casper. Even if sharding can be used in a proof-of-work system, there are two main reasons why this algorithm is preferable :

In a proof-of-work model, a specific fragment might be more easily attacked.

In Casper, which requires a list of validators that have made a security repository, it is much easier to select those validators and distribute them among the different fragments.

When the system is running, each group of transactions is assigned to a specific fragment. A rough example of distribution would be 256 fragments dividing the transactions according to their identifier. In this way, all transactions with an identifier starting with 0x00 would be processed in fragment 1; those starting with 0x01 would go into fragment 2, etc.

Of course, a transaction processed in one fragment may impact a contract in another fragment. Thus, partitioning requires a system of communication between fragments (cross-shard communication) serving to harmonize the overall state of Ethereum. This communication system involves receipts, which are objects representing the effect of a transaction that is not stored directly in the state but is nevertheless kept in another place. These receipts are already used by Ethereum as event logs.

Conclusion

Allowing Blockchains to scale is not an easy thing, but partitioning seems to be well on its way to greatly improve the scalability of Ethereum. According to Vitalik Buterin, it would multiply Ethereum's transactional capacity by 100 and, combined with the network of plasma side chains, by 10,000!

Even if the development of partitioning is progressing, its implementation in Ethereum is not likely to see the light of the day before mid-2020 or even 2021.