Free2Shard: Adversary-resistant Distributed Resource Allocation for Blockchains

Ranvir Rana, Sreeram Kannan, David Tse, Pramod Viswanath

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In this paper, we formulate and study a new, but basic, distributed resource allocation problem arising in scaling blockchain performance. While distributed resource allocation is a well-studied problem in networking, the blockchain setting additionally requires the solution to be resilient to adversarial behavior from a fraction of nodes. Scaling blockchain performance is a basic research topic; a plethora of solutions (under the umbrella of sharding) have been proposed in recent years. Although the various sharding solutions share a common thread (they cryptographically stitch together multiple parallel chains), architectural differences lead to differing resource allocation problems. In this paper we make three main contributions: (a) we categorize the different sharding proposals under a common architectural framework, allowing for the emergence of a new, uniformly improved, uni-consensus sharding architecture. (b) We formulate and exactly solve a core resource allocation problem in the uni-consensus sharding architecture-our solution, Free2shard, is adversary-resistant and achieves optimal throughput. The key technical contribution is a mathematical connection to the classical work of Blackwell approachability in dynamic game theory. (c) We implement the sharding architecture atop a full-stack blockchain in 3000 lines of code in Rust-we achieve a throughput of more than 250,000 transactions per second with 6 shards, a vast improvement over state-of-the-art.

Original languageEnglish (US)
Title of host publicationSIGMETRICS/PERFORMANCE 2022 - Abstract Proceedings of the 2022 ACM SIGMETRICS/IFIP PERFORMANCE Joint International Conference on Measurement and Modeling of Computer Systems
PublisherAssociation for Computing Machinery, Inc
Pages113-114
Number of pages2
ISBN (Electronic)9781450391412
DOIs
StatePublished - Jun 6 2022
Externally publishedYes
Event2022 ACM SIGMETRICS/IFIP PERFORMANCE Joint International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS/PERFORMANCE 2022 - Virtual, Online, India
Duration: Jun 6 2022Jun 10 2022

Publication series

NameSIGMETRICS/PERFORMANCE 2022 - Abstract Proceedings of the 2022 ACM SIGMETRICS/IFIP PERFORMANCE Joint International Conference on Measurement and Modeling of Computer Systems

Conference

Conference2022 ACM SIGMETRICS/IFIP PERFORMANCE Joint International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS/PERFORMANCE 2022
Country/TerritoryIndia
CityVirtual, Online
Period6/6/226/10/22

All Science Journal Classification (ASJC) codes

  • Computational Theory and Mathematics
  • Computer Networks and Communications
  • Hardware and Architecture
  • Software

Keywords

  • game theory
  • sharding

Fingerprint

Dive into the research topics of 'Free2Shard: Adversary-resistant Distributed Resource Allocation for Blockchains'. Together they form a unique fingerprint.

Cite this