A Two-Layer Blockchain Sharding Protocol Leveraging Safety and Liveness for Enhanced Performance

A Two-Layer Blockchain Sharding Protocol Leveraging Safety and Liveness for Enhanced Performance

Speakers: Yibin Xu

Conference: NDSS Symposium

YouTube: https://www.youtube.com/watch?v=KCMt4v0eaTI

Overview

Blockchain technology has ushered in a new era of decentralized applications, but its widespread adoption is often hindered by inherent scalability limitations. The challenge lies in processing a high volume of transactions without compromising the fundamental security properties of decentralization and immutability. Sharding has emerged as a promising solution, segmenting the network into smaller, parallel divisions or shards to boost transaction throughput and reduce consensus overhead. However, this approach introduces a critical trade-off: smaller shards, while increasing parallelism, also become more susceptible to adversarial attacks.

This talk, presented by Yibin Xu at the NDSS Symposium, introduces Reticulum, a novel two-layer blockchain sharding protocol designed to overcome these scalability and security challenges. Reticulum distinguishes itself by explicitly leveraging both liveness and safety properties, a strategy often attempted but rarely achieved without introducing new vulnerabilities or significant overheads like frequent shard respawning or overlapping memberships. The core innovation lies in its unique two-phase voting mechanism, which intelligently distributes workload and dynamically adapts to adversarial behavior, ensuring both high performance and robust security.

Reticulum's significance stems from its ability to address long-standing issues in blockchain sharding. By providing a secure and efficient framework that avoids the pitfalls of prior attempts, it offers a tangible path towards highly scalable decentralized systems. The research not only presents a comprehensive analytical framework but also validates its claims through a fully functional, open-source prototype, inviting further exploration and development in the blockchain community.

Background

▶ Watch: Introduction to blockchain sharding challenges (0:00)

To appreciate Reticulum's contributions, it's essential to understand the foundational concepts and existing challenges in blockchain sharding. At the heart of any distributed consensus system are two critical security properties: liveness and safety. Liveness ensures that a network (or shard) can eventually achieve consensus and make progress, meaning honest nodes will eventually agree on a block. Safety guarantees the accuracy and exclusivity of that consensus, preventing honest nodes from agreeing on conflicting blocks. These properties are quantified by the safety threshold (S) and liveness threshold (L), which represent the maximum ratio of adversarial participants a shard can tolerate while maintaining its respective guarantee.

Traditional sharding solutions typically adopt a conservative approach, assuming a worst-case adversarial model where adversaries attack both liveness and safety simultaneously. This often leads to thresholds like S = L = 50% in a synchronous network, which limits parallelism by requiring larger, more robust shards to withstand attacks. While some recent proposals, such as Gearbox and Rapidchain, have attempted to increase throughput by differentiating between liveness and safety attacks (e.g., increasing S while decreasing L), they frequently introduce their own set of problems. These include costly and frequent shard respawning, where shards are reformed to expel adversaries, or the creation of overlapping shards, which adds complexity and increases the workload on individual nodes. As highlighted in Section V-A of the research, many existing designs, especially those operating in synchronous or partially synchronous environments with certain safety thresholds (S $\ge$ 1/2 or S $\ge$ 1/3 respectively), are prone to equivocation, where different honest nodes may observe conflicting states. Moreover, most lack specific, proactive mechanisms to mitigate liveness attacks, often only detecting them after the fact.

Reticulum's system model operates within a standard synchronous peer-to-peer network comprising N nodes. Node identities are generated via Proof-of-Stake (PoS) to ensure Sybil-resistance. Messages are authenticated and propagated using a synchronous gossip protocol, with a known upper bound Δ on network delay. The threat model considers adaptive, upper-bounded Byzantine adversaries capable of corrupting up to f = (N-1)/3 nodes. These adversaries can collude, send invalid messages, or remain silent. It's crucial to note that while a non-sharded network can tolerate f = (N-1)/2 adversaries, a sharded network with shard size M cannot withstand f = (M-1)/2 adversaries within a shard without a high probability of failure. Theorem 1 further establishes that guaranteeing constant liveness and safety across the entire system necessitates at least 2(N-1)/3 + 1 uncorrupted participants remaining active. Reticulum also introduces the concept of a τ liveness guarantee, where nodes failing to meet this guarantee are subject to expulsion, a novel approach to actively combat liveness attacks.

