Byzantine causal broadcast reduces message size and communication cost
Byzantine Causal Reliable Broadcast (BCRB) with Constant-Size Message Metadata
Distributed, Parallel, and Cluster ComputingData Structures and Algorithms
Summary
Coordinating messages in distributed systems that might have faulty or malicious participants is tricky, especially when message order matters. The researchers designed a new method to ensure messages follow the correct causal order while keeping message information small and communication efficient. Their approach uses both cryptographic and non-cryptographic techniques to prevent issues like premature message reading or replay attacks. They also analyze the probability of errors happening and show the method performs well under certain conditions.
What this means in practice
- •For blockchain platform teams: Enable efficient causal message ordering in blockchain networks with reduced message size and communication overhead to improve scalability and security.
- •For cloud service providers: Improve coordination and fault tolerance of distributed cloud services by integrating Byzantine causal broadcast protocols that reduce network load without sacrificing correctness guarantees.
Authors
Purv Patel, Ajay D. Kshemkalyani
Abstract
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. In this paper, we address Byzantine Causal Reliable Broadcast (BCRB), which builds on BRB to enforce causal message ordering. We present a novel BCRB protocol that decouples causal ordering from the BRB layer, achieving constant-size $\mathcal{O}(1)$ message metadata overhead and $\mathcal{O}(n^2)$ communication word complexity as against $\mathcal{O}(n^3)$ communication word complexity of existing protocols; here $n$ is the number of processes. We present two variants of our protocol: a cryptographic version using a threshold encryption scheme and sequence gating, and its non-cryptographic version. In the cryptographic version, senders broadcast ciphertexts immediately, and decryption shares are piggybacked on out-of-band ACKs, preventing early decryption and front-running. In both versions, causal safety is achieved probabilistically. We evaluate the probability of causal safety violations using a random variable path analysis under independent exponential link delay distributions. We show that both variants satisfy liveness and the probability of weak safety violation is bounded by $\mathcal{O}(f^{-3}\cdot\ln^3 f)$, where $f$ is the upper bound on the number of Byzantine processes, and $f < n/3$ and $f=\mathcal{O}(n)$. Further, for the crypto version, we show that the probability of strong safety violation is bounded by $\mathcal{O}(f^{-1} \cdot \ln^2 f)$. We also show how to modify our two protocols to guarantee 100\% weak safety keeping $\mathcal{O}(1)$ message space overhead but with $\mathcal{O}(n^3)$ messages and $\mathcal{O}(n^3)$ communication word complexity.