arXiv CSopen access

Byzantine Reliable Broadcast with Causal Ordering

Byzantine Reliable Broadcast with Causal Ordering Mariarosaria Barbaraci* University of Bern [email protected]

Christian Cachin* University of Bern [email protected]

arXiv:2609.17074v1 [cs.DC] 15 Sep 2026

16 September 2026

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 totalorder 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). We show 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 concretely via a front-running attack that violates causality in reliable broadcast, but that cannot be captured through the existing definitions. 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(n2 (|m| + λ + n)), where λ denotes the maximal size of a unique (cryptographic) label for m. Finally, we analyze the properties of this protocol and prove that it achieves Byzantine reliable broadcast with causal ordering.

1

Introduction

For implementing distributed services in potentially adversarial environments, causal ordering is essential for applications where the semantic correctness of operations depends on preserving event dependencies. Systems such as decentralized finance, collaboration platforms, and critical infrastructure are particularly vulnerable to adversaries who exploit inconsistent ordering to manipulate state, deceive users, or disrupt operations. By ensuring that correct processes observe causally related events in an order that respects these dependencies, causal ordering strengthens both reliability and security in distributed systems. Many solutions [32, 8, 16, 21, 20, 9, 38] address this problem in total-order broadcast or consensus protocols and enforce a causal order on payload messages delivered to an application. They occupy a prominent position in the blockchain space because they prevent front-running attacks on consensus protocols and on-chain decentralized finance [14, 36]. In particular, Reiter and Birman [32] introduced the notion of input causality for total-order broadcast, according to which a malicious participant must not be able to induce delivery of a payload message m′ after observing a payload message m that has not yet been delivered. This may arise when 1

Institute of Computer Science, University of Bern, Neubrückstrasse 10, 3012 CH-Bern, Switzerland.

1

Byzantine participants observe m in low-level messages exchanged during the execution of the protocol. Cachin et al. [8] formalize this notion as secure causal atomic broadcast, and Duan et al. [16] revisit it by proposing new implementations. These formalizations of causal message order capture the intended restrictions in the Byzantine model in connection with total-ordered delivery of the payload messages, and all implementations rely on consensus. However, they fail to provide an independent definition of causality in this setting. As decentralized systems become increasingly large-scale and geographically distributed, the demand for latency-efficient and scalable solutions continues to grow. And enforcing a total order on all messages introduces substantial overhead, particularly in Byzantine environments where an adversary may delay, reorder, or equivocate messages. It has also been recognized that for many practical applications, total ordering is unnecessarily strong and too costly [31, 33], especially also for BFT state-machine replication and in the domain of cryptocurrencies [15, 17, 13, 1]. Correctness often depends only on preserving the order between causally related messages, while concurrent messages with independent requests may be processed in different orders without affecting system semantics. By relaxing the total order of consensus to reliable broadcast, systems can process messages concurrently with the assurance that eventually all processes will observe all messages. This reduces synchronization cost, improves throughput and responsiveness, and leads to more scalable platforms. Practical systems have recently been proposed for the blockchain space that follow this pattern [25, 35, 10]. Even though it is well-known that total-order message delivery and causal-order message delivery are orthogonal properties [18], formulating and implementing reliable broadcast with causal ordering in the Byzantine model introduces significant challenges. In particular, malicious participants may attempt to fabricate, omit, or reorder causal dependencies in ways that are difficult to detect. In systems tolerating only benign faults, such as crashes, the sender of a message attaches information about past events to it, thereby self-reporting its dependencies. This approach falls short here because a Byzantine sender may equivocate or intentionally manipulate dependency information to violate causality among the correct processes. In this work, we study causal ordering of messages for Byzantine broadcast without total order, in particular for reliable broadcast. We revisit existing notions of causal message ordering in the Byzantine model [3, 29] and recognize that existing definitions do not account for possible Byzantine behavior and effects that such behavior may have, as they still rely on the traditional definition of causality based on events observed at single processes (Lamport’s happened-before relation [24]). To address this gap, we first motivate and introduce an extended abstraction of reliable broadcast and then formalize the first complete notion of causal order among payload messages for the Byzantine model. It is grounded in observations made by sufficiently many correct processes, rather than a single process’s view. However, it is defined in such a way to mirror its crash-fault counterpart. We then define a reliable broadcast channel in the Byzantine model with causal-order message delivery. Furthermore, we provide a protocol of a broadcast channel that extends Bracha’s [6] reliable broadcast to many concurrent instances that respect causal ordering. In one protocol instance, the sender first hides the payload message cryptographically using a verifiable encapsulation (VE) primitive, and the algorithm then proceeds in five rounds: send, echo, ready, schedule, and reconstruction. At the outset of the protocol, processes do not observe the message and agree on a label that VE has associated with the message. A second key mechanism is the use of vector clocks. Each process maintains in a local scheduled vector a list of how many labels per process it has already scheduled. This vector is shared with other processes every time an echo message is being sent. Then, through a causal barrier condition on echo/ready validation, a process accepts an echo/ready message only when the attached vector clock, tracking causal dependencies, is consistent with its local scheduled vector. Consequently, the protocol ensures that labels are scheduled in a causality-respecting order. Once a label is scheduled, it is placed in an ordered queue; after enough processes have scheduled some label, the processes start the reconstruction round, recover the payload, and deliver it in that scheduling order. To complement the above discussion and further motivate the goal of this work, consider how a front-

2

running attack on a replicated service may arise without total-order guarantees. Let P = {p1 , p2 , p3 , p̄4 } be a set of four processes, where p̄4 is Byzantine and controlled by an adversary that also controls the network. In the execution shown in Figure 1, process p1 broadcasts a message m. The solid arrows abstract an execution of Byzantine reliable broadcast [7], where the dot at the sender denotes the broadcast event and the arrowhead denotes message delivery. For clarity, the dashed arrow explicitly represents the first message sent from p1 to p̄4 during the protocol that contains m or lets p̄4 obtain m. Upon learning m, the adversary gains the ability to inject a message m′ on behalf of p̄4 before some correct processes deliver m. By selectively delaying the delivery of m, the adversary can cause some correct processes to deliver m′ before m, while omitting the existing dependency between the two messages. As a result, the adversary effectively hides the causal relation between m and m′ that would exist under a global view of the execution. The attack is subtle because it makes m and m′ appear concurrent from the perspective of correct processes. Consequently, existing reliable broadcast protocols aiming at preserving causal ordering may fail to detect this violation. The reason is that the attack does not explicitly contradict the dependency information reported by Byzantine participants, which in this case can be the empty set or arbitrarily chosen. From the viewpoint of correct processes p2 and p3 , the causal dependencies associated with m′ are simply missing, even when a hidden causal relation to m exists under a global view of the execution. p1

p1 delivers m, m′ , . . .

m

p2 delivers m′ , m, . . .

p2

p3 delivers m′ , m, . . .

p3 p̄4

p̄4 delivers m′ , m, . . . m′

Figure 1. Process p̄4 front-runs message m at p2 and p3 . Even though almost all cryptocurrencies and blockchain networks today deliver their requests in total order among their validators, one can conceive application services for which reliable request delivery is sufficient, assuming that it also respects causal order. A name registry, for instance, may record names and assign exclusive ownership over them to clients. Names are from a large domain, hence, the service can be implemented so that different names are registered concurrently in order to increase throughput. Only when multiple clients try to register the same name, the registry has to invoke consensus and order these requests. If the communication for the registry uses Byzantine reliable broadcast, an “interesting” name contained in a client request may be stolen by a malicious validator process, as shown in the front-running scenario. Causally ordering the requests prevents this attack. Organization. The rest of the paper is organized as follows. In Section 2 we introduce the system model and the necessary background. In Section 3 we present our new definitions of broadcast and causality in the Byzantine setting, and we discuss the security properties required by a reliable broadcast primitive to guarantee causal ordering. In Section 4 we present a protocol that implements the proposed abstraction and in Section 5 show that it satisfies the required properties. Finally, in Section 6 we review related work. Section 7 concludes the paper. Moreover, in Appendix A we discuss secure implementations of VE.

3

2

Preliminaries

2.1

Distributed system model

We consider a standard distributed system consisting of a set P = {p1 , p2 , . . . , pn } of n processes that run local computations and communicate by exchanging messages over a network in order to perform a distributed protocol [7]. Processes communicate through reliable and authenticated point-to-point channels. We refer to a crash-fault model when a process may stop executing local computations and sending messages to other processes. Conversely, we refer to a Byzantine-fault model when a process may deviate in arbitrary ways from the protocol. The failure model sets a lower bound for the size of the set of faulty processes: with f faulty processes, one requires n > 2f for crash faults and n > 3f for Byzantine faults. We call processes that follow the protocol correct. Timing assumptions. The network is asynchronous: there is no global notion, no assumption on the time it takes for messages to be delivered, and no bound on local computation time. Each process can only rely on the events it observes, which arise either from local computation or from messages received from other processes. Following the notions introduced by Lamport [24], every process may keep track of a time by incrementing a logical clock that counts events. Logical clocks naturally capture a causeeffect relation of actual causal influence in this setting. An execution of a distributed protocol can be seen as a sequence of events visible only to a global observer. The happened-before relation captures the potential causal precedence between events occurring at the same process (trivially) or between a reception and subsequent transmission event. In terms of logical clocks, an event happens before another if and only if the logical clock attached to it is strictly smaller.

2.2

Broadcast abstraction

