PaperlayerView exact revision on arXiv

Source-linked AI summary

Byzantine Reliable Broadcast with Causal Ordering

Mariarosaria Barbaraci, Christian Cachin

arXiv:2609.17074v1cs.DC

TL;DR

Classical single-process happened-before causality is insufficient for Byzantine reliable broadcast because faulty processes can lie about, omit, or forge dependencies. The paper extends reliable broadcast with externalized knowledge, formalizes correct-process-based causal ordering, and implements it using verifiable encapsulation, Bracha-style rounds, and vector-clock scheduling. The protocol implements Byzantine reliable broadcast with causal ordering and has bit complexity O(n^2(|m| + λ + n)) per payload instance.

  • Problem

    Classical single-process happened-before causality is insufficient for Byzantine reliable broadcast because faulty processes can lie about, omit, or forge dependencies.

  • Method

    The paper extends reliable broadcast with externalized knowledge, formalizes correct-process-based causal ordering, and implements it using verifiable encapsulation, Bracha-style rounds, and vector-clock scheduling.

  • Results

    The protocol implements Byzantine reliable broadcast with causal ordering and has bit complexity O(n^2(|m| + λ + n)) per payload instance.

  • Takeaways & Limitations

    BRB-CO separates causal delivery from total order while preserving dependencies among messages in the Byzantine setting.

  • Takeaways & Limitations

    Causality cannot be defined through Byzantine processes’ internal delivery or broadcast events, so the formulation must rely on events at correct processes.

Abstract

from arXiv · show

Reliable and total-order broadcasts in the Byzantine-fault model are well studied, but adding causal order has received comparatively little attention, largely due to the complexity that stems from actions of Byzantine processes. Existing solutions almost exclusively build causal ordering on top of total-order broadcast. The combination of causal order with reliable broadcast remains rare, and the few solutions that exist adopt the classical definition of causality based on events occurring at individual processes (the happened-before relation). This definition is not sufficient to enforce causal ordering among broadcast messages: Byzantine processes can lie about, omit, and forge dependency information and thereby violate the causal order among self-reported events. Such manipulations remain indistinguishable from correct behavior to any single observer. We demonstrate the issue and its consequences via a front-running attack. To close this gap, we extend the notion of reliable broadcast to externalize local potential knowledge. We use this to formalize the first complete definition of causal message ordering in reliable broadcast under Byzantine faults. Unlike the classical formalization, this notion is grounded in the joint observations of a sufficiently large group of correct processes rather than a process's own view. Building on this definition, we characterize the properties of a Byzantine reliable broadcast channel that guarantees causal ordering. We then present an efficient protocol that satisfies these properties: it is resilient to the optimal number of $f < n/3$ Byzantine faults and for one instance that broadcasts payload message~$m$, it has bit complexity $O(n^2(|m| + λ+ n))$, where $λ$ denotes the maximal size of a unique (cryptographic) label for~$m$. Finally, we prove the protocol achieves Byzantine reliable broadcast with causal ordering.

1 Introduction

The paper studies causal ordering for Byzantine reliable broadcast without imposing total order, addressing how Byzantine behavior can conceal dependencies and enable front-running. It introduces a correct-process-based causality notion and a protocol combining verifiable encapsulation, vector clocks, and causal scheduling.

  • Motivation: Existing causal-order solutions largely rely on total-order broadcast, although many applications need only ordering between causally related messages.Relaxing total order can reduce synchronization costs and improve throughput and responsiveness.
  • Problem: Byzantine processes can fabricate, omit, or reorder dependency information, making causally related broadcasts appear concurrent to correct observers.A front-running adversary can learn m, inject m′, and selectively delay m so some processes deliver m′ first.
  • Contribution: The paper defines Byzantine causal ordering from the joint observations of sufficiently many correct processes rather than a single process’s happened-before view.This addresses causal effects involving Byzantine processes while avoiding assumptions about their internal events.
  • Contribution: The work establishes Byzantine reliable broadcast with causal ordering as a distinct primitive rather than building causality on total-order broadcast.The introduction positions this abstraction as useful where reliable delivery suffices but causal dependencies must still be preserved.
  • Protocol: The proposed protocol extends Bracha-style reliable broadcast across concurrent instances using verifiable encapsulation, vector clocks, and a causal barrier for echo and ready validation.Labels are scheduled in dependency-respecting order and then placed in an ordered queue.

