1 Introduction↩︎

State machine replication (SMR) protocols are the foundational building blocks of modern decentralized systems [6]. Under partial synchrony [7], classical solutions like PBFT [1] tolerate up to \(f\) Byzantine replicas among \(n \geq 3f+1\), but require three all-to-all communication delays to reach consensus. As decentralized applications demand ever-lower latency, recent research has introduced two-message-delay protocols (e.g., Minimmit [2]). However, achieving this optimal fast-path latency traditionally requires a much larger committee size of \(n \geq 5f+1\), as every silent replica must be conservatively treated as a potential Byzantine equivocator.

0.6-0.5em*The challenge. To mitigate the severe \(5f+1\) requirement, a natural approach is to distinguish between fully Byzantine faults (who may equivocate) and crash faults (who merely go silent). Recent work like Hydrangea [3] and Kudzu [4] adopt this mixed fault model. However, existing hybrid systems focus on providing a fast-path under optimistic conditions, while eagerly falling back to a slower, PBFT-style 3-round path when faults increase.

This leaves an open challenge: How can we maximize the fault tolerance of the optimal 2-message-delay commit itself when relaxing the fault model? Furthermore, if a client does not care about this lower latency, can we enhance the mixed fault model to provide even stronger, FlexibleBFT-style [5] safety guarantees?

0.6-0.5em*Our solution. In this paper, we answer these questions by formally defining the tight quorum intersections required to maximize 2-message-delay commits under separate Byzantine (\(f\)) and crash-faulty (\(c\)) caps. We show that such a system necessitates: \[n \;\geq\; 5f + 3c + 1\] with an optimal fast-path quorum of \(q = n-f-c\), i.e., \(4f+2c+1\) at the minimal committee size. At \(c=0\), this recovers the familiar \(5f+1\) regime, but when crashes are separated, it allows for configurations with better liveness guarantees.

Building on this foundational result, we introduce Orcaella, a hybrid protocol that exposes two explicit finality paths for clients. These paths are built using Quorum Certificates (QCs)—cryptographic proofs consisting of \(q\) matching signed messages from distinct replicas:

• Optimal Fast-Path (2-delay): Clients can finalize quickly after collecting a single quorum of votes (VoteQC), providing safety against \(f\) Byzantine faults.

• Resilient Path (4-delay): Clients willing to wait for two additional rounds (chaining a CheckpointQC and FinalityQC) gain resilience against an additional \(f_{abc}\) alive-but-corrupt [5] replicas. These are replicas that participate but may equivocate.

Crucially, the resilient path provides safety when the core execution assumptions are violated and forks occur. In executions with at most \(f\) equivocators, the protocol retains its normal liveness behavior. If this regime is violated (e.g., AbC-induced forks), liveness is temporarily lost, replicas enter synchronous recovery, and resilient-path safety remains preserved throughout.

0.6-0.5em*Concrete trade-offs. This dual-path architecture allows operators to explicitly navigate the latency-safety-liveness trade-off. Depending on the expected environment, for a deployment of \(n \approx 100\) replicas, an operator can tune their configuration (1):

• Balanced (\(f=12, c=13\)): Tolerates up to 25 offline replicas for liveness, ensures 1-RTT safety against 12 Byzantine faults, and 2-RTT safety against a maximum of 49 total equivocators (strictly below the intersection bound \(T = 50\)).

• Byzantine-heavy (\(f=16, c=6\)): Optimizing for more malicious conditions slightly reduces liveness tolerance (22 offline replicas) but boosts 1-RTT safety to 16 and 2-RTT safety to a maximum of 54 total equivocators (\(< T = 55\)).

• Crash-heavy (\(f=5, c=25\)): Assuming a more benign but flaky network maximizes liveness (tolerating 30 offline replicas) while still offering 2-RTT safety against a maximum of 40 total equivocators (\(< T = 41\)).

This flexibility allows deployments to adapt to their exact threat models without sacrificing the optimal 2-message-delay commit. Although not the focus of this work, Orcaella can be configured with \(f=0\) and \(n=2c+1\) to provide a CFT variant without any code changes other than configuring the quorums. 12 shows an evaluation of this variant for completeness.

0.6-0.5em*Contributions. We make the following contributions:

1. A characterization of vote-counting protocols with tight quorum inequalities (\(n \geq 5f+3c+1\)) that maximize the fault tolerance of 2-delay BFT consensus (1).

2. Orcaella, a protocol that exposes the 2-delay and 4-delay paths, including a fully specified view change and fork recovery mechanism.

3. FlexibleBFT-style client analyses formalizing the safety vs.liveness trade-offs and proving the 4-delay path remains safe against an additional \(f_{abc} < n - 3f - 2c\) alive-but-corrupt faults.

4. OrcDAG, a DAG-based instantiation of Orcaella over an uncertified-DAG fabric, and its evaluation on realistic deployment quantifying the latency gained by trading fault tolerance.

2 Network and Fault Model↩︎

