This article was prepared by James A. Henderson from =nil; Foundation
tl;dr
Ethereum’s design has moved away from state sharding; however, L2 architectures like zkSharding provide a unified protocol in which L2 dApps are composable yet scalable via state sharding, avoiding the need for state fragmentation emerging across distinct L2s. However, sharded systems are not without challenges. In particular, state sharding amplifies MEV exploitation and censorship problems that exist in non-sharded blockchains.
We propose a shardDAG architecture for state sharded blockchains or multi-chain systems, combining protocol rules, rewards and penalties that constrain transaction exploitation [[1904.05234] Flash Boys 2.0: Frontrunning, Transaction Reordering, and Consensus Instability in Decentralized Exchanges] and external influences like regulatory censorship [https://www.mevwatch.info/, U.S. Treasury Sanctions Notorious Virtual Currency Mixer Tornado Cash | U.S. Department of the Treasury]. Constraints on exploitation and censorship are achieved using a DAG architecture that links shard blocks to each other. The DAG provides an enforceable order in which cross-shard transactions must be processed by each shard, thereby constraining manipulation of transaction processing order.
Motivation
State sharded blockchains inherit magnified MEV exploitation and censorship problems that exist in non-sharded blockchains because transaction completion can require block proposers in many distinct shards, and each block proposer could exploit or censor transactions. Further, more severe transaction exploits are possible via inserting other exploitative transactions in intermediate blocks that occur between starting and finishing transaction processing.
To understand this, the example below demonstrates a simple exploit scenario.
Exploit Example
Figure 1: Two shard chains. Blocks 0 and 1 of shard A each contain cross-shard transactions t and u respectively, whose destinations are shard B. Suppose t can be exploited if in shard B u is processed earlier than t. Then the system is dangerous for t’s user without enforceable ordering rules that ensure t must be processed before u in shard B.
Why Cross-Shard Transaction Data Availability Matters
Punishment for censoring a cross-shard transaction (CST), or processing in an incorrect, exploitative order can only be enforced provided that
i) It can be established that all the required data was available to the shard, and
ii) The shard subsequently failed to process the data correctly.
Therefore, a mechanism is required for establishing verifiable cross-shard (or cross-chain, or cross-rollup) transaction data availability. The broad steps in achieving this are illustrated in Fig. 2. Preventing exploitation requires enforceable rules for ordering the processing of transactions and CSTs; however, enforcing processing order requires that each shard receives the CSTs that it is required to process. To be able to receive CSTs, that CST data must be available. Thus, constraining exploitation rests upon ensuring CST data availability.
Figure 2: Goal: ShardDAG ordering aims to constrain manipulation, exploitation and censorship of transactions and cross-shard transactions. Step 3: These constraints require enforceable protocol rules for ordering the processing of transactions and cross-shard transactions. Step 2: Fairly enforcing ordering rules requires on-chain acknowledgement of receipt of cross-shard transactions. Step 1: Receipt of cross-shard transactions requires cross-shard transaction data availability.
Step 3. A Preview: How DAGs Provide Order
Our solution to the transaction and cross-shard transaction ordering problem involves linking shard chains into a shard directed acyclic graph or shardDAG, and then ordering processing according to the partial order specified within shard block subgraphs.
ShardDAG ordering is previewed in Fig. 3. The distinct shard chains are connected to form a shardDAG, providing an enforceable ordering of cross-shard transactions amongst the shard chains. Unlike in Fig. 1, in Fig. 3’s shardDAG, an exploitative CST in a later block cannot be processed before a CST in an earlier block.
Figure 3: Unlike the distinct shard chains in Fig. 1, the shardDAG (top) depicted here defines a partial ordering of shard blocks that fall under any particular block (here shard B block 2) and the cross-shard transactions that the blocks contain. (Middle) A Hasse diagram can be constructed to visualise a partial ordering of the shard blocks (for clarity lines connecting blocks have not been included). The shardDAG is topologically sorted (bottom) to produce a block containing an ordered set of transactions and CSTs. In general many topological sorts are possible, the block builder selects one, likely based on MEV.
A ShardDAG for Data Availability
To establish cross-shard transaction data availability, the simple set of shard chains in Fig. 1 is extended to become a shardDAG that is crafted to incentivize data sharing. In this system all validators participate in a synchronization chain which aggregates and finalises state updates from shards that are each operated by distinct subsets of the total validator set. Transaction and CST processing is performed within shards only, hence the synchronization chain is not a processing bottleneck. Here the details of the synchronization chain are restricted to its involvement in the shardDAG—the broader function of the synchronization chain in the sharded system is beyond the scope of this post.
To form a shardDAG, shard blocks include links to other shard blocks in the form of:
- a hash to the previous shard block in the same shard, as in a typical blockchain,
- a set of hashes to other shards blocks in other shards,
- a hash to a (valid) synchronization block, equal to or later than the most recent synchronization block already used by prior shard blocks that are included in the subgraph.
The formation of a shardDAG is illustrated in Fig. 4, where for clarity only edges in the subgraph of the white block are shown. The thick arrows are the white block’s hashes to other blocks.
The following is a central concept in the function of the shardDAG.
When a shard A creates a shard block that includes the hash h of another shard block or synchronization block, this inclusion acts as an acknowledgement that shard A has received the block headers and outboxes of cross-shard transactions for h and h’s entire subgraph in the shardDAG.
Figure 4: Illustration of the white block’s subgraph in the shard DAG. The white block’s header contains a list of hashes to other shard blocks (thick white arrows), and well as a single hash to a synchronization block (thick grey arrow). Thin grey edges trace the subgraph of the white block, beyond the blocks explicitly included in its header.
Step 2. Enforcing CST Receipt
Enforcing CST Receipt via Shard Chains
To enforce shards to continually acknowledge receipt of new shard block data, the protocol specifies conditions on block validity. Suppose we have a shard block b_i and b_i’s prior shard block b_{i-1} in the same shard as b_i.
- [PARENT CONDITION]: For b_i to be a valid shard block, the graph difference of b_i’s subgraph minus b_{i-1}’s subgraph must contain shard blocks created by more than F>1 shards, where F is a system parameter controlling the branching of the DAG.
Example:
In Fig. 4, the subgraph of the white shard A block only contains two blocks that are not in the subgraph of the previous shard A block, i.e. the white block itself, and the middle shard B block. If in this example F=1, then the white block is valid; however, if F>1 then the white block is invalid.
Enforcing CST Receipt Via the Synchronization Chain
The parent condition enforces receipt of CSTs, but does not guarantee that each CST reaches its destination so that transactions complete. Without additional rules it is possible (though unlikely) for sets of shards to create shard blocks whose subgraphs do not span all shards and therefore do not acknowledge receipt of CSTs from all shards, as illustrated in Fig. 6.
Figure 6: Despite the parent condition for valid shard blocks, it is possible (though unlikely) for shard subgraphs to not acknowledge receipt of CSTs from some other shards via shard block edges, indicated by the vertical dashed line. However, the synchronization parent condition eventually forces all shards to acknowledge all CSTs via synchronization block edges. Here the synchronization parent condition forces shard 4 to acknowledge receipt of the red CST (via the red edges) and therefore process it, because the dashed blue edge exceeds the limit (here S=2) of consecutive synchronization block hashes. For clarity only the subset of synchronization blocks edges that are relevant to illustrating the above point are shown.
This is unlikely to occur in the shardDAG; however, the synchronization chain is used to ensure that it cannot occur via a further block validity condition:
- [SYNCHRONIZATION PARENT CONDITION]: A valid shard block b cannot have more than S prior blocks from the same shard using the same synchronization block hash.
The value of S should be chosen depending on the ratio of rates of synchronization block to shard block creation. It is expected that synchronization blocks will be produced at a slower rate compared to shard blocks.
A malicious shard can only produce S shard blocks before being forced to acknowledge receipt of new shard blocks via the synchronization chain. In Fig. 5, the red CST shard block will eventually be included in a synchronization block, in a worst case scenario waiting until a shard 1 validator becomes the synchronization block proposer. Thus, eventually all shards will acknowledge receiving the red CST, including the red CST’s destination shard, as indicated by the red arrows. The dashed blue arrow indicates that shard 4 block 3 would be invalid if it used this hash because more than S (here 2) consecutive shard blocks would hash to the same synchronization block.
In this way, economically motivated validators (and especially synchronization block proposers) are motivated to share data so that finality can be reached and economic rewards can be distributed.
Step 1. Enforcing CST Data Availability Via DAG Edges Between Shards
While the parent, and synchronization parent conditions force shards to acknowledge receipt of data, these rules do not force shards to distribute shard block data and establish data availability. Thus, the protocol specifies a rule on shard block finality to align data availability with economic incentives.
- [CHILD CONDITION]: For a shard block b to be finalised within the synchronization chain, within the subgraph of any synchronization block, b must have child shard blocks created by more than F shards.
When a block satisfies the child condition its CSTs have been acknowledged as received by more than F other shards and the shard has therefore distributed its CST data.
The child condition is illustrated in Fig. 5. For a shard block to acquire child shard blocks, other (honest) shards must first receive its subgraph data. Thus, shards are economically incentivised to possess and distribute data in their subgraphs.
Figure 5: Illustration of the child condition for the subgraph of the upper left synchronization block. In this example F=2. The white block in finalised because it has child shard blocks from three shards, indicated by thick white arrows. In contrast, the bottom right shard block is not finalised because it only has one child shard block indicated by the thick grey arrow.
Step 3. An Enforceable DAG Partial Order of Transaction and CST Processing
The shardDAG provides a verifiable, enforceable ordering of transactions and CSTs, which constrains exploits and guarantees (eventual) transaction processing. Transactions and cross-shard transactions must be processed in an order consistent with the partial order of the shard blocks that they are each created in.
Suppose that shard B creates a new shard block b. As illustrated in Fig.3, the the steps involved in ordering the processing of CSTs and transactions are:
- First b’s hashes (DAG edges) to other shard blocks and a synchronization block are chosen. Hashes are only chosen if corresponding subgraph CST data is available, otherwise correct ordering cannot be known and penalties may ensue.
- The protocol rules described earlier require that the validator creating and proposing b has all the CST data from b’s subgraph, call these T. The set of pending CSTs P whose destination is shard B, and which have not already been processed in an existing shard B block are extracted from T and any new transactions are added to P.
- The set of pending transactions and CSTs, P are (partially) ordered according to the shardDAG ordering of the shard blocks that they were created in, retaining the order of multiple CSTs created within a single block. P is topologically sorted to create a totally ordered set of transactions and CSTs.
- Block size limits may constrain the number of transactions and cross-shard transactions included in a shard block. If this occurs, it is optional to introduce priority of transactions and CSTs as illustrated in Fig. 7, whereby block proposers select transactions and CSTs to include based on priority fees, and MEV. However, this comes at the cost of potentially allowing exploitative transaction insertion. Pending transactions and CSTs must be processed if allowed by block size limits; any unused block space must be too small to contain any unprocessed transaction or CST.
- New transactions that do not fit into block processing can be included in a shard block’s outbox of CSTs. Such transactions enter the shardDAG for ordering and will therefore be processed in a later block along with other pending transactions and CSTs not included in b.
Validators should only sign a proposed block once they have verified that the block proposer has followed this protocol ordering. If an invalid ordering is used then the block is invalid and/or the signing validators are subjected to penalties. We reiterate that because ordering rules involve only on-chain data, data availability of CSTs and block headers enables any validator or node to verify correctness of ordering.
Figure 7: An extension of Fig.3 when shard B is overloaded and unprocessed transactions and CSTs exceed maximum block size (left). The block builder selects transactions and CSTs to remove from the topological sort for the new block (middle), so that the remaining transactions and CSTs do not exceed block size limits (right). Removed CSTs will be processed in later blocks. This removal of transactions and CSTs is expected to be based on priority fees and MEV. Unprocessed new transactions (b2’) may be included in an outbox as data so that they enter shardDAG ordering for processing in a later block, like b0 and b1 in earlier blocks, but these outboxed transactions are not processed in the current block.
Summary
In state-sharded blockchains, censorship and insertion of exploitative transactions part-way through transaction processing can be constrained by shardDAG transaction and CST ordering. These shardDAG constraints are derived from ordering, which enforces processing of earlier transactions and CSTs before later ones. ShardDAG ordering rests upon economic incentives that motivate validators to suitably participate in the shardDAG to receive block rewards and avoid penalties.
DAGs are a natural tool to be used in ordered systems. The shardDAG broadens the use of DAGs in blockchain, beyond their more common application in consensus mechanisms. The shardDAG has been presented here in a unified state sharded system, but the ideas can be applied to sets of distinct rollups or blockchains.