1 Introduction↩︎

Directed Acyclic Graph (DAG)-based protocols aim to provide a Byzantine Fault Tolerance (BFT) replicated ledger, or blockchain, abstraction, i.e., to maintain a consistent total order of transactions across distributed validators, even in the presence of malicious and faulty nodes [1]–[12]. DAG-protocols are claimed to offer higher throughput even under asynchrony and failures compared to classical leader-based protocols. However, many DAG protocols suffer from high latency. Mysticeti is a recent DAG-based BFT protocol that can achieve the latency lower bound of three message delays and maintains low latency even in the presence of certain crash failures. As an indication of its practical relevance, Mysticeti has been recently adopted by both the Sui and IOTA blockchains.

Interestingly, it was shown that BFT consensus can be accelerated with a fast path, which allows validators to commit values in just two message delays under favorable conditions. This matches the optimal latency achievable in crash fault-tolerant systems. Early work by Martin and Alvisi, who introduced the FaB protocol [13], presented a two-round termination algorithm built on PBFT with \(n \ge 5f + 1\) validators, along with a parameterized variant requiring \(n = 3f + 2p + 1\), where \(f\) denotes the total number of faulty validators tolerated, and \(p \le f\) represents the number of faulty validators that need not participate for the fast path to succeed.

Subsequent works by Kuznetsov et al. [14] and Abraham et al. [15] further reduced these thresholds to \(n = 5f - 1\) and \(n = max(3f+2p-1, 3f+1)\) (for \(p \le f\)), which have been shown to constitute lower bounds for fast-path BFT partially synchronous protocols. Banyan [16] introduced a fast path that achieves fast termination in just two message delays, while departing from traditional PBFT-style designs: it is built on the Internet Computer Consensus (ICC) protocol [17] and operates with \(n = 3f+2p-1\) validators, where \(p \ge 1\) .

In this work, we address the question of whether decisions within two message delays can be achieved in DAG-based protocols. In DAG protocols, the graph continuously grows as rounds advance, and the challenge lies in identifying commit patterns within an already constructed DAG. Our approach integrates fast-path commit patterns with those used for slow-path commits, enabling both paths to coexist consistently within the DAG¹.

Our Contribution: In this work, we introduce FinWhale, a fast-path mechanism for the Mysticeti protocol, making it the first DAG-based protocol to support termination in just two message delays. We prove both safety and liveness under partial synchrony with \(n = 3f + 2p - 1\) validators, matching the lower bound. The protocol tolerates up to \(f\) Byzantine failures and achieves fast termination when the number of actual faults does not exceed \(p\) (\(1 \le p \le f\)), the round leader is honest, and the system has passed GST. This is while preserving the core guarantees and benefits of Mysticeti.

The rest of the paper is organized as follows. Section 2 describes the system model and problem definition. Section 3 reviews the Mysticeti protocol. Section 4 presents the FinWhale protocol. An execution example of FinWhale is illustrated in Section 5. Formal safety and liveness proofs are provided in Section 6 and Section 7. Section 8 discusses related work, and Section 9 concludes the paper.

2 Model↩︎

As is common in many BFT works, we assume a message-passing network among a set of \(n\) validators, connected via reliable and authenticated point-to-point links. Messages sent by honest validators are eventually delivered and cannot be forged, duplicated, or altered by the adversary. The adversary is computationally bounded and cannot break standard cryptographic primitives such as digital signatures or hash functions. In particular, validators cannot impersonate each other.

The network operates under the partially synchronous model [18]. That is, in each run of the system, there exists a Global Stabilization Time (GST), which is unknown to the validators. Before GST, message delays are arbitrary and unbounded. After GST, the network becomes synchronous: all messages between honest validators are guaranteed to be delivered within a known bounded delay \(\Delta\).

We assume that the system can have up to \(f\) Byzantine validators, i.e., validators that may behave arbitrarily, including maliciously, by sending conflicting or incorrect messages to disrupt the protocol. The remaining validators are considered honest, meaning they follow the protocol exactly as specified.

The total number of validators participating in the protocol is \(n \geq 3f + 2p - 1\), where \(p\) is a parameter satisfying \(1 \le p \le f\). Intuitively, \(p\) serves as a flexible threshold for enabling a fast-path decision: if the number of faults in the system is at most \(p\), the protocol can potentially reach consensus quickly using the fast path. However, even when the number of Byzantine faults exceeds this threshold, the protocol still tolerates up to \(f\) Byzantine faults overall by relying on a slower, more conservative decision process to ensure safety and liveness. Setting \(p=1\) enables the protocol to operate with \(3f+1\) validators, achieving the optimal resilience bound [18]. In this setting, the protocol takes the fast path after GST under an honest leader provided that at most one validator fails. In contrast, setting \(p=f\) guarantees that, under an honest leader after GST, the fast path is always taken.

As in prior DAG works [2], [7], [11], the protocol’s goal is to solve the Byzantine Atomic Broadcast (BAB) problem. Specifically, a validator \(v_k\) can invoke \(\mathsf{a\_bcast}_k(m, id)\) to broadcast a message \(m\) with a unique sequence number \(id \in \mathbb{N}\). Each validator \(v_i\) outputs delivered messages via \(\mathsf{a\_deliver}_i(m, id, v_k)\), indicating that \(v_i\) has delivered the message \(m\) associated with \(id\) that was broadcast by \(v_k\). A protocol solving the BAB problem must satisfy the following properties:

1. Agreement: If an honest validator \(v_i\) outputs \(\mathsf{a\_deliver}_i(m, id, v_k)\), then every other honest validator \(v_j\) eventually outputs \(\mathsf{a\_deliver}_j(m, id, v_k)\).

