Conceptio › Archive › arXiv CS

arXiv CSopen access

Byzantine Causal Reliable Broadcast (BCRB) with Constant-Size Message Metadata

· arxiv_cs

arXiv CS · Papers · License: Open Access

Open Source ↗Direct PDF ↓

cloud distributed-computing parallel-computing

distributed computing, parallel computing, cloud

Byzantine Causal Reliable Broadcast (BCRB) with Constant-Size Message Metadata Purv Patel

Ajay D. Kshemkalyani

University of Illinois Chicago Chicago, USA [email protected]

arXiv:2609.24018v1 [cs.DC] 21 Sep 2026

Abstract

primitives (atomic broadcast) are commonly used to resolve ordering conflicts, they require heavy consensus overhead and use randomization [4]. Byzantine Causal Reliable Broadcast (BCRB) offers a lightweight alternative by delivering messages according to Lamport’s happens-before relationship (→) [6]. However, scaling BCRB to large networks is severely limited by previous algorithms which append O (𝑛) metadata to messages and incur O (𝑛 3 ) communication complexity, where 𝑛 is the number of processes [1, 4]. Decoupling causal delivery from the network layer while maintaining a constant O (1) message metadata overhead presents fundamental challenges in asynchronous systems. It has been shown that (deterministically) achieving both strong causal safety and liveness without using cryptography is impossible in asynchronous Byzantine systems [8–12]. Existing protocols for BCRB weaken safety to weak safety [1, 11], or accept probabilistic safety guarantees as in [4]. Such solutions either couple the application data directly with a costly consensus plane to prevent front-running [4], or incur linear metadata overheads that degrade throughput [1, 4, 13]. To resolve this bottleneck, we present a novel BCRB protocol that achieves constant-size O (1) message metadata. Our protocol layers the causal delivery logic directly atop a standard O (𝑛 2 ) messages Byzantine Reliable Broadcast (BRB) primitive [2], routing application payloads over authenticated point-to-point links. Causal dependencies are tracked and resolved out-of-band using pointto-point acknowledgments (ACKs) and sequence gating, entirely eliminating vector clocks from the broadcast payloads.

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 O (1) message metadata overhead and O (𝑛 2 ) communication word complexity as against O (𝑛 3 ) communication word complexity of existing protocols; here 𝑛 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 O (𝑓 −3 ·ln3 𝑓 ), where 𝑓 is the upper bound on the number of Byzantine processes, and 𝑓 < 𝑛/3 and 𝑓 = O (𝑛). Further, for the crypto version, we show that the probability of strong safety violation is bounded by O (𝑓 −1 · ln2 𝑓 ). We also show how to modify our two protocols to guarantee 100% weak safety keeping O (1) message space overhead but with O (𝑛 3 ) messages and O (𝑛 3 ) communication word complexity.

Contributions: • Cryptographic and Non-Cryptographic Variants: We present a cryptographic version of the protocol (Algorithm 1) that secures payload privacy using threshold decryption. Its non-cryptographic version is Algorithm 2. • Constant Message Metadata Space (O (1)): Message metadata is reduced to just O (1) number of O (1) sized fields, eliminating linear vector overheads. • Communication Word Complexity (O (𝑛 2 )): While existing Byzantine causal broadcast protocols require O (𝑛 3 ) communication word complexity [1, 4], our protocols leverage point-to-point ACKs to sequence dependencies, maintaining a total communication word complexity of O (𝑛 2 ) per causal broadcast. • Probabilistic Analysis: We model link propagation delays as independent exponential variables. We formally prove that the probability of causal weak safety violations decays at a rate of O (𝑓 −3 · ln3 𝑓 ), ensuring high causal integrity in practice. Here 𝑓 is the upper bound on the number of Byzantine processes, 𝑓 < 𝑛/3 (the BRB resilience bound) and 𝑓 = O (𝑛). We also prove that for the cryptographic

CCS Concepts • Theory of computation → Distributed algorithms; Concurrent algorithms; • Computer systems organization → Dependable and fault-tolerant systems and networks.

Keywords Causal Broadcast, Byzantine Fault-Tolerance, Threshold Cryptography, Constant Message Overhead

Introduction

Ensuring consistent transaction order in distributed systems subject to Byzantine failures is essential for applications ranging from decentralized state-machine replication (SMR) to financial ledgers. In these environments, Byzantine processes can observe pending messages, manipulate their delivery order, or inject front-running transactions to extract economic value or compromise consistency. However, probabilistic ordering guarantees are often adequate for non-critical applications such as social networks. While total-order 1

Purv Patel and Ajay D. Kshemkalyani

version of our protocol, the probability of causal strong safety violations is O (𝑓 −1 · ln2 𝑓 ). • Weak Safety Guarantee Extensions: We propose Algorithm 3, a variant of Algorithm 1, that replaces direct ACK broadcasts with a BRB of the ACKs. It achieves 100% causal weak safety, liveness, and a probability of causal strong safety violations O (𝑓 −1 · ln2 𝑓 ). It has O (1) message space overhead at the cost of a higher O (𝑛 3 ) communication word complexity. Algorithm 4 is its non-crypto variant; it lacks a bound on probability of causal strong safety violations.

We define the four primitives of this layered architecture and specify their parameters: • Underlying Layer (BRB): – brb_broadcast(𝑠𝑒𝑛𝑑𝑒𝑟, 𝑠𝑛, 𝑐𝑜𝑛𝑡𝑒𝑛𝑡): Invoked by the BCRB layer of the sending process 𝑝𝑠𝑒𝑛𝑑𝑒𝑟 to reliably broadcast 𝑐𝑜𝑛𝑡𝑒𝑛𝑡 (representing either a ciphertext or plaintext) with a sequence number 𝑠𝑛. – brb_deliver(𝑠𝑒𝑛𝑑𝑒𝑟, 𝑠𝑛, 𝑐𝑜𝑛𝑡𝑒𝑛𝑡): Upcall from the BRB layer to the BCRB layer when 𝑐𝑜𝑛𝑡𝑒𝑛𝑡 from 𝑝𝑠𝑒𝑛𝑑𝑒𝑟 with sequence number 𝑠𝑛 is delivered. The BRB layer guarantees Validity, Agreement, and Integrity. • Causal Layer (BCRB): – bcrb_broadcast(𝑝𝑎𝑦𝑙𝑜𝑎𝑑): Invoked by the application layer at process 𝑝𝑖 to causally broadcast a plaintext 𝑝𝑎𝑦𝑙𝑜𝑎𝑑. – bcrb_deliver(𝑠𝑒𝑛𝑑𝑒𝑟, 𝑠𝑛, 𝑝𝑙𝑎𝑖𝑛𝑡𝑒𝑥𝑡): Upcall from the BCRB layer to the application layer to deliver the ordered 𝑝𝑙𝑎𝑖𝑛𝑡𝑒𝑥𝑡 payload originally sent by 𝑝𝑠𝑒𝑛𝑑𝑒𝑟 with sequence number 𝑠𝑛. The layering operates as follows: bcrb_broadcast(𝑝𝑎𝑦𝑙𝑜𝑎𝑑) encapsulates and encrypts the payload, triggering brb_broadcast(𝑖, 𝑠𝑛, 𝑐𝑖𝑝ℎ𝑒𝑟𝑡𝑒𝑥𝑡) on the ciphertext. When brb_deliver(𝑠𝑒𝑛𝑑𝑒𝑟,𝑠𝑛, 𝑐𝑖𝑝ℎ𝑒𝑟𝑡𝑒𝑥𝑡) occurs, the BCRB layer buffers the message and verifies FIFO sequence numbers, sequence blocks, and decryption shares. Once verified, the BCRB layer decrypts the payload and triggers bcrb_deliver(𝑠𝑒𝑛𝑑𝑒𝑟, 𝑠𝑛, 𝑝𝑙𝑎𝑖𝑛𝑡𝑒𝑥𝑡) to the application. For the non-cryptographic version, the layering follows the same flow but bypasses the encryption and decryption steps.

All our algorithms are throughput-scalable, i.e., throughput and rate of sending are not limited by the latency of messages. We do not wait for the previous BRB to be locally delivered before sending the next BRB.

2 System Model and Background 2.1 System Model We assume an asynchronous distributed system of 𝑛 processes, denoted by 𝑝 1, 𝑝 2, . . . , 𝑝𝑛 . The system is subject to Byzantine failures. Any 𝑓 processes can behave arbitrarily by dropping messages, forging causal histories, or colluding. The number of Byzantine processes is bounded by 𝑓 < 𝑛/3 (the BRB resilience bound) [2, 3] and our probability analysis further assumes 𝑓 = O (𝑛). Processes communicate via reliable and authenticated point-to-point FIFO channels. We assume an underlying Byzantine Reliable Broadcast (BRB) primitive (e.g., Bracha’s BRB [2]) that satisfies Validity, Agreement, and Integrity. • Validity: If a correct process broadcasts 𝑚, all correct processes eventually deliver 𝑚. • Agreement: If a correct process delivers 𝑚, all correct processes eventually deliver 𝑚. • Integrity: A message 𝑚 is delivered at most once by each correct process, and if the sender is correct, then only if it was broadcasted by the sender.

2.3

Definition 2.1. The happens before relation → on application messages consists of the following rules: (1) If 𝑝𝑖 bcrb_broadcast(𝑚) or bcrb_deliver(𝑚) before bcrb_broadcast(𝑚 ′ ), then 𝑚 → 𝑚 ′ . (2) If 𝑚 → 𝑚 ′ and 𝑚 ′ → 𝑚 ′′ , then 𝑚 → 𝑚 ′′ . • Strong Causal Safety: If 𝑚 1 → 𝑚 2 then no correct process triggers bcrb_deliver(𝑚 2 ) before bcrb_deliver(𝑚 1 ) [9– 11]. • Weak Causal Safety: If 𝑚 1 → 𝑚 2 and the causal chain from 𝑚 1 to 𝑚 2 passes exclusively through correct processes, then no correct process triggers bcrb_deliver(𝑚 2 ) before bcrb_deliver(𝑚 1 ) [9–11]. • Liveness: Every message broadcasted via bcrb_broadcast(payload) by a correct process is eventually delivered via bcrb_deliver(payload) at all correct processes. Liveness is same as Validity. Additionally, to reason with our algorithms and executions where Byzantine processes may skip the BCRB layer and directly invoke the underlying BRB layer, we define the happens-before relation →𝑏𝑟𝑏 over the messages broadcast via the BRB layer.

We define Lamport’s happens-before relation → [6] over the set of events in the system. For any two events 𝑒 1, 𝑒 2 , we have 𝑒 1 → 𝑒 2 if: (1) they occur at the same process and 𝑒 1 precedes 𝑒 2 in local execution; (2) 𝑒 1 is the broadcast event of a message and 𝑒 2 is the delivery event of that message; or (3) there exists an event 𝑒 3 such that 𝑒 1 → 𝑒 3 and 𝑒 3 → 𝑒 2 . For the cryptographic version of the protocol, we assume an (𝑛 − 𝑓 , 𝑛) threshold decryption scheme (e.g., Shoup’s threshold cryptosystem [14]), where a ciphertext can only be decrypted once at least 𝑛 − 𝑓 valid decryption shares from distinct processes are collected.

2.2

Safety and Liveness Definitions

Layered Broadcast Primitives

Our protocol separates causal ordering logic from reliable delivery by layering the Byzantine Causal Reliable Broadcast (BCRB) layer directly atop an underlying Byzantine Reliable Broadcast (BRB) layer (e.g., Imbs-Raynal BRB [5] or Bracha’s BRB [2]) requiring O (𝑛 2 ) messages. Note, while our protocol design is general, the probabilistic causal safety analysis presented in Section 5 is specifically valid when utilizing Bracha’s BRB algorithm [2], as it relies on Bracha’s specific quorum amplification and threshold properties.

Definition 2.2. The happens before relation →𝑏𝑟𝑏 on messages broadcast by the BRB layer consists of the following rules: (1) If 𝑝𝑖 brb_broadcast(𝑚) or brb_deliver(𝑚) before brb_broadcast(𝑚 ′ ), then 𝑚 →𝑏𝑟𝑏 𝑚 ′ . (2) If 𝑚 →𝑏𝑟𝑏 𝑚 ′ and 𝑚 ′ →𝑏𝑟𝑏 𝑚 ′′ , then 𝑚 →𝑏𝑟𝑏 𝑚 ′′ . 2

Byzantine Causal Reliable Broadcast (BCRB) with Constant-Size Message Metadata

Problem Definition. BCRB must satisfy Validity, Agreement, Integrity, (Weak and/or Strong) Safety, and Liveness. As we layer BCRB over BRB, Validity, Agreement, and Integrity which are provided by BRB need to be satisfied by the BCRB layer, besides proving Weak or Strong Safety, and Liveness.

concrete node ( 𝑗, 𝑠𝑛); otherwise, it adds ( 𝑗, 𝑠𝑛) directly to the node set 𝑁 . It assigns the local physical clock value as the timestamp ( 𝑗, 𝑠𝑛).𝑡𝑠. To enforce FIFO order, if ( 𝑗, 𝑠𝑛 − 1) is in 𝑁 , it adds the edge (( 𝑗, 𝑠𝑛), ( 𝑗, 𝑠𝑛 − 1)) to 𝐸. It adds the message to the pending set. It then calls check_delivery().

2.4