Key Findings

▶ Watch: Core security properties: Liveness and Safety defined (2:00)

Reticulum's research presents several pivotal findings and contributions that significantly advance the state-of-the-art in blockchain sharding:

• Secure and Efficient Liveness/Safety Leveraging: Reticulum is the first protocol to effectively leverage distinct liveness and safety properties without succumbing to known security breaches like equivocation. It achieves this by actively inhibiting adversarial behaviors without the need for runtime shard respawning or the complexities of overlapping shard memberships.
• Novel Two-Layer Consensus Architecture: The protocol introduces a unique two-layer consensus mechanism, comprising process shards and control shards. This design intelligently separates workload: process shards prioritize high parallelism with a stringent unanimous voting requirement for transactions, while control shards act as a robust safety net, resolving disputes and ensuring overall system integrity with a more traditional majority consensus.
• Proactive Liveness Attack Inhibition: Reticulum integrates a robust expulsion mechanism tied to a τ liveness guarantee. This allows the system to detect and penalize nodes that intentionally halt progress by remaining silent or voting for rejection. Adversarial nodes violating this guarantee are expelled and their staked assets confiscated, dynamically adjusting throughput and maintaining system resilience.
• Guaranteed Security Against Equivocation: Unlike many prior L/S leveraging designs, Reticulum is formally proven to prevent equivocation. Theorem 4 demonstrates its security by ensuring that process blocks are confirmed by their control shards before the next epoch, and all votes are aligned through synchronous Byzantine Broadcast protocol ((Δ+δ)-BB).
• Superior Performance and Resource Efficiency: Comprehensive analytical and empirical evaluations consistently show Reticulum outperforming state-of-the-art sharding protocols like Rapidchain and Gearbox. It achieves significantly higher transaction throughput and lower storage overhead per transaction, especially under varying adversarial conditions and liveness guarantee settings.

Technical Deep Dive

▶ Watch: Reticulum's core two-layer consensus mechanism (4:00)

Reticulum's core innovation lies in its two-layer consensus mechanism, designed to intelligently balance scalability and security. Each node in the network is a member of exactly one process shard and one control shard. A crucial design choice is that these memberships are static and non-overlapping at runtime, eliminating the overheads associated with dynamic adjustments or overlapping shards. All nodes also connect to a public communication chain (PC), which serves as the backbone for coordinating the sharding protocol and storing metadata.

The consensus process unfolds in two distinct phases:

1. Phase One: Process Shards for High Parallelism: Members of a process shard are responsible for generating and voting on process blocks containing transactions. These shards operate with an exceptionally high safety threshold (S) = 100% and a liveness threshold (L) = 0%. This means a process block is only accepted if it receives a unanimous vote from all honest nodes within the shard. While this maximizes parallelism and throughput when nodes are honest, it also means even a single adversarial node can halt progress within that specific process shard.
2. Phase Two: Control Shards for Robustness and Dispute Resolution: If a process block fails to achieve a unanimous verdict in the first phase, it is escalated to its governing control shard. Each control shard operates with a more traditional security posture, maintaining L, S $\ge$ 50%, offering comparable worst-case security to other state-of-the-art protocols. In this phase, the control shard reaches a majority verdict on the disputed block. Votes from process shards are broadcast to their corresponding control shards using the Byzantine Broadcast protocol ((Δ+δ)-BB), which ensures alignment among honest nodes despite adversarial interference.