A fundamental primitive for group communication is the broadcast abstraction [7, Sec. 3]. It allows to extend the traditional client-server interaction to a set of processes [11]. Since multiple payload messages may be disseminated like this, the abstraction operates like a broadcast channel. More formally, given a set of n processes P, a broadcast abstraction allows a sender process ps ∈ P to disseminate a payload message m to all processes in P. This primitive is characterized by a broadcast event that occurs only at the sender process. We make the standard assumption that every correct process broadcasts a particular message only once. Every process receives or delivers a payload through a deliver event. The abstraction ensures validity in the sense that every message broadcast by a correct sender is eventually delivered; no duplication, that no message is delivered twice; integrity, ensuring that every delivered message was actually broadcast; and finally agreement, the all-or-nothing property of message delivery. The latter means that if a message m is delivered by some correct process, then every correct process eventually delivers m. Causal broadcast. As protocols become more complex in the context of group communication with crash faults, the happened-before relation can be extended to capture causal dependencies between broadcast and deliver events, specifically by considering the order in which processes broadcast payload messages and how those payloads are delivered by each process in the system. Thus, one can extend the happened-before concept to the broadcast channel [24, 4], where events represent broadcast or deliver events of messages exchanged by the processes in the system, as follows. Definition 1 (Causal-order relation with crash faults). Given two messages m1 and m2 , we say that m1 causally precedes m2 , and write m1 ≺ m2 , if either of the following conditions hold: 1. A process broadcasts m1 and then broadcasts m2 . 2. A process delivers m1 and then broadcasts m2 . 3. There exists a message m′ such that m1 ≺ m′ and m′ ≺ m2 . 4

If m1 ̸≺ m2 and m2 ̸≺ m1 , we say that the two messages are concurrent. The causal-order relation is used to add the property of causal delivery to reliable broadcast, which preserves causal ordering among the delivered messages. It ensures that when a message m1 causally precedes another message m2 , then no process delivers m2 unless it has already delivered m1 . A reliable broadcast that additionally satisfies causal delivery realizes a causal broadcast protocol under crash faults, which is a standard notion in the distributed-computing literature [18, 2]. Causal order actually strengthens FIFO order, which restricts the delivery order only for those payload messages that have been broadcast by the same process. It is also widely understood that imposing causal order on reliable broadcast is orthogonal to requiring total order for all delivered payloads [18]. Practical implementations of causal-order broadcast for systems subject to crash faults rely on an underlying reliable broadcast mechanism for communication, together with a data structure that records the causal past of each message. This can either take the form of a vector clock that consists of one sequence number per sender that indicates how many payload messages from that sender have already been delivered in the context where the sender has previously broadcast the particular payload message. The role of the vector clock is twofold: (1) a sender process includes its causal past when broadcasting a message; (2) a receiving process stores a message m, together with its associated vector clock W , in a pending queue until all the messages reported in W have been delivered. Alternatively, and only as a conceptual solution, one might also add the complete causal past to every payload message during broadcast [18, 2].

2.3

Byzantine reliable broadcast

The existing protocols for reliable broadcast with crash faults rely on correct processes to retransmit low-level messages and assume that all data reported by other processes is accurate and represents the true state at those processes. In the Byzantine model, however, this may not hold. Instead one has to invoke a different approach, since protocols can only rely on actions of correct processes. In particular relies on the view of a majority of correct processes or a quorum to consider an information reliable. A Byzantine quorum tolerating f faulty processes is a set of more than n+f 2 processes [26]. Any two such quorums always overlap in at least one correct process. The notion of Byzantine reliable broadcast is traditionally defined for a single protocol instance where agreement is reached on delivering one payload message. It can be extended modularly to broadcasting multiple messages in the sense of a broadcast channel by collecting together many instances, of which each is identified uniquely [7, Sec. 3.12]. More precisely, each attempt to broadcast a payload message by a particular sender is associated with a label from a global label space L that is partitioned by sender into disjoint subsets Li for pi ∈ P. When process pi broadcasts a payload message m in the message space M, the channel assigns a fresh label ℓ ∈ Li , and the instance is identified by ℓ alone, with the sender implicitly known through the partition of the label space. A partial map µ : L ⇀ M represents this binding on issued labels, so that each defined label corresponds to exactly one attempt to broadcast a payload message. A correct process broadcasts a message m through a ch-broadcast(m) event. The abstraction then selects a label ℓ and reports ℓ in a ch-deliver(ℓ, m) event to indicate that the payload message is received. Definition 2 (Byzantine reliable broadcast channel). A Byzantine reliable broadcast channel (BRCH) allows processes to broadcast payload messages and delivers them such that it satisfies the following properties for each label ℓ: Validity: If a correct process ps broadcasts a message m, then every correct process eventually delivers m with associated label ℓ, such that ℓ ∈ Ls . No duplication: For every label ℓ, every correct process delivers at most one message with label ℓ. Integrity: If some correct process delivers a message m with label ℓ, where ℓ ∈ Ls for some process ps and process ps is correct, then m was previously broadcast by ps . 5

Agreement: If some correct process delivers a message m with label ℓ, then every correct process eventually delivers message m with label ℓ. It is worth noting that the agreement property may be decomposed in two orthogonal ones that hold for each label: First, a safety property, consistency, which enforces that if two correct processes deliver a message with some label ℓ, then it is the same message m that every other correct process delivers with ℓ, and second, a liveness property called totality, which captures the all-or-nothing requirement, that if one correct delivers some message with label ℓ, then all correct processes eventually do so [7]. Implementations of Byzantine reliable broadcast channel are derived directly from the celebrated protocol of Bracha [6] for broadcasting one single payload with an associated label ℓ. The broadcast channel runs one instance of it for each of the n processes that may act as senders concurrently. When one instance terminates, it starts the next one for this sender. This naturally defines also per-sender sequence numbers for payload messages on the broadcast channel. We briefly describe here one instance of Bracha’s protocol. It proceeds in three rounds of communication: In the SEND round, the sender ps sends the message to all processes pi ∈ P. In the ECHO round, a correct process pi retransmits the message from the sender ps to all. In the READY round, a correct process pi , upon collecting a Byzantine quorum ECHO messages, retransmits again the payload to all. Upon collecting more than f READY messages, a correct process that hasn’t still received the quorum of ECHOS, skips ahead and sends a READY message in what is called the amplification step. (It relies on the fact that at least one correct process has received a quorum of ECHO messages for the payload.) And upon collecting more than 2f READY messages, a correct process delivers the contained payload. (This can be done since there are more than f correct processes that entered the READY round and will eventually bring all correct processes to deliver.)

3

Causal ordering in the Byzantine setting

The traditional definition of causality according to Definition 1 is expressed through events occurring at all processes, including the faulty ones. This does not extend to the most useful notion of causal ordering for Byzantine reliable broadcast because it lacks information on events that occur at Byzantine processes. This section discusses the issue and presents a solution by extending the interface of a broadcast primitive.

3.1

Limitations of existing approaches

There are two fundamental issues that make the traditional notion of causal order problematic in the Byzantine model. Events for defining causality. The first problem derives from the lack of information on events that occur at Byzantine processes. Any formal notion in the Byzantine model must be stated in terms of events occurring at correct processes, as no assumptions can be made on the behavior of the adversary and the processes under its control. In other words, one cannot express that a faulty process may have “delivered” some payload message m that subsequently led it to “broadcast” a message m′ that would then causally depend on m. The adversary may skip any kind of “broadcasting behavior” for m′ as long as its actions make some correct process deliver m′ . One of the most advanced definitions of causal reliable broadcast with Byzantine faults, by Auvolat et al. [3], indeed starts from Definition 1, but restricts its second condition to events occurring at correct processes. This modification results in a weaker notion than the one we envisage here. More precisely, Auvolat et al.’s Byzantine causal relation orders all payload messages from the same sender, whether it is faulty or correct, with respect to each other and also considers that any payload message delivered by a correct process causally precedes all payloads broadcast subsequently by that process. (Naturally, the causal order includes also the transitive hull.)

6

In particular, this means that every correct process delivers the payload messages from one sender in the order imposed by the sender (i.e., FIFO order). It also implies that the local order at a correct process among all messages it delivers and subsequently broadcasts is maintained by the causal order. However, the notion does not capture situations in which such a causal influence occurs through the actions of faulty processes, such as the example shown in the introduction (Fig. 1). Low-level messages revealing information about payloads. The second difficulty in the Byzantine model concerns actions available to faulty processes when they exchange low-level protocol messages. When a correct process broadcasts a payload message m, it must communicate m to the other processes through low-level messages. Unless cryptographic techniques are used in the protocol to hide m, an adversary controlling the network has the ability to observe information about m in low-level messages as soon as a m has been broadcast. Such information can then be exploited by the adversary even if m is never delivered by any faulty process. Many existing notions of causal-order broadcast in the Byzantine model have addressed only totalorder message delivery and solved the above problem by adding confidentiality for payload messages through cryptographic means up to a certain point in time. This approach was pioneered by Reiter and Birman [32] and later extended and refined by many others [8, 16, 27]. Their common theme are cryptographic notions of confidentiality that rely on total-order delivery of payloads, i.e., that all correct processes deliver the payload messages in the same sequence. Implementations have either used a commit-reveal strategy, which requires the sender to initially disseminate a commitment or sharing of the input message, and once an order has been decided, they reveal the message. Notably this solution fails in the presence of faulty senders, as it requires the sender to open the commitment in a second stage and speak twice. Other implementations have encrypted the payloads message such that set of processes may jointly decrypt it afterward, typically through threshold cryptography that requires correct processes to collaborate for decryption. Both techniques fail in our setting that does not assume a total order. In particular, the adversary can influence the local delivery order at correct processes after the payload has been revealed or decrypted. This may contradict the desired notion of causality. The inherent problem lies in the lack of synchronization among the correct processes for revealing or decrypting payloads since this may occur concurrently.

3.2

Stronger causal order for Byzantine reliable broadcast

To prevent the front-running attack, one should postpone the moment in which the adversary learns about the payload in message m to a later point after the ch-broadcast event. Moreover, correct processes must be able to “observe” a potential causal dependency for a message m before its delivery. We therefore formally define intermediate events, which occur between ch-broadcast and ch-deliver. In the context of a broadcast channel, we leverage the presence of a label ℓ associated with message m to define (1) when ℓ is first observed and (2) when the message m associated with ℓ can safely be disclosed. Crucially, because a correct process cannot “trust” the legitimacy of a label ℓ the first time it observes it, it needs to know when a particular message referenced by the associated label ℓ is being considered for delivery by sufficiently many processes. We capture these occurrences at a correct process pi like this: we say a correct process ch-acknowledges the presence of a label ℓ when it first observes ℓ, and we say it ch-schedules a label ℓ when enough processes agree on the existence of such ℓ, and, consequently, on the existence of the associated message m. These intermediate events may be exposed by an enhanced broadcast abstraction. Notably, we want to be able to properly define what happens in the system, even as a consequence of adversarial actions, through the perspective of just correct processes. For instance, when a correct process ch-acknowledges a label ℓ, it can either be that a correct process has ch-broadcast a message m associated with ℓ or that a Byzantine process has injected a message m associated with ℓ in the network. In both cases, the ch-

