Byzantine Reliable Broadcast with Causal Ordering: (Research statement)

As decentralized systems become increasingly prevalent, the need for robust communication primitives resilient to Byzantine faults continues to grow. While Byzantine reliable and total-order broadcast have been extensively studied, causal ordering has received comparatively limited attention due to its inherent complexity in the Byzantine model. Existing approaches mainly enforce causal ordering starting from total-order broadcast, while fewer address the problem directly, building on reliable broadcast. However, most work on the latter adopt the classical notion of causality defined in terms of individual process observations, which fails to capture subtle adversarial behaviors. In particular, Byzantine processes may manipulate, omit, or hide dependency information to induce causality violations that remain undetected by existing definitions. We illustrate this limitation through a front-running attack that breaks causal consistency based on reliable broadcast while preserving the locally observable behavior of correct processes. To address these shortcomings, we introduce a new, extended notion of reliable broadcast, together with a more general definition of causality in the Byzantine model. It is grounded in observations from sufficiently many correct processes rather than in the actions or reports of individual participants. With the help of this additional information, we characterize the security properties required by a reliable broadcast primitive to guarantee causal ordering in the presence of Byzantine faults.