Reticulum also incorporates a robust expulsion mechanism to combat liveness attacks. If a node in a process shard votes for rejection or remains silent for a predefined number of votings (the τ liveness guarantee), it is marked as a "violated node." If marked twice, the node is permanently expelled from the system, and its staked Proof-of-Stake is confiscated. This mechanism allows Reticulum to dynamically adjust transaction throughput: when fewer adversaries attack liveness, more process blocks pass unanimously, leading to higher throughput. Conversely, if more adversaries attempt to halt progress, more blocks are routed to control shards, increasing cost but maintaining overall system resilience. Corollary 1 states that if adversaries permanently leave to halt the system, their PoS is confiscated, and the system recovers by seeking unanimous consensus among the remaining honest nodes.

The public communication chain (PC) is a totally-ordered broadcast ledger with persistence and timestamp guarantees, executed by all nodes. Its size is independent of shard content. The system uses Λ control shards, each with at least Nc = N/Λ nodes, and β process shards, each with at least Np = N/β nodes. Each process shard is governed by one control shard, which supervises at least Nc/Np process shards. Process shards manage non-overlapping sets of keys, directing transactions accordingly.

Reticulum employs a state-block-state structure. Process shard states are updated with each process block, and new states are formed in each epoch. Blocks link to previous states, not directly to preceding blocks. If a block fails unanimous voting, only the latest state and the rejected block are synced to the control shard, significantly reducing data transfer.

Bootstrapping initializes the system by randomly and unbiasedly assigning nodes to shards. Algorithm 1, getShardIndex, determines a node's process and control shard memberships based on a global random number generator and a predetermined list of N nodes. Lemma 1 guarantees the safety of this assignment, preventing a node from being assigned to multiple shards.

For cross-shard communication, Reticulum simplifies existing complex protocols by maintaining fixed shard memberships. This allows for direct integration of various cross-shard transaction protocols, as signatures from cross-shard transactions can be trusted without concerns about changing shard members. Algorithm A.3 in the appendix outlines a design for handling cross-shard transactions, ensuring validity, consensus participation, and proof of transaction (Lemma 2).

Shard sizes and time-bounds are carefully calculated. The process shard size Np is determined by the probability of a process shard being compromised (Pfp) and the maximum adversarial ratio (Pa), using Np = log_Pa(Pfp) (Eq. 2). The control shard size Nc is set based on its failure rate (Pfc) and Pa, ensuring S=L $\ge$ 50% (Eq. 3). Table I provides example Np and Nc values. The overall system failure rate Pf is bounded by Pf $\approx$ Pfp β + Pfc Λ (Eq. 5). Time-bounds T1 and T2 are crucial: T1 is constant for unanimous voting in process shards, while T2 dynamically adjusts based on the number of succeeded process shards (Eq. 1), ensuring consistent network bandwidth. In analytical comparisons, T1 is 46s, and T2 can range from 50s (best case) to 800s (worst case), leading to an epoch time (Etime = T1 + T2) between 136s and 886s.

The security analysis in Section V-A highlights critical security breaches in existing L/S leveraging designs. Lemma 3 proves that synchronous shards with S $\ge$ 1/2 or partially synchronous shards with S $\ge$ 1/3 are inherently unable to achieve consensus without the possibility of equivocation. This is because an insufficient number of honest votes can lead to inconsistent views among honest nodes. Reticulum, however, is designed to avoid these vulnerabilities. Theorem 4 formally states that Reticulum is secure when operating with L = 0% and S = 100% process shards, and L, S $\ge$ 50% control shards. This security is guaranteed because process blocks are confirmed by their corresponding control shard before the next epoch, and votes are broadcast using synchronous Byzantine Broadcast to all nodes in the control shard, preventing consensus equivocation.