7

acknowledge event signals that a message associated with ℓ might exist, and therefore it can be used as an anchor for defining potential causality. We repeat the events characterizing a Byzantine broadcast channel and introduce the new intermediate events. They occur in this order at all correct processes, where ch-broadcast occurs only at the sender. • ch-broadcast(m): a sender process ps initiates a broadcast for a message m. • ch-acknowledge(ℓ): a process pj ∈ P acknowledges a label ℓ. • ch-schedule(ℓ): a process pj ∈ P schedules a label ℓ. • ch-deliver(ℓ, m): a process pj ∈ P delivers a label ℓ with the associated message m. We now use these intermediate events to expose actions in the system from the point of view of a global observer monitoring the correct processes during an execution. Looking ahead, we want our definition of causality to not rely on the local view at a single process. Instead, we want to be able to substitute local observations with global observations. The first global event captures the moment when the first correct process receives a label ℓ. It signals that a message associated with ℓ might exist. Definition 3 (Commit event). A commit event for a label ℓ, denoted C(ℓ), is the first point in time when a correct process ch-acknowledges a label ℓ. The second global event captures when enough correct processes consider a label ℓ ready for delivery. Intuitively, we would like a protocol to postpone the release of payload m until this moment. Definition 4 (Quorum schedule event). A quorum schedule event for a label ℓ, denoted QS(ℓ), is the first point in time when more than n−f 2 correct processes have ch-scheduled a label ℓ. Finally, we establish an actual causal-influence relation between these events when occurring for two labels from different senders. Notably, for any label ℓ, it trivially holds that C(ℓ) precedes QS(ℓ). Definition 5 (Schedule order). Given two labels ℓi and ℓj , such that ℓi ∈ Li and ℓj ∈ Lj , where SO

Li ̸= Lj , we define a schedule order relation, denoted ℓi → ℓj , whenever QS(ℓi ) precedes C(ℓj ). The schedule order is strict partial order on labels and associated messages, as it is irreflexive and transitive. Intuitively, we would like a protocol preserving causal ordering to postpone the release of payload m until the moment when the associated label ℓ reaches the quorum schedule event QS(ℓ). Let m be a message broadcast by a correct process and ℓ be the associated label. Then, no event preceding QS(ℓ) should depend on the payload m. We are now finally ready to define a new notion of causality in the Byzantine setting. Notably, the relation is defined on the set of messages delivered by correct processes. Following the structure of Definition 1, the new causal order relation covers three cases: (1) messages sent by the same sender, (2) messages sent by different senders, and (3) transitivity. For messages emitted by the same sender, similar to Auvolat et al. [3], we require that if a correct process delivers two messages from the same sender, then the order of delivery reflects the order chosen by the sender, independently of the time at which the messages appeared in the system. The second case instead captures causal dependencies arising from the global view on protocol events across different processes. In the crash-fault model, we consider the local causal influence relation between the ch-deliver of a message m and a ch-broadcast of a message m′ . In the Byzantine setting, we consider the global causal influence relation that substitutes the ch-deliver with an event happening before delivery, and the ch-broadcast with an event happening after the broadcast in the view of correct processes. This is exactly what the schedule order captures, as it relates the quorum schedule event of a label ℓ with the commit event of another label ℓ′ . The third case is just the transitive closure of the first two. We introduce the new notion as follows: 8

Definition 6 (Causal-order relation for Byzantine faults). Consider two labels ℓ1 and ℓ2 , associated with messages m1 and m2 , respectively, delivered by any correct process. We say (ℓ1 , m1 ) causally precedes (ℓ2 , m2 ) in the Byzantine setting and write (ℓ1 , m1 ) ≺B (ℓ2 , m2 ) whenever any of the following conditions hold: 1. A correct process pi delivers (ℓ1 , m1 ) before (ℓ2 , m2 ) for the same sender ps , such that ℓ1 , ℓ2 ∈ Lj ; if the sender ps is correct, it has broadcast m1 before m2 . SO

2. The two labels ℓ1 and ℓ2 satisfy the schedule order, i.e., ℓ1 → ℓ2 ; or 3. There exists a label ℓ′ associated with message m′ such that (ℓ1 , m1 ) ≺B (ℓ′ , m′ ) and (ℓ′ , m′ ) ≺B (ℓ2 , m2 ). If (ℓ1 , m1 ) ̸≺B (ℓ2 , m2 ) and (ℓ2 , m2 ) ̸≺B (ℓ1 , m1 ), we say that the two messages are concurrent. Since the adversary and the Byzantine processes must not let any information between messages flow outside the causal-order relation, we must also add a confidentiality requirement for payloads. In particular, we require that a payload message m with label ℓ remains hidden up to QS(ℓ). With all necessary ingredients now in place, we introduce a new primitive, Byzantine Reliable Broadcast with Causal Ordering (BRB-CO), which provides a secure building block in the Byzantine setting. BRB-CO extends the properties of a Byzantine reliable broadcast channel with three more properties: completeness, hiding, and Byzantine causal delivery. In the following, we define such primitives and repeat the properties of BRCH (Definition 2) to account for the additional events. Definition 7 (Byzantine reliable broadcast with causal ordering (BRB-CO)). A Byzantine reliable broadcast with causal ordering (BRB-CO) is a Byzantine reliable broadcast channel that satisfies the following properties: Validity: If a correct process ps broadcasts a message m, then every correct process eventually delivers m with associated label ℓ. No duplication: For every label ℓ, every correct process delivers at most one message with the same label ℓ. Integrity: If some correct process pi delivers a message m and label ℓ with ℓ ∈ Ls and the sender process ps is correct, then m was previously broadcast by ps , and pi had acknowledged label ℓ. Agreement: If some correct process delivers a message m with label ℓ, then every correct process eventually delivers message m with the same label ℓ. Completeness: If some correct process schedules a label ℓ, then it will eventually deliver the message m associated to ℓ. Hiding: For any label ℓ associated with a message m broadcast by a correct process ps , no process other than ps can determine any information about m before the quorum schedule event QS(ℓ) occurs. Byzantine Causal Delivery: For any label ℓ1 associated with message m1 that causally precedes ℓ2 associated with m2 , i.e., (ℓ1 , m1 ) ≺B (ℓ2 , m2 ), no correct process delivers m2 with label ℓ2 unless it has already delivered m1 with label ℓ1 . Notably, the completeness property ties the scheduling of a label to eventual delivery, effectively decoupling agreement on the label from retrieval of the associated message. The hiding property requires any implementation to reveal the payload message after the quorum schedule event, that is, only once enough processes have reliably observed that label. Together, the two properties, support and guarantee Byzantine causal delivery. Our notion anchors the causal order in events that arise during the execution. This parallels the traditional causal-order definition in the literature on distributed systems and, unlike earlier definitions of causal-order broadcast in the Byzantine setting [8, 16], it does not define causality directly from cryptographic secrecy. 9

4

Implementation of BRB-CO

In this section, we first define a primitive, which we refer to as verifiable encapsulation (VE), which allows to hide a message m among a set of n processes, and later to recover it from a fraction of them. We then introduce a complete protocol for BRB-CO. Finally, we study the complexity of the proposed implementation.

4.1

Verifiable Encapsulation

We model Verifiable Encapsulation as an ideal distributed functionality, to which every process pi ∈ P has access. The ideal implementation maintains internal shared state through two associative arrays E and V: for each message m the implementation assigns a fresh identifier ℓe such that E[ℓe ] = m, and stores a tuple (ei , si ) per process, such that V[pi , ℓe ] = (ei , si ). Notably, we call ei encapsulation data and si share, and they are used to validate the encapsulation and recover the data for reconstruction, respectively. Practical instantiation of VE may also merge the roles of ei and si into one value. VE provides the following operations: • VE.Setup(n, k) → pp. This function initializes the primitive for n processes and reconstruction threshold k ≤ n. It returns public parameters pp to each process pi ∈ P. • VE.Encapsulate(m) → (ℓe , [ei ]i∈[n] ). On input message m the implementation chooses a fresh encapsulation identifier ℓe and computes a vector of encapsulated data [ei ]i∈[n] and shares [si ]i∈[n] for each process pi ∈ P in the system. It updates its local state such that E[ℓe ] = m and V[pi , ℓe ] = (ei , si ) for each pi ∈ P. It outputs identifier ℓe and vector [ei ]i∈[n] . The vector of shares remains part of the state. Any process may invoke this function. • VE.Validatepi (ℓe , ei ) → b. The invocation specifies a caller process pi ∈ P, and on input an identifier ℓe and encapsulated data ei , the implementation outputs a boolean value b ∈ {0, 1}. The response is 1 if and only if there exist m and si such that E[ℓe ] = m and V[pi , ℓe ] = (ei , si ); otherwise, the response is 0. Only pi may invoke this function. • VE.Extractpi (ℓe , ei ) → si , where si may also be ⊥. The invocation specifies a caller process pi ∈ P, an identifier ℓe , and encapsulated data ei . The method outputs a share si ̸= ⊥ if there exists some m such that E[ℓe ] = m and V[pi , ℓe ] = (ei , si ); and ⊥ otherwise. Only pi may invoke this function. • VE.Verify(pi , ℓe , si ) → b. On input a process pi , an identifier ℓe , and a share si , the function outputs a boolean value b ∈ {0, 1}. The response is 1 if and only if there exists an m such that E[ℓe ] = m and it holds V[pi , ℓe ] = (ei , si ). Otherwise, the output is 0. Any process may invoke this function. • VE.Reconstruct(ℓe , S = {si }) → m, where m = ⊥ is also possible. On input an identifier ℓe and a set of shares S from different processes, the function outputs some message m. The output m is not ⊥ whenever E[ℓe ] = m and there exists a set of at least k processes such that for each pi in this set and si ∈ S, it holds V[pi , ℓe ] = (ei , si ) for some ei . Otherwise, the function outputs ⊥. Any process may invoke this function. Some encapsulation data ei or a share si is called valid (with respect to label ℓe and process pi ) when either VE.Validatepi (ℓe , ei ) = 1 or si is returned by VE.Extractpi (ℓe , ei ). According to this specification, the VE primitive provides the following three properties, which are fundamental for our use: • Identifier uniqueness: Given a identifier ℓe , there exists at most one message m such that E[ℓe ] = m and, for every other process pi , there exist at most one tuple (ei , si ) in V[pi , ℓe ].

