Byzantine reliable broadcast achieves causal ordering among messages
Byzantine Reliable Broadcast with Causal Ordering
Distributed, Parallel, and Cluster Computing
Summary
When computers in a network try to share messages reliably and in the right cause-effect order, some might act maliciously and try to confuse others by lying or hiding information. The authors show that previous ways to make sure messages follow a cause-effect order don't work well against these tricky behaviors. They propose a new approach that looks at the combined observations of many honest computers rather than just one, to keep messages properly ordered. They also created an efficient protocol that can handle up to one-third of the computers being malicious while ensuring messages arrive reliably and in the right causal order.
What this means in practice
- •For distributed system engineers: Develop fault-tolerant communication layers that ensure message causal ordering despite malicious nodes.
- •For blockchain developers: Implement reliable broadcast protocols that prevent manipulation of message dependencies by Byzantine participants.
Authors
Mariarosaria Barbaraci, Christian Cachin
Abstract
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.