Dynamically Sharded Ledgers on a Distributed Hash Table

Read original: arXiv:2405.14991 - Published 5/27/2024 by Christoffer Fink, Olov Schel'en, Ulf Bodin

Dynamically Sharded Ledgers on a Distributed Hash Table

Overview

Explores a new approach to ledger management called "dynamically sharded ledgers" that leverages a distributed hash table (DHT) to enable highly scalable blockchain systems
Introduces a novel protocol called "ScaleGraph" that enables efficient transaction processing and critical event ordering in a sharded blockchain environment
Aims to address key challenges in blockchain scalability, such as handling high transaction volumes and ensuring consistent ordering of critical events across shards

Plain English Explanation

This research paper presents a new way to manage the ledger, or record of transactions, in blockchain systems. It introduces a technique called "dynamically sharded ledgers" that uses a distributed hash table (DHT) to enable more scalable blockchain networks.

The paper proposes a new protocol called "ScaleGraph" that helps efficiently process transactions and ensure the proper ordering of critical events across the different "shards" or partitions of the blockchain. This is an important challenge in blockchain scalability, as the system needs to handle high transaction volumes while maintaining consistency across the network.

By using a DHT to manage the ledger data, the researchers aim to create a more scalable and efficient blockchain architecture that can support the growing demands of real-world applications. The paper explores the technical details of this approach and demonstrates its potential benefits through analysis and experiments.

Technical Explanation

The paper introduces the concept of "dynamically sharded ledgers" on a distributed hash table (DHT) to address the scalability challenges in blockchain systems. The key elements of the proposed approach include:

Distributed Hash Table (DHT): The use of a DHT to store and manage the ledger data, allowing for more efficient partitioning and distribution of the blockchain state across the network.
ScaleGraph Protocol: A novel protocol designed to enable efficient transaction processing and critical event ordering in a sharded blockchain environment. ScaleGraph ensures consistent ordering of events across shards, a critical requirement for maintaining the integrity of the blockchain.
Dynamic Sharding: The ability to dynamically adjust the number of shards based on network load and other factors, providing greater flexibility and scalability compared to static sharding approaches.

The paper presents the technical details of the ScaleGraph protocol, including its algorithms for transaction processing, critical event ordering, and shard management. It also includes an analysis of the protocol's performance and scalability characteristics, as well as a comparison to existing blockchain sharding techniques.

Critical Analysis

The paper presents a promising approach to addressing the scalability challenges in blockchain systems, but it also acknowledges several caveats and areas for further research:

Shard Coordination: The paper notes that the coordination and synchronization between shards is a crucial aspect that requires careful design and implementation to ensure the overall consistency and integrity of the blockchain.
Adversarial Scenarios: The paper does not explicitly address the resilience of the proposed system to adversarial attacks or malicious actors, which is an important consideration for any blockchain-based system.
Experimental Validation: While the paper provides analytical and theoretical insights, the authors suggest that further experimental validation and real-world deployment of the ScaleGraph protocol would be necessary to fully assess its performance and practical viability.
Applicability to Other Blockchain Frameworks: The paper focuses on the ScaleGraph protocol within the context of the proposed dynamically sharded ledgers on a DHT. It would be valuable to explore the potential for adapting or integrating these concepts into other existing blockchain frameworks and platforms.

Conclusion

The "Dynamically Sharded Ledgers on a Distributed Hash Table" paper presents a novel approach to improving the scalability of blockchain systems. By leveraging a distributed hash table and a custom protocol called ScaleGraph, the researchers aim to enable more efficient transaction processing and critical event ordering in a sharded blockchain environment.

The proposed solution addresses key challenges in blockchain scalability, such as handling high transaction volumes and maintaining consistent ordering of events across shards. The technical details and analysis provided in the paper suggest that this approach has the potential to contribute to the ongoing efforts to make blockchain technology more scalable and practical for real-world applications.

However, the paper also highlights areas for further research and validation, including shard coordination, resilience to adversarial scenarios, and the integration of these concepts into other blockchain frameworks. Continued exploration and refinement of this and similar approaches will be crucial in driving the advancement of blockchain technology and its widespread adoption.

This summary was produced with help from an AI and may contain inaccuracies - check out the links to read the original source documents!

Follow @aimodelsfyi on 𝕏 →

Related Papers

Dynamically Sharded Ledgers on a Distributed Hash Table

Christoffer Fink, Olov Schel'en, Ulf Bodin

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.

5/27/2024

DL-Chain: Scalable and Stable Blockchain Sharding with High Concurrency via Dual-Layer Consensus

You Lin, Mingzhe Li, Qingsong Wei, Yong Liu, Siow Mong Rick Goh, Jin Zhang