10

• Privacy: Given a set of valid shares S = {si }, i.e., there exist an identifier ℓe and an encapsulation data ei such that V[pi , ℓe ] = (ei , si ). If |S| < k, no information on m is revealed. • Reconstruction: Given a set of valid shares S = {si }, i.e., there exist an identifier ℓe and an encapsulation data ei such that V[pi , ℓe ] = (ei , si ). If |S| ≥ k, the implementation returns a message m stored at E[ℓe ]. In Appendix A we discuss how to securely instantiate VE with several cryptographic schemes, including threshold cryptosystems and verifiable secret sharing. Next, we introduce the complete protocol for BRB-CO.

4.2

Protocol description

In Alg. 1–2, we present an implementation of the BRB-CO protocol by relying on the VE primitive to ensure the hiding property. The protocol is designed to be resilient to f Byzantine processes, where n > 3f . The protocol follows Bracha’s reliable broadcast [6], and extends it to provide causal ordering for a Byzantine reliable broadcast channel (BRCH) (Definition 2). We characterize the protocol for one payload message by its phases, or communication rounds: the SEND phase, the ECHO phase, the READY phase, the SCHEDULE phase, and the RECONSTRUCTION phase. Before the ECHO phase, a process ch-acknowledges the payload, and at the end of the READY phase, a process ch-schedules the payload according to Section 3.2. We refer to the message a correct process sends in a given round with the name of the round, e.g., in the ECHO phase, a process sends an ECHO message. The communication is one-to-all in the first round, and all-to-all in the others. The protocol implements a Byzantine reliable broadcast channel (BRCH), which handles the broadcast of multiple messages in parallel. Each message is associated with a label ℓ, and the protocol ensures the causal order of the labels, and the associated messages, across all correct processes according to Definition 6. We first present the data structures and their initializations and then give a detailed description of the protocol. Data structures and initialization. Every process first calls the setup function of VE with the number of processes n and reconstruction threshold f < k ≤ ⌊ n−f 2 ⌋ + 1. Recall n > 3f . The process also maintains several variables. A counter lsn records how many messages the process has locally broadcast. A vector clock SV , namely the scheduled vector, records the number of labels per sender this process has locally scheduled. Variables sentecho, sentready, sentschedule, sentrecon, and delivered maintain the respective sets of labels for which the process has locally sent the corresponding protocol message. The variable encaps stores the encapsulation data e per label, similarly, echoes, readys, schedules, and undelivered collect the corresponding protocol messages locally received from every other process pj . The temporary sets pendingecho and pendingready store not-yet-valid ECHO and READY messages. Finally, scheduledqueue maintains scheduled but not-yet-delivered messages. Such data structure implements a first-in first-out queue operated though a enqueue(v) function to add any new element v, and a dequeue() → v function to remove the oldest added element. Additionally, init() initializes the queue as empty and head() → v returns the first element without removing it. Description of the protocol. For every label ℓ, the first part of the protocol follows Bracha’s reliable broadcast with few modifications ensuring that eventually all correct processes schedule the same label ℓ respecting its potential causal dependencies. Scheduling a label corresponds to delivering the payload message in the original protocol, but BRB-CO adds more phases. The causal dependencies are estimated locally during the execution of the first phases according to the view of multiple processes. To this end, each process locally records in the scheduled vector (SV) how many labels from different senders it has locally scheduled, and sends it along with every new ECHO message. The second part allows correct processes to coordinate and jointly recover the associated message m. More precisely, an instance of the protocol consists of the following. A sender process ps encapsulates m using VE and disseminates it to all processes in a SEND message to each process. This contains 11

two values regarding m: the encapsulation data ei , and the associated encapsulation identifier ℓe . The encapsulation data serves two purposes: it allows every process to validate the identifier ℓe before sending an ECHO message, and later, if valid, to extract a share si and to reconstruct the message m. Additionally, SEND also contains the locally assigned sequence number sn. The first modification to Bracha’s protocol is that a process validates ℓe before it sends ECHO: if ℓe is valid, the process assigns to the broadcast instance the label ℓ = (ps , sn, ℓe ), which consists of the sender process ps , the sequence number sn, and the encapsulation identifier ℓe . The process also adds a vector clock W to its ECHO message, which equals the local value of SV . When sending ECHO the process also emits the event brbco-acknowledge(ℓ). The second modification consists of introducing a condition for sending the READY message; we refer to this condition as causal barrier, and it is applied in two places. These two causal barriers prevent a correct process from sending a READY message for a label ℓ that potentially causally depends on some other label ℓ′ before it has locally scheduled ℓ′ . Recall that every label uniquely identifies some associated message m, hence, whenever we talk about causal dependencies of labels, we mean causal dependencies of the associated messages. A correct process sends a READY message in two different places in the algorithm. The first is upon receiving a Byzantine quorum of ECHO messages. The new condition considers an ECHO message from a process pj only valid when the vector clock Wj contained in the message is less than or equal to the local variable SV , i.e., when Wj ≤ SV ; this is the ECHO causal barrier. Its presence implies that the process receiving ECHO has locally already scheduled at least the same number of labels per sender as pj before it proceeds to sending READY. Notably, the labels from one correct sender process follow a contiguous, increasing order due to the presence of the sequence number sn in the label. If an ECHO message is not valid yet, it is inserted into pendingecho until it becomes valid. The second place where a process can send a READY message is upon receiving more than f READY messages at a point in time when it has not yet obtained a Byzantine quorum of ECHO messages. A similar condition as in the ECHO causal barrier should apply here, and to this effect, every process attaches a vector clock also to its READY messages. However, this vector clock cannot be the current variable SV as attached to ECHO. When sending READY, a process should report all potential dependencies, but it is possible that this process is slow and has not yet observed the dependencies a Byzantine quorum in the network has. Therefore, a process attaches to such a READY message the component-wise maximum W max of the vectors from the messages that triggered the sending, i.e., either the quorum of ECHO messages or the set of more than f READY messages. A process receiving a READY message from a process pk considers it valid only after the so-called READY causal barrier, i.e., the vector Wkmax in READY is less than or equal to the local SV . If a READY message is not valid yet, it is inserted into pendingready until it becomes valid. The component-wise maximum ensures that if a label ℓ causally depends on another label ℓ′ , then in every possible Byzantine quorum, there is at least one correct process that sent an ECHO message for ℓ after scheduling ℓ′ . Consequently, every correct process would send a READY message for ℓ only after scheduling ℓ′ . Moreover, a correct process checks the two causal barriers only until it sends the first READY message for ℓ. Once the process has then received more than 2f READY messages for a label ℓ, it proceeds to scheduling ℓ. This means that it increments SV accordingly (at the index of the process that sent ℓ), inserts ℓ into scheduledqueue, sends a SCHEDULE for ℓ, and also emits the brbco-schedule(ℓ) event. This will ensure that the delivery order later follows the scheduling order. The last two rounds of the protocol coordinate the processes to extract and release their shares of the message. In particular, a correct process pi , upon receiving more than n+f 2 SCHEDULE messages, extracts its share si from ei (using VE), provided it initially received ei , and broadcasts it to all processes. If pi has not previously received ei , it simply does not contribute to the reconstruction. Eventually, every correct process schedules a label ℓ and thus receives more than n+f 2 SCHEDULE messages. Therefore, it will receive at least k valid shares from correct processes, which is sufficient to reconstruct the message m using VE. Recall f < k ≤ ⌊ n−f 2 ⌋ + 1.

12

The delivery then follows the ordering defined by the scheduling queue. The correctness of BRB-CO design depends on all its components. In the following, we informally discuss on the necessity of each one. A secure VE instantiation is fundamental to hide the payload of a message among the set of processes and ensure reconstruction later in the protocol even without the participation of the original sender. Definition 6 allows us to clearly capture the view of correct processes even in the presence of maliciously injected messages that reach the schedule phase and that are later delivered. Vector clocks shared during the ECHO round and incremented during the SCHEDULE round at each process, provide a consistent distributed data structure, with reliable increments, tracking possible causal dependencies. The component-wise maximum calculation on a quorum of vector clocks ensures “real” causal dependencies always appear in the local view of a correct process before scheduling a label. The causal barrier conditions prevent malicious senders from reporting false dependencies in such data structures and provide a wrong snapshot of the system global state. Finally, putting all together, the four all-to-all communication rounds bring the protocol to satisfy causal delivery.

4.3

Complexity analysis

We express the bit complexity of the protocol in terms of the size of the message |m|, the number of processes n, and λ, which denotes the maximal size of a unique (cryptographic) label for m. The exact size may depend on the specific VE instantiation. W.l.o.g., we assume the size of the encapsulation data e and the size of a share s of VE are O(|m|). Future work may explore more efficient VE instantiations that reduce the size of e and s by leveraging erasure codes and similar techniques. BRB-CO runs in five communication rounds. In the first round, the sender broadcasts a single message to all other processes; in every subsequent round, each process sends a message to every other process, yielding O(n2 ) messages per round and O(n2 ) overall, since the number of rounds is constant. The size of the messages exchanged is O(n|m| + λ) in the first round, O(λ + n) in the second and third rounds due to the inclusion of vector clocks, O(λ) in the fourth round, and O(|m| + λ) in the fifth round. Combining message and bit complexity across rounds, the overall communication complexity of the protocol is O(n2 (|m|+λ+n)). Notably, an Ω(n) lower bound on vector clock size is an unavoidable cost of capturing causality and concurrency information in a distributed system [2, Sec. 6.1.3.1].