upon receive ACK(M, next_sn, share, k, h). When process 𝑝𝑖 receives an ACK for message 𝑀 (= (𝑙, 𝑠)) from process 𝑘 declaring 𝑛𝑒𝑥𝑡_𝑠𝑛, 𝑠ℎ𝑎𝑟𝑒, and hash ℎ, it waits until 𝑀 and all prior messages 𝑀 ′ = (𝑙, 𝑠 ′ ) (where 𝑠 ′ < 𝑠) from process 𝑙 are BRB-delivered locally. It further verifies that the message 𝑀 is registered in 𝑁 , the hash matches (ℎ = hash(𝑀.𝑐𝑖𝑝ℎ𝑒𝑟𝑡𝑒𝑥𝑡)), and the sequence number is fresh (𝑉𝑖 [𝑘] < 𝑛𝑒𝑥𝑡_𝑠𝑛). If valid, it records 𝑠ℎ𝑎𝑟𝑒 in shares[𝑀] and updates the dependency graph 𝐺 = (𝑁 , 𝐸) as follows:

Byzantine Causal Broadcast

Misra et al. [9, 11, 12] showed that it is impossible to provide both strong safety and liveness for causal ordering without using cryptography, but weak safety and liveness can be provided. It was formally proved in [7] that Bracha’s BRB [2] does not satisfy even the weak safety property. Byzantine causal broadcast algorithm by Auvolat et al. [1] enforces causal order by attaching a “causal barrier" (predecessor message IDs) to every message. This incurs an O (𝑛) space overhead in application messages and runs directly over an O (𝑛 2 ) messages BRB primitive, generating O (𝑛 3 ) message communication complexity. Cachin et al. [4] proposed a secure causal atomic broadcast protocol using threshold encryption. A sender broadcasts the encrypted payload via an atomic broadcast channel. The use of atomic broadcast leads to a probabilistic, randomized (non-deterministic) solution. Once the ciphertext is totally ordered, processes exchange decryption shares to reveal the plaintext. Although this prevents front-running, it tightly couples the data and control planes, forcing large application payloads to be processed by the expensive totalorder consensus layer (O (𝑛 3 ) communication complexity). Our protocols separate the data and control planes, routing payloads via O (𝑛 2 ) BRB and exchanging decryption shares out-of-band via point-to-point ACKs. A comparison with our protocols is given in Table 1. Auvolat et al. [1] provides liveness and weak safety. Cachin et al. [4] provides liveness, and being randomized, provides weak safety and strong safety with high probability.

• If the message node (𝑘, 𝑛𝑒𝑥𝑡_𝑠𝑛) is already present in 𝑁 and (𝑘, 𝑛𝑒𝑥𝑡_𝑠𝑛).𝑡𝑠 > (𝑙, 𝑠).𝑡𝑠 it adds the edge ((𝑘, 𝑛𝑒𝑥𝑡_𝑠𝑛), (𝑙, 𝑠)) to 𝐸. This ensures deadlock is avoided. • If the message node (𝑘, 𝑛𝑒𝑥𝑡_𝑠𝑛) is not yet in 𝑁 , it adds the edge ((𝑘, 𝑛𝑒𝑥𝑡_𝑠𝑛)𝑡𝑒𝑚𝑝 , (𝑙, 𝑠)) to 𝐸 using a temporary node. It then calls check_delivery(). check_delivery(). This procedure evaluates the pending set. A message 𝑚 = (𝑀 = ( 𝑗, 𝑠𝑛), 𝑐𝑖𝑝ℎ𝑒𝑟𝑡𝑒𝑥𝑡) is delivered to the application if: (1) FIFO order is satisfied locally for the sender 𝑗 (V𝑖 [ 𝑗] = sn − 1). (2) It has gathered at least 𝑛−𝑓 valid decryption shares (|shares[𝑀] | ≥ 𝑛 − 𝑓 ). (3) The node ( 𝑗, 𝑠𝑛) has no outgoing edge in 𝐸 (i.e., there are no active causal dependencies blocking its delivery). If satisfied, the process removes 𝑚 from the pending set, deletes node ( 𝑗, 𝑠𝑛) and all its incident edges from the graph 𝐺, decrypts the ciphertext using the gathered shares, triggers bcrb_deliver on the plaintext, updates V𝑖 [ 𝑗] ← 𝑠𝑛, and loops to check if further pending messages can now be delivered.

Algorithm 1: Cryptographic Version

The cryptographic version of our BCRB protocol integrates an (𝑛 − 𝑓 , 𝑛) threshold decryption scheme and a sequence gating mechanism. Senders encrypt payloads and broadcast immediately. Decryption shares are piggybacked on out-of-band ACKs.

Algorithm 2: Non-Cryptographic Version

Algorithm 2 pseudo-code is same as Algorithm 1, except (1) ciphertext is identical to plaintext, i.e., no encryption/decryption, and (2) decryption share is set to the sender process ID. Without threshold decryption, a Byzantine process can read plaintexts in transit and attempt front-running and not wait for 𝑛 − 𝑓 ACKs before triggering bcrb_deliver.

bcrb_broadcast(payload). When the application layer broadcasts a payload, the sender increments its 𝑙𝑜𝑐𝑎𝑙_𝑠𝑛. The payload is encrypted under the system public key PK to obtain a 𝑐𝑖𝑝ℎ𝑒𝑟𝑡𝑒𝑥𝑡. A message 𝑚 = (𝑖, 𝑙𝑜𝑐𝑎𝑙_𝑠𝑛, 𝑐𝑖𝑝ℎ𝑒𝑟𝑡𝑒𝑥𝑡) is created and immediately broadcasted via the underlying BRB layer. The message carries no vector clocks, ensuring O (1) message overhead.

5 Correctness Proof for Algorithms 1, 2 5.1 Background: Bracha’s Reliable Broadcast

upon brb_deliver(j, sn, ciphertext). Upon BRB-delivering a message ( 𝑗, 𝑠𝑛, 𝑐𝑖𝑝ℎ𝑒𝑟𝑡𝑒𝑥𝑡), a process waits until all preceding messages 𝑀 (= ( 𝑗, 𝑠𝑛 ′ )) for 𝑠𝑛 ′ < 𝑠𝑛 are BRB-delivered to preserve FIFO order. It then computes a cryptographic decryption share 𝑠ℎ𝑎𝑟𝑒 using its secret key share SK 𝑖 , determines its next sequence number 𝑛𝑒𝑥𝑡_𝑠𝑛 ← 𝑙𝑜𝑐𝑎𝑙_𝑠𝑛 + 1, and computes the payload hash ℎ ← hash(𝑐𝑖𝑝ℎ𝑒𝑟𝑡𝑒𝑥𝑡). It broadcasts 𝐴𝐶𝐾 (( 𝑗, 𝑠𝑛), 𝑛𝑒𝑥𝑡_𝑠𝑛, 𝑠ℎ𝑎𝑟𝑒, 𝑖, ℎ) to all processes. The process then updates the local dependency graph 𝐺 = (𝑁 , 𝐸) to represent the causal history: if a temporary node ( 𝑗, 𝑠𝑛)𝑡𝑒𝑚𝑝 already exists (created by a prior ACK delivery), it relabels it as the

To ground our correctness and probability analysis, we review Bracha’s Byzantine Reliable Broadcast (BRB) algorithm [2], which serves as our underlying BRB primitive. Bracha’s protocol uses three types of messages: init (for initial), echo, and ready. A broadcast is initiated by a sender broadcasting init. The correct processes transition through three steps based on threshold quorums: • Step 1: A process waits to receive one init message from the sender. It then broadcasts echo to all. 3

Purv Patel and Ajay D. Kshemkalyani

Table 1: Comparative Analysis of Byzantine Causal Broadcast Protocols Property Deterministic Crypto Message Size Overhead Communic. Complexity Front-Running Protection Throughput-scalable 𝑃 (weak safety violation) 𝑃 (strong safety violation)

Auvolat et al. [1] Yes No O (𝑛) O (𝑛 3 ) No Yes 0 high; front-running + fake causal barriers

Cachin et al. [4] No (randomized) Yes O (𝑛) (Encrypt. Hdrs) O (𝑛 3 ) Yes No 𝜖>0 𝜖>0

Algorithm 1 Yes Yes O (1) O (𝑛 2 ) Yes Yes O ( 𝑓 −3 · ln3 𝑓 ) O ( 𝑓 −1 · ln2 𝑓 )

Algorithm 2 Yes No O (1) O (𝑛 2 ) No Yes O ( 𝑓 −3 · ln3 𝑓 ) front-running

Algorithm 3 Yes Yes O (1) O (𝑛 3 ) Yes Yes 0 O ( 𝑓 −1 · ln2 𝑓 )

Algorithm 4 Yes No O (1) O (𝑛 3 ) No Yes 0 front-running

Algorithm 1: Byzantine Causal Reliable Broadcast (BCRB) with Constant-Size Messages (Process 𝑖) state variables: 𝑙𝑜𝑐𝑎𝑙_𝑠𝑛 ← 0 ; // Seq. num. for process 𝑖 ’s broadcasts 3 V𝑖 ← [0, . . . , 0] ; // Vec. of BCRB-delivered seq. nos. 4 𝑝𝑒𝑛𝑑𝑖𝑛𝑔 ← ∅ ; // processed BRB-delivery, pending BCRB delivery 5 𝑠ℎ𝑎𝑟𝑒𝑠 ← Array of ∅ ; // Maps msg ID to decryption shares 6 𝐺 = (𝑁 , 𝐸 ) ← ( ∅, ∅ ) ; // graph of dependencies between msg IDs

upon receive ACK(M, next_sn, share, k, h): wait until 𝑀 (= (𝑙, 𝑠 ) ) and all 𝑀 ′ = (𝑙, 𝑠 ′ ) where 𝑠 ′ < 𝑠 are brb-delivered and execution of brb-deliver is completed; 27 if 𝑀 ∈ 𝑁 ∧ ℎ = ℎ𝑎𝑠ℎ (𝑀 .𝑐𝑖𝑝ℎ𝑒𝑟𝑡𝑒𝑥𝑡 ) ∧ 𝑉𝑖 [𝑘 ] < 𝑛𝑒𝑥𝑡 _𝑠𝑛 then 28 𝑠ℎ𝑎𝑟𝑒𝑠 [𝑀 ] ← 𝑠ℎ𝑎𝑟𝑒𝑠 [𝑀 ] ∪ {𝑠ℎ𝑎𝑟𝑒 }; 29 if (𝑘, 𝑛𝑒𝑥𝑡 _𝑠𝑛) ∈ 𝑁 ∧ (𝑘, 𝑛𝑒𝑥𝑡 _𝑠𝑛).𝑡𝑠 > (𝑙, 𝑠 ).𝑡𝑠 then 30 add ( (𝑘, 𝑛𝑒𝑥𝑡 _𝑠𝑛), (𝑙, 𝑠 ) ) to 𝐸;

procedure bcrb_broadcast(payload): 𝑙𝑜𝑐𝑎𝑙_𝑠𝑛 ← 𝑙𝑜𝑐𝑎𝑙_𝑠𝑛 + 1; 9 𝑐𝑖𝑝ℎ𝑒𝑟𝑡𝑒𝑥𝑡 ← encrypt(𝑝𝑎𝑦𝑙𝑜𝑎𝑑, PK ); 10 brb_broadcast((𝑖, 𝑙𝑜𝑐𝑎𝑙_𝑠𝑛, 𝑐𝑖𝑝ℎ𝑒𝑟𝑡𝑒𝑥𝑡 )); 7

else if (𝑘, 𝑛𝑒𝑥𝑡 _𝑠𝑛) ∉ 𝑁 then add ( (𝑘, 𝑛𝑒𝑥𝑡 _𝑠𝑛) 𝑡𝑒𝑚𝑝 , (𝑙, 𝑠 ) ) to 𝐸;

check_delivery();

upon brb_deliver(j, sn, ciphertext): wait until 𝑀 (= ( 𝑗, 𝑠𝑛 ′ ) ) for all 𝑠𝑛 ′ < 𝑠𝑛 are brb-delivered and execution of brb-deliver is completed; 13 𝑠ℎ𝑎𝑟𝑒 ← dec_share(𝑐𝑖𝑝ℎ𝑒𝑟𝑡𝑒𝑥𝑡, SK 𝑖 ); 14 𝑛𝑒𝑥𝑡 _𝑠𝑛 ← 𝑙𝑜𝑐𝑎𝑙_𝑠𝑛 + 1; 15 ℎ ← ℎ𝑎𝑠ℎ (𝑐𝑖𝑝ℎ𝑒𝑟𝑡𝑒𝑥𝑡 ); 16 broadcast 𝐴𝐶𝐾 ( ( 𝑗, 𝑠𝑛), 𝑛𝑒𝑥𝑡 _𝑠𝑛, 𝑠ℎ𝑎𝑟𝑒, 𝑖, ℎ) to all; 17 if ( 𝑗, 𝑠𝑛) 𝑡𝑒𝑚𝑝 exists then 18 relabel it as ( 𝑗, 𝑠𝑛); ( 𝑗, 𝑠𝑛).𝑡𝑠 ← local physical clock timestamp;

19 20 21 22 23 24