Sharding enhances blockchain scalability by partitioning nodes into multiple groups for concurrent transaction processing. Configuring a large number of emph{small shards} helps improve the transaction concurrency of a sharding system. However, it increases the fraction of malicious nodes within each shard, easily leading to shard corruption and jeopardizing system security. Some existing works have attempted to improve concurrency by reducing the shard size while maintaining security. However, they often require frequent and time-consuming recovery of corrupted shards, leading to severe system stagnation. Also, they usually require network-wide consensus to guarantee security, which limits scalability. To address these issues, we propose DL-Chain, a blockchain sharding system that can securely provide emph{high concurrency with stable and scalable performance.} Our core idea is a underline{D}ual-underline{L}ayer architecture and consensus, which consists of numerous smaller proposer shards (PSs) for transaction processing and multiple larger finalizer committees (FCs) for transaction finalization. To avoid system stagnation and thus guarantee stable performance, we ensure PSs' liveness even if they are corrupted through the cooperation of PSs and FCs, thus eliminating the recovery process of corrupted PSs. To better trade-off security and scalability, we fine-tune the FCs to enable multiple FCs to coexist securely. As a result, DL-Chain allows a larger fraction of malicious nodes in each PS ($<1/2$) and thus can securely configure smaller shards for boosted stable and scalable concurrency. Evaluation results show that DL-Chain achieves up to 10 times improvement in throughput compared to existing solutions and provides stable concurrency with up to 2,550 nodes.

7/10/2024

📶

Fast Transaction Scheduling in Blockchain Sharding

Ramesh Adhikari, Costas Busch, Miroslav Popovic

Sharding is a promising technique for addressing the scalability issues of blockchain. It divides the $n$ participating nodes into $s$ disjoint groups called shards, where each shard processes transactions in parallel. We investigate scheduling algorithms for the blockchain sharding systems, where each transaction resides in a shard of the communication graph and attempts to access accounts at possibly remote shards. We examine batch scheduling problems on the shard graph $G_s$, where given a set of transactions, we aim to find efficient schedules to execute them as fast as possible. First, we present a centralized scheduler where one of the shards has global knowledge of transactions to be processed. For general graphs, where the transaction and its accessing objects are arbitrarily far from each other with a maximum distance $d$, the centralized scheduler provides $O(kd)$ approximation to the optimal schedule, where $k$ is the maximum number of shards each transaction accesses. Consequently, for a Clique graph where shards are at a unit distance from each other, we obtain $O(k)$ approximation to the optimal schedule. We also get $O(k log s)$ approximation for Hypercube, Butterfly, and $g$-dimensional Grid, where $g=O(log s)$. Next, we provide a centralized scheduler with a bucketing approach that offers improved bounds for special cases. Finally, we provide a distributed scheduler where shards do not require global transaction information. We achieve this by using a hierarchical clustering of the shards and using the centralized scheduler in each cluster. We show that the distributed scheduler has a competitive ratio of $O(mathcal{A_mathcal{CS}} log ^2 s)$, where $mathcal{A_mathcal{CS}}$ is the approximation ratio of the centralized scheduler. To our knowledge, we are the first to give provably fast transaction scheduling algorithms for blockchain sharding systems.

5/27/2024

🛸

Stable Blockchain Sharding under Adversarial Transaction Generation

Ramesh Adhikari, Costas Busch, Dariusz R. Kowalski

Sharding is used to improve the scalability and performance of blockchain systems. We investigate the stability of blockchain sharding, where transactions are continuously generated by an adversarial model. The system consists of $n$ processing nodes that are divided into $s$ shards. Following the paradigm of classical adversarial queuing theory, transactions are continuously received at injection rate $rho leq 1$ and burstiness $b > 0$. We give an absolute upper bound $max{ frac{2}{k+1}, frac{2}{ leftlfloorsqrt{2s}rightrfloor}}$ on the maximum injection rate for which any scheduler could guarantee bounded queues and latency of transactions, where $k$ is the number of shards that each transaction accesses. We next give a basic distributed scheduling algorithm for uniform systems where shards are equally close to each other. To guarantee stability, the injection rate is limited to $rho leq max{ frac{1}{18k}, frac{1}{lceil 18 sqrt{s} rceil} }$. We then provide a fully distributed scheduling algorithm for non-uniform systems where shards are arbitrarily far from each other. By using a hierarchical clustering of the shards, stability is guaranteed with injection rate $rho leq frac{1}{c_1d log^2 s} cdot max{ frac{1}{k}, frac{1}{sqrt{s}} }$, where $d$ is the worst distance of any transaction to the shards it will access, and $c_1$ is some positive constant. We also conduct simulations to evaluate the algorithms and measure the average queue sizes and latency throughout the system. To our knowledge, this is the first adversarial stability analysis of sharded blockchain systems.

4/23/2024