Ethereum Sharding: Overview and Finality

In Ethereum Casper 101 [1], Jon Choi gave a great clear overview of Casper and why explicit finality can be beneficial to scalability. The aim of this article is to give an overview of Ethereum sharding design and explain how explicit finality helps for blockchain sharding.

To fully understand the specification of Ethereum sharding mechanism proposal, I highly recommend digging in sharding doc [2] by Vitalik.

Blockchain Scalability Issues

1. Growth of transactions. We love unicorns and kittens.
2. Limitation of scalability with current block creation process. Block gas limit restricts the computational capacity of the block. Increasing block gas limit or decreasing block time too much would lead to high stale rate and weaken the ability of the network against attacks.
3. Lack of parallelizability. First, current EVM operates transactions in sequence. Second, every full node executes each transaction and store the whole (or pruned) state trie for security and decentralization.

Further reading: EIP 648 — Easy parallelizability for executing transactions in parallel.

To solve scalability problems, sharding is a solution that introduces to on-chain state partition and gains higher throughput.

source: https://pixabay.com/photo-2695569/ (CC0 Creative Commons)

Terminology

At first, let’s take a look at terms for differentiating the objects on main chain (you can take as the current Mainnet chain) or shard chain in different levels:

Table 1. Terminology.

You can simply imagine that the transactions would be wrapped in a “collation”; similar to block, a collation also points to its parent collation in chains — that’s the shard chains we’re going to talk about. Being a “collator” means having the eligibility to propose a new collation on the proof-of-stake shard chain.

Figure 1. A glimpse of basic collation data structure.

Basic Quadratic Sharding

The Consensus of Shard Chain Depends on Main Chain

Similar to side chain technology, only the small pieces of proof of collations have to be recorded on main chain — that’s the basic idea of how we scale out the blockchain: (i) the shard chains have their own galaxy with their own transactions, shard validators only have to verify the shard they are watching for; (ii) shard chains also stick on main chain universe for reaching higher level of consensus via proof-of-stake mechanism.

Validator Manager Contract (VMC)

For joining shard chains on main chain, there’s going to be a special contract on main chain called Validator Manager Contract (VMC). VMC is the core of this sharding mechanism; the purpose of VMC can be outlined as follows:

1. Proof-of-stake system. The validators’ stake may be slashed if they misbehaved.
2. Pseudorandomness sampling. By applying recent block hash as the seed to sample the eligible collator. Basically, the validators deposit their stake in VMC, and then their validation code address would be recorded in a global validators pool list inside VMC. One shard chain validator would be sampled from validators pool list, and become the collator of the specific shards in specific “period” (as it will be explained below). The idea is making validators unable to forecast when they would be the collator and in which shard many days ago.
3. Collation header validation. VMC contains an addHeader(bytes collationHeader) function to verify the collation header and writing a record of valid collation header hash. This function provides on-chain verification immediately.
4. Cross-shard communication. By utilizing UTXO model, the user can deposit ether on a specific shard via transaction call and create a receipt (with a receipt ID) on main chain. The shard chain user can create a receipt-consuming transaction with the given receipt ID to spend this receipt.
5. On-chain governance. With VMC as the parliament, it enables validators to vote on-chain.

How to Propose a Collation in Shard?

In phase 1, VMC would maintain 100 shards (SHARD_COUNT = 100). Each shard operates in parallel and the clients of shard i only have to verify the transactions on shard i.

“period” is defined as a window of block times, e.g., PERIOD_LENGTH = 5 means 5 blocks per period. This indicated in each period, there’s only lesser than or equal to one valid collation for each shard.

Figure 2 (a). Quadratic sharding. The proofs of shard states would be recorded on main chain VMC.

Once the validator gets sampled to be eligible collator to propose a new collation, the collator has to validate the recent collations and send a transaction to call addHeader function. Note that if the collator is sampled to propose a new collation on period 10, that means the addHeader transaction has to be included in period 10, i.e., block number10 * PERIOD_LENGTH to block number (10 + 1) * PERIOD_LENGTH — 1.

Figure 2 (b). For one shard, only one collation per period; one block can include multiple addHeader transactions of different shards.

The collation header hash must be recorded on VMC to prove its header is valid in global. Also, the other validators of the shard have to watch VMC all the time for getting latest status and then verify if the transactions are valid too.

Fork Choice Rule of Shard Chain

In basic sharding, the fork choice rule depends on the longest main chain. The valid head collation of the given shard is not simply the head collation of “longest valid shard chain” but the “the longest valid shard chain within the longest valid main chain”.

An example is described in Figure 3: in Figure 3(a), there are two forks of main chain and the second chain is the longest valid main chain in the following figure. Since block B3 is the head block, it’s easy to see that collation C3 is the head collation.

Figure 3 (a).

And then block B3' arrives in Figure 3 (b). Assume that the score of block B3 is higher than the score of block B3', so the upper chain is still the longest main chain:

Figure 3(b).

Lastly, block 4 arrives in Figure 3 (c). Note that for this shard, collation C3 has a higher score than collation C2, but the below chain is the longest valid main chain, so collation C2 is the head collation now:

Figure 3 (c).

Further reading: another design — Vlad Zamfir’s sharded fork choice rule. 🦌🌲🎁

An ingenious design for guaranteeing blocks atomicity before they are finalized.

Trade-off between Scalability and Security