2. Integrity: For each sequence number \(id \in \mathbb{N}\) and validator \(v_k\), there exists at most one message \(m\) such that an honest validator \(v_i\) outputs \(\text{deliver}_i(m, id, v_k)\).

3. Validity: If an honest validator \(v_k\) calls \(\mathsf{a\_bcast}_k(m, id)\), then every honest validator \(v_i\) eventually outputs \(\mathsf{a\_deliver}_i(m, id, v_k)\).

4. Total Order: If an honest validator \(v_i\) outputs \(\mathsf{a\_deliver}_i(m, id ,v_k)\) before \(\mathsf{a\_deliver}_i(m', id', v_k')\), then no honest validator \(v_j\) outputs \(\mathsf{a\_deliver}_j(m', id', v_k')\) before \(\mathsf{a\_deliver}_j(m, id, v_k)\).

3 Mysticeti Overview↩︎

The Mysticeti paper [2] refers to the core DAG-based atomic broadcast protocol as Mysticeti-C. For brevity, in the rest of this work, we simply refer to both the system and the protocol as Mysticeti.

Below, we present the basic building blocks of Mysticeti, which also constitute the slow path of our protocol. The original construction as described in [2] was shown to suffer from liveness issues [10], [19], which were subsequently resolved in [9]. We therefore adopt the version of Mysticeti as presented in [9] , which augments the protocol with a push-based pacemaker and provides provable liveness guarantees.

DAG structure: The protocol proceeds in consecutive rounds. In each round \(r\), every honest validator broadcasts a single signed block containing its identifier (author), the round number \(r\), payload (users’ transactions), and a set of \(n\) edges to the latest blocks created by distinct validators in rounds up to \(r-1\). Among these edges, at least \(n - f\) refer to blocks created in round \(r-1\).

Each edge includes the hash of a previously received block, and the referenced block is called a parent of the new block. In addition, every block includes an edge that references the previous block created by the same validator.

A block is said to be valid if it conforms to the above block structure and its signature is correctly verified under the public key of its author. Each honest validator maintains a local DAG consisting of the blocks it has created and the valid blocks it has received. A block is inserted only when all its parent blocks are present; otherwise, it is buffered until the missing parents are received. The conditions under which a validator creates a block and advances to the next round are defined below when we discuss the pacemaker.

When an \(\text{a\_bcast}_i(m, id)\) is invoked at validator \(v_i\), the tuple \((m,id)\) is pushed to the DAG layer. Validator \(v_i\) will include \((m, id)\) in the payload field of its next created block.

Leader slots: The protocol deterministically designates a leader for each round, according to a round-robin schedule over the validators. Each leader together with its round defines a leader slot. Note that if the leader equivocates, multiple blocks may be associated with the leader slot.

Each leader slot is initially marked as undecided. Each validator analyzes its local DAG and decides, for every leader slot, whether its state should be changed to to-commit or to-skip. Once taken, such decisions are non-reversible.

A slot marked to-commit designates its associated leader block as committed, and the decision rules ensure that at most one block is committed per slot. The committed leader blocks determine the ordering of all blocks in the DAG.

We now define the notion of voting, a key concept in identifying DAG-based patterns underlying the decision rules.