procedure check_delivery(): 𝑝𝑟𝑜𝑔𝑟𝑒𝑠𝑠 ← True; 36 while 𝑝𝑟𝑜𝑔𝑟𝑒𝑠𝑠 = True do 37 𝑝𝑟𝑜𝑔𝑟𝑒𝑠𝑠 ← False; 38 foreach 𝑚 = (𝑀 = ( 𝑗, 𝑠𝑛), 𝑐𝑖𝑝ℎ𝑒𝑟𝑡𝑒𝑥𝑡 ) ∈ 𝑝𝑒𝑛𝑑𝑖𝑛𝑔 do 39 𝑓 𝑖 𝑓 𝑜_𝑜𝑘 ← (V𝑖 [ 𝑗 ] = 𝑠𝑛 − 1); 40 𝑞𝑢𝑜𝑟𝑢𝑚_𝑜𝑘 ← ( |𝑠ℎ𝑎𝑟𝑒𝑠 [𝑀 ] | ≥ 𝑛 − 𝑓 ); 41 if 𝑓 𝑖 𝑓 𝑜_𝑜𝑘 ∧ 𝑞𝑢𝑜𝑟𝑢𝑚_𝑜𝑘 ∧ ( 𝑗, 𝑠𝑛) has no outgoing edge in 𝐸 then 42 𝑝𝑒𝑛𝑑𝑖𝑛𝑔 ← 𝑝𝑒𝑛𝑑𝑖𝑛𝑔 \ {𝑚}; 43 delete 𝑀 from 𝑁 and all incident edges in 𝐸; 44 𝑝𝑙𝑎𝑖𝑛𝑡𝑒𝑥𝑡 ← decrypt(𝑐𝑖𝑝ℎ𝑒𝑟𝑡𝑒𝑥𝑡, 𝑠ℎ𝑎𝑟𝑒𝑠 [𝑀 ], PK ); 45 V𝑖 [ 𝑗 ] ← 𝑠𝑛; 46 bcrb_deliver( 𝑗, 𝑠𝑛, 𝑝𝑙𝑎𝑖𝑛𝑡𝑒𝑥𝑡 ); 47 𝑝𝑟𝑜𝑔𝑟𝑒𝑠𝑠 ← True; 48 break;

else add ( 𝑗, 𝑠𝑛) to 𝑁 ; ( 𝑗, 𝑠𝑛).𝑡𝑠 ← local physical clock timestamp; if ( 𝑗, 𝑠𝑛 − 1) ∈ 𝑁 then add edge ( ( 𝑗, 𝑠𝑛), ( 𝑗, 𝑠𝑛 − 1) ) to 𝐸; 𝑝𝑒𝑛𝑑𝑖𝑛𝑔 ← 𝑝𝑒𝑛𝑑𝑖𝑛𝑔 ∪ { ( ( 𝑗, 𝑠𝑛), 𝑐𝑖𝑝ℎ𝑒𝑟𝑡𝑒𝑥𝑡 ) }; check_delivery();

Algorithm 2: Non-Cryptographic Byzantine Causal Reliable Broadcast (BCRB) (Process 𝑖) 1

These step thresholds ensure that even if a Byzantine sender attempts to equivocate, no two correct processes can deliver different payloads, and if any correct process delivers a payload, all correct processes eventually deliver it. That is, Validity, Agreement, and Integrity are satisfied.

Same as Algorithm 1 except: (1) ciphertext is identical to plaintext, i.e., encryption/decryption are idempotent operations, and (2) decryption share is set to the sender process ID.

5.2

Correctness Proofs — Weak Safety

Theorem 5.1 (Byzantine Front-Running Mitigation). Under the (𝑛 − 𝑓 , 𝑛) threshold decryption scheme, a Byzantine process cannot decrypt or learn the plaintext content of any message 𝑚 broadcasted by a correct process before it has been BRB-delivered by at least 𝑛 − 2𝑓 correct processes.

𝑛+𝑓

• Step 2: A process waits to receive 2 echo messages or 𝑓 + 1 ready messages. It then broadcasts ready to all. • Step 3: A process waits to receive 2𝑓 + 1 ready messages, after which it delivers (accepts) the payload. 4

Byzantine Causal Reliable Broadcast (BCRB) with Constant-Size Message Metadata

Proof. Reconstructing the plaintext requires at least 𝑛 − 𝑓 distinct decryption shares. Correct processes only compute and broadcast their decryption share 𝑠ℎ𝑎𝑟𝑒 of a message 𝑚 after they have BRB-delivered 𝑚. Suppose a Byzantine process attempts to decrypt 𝑚 prematurely. The Byzantine process controls at most 𝑓 shares. To decrypt, it must obtain at least (𝑛 − 𝑓 ) − 𝑓 = 𝑛 − 2𝑓 decryption shares from correct processes. Since correct processes only broadcast their share upon BRB-delivering 𝑚, the Byzantine process cannot obtain these shares until at least 𝑛 − 2𝑓 correct processes have BRB-delivered 𝑚. Under standard 𝑛 ≥ 3𝑓 + 1 resilience, this requires at least 𝑓 + 1 correct processes to have BRB-delivered 𝑚. Thus, the Byzantine process cannot decrypt or front-run the message contents early, thereby mitigating the impact of front-running attacks. □

– 𝑇2(1) ∼ 𝑇cascade (𝑚 1, READY, 𝑓 + 1, max) represents the second phase of Bracha’s BRB READY cascade. This is the time required for these 𝑓 + 1 READY(𝑚 1 ) messages broadcast at the end of 𝑇1(1) to propagate and be received (besides the 𝑓 + 1 READY broadcast at the start of 𝑇1(1) ) by a quorum of 2𝑓 + 1 correct processes, causing them to broadcast ACK(𝑚 1 ). – 𝑇3(1) ∼ 𝑇cascade (𝑚 1, ACK, 2𝑓 + 1, max) represents the time required for the 2𝑓 +1 ACK messages from correct processes to reach the destination process 𝑝 𝑗 to satisfy the BCRB delivery quorum check of 𝑛 − 𝑓 ACKs. • Path A’ (BRB-delivery of 𝑚 1 to 𝑝 𝑗 , worst-case):

We first analyze the probability of a weak causal safety violation assuming no deadlocks arise and no edge is deleted in the dependency graph 𝐺 for deadlock avoidance. Then in Section 5.7 we analyze the impact of an edge deletion on this probability.

• Path B (BCRB-delivery of 𝑚 2 to 𝑝 𝑗 , best case):

𝐴′ = 𝑇1(1) + 𝑇2(1)

𝐵 = 𝑇1(2) + 𝑇2(2) + 𝑌1 (𝑚 2, INIT, 1, −) + 𝑇3(2) + 𝑇4(2) + 𝑇5(2) where: – 𝑇1(2) ∼ 𝑇cascade (𝑚 1, READY, 𝑓 + 1, max) is the first cascade phase of 𝑚 1 (time for the READY messages sent at the start of 𝑇1(1) to reach 𝑝𝑘 ). We assume the READY from Byzantine processes have already reached 𝑝𝑘 . 𝑇1(2) has same duration as 𝑇1(1) . – 𝑇2(2) ∼ 𝑇cascade (𝑚 1, ACK, 𝑓 + 1, max) is the ACK for 𝑚 1 propagation time from 𝑓 + 1 correct processes to the sender of 𝑚 2 (process 𝑝𝑘 ) so that 𝑝𝑘 delivers 𝑚 1 after which it broadcasts 𝑚 2 . Assume the ACK from Byzantine processes have already reached 𝑝𝑘 . – 𝑌1 (𝑚 2, INIT, 1, −) ∼ Exp(𝜆) is the direct link propagation delay for 𝑚 2 ’s initial broadcast from 𝑝𝑘 to the correct processes. – 𝑇3(2) ∼ 𝑇cascade (𝑚 2, ECHO, 2𝑓 + 1, max) is the ECHO phase of 𝑚 2 in Bracha’s BRB. – 𝑇4(2) ∼ 𝑇cascade (𝑚 2, READY, 𝑓 + 1, max) is the READY phase of 𝑚 2 from correct processes. Assume 𝑓 Byzantine processes have already sent the READY. – 𝑇5(2) ∼ 𝑇cascade (𝑚 2, ACK, 𝑓 + 1, max) is the time for ACK phase of 𝑚 2 from correct processes (to reach 𝑝 𝑗 ). Assume 𝑓 Byzantine processes have already sent the ACK. 𝑝 𝑗 now satisfies BCRB delivery quorum check. • Path B’ (BRB-delivery of 𝑚 2 to 𝑝 𝑗 , best case):

Theorem 5.2 (Probabilistic (Weak) Causal Safety). Let process 𝑝𝑖 broadcast message 𝑚 1 , and correct process 𝑝𝑘 broadcast message 𝑚 2 after delivering 𝑚 1 . The probability that any correct process 𝑝 𝑗 delivers 𝑚 2 before 𝑚 1 is 𝑃 (CO violation at 𝑝 𝑗 ) = 𝑃 (𝐵 < 𝐴) × [1 − (1 − 𝑃 (𝐵 < 𝐴′ )) × (1 − 𝑃 (𝐷 < 𝐶))] where 𝐴, 𝐵, 𝐶, and 𝐷 are defined in the body of the proof. Proof. Let 𝑝𝑖 broadcast 𝑚 1 and 𝑝𝑘 broadcast 𝑚 2 after delivering 𝑚 1 . The sender 𝑝𝑘 must have BCRB-delivered 𝑚 1 prior to broadcasting 𝑚 2 . Under optimal 𝑛 ≥ 3𝑓 + 1 resilience, there are at least 𝑓 + 1 correct processes that have initiated the cascade of 𝑚 1 by broadcasting their READY(𝑚 1 ) messages. To model the probability of a causal ordering (weak safety) violation at a correct process 𝑝 𝑗 (delivering 𝑚 2 before 𝑚 1 ), we define the critical path delay variables. Let each network link delay be an independent exponential random variable with rate 𝜆 (mean delay 1/𝜆). Let 𝑇cascade (𝑀, type, 𝑁 , max) = max(𝑋 1, . . . , 𝑋 𝑁 ) represent the delay to complete a quorum phase, where 𝑁 correct processes send control messages of a given type and all of them arrive at the destination. We let 𝑇𝑖(ℎ) represent the ℎ-th independent realization (or instantiation) of these quorum phase distributions for message 𝑀, capturing independent runs of the same protocol phase. We next define the critical path time durations for the delivery of 𝑚 1 and 𝑚 2 at 𝑝 𝑗 . As 𝑝𝑘 has BRB-delivered 𝑚 1 , it has received at least 𝑓 +1 READY(𝑚 1 ) messages from correct processes, which must have been sent. Start measuring from this sending point in time that triggers a cascade in Bracha’s BRB. • Path A (BCRB-delivery of 𝑚 1 to 𝑝 𝑗 , worst case):

𝐵 ′ = 𝑇1(2) + 𝑇2(2) + 𝑌1 (𝑚 2, INIT, 1, −) + 𝑇3(2) + 𝑇4(2) Counting from the point where BRB delivery of 𝑚 1 occurs at 𝑝𝑘 : • Path C (delivery of the direct ACK of 𝑚 1 from 𝑝𝑘 to 𝑝 𝑗 ): 𝐶 = 𝑋 1 (𝑚 1, ACK, 1, −) ∼ Exp(𝜆)

𝐴 = 𝑇1(1) + 𝑇2(1) + 𝑇3(1)

• Path D (BCRB-delivery of 𝑚 2 to 𝑝 𝑗 , best case):

where: – 𝑇1(1) ∼ 𝑇cascade (𝑚 1, READY, 𝑓 + 1, max) represents the time for the 𝑓 + 1 READY messages sent by those correct processes to reach other 𝑓 correct processes (so that then can then amplify the cascade by themselves broadcasting READY).

𝐷 = 𝑇2(3) + 𝑌1 (𝑚 2, INIT, 1, −) + 𝑇3(3) + 𝑇4(3) + 𝑇5(3) where 𝑇2(3) ∼ 𝑇cascade (𝑚 1, ACK, 𝑓 + 1, max), 𝑇3(3) ∼ 𝑇cascade (𝑚 2, ECHO, 2𝑓 + 1, max), 𝑇4(3) ∼ 𝑇cascade (𝑚 2, READY, 𝑓 + 1, max), and 𝑇5(3) ∼ 𝑇cascade (𝑚 2, ACK, 𝑓 + 1, max). 5

Purv Patel and Ajay D. Kshemkalyani

Letting 𝑍 = RHS − LHS, the goal is to evaluate 𝑃 (𝑍 > 0). The Moment Generating Function (MGF) of 𝑍 is: Î2𝑓 +1 𝑗 𝑚LHS ( 𝑗 ) Î2𝑓 +1 𝑗 𝑚RHS ( 𝑗 ) × 𝑀𝑍 (𝑠) = 𝑗=1 𝑗=1 𝑗 −𝑠 𝑗+𝑠

Under the approximation assumption that each phase ends at all correct processes at the same time, the sequential phases are independent. Observe from Algorithm 1 that a causal ordering violation occurs at 𝑝 𝑗 if 𝐵 < 𝐴 and it does not happen that 𝐴′ < 𝐵 and 𝐶 < 𝐷. (When 𝐴′ < 𝐵 and 𝐶 < 𝐷, 𝑝 𝑗 adds the dependency edge (𝑚 2, 𝑚 1 ) in 𝐺, and 𝑚 1 has been BRB-delivered to 𝑝 𝑗 .) Thus when 𝑚 2 from 𝑝𝑘 is BRB-delivered to 𝑝 𝑗 , its BCRB-delivery is not blocked by 𝑚 1 . Note, since 𝑝𝑖 is correct, its INIT messages follow FIFO order, and all correct processes will broadcast ECHO and the READY messages in expected FIFO order. So we assume that earlier than 𝑚 1 messages 𝑝𝑖 BRB-broadcast are also expected to have BRB-delivered to 𝑝 𝑗 before 𝑚 1 . Since the phases are independent, the probability of the joint event of CO violation is:

By closing the complex contour around the Right Half-Plane (RHP), we isolate only the positive poles. This minimizes the computation since the higher-index positive poles drop down to a multiplicity of 1. The exact probability is found by summing the residues Í2𝑓 +1 of 𝑀𝑍𝑠 (𝑠 ) at these positive poles: 𝑃 (𝑍 > 0) = − 𝑗=1 Res 𝑀𝑍𝑠 (𝑠 ) , 𝑠 = 𝑗 • For 𝑗 ≤ 𝑓 + 1: The poles have a multiplicity of 3, requiring a 2nd-order derivative to find the residue. • For 𝑗 ≥ 𝑓 + 2: The poles have a multiplicity of 1, allowing for a direct substitution without derivatives.