5

Analysis

In this section, we provide a formal analysis of the proposed protocol and ultimately prove it implements a Byzantine reliable broadcast with causal ordering (BRB-CO). First, we prove agreement on the label ℓ. Lemma 1 (Label agreement). If a correct process pi brbco-schedules a label ℓ, then all correct processes eventually brbco-schedule ℓ. Proof by induction. (Base case): Let us assume all correct processes in the network have not yet brbcoscheduled any label, i.e., SV = [0]n at every correct process. Let us consider a correct process pi who brbco-schedules a label ℓ. Following the protocol, pi received more than 2f valid READY messages for label ℓ, and among those messages, more than f are from correct processes. Thus, every correct process pj who sent a valid READY message for ℓ attached to it a max vector Wj that is less than or equal to the local SV, i.e., Wj ≤ [0]n . Moreover, for the amplification step (line 45) every correct process pk , who has not sent READY, will eventually receive more than f valid READY messages for label ℓ, and send a READY message for ℓ and compute a max vector Wk ≤ SV ≤ [0]n . Hence, every correct process eventually collects more than 2f valid READY messages for label ℓ and thus brbco-schedules ℓ. (Induction step): Let us assume a set of labels Λ such that, if a correct process has brbco-scheduled all labels ℓ ∈ Λ, then all correct processes eventually brbco-schedule all ℓ ∈ Λ. Therefore, the vector clock SV at every correct process is eventually reporting the same number of scheduled labels for each sender; let us denote this vector SVΛ . We want to show that, if a correct process brbco-schedules a new label ℓ′ ∈ / Λ, then all correct processes eventually schedule ℓ′ . In fact, the same reasoning as in the base 13

Algorithm 1 Byzantine Reliable Broadcast with Causal Ordering (BRB-CO, part 1) for pi 1: State 2: pp ← VE.Setup(n, k) //VE functionality setup 3: lsn ← 0 //local sequence number of broadcast messages 4: SV ← [0]n //vector clock for SCHEDULE messages 5: sentecho ← ∅ //keeps the set of labels for which ECHO was sent 6: sentready ← ∅ //keeps the set of labels for which READY was sent 7: sentschedule ← ∅ //keeps the set of labels for which SCHEDULE was sent 8: sentrecon ← ∅ //keeps the set of labels for which RECONSTRUCT was sent 9: delivered ← ∅ //keeps the set of labels that have been delivered 10: encaps ← ∅ //for each label, collects the valid encapsulation data 11: echoes ← [∅]n //collects the valid ECHO messages from every other processes 12: readys ← [∅]n //collects the valid READY messages from other processes 13: schedules ← [∅]n //collects the valid SCHEDULE messages from other processes 14: undelivered ← [∅]n //collects the valid shares from other processes 15: pendingecho ← ∅ //collects ECHO messages 16: pendingready ← ∅ //collects not-yet-valid READY messages 17: scheduledqueue.init() //stores scheduled label in FIFO order 18: upon invocation brbco-broadcast(m) do 19: (ℓe , [e1 , . . . , en ]) ← VE.Encapsulate(m) 20: send message [SEND, lsn, ℓe , ej ] to all pj ∈ P 21: lsn ← lsn + 1

//only the sender ps

22: upon receiving a message [SEND, sn, ℓe , ei ] from ps ∈ P ∧ sn ≥ 0, ℓe ̸= ⊥ 23: 24: 25: 26: 27:

such that ℓ = (ps , sn, ℓe ) ∈ / sentecho ∧ VE.Validatepi (ℓe , ei ) do ℓ ← (ps , sn, ℓe ) sentecho ← sentecho ∪ {ℓ} encaps[ℓ] ← ei output brbco-acknowledge(ℓ) send message [ECHO, ℓ, SV] to all pj ∈ P

28: upon receiving a message [ECHO, ℓ, W ] from pj do 29: pendingecho ← pendingecho ∪ {(ℓ, pj , W )} 30: upon exists (p′j , ℓ′ , W ′ ) ∈ pendingecho such that W ′ ≤ SV do 31: pendingecho ← pendingecho \ {(p′j , ℓ′ , W ′ )} 32: echoes[p′j ] ← (ℓ′ , W ′ )

//ECHO causal barrier

33: upon exists ps , pj ∈ P, sn ≥ 0, ℓe ̸= ⊥

/ sentready do such that ℓ = (ps , sn, ℓe ) ∧ |{pj |echoes[pj ] = (ℓ, ·)}| > n+f 2 ∧ℓ∈ 34: sentready ← sentready ∪ {ℓ}   35: Wm ← maxvector W |(ℓ, W ) ∈ echoes[pj ] 36: send message [READY, ℓ, Wm ] to all pj ∈ P 37: upon receiving a message [READY, ℓ, Wm ] from pj do 38: pendingready ← pendingready ∪ {(pj , ℓ, Wm )} ′ ′ 39: upon exists (p′j , ℓ′ , Wm ) ∈ pendingready such that Wm ≤ SV do ′ ′ ′ 40: pendingready ← pendingready \ {(pj , ℓ , Wm )} ′ 41: readys[p′j ] ← (ℓ′ , Wm ) ′ 42: upon exists (p′j , ℓ′ , Wm ) ∈ pendingready such that ℓ′ ∈ sentready do ′ 43: pendingready ← pendingready \ {(p′j , ℓ′ , Wm )} ′ 44: readys[p′j ] ← (ℓ′ , Wm )

14

//READY causal barrier

//READY sent //flush the pending set for ℓ′

Algorithm 2 Byzantine Reliable Broadcast with Causal Ordering (BRB-CO, part 2) for pi 45: upon exists ps , pj ∈ P, sn ≥ 0, ℓe ̸= ⊥ such that ℓ = (ps , sn, ℓe ) ∧ |{pj |readys[pj ] = (ℓ, ·)}| > f ∧ ℓ ∈ / sentready do sentready ← sentready ∪ {ℓ}   ′ ′ 47: Wm ← maxvector Wm |(ℓ, Wm ) ∈ readys[ps , sn, j] 48: send message [READY, ℓ, Wm ] to all pj ∈ P 46:

49: upon exists ps , pj ∈ P, sn ≥ 0, ℓe ̸= ⊥ 50: 51: 52: 53: 54:

such that ℓ = (ps , sn, ℓe ) ∧ |{pj |readys[pj ] = (ℓ, ·)}| > 2f ∧ ℓ ∈ / sentschedule ∧ sn = SV[ps ] do sentschedule ← sentschedule ∪ {ℓ} send message [SCHEDULE, ℓ] to all pj ∈ P SV[ps ] ← SV[ps ] + 1 scheduledqueue.enqueue(ℓ) output brbco-schedule(ℓ)

55: upon receiving a message [SCHEDULE, ℓ] from pj do 56: schedules[pj ] ← ℓ 57: upon exists ps , pj ∈ P, sn ≥ 0, ℓe ̸= ⊥

/ sentrecon do such that ℓ = (ps , sn, ℓe ) ∧ |{pj |schedules[pj ] = ℓ}| > n+f 2 ∧ℓ∈ 58: sentrecon ← sentrecon ∪ {ℓ} 59: if encaps[ℓ] ̸= ⊥ then 60: ei ← encaps[ℓ] 61: si ← VE.Extractpi (ℓ, ei ) 62: send message [RECONSTRUCT, ℓ, si ] to all pj ∈ P 63: upon receiving a message [RECONSTRUCT, ℓ, sj ] from pj ∈ P∧ upon exists ps ∈ P, sn ≥ 0, ℓe ̸= ⊥ 64:

such that ℓ = (ps , sn, ℓe ) ∧ VE.Verify(pj , ℓe , sj ) do undelivered[pj ] ← (ℓ, sj )

65: upon exists ps , pj ∈ P, sn ≥ 0, ℓe ̸= ⊥ such that ℓ = (ps , sn, ℓe ) 66: 67: 68: 69:

∧|{pj |undelivered[pj ] = (ℓ, ·)}| ≥ k ∧ ℓ ∈ / delivered ∧ scheduledqueue.head() = ℓ do m ← VE.Reconstruct(ℓ, {sj |undelivered[pj ] = (ℓ, sj )}) delivered ← delivered ∪ {ℓ} ℓ ← scheduledqueue.dequeue() output brbco-deliver(ℓ, m)

70: function maxvector(list): 71: result ← [0]n 72: for W ∈ list do 73: for i ∈ [1, n] do 74: result[i] ← max(result[i], W [i]) 75: return result

//where list is a collection of vector clocks W of size n

15

