Paper 2019/1172

Lever: Breaking the Shackles of Scalable On-chain Validation

Mingming Wang and Qianhong Wu

Abstract

Blockchain brings dawn to decentralized applications which coordinate correct computations without a prior trust. However, existing scalable on-chain frameworks are incompetent in dealing with intensive validation. On the one hand, duplicated execution pattern leads to limited throughput and unacceptable expenses. On the other hand, there lack fair and secure incentive mechanisms allocating rewards according to the actual workload of validators, thus deriving bad dilemmas among rational participants and inducing effective attacks from shrewd adversaries. While most solutions rely on off-chain patterns to sidestep the shackles, it further introduces unexpected issues in applicability, fairness and brittle dependency on interactive cooperation. The intrinsic bottleneck of backbone has never been drastically broken. This work presents Lever, the first scalable on-chain framework which supports intensive validation, meanwhile achieves validity, incentive compatibility and cost-efficiency tolerance of f<n/4 Byzantine participants. Lever firstly integrates the evaluation of complexity into the correctness of transaction, thoroughly decoupling intensive validation from regular Byzantine consensus. Significant scalability is then achieved by launching few rounds of novel validation-challenge game between potential adversaries and rational stakeholders; compelling incentive mechanism effectively transfers deposits of adversary to specialized rewards for honest validators, therefore allows the user to lever sufficient endorsement for verification with minimum cost. Combined with game-theoretic insights, a backstop protocol is designed to ensure finality and validity of the framework, breaking through the famous Verifier’s Dilemma. Finally, we streamline Lever under the efficient architecture of sharding, which jointly shows robust to conceivable attacks on validation and performs outstanding ability to purify Byzantine participants. Experimental results show that Lever vastly improves the throughput and reduces expenses of intensive validation with slight compromise in latency.

Note: -2019.10.08 An early version of this paper was submitted to CCS 2019. Though the significance and novelty of our construction get fully recognized by most of the reviewers, it was finally rejected due to the poor presentation and an unclear structure which “does not do justice with the contribution of the paper”. We appreciate the valuable constructive suggestions from the anonymous reviewers. After accordingly revising and refining our paper, we decide to preprint the full version to share our research with the academia. Compared to the old version, underlying changes have been made: 1)The paper is reconstructed with a more readable structure, where the main protocol and sharding-based optimizations are decoupled and stated in a progressive manner. 2)We try our best to improve presentation, removing mistakes and meaningless buzzwords, replenishing necessary definitions and self-contained background knowledge, as well as making our framework more concise. 3)Complete proofs and analyses are provided with detailed explanations to account for all the doubts from the reviewers. We will maintain this log to present the latest progress of the work and we are looking forward to any valuable comments, suggestions and cooperation. We hope our contribution could accelerate the development of the Blockchain ecology.