𝑃 (𝐵 < 𝐴) × [1 − 𝑃 (𝐴′ < 𝐵) × 𝑃 (𝐶 < 𝐷)]

To find the asymptotic behavior of the probability, we analyze how the logarithmic growth of the maximum statistics scales on both sides of the inequality. As the sample size grows large, the maximum of 𝑀 independent standard exponential random variables converges to a Gumbel distribution shifted by ln 𝑀: Max𝑀 ≈ ln 𝑀 + 𝐺, where 𝐺 is a standard Gumbel random variable with an exponential upper tail 𝑃 (𝐺 > 𝑥) ≈ 𝑒 −𝑥 .

= 𝑃 (𝐵 < 𝐴) × [1 − (1 − 𝑃 (𝐵 < 𝐴′ )) × (1 − 𝑃 (𝐷 < 𝐶))] We later consider the impact of deadlock avoidance by considering 𝑃 (𝐵 ′ < 𝐴′ ) in Theorem 5.12 (Section 5.7). □

5.3

Analytic Evaluation of Probabilities

To simplify notation, we relabel the terms 𝑇1(1) , 𝑇1(2) , 𝑇1(3) in path 𝐴 as 𝑋 1, 𝑋 2, 𝑋 3 , respectively, the terms 𝑇2(1) , 𝑇2(2) , 𝑇2(3) , 𝑇2(4) , 𝑇2(5) , and 𝑌1 in path 𝐵 as 𝑌1, 𝑌2, 𝑌3, 𝑌4, 𝑌5 , and 𝑌 , respectively.

(1) Right-Hand Side (RHS): The RHS contains two variables of size 𝑓 + 1 and one of size 2𝑓 + 1: RHS ≈ ln(𝑓 + 1) + ln(𝑓 + 1) + ln(2𝑓 + 1) + (𝐺𝑋 ,1 + 𝐺𝑋 ,2 + 𝐺𝑋 ,3 ) Using the logarithmic property ln(2𝑓 + 1) ≈ ln 𝑓 + ln 2, this simplifies Í3 to: RHS ≈ 3 ln 𝑓 + ln 2 + 𝑖=1 𝐺𝑋 ,𝑖 (2) Left-Hand Side (LHS): The LHS contains four variables of size 𝑓 + 1, one of size 2𝑓 + 1, and the standard exponential Í variable 𝑌 : LHS ≈ 4 ln(𝑓 + 1) + ln(2𝑓 + 1) + 𝑌 + 5𝑗=1 𝐺𝑌 ,𝑗 Simplifying the logarithmic growth: LHS ≈ 5 ln 𝑓 + ln 2 + Í 𝑌 + 5𝑗=1 𝐺𝑌 ,𝑗

′ ′ ′ 5.3 (𝑃 (𝐵 < 𝐴), Theorem 𝑃 (𝐵 < 𝐴 ), 𝑃 (𝐵 < 𝐴 )). 𝑃 (𝐵 < 𝐴) = ln2 𝑓 ln 𝑓 ln 𝑓 ′ ′ ′ O 𝑓 2 , 𝑃 (𝐵 < 𝐴 ) = O 𝑓 3 , 𝑃 (𝐵 < 𝐴 ) = O 𝑓 2

Proof. To compute 𝑃 (𝐵 < 𝐴), the exact probability that 𝑌 + 𝑌1 + 𝑌2 + 𝑌3 + 𝑌4 + 𝑌5 < 𝑋 1 + 𝑋 2 + 𝑋 3 can be solved using Rényi’s representation for exponential order statistics. Using Rényi’s representation, the maximum of 𝐾 independent identically distributed exponential variables with rate 𝜆 is identically distributed to a weighted sum of independent standard exponentials with rates scaling from 1𝜆 to 𝐾𝜆. Setting 𝜆 = 1 without loss of generality, we can group the total number of overlapping independent exponential variables (multiplicities) on both sides: Right-Hand Side (RHS) Pools: • From 𝑋 1, 𝑋 2 : Two independent sets of exponentials at each rate 𝑗 ∈ {1, . . . , 𝑓 + 1}. • From 𝑋 3 : One set of exponentials at each rate 𝑗 ∈ {1, . . . , 2𝑓 + 1}. Left-Hand Side (LHS) Pools: • From 𝑌 : One standard exponential at rate 1. • From 𝑌1, 𝑌2, 𝑌4, 𝑌5 : Four independent sets of exponentials at each rate 𝑗 ∈ {1, . . . , 𝑓 + 1}. • From 𝑌3 : One set of exponentials at each rate 𝑗 ∈ {1, . . . , 2𝑓 + 1}. Total Multiplicities by Rate Pool: By aggregating the variables across their respective spans, we establish the pole structures for the system: • Rate range: 𝑗 = 1; LHS multiplicity (Poles at −𝑗): 6; RHS multiplicity (Poles at +𝑗): 3 • Rate range: 2 ≤ 𝑗 ≤ 𝑓 + 1; LHS multiplicity (Poles at −𝑗) : 5; RHS multiplicity (Poles at +𝑗): 3 • Rate range: 𝑓 + 2 ≤ 𝑗 ≤ 2𝑓 + 1; LHS multiplicity (Poles at −𝑗): 1; RHS multiplicity (Poles at +𝑗): 1

Determining the Big-O Bound: We want to find the probability that RHS − LHS > 0. Subtracting the two expressions gives: Í3 Í 3 ln 𝑓 + ln 2 + 𝑖=1 𝐺𝑋 ,𝑖 − 5 ln 𝑓 + ln 2 + 𝑌 + 5𝑗=1 𝐺𝑌 ,𝑗 > 0 Notice that the ln 2 terms from the 2𝑓 + 1 distributions cancel Í3 Í out perfectly, leaving: 𝑖=1 𝐺𝑋 ,𝑖 − 5𝑗=1 𝐺𝑌 ,𝑗 − 𝑌 > 2 ln 𝑓 . Let 𝑊 Í3 represent the combined stochastic error terms: 𝑊 = 𝑖=1 𝐺𝑋 ,𝑖 − Í5 𝐺 − 𝑌 . The problem reduces to evaluating the upper-tail 𝑗=1 𝑌 ,𝑗 probability 𝑃 (𝑊 > 2 ln 𝑓 ): (1) The Exponential Decline (𝑓 2 Denominator): The systemic mean shift moving against the inequality grows at a rate of 2 ln 𝑓 . Because the upper tails of Gumbel variables decay exponentially (𝑒 −𝑥 ), evaluating this decay at the required shift threshold yields: 𝑒 −2 ln 𝑓 = 𝑓12 (2) The Polynomial Prefactor (ln2 𝑓 Numerator): The upper tail of 𝑊 is entirely driven by the convolution of the 3 positive Gumbel variables (𝐺𝑋 ,1, 𝐺𝑋 ,2, 𝐺𝑋 ,3 ). Convolving 𝑘 independent variables with exponential tails introduces a polynomial prefactor of order 𝑥 𝑘 −1 . For 𝑘 = 3, the tail profile behaves as O (𝑥 2𝑒 −𝑥 ). Substituting 𝑥 = 2 ln 𝑓 yields: (2 ln 𝑓 ) 2 = O (ln2 𝑓 ) Combining these two gives the final tight asymptotic dynamics

bound: 𝑃 (𝑍 > 0) = O 6

ln2 𝑓 𝑓2

= 𝑃 (𝐵 < 𝐴).

Byzantine Causal Reliable Broadcast (BCRB) with Constant-Size Message Metadata

Table 2: Comparative Analysis of Features of the Probability derivations. System State

Dominant RHS Growth

Dominant LHS Growth

Net Deterministic Drag

Positive Poles (𝑘)

𝑃 (𝐵 < 𝐴)

3 ln 𝑓

5 ln 𝑓

2 ln 𝑓

𝑃 (𝐵 < 𝐴′ ); Remove 𝑋 3

2 ln 𝑓

5 ln 𝑓

3 ln 𝑓

𝑃 (𝐵 ′ < 𝐴′ ); Remove 𝑋 3 ,𝑌5

2 ln 𝑓

4 ln 𝑓

2 ln 𝑓

ordering weak safety violation at any correct process 𝑝 𝑗 (for a path

If we remove 𝑋 3 from the Right-Hand Side (RHS), proceeding along similar lines, it follows that the probability scales asymptoti-

ln3 𝑓

length of 2: 𝑝𝑖 to 𝑝𝑘 to 𝑝 𝑗 ) is bounded by O ( 𝑓 4 ).

cally as O = 𝑃 (𝐵 < 𝐴′ ). If we remove 𝑌5 from the Left-Hand Side (LHS) while keeping 𝑋 3 removed from the RHS, proceeding along similar it follows lines, ln 𝑓 𝑓3

Proof. Using the bounds derived in Theorems 5.3, 5.4, the probability of a causal safety violation at process 𝑝 𝑗 as per Theorem 5.2 is:

that the probability scales asymptotically as O 𝑓 2 = 𝑃 (𝐵 ′ < 𝐴′ ). Table 2 compares features of the three computations. □ Theorem 5.4 (𝑃 (𝐷 < 𝐶)). 𝑃 (𝐷 < 𝐶) = O 𝑓14 ln 𝑓