case applies: a correct process pi scheduling ℓ′ has received more than f READY messages from correct processes with max vectors Wj less than or equal to the local SV ≤ SVΛ , which implies also Wj ≤ SVΛ . Again, for the amplification step, every correct process pk , who has not sent READY, will eventually receive more than f valid READY messages for label ℓ′ , and thus send a READY message for ℓ′ and max vector Wk ≤ SVΛ . Hence, every correct process eventually collects more than 2f valid READY messages for ℓ′ and thus brbco-schedules ℓ′ . Given that the agreement property inherently implies reliable updates to the scheduled vector, the next lemma proves that the order in which labels are scheduled at every correct process preserves causal ordering. We first prove the lemma and then describe a possible execution. Lemma 2 (Causal schedule). If (ℓ1 , m1 ) ≺B (ℓ2 , m2 ), then no correct process brbco-schedules ℓ2 before ℓ1 . Proof. From Definition 6, we assume that there exists a correct process pi that brbco-delivers (ℓ1 , m1 ) and (ℓ2 , m2 ). For each label, we will omit to report the corresponding message in the rest of the proof. Following the protocol, pi has previously brbco-scheduled ℓ1 and ℓ2 . Moreover, pi brbco-delivers the labels dequeued from the local queue scheduledqueue, which implies that pi has brbco-delivered either ℓ1 before ℓ2 or ℓ2 before ℓ1 , and consequently brbco-scheduled them in the same order. We want to show that every correct process brbco-schedules ℓ1 before ℓ2 . We distinguish between two cases: (1) ℓ1 and ℓ2 are from the same sender, or (2) from different senders. (1) For the same sender the order in the protocol is defined by the sequence numbers. Again, from the first condition in Definition 6, we know that there exists a correct process that has brbco-delivered ℓ1 before ℓ2 . This means that the sequence number attached to ℓ1 is smaller than the one attached to ℓ2 . Following the protocol, the sequence number is part of the label, i.e., ℓ = (ps , sn, ℓe ), and a correct process can only brbco-schedule a label ℓ with sequence number sn if it has already brbco-scheduled all labels from the same sender with sequence number smaller than sn (line 49). Hence, by label agreement (Lemma 1), every correct process brbco-schedules ℓ1 before ℓ2 . SO (2) For different senders the schedule order holds, ℓ1 → ℓ2 , and thus QS(ℓ1 ) precedes C(ℓ2 ). The commit event C(ℓ2 ) is defined as the first time a correct process brbco-acknowledges ℓ2 . From the protocol, this happens before the same correct process sends an ECHO message for ℓ2 (line 26). Let us consider a correct process pk ̸= pi who sends a READY message for ℓ2 , after receiving more than n+f 2 ECHO messages for ℓ2 . A vector clock is attached to each ECHO, and among such messages, more than n−f 2 are from correct processes. From the schedule order assumption we also know that there are more than n−f 2 correct processes that already have brbco-scheduled ℓ1 . Hence, there is at least one correct process pj that has already brbco-scheduled ℓ1 and sent an ECHO message for ℓ2 to pk with vector clock Wj that has already incremented in the position indexed by the sender of ℓ1 . More precisely, Wj [sender(ℓ1 )] ≥ sn(ℓ1 ) + 1, where sender(ℓ1 ) and sn(ℓ1 ) extracts from label ℓ1 the corresponding sender and sequence number, respectively. Moreover, because pk accepted this ECHO from pj , it holds Wj ≤ SVk , where SVk is the value of SV at pk . Then pk must have already brbco-scheduled ℓ1 . Notably, this also means that the component-wise maximum vector Wkmax computed by pk and attached to READY will already count ℓ1 , i.e., Wkmax [sender(ℓ1 )] ≥ sn(ℓ1 ) + 1, therefore reporting it as a possible dependency. We apply the same reasoning to every process sending READY after a quorum of ECHO. A similar reasoning holds for a process pq sending a READY in the amplification step, i.e., after receiving more than f READY. At least one of the READY messages is sent by a correct process, and, as is clear from the structure of the protocol, and shown formally in many analyses of the Bracha broadcast protocol [7], the first READY message ever sent by a correct process px was sent in response to receiving a quorum of ECHO. From before we know that, then px will count ℓ1 in its READY message, consequently, if a correct process pq accepts such a READY as valid, it means that Wxmax ≤ SVq , thus pq has already brbco-scheduled ℓ1 . In Fig. 2, we illustrate an execution of the protocol with four processes, where the adversary controls process P¯3 . W.l.o.g. we represent only brbco-acknowledge(ℓ) and brbco-schedule(ℓ) events. The former 16

P1

(ℓ1 , [0, 0, 0, 0]) (ℓ2 , [0, 0, 0, 0])

P2

ℓ2

(ℓ2 , [0, 0, 0, 0]) (ℓ1 , [0, 0, 0, 0])

(ℓ3 , [1, 1, 0, 0])

ℓ1 ℓ1

ℓ3

(ℓ3 , [1, 1, 0, 0])

ℓ2

ℓ3

P¯3 P4

t

(ℓ2 , [0, 0, 0, 0]) (ℓ1 , [0, 0, 0, 0])

C(ℓ1 ) C(ℓ2 )

(ℓ3 , [0, 0, 0, 0]) ℓ1

QS(ℓ1 ) QS(ℓ2 )

ℓ2

ℓ3

C(ℓ3 )

Figure 2. Execution for ℓ1 , ℓ2 and ℓ3 , where ℓ1 and ℓ2 are concurrent, and ℓ3 causally depends on both ℓ1 and ℓ2 . We show on the temporal line only the global events relevant to observe the causal precedence of ℓ3 from ℓ1 and ℓ2 . Notably, P4 that is slightly behind schedules first ℓ1 and ℓ2 , and only after ℓ3 . are denoted by an empty circle, and they occur at every correct process when it sends an ECHO message; this message contains the label and the local scheduled vector SV, which we explicitly depict. The latter events, brbco-schedule, are denoted by a filled circle, they occur at every correct process, and they report just the label. As we can observe from the projection on the temporal axis, the messages with labels ℓ1 and ℓ2 are concurrent, while the one with ℓ3 causally depends on both ℓ1 and ℓ2 following Definition 6 as both QS(ℓ1 ) and QS(ℓ2 ) precede C(ℓ3 ). Looking at the execution trace, we see that all the correct processes respect the causal relation at delivery. In particular, P4 is the first process emitting brbco-acknowledge(ℓ3 ), however, it will not send a ready for ℓ3 , until it locally schedules ℓ1 and ℓ2 , reported by both P1 and P2 as possible dependencies, effectively delaying the schedule of ℓ3 . Notably, even if the faulty P¯3 would inject protocol messages, process P4 still waits for a Byzantine quorum of ECHO, including either the messages of P1 or P2 , which include in the attached vector clock the information about ℓ1 and ℓ2 , thus respecting the causal order. In the following, we show that if a correct process schedules a label ℓ, there are enough processes that validated ℓ, acknowledged it, and are able to reconstruct the associated message m. Lemma 3. If a correct process pi brbco-schedules a label ℓ, more than n−f 2 correct processes have brbco-acknowledged the same label ℓ. Proof. Let us show that if the number of processes that brbco-acknowledge ℓ is less than or equal to n−f 2 , no correct process can brbco-schedule ℓ. Following the protocol, after that a correct process brbcoacknowledges a label ℓ, it sends an ECHO message. Let us consider a correct process pi that receives no more than n−f 2 ECHO messages from correct processes and other f (potentially from the adversary). But n−f + f is strictly less than the necessary quorum to send a READY message and progress, thus pi will 2 never move forward. This is true for every correct process. As the protocol requires a correct process to collect more than 2f READY messages in order to brbco-schedule ℓ and more than f for triggering the amplification step, no correct process can ever brbco-schedule label ℓ. Corollary 4. If a correct process pi brbco-schedules a label ℓ, enough correct processes jointly have the necessary information to reconstruct m. Proof. The corollary directly follows from Lemma 3 and the protocol: as more than n−f 2 correct processes brbco-acknowledge ℓ, given ℓ = (ps , sn, ℓe ), they previously received and validated the encapsulated data ei received by ps . As the reconstruction threshold of VE lives in f < k ≤ ⌊ n−f 2 ⌋ + 1, enough correct processes jointly have the necessary information to reconstruct m. By using the previous results, we prove that the provided implementation satisfies the BRB-CO properties. 17

Theorem 5. The protocol described in Alg. 1–2 implements the BRB-CO primitive. Proof. (Completeness) Let us consider a correct process pi that brbco-schedules label ℓ. By Lemma 1, we know that every other correct process eventually brbco-schedules ℓ. Thus, given that there are n − f correct processes in the system, pi collects enough SCHEDULE messages to trigger reconstruction (line 57). Similarly, every other process does so. During reconstruction, processes that hold valid e can extract the corresponding share s. Corollary 4 ensures that there are enough correct processes in the system able to reconstruct m. Finally, pi receives such shares (line 65), reconstructs m, and delivers m with label ℓ. (Validity) Let us assume a correct process ps brbco-broadcast a message m: it encapsulates m and obtains the encapsulation label ℓe and a vector of encapsulated data [ei ]i∈n , thus sends to each process pi the tuple (ℓe , ei ) and the local sequence number sn. Let us now assume correct process pj that receives ej and ℓe from ps , successfully validates them, assigns the associated label as ℓ = (ps , sn, ℓe ), brbcoacknowledges it and, finally, sends an ECHO message. The ECHO message contains also the vector SVj reporting possible dependencies that pj has already locally scheduled. Lemma 1 ensures that every other correct process eventually schedules those dependencies. The same happens at every other correct process either than pj . Upon receiving ECHO messages, pj validates them against the causal barrier condition (line 30). Once it collects enough ECHO (line 33), it sends a READY message. Following the protocol, every correct process sends a READY message, and upon collecting enough READY, it brbcoschedules label ℓ. At this point, the rest follows from Lemma 1, namely, every other correct process brbco-schedules label ℓ, and completeness. (No duplication and Integrity) The no duplication property and integrity follow from the definition of the label space and the label uniqueness property of VE. (Agreement) Let us consider a correct process pi , who delivers a message m with label ℓ. pi dequeued ℓ from the scheduled queue (line 68), thus it must have previously scheduled ℓ. The rest follows from Lemma 1, all other correct processes eventually schedule label ℓ, and completeness, every process that schedules a label ℓ eventually delivers it. (Hiding) The property directly follows from the algorithm and the privacy property of VE. Let us assume a correct process pi that brbco-schedules a label ℓ. From Corollary 4, we know that enough correct processes jointly have the necessary information to reconstruct m. At this point, the adversary knows only f shares, which by the privacy property of VE, is not enough to learn information about m. Following the algorithm, a correct process pi forwards its share si to all other processes only after n−f collecting more than n+f 2 SCHEDULE messages. Because 2 of those messages are from correct processes, the adversary may gain information about m only after more than n−f 2 correct processes have already brbco-scheduled ℓ, thus effectively after the quorum schedule event QS(ℓ). (Byzantine Causal Delivery) The property directly follows from Lemma 2 and the protocol. The first ensures that, for each correct process, the causal order is preserved at the brbco-schedule. Then, upon scheduling, labels are inserted in the scheduled queue (line 53), and brbco-delivered in the same order in which they are dequeued (line 68).

6

Related Work

