Cross-Consensus Reliable Broadcast and its Applications

Cross-Consensus Reliable Broadcast and its Applications

Speakers: Yue Huang

Conference: NDSS Symposium

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

Overview

Modern distributed infrastructures are moving beyond isolated consensus islands toward multi-group coordination architectures -- sharded blockchains, cross-chain bridges, and replicated state machines. This talk introduces Cross-Consensus Reliable Broadcast (CrossRBC), the first formal treatment of how groups with their own consensus protocols can reliably communicate with each other. The researchers present three protocol constructions with increasing efficiency, culminating in CrossRBC-SIG -- the first cross-consensus protocol decoupled from source group size, enabling scalable interconnection of thousands of shards or chains.

Applied to three real-world scenarios, CrossRBC achieves 60% latency reduction for cross-shard coordination (replacing Reticulum's control shard), 50% latency reduction for cross-shard transactions (replacing ChainSpace's BFT initiator), and provides a lightweight cross-chain bridge architecture eliminating the need for expensive third-party relay chains. All code is open-sourced.

Background

▶ Watch: Motivation: moving beyond isolated consensus islands (0:00)

Traditional blockchain systems operate as isolated consensus islands with a single protocol. Modern architectures require multi-group coordination: sharded blockchains need cross-shard communication, cross-chain bridges need reliable message delivery, and replicated state machines need coordination across partitions. Existing solutions treat cross-group communication as ad hoc side features, suffering from three shortcomings: inefficiency (O(MN) cubic complexity for parallel reliable broadcast), fragility (single-leader designs where Byzantine leaders can cause system failure), and inconsistency (compromised nodes sending conflicting intermediate values).

The work builds on three classical distributed systems primitives: Reliable Broadcast (RBC), Byzantine Reliable Agreement (BRA), and Atomic Broadcast (ABC) (exemplified by HotStuff).

Key Findings

▶ Watch: CrossRBC core model and three safety properties (4:00)

• CrossRBC-SIG reduces message complexity to O(N MAC), completely decoupled from source group size M -- enabling scalable interconnection of thousands of shards
• 60% latency reduction for cross-shard coordination compared to Reticulum (NDSS prior work)
• 50% latency reduction under failure conditions for cross-shard transactions compared to ChainSpace (NDSS prior work)
• Three protocol constructions for different trust assumptions: CrossRBC (no consensus needed in target), CrossRBC-WA (reusing target's existing ABC), and CrossRBC-SIG (proof-of-delivery with fetch-and-catchup)
• Eliminates complex timeout timers in cross-shard transaction protocols by directly guaranteeing reliable delivery
• Scalability validated: Latency degradation is minimal and linear as fault tolerance increases from 10 to 30

Technical Deep Dive

▶ Watch: Application 1: 60% latency reduction replacing Reticulum (8:00)

CrossRBC (Baseline): For scenarios where the target group B has no pre-existing leader, nodes in A send messages to B, nodes in B wait for a threshold of t+1 matching messages, then run Reliable Agreement to decide. Communication complexity: O(NL + KPA^2).

CrossRBC-WA (With Atomic Broadcast): For blockchain-to-blockchain scenarios, reuses the target group's existing atomic broadcast infrastructure. A delivery predicate validates that values are supported by sufficient evidence from the source group. Communication complexity: O(NL + ABC complexity with K-byte messages).

CrossRBC-SIG (Proof of Delivery): The flagship protocol using a single responsible node to send messages and proofs to the target group. Proof-of-delivery serves as a fetch-and-catchup mechanism handling malicious responsible nodes. Communication complexity: O(NL + ABC complexity with K-byte messages), decoupled from source size M.

Three core properties are guaranteed: safety (consistent ordering), integrity (at-most-once delivery from authenticated source), and termination (eventual delivery if sufficient correct nodes broadcast).

Demo / Proof of Concept

▶ Watch: Application 2: 50% latency reduction replacing ChainSpace (9:00)

Evaluated on AWS across three applications. Cross-shard coordination replaces Reticulum's expensive control shard with CrossRBC-WA, achieving 60% latency reduction at 30 failure nodes. Cross-shard transactions replace ChainSpace's fragile BFT initiator (single point of failure) with CrossRBC, eliminating complex timeout-based recovery and reducing latency by 50% under failure conditions. A cross-chain bridge middleware using CrossRBC-SIG creates two-way pegs between chains with guaranteed atomicity.

Defensive Implications

▶ Watch: Q&A: deployment without changing existing chain consensus (12:00)

• Byzantine fault tolerance: CrossRBC provides formally guaranteed reliable delivery even when up to t nodes in the source group are malicious
• Elimination of single points of failure: Replacing BFT initiator designs removes a known attack vector in cross-shard protocols
• Cross-chain security: Guaranteed atomicity in cross-chain bridges prevents the partial-execution attacks that have led to billions in DeFi exploits
• Scalable security: Source-size-independent complexity means security guarantees don't degrade as networks grow

Key Takeaways

• CrossRBC is the first formal primitive for inter-group communication in multi-consensus systems
• CrossRBC-SIG achieves source-size-independent complexity, enabling thousands of shards to interconnect
• 60% and 50% latency reductions over prior NDSS work (Reticulum, ChainSpace) in cross-shard scenarios
• Eliminates fragile single-leader designs and complex timeout recovery mechanisms
• All code is open-sourced for community extension

About the Speaker(s)

Yue Huang (Hu) is a researcher at Tsinghua University. The research is a collaboration between Tsinghua and partnering institutions, addressing a critical gap in distributed systems security infrastructure.