  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. Sharding divides the blockchain network
into multiple committees and is a common approach to improve scalability.
However, with current sharding approaches, costly cross-shard verification is
needed to prevent double-spending. This paper 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 cyber security in terms of integrity,
availability, and trust, 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, 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 which 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.