We use standard message-passing state machine replication [8] among \(n\) replicas (the leader or primary proposes each slot) under partial synchrony [7]. Channels are authenticated; digital signatures identify senders. Each replica is in exactly one of four disjoint classes:

• Byzantine (at most \(f\)) replicas, which may crash or send arbitrary messages including equivocations (inconsistent signed statements to different recipients) on any protocol message;

• Crash-faulty (at most \(c\)) replicas, which follow the protocol while active and may then permanently stop sending messages without equivocating;

• Alive-but-Corrupt (AbC, at most \(f_{abc}\)) replicas, which represent a separate client-side threat model used only for the Resilient Path analysis, where they may equivocate on any protocol message—votes and checkpoint proposals alike—and can thus cause VoteQC forks, whereas in the core Fast-Path execution model and liveness analysis, AbC behavior is not activated and only up to \(f\) replicas may equivocate;

• Correct replicas, which remain honest and live throughout the execution under consideration, assuming \(n-f-c\) correct replicas for Fast-Path safety/liveness (core protocol) and \(n-f-c-f_{abc}\) correct replicas for Resilient Path client-side safety under AbC assumptions.

The standard partial synchrony network model [7] assumes that after an unknown Global Stabilization Time (GST), message delays between correct replicas are bounded by a known constant \(\Delta\). The adversary controls all non-honest replicas up to the misbehavior they are allowed to perform and the network scheduling (subject to this bound after GST). It cannot break cryptography.

3 The Orcaella Protocol↩︎

This section instantiates the fault model and Fast-Path/Resilient Path split from 2 into a message-level protocol. It uses the thresholds derived in 1: \(n \geq 5f+3c+1\) and \(q = n-f-c\) (equal to \(4f+2c+1\) at the minimal \(n\)). Replicas communicate on authenticated channels under partial synchrony. The protocol proceeds in views \(v \in \mathbb{N}\), each with a designated leader \(\mathrm{\small Leader}(v)\), and assigns proposals to sequence numbers \(s \in \mathbb{N}\).

3.1 The protocol↩︎

[alg:protocol] specifies the protocol, covering both normal operation and leader recovery. Normal operation is divided into a Fast-Path (Steps 0–1, ) that guarantees safety against \(f\) Byzantine faults in two message delays, and a Resilient Path (Steps 2–4, ) that provides extended safety against alive-but-corrupt (AbC) faults at the cost of two additional message delays.

0.6-0.5em*Client finalization paths. Clients finalize transactions by observing the certificates produced by the protocol. The latency bounds stated in this paper (e.g., two or four message delays) assume that clients are collocated on the replicas participating in the consensus protocol. If clients are external, their perceived finality latency naturally increases by the round-trip time (RTT) to communicate with the replica set, as is standard in all BFT protocols.

• Fast-Path (2-delay): A client finalizes \((v,s,h)\) immediately upon collecting a VoteQC. This provides optimal latency and safety against \(f\) Byzantine faults.

• Resilient Path (4-delay): A client finalizes \((s,h,\sigma)\) upon obtaining a FinalityQC(output by a replica in Step 4, [step:4]) together with its underlying CheckpointQC. This trades higher latency for extended safety against an additional \(f_{abc}\) alive-but-corrupt faults, without interfering with the core protocol’s liveness [5].

0.6-0.5em*Protocol description. The leader of view \(v\) proposes a batch of transactions. Replicas validate the proposal and cast an accept vote, but only if the proposal is consistent with the branch \(\mathcal{O}\) adopted from the latest NewView ([step:1]); this guard is what carries Fast-Path commits across view changes (3). Correct replicas send at most one vote per slot \((v,s)\). If a client gathers \(q\) such accept votes, it forms a VoteQC and can immediately safely execute the payload (Fast-Path). If the leader is faulty [9] or the network is asynchronous, replicas eventually timeout and broadcast ViewChange messages, which collectively serve as an implicit abandon for uncommitted slots.