𝑃 (𝐵 < 𝐴) × [1 − (1 − 𝑃 (𝐵 < 𝐴′ )) × (1 − 𝑃 (𝐷 < 𝐶))] ln2 𝑓 ln 𝑓 ln3 𝑓 1 ) × [1 − (1 − O ( )) × (1 − O ( ))] ≤ O ( ) 𝑓2 𝑓3 𝑓4 𝑓5 Since 𝑝𝑘 could be any correct process, by a union bound over the 𝑛 − 𝑓 ∼ 2𝑓 correct processes: ≤ O(

Proof. For the inequality 𝑌 + 𝑌2 + 𝑌3 + 𝑌4 + 𝑌5 < 𝑋 , where 𝑋 is an independent standard exponential random variable, we show

that the probability scales asymptotically as O 𝑓14 . Because 𝑋 is a single standard exponential variable on the larger side of the inequality, this problem can be solved exactly for any 𝑓 without needing Gumbel approximations. Let 𝑉 = 𝑌 +𝑌2 +𝑌3 +𝑌4 +𝑌5 . Because 𝑉 is a sum of strictly positive random variables completely independent of 𝑋 , we can find the probability 𝑃 (𝑋 > 𝑉 ) by conditioning on 𝑉 : 𝑃 (𝑋 > 𝑉 ) = E[𝑃 (𝑋 > 𝑉 | 𝑉 )]. Since 𝑋 ∼ Exp(1), its survival function is exactly 𝑃 (𝑋 > 𝑣) = 𝑒 −𝑣 . Substituting this in gives: 𝑃 (𝑋 > 𝑉 ) = E[𝑒 −𝑉 ] = 𝑀𝑉 (−1) where 𝑀𝑉 (−1) is the Moment Generating Function (MGF) of 𝑉 evaluated at 𝑠 = −1. Because all components of 𝑉 are independent, the MGF of the sum is simply the product of their individual MGFs: 𝑀𝑉 (−1) = 𝑀𝑌 (−1) · 𝑀𝑌2 (−1) · 𝑀𝑌4 (−1) · 𝑀𝑌5 (−1) · 𝑀𝑌3 (−1) (1) MGF of the Standard Exponential (𝑌 ) 1 For 𝑌 ∼ Exp(1), the MGF is 1−𝑠 . Evaluated at 𝑠 = −1: 1 1 𝑀𝑌 (−1) = 1− (−1) = 2 (2) MGF of the Maximum Statistics (𝑌2, 𝑌4, 𝑌5, 𝑌3 ) Using Rényi’s representation, the maximum of 𝐾 independent standard exponential variables has an MGF of Î𝐾 𝑗 𝑗=1 𝑗 −𝑠 . When evaluated at 𝑠 = −1, this telescopes perÎ 𝑗 𝐾 1 fectly: 𝑀max𝐾 (−1) = 𝐾𝑗=1 𝑗+1 = 12 · 23 · 43 · · · 𝐾+1 = 𝐾+1 Applying this clean identity to our specific variables: • For 𝑌2, 𝑌4, 𝑌5 (each a maximum of 𝐾 = 𝑓 + 1 variables): 1 1 𝑀𝑌𝑖 (−1) = ( 𝑓 +1)+1 = 𝑓 +2 • For 𝑌3 (a maximum of 𝐾 = 2𝑓 +1 variables): 𝑀𝑌3 (−1) = 1 1 (2𝑓 +1)+1 = 2𝑓 +2

𝑃 (CO violation) ≤ 2𝑓 · O (

ln3 𝑓 ln3 𝑓 ) ≤ O ( ) 𝑓5 𝑓4 □

5.5

Causal Weak Safety Violation Probability ln3 𝑓 for All Path Lengths (O ( 𝑓 4 ))

We generalize the analysis to causal chains of longer path lengths through non-repeating/unique processes. Theorem 5.6 (Causal Weak Safety Violation for Longer Paths). Under optimal resiliency bounds (𝑛 ≥ 3𝑓 + 1), for all causal chains of path length 𝐿, where (𝑛 − 𝑓 ) > 𝐿 > 2, passing through correct processes, the sum of the probabilities of a causal ordering weak safety violation at any correct process is strictly smaller than ln3 𝑓

that of path length 2, which is O ( 𝑓 4 ), as the system size scales. Proof. Let a causal chain for path B of length 𝐿 ≥ 2 be 𝑚 1 → 𝑚 2 → · · · → 𝑚𝐿 , where the messages are broadcasted sequentially by correct processes. Path A (BCRB-delivery of 𝑚 1 to 𝑝 𝑗 ) is independent of the chain length 𝐿. Path B (BCRB-delivery of 𝑚𝐿 to 𝑝 𝑗 ) scales with 𝐿: 𝐵(𝐿) = 𝑇1(2) + 𝑇2(2) + 𝐿 𝑌1 (𝑚 2, INIT, 1, −) + 𝑇3(2) + 𝑇4(2) + 𝑇5(2) = 𝑌1 + 𝑌2 + 𝐿 (𝑌 + 𝑌3 + 𝑌4 + 𝑌5 ) We first compute 𝑃 (𝐵 < 𝐴) for the asymptotic case. Using the Gumbel approximation (Max𝑀 ≈ ln 𝑀 +𝐺), we map out the growth rates of both sides:

Multiplying these independent expectations together yields: 𝑃 (𝑋 > 3 1 𝑉 ) = 21 · 𝑓 +2 · 2(𝑓1+1) = 4( 𝑓 +1)1( 𝑓 +2) 3 = 𝑃 (𝐷 < 𝐶) □

5.4

Asymptotic Probability 2 ln 𝑓 O 𝑓2 ln 𝑓 O 𝑓3 ln 𝑓 O 𝑓2

• Max of 𝑓 + 1 variables: 𝑌1, 𝑌2, 𝑌4, 𝑌5, 𝑋 1, 𝑋 2 ≈ ln 𝑓 + 𝐺 • Max of 2𝑓 +1 variables: 𝑌3, 𝑋 3 ≈ ln(2𝑓 ) +𝐺 = ln 𝑓 +ln 2+𝐺 • Standard exponential variable: 𝑌 ≈ O (1)

Analytical Evaluation of Causal Weak ln3 𝑓 Safety Violation (O ( 𝑓 4 ))

(1) Right-Hand Side (RHS) Growth: The RHS contains two variables of size 𝑓 + 1 and one variable of size 2𝑓 + 1: RHS ≈ Í3 Í3 ln 𝑓 +ln 𝑓 + (ln 𝑓 +ln 2) + 𝑖=1 𝐺𝑋 ,𝑖 = 3 ln 𝑓 +ln 2+ 𝑖=1 𝐺𝑋 ,𝑖

Theorem 5.5 (Causal Weak Safety Violation Bound). Under optimal resilience bounds (𝑛 ≥ 3𝑓 + 1), the probability of a causal 7

Purv Patel and Ajay D. Kshemkalyani

(2) Left-Hand Side (LHS) Growth: The modified LHS scales 𝑌 , 𝑌3, 𝑌4, 𝑌 5 by the factor 𝐿: LHS ≈ (ln 𝑓 + 𝐺𝑌 ,1 ) + (ln 𝑓 +

To evaluate the overall weak safety violation probability for paths of any length greater than 2, we sum the probabilities for all possible path lengths 𝐿 from 3 to the maximum path length through correct processes, 𝑛 − 𝑓 ∼ 2𝑓 : 2𝑓 ∑︁ 𝐿 2 ln2 𝑓 𝐿 ln 𝑓 𝐿−1 −4 (2𝑓 ) · O ( 3𝐿−1 ) · O ( 3𝐿 ) + O (𝑓 ) 𝑓 𝑓 𝐿=3

𝐺𝑌 ,2 ) +𝐿 O (1) + (ln 𝑓 +ln 2+𝐺𝑌 ,3 ) +ln 𝑓 +ln 𝑓 +𝐺𝑌 ,4 +𝐺𝑌 ,5 Collapsing the logarithmic coefficients yields: LHS ≈ 2 ln 𝑓 + 𝐺𝑌 ,1 + 𝐺𝑌 ,2 + 𝐿 3 ln 𝑓 + ln 2 + 𝐺𝑌 ,3 + 𝐺𝑌 ,4 + 𝐺𝑌 ,5

LHS ≈ (2 + 3𝐿) ln 𝑓 + 𝐿 ln 2 + 𝐺𝑌 ,1 + 𝐺𝑌 ,2 + 𝐿(𝐺𝑌 ,3 + 𝐺𝑌 ,4 + 𝐺𝑌 ,5 ) Í3 We now evaluate 𝑃 (RHS−LHS) > 0: 3 ln 𝑓 + ln 2 + 𝑖=1 𝐺 𝑋 ,𝑖 − (2 + 3𝐿) ln 𝑓 + 𝐿 ln 2 + 𝐺𝑌 ,1 + 𝐺𝑌 ,2 + 𝐿(𝐺𝑌 ,3 + 𝐺𝑌 ,4 + 𝐺𝑌 ,5 ) > 0. Isolating the deterministic growth terms on the right-hand side gives: 3 ∑︁

≤

2𝑓 ∑︁

(2𝑓 ) 𝐿−1 · O (

𝐿 2 ln2 𝑓 ln2 𝑓 −4 ) · O (𝑓 ) ≤ O ( ) 𝑓4 𝑓 3𝐿−1

𝐿=3

This confirms that longer paths lead to strictly lower order violation probabilities than for paths of length 2 (Theorem 5.5). □

𝐺𝑋 ,𝑖 −𝐺𝑌 ,1 −𝐺𝑌 ,2 −𝐿(𝐺𝑌 ,3 +𝐺𝑌 ,4 +𝐺𝑌 ,5 ) > (3𝐿−1) ln 𝑓 +(𝐿−1) ln 2

Corollary 5.7. The probability of weak safety violation (without

𝑖=1

ln3 𝑓

considering deadlock avoidance) over all path lengths ≥ 2 is O ( 𝑓 4 ).

Let 𝑊 represent the combined stochastic terms on the left. The upper-tail probability 𝑃 (𝑊 > (3𝐿−1) ln 𝑓 +(𝐿−1) ln 2) decomposes into: (1)

5.6

The Exponential Decline (𝑓 3𝐿−1 Denominator): Because 𝐿 > 1, the LHS outpaces the RHS. The net deterministic drag moving against the inequality grows at a rate ≈ (3𝐿 −1) ln 𝑓 . Evaluating the exponential tail decay (𝑒 −𝑥 ) at this exact 1 threshold yields: 𝑒 − (3𝐿−1) ln 𝑓 = 𝑓 3𝐿−1

Theorem 5.8 (Probabilistic (Strong) Causal Safety). Let process 𝑝𝑖 broadcast message 𝑚 1 , and (correct or Byzantine) process 𝑝𝑘 broadcast message 𝑚 2 after delivering 𝑚 1 . The probability that any correct process 𝑝 𝑗 delivers 𝑚 2 before 𝑚 1 is

(2) The Polynomial Prefactor (ln2 𝑓 Numerator): The upper tail behavior of𝑊 is entirely governed by the convolution of the 3 positive Gumbel variables on the RHS (𝐺𝑋 ,1, 𝐺𝑋 ,2, 𝐺𝑋 ,3 ). Convolving 𝑘 = 3 independent variables with exponential tails introduces a polynomial prefactor of order 𝑥 𝑘 −1 = 𝑥 2 . Substituting the threshold 𝑥 ≈ (3𝐿 − 1) ln 𝑓 results in: ((3𝐿 − 1) ln 𝑓 ) 2 = O (𝐿 2 ln2 𝑓 )

𝑃 (CO violation at 𝑝 𝑗 ) = 𝑃 (𝐵 < 𝐴) where 𝐴, 𝐵 are defined in the body of the proof of Theorem 5.2. Proof. Follows from the proof of Theorem 5.2. The only difference is that a Byzantine process 𝑝𝑘 may not send ACKs. So 𝐶 = ∞ and 𝑃 (𝐷 < 𝐶) = 1. □

Combining these the corrected, final asymptotic bound: two yields

Theorem 5.9 (Causal Strong Safety Violation Bound). Under optimal resilience bounds (𝑛 ≥ 3𝑓 + 1), the probability of a causal ordering strong safety violation at any correct 𝑝 𝑗 (for a path process

𝐿 2 ln2 𝑓

𝑃 (𝑍 > 0) = O 𝑓 3𝐿−1 = 𝑃 (𝐵 < 𝐴) Path A’ (BRB-delivery of 𝑚 1 to 𝑝 𝑗 ) is independent of the chain length 𝐿. Similar to the derivation of 𝑃 (𝐵 < 𝐴) above, we have: 𝑃 (𝐵 < 𝐴′ ) = O

length of 2: 𝑝𝑖 to 𝑝𝑘 to 𝑝 𝑗 ) is bounded by O

𝐿 ln 𝑓 𝑓 3𝐿

For the 𝑃 (𝐷 < 𝐶) term, the delivery race condition concerns each suffix of the causal chain (𝑚𝐿−𝑥 → 𝑚𝐿 ). Based on the derivation of 𝑃 (𝐷 < 𝐶) of the baseline case of path length 2, we have: 𝑃 (𝐷 < 𝐶) =

Analytical Evaluation of Strong Safety ln2 𝑓 Violation: Algorithm 1, 3 (O ( 𝑓 ))

ln2 𝑓 𝑓

Proof. Follows from the proof of Theorems 5.8 and 5.3. 𝑃 (𝐵 < ln2 𝑓

𝐴) ≤ O ( 𝑓 2 ) for the path 𝑝𝑖 to 𝑝𝑘 to 𝑝 𝑗 but considering all (𝑛−2) ∼ 3𝑓 (= O (𝑓 )) paths of length of 2 from 𝑝𝑖 to 𝑝 𝑗 : 2 2 ln 𝑓 ln 𝑓 ≤ O 𝑃 (𝐵 < 𝐴) ≤ (3𝑓 ) × O 2 𝑓 𝑓

𝐿−1 ∑︁

1 ≤≈ O (𝑓 −4 ) 3 )𝑥 (4(𝑓 + 1)(𝑓 + 2) 𝑥=2

To perform a worst-case analysis considering multiple paths of length 𝐿, we note that there are at most (𝑛 − 𝑓 ) 𝐿−1 ≈ (2𝑓 ) 𝐿−1 causal paths of length 𝐿 for 𝐵. (This assumes 𝑛 = O (𝑓 ) and close to optimal resilience bound 3𝑓 + 1.) By taking a union bound over these paths, the probability that any such path 𝐵(𝐿) delivers before path 𝐴 and violates gating is bounded by:

□ Theorem 5.10 (Causal Strong Safety Violation for Longer Paths). Under optimal resiliency bounds (𝑛 ≥ 3𝑓 + 1), for all causal chains of path length 𝐿, where 𝑛 > 𝐿 > 2, passing through correct or Byzantine processes, the sum of the probabilities of a causal ordering strong safety violation at any correct process is strictly smaller than

𝑃 (CO violation for all paths of length 𝐿)

that of path length 2, which is O (

≤ (2𝑓 ) 𝐿−1 · 𝑃 (𝐵 < 𝐴) · [1 − (1 − 𝑃 (𝐵 < 𝐴′ )) · (1 − 𝑃 (𝐷 < 𝐶))] 𝐿 2 ln2 𝑓 𝐿 ln 𝑓 ≤ (2𝑓 ) 𝐿−1 · O ( 3𝐿−1 ) · 1 − (1 − O ( 3𝐿 )) · (1 − O (𝑓 −4 ) 𝑓 𝑓 2 2 𝐿 ln 𝑓 𝐿 ln 𝑓 ≤ (2𝑓 ) 𝐿−1 · O ( 3𝐿−1 ) · O ( 3𝐿 ) + O (𝑓 −4 ) 𝑓 𝑓

ln2 𝑓 𝑓 ), as the system size scales.

Proof. Follows from the proofs of Theorem 5.8 and similar to the proof of Theorem 5.6. For a path of length 𝐿, assume the worstcase scenario that all processes on the path are Byzantine (and even when 𝐿 > 𝑓 ), and none of them send ACKs. Then 𝑃 (𝐷 < 𝐶) = 1, resulting in the highest probability of CO violation as per 8

Byzantine Causal Reliable Broadcast (BCRB) with Constant-Size Message Metadata

proof of Theorem 5.2 and 𝑃 (𝐵 ′ < 𝐴′ ) = O ( 𝑓 2 ) was computed in Theorem 5.3. Therefore, the probability of weak safety violation considering non-addition of edge (𝑚 2, 𝑚 1 ) at 𝑝 𝑗 is: ln 𝑓

Theorem 5.8 formula. The number of paths of length 𝐿 from 𝑝𝑖 to 𝑝 𝑗 is 𝑛𝐿−1 ∼ (3𝑓 ) 𝐿−1 (assuming 𝑛 = O (𝑓 )). 𝑃 (CO violation for all paths of length 𝐿) ≤ (3𝑓 ) 𝐿−1 · 𝑃 (𝐵 < 𝐴) 𝐿 2 ln2 𝑓 𝐿 2 ln2 𝑓 ) = O ( 𝐿+1 ) 3𝐿−1 𝑓 𝑓 To evaluate the overall strong safety violation probability for paths of all lengths greater than 2, we sum the probabilities for all possible path lengths 𝐿 from 3 to the maximum length of paths through unique processes, 𝑛 ∼ 3𝑓 :

𝑃 (𝑊 𝑆𝑉 𝐷𝐴) = 𝑃 (weak safety violation with deadlock avoidance)

≤ (3𝑓 ) 𝐿−1 · O (

3𝑓 ∑︁

= 𝑃 (𝐵 < 𝐴)·𝑃 (𝐵 ′ < 𝐴′ )+𝑃 (𝑠𝑡𝑚𝑡 . 𝑜 𝑓 𝑇ℎ𝑒𝑜𝑟𝑒𝑚 5.2)·(1−𝑃 (𝐵 ′ < 𝐴′ )) ln2 𝑓 ln 𝑓 ln3 𝑓 ln 𝑓 ln3 𝑓 = O ( 2 ) · O ( 2 ) + O ( 5 ) · (1 − O ( 2 )) = O ( 4 ) 𝑓 𝑓 𝑓 𝑓 𝑓 As 𝑝𝑘 in our scenario could be any of 𝑛 − 𝑓 ≃ 2𝑓 correct processes, using union-bound over 𝑓 processes:

𝐿 2 ln2 𝑓 ln2 𝑓 ) ≤ O ( ) 𝑓2 𝑓 𝐿+1

ln3 𝑓 ln3 𝑓 ) = O( 3 ) 4 𝑓 𝑓 Thus the probability of weak safety violation when considering 𝑃 (WSVDA) = 2𝑓 · O (

𝐿=3 ln2 𝑓

The sum is certainly O ( 𝑓 ), which is the probability of violation for path length 2 (Theorem 5.9), confirming that longer paths lead to strictly lower order violation probabilities. □

ln3 𝑓

5.7

ln2 𝑓 𝑓 ).