Voting: A block \(b'\) in round \(r+1\) votes for a leader block \(b\) in round \(r\) if \(b\) is one of its parents. Clearly, a block created by a Byzantine validator may reference more than one leader block; in this case, it votes for the first leader block in its parent set.

Since Mysticeti serves as the slow path of our protocol, we retain its certificate-based decision mechanism, and refer to it as the slow-path certificate (SP-certificate), and refer to its skip condition as the slow-path skip pattern (SP-skip).

SP-certificate: Given a leader block \(b\) at round \(r\), a block \(b'\) at round \(r+2\) is called an SP-certificate for \(b\) if it references a quorum of \(\lceil \frac{n+f+1}{2} \rceil\) blocks from distinct validators that vote for \(b\).

SP-skip: An SP-skip pattern occurs when, for each block \(b\) of the leader slot (there may be multiple such blocks if the leader equivocates), there exists a quorum of blocks from distinct validators in round \(r+1\) that do not vote for \(b\). Particularly, if a block \(b\) of the leader slot is not in the local DAG, then all observed blocks in round \(r+1\) trivially do not vote for \(b\).

Note that in case of conflicting leader blocks for the same slot, at most one of them can have an SP-certificate, since by quorum intersection, at most one can garner the required quorum of blocks from distinct validators that vote for it. This property is crucial for the correctness of the decision rules.

Decision rules: Each validator attempts to decide each leader slot by first applying the direct decision rule, and then applying the indirect commit rule to earlier undecided slots. This process proceeds from the highest decided round to the lowest undecided round.

The direct decision rule marks a leader slot at round \(r\) as to-commit if there exists a quorum of SP-certificates for its leader block at round \(r+2\), in which case that block is committed(see Fig. 2 (a)). The slot is marked to-skip if the DAG contains an SP-skip pattern for the slot.

The direct commit rule enables committing leader blocks within three message delays when there are no failures and the system is fully synchronized. The direct skip rule allows slots to be decided quickly when the leader has crashed or failed to produce a valid block, thereby reducing the number of undecided slots.

If the direct decision rule does not decide the leader slot at round \(r\), the validator applies the indirect decision rule: The validator first searches for an anchor. The anchor is the earliest leader slot with round number greater than \(r+2\) that is marked as either to-commit or undecided. If the anchor is undecided, then the slot remains undecided. If the anchor is marked to-commit, the validator checks whether there exists a path from the anchor to an SP-certificate for a block from the leader slot. If such a path exists, the slot is marked to-commit and the corresponding block is committed (see Fig. 2 (d)); otherwise, it is marked to-skip.

Commit sequence: After applying the decision rules to all leader slots, the validator extends its commit sequence in ascending order of round numbers. Leader slots marked as to-skip are omitted, while committed blocks from slots marked as to-commit are included in the sequence. The sequence terminates at the first undecided slot. The safety and liveness proofs of Mysticeti establish that all honest validators commit a consistent sequence of leader blocks and that, eventually, every slot is decided.

Total ordering: Validators obtain a total order over all blocks in the DAG by deterministically sorting the causal histories of leader blocks in the commit sequence. Specifically, for each leader block in the commit sequence, the latter part of its causal history that has not been already ordered by previous leader blocks is deterministically sorted and added to the total ordering sequence.

For each ordered block \(b\), validators deliver \((m,id,b.author)\) tuples derived from the \((m,id)\) tuples in the payload of \(b\). Any \((m,id,b.author)\) tuple that has already been delivered is filtered out, ensuring that each tuple is delivered exactly once.

Safety intuition: If a validator commits a block \(b\) for a given slot, then no other validator can skip that slot or commit a conflicting block for the same slot. To that end, a key property proved in [2], [9] and by our Lemma 2 states that: if \(b\) is committed directly by some validator, then a path from the anchor to an SP-certificate for \(b\) exists in every validator’s DAG. This property rules out indirect skipping by definition. Moreover, the presence of an SP-certificate, whether \(b\) is committed directly or indirectly, excludes both direct skipping and committing a conflicting block, by quorum intersection. The remaining case is when \(b\) is committed indirectly by different validators. In this case, all validators agree on the same committed anchor block, as shown in [2], [9] and by our Lemma [lemma:consistent-slots-1]. Consequently, they observe the same causal history and reach the same decision for that slot.

Push Pacemaker: The Push Pacemaker is responsible for ensuring liveness, by specifying the conditions for advancing rounds, creating blocks, and broadcasting unknown parts of the history. It consists of the following aspects:

Advancing rounds: A validator advances from round \(r-1\) to round \(r\) when the following two conditions are satisfied:

A1:

There are \(n-f\) round \(r-1\) blocks from distinct validators in the local DAG.

A2:

The validator has created its own block in round \(r-1\).

Creating blocks: After advancing to round \(r\), a validator records its local time. We set \(\delta_{LT} = 2\Delta\) as the timeout duration. The validator then creates its block when one of the following three conditions holds:

C1:

The following two requirements are satisfied:

L1:

The local DAG contains a leader block from round \(r-1\).

L2:

The local DAG contains either (i) a quorum of voters from distinct validators for the leader of \(r-2\), or (ii) an SP-skip pattern for the leader of \(r-2\).

C2:

The \(\delta_{LT}\) timeout has expired.

C3:

The local DAG contains \(n-f\) blocks from distinct validators in round \(r\).

When C1 triggers block creation, the validator should choose to include in its parents the set of blocks that were used to satisfy requirement L2 (it is important in cases where there are multiple versions of \(r-1\) blocks belonging to Byzantine validators). Waiting for C1 to be satisfied ensures that after GST, honest leaders get committed. C2 requires that upon expiration of a timeout, the validator creates a block, even if condition C1 is not satisfied. C3 ensures that slower validators can catch up: if C1 is not satisfied but \(n-f\) blocks have already been produced in round \(r\), a validator may proceed without waiting for the timeout to expire.

Broadcasting unknown history: When a validator receives a block, it attempts to add it to its local DAG only if all its parents (and, transitively, its entire causal history) are already present in the DAG. Since Byzantine validators may send blocks to only a subset of validators or send conflicting versions to different validators, when an honest validator creates and sends its block, its parents may include blocks created by Byzantine validators. To ensure that such blocks can be added to other validators’ DAGs, validators follow the principle of cordial dissemination [20], by which a validator \(v_i\) sends to another validator \(v_j\) the blocks in its local DAG that it believes \(v_j\) did not yet receive. Formally, let \(\mathrm{DAG}_i\) denote the set of blocks in the local DAG of \(v_i\). From the perspective of \(v_i\), the set of blocks known to \(v_j\) is defined as \(\mathrm{known}_i(j) = H_{i,j} \cup S_{i,j}\), where \(H_{i,j}\) is the union of the causal histories of all blocks in \(\mathrm{DAG}_i\) created by \(v_j\), and \(S_{i,j}\) is the set of all blocks sent from \(v_i\) to \(v_j\). Accordingly, the set of blocks unknown to \(v_j\) is \(\mathrm{unknown}_i(j) = \mathrm{DAG}_i \setminus \mathrm{known}_i(j)\).

Upon any of the following pacemaker triggers, a validator \(v_i\) sends the unknown portion of its history to its peers:

B1:

creating a block.

B2:

advancing to a new round.

The Push pacemaker ensures synchronicity after GST: when a fast honest validator advances to a new round, its history is broadcast to all validators via B2. As a result, they can create blocks in all rounds up to that round via C3 and advance to the new round according to A1 and A2. Moreover, B1 ensures that if a fast honest validator creates a block under C1, then all honest validators observe the same conditions and can therefore also create their blocks under C1.

Liveness intuition: With the Push pacemaker, [9] establishes synchronicity after GST: validators enter each new round within \(\Delta\) and create blocks within \(\Delta\) of one another. This property was assumed without proof in [2]. Building on this, [2], [9] show that, after GST, any honest leader slot is eventually marked to-commit by the direct decision rule, and that all leader slots are eventually decided. Consequently, every honest leader block is included in the commit sequence. Moreover, any block created by an honest validator eventually becomes part of the causal history of some committed honest leader block, and is therefore ordered and delivered.

4 FinWhale↩︎

4.1 Protocol Description↩︎

In addition to the Byzantine Atomic Broadcast properties, FinWhale satisfies an additional Fast Termination property. We adapt its definition from Banyan [16] to our setting.

To support the Fast Termination property, we introduce an additional direct commit rule: A leader block \(b\) of round \(r\) is fast-directly committed if there exist \(n-p\) blocks from distinct validators in round \(r+1\) that reference \(b\), i.e., if there are \(n-p\) voters for \(b\). With this rule, a leader block can be committed within two message delays when network conditions permit.

In Mysticeti, the presence of a direct commit pattern within a given DAG guarantees that any other DAG will contain a corresponding pattern serving as evidence that neither a skip can be determined for the slot nor a conflicting block can be committed. Similarly, we require that if a fast direct commit of the leader block occurs in the DAG of some validator, then every other validator must observe in its DAG a corresponding pattern that rules out both conflicting commits and skip decisions for the same slot.

We introduce a new notion, where blocks in round \(r+2\) serve as an FP-evidence for a leader block \(b\) of round \(r\). Intuitively, when a block is committed directly via the fast path in a DAG of validator \(v_i\) during round \(r+1\), it leaves evidence in round \(r+2\) in all other DAGs in the form of FP-evidence blocks.

We note that a single FP-evidence block represents a weaker form of voting evidence than an SP-certificate, and the DAG may simultaneously contain FP-evidence for conflicting leader blocks. However, the presence of a quorum of such FP-evidence blocks suffices to guarantee consistent behavior across all honest validators’ DAGs.

Block construction: In Mysticeti, advancing from the current round to the next round according to condition A1 requires observing \(n - f\) blocks from different validators. To enable the fast path under the tighter bound \(n = 3f + 2p - 1\), an honest validator must take into account not only the blocks from the current round, but also the behavior of the leader of the previous round².

Specifically, a Byzantine leader in the previous round may equivocate by broadcasting multiple conflicting versions of its block. However, if an honest validator receives blocks that reference more than one version of the leader block, then this is an evidence that the previous round leader is Byzantine. In this case, the validator can safely wait for \(n-f\) blocks not including the block authored by the Byzantine leader without blocking. Consequently, the validator observes and references at least \(n - f\) blocks, among which at most \(f - 1\) are from Byzantine validators, because the block authored by the detected equivocating leader is not included as a parent when the validator constructs its next block.

Throughout this section, we denote \(L_r\) the leader of round \(r\). In particular, \(L_{r-1}\) and \(L_{r-2}\) denote the leaders of rounds \(r-1\) and \(r-2\), respectively.

Leader-consistent. A set of round-\(r\) blocks \(B_r\) is said to be leader-consistent with respect to \(L_{r-1}\) if all blocks in \(B_r\) vote for at most one block proposed by \(L_{r-1}\).

Block validity As before, blocks are added to the DAG of an honest validator only if it obeys the block validity rules. FinWhale’s definition of a valid block extends Mysticeti’s validity rules by adding the following requirements:

1. Each block has at most a single parent per validator. We do not allow malformed blocks (e.g., those created by Byzantine validators) that contain multiple edges to blocks of the same validator.

2. A block in round \(r\) must be valid with respect to round \(r-2\). That is, it links to at least \(n-f\) blocks from round \(r-1\), each from a distinct validator, and satisfies one of the following conditions:

FP-evidence, Non-FP-evidence: We say that a block \(b'\) of round \(r+2\) exposes equivocation by \(L_r\) if its parent set is not leader-consistent, i.e., its causal history contains multiple conflicting versions of \(L_r\)’s block.

A block \(b'\) of round \(r+2\) is an FP-evidence for a leader block \(b\) of round \(r\) if one of the following conditions holds:

• Equivocating case: \(b'\) exposes equivocation of \(L_r\). It references at least \(f+p\) parent blocks that vote for \(b\), while fewer than \(f+p\) of its parent blocks vote for any block conflicting with \(b\).

• Non-equivocating case: \(b'\) does not expose equivocation of \(L_r\). It references at least \(f+p-1\) parent blocks that vote for \(b\).

Finally, a block at round \(r+2\) is a Non-FP-evidence if it is not an FP-evidence for any block proposed by \(L_r\).

Examples of FP-evidence and Non-FP-evidence blocks are in Figure 1.

A key property we prove in Lemma 3 below is that if a leader block of round \(r\) is directly committed via the fast path, then every block at round \(r+2\) in any DAG is an FP-evidence block for \(b\).

FinWhale relies on the same definitions of SP-certificate and SP-skip patterns as Mysticeti. Recall that in our setting, a quorum of size \(\left\lceil \frac{n+f+1}{2} \right\rceil\) equals \(2f+p\). With the additional definitions of FP-evidence blocks and Non-FP-evidence blocks, we are now ready to formally define FinWhale’s decision rules. Here again, each validator iterates over rounds from the highest to the lowest undecided round and applies the decision rules.

Direct decision rules: The validator marks a leader slot of round \(r\) as to-commit if it observes one of the following cases:

1. There exists a quorum of \(\left\lceil \frac{n+f+1}{2} \right\rceil = 2f+p\) SP-certificates from distinct validators in round \(r+2\) for a block \(b\) of the slot. \(b\) is then committed.

2. There exist \(n-p\) blocks from distinct validators in round \(r+1\) that vote for a block \(b\) of the slot. \(b\) is then committed.

The validator marks a slot as to-skip when both of the following conditions hold:

1. The SP-skip pattern is observed in round \(r+1\).

2. There are at least \(\left\lceil \frac{n+f+1}{2} \right\rceil = 2f+p\) Non-FP-evidence blocks from distinct validators in round \(r+2\).

Indirect decision rule: If during the reverse pass over undecided round, the direct decison rules did not decide a given slot, the validator tries to apply the indirect decsion rules: First it searches for an anchor, which is defined as in Mysticeti, to be the first slot with round number greater than \(r+2\) that is marked either to-commit or undecided. If the anchor is undecided then the slot is marked undecided as well. If the anchor is marked to-commit, the validator marks the slot as to-commit if one of the following conditions holds:

1. There exists a path from the anchor to an SP-certificate for a block \(b\) of the slot, in which case \(b\) is committed.

2. There exist paths from the anchor to a quorum of \(\left\lceil \frac{n+f+1}{2} \right\rceil = 2f+p\) FP-evidence blocks from distinct validators, all for the same block \(b\) of the slot, in which case \(b\) is committed.

Otherwise, the slot is marked to-skip.

The decision rules are illustrated in Figure 2. Note that both of the above conditions may hold simultaneously for conflicting blocks of the same slot. In such a case, one of the blocks is selected for commitment according to a deterministic rule. Such a pattern cannot arise if any validator can decide the slot directly, either by direct skip or direct commit: a direct skip rules out the conditions for an indirect commit, and a direct commit rules out the conditions for an indirect commit of a conflicting block. Hence, all validators must decide the slot indirectly, in which case they all reach the same decision. The patterns induced by direct decisions, as well as the consistency of indirect decisions, are described in the safety intuition and proved in the safety section.

Commit sequence: The algorithm proceeds similarly to Mysticeti. It examines leader slots from the highest round down to the lowest undecided round. For each slot, the validator applies the commit rules to determine its state. The commit sequence is then extended in ascending order of round numbers by including slots marked to-commit together with their committed blocks, while omitting slots marked to-skip. The process stops upon reaching the first undecided slot. Figure 3 illustrates how the commit sequence is extended by including committed leader blocks until reaching the first undecided slot.

Total order: As in Mysticeti, the final total order is obtained by deterministically sorting the causal histories of the committed leader blocks. For each ordered block \(b\), all \((m,id)\) pairs in its payload are delivered as \((m,id,b.\text{author})\), while filtering out any such tuples that have already been delivered.

Safety intuition: validators cannot reach conflicting decisions: they either both commit the same block for a leader slot \(s\) or both skip \(s\). We rely on the following structural properties of the protocol:

1. A slow-path direct commit of block \(b\) yields a path from the anchor to an SP-certificate for \(b\) in every DAG (Lemma 2).

2. A fast-path direct commit yields a path from the anchor to a quorum of FP-evidence blocks for \(b\) in every DAG (Lemma 4).

3. An SP-certificate for \(b\) is also an FP-evidence for \(b\) (Lemma 1).

We claim that if a validator directly skips a leader slot \(s\), no other validator can commit a block for the slot (Lemma 5). A direct skip requires collecting a quorum of blocks not voting for any block of \(s\) together with a quorum of Non-FP-evidence blocks. By quorum intersection, this precludes the existence of an SP-certificate or a quorum of FP-evidence blocks for any block of slot \(s\) in any other DAG. Since either of these is necessary for an indirect commit, the latter is impossible. Further, the presence of a quorum of non-voters for any leader blocks also rules out a direct commit in any other DAG.

If a validator directly commits a block \(b\) of slot \(s\), then no other validator can skip \(s\) (Lemma 6) or commit a conflicting block (Lemma 8 and Lemma 9). When a validator directly commits \(b\), depending on whether the slow or fast path is taken, any other DAG contains either a path from the anchor to an SP-certificate for \(b\) or paths from the anchor to a quorum of FP-evidence blocks for \(b\) (Properties 1 and 2, respectively). This already rules out indirect skipping in any other DAG by definition. To show consistency with respect to a conflicting block \(b'\), observe that a direct commit of \(b\) implies a quorum of voters for \(b\), which by quorum intersection rules out the existence of an SP-certificate for \(b'\). It also rules out a quorum of FP-evidence blocks for \(b'\). Indeed, if \(b\) is committed via the fast path, then by Property 2 every DAG contains a quorum of FP-evidence blocks for \(b\). If \(b\) is committed via the slow path, the SP-certificates for \(b\) form a quorum, which in turn induces a quorum of FP-evidence blocks for \(b\) by Property 3. In both cases, quorum intersection prevents the existence of an FP-evidence quorum for \(b'\). The absence of either an SP-certificate or a quorum of FP-evidence blocks for \(b'\) precludes an indirect commit of \(b'\). Moreover, by a simple quorum intersection argument, a direct commit of \(b'\) is also impossible.

Finally, if validators decide \(s\) indirectly, they rely on the same committed anchor block, and therefore observe the same causal history and reach the same decision (Lemma [lemma:consistent-slots-1]).

Pacemaker conditions: Similarly to Mysticeti, we define pacemaker conditions for FinWhale that ensure both liveness and the creation of valid blocks.

Advancing rounds: An honest validator advances from round \(r-1\) to round \(r\) when two conditions are satisfied: \(\boldsymbol{A1'}\) and \(\boldsymbol{A2}\). Condition \(\boldsymbol{A2}\) is inherited from Mysticeti and is restated here for completeness. Condition \(\boldsymbol{A1'}\) determines the threshold on the number of round \(r-1\) blocks (from distinct validators) that are required for advancement, as in Mysticeti’s \(\boldsymbol{A1}\). However, here the value depends on whether a leader-consistent set is observed.

A1’

If there exists a set of round \(r-1\) blocks that is leader-consistent with respect to \(L_{r-2}\) and contains a block from each validator whose round \(r-1\) block has been received, then the threshold is \(n-f\); otherwise, the threshold is \(n-f\), where blocks created by \(L_{r-2}\) are not counted.

A2

The validator has created its own block in round \(r-1\).

Block creation: A block in round \(r\) is created if at least one of the following conditions is satisfied:

C1

The following two requirements are satisfied:

L1

The local DAG contains a block of \(L_{r-1}\).

L2

The local DAG contains either \((i)\) a quorum of voters from distinct validators for \(L_{r-2}\) block, or \((ii)\) contains an SP-skip pattern for \(L_{r-2}\)

C2

The timeout \(\delta_{LT} = 2\Delta\) has expired.

C3

The local DAG contains \(n-f\) blocks from distinct validators in round \(r\).

Selecting the parents: When a block is created in round \(r\), the validator must select its parent set from round \(r-1\) blocks. Byzantine validators may produce multiple blocks in round \(r-1\), but the validator includes at most one parents per validator, while selecting the blocks that satisfy conditions \(\boldsymbol{L1}\) and \(\boldsymbol{L2}\) if condition \(\boldsymbol{C1}\) triggers block creation.

Whenever the parent set is not leader-consistent with respect to \(L_{r-2}\), the round-\((r-1)\) block created by \(L_{r-2}\) must be excluded. Accordingly, the parent selection algorithm needs to exclude this block whenever the resulting parent set violates leader-consistency with respect to \(L_{r-2}\). However, when there are round-\((r-1)\) blocks from exactly \(n-f\) validators, excluding this block would leave only \(n-f-1\) parents, violating the requirement that a parent set contains at least \(n-f\) blocks. Therefore, in this case, we must guarantee that multiple round-\((r-1)\) blocks produced by Byzantine validators do not prevent the construction of a leader-consistent parent set. Condition A1’ ensures the existence of such a leader-consistent set of size \(n-f\).

Formally, the parent selection proceeds as follows:

1. Initialize the candidate set with the blocks in the local view of \(DAG[r-1]\).

2. If the round-\((r-1)\) block proposed by \(L_{r-2}\) is present and round-\((r-1)\) blocks from exactly \(n-f\) distinct validators are available, construct a leader-consistent set with respect to \(L_{r-2}\) that contains at least one block from each of these validators. Such a set exists by condition A1’.

3. Construct the parent set from the candidate set such that: (1) for each validator \(v\), the parent set contains exactly one block authored by \(v\), and (2) if condition \(\boldsymbol{C1}\) triggers block creation, all blocks in the candidate set that satisfy condition \(\boldsymbol{L1}\) and \(\boldsymbol{L2}\) are included in the parent set.

4. If the current parent set is not leader consistent w.r.t. \(L_{r-2}\), exclude the round-\((r-1)\) parent block proposed by \(L_{r-2}\) from the parent set, even if it was previously included (by the previous step).

Finally, the validator includes blocks from rounds older than \(r-1\) in its parent set as follows: the latest block from each author that has not yet been referenced by a previous block of the validator is included in the parent set. This ensures that every block created by an honest validator appears in the causal history of some honest leader block, and is therefore ordered and its payload delivered.

Broadcasting history: A validator broadcasts its unknown history under the same \(\boldsymbol{B1}\) and \(\boldsymbol{B2}\) conditions as in Mysticeti.

Liveness intuition: Liveness in FinWhale is based on the liveness of the slow path. After GST, every leader block created by an honest validator is eventually included in the commit sequence, and its causal history is delivered. When conditions allow the fast path to be taken, leader blocks can be marked to-commit more quickly, thereby accelerating total ordering and delivery.

Additional Discussion Points: It is possible to simplify FinWhale by relaxing the resilience threshold from the lower bound of \(n = 3f + 2p - 1\) validators to \(n = 3f + 2p + 1\). For instance, this would enable a simpler DAG construction, in which it is not necessary to wait for an additional block in round \(r+1\) when the round-\(r\) leader is proven to be Byzantine. Moreover, eliminating the need to distinguish between equivocating and non-equivocating cases would simplify the definition of FP-evidence.

Under the relaxed assumption \(n = 3f + 2p + 1\), there exist scenarios in which Byzantine leader blocks may be directly committed despite equivocation. In contrast, under the tighter bound of \(n = 3f + 2p - 1\), enforcing that at most \(f-1\) Byzantine blocks are selected as parents prevents such direct commits. These scenarios are rare and arise only under highly specific conditions.

Mysticeti [2] targets direct skipping as a mechanism to efficiently handle benign crashed leaders by promptly skipping them and reducing their impact on performance. When the leader is Byzantine, however, it may attempt to prevent direct skipping, thereby leaving the slot undecided. In particular, to preclude the formation of a quorum of non-voters after GST, a Byzantine leader must ensure that its block is disseminated to sufficiently many honest validators so that they produce voting blocks; otherwise, a quorum of non-voters may form, leading to a direct skip. On the other hand, once honest validators create voting blocks, they broadcast their history, which may cause other honest validators to receive the leader’s block and form an SP-certificate, resulting in a direct commit. Therefore, a Byzantine leader must carefully and selectively disseminate its block so that enough honest validators vote for it, while ensuring that their history broadcasts do not propagate in time to enable SP-certificate formation. This leaves the leader slot undecided. In FinWhale, however, direct skipping requires a quorum of non-FP-evidence blocks in addition to a quorum of non-voters. This makes the Byzantine attack simpler in the optimal-resilience setting. In particular, the leader may withhold its block from all honest validators, while all \(f\) Byzantine validators send their round-\(r+1\) blocks voting for the leader. When \(p=1\), these \(f\) Byzantine votes are sufficient to cause honest validators to produce FP-evidence blocks, thereby preventing a direct skip. As in Mysticeti, when the system is configured with \(n = 3f + 2p + 1\) validators, this simple attack is no longer feasible. It remains an open question whether achieving the lower bound on \(n\) inherently facilitates this simple attack that prevents direct skipping.

FinWhale differs from Mysticeti in the timing at which the direct-skip decision is made. In our protocol, a direct skip can occur only at the end of round \(r+2\), whereas in Mysticeti, a direct skip may occur already in round \(r+1\). However, this difference does not actually delay the commit sequence. The purpose of the direct skip rule is to decide slots as early as possible, so as not to delay the commit of subsequent leaders. Since in Mysticeti the next leader can be committed only at round \(r+3\), our modified direct skip decision does not introduce any additional delay in the overall commit sequence.

4.2 Algorithm and Pseudo Code↩︎

The pseudocode for FinWhale is given in Algorithms 4–8. It is based on the Mysticeti design, with the necessary modifications to enable the fast path. Algorithms 4 and 5 describe the construction of the DAG, including executing rounds, creating blocks, advancing rounds, and broadcasting unknown history. Algorithm 6 presents the helper functions, while Algorithm 7 introduces new helper functions required specifically for enabling the fast path. Algorithm 8 describes the logic for deciding leader slots, ordering blocks in the DAG, and delivering payloads. In the code, we use \(DAG[r]\) to refer to the set of all blocks from round \(r\) stored in the local DAG.

5 An Example of FinWhale Execution↩︎

Figure 9 illustrates an example of the DAG with four validators at a specific moment. The protocol iterates the rounds from highest, round 5, to the lowest undecided round, round 1. Initially they are all undecided. The leader of round 5 remains undecided as there are no blocks in subsequent rounds voting for it. The leader of round \(4\) is directly committed via the fast path, since it has more than \(n-p=3\) voters in round \(5\).

The leader of round \(3\) is directly skipped due to the following two conditions: (a) it has a quorum (\(3\)) of non-voters in round \(4\); and (b) in round \(5\), there is a quorum of Non-FP-evidence blocks: each such block references no voters for the round-\(3\) leader block and therefore qualifies as a Non-FP-evidence block.

The leader of round \(2\) remains undecided. It has only two voters, and is therefore neither directly skipped (which requires at least three non-voters) nor directly committed (which requires at least three voters). Moreover, its anchor in round \(5\) is still undecided.

The leader block of round \(1\) cannot be decided directly. It is not directly committed because there is only one vote for it in round \(2\). It is also not directly skipped because, in round \(3\), there are no Non-FP-evidence blocks. All round-\(3\) blocks are FP-evidence for the round-\(1\) leader block, as each references the round-\(2\) block of \(V_1\), which votes for that leader block. In the absence of equivocation, referencing \(f+p-1=1\) voter is sufficient to qualify as FP-evidence.

However, the leader block of round \(1\) can be indirectly committed. The round-\(4\) leader block is marked to-commit and therefore serves as the anchor. Moreover, it has paths to a quorum (\(3\)) of round-\(3\) blocks that are FP-evidence for the round-\(1\) leader block. Thus, the round-\(1\) leader block is indirectly committed.

The commit sequence is extended to include all leader blocks committed up to the first undecided slot. Therefore, the leader of round \(1\) is included in the commit sequence, all blocks in its causal history are ordered (if they have not already been ordered by a previous leader), and their payloads are delivered.

6 FinWhale’s Safety Proof↩︎

In this section, we establish the safety of our protocol. Specifically, we prove that the commit sequence is consistent among all honest validators, and consequently that the integrity and total order properties of Byzantine Atomic Broadcast (BAB) hold. To account for the fast path, we adapt existing statements and proofs where necessary, introducing the additional arguments required for fast-path commits while preserving the overall proof structure.

Combining Lemma 8 and Lemma 9 implies the following:

7 FinWhale Liveness↩︎

In this section, we establish liveness under partial synchrony. We first show that any honest leader block is eventually committed via the slow path after GST. Since any block created by an honest validator is part of the causal history of some honest leader block, it follows that every honest block is eventually ordered and its payload is delivered.

In addition, we show that if at most \(p\) validators behave Byzantine, an honest leader block can be committed via the fast path in just two rounds (fast termination).

Since liveness is established via the slow path, the proof follows [2], which provides the original liveness argument, and [9], which further refines and completes the argument, with minor adjustments required for the fast path.

We now introduce notation used in the liveness analysis.

Let \(r_{\max}\) be the largest round reached by any honest validator at GST.

8 Related Work↩︎

8.1 DAG-based Protocols↩︎

DAG-based BFT protocols can be broadly classified into certified and uncertified DAG protocols, according to the mechanism used to disseminate blocks. In certified DAG protocols, validators disseminate blocks using a Byzantine Reliable Broadcast (BRB) primitive. BRB prevents equivocation and ensures block availability by guaranteeing that blocks are consistently delivered to all honest validators. Typically, each block must first be certified by a quorum of validators before being included in the DAG. However, BRB-based dissemination may incur an additional latency of \(2\)–\(4\) message delays. In contrast, uncertified DAG protocols aim to improve latency by using best-effort broadcast (BEB) instead of BRB, where the uniqueness of a block is not guaranteed. Thus, these protocols must explicitly handle equivocations.

We first consider certified DAG-based consensus protocols. Aleph is an asynchronous protocol that constructs a round-based DAG and uses an efficient binary agreement protocol for ordering. DAG-Rider [7] is an asynchronous DAG-based BFT protocol that progresses in waves consisting of four rounds, with a single leader in each wave. Tusk [4] refines DAG-Rider by replacing conventional BRB with quorum-based BRB, modifying the commit rules to improve latency in common-case executions, and enabling efficient garbage collection.

Bullshark [11] builds upon DAG-Rider to improve commit latency during synchronous periods. Its partially synchronous variant elects one leader every two rounds. Shoal [12] interleaves two instances of Bullshark, thereby introducing a leader in every round. Sailfish [10] and Shoal++ [1] similarly optimize the commit rules for leader blocks by using the first messages of the BRB to count votes for the leader. In addition, they support multiple leaders per round, further improving commit latency.

We next discuss uncertified DAG-based protocols. HashGraph [3] builds an unstructured DAG through validators disseminating blocks containing two references to previous blocks. It uses virtual voting by interpreting the Hashgraph structure itself, together with the notion of “strongly seeing” (similar to certificates), to handle equivocations. A binary agreement protocol is then used to order transactions.

Cordial Miners [8] introduce both asynchronous and partially synchronous DAG-based protocols. In these constructions, a single leader is assigned in the first round of each wave, where waves consist of five rounds in the asynchronous setting and three rounds in the partially synchronous setting.

Mysticeti [2] is a partially synchronous DAG protocol built upon Cordial Miners. It pipelines waves and supports multiple leaders per round in order to improve commit latency. A followup work [9] introduced four DAG protocols: The first revisits Mysticeti with an improved push-based pacemaker that resolves its liveness issues. Starfish further decouples payload dissemination from metadata dissemination, improving communication complexity. Finally, Starfish-L and Mysticeti-L combine multi-signatures with a Lazy-Push pacemaker to further reduce communication overhead. In Finwhale, we build on and adapt the revised Mysticeti protocol introduced in [9], as well as their approach of using a single leader per round. BBCA-Chain [21] introduces a design in which leader blocks are broadcast using a BBCA primitive built on top of BRB, while non-leader blocks are disseminated using BEB, where leaders are assigned in every round.

8.2 Fast Consensus↩︎

Kursawe[22] was the first to implement a fast (two-step) Byzantine consensus protocol in which two-step fast path is paired with a subprotocol in the slow path. It is able to run with \(3f+1\) validators and the fast path is taken when all validators are honest and the network is synchronous. Otherwise, a fallback subprotocol is used to ensure liveness. An asynchronous binary Byzantine consensus protocol with fast-path termination is presented in [23]. The randomized protocol, assisted by a random oracle, tolerates \(n>5f\) validators and decides within one communication round in favorable executions.

Bosco bosco? is a Byzantine consensus protocol that achieves a two-step fast path with \(n>5f\) validators when all validators propose the same value. The fast path can also be achieved with \(n>7f\) when all honest validators are in pre-agreement.

FaB Paxos [13] is a fast Byzantine consensus protocol requiring \(n \ge 5f+1\) validators. The paper also presents a parameterized variant with \(n \ge 3f+2p+1\), which achieves a two-step fast path in the common case when the leader is correct, the network is synchronous, and at most \(p\) validators are Byzantine.

The lower bound of FaB Paxos was later improved to \(n \ge 5f-1\) by [15]. An independent work [14] proved a lower bound of \(n \ge 3f+2p-1\) for the parameterized setting. The key idea is that equivocating leaders can be detected, allowing validators to wait for \(n-f\) votes while excluding the vote of the Byzantine leader.

Banyan [16] is a rotating-leader protocol based on ICC [17]. It achieves two-step termination in the partially synchronous model with \(n \ge 3f+2p-1\) validators. As long as at most \(p\) replicas are unresponsive, termination occurs within two message delays. The dual-mode mechanism enables two-step finalization latency in the fast path, and ensures that no penalties are incurred when the fast path is not taken.

Kudzu [24] is an atomic broadcast protocol with an integrated fast path. It achieves finality in just two rounds of communication for \(n = 3f + 2p + 1\) validators, provided that at least \(n - p\) replicas behave honestly. Building on DispersedSimplex [25], Kudzu introduces minimal modifications to incorporate a fast path. Furthermore, the protocol uses erasure codes to ensure that the leader can disseminate large blocks with low and well-balanced communication complexity.

9 Conclusions↩︎

In this work, we presented FinWhale, the first DAG-based Byzantine Fault Tolerant protocol to integrate a fast-path mechanism that achieves termination in just two message delays when favorable conditions occur. By carefully combining fast-path commit patterns with the existing slow-path mechanisms of Mysticeti, FinWhale enables validators to commit transactions more quickly while maintaining safety and liveness under partial synchrony with \(n = 3f + 2p - 1\) validators.

Our protocol tolerates up to \(f\) Byzantine faults and ensures fast termination whenever the number of faults does not exceed \(p\), all while preserving the foundational guarantees and high-throughput benefits of Mysticeti. Beyond achieving the theoretical lower bound for latency in BFT consensus based protocols, FinWhale demonstrates that fast-path techniques traditionally applied to leader-based protocols can be effectively adapted to DAG structures. This helps bridge the gap between high-throughput DAG designs and optimal fast-path decision-making.

Starfish, Starfish-L, and Mysticeti-L [9] are protocols closely related to Mysticeti and designed to achieve improved communication complexity by combining multi-signatures, lazy dissemination of history, and efficient information dispersal techniques. Exploring how these techniques can be incorporated into FinWhale is an interesting direction for future work.

Acknowledgements.

We thank Alberto Sonnino and Sebastian Müller for insightful discussions that helped us better understand Mysticeti and Starfish.

References↩︎

---

1. The Mysticeti paper [2] introduces Mysticeti-FPC, which provides a fast path for transactions that do not require consensus. In contrast, our work adds a fast path to the consensus protocol itself, covering all types of transactions.↩︎

2. This additional requirement does not arise under the looser bound \(n = 3f + 2p + 1\), as discussed later.↩︎