Dynamically Sharded Ledgers on a Distributed Hash Table

Abstract

Distributed ledger technology such as blockchain is considered essential for supporting large numbers of micro-transactions in the Machine Economy, which is envisioned to involve billions of connected heterogeneous and decentralized cyber-physical systems. This stresses the need for performance and scalability of distributed ledger technologies. Addressing this, sharding techniques that divide the blockchain network into multiple committees are a common approach to improve scalability. However, with current sharding approaches, costly cross-shard verification is needed to prevent double-spending. This article proposes a novel and more scalable distributed ledger method named ScaleGraph that implements dynamic sharding by using routing and logical proximity concepts from distributed hash tables. ScaleGraph addresses cybersecurity in terms of integrity and availability to support frequent micro-transactions between autonomous devices. Benefits of ScaleGraph include a total storage space complexity of \(O(t)\) , where \( t \) is the global number of transactions (assuming a constant replication degree). This space is sharded over \( N \) nodes so that each node needs \(O(t/N)\) storage in expectation, which provides a high level of concurrency and data localization as compared to other delegated consensus proposals. ScaleGraph allows for a dynamic grouping of validators that are selected based on a distance metric. We analyze the consensus requirements in such a dynamic setting and show that a synchronous consensus protocol allows shards to be smaller than an asynchronous one, and likely yields better performance. Moreover, we provide an experimental analysis of security aspects regarding the required size of the consensus groups with ScaleGraph. Our analysis shows that dynamic sharding based on proximity concepts brings attractive scalability properties in general, especially when the fraction of corrupt nodes is small.