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.
In addition to supporting multiple shards within the Quai ledger, the address space needs to account for other ledgers as well. This includes the native Qi UTXO ledger as well as dynamically registered application chains (a.k.a. para-chains).
The address space is divided into subsets according to address prefix. Each subset will identify a shard of the overall state space; i.e. state transitions pertaining to any address within a given subset of the address space will be processed wholly by one and only one transaction ledger. 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 tree is subdivided first according to ontological position of a shard within in the tree, and secondarily subdivided according to witch transaction ledger an address belongs to.
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 9 bits. The first 4 MSb of the identifier indicates which region this shard belongs to. The second 4 MSb of the indentifier, indicates which zone within the region, this shard belongs to. The LSb designates which ledger the address belongs to, Qi or Quai.
| bits 0..3 | bits 4..7 | bit 9 |
|---|---|---|
| region number | zone number | ledger identifier |
Region number and zone number are simply the ontological position of a chain within the hierarchy of chains. The ledger identifier is a subdivision within each chain, which specifies which ledger an address belongs to. The mapping of ledger identifiers is given below:
| ledger ID | ledger name |
|---|---|
| 0 | Quai account address space |
| 1 | Qi UTXO address space |
The following table gives a few example shard identifiers, and which shard and ledger an address belongs to.
| Name | Address | Region | Zone | Ledger |
|---|---|---|---|---|
| shard-0-qu | 0x000DEADBEEFCAFE0000000000000000000000000 | region-0 | zone-0 | Quai account |
| shard-42-qu | 0x2A40000DEADBEEFCAFE000000000000000000000 | region-2 | zone-10 | Quai account |
| shard-255-qu | 0xFF700000000DEADBEEFCAFE00000000000000000 | region-15 | zone-15 | Quai account |
| shard-0-quai | 0x008000000000000DEADBEEFCAFE0000000000000 | region-0 | zone-0 | Qi UTXO address |
| shard-243-quai | 0xF3F0000000000000000DEADBEEFCAFE000000000 | region-15 | zone-3 | Qi UTXO address |
There is no requirement for shards to be active. In fact, consensus is optimal if new chains are activated only as there is enough transactional demand to necessitate more chains. Since each chain runs two shards (one Qi shard and one Quai shard), at mainnet launch only shard-0-qu and shard-0-quai will be active. New chains with new shards will be activated dynamically as network load necessitates.
This QIP licensed under the BSD 2-clause license.