Justitia: An Incentive Mechanism Towards the Fairness of Cross-Shard Transactions

A cross-shard transaction (CTX) is parsed into two sub-transactions, which are then executed in the source and destination shards, respectively. However, the problem is that the client who submits the original transaction only pays one unit of the transaction fee. Thus, sub-transactions will experience much higher queueing delays than regular intra-shard transactions when they wait in shard transaction pools. This is unfair for those original transactions that will be parsed into sub-transactions from the perspective of a sharded blockchain. Therefore, how to ensure fairness for all CTXs while securing the atomicity of any pair of sub-transactions becomes a critical challenge. State-of-the-art solutions addressed the transaction atomicity challenge, but the literature still lacks a dedicated incentive mechanism to ensure the fairness of CTXs. To this end, we propose an incentive mechanism named Justitia, which aims to achieve fairness by motivating blockchain proposers to prioritize the CTXs queueing in transaction pools when they package transactions to generate a new block. We rigorously analyze that Justitia upholds the fundamental properties of a sharded blockchain, including security, atomicity, and fairness. We then implement a prototype of Justitia on an open-source sharding-enabled blockchain testbed. Our experiments using historical Ethereum transactions demonstrate that i) Justitia guarantees fairness while processing CTXs, ii) its token-issuance mechanism does not lead to unstable economic inflation, and iii) Justitia only yields 20%-80% of queueing latency for CTXs upon comparing with Monoxide protocol.