TY - JOUR
T1 - Free2Shard
T2 - Adversary-resistant Distributed Resource Allocation for Blockchains
AU - Rana, Ranvir
AU - Kannan, Sreeram
AU - Tse, David
AU - Viswanath, Pramod
N1 - Funding Information:
This research was partly supported by US Army Research Office Grant W911NF-18-1-0332, National Science Foundation CCF-1705007, NeTS 1718270 and the XDC network.
Publisher Copyright:
© 2022 ACM.
PY - 2022/3
Y1 - 2022/3
N2 - In this paper, we study a canonical distributed resource allocation problem arising in blockchains. 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 study a canonical distributed resource allocation problem arising in blockchains. 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=85125845330&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85125845330&partnerID=8YFLogxK
U2 - 10.1145/3508031
DO - 10.1145/3508031
M3 - Article
AN - SCOPUS:85125845330
SN - 2476-1249
VL - 6
JO - Proceedings of the ACM on Measurement and Analysis of Computing Systems
JF - Proceedings of the ACM on Measurement and Analysis of Computing Systems
IS - 1
M1 - 11
ER -