Regarding overhead in Byzantine Broadcast Protocol utilization, traditional BFT protocols like PBFT incur O(M²) communication complexity. While (Δ+δ)-BB typically has O(N²) complexity, Reticulum optimizes this by combining step 2 of all (Δ+δ)-BB instances, maintaining an overall communication overhead of O(N²), albeit with a larger constant than basic BFT protocols. The analysis also explores attacks on liveness with different τ values. A larger τ implies a more relaxed liveness requirement for adversarial nodes, meaning they can remain silent for more epochs before expulsion. Figure 4 illustrates this trade-off between τ and the success rate Rp, showing that even with substantial silent periods, high success rates are achievable, providing a reasonable relaxation compared to constant liveness requirements.

Demo / Proof of Concept

▶ Watch: Unanimous voting in process shards (L=0%, S=100%) (4:25)

To validate its analytical findings, Reticulum was implemented in Golang and empirically evaluated against a Rapidchain-like Baseline protocol. Due to the unavailability of source code and detailed designs, Gearbox was evaluated purely through mathematical simulations.

The experimental environment consisted of fifteen servers, each equipped with 32-core AMD EPYC 7R13 processors, providing 128 vCPUs, 256 GB RAM, and a 10 Gbps network. A 200ms delay was introduced to messages to simulate geographic distribution and realistic network latency.

Reticulum's resilience was tested under four distinct adversarial attack strategies:

1. BankRun: All adversarial nodes collectively refuse to vote for process blocks in a single epoch. This specific attack can occur once in every τ epochs.
2. Average: Each adversarial node individually skips voting once in a randomly chosen epoch within every τ epochs.
3. Worst: Only one adversarial node consistently refuses to vote at each process shard in every epoch. This strategy aims to halt a process shard for up to τ epochs.
4. Suicidal: Based on the Worst strategy, but adversarial nodes vote at most τ-2 epochs within every τ epoch, intentionally leading to their expulsion.

For the artifact evaluation, practical constraints necessitated a downscaled experiment. This involved 45 nodes, with the system failure probability adjusted to 10⁻². This allowed for the safe implementation of one control shard (comprising all 45 nodes) and three process shards (each with 15 nodes).

The experimental results (Figures 6, 8, 9, 10, 11) consistently confirmed Reticulum's superior performance across various metrics. Figure 6 demonstrated that Reticulum consistently achieved higher throughput than the Baseline protocol under all attack strategies and τ values. Larger τ values (e.g., τ=411 vs. τ=40) reduced the frequency of the "Worst" attack scenario, leading to higher average throughput. For instance, with τ=411, even the "Worst" attack had a mitigated impact, showcasing the system's stability.

When compared against Gearbox through simulation, Reticulum also exhibited significant advantages. Figure 7 illustrated Gearbox's limitations, showing its iterative resizing leading to overlapping shards, which increases workload and cross-shard transaction complexity. Furthermore, Gearbox's design was prone to equivocation, and its control chain imposed a substantial communication burden on all system nodes. Figure 8 directly compared Reticulum's throughput with Gearbox under different adversarial ratios (Pa-run: 10%, 20%, 30%). Reticulum consistently maintained significantly higher throughput. For example, at Pa-run=30%, Reticulum's throughput remained robust across all attack types, while Gearbox's throughput was notably lower and less stable.

Figure 9 highlighted Reticulum's efficiency in storage, showing consistently less storage incurred per transaction compared to Gearbox across all adversarial ratios and attack types. This efficiency is attributed to Reticulum's two-layer design and the unanimous voting in process shards, which allows a greater volume of transactions to be handled at the process shard level, involving fewer nodes. Figures 10 and 11 further detailed the storage and download bandwidth comparisons between Reticulum and Baseline, reinforcing Reticulum's superior performance with lower storage per transaction and more stable bandwidth usage, particularly under various attack scenarios. The "silent nodes ratio" in these figures effectively illustrated how Reticulum's expulsion mechanism managed adversarial behavior.

Defensive Implications