The most prominent methods to impose causal-order delivery in the Byzantine model rely on underlying total-order guarantees together with confidentiality from threshold cryptography. Early work dates back decades, starting with Reiter and Birman [32, 8]. It uses threshold ciphers [34] and atomic broadcast tolerating Byzantine faults; later Duan et al. [16] propose more efficient implementations based on secret sharing. Like our protocol, these methods require (at least) one extra round of message exchange for each payload message to be delivered. This line of work has recently been revitalized with batched threshold encryptions schemes [5, 12] that permit to combine the decryption step for multiple messages into one round of message exchange. Malkhi and Szalachowski [27] show how similar techniques seamlessly integrate with DAG-based consensus [19]. 18

More recently, Kelkar et al. [21] have introduced the notion of fair ordering or receive-order fairness that gives ordering guarantees related to causal order, but completely avoiding any use of encryption. Such a fair order should respect the order in which messages appear on the network according to the view of a majority among the correct processes. The notion is also tied to consensus, i.e., it relies on total-order broadcast. A prominent line of work [38, 23, 9, 20] investigates this property in the context of blockchains. However, many proposed solutions employ strong assumptions, such as synchrony or nonoptimal resilience to failures; the resulting properties at the level of message delivery order are weaker than for threshold-cryptography based causal ordering methods. Misra et al. [28, 29, 30] focus on Byzantine-tolerant causal ordering and detection of causality. These works restrict the causality definition to messages sent by correct processes, without trying to capture, as we are doing here, the effects of malicious behavior. This leads to weaker notions of causality. Using similar definitions, Auvolat et al. [3] show how to design a Byzantine causal order broadcast with implementation and security analysis. Kowalski et al. [22] propose a protocol based on mutual broadcast that achieves causal ordering, but only when the sender process is correct. In the shared-memory model, Teng et al. [37] propose an algorithm to preserve causal consistency in the presence of Byzantine servers, but crash-fault clients. This line of work is complementary to ours: it studies how causality constrains reads and writes on shared objects, whereas we focus on messagepassing broadcast primitives. Still, both settings highlight the same core difficulty in the Byzantine model, namely that causality cannot be inferred from the local view of a single participant alone. Sharedmemory protocols typically rely on message-passing primitives or quorum-based validation to order operations, which parallels our use of labels, scheduled vectors, and quorum events to recover a global causal relation from local observations.

7

Conclusion

We introduced Byzantine Reliable Broadcast with Causal Ordering (BRB-CO), a broadcast primitive that satisfies a new notion of causality in the presence of Byzantine processes. BRB-CO separates causality from total order, mirroring the role causal broadcast plays under crash faults but for the Byzantine setting. We are the first to formally define the causal relation required in this setting, state the properties a suitable broadcast channel must satisfy, and give a protocol based on verifiable encapsulation (VE) and Brachastyle broadcast that realizes them. Beyond the specific protocol, the main takeaway is that causal ordering under Byzantine faults can be enforced directly at the broadcast layer, without resorting to total order. This opens the door to broadcast-based services that need concurrency while remaining secure against strong adversaries and dependency-manipulation attacks. Natural directions for future work include more efficient instantiations of the encapsulation primitive, applications that exploit BRB-CO as a modular communication substrate for scalable, concurrent Byzantine systems, and a closer study of how this causal definition relates to existing work on secure causal atomic broadcast.

Acknowledgments This work has been supported by a donation from the Ripple Impact Fund in connection with the University Blockchain Research Initiative (UBRI).

References [1]

O. Alpos, C. Cachin, G. A. Marson, and L. Zanolini. “On the Synchronization Power of Token Smart Contracts”. In: 41st IEEE International Conference on Distributed Computing Systems, ICDCS 2021, Washington DC, USA, July 7-10, 2021. IEEE, 2021, pp. 640–651. DOI: 10.1109/ ICDCS51616.2021.00067.

19

[2]

H. Attiya and J. L. Welch. Distributed computing - fundamentals, simulations, and advanced topics (2. ed.) Wiley series on parallel and distributed computing. Wiley, 2004. ISBN: 978-0-47145324-6.

[3]

A. Auvolat, D. Frey, M. Raynal, and F. Taı̈ani. “Byzantine-tolerant causal broadcast”. In: Theor. Comput. Sci. 885 (2021), pp. 55–68. DOI: 10.1016/J.TCS.2021.06.021.

[4]

K. P. Birman and T. A. Joseph. “Exploiting Virtual Synchrony in Distributed Systems”. In: Proceedings of the Eleventh ACM Symposium on Operating System Principles, SOSP 1987, Stouffer Austin Hotel, Austin, Texas, USA, November 8-11, 1987. Ed. by L. Belady. ACM, 1987, pp. 123– 138. DOI: 10.1145/41457.37515.

[5]

J. Bormet, S. Faust, H. Othman, and Z. Qu. “BEAT-MEV: Epochless Approach to Batched Threshold Encryption for MEV Prevention”. In: 34th USENIX Security Symposium, USENIX Security 2025, Seattle, WA, USA, August 13-15, 2025. Ed. by L. Bauer and G. Pellegrino. USENIX Association, 2025, pp. 3457–3476. URL: https : / / www . usenix . org / conference / usenixsecurity25/presentation/bormet.

[6]

G. Bracha. “Asynchronous Byzantine Agreement Protocols”. In: Inf. Comput. 75.2 (1987), pp. 130– 143. DOI: 10.1016/0890-5401(87)90054-X.

[7]

C. Cachin, R. Guerraoui, and L. E. T. Rodrigues. Introduction to Reliable and Secure Distributed Programming (2. ed.) Springer, 2011. ISBN: 978-3-642-15259-7. DOI: 10.1007/978-3-64215260-3.

[8]

C. Cachin, K. Kursawe, F. Petzold, and V. Shoup. “Secure and Efficient Asynchronous Broadcast Protocols”. In: Advances in Cryptology - CRYPTO 2001, 21st Annual International Cryptology Conference, Santa Barbara, California, USA, August 19-23, 2001, Proceedings. Ed. by J. Kilian. Vol. 2139. Lecture Notes in Computer Science. Springer, 2001, pp. 524–541. DOI: 10.1007/3540-44647-8\_31.

[9]

C. Cachin, J. Micic, N. Steinhauer, and L. Zanolini. “Quick Order Fairness”. In: Financial Cryptography and Data Security - 26th International Conference, FC 2022, Grenada, May 2-6, 2022, Revised Selected Papers. Ed. by I. Eyal and J. A. Garay. Vol. 13411. Lecture Notes in Computer Science. Springer, 2022, pp. 316–333. DOI: 10.1007/978-3-031-18283-9\_15.

[10]

A. Z. Chahoki, M. Herlihy, and M. Roveri. “SoK: Concurrency in Blockchain - A Systematic Literature Review and the Unveiling of a Misconception”. In: CoRR abs/2506.01885 (2025). arXiv: 2506.01885. DOI: 10.48550/ARXIV.2506.01885.

[11]

G. V. Chockler, I. Keidar, and R. Vitenberg. “Group communication specifications: a comprehensive study”. In: ACM Comput. Surv. 33.4 (2001), pp. 427–469. DOI: 10.1145/503112. 503113.

[12]

A. R. Choudhuri, S. Garg, G. Policharla, and M. Wang. “Practical Mempool Privacy via Onetime Setup Batched Threshold Encryption”. In: 34th USENIX Security Symposium, USENIX Security 2025, Seattle, WA, USA, August 13-15, 2025. Ed. by L. Bauer and G. Pellegrino. USENIX Association, 2025, pp. 3477–3495. URL: https : / / www . usenix . org / conference / usenixsecurity25/presentation/choudhuri.

[13]

D. Collins, R. Guerraoui, J. Komatovic, P. Kuznetsov, M. Monti, M. Pavlovic, Y. Pignolet, D. Seredinschi, A. Tonkikh, and A. Xygkis. “Online Payments by Merely Broadcasting Messages”. In: 50th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, DSN 2020, Valencia, Spain, June 29 - July 2, 2020. IEEE, 2020, pp. 26–38. DOI: 10.1109/DSN48063. 2020.00023.

[14]

P. Daian, S. Goldfeder, T. Kell, Y. Li, X. Zhao, I. Bentov, L. Breidenbach, and A. Juels. “Flash Boys 2.0: Frontrunning in Decentralized Exchanges, Miner Extractable Value, and Consensus Instability”. In: 2020 IEEE Symposium on Security and Privacy, SP 2020, San Francisco, CA, USA, May 18-21, 2020. IEEE, 2020, pp. 910–927. DOI: 10.1109/SP40000.2020.00040. 20

[15]

T. D. Dickerson, P. Gazzillo, M. Herlihy, and E. Koskinen. “Adding concurrency to smart contracts”. In: Distributed Comput. 33.3-4 (2020), pp. 209–225. DOI: 10.1007/S00446- 01900357-Z.

[16]

S. Duan, M. K. Reiter, and H. Zhang. “Secure Causal Atomic Broadcast, Revisited”. In: 47th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, DSN 2017, Denver, CO, USA, June 26-29, 2017. IEEE Computer Society, 2017, pp. 61–72. DOI: 10.1109/ DSN.2017.64.

[17]

R. Guerraoui, P. Kuznetsov, M. Monti, M. Pavlovic, and D. Seredinschi. “The consensus number of a cryptocurrency”. In: Distributed Comput. 35.1 (2022), pp. 1–15. DOI: 10.1007/S00446021-00399-2.

[18]

V. Hadzilacos and S. Toueg. “Fault-Tolerant Broadcasts and Related Problems”. In: Distributed Systems (2nd Ed.) Ed. by S. J. Mullender. Expanded version appears as Technical Report TR941425, Department of Computer Science, Cornell University, Ithaca NY, 1994. New York: ACM Press & Addison-Wesley, 1993.

[19]

I. Keidar, E. Kokoris-Kogias, O. Naor, and A. Spiegelman. “All You Need is DAG”. In: PODC ’21: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, July 26-30, 2021. Ed. by A. Miller, K. Censor-Hillel, and J. H. Korhonen. ACM, 2021, pp. 165–175. DOI: 10.1145/3465084.3467905.

[20]

