QIP: 2 Layer: Consensus (hard fork) Title: Sharded ledger Author: wizeguyy <[email protected]> Comments-Summary: No comments yet. Comments-URI: https://github.com/quainetwork/qips/wiki/Comments:QIP-0002 Status: Draft Type: Standards Track Created: 2023-09-07 License: BSD-2-Clause
The Quai protocol accommodates high transactional throughput by splitting ledger state into independent shards. Each shard is updated via block chain and merge mined with the other shard chains. This QIP describes a mechanism of splitting the state trie according to account prefix, in order to guarantee no two shards posess conflicting state transitions.
Sharding makes it possible to asynchronously progress multiple chains simultaneously. Concretely, sharding the ledger provides a simple guarantee that no two zone chains will have conflicting state transitions. Without this guarantee, zone chains would not be able progress asynchronously. Put differently, if zone chains could have conflicting transactions, then no chain would reach finality until it found a merge mined block that the entire network accepts as canonical. This would completely negate the scaling benefits of Quai's merge mined architecture, reducing the network throughput to that of a single chain of merged blocks.
The address space is divided into subsets according to address prefix. The account state for each subset of addresses will be maintained wholly by one and only one shard. Intra-shard transactions may only be processed by the blockchain which maintains that shard. Inter-shard transactions are possible, but the specification for those will be left to another QIP.
The Quai protocol defines a hierarchy of merge mined blockchains. This hierarchy takes the form of a tree with two levels under the root. The root chain (aka prime chain) is merge mined by several "region chains" of lower difficulty. Each region chain is merge mined by "zone chains" of lower difficulty.
Since this architecture is symmetric, the total number of shards which can exist in a region is `sqrt(N)`, where `N` is the total number of shards in the network.
Each shard is given a binary identifier. Any address which has a matching binary prefix will exist in that shard. The shard identifier is a single byte. The first 4 MSb of the identifier indicates which region this shard belongs to. The remaining 4 LSb of the indentifier, indicates which zone within the region, this shard belongs to.
| bits 0..4 | bits 4..8 |
|---|---|
| region number | zone number |
The following table gives a few example shard identifiers, and which zone chain they belong to.
| Shard ID | Hex Value | Region | Zone |
|---|---|---|---|
| shard-0 | 0x00 | region-0 | zone-0-0 |
| shard-1 | 0x01 | region-0 | zone-0-1 |
| shard-10 | 0x0A | region-0 | zone-0-10 |
| shard-42 | 0x2A | region-2 | zone-2-10 |
| shard-255 | 0xFF | region-15 | zone-15-15 |
There is no requirement for shards to be active. It is likely that only a fraction of the shards will be active initially, and the network will expand to activate more shards as network demand increases. The exact process for deciding how/when to activate more shards will be left for a future QIP. The Quai protocol defines the initial topology to be a 3x3 tree, so there will be 9 shards active in this minimum topology. Those shards are given below.
| Shard ID | Hex Value |
|---|---|
| shard-0 | 0x00 |
| shard-1 | 0x01 |
| shard-2 | 0x02 |
| shard-3 | 0x10 |
| shard-4 | 0x11 |
| shard-5 | 0x12 |
| shard-6 | 0x20 |
| shard-7 | 0x21 |
| shard-8 | 0x22 |
This QIP licensed under the BSD 2-clause license.