Source-linked AI summary
Byzantine Causal Reliable Broadcast with Constant Metadata Overhead
Purv Patel, Ajay D. Kshemkalyani
TL;DR
Existing BCRB approaches face trade-offs in safety, front-running, consensus overhead, or metadata cost. The paper re-engineers Bracha’s reliable broadcast to integrate causal ordering. It reports strong safety and liveness with constant metadata and quadratic communication complexity, while retaining throughput independent of message latency.
Problem
Existing BCRB protocols often use O(n) message metadata, and prior constant-metadata alternatives do not provide the same guaranteed safety.
Source: §1 · p. 1Method
The algorithm re-engineers Bracha’s BRB to integrate causal-ordering logic with reliable delivery.
Source: §1 · p. 1Results
O(1) message metadata, O(n^2) messages, and O(n^2) communication word complexity versus O(n^3) for existing protocols, with strong safety and liveness.
Source: §5 · p. 7Takeaways & Limitations
Throughput and sending rate are not limited by message latency because a process need not await local delivery before sending its next BCRB instance.
Source: §1 · p. 1A Byzantine sender can permanently halt its own message stream at correct processes by sending conflicting or arbitrary-sequence messages, or selectively omitting protocol messages.
Source: §4.2 · p. 7
Abstract
from arXiv · showhide
Asynchronous Byzantine Reliable Broadcast (BRB) is a fundamental primitive that guarantees agreement and validity in distributed systems subject to Byzantine faults, but it lacks ordering guarantees. Causal message ordering is important for many applications such as blockchain and social networking. Existing solutions for Byzantine Causal Reliable Broadcast (BCRB) have several drawbacks. Such protocols typically append vector clocks or dependency barriers to application messages, resulting in a metadata overhead that scales linearly with $n$, the number of processes in the system. In this paper, we propose the first optimal message overhead BCRB algorithm that guarantees safety. We do this by re-engineering Bracha's BRB algorithm with relatively small but critical modifications, and prove that our algorithm solves BCRB with optimal message metadata. The algorithm achieves constant-size $\mathcal{O}(1)$ message metadata overhead and $\mathcal{O}(n^2)$ messages, resulting in $\mathcal{O}(n^2)$ communication word complexity. This is as against $\mathcal{O}(n^3)$ communication word complexity of existing protocols. The algorithm tolerates $f < n/3$ Byzantine processes, which is the well-known optimal resilience bound, and uses four phases.
1 Introduction
Causal ordering can address message-order conflicts in Byzantine systems, but existing Byzantine Causal Reliable Broadcast (BCRB) protocols face trade-offs in safety, front-running, consensus overhead, or metadata cost. This paper re-engineers Bracha’s reliable broadcast to provide strong safety and liveness with constant metadata overhead.
1 Introduction
- Causal ordering follows Lamport’s happens-before relation, while total-order primitives are described as requiring heavy consensus overhead and randomization.The introduction connects consistent transaction ordering to decentralized state-machine replication, financial ledgers, and social networks.Source: §1 · p. 1
- Prior protocols typically use O(n) message metadata and O(n^3) communication word complexity, while the known O(1)-metadata, O(n^2)-message alternative has probabilistic safety bounds.The paper presents its result as filling the gap with a safety guarantee.Source: §1 · p. 1
- Existing BCRB approaches can weaken safety, accept front-running, couple application data to costly consensus, or incur O(n) metadata.The cited options include weak-safety protocols and probabilistic-safety protocols [14].Source: §1 · p. 1
- The protocol provides strong safety and liveness with O(1) message metadata, O(n^2) messages, and O(n^2) communication word complexity.The paper contrasts its communication word complexity with O(n^3) for previous protocols.Source: §1 · p. 1
- The algorithm tolerates f < n/3 Byzantine processes, uses four phases, and gives new definitions of Byzantine happens-before and BCRB.The paper identifies f < n/3 as the optimal fault-tolerance bound.Source: §1 · p. 1
2 System Model and Background
The paper sets an asynchronous Byzantine system model, defines its broadcast events and causal-order requirements, and reviews existing BCRB approaches and Bracha’s reliable-broadcast protocol. Its new Byzantine happens-before relation accounts for causal influence through Byzantine processes.
2.1 System Model
- The model has n processes, up to f < n/3 Byzantine faults, and reliable authenticated FIFO channels; it also assumes threshold decryption requiring n−f valid shares.The paper calls the resilience bound optimal.Source: §2.1 · p. 2
2.2 Broadcast Primitives
- The application invokes bcrb_broadcast to causally broadcast plaintext, while bcrb_deliver returns the sender, sequence number, and ordered plaintext.The paper distinguishes plaintext_ready, bcrb_ready, and bcrb_deliver events; their order can vary across processes, but delivery occurs last.Source: §2.2 · p. 2
2.3 Safety and Liveness Definitions
- The new Byzantine happens-before relation orders each sender’s delivered messages by sequence number and links a message read before a later broadcast, including influence involving Byzantine processes.The relation is defined over messages delivered by correct processes and is described as a partial order.Source: §2.3 · p. 2
- BCRB requires validity, agreement, integrity, strong causal safety, and liveness; strong safety orders causally related deliveries even when the causal chain includes Byzantine processes.A proposed alternative based on bcrb_ready can misstate causality if plaintext becomes available earlier or remains unavailable at that event.Source: §2.3 · p. 3
2.4 Background: Byzantine Causal Broadcast
- Earlier protocols trade overhead and guarantees: causal barriers add O(n) metadata and O(n^3) communication, while another approach uses randomized total order and offers strong safety only with high probability.The causal-barrier protocol provides liveness and weak safety; the total-order approach prevents front-running but couples data to costly consensus.Source: §2.4 · p. 3
2.5 Background: Bracha’s Reliable Broadcast
- Bracha’s broadcast has init, echo, and ready steps, with quorum thresholds that support validity, agreement, and integrity despite sender equivocation.Processes send ready after enough echo or ready messages and deliver after receiving 2f+1 ready messages.Source: §2.5 · p. 3
3 Proposed Algorithm
The proposed algorithm integrates causal ordering into Bracha’s reliable-broadcast logic rather than placing it in a separate layer. Its modifications include a BCRB-ready event and a fourth ACK phase.
3.1 Basic Idea
- The algorithm integrates causal ordering with reliable delivery by re-engineering Bracha’s BRB, aiming for strong safety with constant message overhead.The design routes payloads through O(n^2) BRB and then exchanges decryption shares.Source: §3.1 · p. 3
- Unlike the prior causal-barrier approach, which attaches O(n) dependency metadata, this design integrates the ordering logic with the BRB layer.The prior approach buffers BRB-delivered messages until identified causal predecessors are delivered.Source: §3.1 · p. 3
- A message becomes BCRB-ready after a correct process handles 2f+1 READY messages; it is then queued for delivery, pending possible decryption.The algorithm also adds a fourth ACK phase.Source: §3.1 · p. 3
9 Msg: record {
The protocol integrates causal barrier checks into Bracha’s BRB phases, delaying phase transitions until relevant dependencies are locally satisfied. It computes barriers locally using ACK-related state rather than transmitting barrier metadata.
Causal barrier checks
- Causal barriers gate READY broadcasts so a causally prior message is BCRB-ready and enqueued before its successor can be BCRB-ready.The proof ties each barrier to an ECHO or READY message and shows that a dependency must be locally satisfied before the corresponding READY is broadcast.Source: §9 · pp. 4–5
- Barrier checks delay transitions to later BRB phases until dependencies are satisfied, but do not alter Bracha’s BRB properties.Checks apply to the required quorum of ECHO or READY messages.Source: §9 · p. 5
Local barrier computation
- The algorithm computes barriers incrementally from ACKs and local state, without transmitting barrier data or metadata.Processes update an n×n matrix D from valid ACK shares and use a local vector LD to track BCRB-ready sequence numbers; barriers are then checked against LD.Source: §9 · p. 5
4 Correctness Proof
The correctness proof establishes causal safety alongside BRB validity, agreement, and integrity. It also gives the protocol’s complexity and notes that a Byzantine sender can halt its own message stream.
4.1 Safety
- If m→m′, no correct process BCRB-delivers m′ before m, and m is BCRB-ready before m′ at each correct process.The proof establishes the delivery-order guarantee and its corresponding ready-order corollary.Source: §4.1 · p. 6
4.2 Validity, Agreement, and Integrity
- The protocol satisfies validity, agreement, and integrity: correct broadcasts reach all correct processes, delivery is consistent, and messages are delivered at most once.For a correct sender, a message is delivered only if that sender broadcast it.Source: §4.2 · pp. 6–7
- A Byzantine sender can permanently halt its own message stream at correct processes by sending conflicting or arbitrary-sequence messages or selectively omitting protocol messages.The stated effect is confined to that Byzantine sender’s stream.Source: §4.2 · p. 7
4.3 Complexity
- The protocol has O(n^2) messages, O(1) message metadata, and O(n^2(|m| + 1)) communication word complexity, scaling as O(n^2).The four phases comprise Bracha’s INIT, ECHO, and READY phases plus an ACK phase.Source: §4.3 · p. 7
5 Conclusions
The conclusion presents a BCRB protocol with optimal O(1) metadata overhead and O(n^2) communication word complexity, achieving strong safety and liveness by integrating causal-order logic into Bracha’s BRB layer.
5 Conclusions
- The protocol guarantees strong safety and liveness while achieving optimal O(1) metadata overhead and O(n^2) communication word complexity.Existing algorithms have O(n^3) communication word complexity.Source: §5 · p. 7
- Reengineering Bracha’s BRB layer integrates causal-order logic with reliable delivery, using O(n^2) messages with O(1) metadata.The approach relies on Bracha’s quorum amplification and threshold properties.Source: §5 · p. 7
- The design is specific to Bracha’s algorithm but can be analogously integrated into other BRB protocols, such as Imbs-Raynal.Source: §5 · p. 7