▶ Watch: Detailed system architecture and shard structure (6:00)

Reticulum's research offers profound implications for defenders and architects of blockchain systems, particularly those grappling with scalability and resilience in sharded environments. The insights derived from its design and evaluation provide a blueprint for building more robust and performant decentralized ledgers.

Firstly, the explicit distinction and leveraging of liveness and safety properties, coupled with dynamic adaptation, is a critical takeaway. Defenders should move beyond a one-size-fits-all security model and consider mechanisms that dynamically adjust to the observed adversarial behavior. Reticulum demonstrates that by tolerating temporary liveness attacks in smaller, highly parallel shards, and providing a robust safety net with larger, more secure control shards, overall system throughput can be dramatically increased without sacrificing security. This suggests that future sharding designs should prioritize a tiered security approach.

Secondly, the expulsion mechanism tied to the τ liveness guarantee is a powerful defensive primitive. Implementing a proactive system to detect and penalize nodes that intentionally disrupt liveness (e.g., by remaining silent or consistently voting against valid blocks) is crucial. This not only deters adversaries but also ensures system recovery and maintains progress. Defenders should explore similar reputation-based or stake-slashing mechanisms that automatically adapt to and mitigate liveness attacks, thereby reducing the window of opportunity for denial-of-service attempts.

Thirdly, Reticulum's proven resilience against equivocation (Theorem 4) highlights a fundamental vulnerability in many existing L/S leveraging protocols. Defenders must ensure that their sharding protocols incorporate strong synchronization mechanisms, like Reticulum's use of synchronous Byzantine Broadcast to align control shard views, to prevent honest nodes from holding conflicting views of the ledger. This is paramount for maintaining the integrity and consistency of the blockchain.

Finally, the fixed and non-overlapping shard memberships, combined with the state-block-state structure, offer significant advantages in simplifying cross-shard communication and reducing data transfer overhead. For defenders, this means less complexity in managing shard reconfigurations and a more predictable environment for securing inter-shard transactions. Adopting architectures that minimize dynamic re-sharding and optimize data flow can lead to more stable and auditable systems. The performance gains in throughput and storage efficiency also translate directly into more cost-effective and resource-efficient deployments, which is a key consideration for long-term operational security.

Key Takeaways

• Two-Layer Sharding for Scalability: Reticulum introduces a novel two-layer architecture with high-parallelism process shards requiring unanimous votes and robust control shards ensuring safety with majority consensus, effectively balancing throughput and security.
• Proactive Liveness Attack Mitigation: The protocol incorporates an expulsion mechanism based on a τ liveness guarantee, actively penalizing and removing adversarial nodes that attempt to halt progress, a significant improvement over passive detection.
• Guaranteed Security Against Equivocation: Reticulum is formally proven to avoid equivocation issues prevalent in other L/S leveraging designs, ensuring consistent views among honest nodes through synchronous Byzantine Broadcast and inter-epoch confirmation.
• Superior Performance and Efficiency: Both analytical and empirical evaluations demonstrate Reticulum's significantly higher transaction throughput and lower storage overhead compared to state-of-the-art protocols like Rapidchain and Gearbox.
• Static, Non-Overlapping Shard Membership: By maintaining fixed shard memberships, Reticulum simplifies cross-shard communication, reduces overhead from dynamic reconfigurations, and enhances overall system stability.
• Dynamic Adversarial Adaptation: The protocol dynamically adjusts to the presence of adversaries by routing disputed blocks to control shards and expelling malicious nodes, ensuring resilience without costly shard respawning.

About the Speaker(s)

Yibin Xu is the speaker who presented this detailed technical article on "A Two-Layer Blockchain Sharding Protocol Leveraging Safety and Liveness for Enhanced Performance" at the NDSS Symposium. The transcript and metadata provided focus on the research itself, and as such, no further biographical details such as title, company, or specific academic affiliations were included in the provided input.