To support the Resilient Path, replicas that observe a VoteQC compute the resulting deterministic state root \(\sigma\) and broadcast a checkpoint proposal. We assume state roots bind the execution history: \(\sigma_s\) commits to the previous root and the applied digest (e.g., \(\sigma_s = H(\sigma_{s-1} \,\Vert\, h)\)), so a root at height \(s\) determines the checkpointed content at every height below it. Safety is strictly guarded by Step 2 ([step:2]): to prevent conflicting checkpoints, an honest replica broadcasts at most one ChkProp per slot height. For this reason, checkpoint artifacts deliberately carry no view number: a slot’s VoteQC may form in view \(v\) at one replica and in a later view \(v'\) at another (with the same digest, by Fast-Path safety), and view-tagged ChkProps would split each replica’s single permitted proposal across views, permanently blocking the checkpoint. While this strict locking rule means liveness can be lost if honest replicas split their ChkProp messages across different branches (a trade-off we explicitly accept), it provides an ironclad safety guarantee. Once \(q\) replicas agree on this checkpoint (forming a CheckpointQC), they lock it by broadcasting a ChkWitness message. Note that ChkWitness messages attest to the checkpoint content \((s,h,\sigma)\) rather than to one specific certificate: two CheckpointQCs over the same content but different signer sets may circulate, and binding witnesses to a particular certificate would needlessly split them. To safely support a checkpoint, an honest replica will broadcast a ChkWitness as long as the checkpoint’s state \(\sigma\) matches its own deterministic execution of the payload (\(\sigma = \mathrm{\small Apply}(h)\)), even if its single permitted ChkProp for that height was already spent on a different, unfinalized branch. Once \(q\) such witness messages are collected, a replica outputs a FinalityQC(Step 4, [step:4]) as its Resilient Path finality decision for that slot.

Notice that with \(f_{abc}\) alive-but-corrupt faults, there can be VoteQC forks across different views. However, because honest replicas only broadcast a single ChkProp per height, the double-signing bound (4) guarantees that at most one valid CheckpointQC can ever be formed per height. Any resulting loss of liveness on the Resilient Path is cleanly resolved by the Fork Recovery protocol ([alg:fork95recovery]) during a synchronous epoch. Steps 2–4 () ensure that this single CheckpointQC is witnessed by the network and the resulting FinalityQC is propagated before resilient finalization. Notice that every protocol artifact (VoteQC, CheckpointQC, FinalityQC) uses the exact same quorum threshold \(q\).

0.6-0.5em*View-Change details. The view change protocol is structurally similar to both PBFT and modern protocols like Streamlet [10] or HotStuff [11], [12]. If \(\mathrm{\small Leader}(v+1)\) fails to assemble a valid NewView before a timeout, replicas re-issue ViewChange messages for view \(v+2\) with doubled timeouts, following standard view synchronization [1]. Assuming the core limit of \(f\) Byzantine faults holds (i.e., there are no VoteQC forks), any two sets of \(q\) ViewChange messages intersect at an honest replica (\(2q - n > f\)). This guarantees that any VoteQC used by a client to finalize a Fast-Path commit is reported to the new leader and preserved in the new view’s starting state \(\mathcal{O}\). Since replicas may re-vote for the same digest across views, the leader counts the reported votes per digest rather than per view (3). By operating over a large \(5f+1\) style quorum, the protocol acts as a generalized 2-chain Streamlet, enabling rapid 2-message-delay finality instead of the standard 3-chain required under \(3f+1\). If the \(f\) limit is exceeded (e.g., by AbC faults double-voting) and a VoteQC fork occurs, Fast-Path safety is broken and preserving it is no longer required; instead, replicas halt and rely on Fork Recovery to salvage the Resilient Path. Note that for simplicity, [alg:protocol] requires replicas to send all their highest-view votes. In a practical implementation, replicas would use CheckpointQCs to prove a globally agreed upon state and safely truncate the required vote history, significantly reducing the size of ViewChange messages [13].

3.2 Fork recovery↩︎

[alg:fork95recovery] specifies the procedure for detecting and recovering from forks (when the core \(f\) Byzantine limit is exceeded but clients rely on Resilient Path safety).

0.6-0.5em*Synchronous network model. Unlike normal operation which relies on partial synchrony, this recovery procedure operates under a strictly synchronous network model. We assume that message delays between correct replicas are guaranteed to be bounded by a known, pessimistic constant \(\Delta_{\mathrm{sync}}\). Replicas anchor the epoch’s lockstep round structure at the delivery of the first valid Alarm (which every correct replica re-broadcasts), so the round boundaries of correct replicas are offset by at most \(\Delta_{\mathrm{sync}}\)—a bounded skew that synchronous broadcast protocols tolerate by standard techniques [14].

0.6-0.5em*Fork recovery details. While the core protocol naturally resists up to \(f\) fully Byzantine faults, Resilient Path clients may additionally assume \(f_{abc}\) alive-but-corrupt replicas. These replicas behave correctly during normal operation but might double-sign conflicting ChkProp messages to intentionally cause forks.

However, because honest replicas only broadcast a single ChkProp per height, the double-signing bound (4) explicitly prevents the \(f_{abc}\) alive-but-corrupt replicas from successfully forming two conflicting CheckpointQCs. Thus, there can be at most one valid CheckpointQC per height.

If a VoteQC fork occurs (exceeding the core \(f\) Byzantine limit), correct replicas immediately detect it via cryptographic evidence, halt normal operation, and force a global repair by broadcasting an Alarm. Upon entering this synchronous recovery epoch, every replica initiates its own Byzantine Broadcast instance (such as Dolev-Strong [15]), \(n\) in parallel, to reliably exchange all locally known CheckpointQCs and VoteQCs; correct replicas then operate on the union of the delivered sets. Because Dolev-Strong does not rely on an honest majority, it guarantees that all correct replicas will output the exact same set of valid certificates, even if the total number of faulty replicas (\(f + f_{abc}\)) constitutes a dishonest majority (\(>n/2\)). However, if the deployment guarantees that \(f + f_{abc}\) remains a strict minority (\(<n/2\)), this recovery step can be significantly optimized by deploying an honest-majority synchronous broadcast protocol that terminates much faster than Dolev-Strong’s \((f+f_{abc})+1\) rounds (e.g., expected constant-round protocols [16] or practical synchronous SMR implementations like Sync HotStuff [14]). When the broadcast protocol completes, replicas collect all delivered CheckpointQCs across all slots. Because there is at most one per height and checkpoints are chain-consistent across heights (4 5), they form a single, non-conflicting history. Replicas simply identify the highest CheckpointQC and adopt its branch as canonical, extending it with any arbitrary valid VoteQCs for subsequent slots. If no CheckpointQC was ever formed, they can safely choose either valid VoteQC branch. This guarantees that Resilient Path safety remains unbroken.

4 Safety and Liveness Proofs↩︎

We show that Orcaella satisfies safety and liveness under the network and fault model defined in 2. Throughout, the quorum threshold is \(q = n-f-c\) and the view-change accept threshold is \(k = 2f+c+1\); at the minimal committee size \(n = 5f+3c+1\), \(q = 4f+2c+1\). We derive both thresholds directly through these proofs, ensuring a rigorous foundation for the optimal \(n \ge 5f+3c+1\) bound.

We say a protocol is vote-counting if it (i) finalizes a digest on the Fast-Path upon \(q\) matching first-round votes, and (ii) recovers from leader failure through a view change in which the new leader re-proposes a digest if and only if it appears in at least \(k\) of the highest-view vote reports embedded in \(q\) ViewChange messages \(\mathcal{V}\).

4.1 Quorum intersection and Fast-Path safety↩︎

4.2 View-Change safety↩︎

To guarantee that a finalized Fast-Path commit is never overwritten by a subsequent leader, the View-Change protocol must enforce that any newly proposed branch \(\mathcal{O}\) preserves previously committed digests. This is achieved via the view-change accept threshold \(k = 2f+c+1\).

4.3 Liveness↩︎

4.4 Resilient Path and fork recovery safety↩︎

The Resilient Path provides an extended safety guarantee against an adversary capable of breaking the core \(f\) Byzantine limit by leveraging up to \(f_{abc}\) alive-but-corrupt replicas.

4 rules out conflicts at a single height. To safely adopt the highest checkpoint during recovery, we additionally need checkpoints at different heights to agree on their common prefix. Recall (3) that state roots bind history: \(\sigma_s\) commits to \(\sigma_{s-1}\) and the applied digest.

5 OrcDAG: A DAG-Based Implementation↩︎

[sec:model,sec:proofs] are independent of how proposals are represented: safety uses first-round votes and the thresholds \(q\) and \(k\) of the vote-counting template (1). The Orcaella protocol (3) uses \(q\) for every certificate round. Many high-throughput systems nonetheless realize the same logic over a directed acyclic graph of blocks or vertices, with edges for dependencies and leaders extending a frontier of the DAG [17]–[24]. We present OrcDAG, a dag-based instantiate of Orcaella.

A DAG vertex (block) plays the role of the primary’s proposal for a slot; a replica issues accept/reject once its local validity rules (including dependency checks) hold. The key idea of OrcDAG is that a vote is not a separate signed message but a causal edge: a round \(R+1\) block votes for a block \(B\) precisely when its causal history includes \(B\) (the Vote of [alg:dag]), and blames \(B\) when it does not (the Blame of [alg:dag]). The DAG structure itself carries the first-round votes, so no explicit vote messages are needed even though the DAG is uncertified. The Direct Decision Rule of [alg:dag] realizes the Fast-Path: collecting \(q\) agreeing first-round votes is exactly \(\geq q\) distinct round \(R+1\) authors voting for \(B\), using the same quorum \(q = n-f-c\) from 1; symmetrically, \(q\) blames force a Skip.

The Indirect Decision Rule of [alg:dag] realizes the View-Change. The “later authenticated artifact” of the abstract protocol Orcaella is concretely a committed anchor \(A\) at a round \(\geq R+2\): because reachability in the DAG certifies the votes enclosed in its causal past, \(A\) linking to \(\geq k\) distinct round \(R+1\) authors that vote for \(B\) plays the role of the embedded vote reports in the view change of 3, with the accept threshold \(k = 2f+c+1\). This single anchor object subsumes the abstract alternatives—such as a commit certificate on a descendant, a checkpoint quorum, or a bundle hashing prior votes—as all collapse to the anchor’s causal history, which reachability certifies without any separate certificate. The choice of \(k\) is exactly what the Reachability, Exclusivity, and Liveness conditions of 4 require for safe indirect commits.

9 provides detailed algorithms to formally define OrcDAG.

6 Evaluation↩︎

OrcDAG is a DAG-based instantiation of Orcaella that we implement and benchmark, built in Rust as a fork of Mysticeti [25]. 10 details its implementation and testing methodology.

6.1 Evaluation scope↩︎

Our evaluation has a single goal: quantify the latency we gain by trading away fault tolerance, i.e., by moving from the optimal \(n=3f+1\) three-message-delay fault budget to Orcaella’s \(n=5f+3c+1\) two-message-delay design space. Put differently: what latency do we gain by giving up the fault tolerance represented by the orange wedge of 1 (1)? This is not trivial. A naive observer might expect a direct 33% latency reduction simply from cutting one of the three commit rounds. But two factors complicate the picture: (1) Orcaella needs a larger quorum of replicas per round than a typical \(n=3f+1\) protocol; and (2) the saved round only reduces commit latency (from block proposal to commit), not queuing latency (from transaction submission to block proposal).

Our evaluation makes the following claims:

• C: OrcDAG’s lower latency is bought with fault tolerance alone, not throughput.

• C: Under benign crash faults, OrcDAG degrades gracefully, retaining its throughput and low latency.

• C: OrcDAG’s latency reduction over the \(n=3f+1\) baseline is load-dependent, ranging from \({\sim}24\%\) at low load to \({\sim}14\%\) at high load due to its larger quorum and queuing delay.

• C: OrcDAG’s commit latency is independent of how the fault budget splits between \(f\) and \(c\) in a typical geo-distribution, and a split budget deploys at strictly smaller \(n\) than the pure-Byzantine \(5f+1\) (\(c=0\)) point.

• C: Geo-distribution is decisive: OrcDAG’s latency advantage holds when all protocols operate over the same geo-locations, but is negated when the baseline’s smaller quorum can exclude a remote region that OrcDAG’s larger quorum cannot.

Benchmarking BFT protocols under actual Byzantine behavior is an open problem [26], [27]; the state of the art establishes worst-case guarantees through formal proofs, which we give in 4.

6.2 Experimental setup↩︎

To demonstrate these claims, we deploy four OrcDAG configurations spanning the fault-budget spectrum (2): Byzantine-only (\(f{=}10,c{=}0\)), Byzantine-heavy (\(f{=}8,c{=}3\)), Balanced (\(f{=}6,c{=}6\)), and Crash-heavy (\(f{=}2,c{=}13\)). We use two baselines: (i) Mysticeti [19], the closest \(n=3f+1\) protocol to OrcDAG in terms of both design and implementation, representing the standard 3-round PBFT-style baseline; (ii) Hydrangea [3], an alternative hybrid \((f,c)\) design with \(n=3f+2c+k+1\) that can commit in a single round-trip (via an optimistic path) and is, to our knowledge, the only other protocol in this design space with a deployable implementation. The pure-Byzantine \(c=0\) point (an \(n=5f+1\) deployment) is itself an OrcDAG configuration, which we include as an additional reference rather than as a separate system.

Several recent protocols explore designs in the same neighborhood (7), including Minimmit [2], Kudzu [4], and Alpenglow [28]. None of these provide deployable implementations with networking code; their codebases are intended for simulation only and are therefore excluded from our WAN measurements. The remaining systems, Mysticeti and Hydrangea, both have mature deployable implementations and serve as our baselines. We configure Hydrangea at \(f{=}9\), \(c{=}10\), \(k{=}2\) for the \(n{=}50\) committee; in this regime it tolerates more crash faults than OrcDAG, but, being built atop HotStuff, it inherits the data-dissemination bottleneck identified by Narwhal [17].

Unless stated otherwise, we emulate a typical blockchain replica distribution [29], [30]: a fast quorum region (EU-US) plus a remote tail (Tokyo). We report median (p50) commit latency with p90 whiskers. 11 describes the precise geo-distribution and testbed details used in this section. In all graphs, latency refers to the time elapsed from the moment a client submits a transaction to when it is committed by the replicas, and throughput refers to the number of (512 bytes) transactions committed per second.

6.3 Throughput vs.fault tolerance trade-off↩︎

3 evaluates a roughly \(50\)-replica WAN deployment under failure-free conditions. The throughput of OrcDAG matches Mysticeti, which is expected as both build upon the same uncertified-DAG fabric, corroborating related work [17]. For cost reasons, we cap the offered load at \(100{,}000\) tx/s, which is two orders of magnitude above the peak throughput of existing blockchains and ample to stress the systems [31]. This confirms claim [claim:c1]: OrcDAG is realizable without sacrificing throughput. Hydrangea performs significantly worse at scale (red line in 3). At \(50\) replicas, its latency exceeds the plotted range even under minimal load, demonstrating that it does not scale gracefully to large committees. This limitation stems from its HotStuff-style data-dissemination mechanism, consistent with findings reported in related work [17].

The figure also shows that OrcDAG commits at lower latency than Mysticeti; we dissect this latency–fault-tolerance trade-off in 6.5.

6.4 Impact of benign crash faults↩︎

4 shows OrcDAG, Mysticeti, and Hydrangea under benign crash faults in committees of approximately \(10\) replicas. The DAG-based systems sustain the offered load with a graceful latency inflation relative to the fault-free runs, absorbing crashes by quickly skipping crashed leaders via the direct skip rule (5). Each system runs at the minimal committee for this fault budget—Mysticeti at \(n{=}7\) (\(f{=}2\)), OrcDAG at \(n{=}9\) (\(f{=}1,c{=}1\)), and the \(c{=}0\) reference at \(n{=}11\) (\(f{=}2\))—so every committee operates at its maximum fault load. At these minimal committees, OrcDAG matches its own \(c=0\) point because crashed replicas count against \(c\) rather than \(f\) and so do not consume the Byzantine budget (the \(n{=}9\) hybrid and the \(n{=}11\) \(c{=}0\) reference commit in \(379\) and \(394\) ms). This split remains latency-neutral while delivering a latency win over Mysticeti: at low load (\(10{,}000\) tx/s) OrcDAG commits in \(378\) ms versus \(492\) ms (a \({\sim}23\%\) reduction), and near the high-load cap (\(50{,}000\) tx/s) \(395\) ms versus \(567\) ms (a \({\sim}30\%\) reduction). This confirms claim [claim:c2]. Hydrangea’s latency exceeds the plotted range, confirming it does not tolerate faults gracefully, corroborating related work [17]. These small committees represent the worst case for the fault budget: a crash removes a large fraction of a \(10\)-replica committee but a negligible fraction of a \(50\)-replica one.

6.5 Understanding the latency trade-off↩︎

We zoom into 3 to understand OrcDAG’s latency–fault-tolerance trade-off. At \(100{,}000\) tx/s, OrcDAG commits in \(330\) ms (p50) versus \(382\) ms for Mysticeti, a \({\sim}14\%\) reduction; at low load (\(10{,}000\) tx/s) the gap widens to \(282\) ms versus \(367\) ms, a \({\sim}23\%\) reduction. All OrcDAG configurations, including the \(c{=}0\) (\(5f{+}1\)) reference, fall within \({\sim}12\) ms of one another. A naive view expects the move from three to two message delays to give a \({\sim}33\%\) latency reduction. Two coupled effects erode this: (1) OrcDAG uses a larger quorum (\({\sim}80\%\) of replicas versus \({\sim}67\%\) for Mysticeti); (2) per-replica queuing under load. The two are coupled: queuing widens the latency distribution, and the larger quorum must wait on a higher percentile of that distribution.

5 reports per-protocol latency at low load (\(10\)k tx/s), which isolates the quorum-width effect (1) because queuing is negligible. Here, a \({\sim}20\)–\(25\%\) reduction holds for all OrcDAG configurations. 6 adds high load (\(100\)k tx/s), introducing effect (2). Per-replica queuing is the same for all protocols, but OrcDAG’s larger quorum amplifies its impact on commit latency (OrcDAG adds \(+43\)–\(49\) ms versus \(+15\) ms for Mysticeti). As a result, the reduction erodes by about \(10\) percentage points, from \({\sim}24\%\) to \({\sim}14\%\) as load grows from \(10\)k to \(100\)k tx/s, and it does so similarly across all \((f,c)\) splits. 7 summarizes this by plotting the total latency reduction over Mysticeti against load, capturing both effects, and confirms claim [claim:c3]: OrcDAG’s latency reduction ranges from \({\sim}24\%\) to \({\sim}14\%\) depending on load.

6.6 The role of quorum location↩︎

[fig:bars-10k,fig:bars-100k] show that, across OrcDAG configurations, commit latency is not ordered by quorum size. All configurations commit in two message delays over the same uncertified-DAG structure, so in a fault-free run their finalization latencies are effectively indistinguishable regardless of how the fault budget splits between \(f\) and \(c\). This confirms claim [claim:c4]: OrcDAG pays no performance penalty for the hybrid-fault analysis, and a split budget deploys at strictly smaller \(n\) than the pure-Byzantine \(5f+1\) (\(c=0\)) point. Concretely, the configurations cluster at \(281\)–\(293\) ms at low load and \(329\)–\(341\) ms at high load, versus \(367\) and \(382\) ms for Mysticeti; the \(c=0\) (Byzantine-only) point, which has the largest quorum (\(q{=}41\)), is among the fastest, so the \({\sim}12\) ms spread is run-to-run measurement noise (WAN and egress jitter). Crucially, this neutrality is conditional. The split sets the fast-path quorum size \(q=4f+2c+1\): a Byzantine-leaning split carries a larger quorum (\(q{=}41\) for Byzantine-only) than a crash-leaning one (\(q{=}35\) for Crash-heavy). The configurations are latency-neutral only because, in this graceful geo-distribution, all of these quorums still form within the fast region.

8 shows what happens when the quorum is forced out of the fast region. We use crash faults on minimal committees (\(2\) crashes) to force the quorum to include a remote region (Tokyo). When every protocol must reach Tokyo, Mysticeti is penalized more because its extra (third) round waits on the remote replica once more than OrcDAG. But when Mysticeti’s larger fault-tolerance budget gives it enough slack to exclude Tokyo while OrcDAG’s tighter quorum cannot, the advantage reverses. Concretely, Mysticeti with \(f{=}3\) (\(n=10\)) keeps slack and excludes Tokyo (\(327\) ms), whereas OrcDAG with \(f{=}1,c{=}1\) (\(n=9\)) and Mysticeti with \(f{=}2\) (\(n=7\)) have no slack and must include Tokyo (\(378\) ms and \(492\) ms). So OrcDAG beats the minimal Mysticeti (two rounds versus three) but loses to the over-provisioned Mysticeti that dodges Tokyo. This confirms claim [claim:c5]. The same mechanism bounds claim [claim:c4]: under a less graceful geo-distribution, a Byzantine-leaning configuration’s larger quorum (\(q{=}41\)) could be forced to include the slow region while a crash-leaning one (\(q{=}35\)) avoids it, at which point the split would no longer be latency-neutral. Both claims therefore hold only while the quorum stays within the fast region.

7 Related Work↩︎

0.6-0.5em*Hybrid fault models. The formal separation of Byzantine and benign faults was first explored by Thambidurai and Park [32] for interactive consistency. While their work demonstrated that protocols can achieve higher resilience by not treating all failures as worst-case Byzantine, it did not address the latency limitations of state machine replication (SMR). Later pragmatic systems like UpRight [33] and XFT [34] applied this separation to cluster architectures. However, UpRight focuses on end-to-end service robustness rather than theoretical latency minimums, and XFT opportunistically tolerates Byzantine faults only when an honest majority communicates synchronously. In contrast, our work fundamentally re-examines the quorum intersections of SMR under partial synchrony, specifically optimizing for the minimal 2-message-delay commit path while treating \(f\) and \(c\) as distinct variables.

0.6-0.5em*Low-latency SMR and \(5f{+}1\) protocols. The demand for ultra-low latency in decentralized networks has driven recent protocols—such as Kudzu [4], Minimmit [2], and Alpenglow [28]—to instantiate optimal two-round decision paths. However, these systems rely on a pure counting model that conservatively requires \(n \geq 5f+1\), treating any offline replica as a potential equivocator. Hydrangea [3] introduces a hybrid \((f,c)\) analysis requiring \(n = 3f+2c+k+1\), but it focuses on providing a fast-path under optimistic conditions that falls back to a slower 3-round path when faults increase. At the limit of Hydrangea it can be instantiated with \(k=2f+c-3\)resulting in \(n=5f+3c-2\), which allows for a two-round commit path with \(p=f+c-2\). Unlike these approaches, we prove that \(n = 5f+3c+1\) is necessary for any protocol that commits in two message delays from a single vote quorum and recovers via a vote-counting view change (1), and sufficient via Orcaella—eliminating the need for fallback paths and explicitly separating the cost of crash faults from Byzantine faults. Our choice allows us to also provide a resilient path for clients to tolerate an additional \(f_{abc}\) equivocators at the cost of two extra message delays, without ever degrading the core protocol’s optimal liveness, but results in lower fast-path liveness gurantees than Hydrangea.

0.6-0.5em*Client-side safety and Alive-but-Corrupt faults. FlexibleBFT [5] introduced the concept of alive-but-corrupt (\(f_{abc}\)) faults, cleanly separating replica-quorum liveness assumptions from client-visible safety guarantees. While FlexibleBFT primarily uses this slack to separate synchronous and asynchronous network assumptions, we apply it directly to the 2-delay quorum framework. Unlike existing systems that force all clients to accept the same latency-security trade-off, our dual-path architecture explicitly empowers clients. By chaining CheckpointQCs, our Resilient Path allows clients to tolerate an additional \(f_{abc}\) equivocators at the cost of two extra message delays, without ever degrading the core protocol’s optimal liveness. Orthogonally, a line of low-latency payment systems—FastPay [35], Zef [36], and Stingray [37]—forgoes consensus entirely for single-owner transactions, trading general programmability for latency; Orcaella instead retains full SMR while minimizing the commit path.

8 Conclusion↩︎

We explored the fundamental limits of achieving optimal 2-message-delay consensus under a hybrid fault model. By cleanly separating Byzantine faults (\(f\)) from crash faults (\(c\)), we derived tight quorum intersections requiring \(n \geq 5f+3c+1\) with an optimal Fast-Path threshold of \(q = n-f-c\) (\(4f+2c+1\) at the minimal committee size). This allows modern decentralized systems to relax the severe liveness requirements associated with pure \(5f+1\) protocols without sacrificing latency.

Building upon these thresholds, we introduced Orcaella, a dual-path consensus protocol that explicitly exposes a latency-safety trade-off to clients. Clients requiring ultra-low latency can finalize in two message delays via the Fast-Path (relying on VoteQCs), while clients prioritizing safety can wait four message delays for the Resilient Path (chaining CheckpointQCs and FinalityQCs). By enforcing a strict single-proposal rule for checkpoints, the Resilient Path guarantees safety against an extended set of \(f_{abc}\) alive-but-corrupt replicas. If the core \(f\) threshold is ever breached, the system safely halts and employs an Authenticated Byzantine Broadcast recovery mechanism to deterministically salvage the Resilient Path.

Finally, we demonstrated the practical applicability of our results by showing how they seamlessly map onto state-of-the-art DAG-based architectures. Future work includes extending these hybrid threshold derivations to fully asynchronous consensus environments and developing formal economic models to dynamically adjust \(f\), \(c\), and \(f_{abc}\) budgets during live deployments.

Acknowledgements↩︎

This work is partially funded by Mysten Labs.

9 Detailed Algorithms for the DAG-Based Variant↩︎

This appendix complements 5 by formally defining the commit logic of OrcDAG, the DAG-based variant of Orcaella, through detailed algorithms.

0.6-0.5em*DAG-building layer. We assume the underlying DAG-building logic of Mysticeti [19]: replicas proceed in logical rounds; in each round every honest replica proposes one block referencing \(\geq q\) distinct valid blocks from the previous round; blocks are disseminated to others; only blocks whose entire causal history has been validated are stored locally. The decision logic specified here operates on this local DAG and is independent of how blocks reach the replica.

0.6-0.5em*Entry point and idempotency. 9 is the commit-logic entry point. Inline with related work [19], [21], it is idempotent and stateless from the DAG engine’s perspective: the engine may invoke it whenever it likes, typically upon receiving and integrating a new block, passing the highest round currently in the local DAG (\(r_{highest}\)) and the round of the last block already committed (\(r_{committed}\)). The procedure returns the extension to the commit sequence (possibly empty) that the engine should append to its committed prefix. The entry point is , which internally calls to evaluate each undecided leader slot using the rules in 10, then linearises the causal sub-DAG of every newly committed leader (as introduced by DAG-Rider [38]). 10 specifies the per-slot decision process and with the supporting helper procedures (, , ).

10 Implementation↩︎

We implement a networked, multi-core OrcDAG replica in Rust by forking the Mysticeti codebase [25], [31]. Our implementation leverages tokio [39] for asynchronous networking, utilizing raw TCP sockets for communication without relying on any RPC frameworks. For cryptographic operations, we rely on ed25519-consensus [40], [41] for asymmetric cryptography and blake2 [42] for cryptographic hashing. To ensure data persistence and crash recovery, we employ a Write-Ahead Log (WAL). The WAL optimizes I/O operations through vectored writes [43] and efficient memory-mapped file usage with the minibytes [44] crate, minimizing data copying and serialization. In addition to regular unit tests, we inherit and use two supplementary testing utilities from the Mysticeti codebase. First, a simulation layer replicates the functionality of the tokio runtime and TCP networking; the simulated network reproduces realistic WAN latencies, while the tokio runtime simulator employs a discrete-event simulation approach to model the passage of time. Second, a command-line utility (called the orchestrator) [17], [18] deploys real-world clusters of OrcDAG replicas on machines distributed across the globe. We open-source our OrcDAG implementation, along with its simulator and orchestration tools, to ensure reproducibility of our results¹.

11 Testbed Details↩︎

This appendix complements 6 by detailing the testbed and experimental setup used to evaluate OrcDAG.

We deploy all protocols on AWS, using m5d.8xlarge instances across \(6\) different AWS regions: Northern Virginia (us-east-1), Ohio (us-east-2), Frankfurt (eu-central-1), London (eu-west-2), Paris (eu-west-3), and Tokyo (ap-northeast-1). Replicas are distributed across those regions as equally as possible. Each machine provides \(10\) Gbps of bandwidth, \(32\) virtual CPUs (16 physical cores) on a \(3.1\) GHz Intel Xeon Skylake 8175M, \(128\) GB memory, and runs Linux Ubuntu server \(24.04\).

We instantiate several geo-distributed benchmark clients within each replica submitting transactions in an open-loop model at a fixed rate. We experimentally increase the load of transactions sent to the systems, and record the throughput and latency of commits. As a result, all plots in 6 illustrate the steady-state latency of all systems under low load, as well as the maximal throughput they can provide after which latency grows quickly. Transactions in the benchmarks are arbitrary and contain \(512\) bytes. We configure Orcaella and Mysticeti with \(2\) leaders per round, and all protocols use a leader timeout of \(1\) second.

12 Crash-Only Deployment↩︎

When configured with \(f=0\) to tolerate only crashes and no Byzantine faults, Orcaella reduces to an optimal crash-fault-tolerant (CFT) protocol [45]. 11 reports the performance of OrcDAG configured with \(f=0\) and \(c=1\) in a minimal \(n=3\) deployment, where the three replicas run in three distinct, nearby European regions—Frankfurt (eu-central-1), Ireland (eu-west-1), and London (eu-west-2)—to model a regional CFT deployment. The plot shows two loads, \(1\)k and \(10\)k tx/s. Each box spans the mean \(\pm\) \(1\) standard deviation, and the whiskers denote \(\pm\) \(2\) standard deviations. In this lightly-loaded regime the commit latency is load-independent and essentially flat: OrcDAG commits with a mean latency of about \(22\) ms at \(1\)k tx/s and about \(23\) ms at \(10\)k tx/s, with a standard deviation of about \(7\) ms. This is roughly two orders of magnitude below the hundreds of milliseconds observed in the geo-distributed WAN runs of the main evaluation (6), highlighting the best-case latency of a regional crash-tolerant deployment.

References↩︎

---

1. https://github.com/asonnino/mysticeti (commit 96dee8d)↩︎