5.8

ln2 𝑓 𝑓 ).

Validity, Agreement, and Integrity

Theorem 5.13. If a correct process 𝑝𝑖 adds edge ((𝑧, 𝑛𝑒𝑥𝑡_𝑠𝑛), (𝑀 ′ = (𝑥, 𝑠𝑥 ))) in 𝐺, then 𝑀 ′ has been BRB-broadcast by 𝑝𝑥 before broadcast of 𝐴𝐶𝐾 (𝑀 ′, 𝑛𝑒𝑥𝑡_𝑠𝑛, 𝑠ℎ𝑎𝑟𝑒, 𝑧, ℎ) by 𝑝𝑧 .

Impact of Deadlock Avoidance on Weak ln3 𝑓 Safety Violation (𝑃 = O ( 𝑓 3 ))

Theorem 5.12. [Causal Weak Safety Violation Bound Considering Deadlock Avoidance] Under optimal resilience bounds (𝑛 ≥ 3𝑓 +1), the probability of a causal ordering weak safety violation at any correct process 𝑝 𝑗 , considering impact of deadlock avoidance, is bounded by: 𝑃 (CO violation at some correct process) ≤ O (

□

The probability of strong safety violation even considering deadlock avoidance remains unaffected at O (

Corollary 5.11. The probability of strong safety violation over all path lengths ≥ 2 is O (

ln3 𝑓

deadlock avoidance increases from O ( 𝑓 4 ) to O ( 𝑓 3 ).

Proof. If 𝑝𝑧 is a correct process, the theorem follows from the Algorithm pseudo-code. So consider that 𝑝𝑧 is Byzantine. In receive ACK processing, the hash of 𝑀 ′ .𝑐𝑖𝑝ℎ𝑒𝑟𝑡𝑒𝑥𝑡 sent on ACK as parameter ℎ must match the hash 𝑀 ′ .𝑐𝑖𝑝ℎ𝑒𝑟𝑡𝑒𝑥𝑡 as computed by 𝑝𝑖 on BRB-delivery of 𝑀 ′ . This ensures 𝑀 ′ was BRBbroadcast before broadcast of 𝐴𝐶𝐾 (𝑀 ′ ) in order for 𝑝𝑧 to compute and piggyback the correct hash of 𝑀 ′ on 𝐴𝐶𝐾 (𝑚 ′ ). □

ln3 𝑓 ) 𝑓3

Proof. A deadlock cycle may arise if there is (at least) one ByzanTheorem 5.14 (BCRB Delivery). If a message 𝑚 1 = ((𝑏 1, 𝑠 1 ), payload) tine process 𝑝𝑏 that sends 𝐴𝐶𝐾 (𝑚 = (𝑙, 𝑠), 𝑛𝑒𝑥𝑡_𝑠𝑛, . . .) where it has from process 𝑏 1 (whether 𝑏 1 is a Byzantine or correct process) is in′ ′ already BCRB-broadcast (𝑚𝑏 = (𝑏, 𝑛𝑒𝑥𝑡_𝑠𝑛 ), 𝑝𝑙) and 𝑛𝑒𝑥𝑡_𝑠𝑛 ≥ serted into the local pending set of any correct process 𝑝𝑖 then 𝑚 1 𝑛𝑒𝑥𝑡_𝑠𝑛, and there is a (possibly transitive) causal dependency of will eventually be BCRB-delivered by every correct process. 𝑚 on 𝑚𝑏 (i.e., there is a path from 𝑚 to 𝑚𝑏 in 𝐺) because 𝑚𝑏 is BRBdelivered and processed at 𝑝𝑙 before 𝑝𝑙 BCRB-broadcast 𝑚. Thus Proof. If message 𝑚 1 = ((𝑏 1, 𝑠 1 ), 𝑐𝑖𝑝ℎ𝑒𝑟𝑡𝑒𝑥𝑡) is inserted into there is a path in 𝐺 from 𝑚𝑏 to 𝑚 (due to edge or path (𝑚𝑏 , 𝑚)) and pending at any correct process 𝑝𝑖 (implying 𝑚 1 was BRB-delivered from 𝑚 to 𝑚𝑏 , thereby completing a cycle. at 𝑝𝑖 ), then all 𝑚 1′ = (𝑏 1, 𝑠 1′ )|𝑠 1′ ≤ 𝑠 1 , are also BRB-delivered locally For a true dependency edge ((𝑧, 𝑠𝑧 ), (𝑦, 𝑠 𝑦 )) to form, the physical and inserted in 𝑝𝑒𝑛𝑑𝑖𝑛𝑔. By the Agreement property of BRB layer, time of BRB-broadcast((𝑧, 𝑠𝑧 )) > physical time of BRB-broadcast((𝑦, 𝑠 𝑦 )). 𝑚 1 and all 𝑚 1′ are also eventually BRB-delivered at every correct However, a third observer process 𝑝 𝑗 may observe these two broadprocess 𝑝𝑘 and added to 𝑝𝑘 ’s local pending set. casts in any order based on the completion times of the BRBUpon BRB delivery of 𝑚 1 , every correct process 𝑝𝑘 broadcasts deliveries at 𝑝 𝑗 , and this can lead to observing a cycle. Algorithm 1 an 𝐴𝐶𝐾 (𝑚 1, 𝑛𝑒𝑥𝑡_𝑠𝑛, 𝑠ℎ𝑎𝑟𝑒, 𝑘, ℎ). As there are at least 𝑛 − 𝑓 correct uses deadlock avoidance: it assigns local physical clock timesprocesses, every correct process 𝑝𝑘 eventually receives at least 𝑛 − 𝑓 tamps (.𝑡𝑠) to nodes in 𝐺 at the time they are locally formed (BRBACKs/shares for 𝑚 1 (and 𝑚 1′ ), satisfying 𝑞𝑢𝑜𝑟𝑢𝑚_𝑜𝑘. delivery processed); an edge ((𝑧, 𝑠𝑧 ), (𝑦, 𝑠 𝑦 )) is not added to 𝐺 if As 𝐺 is acyclic (and hence a DAG), all paths from 𝑚 1 lead to (𝑧, 𝑠𝑧 ).𝑡𝑠 < (𝑦, 𝑠 𝑦 ).𝑡𝑠. This guarantees that 𝐺 is always a DAG. leaf nodes 𝑚 = (𝑏, 𝑠𝑏 ) at any point in time. 𝑚 satisfies 𝑓 𝑖 𝑓 𝑜_𝑜𝑘 To analyze the impact of the non-addition of a correct edge on because all lower seq numbered messages (from 𝑏) have been BCRBthe probability of weak safety violation in a worst-case scenario, it delivered and removed from 𝐺. Within bounded time 𝑚 will satisfy is sufficient to analyze the following scenario, also considered in 𝑞𝑢𝑜𝑟𝑢𝑚_𝑜𝑘 by the reasoning in the above para. Thus it will be the setting of Theorem 5.2. Let correct process 𝑝𝑖 BCRB-broadcast BCRB-delivered and 𝑚 and its incoming edges deleted from 𝐺 message 𝑚 1 , and correct process 𝑝𝑘 BCRB-broadcast message 𝑚 2 leading to shorter paths to new leaf nodes. However if 𝑞𝑢𝑜𝑟𝑢𝑚_𝑜𝑘 after BCRB-delivering 𝑚 1 . The true dependency edge (𝑚 2, 𝑚 1 ) is not is not satisfied at this point in time, an outgoing edge (𝑚, 𝑚 ′ ) may be added to 𝐺 at correct observer 𝑝 𝑗 if 𝑚 2 .𝑡𝑠 < 𝑚 1 .𝑡𝑠. The probability added on receipt of ACK(𝑚 ′, 𝑠𝑏 , 𝑠ℎ𝑎𝑟𝑒, 𝑏, ℎ), provided the earlier sent of this happening is 𝑃 (𝐵 ′ < 𝐴′ ), where 𝐵 ′, 𝐴′ were defined in the 𝑚 ′ than 𝑚 (by Theorem 5.13) is BRB-delivered and processed but 9

Purv Patel and Ajay D. Kshemkalyani

not yet BCRB-delivered. This leads to a new leaf node that satisfies 𝑓 𝑖 𝑓 𝑜_𝑜𝑘 and guaranteed to satisfy 𝑞𝑢𝑜𝑟𝑢𝑚_𝑜𝑘. Such extensions to the path(s) from 𝑚 are bounded by the size of the history, which contains a bounded number of messages. Eventually the paths from 𝑚 must shrink and 𝑚 will be BCRB-delivered and along with its incoming edges removed from 𝐺. The same logic shows that the new sink nodes reachable via shorter paths from 𝑚 1 will be BCRB-delivered and the paths from 𝑚 1 will inductively keep shrinking until 𝑚 1 gets BCRB-delivered. □

violation remains the same, running a BRB instance for every ACK increases the number of messages sent to O (𝑛 3 ). Thus the communication word complexity is O (𝑛 3 ); the application payload still gets sent only on O (𝑛 2 ) messages. Explanation is in Appendix A. Correctness proof is in Appendix B.

Theorem 5.15. Algorithms 1, 2 satisfy Validity, Agreement, and Integrity at the BCRB layer. Proof. Follows from Theorem 5.14 and the properties of the underlying BRB layer: • Validity: If a correct process 𝑝𝑖 BCRB-broadcasts 𝑚, by Validity of the underlying BRB layer, 𝑚 is BRB-delivered to each correct process. It will be inserted into pending at all correct processes as 𝑝𝑖 must have BCRB-broadcast all messages with lower sequence numbers in order, which will also be BRB-delivered in order and placed in their pending at all correct processes. By Theorem 5.14, 𝑚 is eventually BCRB-delivered by every correct process. • Agreement: If a correct process 𝑝𝑖 BCRB-delivers 𝑚, 𝑚 was BRB-delivered and placed in pending at 𝑝𝑖 . By Theorem 5.14, 𝑚 is eventually BCRB-delivered by every correct process. • Integrity: At-most-once delivery is guaranteed because V𝑘 [ 𝑗] strictly increments upon delivery, causing 𝑓 𝑖 𝑓 𝑜_𝑜𝑘 to evaluate to False for any duplicate processing. Authenticity for correct senders follows from the Integrity property of the underlying BRB layer: since correct processes only send messages via bcrb_broadcast, and the underlying BRB layer guarantees sender authenticity, a Byzantine process directly invoking brb_broadcast (bypassing the BCRB layer) cannot forge messages from a correct sender.

References [1] Alex Auvolat, Davide Frey, Michel Raynal, and François Taïani. 2021. Byzantinetolerant causal broadcast. Theor. Comput. Sci. 885 (2021), 55–68. doi:10.1016/J. TCS.2021.06.021 [2] Gabriel Bracha. 1987. Asynchronous Byzantine Agreement Protocols. Inf. Comput. 75, 2 (1987), 130–143. doi:10.1016/0890-5401(87)90054-X [3] Gabriel Bracha and Sam Toueg. 1985. Asynchronous Consensus and Broadcast Protocols. J. ACM 32, 4 (1985), 824–840. doi:10.1145/4221.214134 [4] Christian Cachin, Klaus Kursawe, Frank Petzold, and Victor Shoup. 2001. Secure and Efficient Asynchronous Broadcast Protocols. In Advances in Cryptology — CRYPTO 2001, Joe Kilian (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 524–541. [5] Damien Imbs and Michel Raynal. 2016. Trading off t-Resilience for Efficiency in Asynchronous Byzantine Reliable Broadcast. Parallel Process. Lett. 26, 4 (2016), 1650017:1–1650017:8. doi:10.1142/S0129626416500171 [6] Leslie Lamport. 1978. Time, clocks, and the ordering of events in a distributed system. Commun. ACM 21, 7 (1978), 558–565. [7] Anshuman Misra and Ajay D. Kshemkalyani. 2022. Causal Ordering Properties of Byzantine Reliable Broadcast Primitives. In 2022 IEEE 21st International Symposium on Network Computing and Applications (NCA). 115–122. doi:10.1109/NCA55306.2022.9936749 [8] Anshuman Misra and Ajay D. Kshemkalyani. 2022. Detecting Causality in the Presence of Byzantine Processes: There is No Holy Grail. In 2022 IEEE 21st International Symposium on Network Computing and Applications (NCA). 73–80. doi:10.1109/NCA57778.2022.10013644 [9] Anshuman Misra and Ajay D. Kshemkalyani. 2022. Solvability of Byzantine FaultTolerant Causal Ordering Problems. In Networked Systems - 10th International Conference, NETYS 2022, Virtual Event, May 17-19, 2022, Proceedings (Lecture Notes in Computer Science, Vol. 13464), Mohammed-Amine Koulali and Mira Mezini (Eds.). Springer, 87–103. doi:10.1007/978-3-031-17436-0_7 [10] Anshuman Misra and Ajay D. Kshemkalyani. 2023. Byzantine Fault-Tolerant Causal Ordering. In 24th International Conference on Distributed Computing and Networking, ICDCN 2023, Kharagpur, India, January 4-7, 2023. ACM, 100–109. doi:10.1145/3571306.3571395 [11] Anshuman Misra and Ajay D. Kshemkalyani. 2024. Byzantine-Tolerant Causal Ordering for Unicasts, Multicasts, and Broadcasts. IEEE Trans. Parallel Distributed Syst. 35, 5 (2024), 814–828. doi:10.1109/TPDS.2024.3368280 [12] Anshuman Misra and Ajay D. Kshemkalyani. 2025. Byzantine-tolerant detection of causality: There is no holy grail. Parallel Comput. 124 (2025), 103136. doi:10. 1016/J.PARCO.2025.103136 [13] Laine Rumreich and Paolo A. G. Sivilotti. 2025. Using Minicasts for Efficient Asynchronous Causal Unicast and Byzantine Tolerance. In Parallel and Distributed Processing Techniques, Hamid R. Arabnia, Masami Takata, Leonidas Deligiannidis, Pablo Rivas, Masahito Ohue, and Nobuaki Yasuo (Eds.). Springer Nature Switzerland, Cham, 65–81. [14] Victor Shoup. 2000. Practical threshold signatures. In Advances in Cryptology—EUROCRYPT 2000: International Conference on the Theory and Application

□ A Byzantine sender can broadcast conflicting messages with arbitrary sequence numbers or omit sending ACKs selectively. This can at worst result in the Byzantine sender’s own message stream being blocked or halted permanently at correct processes. The impact on safety was already accounted for in violation bounds.

Conclusions

We proposed the first O (1) metadata overhead BCRB algorithm with O (𝑛 2 ) communication word complexity. We also proved bounds on the probabilities of violation of strong safety and of weak safety. Such bounds for our low-cost solutions are particularly attractive for non-critical applications like social networks. Our algorithms and associated safety violation bounds (even for Algorithms 3, 4 which are O (𝑛 3 ) algorithm variants) represent a good trade-off against more expensive O (𝑛 3 ) communication word complexity algorithms [1, 4]. Additionally, Cachin et al. [4] uses randomized consensus and is not throughput-scalable whereas Auvolat et al. [1] has a high probability of strong safety violations (not analyzed by them) because of not just front-running attacks but also other attacks like arbitrarily erasing/manipulating causal barriers.

Weak Safety Guarantee via BRB-Gated ACKs

Algorithms 3, 4 are like Algorithms 1, 2, resp.. Difference is that rather than sending ACKs point-to-point, they are sent via BRB. Specifically, before a correct 𝑝𝑘 BCRB-broadcasts a subsequent application message 𝑚 2 (and hence BRB-broadcast it), 𝑝𝑘 initiates the BRB of the 𝐴𝐶𝐾 (𝑚 1 ) for the predecessor message 𝑚 1 that has been BRB-delivered and that processing completed. On BRB-delivery of the ACK, it is subject to 𝑓 𝑖 𝑓 𝑜_𝑜𝑘 check. This 𝑓 𝑖 𝑓 𝑜_𝑜𝑘 check ensures that BRBs (of ACK(𝑚 1 ) and of 𝑚 2 ) from 𝑝𝑘 are processed in FIFO order (globally) and 𝑚 2 is BCRB-delivered after BRB-delivered ACK(𝑚 1 ) is processed and the dependency of 𝑚 2 on 𝑚 1 is registered. This guarantees 100% weak safety. While the message overhead remains constant-size O (1) and the probability of strong safety 10

Byzantine Causal Reliable Broadcast (BCRB) with Constant-Size Message Metadata

Algorithm 3: Byzantine Causal Reliable Broadcast (BCRB) with BRB of ACKs (Process 𝑖) state variables: 𝑙𝑜𝑐𝑎𝑙_𝑠𝑛 ← 0 ; // Seq. num. for process 𝑖 ’s broadcasts 3 V𝑖 ← [0, . . . , 0] ; // Vec. of BCRB-delivered seq. nos. 4 𝑝𝑒𝑛𝑑𝑖𝑛𝑔 ← ∅ ; // processed BRB-delivery, pending BCRB delivery 5 𝑠ℎ𝑎𝑟𝑒𝑠 ← Array of ∅ ; // Maps msg ID to decryption shares 6 𝐺 = (𝑁 , 𝐸 ) ← ( ∅, ∅ ) ; // graph of dependencies between msg IDs

upon brb_deliver(j, sn, payload): wait until all 𝑀 = ( 𝑗, 𝑠 ), 𝑠 < 𝑠𝑛 are brb-delivered and execution of brb-deliver is completed; 31 if payload is ACK[(𝑀 ← (𝑘, 𝑠𝑛𝑘 ) ), 𝑠ℎ𝑎𝑟𝑒, ℎ] then 32 wait until all 𝑀 ′ = (𝑘, 𝑠 ′ ), 𝑠 ′ ≤ 𝑠𝑛𝑘 are brb-delivered and execution of brb-deliver is completed; 33 if 𝑀 ∈ 𝑁 ∧ ℎ = ℎ𝑎𝑠ℎ (𝑀 .𝑐𝑖𝑝ℎ𝑒𝑟𝑡𝑒𝑥𝑡 ) then 34 𝑠ℎ𝑎𝑟𝑒𝑠 [𝑀 ] ← 𝑠ℎ𝑎𝑟𝑒𝑠 [𝑀 ] ∪ {𝑠ℎ𝑎𝑟𝑒 }; 35 𝐸 ← 𝐸 ∪ { ( ( 𝑗, 𝑠𝑛 + 1) 𝑡𝑒𝑚𝑝 , (𝑘, 𝑠𝑛𝑘 ) ) };

procedure bcrb_broadcast(payload): 𝑙𝑜𝑐𝑎𝑙_𝑠𝑛 ← 𝑙𝑜𝑐𝑎𝑙_𝑠𝑛 + 1; 9 𝑐𝑖𝑝ℎ𝑒𝑟𝑡𝑒𝑥𝑡 ← encrypt(𝑝𝑎𝑦𝑙𝑜𝑎𝑑, PK ); 10 brb_broadcast((𝑖, 𝑙𝑜𝑐𝑎𝑙_𝑠𝑛, 𝑐𝑖𝑝ℎ𝑒𝑟𝑡𝑒𝑥𝑡 ));

procedure check_delivery(): 𝑝𝑟𝑜𝑔𝑟𝑒𝑠𝑠 ← True; 13 while 𝑝𝑟𝑜𝑔𝑟𝑒𝑠𝑠 = True do 14 𝑝𝑟𝑜𝑔𝑟𝑒𝑠𝑠 ← False; 15 foreach 𝑚 = (𝑀 = ( 𝑗, 𝑠𝑛), 𝑝𝑎𝑦𝑙𝑜𝑎𝑑 ) ∈ 𝑝𝑒𝑛𝑑𝑖𝑛𝑔 do 16 𝑓 𝑖 𝑓 𝑜_𝑜𝑘 ← (V𝑖 [ 𝑗 ] = 𝑠𝑛 − 1); 17 𝑞𝑢𝑜𝑟𝑢𝑚_𝑜𝑘 ← True; 18 if 𝑝𝑎𝑦𝑙𝑜𝑎𝑑 is not ACK then 19 𝑞𝑢𝑜𝑟𝑢𝑚_𝑜𝑘 ← ( |𝑠ℎ𝑎𝑟𝑒𝑠 [𝑀 ] | ≥ 𝑛 − 𝑓 );

20 21 22 23 24 25 26 27 28

39 40 41 42 43 44 45

if 𝑓 𝑖 𝑓 𝑜_𝑜𝑘 ∧ 𝑞𝑢𝑜𝑟𝑢𝑚_𝑜𝑘 ∧ ( 𝑗, 𝑠𝑛) has no outgoing edge in 𝐸 then 𝑝𝑒𝑛𝑑𝑖𝑛𝑔 ← 𝑝𝑒𝑛𝑑𝑖𝑛𝑔 \ {𝑚}; delete 𝑀 from 𝑁 and all incident edges in 𝐸; V𝑖 [ 𝑗 ] ← 𝑠𝑛; if payload is not an ACK then 𝑝𝑙𝑎𝑖𝑛𝑡𝑒𝑥𝑡 ← decrypt(𝑝𝑎𝑦𝑙𝑜𝑎𝑑, 𝑠ℎ𝑎𝑟𝑒𝑠 [𝑀 ], PK ); bcrb_deliver( 𝑗, 𝑠𝑛, 𝑝𝑙𝑎𝑖𝑛𝑡𝑒𝑥𝑡 );

46 47 48

else add ( 𝑗, 𝑠𝑛) to 𝑁 ; if ( 𝑗, 𝑠𝑛 − 1) ∈ 𝑁 then add edge ( ( 𝑗, 𝑠𝑛), ( 𝑗, 𝑠𝑛 − 1) ) to 𝐸; 𝑝𝑒𝑛𝑑𝑖𝑛𝑔 ← 𝑝𝑒𝑛𝑑𝑖𝑛𝑔 ∪ { ( ( 𝑗, 𝑠𝑛), 𝑝𝑎𝑦𝑙𝑜𝑎𝑑 ) }; check_delivery();

than sent point-to-point. A process waits until all preceding messages 𝑀 = ( 𝑗, 𝑠) for 𝑠 < 𝑠𝑛 from process 𝑗 are BRB-delivered to preserve FIFO order. • Case 1: The payload is an ACK [(𝑀 = (𝑘, 𝑠𝑛𝑘 )), 𝑠ℎ𝑎𝑟𝑒, ℎ]: The process waits until the target message 𝑀 and all its predecessor messages 𝑀 ′ = (𝑘, 𝑠 ′ ) where 𝑠 ′ ≤ 𝑠𝑛𝑘 are BRBdelivered. It then verifies that 𝑀 is registered in the node set 𝑁 and the hash matches (ℎ = hash(𝑀.𝑐𝑖𝑝ℎ𝑒𝑟𝑡𝑒𝑥𝑡)). If valid, it records the decryption share in shares[𝑀] and registers a dependency by adding the edge (( 𝑗, 𝑠𝑛 + 1)𝑡𝑒𝑚𝑝 , (𝑘, 𝑠𝑛𝑘 )) to the dependency graph’s edge set 𝐸. • Case 2: The payload is an application message (not an ACK): The process increments 𝑙𝑜𝑐𝑎𝑙_𝑠𝑛, computes its cryptographic decryption share of the ciphertext using its secret key share SK 𝑖 , computes the payload hash ℎ ← hash(𝑝𝑎𝑦𝑙𝑜𝑎𝑑), and broadcasts its ACK via the BRB layer: brb_broadcast(𝑖, 𝑙𝑜𝑐𝑎𝑙_𝑠𝑛, 𝐴𝐶𝐾 [( 𝑗, 𝑠𝑛), 𝑠ℎ𝑎𝑟𝑒, ℎ]). After handling either case, the process checks if a temporary node ( 𝑗, 𝑠𝑛)𝑡𝑒𝑚𝑝 exists. If so, it relabels it as the concrete node ( 𝑗, 𝑠𝑛); otherwise, it adds ( 𝑗, 𝑠𝑛) to the node set 𝑁 . To enforce FIFO order, if ( 𝑗, 𝑠𝑛 − 1) is in 𝑁 , it adds the edge (( 𝑗, 𝑠𝑛), ( 𝑗, 𝑠𝑛 − 1))

Same as Algorithm 3 except: (1) ciphertext is identical to plaintext, i.e., encryption/decryption are idempotent operations, and (2) decryption share is set to the sender process ID.

of Cryptographic Techniques, Bruges, Belgium, May 14-18, 2000. Proceedings 19. Springer, 207–220.

if ( 𝑗, 𝑠𝑛) 𝑡𝑒𝑚𝑝 exists then relabel it as ( 𝑗, 𝑠𝑛);

𝑝𝑟𝑜𝑔𝑟𝑒𝑠𝑠 ← True; break;

Algorithm 4: Non-Cryptographic Byzantine Causal Reliable Broadcast (BCRB) with BRB of ACKs 1

else 𝑙𝑜𝑐𝑎𝑙_𝑠𝑛 ← 𝑙𝑜𝑐𝑎𝑙_𝑠𝑛 + 1; 𝑠ℎ𝑎𝑟𝑒 ← dec_share(𝑝𝑎𝑦𝑙𝑜𝑎𝑑, SK 𝑖 ); ℎ ← ℎ𝑎𝑠ℎ (𝑝𝑎𝑦𝑙𝑜𝑎𝑑 ); brb_broadcast(i, local_sn, ACK[(j,sn), share, h]);

Explanation of Algorithm 3: Cryptographic Version with BRB of ACKs

Purv Patel and Ajay D. Kshemkalyani

to 𝐸. Finally, it buffers the message in the pending set and calls check_delivery().

reports on target messages and subsequent messages broadcast by it may never complete processing of BRB-delivery and hence not qualify to be inserted in pending and in 𝐺 at correct processes. In fact, multiple incomplete BRB-delivery instances may have cyclic dependencies (all having been been created by Byzantine processes) but these messages or their dependencies will not enter 𝐺. Because all dependencies target messages that were already BRBdelivered (and that processing completed) prior to the generation of the corresponding ACK, the dependency relation is a strict partial order based on the real-time sequence of completion of processing of BRB-deliveries. Thus, no circular dependencies can form, and 𝐺 is guaranteed to be acyclic. □

check_delivery(). This procedure evaluates the pending set. A pending message 𝑚 = (𝑀 = ( 𝑗, 𝑠𝑛), 𝑝𝑎𝑦𝑙𝑜𝑎𝑑) is processed as follows. If: (1) FIFO order is satisfied locally for the sender 𝑗 (V𝑖 [ 𝑗] = sn − 1). (2) If the payload is not an ACK, it has gathered at least 𝑛 − 𝑓 valid decryption shares (|shares[𝑀]| ≥ 𝑛 − 𝑓 ). (3) The node ( 𝑗, 𝑠𝑛) has no outgoing edge in 𝐸 (i.e., there are no active causal dependencies blocking its delivery). are satisfied, the process removes 𝑚 from the pending set, deletes node ( 𝑗, 𝑠𝑛) and all its incident edges from 𝐺, and updates V𝑖 [ 𝑗] ← 𝑠𝑛. And if the payload is an application message (not an ACK), the process decrypts the ciphertext using the shares, and triggers bcrb_deliver on the plaintext. Then the process loops to check if further pending messages can now be processed.

B.2

Proof. Weak Causal Safety equivalently states that if 𝑚 1 →𝑏𝑟𝑏 𝑚 2 and the causal chain from 𝑚 1 to 𝑚 2 passes exclusively through correct processes, then no correct process triggers bcrb_deliver(𝑚 2 ) before bcrb_deliver(𝑚 1 ). Suppose there is a causal chain of messages from 𝑚 1 to 𝑚 2 broadcast via the underlying BRB layer and passing exclusively through correct processes:

Correctness Proof of Algorithm 3, 4

We prove that Algorithm 3 satisfies deadlock-freedom, 100% Weak Safety, and Validity, Agreement, and Integrity in Byzantine environments.

B.1

100% Weak Safety Guarantee

Theorem B.2. Algorithm 3 guarantees 100% Weak Causal Safety.

𝑚 1 = 𝑚 (0) →𝑏𝑟𝑏 𝑚 (1) →𝑏𝑟𝑏 · · · →𝑏𝑟𝑏 𝑚 (𝑞) = 𝑚 2

Deadlock Freedom (Acyclicity of 𝐺)

where each message 𝑚 (𝑟 ) (for 0 ≤ 𝑟 ≤ 𝑞) is broadcast by a correct process 𝑝 (𝑟 ) . Since each process 𝑝 (𝑟 ) (1 ≤ 𝑟 ≤ 𝑞) in the causal chain is correct, it obeys the protocol and only initiates the BRB of 𝑚 (𝑟 ) after it has BRB-delivered 𝑚 (𝑟 −1) and completed its processing, which includes broadcasting 𝐴𝐶𝐾 (𝑚 (𝑟 −1) ) via the BRB layer. Let 𝑠𝑛𝑟 be the sequence number of the BRB broadcast of 𝑚 (𝑟 ) by 𝑝 (𝑟 ) , so the ACK for 𝑚 (𝑟 −1) is sent by 𝑝 (𝑟 ) with sequence number 𝑠𝑛𝑟 − 1. By the Agreement property of the underlying BRB layer, and the FIFO processing property guaranteed by the wait step of BRB-delivery processing, every correct process 𝑝𝑖 is guaranteed to BRB-deliver the 𝐴𝐶𝐾 (𝑚 (𝑟 −1) ) from 𝑝 (𝑟 ) before it BRB-delivers 𝑚 (𝑟 ) from 𝑝 (𝑟 ) . Upon BRB-delivering 𝐴𝐶𝐾 (𝑚 (𝑟 −1) ), 𝑝𝑖 registers the dependency edge ((𝑝 (𝑟 ) , 𝑠𝑛𝑟 )𝑡𝑒𝑚𝑝 , 𝑚 (𝑟 −1) ), which is relabeled to ((𝑝 (𝑟 ) , 𝑠𝑛𝑟 ), 𝑚 (𝑟 −1) ) in 𝐸 when 𝑚 (𝑟 ) is BRB-delivered. This establishes a directed dependency path in the graph 𝐺 from the node of 𝑚 2 to the node of 𝑚 1 :

Theorem B.1. The dependency graph 𝐺 = (𝑁 , 𝐸) constructed by any correct process in Algorithm 3 is always a directed acyclic graph (DAG). Proof. By construction, edges in 𝐸 are added in two cases: (1) FIFO Edges: Edges of the form (( 𝑗, 𝑠𝑛), ( 𝑗, 𝑠𝑛−1)) are added between successive messages of the same sender 𝑗. Since sequence numbers strictly increase, these local edges are naturally acyclic. (2) Causal Dependency Edges: Edges of the form (( 𝑗, 𝑠𝑛 + 1), (𝑘, 𝑠𝑛𝑘 )) are added when process 𝑝𝑖 BRB-delivers an ACK from process 𝑗 sent as 𝑗’s message sequence number 𝑠𝑛, and that processing completed. Suppose a cycle exists in 𝐺, which requires a circular dependency chain 𝑀1 → 𝑀2 → · · · → 𝑀𝑚 → 𝑀1 . For a causal dependency edge (( 𝑗, 𝑠𝑛 + 1), (𝑘, 𝑠𝑛𝑘 )) to be added: • If process 𝑗 is correct, it only broadcasts 𝐴𝐶𝐾 (𝑀) after 𝑀 has been BRB-delivered locally and that processing completed. Thus, the physical broadcast of 𝑀 must have occurred in real-time before the broadcast of 𝐴𝐶𝐾 (𝑀). • If process 𝑗 is Byzantine, it cannot construct a valid ACK for a future message 𝑀 because the correct process checking the ACK enforces ℎ = hash(𝑀.𝑐𝑖𝑝ℎ𝑒𝑟𝑡𝑒𝑥𝑡). Since future ciphertexts are generated using a randomized threshold encryption scheme, they are unpredictable, preventing the Byzantine process from computing the correct hash ℎ beforehand. • The wait steps of BRB-delivery processing guarantee FIFO processing order, defined on the sender-assigned sequence number, of all broadcasts from the same sender. If a Byzantine process does not follow these rules, the dependencies it

𝑚 2 → 𝑚 (𝑞−1) → · · · → 𝑚 1 In Algorithm 3, a message 𝑚 2 can only be delivered to the application if it has no outgoing edges in 𝐸. Since 𝐺 is acyclic (Theorem B.1) and no dependency edges are ever deleted to resolve cycles, the path from 𝑚 2 to 𝑚 1 remains intact in 𝐺 as long as 𝑚 1 is undelivered. Thus, 𝑚 2 has at least one outgoing edge and cannot satisfy the delivery condition. Consequently, no correct process can BCRB-deliver 𝑚 2 before delivering 𝑚 1 , satisfying the definition of Weak Causal Safety. □

B.3

Validity, Agreement, and Integrity

Theorem B.3. If a correct process 𝑝𝑖 adds dependency edge (( 𝑗, 𝑠𝑛 + 1)𝑡𝑒𝑚𝑝 , (𝑘, 𝑠𝑛𝑘 )) (re-labeled as (( 𝑗, 𝑠𝑛 + 1), (𝑘, 𝑠𝑛𝑘 ))) in 𝐺, then the target message 𝑀 = (𝑘, 𝑠𝑛𝑘 ) must have been broadcast via brb_broadcast by 𝑝𝑘 before the brb-broadcast of the ACK [𝑀, 𝑠ℎ𝑎𝑟𝑒, ℎ] by 𝑝 𝑗 . 12

Byzantine Causal Reliable Broadcast (BCRB) with Constant-Size Message Metadata

• Validity: If a correct process 𝑝𝑖 BCRB-broadcasts 𝑚, by Validity of the underlying BRB layer, 𝑚 is BRB-delivered to each correct process. It will be inserted into pending at all correct processes as 𝑝𝑖 must have BCRB-broadcast all messages with lower sequence numbers in order, which will also be BRB-delivered in order and placed in their pending at all correct processes. By Theorem B.4, 𝑚 is eventually BCRB-delivered by every correct process. • Agreement: If a correct process 𝑝𝑖 BCRB-delivers 𝑚, 𝑚 was BRB-delivered and placed in pending at 𝑝𝑖 . By Theorem B.4, 𝑚 is eventually BCRB-delivered by every correct process. • Integrity: Integrity consists of two properties: (1) at-mostonce delivery, and (2) authenticity (a correct process only delivers a message from a correct sender if that sender actually broadcast it). For at-most-once delivery: Upon satisfying the delivery checks in check_delivery(), process 𝑝𝑘 removes the message from its pending set, updates its local sequence vector V𝑘 [ 𝑗] ← 𝑠𝑛, and triggers bcrb_deliver. Since V𝑘 [ 𝑗] is strictly incremented to 𝑠𝑛, the FIFO check 𝑓 𝑖 𝑓 𝑜_𝑜𝑘 (V𝑘 [ 𝑗] = 𝑠𝑛 − 1) will evaluate to False for any duplicate sequence number, preventing duplicate deliveries. For authenticity: If the sender 𝑝 𝑗 is correct, it obeys the protocol and only sends messages via bcrb_broadcast. By the Integrity property of the underlying BRB layer, no correct process can BRB-deliver a message (( 𝑗, 𝑠𝑛), 𝑐𝑖𝑝ℎ𝑒𝑟𝑡𝑒𝑥𝑡) unless 𝑝 𝑗 actually invoked brb_broadcast. Even if a Byzantine process attempts to directly invoke the lower-level brb_broadcast to bypass the BCRB layer, it cannot forge messages from the correct process 𝑝 𝑗 because the underlying BRB layer guarantees sender authenticity (e.g., using signatures or authenticated point-to-point channels). Therefore, no correct process ever BCRB-delivers a forged message from a correct sender. □

Proof. If 𝑝 𝑗 is a correct process, the theorem follows directly from the algorithm pseudo-code. If 𝑝 𝑗 is Byzantine, the condition checking hash ℎ = hash(𝑀.𝑐𝑖𝑝ℎ𝑒𝑟𝑡𝑒𝑥𝑡) ensures that 𝑀 was already broadcast via brb_broadcast by 𝑝𝑘 before 𝑝 𝑗 broadcasted its ACK. Otherwise, due to the unpredictable nature of randomized threshold ciphertexts, 𝑝 𝑗 could not have predicted the ciphertext hash beforehand to piggyback the correct ℎ on its ACK message. □ Theorem B.4 (BCRB Delivery). If a message 𝑚 1 = ((𝑏 1, 𝑠 1 ), payload) from process 𝑏 1 (whether 𝑏 1 is a Byzantine or correct process) is inserted into the local pending set of any correct process 𝑝𝑖 , then 𝑚 1 will eventually be BCRB-delivered by every correct process (if payload is not an ACK). Proof. If message 𝑚 1 = ((𝑏 1, 𝑠 1 ), 𝑝𝑎𝑦𝑙𝑜𝑎𝑑) is inserted into pending at any correct process 𝑝𝑖 (implying 𝑚 1 was BRB-delivered at 𝑝𝑖 ), then all 𝑚 1′ = (𝑏 1, 𝑠 1′ ) | 𝑠 1′ ≤ 𝑠 1 , and all their transitive causal predecessors that have been reported on ACKs, are also BRBdelivered and their processing completed locally in source-FIFO order and added to pending and to 𝐺. By the Agreement property of the underlying BRB layer, 𝑚 1 and all 𝑚 1′ are also eventually BRB-delivered at every correct process 𝑝𝑘 and added to 𝑝𝑘 ’s local pending set and 𝐺. Upon BRB delivery of 𝑚 1 , every correct process 𝑝𝑘 broadcasts its 𝐴𝐶𝐾 (𝑚 1 ) via the BRB layer if 𝑝𝑎𝑦𝑙𝑜𝑎𝑑 is not ACK. Since there are at least 𝑛 − 𝑓 correct processes, every correct process 𝑝𝑘 eventually BRB-delivers at least 𝑛 − 𝑓 ACKs/shares for 𝑚 1 (and 𝑚 1′ ), satisfying the 𝑞𝑢𝑜𝑟𝑢𝑚_𝑜𝑘 condition. Since the dependency graph 𝐺 = (𝑁 , 𝐸) is a DAG (Theorem B.1) with finite history, all paths from 𝑚 1 lead to leaf nodes. The leaf nodes satisfy the delivery conditions (𝑓 𝑖 𝑓 𝑜_𝑜𝑘 and no outgoing edges), and are BCRB-delivered if 𝑝𝑎𝑦𝑙𝑜𝑎𝑑 is not ACK. A leaf node along with its incident edges is also deleted from the graph, and deleted from pending. This recursively reduces the path lengths for the ancestor nodes. Inductively, all predecessor dependencies of 𝑚 1 are delivered (if their 𝑝𝑎𝑦𝑙𝑜𝑎𝑑 is not ACK), and cleared from the graph. Once all outgoing dependency edges of 𝑚 1 are deleted, 𝑚 1 itself satisfies the delivery conditions and is BCRB-delivered (if 𝑝𝑎𝑦𝑙𝑜𝑎𝑑 is not ACK) at every correct process. □

Observe that the above theorems B.1, B.2, B.3, B.4, B.5 also hold for Algorithm 4. 3 has the same probability of strong safety violation Algorithm ln2 𝑓

Theorem B.5. Algorithm 3 satisfies Validity (Liveness), Agreement, and Integrity at the BCRB layer.

O 𝑓 as Algorithm 1 because the same analysis as in Theorem 5.8 holds and 𝑃 (𝐵 < 𝐴) is the same as in Theorems 5.3 and 5.6. Algorithms 2, 4 are subject to strong safety violations due to frontrunning attacks as well as 𝑃 (𝐵 < 𝐴) (the same as in Theorems 5.3 and 5.6) being greater than 0.

Proof. Follows from Theorem B.4 and the properties of the underlying BRB layer:

Record · ID 1028659 · SHA-256 7ac7a82bd6c87de1
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.