Shardeum and Dynamic State Sharding: Another Possibility for Sharding

On September 15, 2022, Ethereum completed the long-awaited merge (Merge). This is a historic moment, and Ethereum has prepared for it for 5 years, delaying it 6 times. Due to repeated debugging and long-term development, many people mistakenly believe that the merge will naturally bring higher scalability, security, and sustainability, but this is not the case. The transition from PoW to PoS is merely a change of tracks and wheels; it does not directly lead to faster speeds, larger capacities, or lower fees. What truly achieves these is a complete set of solutions: a mainnet with Sharding capability paired with Layer 2 solutions that enhance scalability.

As pointed out by Ethereum founder Vitalik Buterin, Sharding is a scalability solution under the scalability trilemma, which involves dividing nodes in the network into smaller groups to handle different sets of transactions and achieve parallel processing. By sharing the burden of processing the vast amounts of data required to aggregate across the entire network, it can intuitively reduce queue times and improve checkout efficiency, just like opening multiple checkout lanes in a supermarket.

This is the logic of Sharding, direct and simple, however, the devil is in the details. The principle and direction are correct, but many problems are always encountered during implementation. This article aims to clarify the direction and dilemmas on the road of "Sharding" and to draw a map of the Sharding explorer that looks up at the starry sky while keeping feet on the ground. At the same time, by comparing existing Sharding solutions, it seeks to find some common issues and propose a feasible exploration direction: Shardeum and dynamic Sharding.

1. About "Sharding"

In simple terms, considering the constraints of the impossible triangle, starting from Ethereum as the origin of the coordinate system (, 0), we divide the current blockchain scalability methods into two main categories based on the "vertical" and "horizontal" approaches:

Vertical Scaling(: Achieved by enhancing the performance of the existing hardware in the system. Establishing a decentralized network where each node in the network has supercomputing power, meaning each node requires "better" hardware. This method is simple and effective and can lead to initial improvements in throughput, particularly suited for high-frequency trading, gaming, and other latency-sensitive applications. However, this scaling method limits the level of decentralization of the network, as the cost of running verification nodes or full nodes increases. Maintaining the level of decentralization is constrained by the approximate growth rate of computing hardware performance), which is known as "Moore's Law": the number of transistors on a chip doubles every two years, while computing costs are halved(.

Horizontal Scaling)Horizontal Scaling(: Horizontal scaling generally has a few approaches. One is to distribute the transaction computation load within a certain ecosystem across multiple independent blockchains, where each chain has its own block producers and execution capacity. This method allows for full customization of each chain's execution layer, such as node hardware requirements, privacy features, gas fees, virtual machines, and permission settings. Another horizontal scaling solution is modular blockchain, which divides the blockchain's infrastructure into execution layer, data availability layer)DA(, and consensus layer. The most mainstream modular mechanism in blockchain is rollup. Another approach is to split a blockchain into many shards that execute in parallel. Each shard can be seen as a blockchain, meaning that many blockchains can execute in parallel. Additionally, there is typically a main chain whose sole task is to keep all shards synchronized.

It should be noted that the above scalability approaches do not exist in isolation; each solution finds a trade-off point within the impossible triangle, combined with the incentive mechanisms created by the economic forces in the system, to achieve an effective balance on both macro and micro levels.

To discuss "Sharding", we need to start from the beginning.

Assuming such a scenario, in a supermarket checkout, in order to improve checkout efficiency and reduce customer waiting time, we expand from a single checkout lane to 10 checkout windows. To avoid bookkeeping errors, we need to establish unified rules at this time:

First, if we have 10 cashiers, how should we assign them to which window to work?

Second, if we have 1000 customers waiting in line, how do we decide which window each customer goes to for checkout?

Third, how should the 10 separate ledgers corresponding to these 10 windows be summarized?

Fourth, how can we prevent cashiers from making mistakes to avoid discrepancies in accounts?

These questions actually correspond to several key issues in Sharding, which are:

How to determine which shard the nodes/validators of the entire network belong to? That is: how to perform Network Sharding );

How to determine which shard each transaction is allocated to? That is: how to perform transaction sharding (Transaction Sharding);

How is blockchain data stored in different Sharding? That is: how to perform state sharding (State Sharding);

Complexity implies risk. Given all the above, how can we avoid the fragmentation of the entire system's security?

( 01 Network Sharding )

If we simply understand blockchain as a decentralized ledger, both PoS and PoW consensus mechanisms are designed for nodes to compete for the right to record transactions according to certain established rules, ensuring the correctness of the ledger in the process. Sharding refers to the need for another set of established rules to partition the blockchain network, allowing each shard to handle on-chain transactions and compete for the right to record transactions, while minimizing communication between them - that is, the grouping rules of the nodes.

The problem encountered during this process is that as the internal nodes of the blockchain are divided into different Shardings, the difficulty and cost for attackers will decrease linearly. We can infer that if the rules and results of this grouping process are fixed and predictable, then an attacker wanting to control the entire blockchain network only needs to strategically control one Sharding and bribe a portion of the nodes within that Sharding.

