S-Store: A Scalable Data Store towards Permissioned Blockchain Sharding

Sharding technique, which divides the whole network into multiple disjoint groups or committees, has been recognized as a revolutionary solution to enhance the scalability of blockchains. For account-based model, state data are partitioned over all committees and organized as Merkle trees to ensure data consistency and immutability. However, existing techniques on Merkle tree-based state storage fail to scale out due to a large amount of network and compute overheads incurred by data migration and Merkle tree reconstruction, respectively. In this paper, we propose $\mathcal{S}$-Store, a scalable data storage technique towards permissioned blockchain sharding based on Aggregate Merkle B+ tree (AMB-tree). $\mathcal{S}$-Store utilizes consistent hashing to reduce data migration among committees and uses split and merge on AMB-tree to decrease Merkle tree reconstruction overheads. $\mathcal{S}$-Store also employs a novel committee addition protocol that guarantees the system service availability during data migration. Extensive experiments show that $\mathcal{S}$-Sotre outperforms existing techniques by one order of magnitude in terms of transaction execution, data transmission, and committee addition.