Moving ETH between shards: the problem statement

Sharding
8

Good summary! I would like to share our thoughts on moving native token between shards, which are close to the solutions (2) and (5) with the following features:

  • Guaranteed and ordered delivery via incentives: A cross-shard receipt will be incentivized to be eventually processed at destination shard.
  • DoS attack prevention: Even the attacks may send lots of transactions to one shard from other shards, the system would continue to work.
  • Happen-before guarantee: A cross-shard receipt will be always processed at the destination shard after the original token was spent from the source shard.

Assumptions:

A1. A BP node of shard j is a light-client of shard i and full node of the root chain (similar to beacon chain in ETH2.0), and thus the node is able to obtain and verify the receipts of all blocks of shard i via a Merkle root hash (Note that “all blocks” constraint may be relaxed to “recent blocks”)

A2. The Merkle root hashes of cross-shard receipts from all shards are included in the root chain in a deterministic order.

A3. A shard block contains a hash pointer to root block and a cursor:

  • The root block hash pointer tells which root block the BP of the shard block observed and included. According to A1, the BP could fully recover all receipts from shards by the Merkle root hashes of the blocks of root chain since the genesis root block. By ordering the receipts according to their position in the Merkle root and the position in the root chain, we can obtain a deterministic receipt queue, which will be processed by the shard in sequence.
  • The cursor tells which receipt has been processed by the shard block in the queue, and thus the rest of the queue is called post-block unprocessed receipt queue, which can be very long due to DoS (however, the queue can be constructed by any BP of the shard on-demand and asynchronously according to A1 and A2, and thus all BP of the shard to be attacked won’t be overwhelmed by the DoS attack)

Steps

The following are the steps for a cross-shard transaction:

  1. A user generates a cross-shard transaction from shard i to shard j, and the tx is included in shard i block A. The receipts of all txs of the block are generated and its Merkle root is included in a future root block.

  2. At target shard j, upon observing a new root block and creating a new shard block, the BP of shard j create a pre-block unprocessed receipt queue by electing to include the root block or not in the shard block and :

  • If a root block is not included, the pre-block unprocessed receipt queue of the new block equals to the post-block unprocessed receipt queue of the previous block
  • If a root block is included, the pre-block unprocessed receipt queue of the block is constructed by appending all receipts included to the post-block unprocessed receipt queue of the previous block. Again, the construction can be on-demand and asynchronously according to A1.

When creating a shard block, the consensus forces that a valid block must process the receipts in the pre-block unprocessed receipt queue until the queue is empty or a pre-set cross-shard transaction gas limit is exhausted. The pseudo-code looks like:

def process_receipts(state, xshard_gas_limit, cursor):
  xshard_gas_remained = xshard_gas_limit
  while xshard_gas_remained > 0 and cursor.has_next() and cursor.peek().startgas > xshard_gas_remained:
      receipt = cursor.next()
      xshard_gas_remained = process_one_receipt(state, receipt)
return state, xshard_gas_remained, cursor

Comments

Guaranteed and ordered delivery via incentives

According to A2 and A3, as long as the receipt queue is deterministically ordered, the delivery is also ordered. To ensure guaranteed delivery, i.e., to encourage a BP of a shard to include the latest root block (and thus forcibly process the receipt queue), we could have

  • (Incentive from cross-shard receipt tx fee). If the BP doesn’t include the root block while the unprocessed receipt queue is empty, it will waste its cross-shard gas limit and the corresponding tx fee;
  • (Incentive from block reward). In the case tx fee is small, we could further incentivize the BP as follows: if a BP includes a new root block, it will collect a full block reward rather than a partial block reward.

DoS Attack

If an attacker sends overwhelming receipts from other shards to destination shard, the attack won’t prevent the BPs of the target shard from working:

  • According to A3, the receipt queue can be constructed on-demand and asynchronously to the current block production of the shard.
  • Each shard block will process the receipts with gas up to cross-shard gas limit

Happen-before guarantee

The generating of the receipt at source shard and the processing of the receipt at target shard is a partial order.

Other notes

  • Gas limit for a receipt: The gas limit of a receipt cannot greater than cross-shard gas limit.
  • Mathematical description: An early mathematical description of the model can be found in [1, Section III.E]
2 Likes