TY - GEN
T1 - Free2Shard
T2 - 2022 ACM SIGMETRICS/IFIP PERFORMANCE Joint International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS/PERFORMANCE 2022
AU - Rana, Ranvir
AU - Kannan, Sreeram
AU - Tse, David
AU - Viswanath, Pramod
N1 - Publisher Copyright:
© 2022 Owner/Author.
PY - 2022/6/6
Y1 - 2022/6/6
N2 - 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.
AB - 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.
KW - game theory
KW - sharding
UR - http://www.scopus.com/inward/record.url?scp=85132156109&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85132156109&partnerID=8YFLogxK
U2 - 10.1145/3489048.3522651
DO - 10.1145/3489048.3522651
M3 - Conference contribution
AN - SCOPUS:85132156109
T3 - SIGMETRICS/PERFORMANCE 2022 - Abstract Proceedings of the 2022 ACM SIGMETRICS/IFIP PERFORMANCE Joint International Conference on Measurement and Modeling of Computer Systems
SP - 113
EP - 114
BT - SIGMETRICS/PERFORMANCE 2022 - Abstract Proceedings of the 2022 ACM SIGMETRICS/IFIP PERFORMANCE Joint International Conference on Measurement and Modeling of Computer Systems
PB - Association for Computing Machinery, Inc
Y2 - 6 June 2022 through 10 June 2022
ER -