A certain public chain founder described this issue as follows: If a single chain with X validators decides to hard fork into a sharding chain and divides the X validators into 10 shards, each shard now has only X/10 validators. To compromise a shard, it only requires compromising 5.1% of the total number of validators, which is ###51% / 10(. This leads to the second point: Who selects the validators for each shard? It is only harmful to control 5.1% of the validators when all those 5.1% validators are in the same shard. If validators cannot choose which shard to validate in, it is extremely unlikely that participants controlling 5.1% of the validators will place all the validators in the same shard, thereby greatly reducing their capacity to disrupt the system.

The sharding system must develop a mechanism to trust that the network will not reverse these transactions from external shards. So far, the best answer may be to ensure that the number of validators within a shard is above a certain minimum threshold, thus minimizing the chances of dishonest validators overwhelming a single shard. The most common approach is to build a certain degree of unbiased randomness, mathematically reducing the attacker’s probability of success to a minimum. For example, in Ethereum, the solution is to randomly select the validators for a shard from all validators, and every 6.4 minutes ), which is the length of an epoch (, the validators are changed.

In simpler terms, it means randomly grouping nodes and then assigning work for each group of nodes to validate independently.

However, it should be noted that randomness in blockchain is a very challenging topic. Logically, the process of generating this random number should not depend on the computing of any specific Sharding. For this computation, many existing design ideas involve developing a separate blockchain to maintain the entire network. Such a chain is referred to as the Beacon chain in Ethereum and Near, the Relay chain in PolkaDot, and the Cosmos Hub in Cosmos.

![In-depth Analysis of the New Public Chain Shardeum: Another Possibility for Sharding])https://img-cdn.gateio.im/webp-social/moments-6e8d3331d7d68cb512eb2eb47bd9064d.webp(

) 02 Transaction Sharding (

Transaction sharding refers to the rules governing "which transactions are assigned to which shards", which can achieve the goal of parallel processing while avoiding the occurrence of double spending issues. The differences in the ledger model of the blockchain will affect the development of transaction sharding.

Currently, there are two types of accounting methods in blockchain networks: UTXO) Unspent Transaction Outputs model and account/balance model. The former is typified by BTC, while the latter includes ETH.

UTXO Model: In BTC transactions, each transaction has one or more outputs. UTXO refers to unspent transaction outputs on the blockchain, which can be used as inputs for new transactions, while spent transaction outputs cannot be reused. This is similar to cash transactions where a customer pays with one or more banknotes, and the store gives back one or more banknotes as change. Under the UTXO model, sharding requires cross-shard communication. A transaction may include multiple inputs and multiple outputs, with no concept of accounts or balance records. One possible method is to process it through a hash function based on a certain input value of the transaction to determine which shard the data should go to.

To ensure that entries are placed in the correct sharding in a consistent manner, the values input into the hash function should come from the same column. This column is called the Shard Key. Subsequently, transactions that generate a value of 1 will be allocated to shard 1, and transactions that generate a value of 2 will be allocated to shard 2. The drawback of this approach is that shards must communicate with each other to prevent double-spending attacks. If cross-shard transactions are restricted, it will limit the availability of the platform, while allowing cross-shard transactions must weigh the costs of cross-shard communication against the performance benefits it brings.

Account/Balances Model: The system records the balance of each account. When a transaction is made, the system checks whether the account has sufficient balance for payment. This is similar to a bank transfer, where the bank records the balance of each account, and the transaction can only proceed if the account balance is greater than the required transfer amount. Under the account/balances model, since a transaction has only one input, as long as the transactions are sharded by the sender's address, it can ensure that multiple transactions from the same account are processed within the same shard, effectively preventing double spending. Therefore, most blockchains that adopt sharding technology are account ledger systems like Ethereum.

![Detailed Explanation of the New Public Chain Shardeum: Another Possibility of Sharding]###https://img-cdn.gateio.im/webp-social/moments-4227a2e49f76cd01b23d7b5398e51a3c.webp(

) 03 State Sharding (

State sharding refers to how blockchain data is allocated and stored across different shards.

Still using the example of queuing in our supermarket, each window has a ledger. How is their ledger recorded? For example: which queue the customer comes to, that is the ledger that is recorded. If customer A goes to window A, and then the next day that customer goes to another checkout window, say window B, but window B does not have that customer's past account information ), such as involving stored value cards and other checkout methods (, what should be done? Should window A call that customer's account information?

State sharding is the biggest challenge of sharding, more tricky than the aforementioned network sharding and transaction sharding. Because under the sharding mechanism, transactions are processed in different shards based on address allocation, meaning that the state will only be stored in the shard where its address resides. At this point, one issue to face is that transactions do not occur solely within a single shard, and often involve cross-sharding )Cross-Sharding###.

Consider a transfer scenario where Account A transfers 10U to Account B. The address of A is allocated in Sharding 1, and the transaction record will also be stored in Sharding 1. The address of B is allocated in Sharding 2, and the transaction record will be stored in Sharding 2.

Once A wants to transfer to B, a cross-Sharding transaction will be formed. Sharding 2 will call past transaction records from Sharding 1 to confirm the validity of the transaction. If A frequently sends coins to B, Sharding 2 must continuously interact with Sharding 1, which will reduce the efficiency of transaction processing. However, if not downloading and verifying...