M. Kelkar, S. Deb, S. Long, A. Juels, and S. Kannan. “Themis: Fast, Strong Order-Fairness in Byzantine Consensus”. In: Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, CCS 2023, Copenhagen, Denmark, November 26-30, 2023. Ed. by W. Meng, C. D. Jensen, C. Cremers, and E. Kirda. ACM, 2023, pp. 475–489. DOI: 10 . 1145 / 3576915.3616658.

[21]

M. Kelkar, F. Zhang, S. Goldfeder, and A. Juels. “Order-Fairness for Byzantine Consensus”. In: CRYPTO (3). Vol. 12172. Lecture Notes in Computer Science. Springer, 2020, pp. 451–480.

[22]

V. Kowalski, A. Mostéfaoui, and M. Perrin. “Invited Paper: Causal Mutual Byzantine Broadcast”. In: Proceedings of the 2024 Workshop on Advanced Tools, Programming Languages, and PLatforms for Implementing and Evaluating algorithms for Distributed systems, ApPLIED 2024, Nantes, France, 17 June 2024. Ed. by I. Chatzigiannakis and V. Gramoli. ACM, 2024, pp. 1–8. DOI: 10.1145/3663338.3663679.

[23]

K. Kursawe. “Wendy Grows Up: More Order Fairness”. In: Financial Cryptography and Data Security. FC 2021 International Workshops - CoDecFin, DeFi, VOTING, and WTSC, Virtual Event, March 5, 2021, Revised Selected Papers. Ed. by M. Bernhard, A. Bracciali, L. Gudgeon, T. Haines, A. Klages-Mundt, S. Matsuo, D. Perez, M. Sala, and S. Werner. Lecture Notes in Computer Science. Springer, 2021, pp. 191–196. DOI: 10.1007/978-3-662-63958-0\_17.

[24]

L. Lamport. “Time, Clocks, and the Ordering of Events in a Distributed System”. In: Commun. ACM 21.7 (1978), pp. 558–565. DOI: 10.1145/359545.359563.

[25]

H. Lin, H. Feng, Y. Zhou, and L. Wu. “ParallelEVM: Operation-Level Concurrent Transaction Execution for EVM-Compatible Blockchains”. In: Proceedings of the Twentieth European Conference on Computer Systems, EuroSys 2025, Rotterdam, The Netherlands, 30 March 2025 - 3 April 2025. ACM, 2025, pp. 211–225. DOI: 10.1145/3689031.3696063.

[26]

D. Malkhi and M. K. Reiter. “Byzantine Quorum Systems”. In: Distributed Comput. 11.4 (1998), pp. 203–213.

[27]

D. Malkhi and P. Szalachowski. “Maximal Extractable Value (MEV) Protection on a DAG”. In: Tokenomics. OASIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, 6:1–6:17.

[28]

A. Misra and A. D. Kshemkalyani. “Byzantine Fault-Tolerant Causal Ordering”. In: 24th International Conference on Distributed Computing and Networking, ICDCN 2023, Kharagpur, India, January 4-7, 2023. ACM, 2023, pp. 100–109. DOI: 10.1145/3571306.3571395. 21

[29]

A. Misra and A. D. Kshemkalyani. “Byzantine-Tolerant Causal Ordering for Unicasts, Multicasts, and Broadcasts”. In: IEEE Trans. Parallel Distributed Syst. 35.5 (2024), pp. 814–828. DOI: 10. 1109/TPDS.2024.3368280.

[30]

A. Misra and A. D. Kshemkalyani. “Byzantine-tolerant detection of causality: There is no holy grail”. In: Parallel Comput. 124 (2025), p. 103136. DOI: 10.1016/J.PARCO.2025.103136.

[31]

I. Moraru, D. G. Andersen, and M. Kaminsky. “There is more consensus in Egalitarian parliaments”. In: ACM SIGOPS 24th Symposium on Operating Systems Principles, SOSP ’13, Farmington, PA, USA, November 3-6, 2013. Ed. by M. Kaminsky and M. Dahlin. ACM, 2013, pp. 358– 372. DOI: 10.1145/2517349.2517350.

[32]

M. K. Reiter and K. P. Birman. “How to Securely Replicate Services”. In: ACM Trans. Program. Lang. Syst. 16.3 (1994), pp. 986–1009. DOI: 10.1145/177492.177745.

[33]

F. Ryabinin, A. Gotsman, and P. Sutra. “Making Democracy Work: Fixing and Simplifying Egalitarian Paxos”. In: 29th International Conference on Principles of Distributed Systems, OPODIS 2025, Iaşi, Romania, December 3-5, 2025. Ed. by A. Arusoaie, E. Onica, M. Spear, and S. T. Piergiovanni. Vol. 361. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, 22:1–22:19. DOI: 10.4230/LIPICS.OPODIS.2025.22.

[34]

V. Shoup and R. Gennaro. “Securing Threshold Cryptosystems against Chosen Ciphertext Attack”. In: J. Cryptol. 15.2 (2002), pp. 75–96. DOI: 10.1007/S00145-001-0020-9.

[35]

S. Sridhar, A. Sonnino, and L. Kokoris-Kogias. “Stingray: Fast Concurrent Transactions Without Consensus”. In: CoRR abs/2501.06531 (2025). arXiv: 2501.06531. DOI: 10.48550/ARXIV. 2501.06531.

[36]

C. F. Torres, R. Camino, and R. State. “Frontrunner Jones and the Raiders of the Dark Forest: An Empirical Study of Frontrunning on the Ethereum Blockchain”. In: 30th USENIX Security Symposium, USENIX Security 2021, August 11-13, 2021. Ed. by M. D. Bailey and R. Greenstadt. USENIX Association, 2021, pp. 1343–1359. URL: https : / / www . usenix . org / conference/usenixsecurity21/presentation/torres.

[37]

L. Tseng, Z. Wang, Y. Zhao, and H. Pan. “Distributed Causal Memory in the Presence of Byzantine Servers”. In: 18th IEEE International Symposium on Network Computing and Applications, NCA 2019, Cambridge, MA, USA, September 26-28, 2019. Ed. by A. Gkoulalas-Divanis, M. Marchetti, and D. R. Avresky. IEEE, 2019, pp. 1–8. DOI: 10.1109/NCA.2019.8935059.

[38]

Y. Zhang, S. T. V. Setty, Q. Chen, L. Zhou, and L. Alvisi. “Byzantine Ordered Consensus without Byzantine Oligarchy”. In: 14th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2020, Virtual Event, November 4-6, 2020. USENIX Association, 2020, pp. 633–649. URL: https://www.usenix.org/conference/osdi20/presentation/zhangyunhao.

A

Secure VE instantiations

Instantiating the verifiable encapsulation functionality requires cryptographic mechanisms. In particular, VE must: (i) hide the content of a message before sufficiently many processes trigger release (threshold privacy), (ii) bind one identifier to one cryptographic transcript and therefore to one message (binding), (iii) allow processes to prove that released shares are valid (verifiability), and (iv) guarantee that sufficiently many valid shares reconstruct exactly the same message (correctness and robustness). These properties prevent an adversary from learning or manipulating the content too early. We discuss three concrete instantiations and their trade-offs. • A threshold cipher provides confidentiality under a public key shared by the set of processes. The corresponding secret decryption key is not held by one process; it is split into key shares distributed

22

among processes. Reconstruction is possible only when sufficiently many processes provide valid partial decryptions. In this setting, VE.Encapsulate(m) encrypts m and produces a ciphertext c. For every process pi , the encapsulated value is the same, i.e., ei = c. The identifier is defined as ℓe = H(c), where H is a collision-resistant hash function. Function VE.Validatepi (ℓe , ei ) checks that ei is a well-formed ciphertext and that its hash matches the label. Then, VE.Extractpi (ℓe , ei ) computes a partial decryption share using the secret key share of pi , and VE.Verify(pi , ℓe , si ) verifies the partial decryption share from process pi . Finally, VE.Reconstruct(ℓe , S) combines sufficiently many valid shares to recover m. This instantiation naturally works over authenticated point-to-point channels at the cost of key setup through either a trusted dealer or distributed key generation. • Verifiable secret sharing (VSS) guarantees consistency of shares of one secret distributed among the set of processes, allowing each process to verify that its share corresponds to one committed secret. In this setting, VE.Encapsulate(m) secret-shares m into multiple shares and sends an encapsulated value ei privately to each process pi , together with a commitment ℓe binding all shares to the same secret. Validation through VE.Validatepi (ℓe , ei ) checks the local share against that commitment. Extraction with VE.Extractpi (ℓe , ei ) corresponds to releasing the already-held share, and VE.Verify(pi , ℓe , si ) checks that a share released by another process is consistent with the commitment. Finally, VE.Reconstruct(ℓe , S) recovers m from sufficiently many valid shares. In this instantiation, confidentiality additionally relies on secure point-to-point channels during share distribution. • Publicly verifiable secret sharing (PVSS) provides publicly checkable correctness of the sharing process, so that anyone can verify that revealed shares are consistent with one public transcript. In this setting, VE.Encapsulate(m) runs PVSS sharing on m and outputs a public transcript T and one designated encrypted share per process. The label is derived from the transcript, e.g., ℓe = H(T ). For each process pi , ei is the designated encrypted share for pi in T . Similar to VSS, VE.Validatepi (ℓe , ei ) checks that the designated encrypted share is well-formed with respect to T and that ℓ = H(T ). Then, VE.Extractpi (ℓe , ei ) means that pi decrypts its own share. Verification with VE.Verify(pi , ℓe , si ) publicly checks that the released share of pi is valid under T . Finally, VE.Reconstruct(ℓe , S) combines sufficiently many valid released shares to recover m. This instantiation does not require secure channels, as the public transcript ensures that shares are consistent and valid. However, PVSS schemes are generally more complex and less efficient than VSS or threshold ciphers, both in terms of communication and computation. Threshold ciphers are attractive when confidentiality over public channels is needed and the assumption of a trusted setup is not a limitation. VSS with secure channels is convenient when private channels are already available and a simpler sharing-based construction is preferred. PVSS removes the need for secure channels while preserving public verifiability, at the cost of higher communication and computational complexity than plain VSS.

23