Blockchain State Sharding With Space-Aware Representations
- 15 October 2020
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Network and Service Management
- Vol. 18 (2) , 1571-1583
Abstract
State sharding is a common solution to the scalability problem in blockchain systems, allowing nodes to hold a partial view of the system state. With sharding, the processing of a transaction might not be completed locally within a node and potentially requires involvement of multiple shards. Such cross-shards transactions have a negative impact on system performance and are frequent with traditional state partition solutions which are often based on a simple mapping of data into shards. By locating together parts of the system state accessed by frequent transactions, the amount of cross-shard transactions can be reduced. On the other hand, the representation of such particular mappings can be memory intensive. In this article, we study traffic-aware sharding that can be described in memory-efficient mappings. We first survey existing mapping schemes in common blockchains. We indicate the tradeoff between the size of the mapping of data to shards and the required transaction processing time and suggest algorithms for finding memory-light sharding of low cross-shard rate. We generalize the approach towards an efficient incremental computation of shards and probabilistic representation of the mapping to shards. We examine the efficiency of the solutions and the required frequency of sharding computation based on real information of the Ethereum network.Keywords
Funding Information
- Technion Hiroshi Fujiwara Cyber Security Research Center and the Israel National Cyber Directorate
- Gordon Fund for System Engineering
- Alon fellowship, by German-Israeli Science Foundation (GIF) Young Scientists Program
- Taub Family Foundation
- Polak Fund for Applied Research, at the Technion
This publication has 22 references indexed in Scilit:
- SpannerACM Transactions on Computer Systems, 2013
- Streaming graph partitioning for large distributed graphs2012
- SchismProceedings of the VLDB Endowment, 2010
- Kademlia: A Peer-to-Peer Information System Based on the XOR Metric2002
- Statistical mechanics of complex networksReviews of Modern Physics, 2002
- ChordACM SIGCOMM Computer Communication Review, 2001
- A Fast and High Quality Multilevel Scheme for Partitioning Irregular GraphsSIAM Journal on Scientific Computing, 1998
- Principles of transaction-oriented database recoveryACM Computing Surveys, 1983
- Some simplified NP-complete problems1974
- Space/time trade-offs in hash coding with allowable errorsCommunications of the ACM, 1970