Shardeum and Dynamic State Sharding: Another Possibility of Sharding Exploration

On September 15, 2022, Ethereum completed the long-awaited merge (Merge). This historic moment marks Ethereum's transition from Proof of Work (PoW) to Proof of Stake (PoS), which the Ethereum team prepared for over 5 years and postponed 6 times. However, many people mistakenly believe that the merge will naturally bring higher scalability, security, and sustainability, but this is not the case. The merge merely replaced the "tracks and wheels" and will not directly lead to faster speeds, greater capacity, or lower fees. What truly achieves these goals is a complete set of solutions: a mainnet with Sharding capabilities 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. It works by dividing the nodes in the network into smaller groups, handling different sets of transactions, and achieving parallel processing. By sharing the burden of processing the massive amount of data required for aggregation 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 basic logic of Sharding, simple and straightforward. However, the devil is in the details - the principles and direction are correct, but there are always many problems encountered in implementation. This article aims to clarify the direction and dilemmas on the road of "Sharding," drawing a map for Sharding explorers. At the same time, by comparing existing Sharding solutions, it seeks to identify 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 can divide the current scalability methods of blockchain into two major categories based on "vertical" and "horizontal" approaches:

Vertical Scaling(: Achieved by improving the performance of the existing hardware in the system. A decentralized network is established, where each node in the network has supercomputing capabilities, meaning each node requires "better" hardware. This method is simple and effective, allowing for a preliminary improvement in throughput, especially suitable for high-frequency trading, gaming, and other applications that are sensitive to latency. However, this scaling method limits the level of decentralization of the network, as the cost of running validation nodes or full nodes becomes higher. 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 the cost of computing is halved(.

Horizontal Scaling)Horizontal Scaling(: Horizontal scaling generally has several approaches. One approach is to distribute the transaction computation load of a certain ecosystem across multiple independent blockchains in the context of blockchain, where each chain has its own block producers and execution capabilities. This method allows for full customization of the execution layer of each chain, 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 infrastructure into execution layers, data availability layers)DA(, and consensus layers. The most mainstream modular mechanism in blockchain is rollup. Another method is to split a blockchain into many shards for parallel execution. Each shard can be seen as a blockchain, meaning that many blockchains can execute in parallel. Additionally, there is usually a main chain whose sole task is to keep all shards in sync.

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 at both macro and micro levels.

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

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

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

Secondly, if we have 1000 customers waiting in line, how do we decide which window each customer should go 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 in the entire network belong to? That is: how to perform network sharding )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 across 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?

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

) 01 Network Sharding ###

If we simply understand blockchain as a decentralized ledger, whether it is PoS or PoW consensus mechanisms, they are both designed to allow various nodes to compete for the right to record transactions according to certain established rules, ensuring the accuracy of the ledger in the process. Network Sharding refers to the need for another established rule to shard the blockchain network, allowing each shard to process on-chain transactions and compete for the right to record transactions with minimal intercommunication - that is, the grouping rules of the nodes.

The problem encountered in 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 who wants to control the entire blockchain network only needs to specifically control one Sharding and bribe some nodes within that Sharding.

Alexander Skidanov, the founder of Near, described the problem this way: If a single chain with X validators decides to hard fork into a sharded 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? Controlling 5.1% of the validators is harmful only when all these 5.1% validators are in the same shard. If validators cannot choose which shard to validate in, it is highly unlikely that participants controlling 5.1% of the validators will place all validators in the same shard, significantly reducing their ability to compromise 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 making it very unlikely for dishonest validators to overwhelm a single shard. The most common approach is to build a certain degree of unbiased randomness, relying on mathematical methods to minimize the attacker’s probability of success. For example, Ethereum's solution is to randomly select validators for a shard from all validators, and every 6.4 minutes (, the epoch length ) changes the validators.

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

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 computation of any specific Sharding. For this computation, many existing design ideas involve developing a separate blockchain to maintain the entire network. Such chains are referred to as Beacon chains in Ethereum and Near, Relay chains in PolkaDot, and Cosmos Hub in Cosmos.

( 02 Transaction Sharding )

Transaction sharding refers to the rules governing "which transactions should be allocated to which shards," which can achieve the goal of parallel processing while avoiding the occurrence of double-spending problems. The different ledger models of blockchain can impact the development of transaction sharding.

Currently, there are two types of accounting methods in blockchain networks, namely UTXO### Unspent Transaction Outputs model and account/balance model. The former is typically represented by BTC, while the latter is represented by ETH.

UTXO Model: In BTC transactions, each transaction will have one or more outputs. UTXO refers to the unspent outputs of blockchain transactions, which can be used as inputs for new transactions, while spent transaction outputs cannot be spent again. This is similar to cash transactions where the customer pays with one or more banknotes, and the store gives one or more banknotes as change. Under the UTXO model, transaction sharding requires cross-shard communication. A transaction may include multiple inputs and multiple outputs, with no concept of accounts and no balance records. One possible method is to process the value of a certain input of the transaction through a hash function to generate a discrete hash value 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 yield a value of 1 will be assigned to Sharding 1, and transactions that yield a value of 2 will be assigned to Sharding 2. The downside of this approach is that communication between shards is necessary to avoid double-spending attacks. Restricting cross-shard transactions will limit the platform's availability, while allowing cross-shard transactions will require weighing the costs of cross-shard communication against the performance gains.

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, similar to how banks record the balance of each account during bank transfers, only allowing transactions to proceed when the account balance is greater than the required transfer amount. In the account/balances model, since a transaction has only one input, as long as the transactions are sharded according to 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.

( 03 状态Sharding)State Sharding(

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

Continuing with our example of queuing at the supermarket, how is each window's account recorded? If a customer queues at a certain line, that account is recorded. For example, if customer A goes to window A, and the next day that customer goes to another checkout window, such as window B, and window B does not have the past account information of that customer ), for example, related to stored value cards and other payment methods ###, what should be done? Should we call the account information of that customer from window A?

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 allocated to different shards based on the address, meaning that the state will only be stored in the shard corresponding to its address. At this point, one problem to face is that transactions do not occur only within a single shard; they often involve cross-shard (Cross-Sharding).

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

Once A wants to transfer funds to B, a cross-Sharding transaction will occur. 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 will have to continuously interact with Sharding 1, which will lower the transaction processing efficiency. However, if not