2 Preliminaries

The preliminaries define the distributed-system and broadcast setting, explain causal delivery, and introduce Byzantine reliable broadcast channels. They contrast crash-fault assumptions with Byzantine quorum-based reasoning and outline Bracha’s protocol structure.

  • Distributed system model: The model uses authenticated reliable point-to-point channels and permits up to f Byzantine faults only when n > 3f.The network is asynchronous, with no bounds on message delivery or local computation time.
  • Broadcast abstraction: Reliable broadcast delivers each correct sender’s message eventually, without duplication, while preserving agreement and integrity conditions.Agreement can be viewed as consistency of delivered payloads plus totality across correct processes.
  • Causal broadcast: Causal delivery requires every process to deliver m1 before m2 whenever m1 causally precedes m2, while concurrent messages need not share an order.The causal relation is generated by broadcast order, delivery-then-broadcast order, and transitivity.
  • Causal broadcast: Causal broadcast is orthogonal to total order and can be implemented with reliable broadcast plus metadata such as vector clocks recording causal past.FIFO order is weaker because it constrains only messages from the same sender.
  • Byzantine reliable broadcast: Byzantine reliable broadcast extends single-message instances into a channel of uniquely labeled concurrent broadcasts, using Bracha’s SEND, ECHO, and READY rounds.Byzantine quorums provide overlap guarantees that support reliable agreement despite faulty processes.

3 Causal ordering in the Byzantine setting

The paper identifies why traditional, single-process causality is insufficient for Byzantine reliable broadcast and introduces a global, execution-based causal order with an enhanced broadcast abstraction.

  • 3.1 Limitations of existing approaches: Traditional causality cannot account for events at Byzantine processes, so it misses dependencies created through faulty-process actions.Existing definitions restricted to correct-process events can preserve sender FIFO order yet fail to capture causal influence mediated by faulty processes.
  • 3.1 Limitations of existing approaches: Low-level protocol messages can reveal payload information before delivery, allowing adversaries to exploit dependencies even when faulty processes never deliver the payload.Commit-reveal and threshold-decryption approaches also fail without total-order synchronization because payloads may be revealed concurrently and local delivery orders can diverge.
  • 3.2 Stronger causal order for Byzantine reliable broadcast: The proposed abstraction exposes intermediate events so correct processes can observe potential dependencies from a global view rather than relying on one process’s local history.These events include label acknowledgement, commit, quorum scheduling, and delivery-related events occurring between broadcast and delivery.
  • 3.2 Stronger causal order for Byzantine reliable broadcast: The new causal relation orders same-sender messages, captures cross-sender dependencies through global protocol events, and applies transitively to messages delivered by correct processes.It replaces local delivery-to-broadcast influence with events before delivery and after broadcast as observed across correct processes.
  • 3.2 Stronger causal order for Byzantine reliable broadcast: BRB-CO extends Byzantine reliable broadcast with completeness, hiding, and Byzantine causal delivery, anchoring causality in execution events rather than directly in cryptographic secrecy.The abstraction supports causal ordering while keeping payloads hidden until a quorum schedule event.

4 Implementation of BRB-CO

