Cross Shard Transaction

A cross-shard transaction is a native token (QKC) transfer transaction with fromFullShardId and toFullShardId resolving to different shards moving native tokens from one shard to another. The cross-shard transaction must be issued directly from the user. Smart contract has no capability to make such cross-shard transaction or invoke smart contract on a different shard.

Processing Cross-Shard Transaction

It takes three steps to complete a cross-shard transaction involving intra-cluster RPCs as described in Cluster Design.

1. The source shard (decided by the fromFullShardId) processes the transaction by deducting the transaction value and gas fee from the sender's account. As the receiver of this transfer is on a different shard, a cross-shard deposit record (R) is created and send to the destination shard (toFullShardId) so that the recevier can be credited later. Same as processing in-shard transactions a block (A) is created and mined to confirm this transaction and others. The state root in the block header reflects the value deduction on the sender's account.

   One block may confirm many cross-shard transactions and thus generating many cross-shard deposits like R. Those deposits are grouped by the destination shard id and then sent to the destination shard in a single batch tagged with the block hash. The destination shard persists the deposits in db keyed by the block hash. In this case the destination shard will have a db entry (key=hash(A), value=[R, ...]).

2. A root block (B) confirming block A is mined and broadcasted to the destination shard. This makes R available to be confirmed by the next block (C) on the desination shard.

3. C refers to the latest root block B, looks up all the cross-shard deposits by the shard block hashes in B, and credits the receivers.Crediting cross-shard transaciton receivers also burns gas counted towards the block gas limit. It's required that all the cross-shard dposits associated with a root block through the shard blocks it confirms must be processed in a single shard block. In this case, B has hash(A) which is used to retrieve R from db. The receiver is then credited which completes the cross-shard transaction.

Scalability Challenge

The approch above will not scale without solving the following two problems.

1. Intra-cluster communication cost could be very high with large number of shards if all the shards need to talk with each other implying O(N^2) cost where N is the number of shards.
2. The computation carried in a single block could be overwhelming if there are too many cross-shard deposits associated with a root block in step 3. (Hot shard problem.)

The solution is simply to put constraints on the shards that a given shard can reach and throttle the number of cross-shard transactions in the network.

Neighbor

To implement the solution for the first challenge we introduce the concept of neighbor. A neighbor function decides if two shards can talk to each other. It takes two branches identifying the two shards as parameter and return a boolean ruling the neighbor relationship.

def is_neighbor(b1: Branch, b2: Branch) -> bool:

One shard only connects to its neighbor shards and thus cross-shard transactions between non-neighbor shards are prohibited in the network but can be carried out through some intermediate shards by making multiple cross-shard transactions.

If we draw a graph where the nodes represent the shards and the edges represent the neighbor relationship, the neighbor function must guarantee the connectivity of the graph so that any account in the network can transfer tokens to any other account regardless of the shards they belong to.

The maximum number of neighbors a shard can have is 32.

Throttling

The number of cross-shard transactions targeting a specific destination shard should also be limited to prevent hot shard. When processing cross-shard deposits each deposit will cost DEPOSIT_GAS (9000) gas. The total number of deposits associated with a root block should not exceed BLOCK_GAS_LIMIT / DEPOSIT_GAS. X - the max number of cross-shard transactions targeting a destination shard in a block shall satisfy

X * MAX_BLOCKS_PER_SHARD * MAX_NEIGHBORS <= BLOCK_GAS_LIMIT / DEPOSIT_GAS

where MAX_BLOCKS_PER_SHARD is the max number of shard blocks that can be included by a root block, MAX_NEIGHBORS is the max number of neighbors a shard can have.

So we need to enforce that

X <= BLOCK_GAS_LIMIT / DEPOSIT_GAS / MAX_NEIGHBORS / MAX_BLOCKS_PER_SHARD

Using the following parameters

BLOCK_GAS_LIMIT = 10,000,000
DEPOSIT_GAS = 9,000
MAX_NEIGHBORS = 32
MAX_BLOCKS_PER_SHARD = 10

we got X < 3.5

More on BLOCK_GAS_LIMIT

BLOCK_GAS_LIMIT of the destination shard is taken from the root block. For example, we have a root block R(A1, A2, B1, B2, B3) which contains shard block headers A1, A2 for shard A and B1, B2, B3 for shard B. When creating a new block on shard A which refers to R the BLOCK_GAS_LIMIT used for shard B is taken from B3.

It is possible that processing cross-shard deposits might exceed the BLOCK_GAS_LIMIT on the destination shard if the block gas limit is tuned down after the cross-shard transactions have been processed by the source shard. Exceeding block gas limit is explicitly allowed in this case.

Since the genesis root block doesn't include any shard block headers, initially all the block gas limits perceived by the source shard are 0 by default and thus no cross-shard transactions are allowed. As soon as a new root block arrives the block gas limits will be updated.