Blockchain systems can only at most have two of the following three properties: decentralization, scalability, and security.

— Blockchain Trilemma in Sharding FAQ [3]

The limitation of scalability is based on the security guarantees of the system [3]. While we increased TPS (Transactions Per Second) by distributing transactions to shards, we also decreased computational resources for each transaction consequently.

One of the important mechanism of sharding is how to produce randomness on-chain.

• The chance of being selected as collator should only be relevant and proportional to the validator’s deposit.
• If the validators can predict or choose which shard they will participate in arbitrarily, the dishonest validators can collude with each other and start an adaptive attack.

If the sampling process fails to select with high randomness, it’s possible for an attacker to start 1% attack in the shard: if there are 100 shards, the attacker can focus on attack one particular shard, they only need 1% hash rate (PoW)/deposit (PoS) to control the shard [4].

Figure 4. Traditional majority attack (51 % Attack)

Figure 5. Sharding 1% attack

Blockchain Explicit Finality for Sharding

Implicit Finality v.s. Explicit Finality

At first, I have to clarify that the sharding mechanism should be able to apply in both proof-of-work chain and proof-of-stake chain; even so, explicit finality gadget like Casper can make sharding stronger.

In general proof-of-work chains, finality is probabilistic and implicit [1] [5]; in simpler words, it’s always possible to rewrite the chain even the block has gotten thousands of confirmations. In contrast, applying proof-of-stake with Casper the Friendly Finality Gadget (“FFG”) cryptoeconomic mechanism explicitly enforces finality of we-can-check-if-its-finalized-for-us in-protocol.

[Notes from Vlad] There’s an economic risk of in-protocol explicit finality threshold: it creates the ideal cartel sizes at 2/3 + 1 and 1/3 + 1. Accordingly, the marginal contribution to finality of any node which is not in 2/3 + 1 coalition becomes 0. 🥒

Dependency on Main Chain Finality

In basic sharding, the shard chains are pegging on main chain.

To the shard validators, we expect with sharding, the blockchain capacity became 100x higher in phase 1, thus all the validators of these 100 shards will need to watch VMC status to get the correct valid head collation. It’s important for validators to be certain of know they are the collator or not as soon as possible; to the normal users, if we apply cross-shard transactions in phase 2, the normal users will also need to retrieve their deposit information (receipt ID) on VMC.

Explicit finality would help for mitigating the uncertainty of syncing between main chain and massive shard chains.

Explicit Finality Helps for Stateless Client

The basic idea of stateless clients is that the stateless clients don’t store the whole state trie, instead, they only store the state trie root. The archival clients store the full state trie and provide the Merkle branches that the given collation needs. With these Merkle branches, the stateless clients are capable of building the partial state trie and verifying the collation [6].

The syncing process would be triggered once the validator gets sampled and starts reshuffling (i.e., changing the shards which the validators watch for and syncing the shard chains). With stateless client mechanism, the cost of reshuffling drops to (near) zero because they only have to validate the recent collations (i.e., collations with high score) to sync with the shard.

Figure 6. Stateless client model. (Icons made by DinosoftLabs from www.flaticon.com is licensed by CC 3.0 BY)

Since the syncing process could be much faster, stateless client model makes it possible to reshuffle between each collation. It not only reduces the storage burden and overhead but also makes the system more secure because frequent sampling gains adaptive attack resistance.

Although the syncing cost becomes much lower, the stateless validators still have to verify as more collations as they can within a certain period of time to confirm that they get the best valid collation with the highest score.

Casper FFG will provide explicit finality threshold after about 2.5 “epoch times”, i.e., 125 block times [1] [7]. If validators can verify more than 125 / PERIOD_LENGHT = 25 collations during reshuffling, the shard system can benefit from explicit finality and be more confident of the 25 ahead collations from now are all finalized.

Note that of course, it’s more secure if we have more collations get verified on syncing.

Conclusion

I wish I gave a preliminary brief of current Ethereum sharding design concept and how explicit finality benefits sharding mechanism. For diving deeper into protocol design, please visit ETHResear.ch and sharding doc.

Please don’t hesitate to point out any mistake or unclear expression. 🙂

Special thanks to Vitalik Buterin for all the great work, Jon Choi for pushing me to write up, Dr. Chang-Wu Chen for refining, Brian Chen for giving feedback, and Vlad Zamfir for sharing thoughts plus the super cool Vlarding.

Reference

1. Jon Choi. Casper 101: https://medium.com/@jonchoi/ethereum-casper-101-7a851a4f1eb0
2. Vitalik Buterin. Sharding Document: https://github.com/ethereum/sharding/blob/develop/docs/doc.md
3. Vitalik Buterin and the contributors. Sharding FAQ: https://github.com/ethereum/wiki/wiki/Sharding-FAQ
4. Vitalik Buterin. Sharding Mindmap: https://www.mindomo.com/mindmap/sharding-d7cf8b6dee714d01a77388cb5d9d2a01
5. Vitalik Buterin. On Settlement Finality: https://blog.ethereum.org/2016/05/09/on-settlement-finality/
6. Ethresear.ch thread — The Stateless Client Concept: https://ethresear.ch/t/the-stateless-client-concept/172
7. Ethresear.ch thread — Casper contract and full POS: https://ethresear.ch/t/casper-contract-and-full-pos/136/2