The BRB-CO implementation combines verifiable encapsulation with Bracha-style reliable broadcast, vector-clock scheduling, and five communication phases to enforce causal ordering under Byzantine faults. It tolerates n > 3f and has overall bit complexity O(n^2(|m|+λ+n)) per broadcast instance.

  • Verifiable encapsulation: Verifiable encapsulation hides message m, validates labels and encapsulated data, distributes recoverable shares, and reconstructs m from at least k valid shares.VE supports setup, encapsulation, validation, extraction, verification, and reconstruction operations.
  • Protocol overview: BRB-CO extends Bracha’s reliable broadcast into five phases—SEND, ECHO, READY, SCHEDULE, and RECONSTRUCTION—for parallel causally ordered broadcasts.The protocol uses one-to-all communication in the first phase and all-to-all communication thereafter.
  • Protocol state: The protocol maintains per-sender sequence numbers, scheduled vector clocks, phase-specific label sets, and a FIFO queue for scheduled but undelivered messages.These structures support contiguous label ordering and track progress through the protocol phases.
  • Causal scheduling: Vector clocks and scheduled-state checks form an ECHO causal barrier that delays invalid ECHO messages until their dependencies have been locally scheduled.An ECHO from pj is valid only when its vector clock Wj is componentwise less than or equal to the receiver’s scheduled vector SV.
  • Complexity: For n > 3f Byzantine resilience, BRB-CO communicates in O(n^2) messages and achieves overall bit complexity O(n^2(|m|+λ+n)) per broadcast instance.The Ω(n) vector-clock component is identified as unavoidable for representing causality and concurrency information.

5 Analysis

The analysis proves that BRB-CO satisfies agreement, completeness, validity, and Byzantine causal delivery through its label, scheduling, reconstruction, and delivery mechanisms.

  • If one correct process schedules a label, all correct processes eventually schedule it, establishing label agreement.
  • If (ℓ1, m1) causally precedes (ℓ2, m2), no correct process schedules ℓ2 before ℓ1.
  • Vector clocks carried in ECHO messages make a process wait for dependencies before sending READY, preserving causal order despite Byzantine injections.
  • Theorem 5 proves that Algorithms 1–2 implement the BRB-CO primitive.
  • The protocol reconstructs and delivers a scheduled message after collecting enough SCHEDULE messages and valid shares.
  • Scheduled labels enter a queue and are delivered in dequeue order, so Lemma 2 directly yields Byzantine causal delivery.

6 Related Work

Prior Byzantine causal-ordering approaches largely rely on total-order broadcast or weaker causality definitions, whereas this work targets message-passing broadcast directly.

  • Most existing methods impose causal delivery through total-order broadcast, consensus, and often cryptographic confidentiality mechanisms.
  • Several Byzantine causal-ordering works restrict causality to messages from correct processes, yielding weaker notions than this paper’s target.
  • Related shared-memory work also identifies the difficulty of inferring causality from one participant’s local view, but studies reads and writes rather than broadcast.

7 Conclusion

The paper introduces BRB-CO, formally defines Byzantine causal ordering, and shows that causal delivery can be enforced at the broadcast layer without total order.

  • BRB-CO provides a Byzantine broadcast primitive satisfying a new notion of causality in the presence of Byzantine processes.
  • Causal ordering can be enforced directly at the broadcast layer without total order, supporting concurrency against dependency-manipulation attacks.

A Secure VE instantiations

The paper describes threshold cryptography, VSS, and PVSS as instantiations of verifiable encapsulation, with different communication, setup, and verification trade-offs.

  • Verifiable encapsulation must hide messages, bind identifiers to cryptographic transcripts, verify shares, and reconstruct one consistent message.
  • Threshold ciphers provide confidentiality through shared decryption keys, with labels derived from ciphertext hashes.
  • VSS distributes consistent private shares under a commitment, allowing local validation against one committed secret.
  • PVSS enables public verification without secure channels, using a public transcript and designated encrypted shares.
  • Threshold ciphers require trusted setup, VSS assumes secure channels, and PVSS avoids secure channels at higher communication and computational cost.
Loading 2609.17074v1…