arXiv CSopen access

Clownfish: Scaling DAG-based BFT Consensus via Sparse Edges

arXiv:2606.04687v1 [cs.DC] 3 Jun 2026

Clownfish: Scaling DAG-based BFT Consensus via Sparse Edges Feifan Wang∗

Jingfan Yu∗

Tsinghua University Beijing, China [email protected]

Tsinghua University Beijing, China [email protected]

Zixi Cai

Zhixuan Fang†

Tsinghua University Beijing, China [email protected]

Tsinghua University Beijing, China [email protected]

Abstract Directed Acyclic Graph (DAG) based BFT protocols have demonstrated the capability to achieve significantly high throughput in practice. Recent advancements focused on minimizing the goodcase latency of these protocols, approaching the theoretical lower bound. However, the high communication complexity inherent in existing DAG-based protocols limits their scalability. This primarily arises because each vertex in the DAG must include a linear number of edges (references) to vertices from previous rounds. We present Clownfish, a partially synchronous DAG-based BFT protocol designed to address the scalability bottleneck. Clownfish achieves lower communication complexity by selectively reducing the number of edges in DAG vertices. When using a communicationoptimal consistent broadcast, Clownfish attains quadratic total communication complexity per round, outperforming prior DAG-based protocols. Clownfish also reduces the additional latency in failure cases by optimizing the round advancement rule. Additionally, Clownfish supports multiple leaders per round to reduce average latency while maintaining its lower communication complexity. Our experimental evaluation demonstrates that Clownfish provides significantly better scalability than existing DAG-based protocols.

Keywords Byzantine Fault Tolerance, DAG-based Consensus, Communication Complexity, Scalability

1

Introduction

Byzantine Fault Tolerant (BFT) consensus enables a set of replicas to consistently commit a sequence of values even under adversarial conditions. With the proliferation of decentralized systems such as blockchains, BFT consensus protocols—serving as their fundamental building blocks—have garnered extensive research attention [15, 43, 50]. Under specific network and adversarial assumptions, the key metrics used to evaluate BFT consensus protocols include latency, throughput, and communication complexity. Among these, latency and throughput directly reflect the execution efficiency of a protocol, whereas communication complexity serves as a crucial indicator of system scalability [3]. Following the seminal work of PBFT [15], traditional BFT consensus protocols have widely adopted the leader-based paradigm [13, 25, 50]. These protocols rely on a single, rotating leader to propose ∗ Both authors contributed equally to this research. † Corresponding author.

blocks containing transactions (data), while the remaining replicas participate in multi-phase voting to commit these blocks. In partial synchrony networks [21], protocols following this paradigm can achieve optimal latency [1] (3 message delays in PBFT) or optimal communication complexity (linear complexity in HotStuff [50]) in the good case. However, the single leader becomes a system bottleneck that significantly constrains the achievable throughput [19]. The key to enhancing throughput lies in fully utilizing the bandwidth of all replicas for data transmission. Effective approaches to achieve this include running multiple leader-based BFT instances concurrently with distinct leaders [45, 46], as well as decoupling data dissemination from consensus logic [26, 49]. A recently emerging paradigm is Directed Acyclic Graph (DAG)-based BFT [19, 23, 33, 43]. This paradigm naturally integrates the aforementioned ideas and has been successfully deployed in modern blockchains [9] due to its simplicity and practical efficiency. In DAG-based BFT protocols, replicas concurrently construct a DAG in a structured manner. Typically, these protocols proceed in rounds. In each round, every replica disseminates a vertex packed with transactions. Each vertex contains references to at least 𝑛 − 𝑓 vertices from the previous round via edges, where 𝑛 is the total number of replicas and 𝑓 is the maximum number of Byzantine replicas. Collectively, these vertices and edges form a DAG. The consensus logic is intrinsic to the DAG structure, allowing all replicas to commit a consistent DAG prefix through local interpretation. DAG-based BFT protocols have demonstrated significantly high throughput in practice [19, 43]. To achieve better efficiency, many recent DAG protocols have adopted the partial synchrony network assumption [40, 42, 44]. By pre-designating leader vertices (also referred to as anchors) and introducing timeouts into the rounds, these protocols facilitate a total ordering of the DAG through simple commit rules. State-of-the-art protocols leverage this approach to achieve near-optimal latency in the good case [6, 7, 40]. However, these performance gains often come at the cost of high communication complexity, which significantly constrains the scalability of DAG-based protocols. The high communication complexity in existing protocols stems from the structural requirement that each vertex must carry at least 𝑛 − 𝑓 references (counted as metadata). Given that 𝑂 (𝑛) vertices are disseminated per round— typically via Reliable Broadcast (RBC) [11] or Consistent Broadcast (CBC) [19]—the per-round metadata communication overhead amounts to at least Ω(𝑛 3 ) times the size of a single reference. When references are represented by signatures or hashes, this overhead scales to Ω(𝜆𝑛 3 ), where 𝜆 denotes the security parameter.

Feifan Wang, Jingfan Yu, Zixi Cai, and Zhixuan Fang

Table 1: Theoretical performance of partially synchronous DAG-based BFT protocols (after GST)

Protocol

Broadcast Primitive Used

LV Commit Latency

NLV (1) Commit Latency

Communication (2) Complexity (Good / Bad Case)

NLV Latency (3) Under Failure (Single / Consecutive)

Multiple Leaders

Bullshark [43]

Bracha’s RBC[11] CCBRB[2] Latency-optimal RBC[1] Narwhal’s CBC[19]

6𝛿 6𝛿 4𝛿 6𝛿

+6𝛿 +6𝛿 +4𝛿 +6𝛿

𝑂 (𝑛 4 ) 𝑂 (𝜆𝑛 3 ) ∗ 𝑂 (𝑛 4 ) 𝑂 (𝜆𝑛 3 )/𝑂 (𝜆𝑛 4 )

+(5Δ + 3𝛿 ) +(5Δ + 3𝛿 ) +(3Δ + 2𝛿 ) +(4Δ + 3𝛿 )

×

Shoal++ [6]

Bracha’s RBC[11] CCBRB[2] Latency-optimal RBC[1] Narwhal’s CBC[19]

4𝛿 4𝛿 3𝛿 4𝛿

+3𝛿 +3𝛿 +2𝛿 +3𝛿

𝑂 (𝑛 4 ) 𝑂 (𝜆𝑛 3 ) ∗ 𝑂 (𝑛 4 ) 𝑂 (𝜆𝑛 3 ) / 𝑂 (𝜆𝑛 4 )

+(5Δ + 3𝛿 ) +(5Δ + 3𝛿 ) +(3Δ + 2𝛿 ) +(4Δ + 3𝛿 )

✓

Sailfish [40]

Bracha’s RBC[11] CCBRB[2] Latency-optimal RBC[1] Narwhal’s CBC[19]

4𝛿 4𝛿 3𝛿 4𝛿

+3𝛿 +3𝛿 +2𝛿 +3𝛿

𝑂 (𝑛 4 ) 𝑂 (𝜆𝑛 3 ) ∗ 𝑂 (𝑛 4 ) 𝑂 (𝜆𝑛 3 ) / 𝑂 (𝜆𝑛 4 )

+(5Δ + 2𝛿 ) / +(7Δ + 2𝛿 ) +(5Δ + 2𝛿 ) / +(7Δ + 2𝛿 ) +(3Δ + 2𝛿 ) / +(4Δ + 2𝛿 ) +(4Δ + 2𝛿 ) / +(5Δ + 2𝛿 )

✓

Sparse Bullshark [4] Cordial Miners [34] Mysticeti [7]

Narwhal’s CBC[19] Best-effort Broadcast Best-effort Broadcast

6𝛿 3𝛿 3𝛿

+6𝛿 +3𝛿 +3𝛿

𝑂 (𝜆 2𝑛 2 ) / 𝑂 (𝜆 2𝑛 3 ) 𝑂 (𝜆𝑛 3 ) / 𝑂 (𝜆𝑛 4 ) 𝑂 (𝜆𝑛 3 ) / 𝑂 (𝜆𝑛 4 )

+(4Δ + 3𝛿 ) +6Δ +(4Δ + 2𝛿 )

× × ✓

Clownfish

Bracha’s RBC[11] CCBRB[2] Latency-optimal RBC[1] Narwhal’s CBC[19]

4𝛿 4𝛿 3𝛿 4𝛿

+3𝛿 +3𝛿 +2𝛿 +3𝛿

𝑶 (𝒏3 log 𝒏) 𝑂 (𝜆𝑛 3 ) ∗ 𝑶 (𝝀𝒏3 ) 𝑶 (𝝀𝒏2 )/𝑶 (𝝀𝒏3 )

+(5𝚫 + 𝜹 ) +(5𝚫 + 𝜹 ) +(3𝚫 + 𝜹 ) +(4𝚫 + 𝜹 )

✓

LV and NLV denote the leader vertex and non-leader vertex, respectively. (1) This column represents the additional commit latency required for an NLV relative to the LV of the same round. (2) This column represents the total metadata communication complexity per round. The terms “good case” and “bad case” indicate whether fetching missing data incurs additional communication overhead (relevant only when using Narwhal’s CBC or best-effort broadcast). (3) This column represents the additional latency imposed on an NLV by a Byzantine leader (relative to column (1)). The terms “single” and “consecutive” refer to scenarios involving a single or multiple consecutive Byzantine leaders, respectively (relevant only to Sailfish). ∗ Due to the use of erasure codes, the broadcast protocol incurs additional computational cost and larger vertex size. Blue text highlights where Clownfish demonstrates an advantage over other protocols (under specific broadcast primitives).

Existing DAG-based protocols usually amortize this high communication overhead by batching Ω(𝑛) transactions within each vertex. Leveraging erasure codes [20], this achieves amortized linear complexity per transaction. However, this approach faces two critical limitations. First, in many modern blockchain systems [5, 47], a lot of blocks (vertices) only contain few or even zero transactions. As 𝑛 increases, waiting to accumulate Ω(𝑛) transactions imposes prohibitive queueing latency, which is impractical. Second, even assuming sufficient transactions, since block sizes cannot increase indefinitely, this method remains unsustainable as 𝑛 scales [4]. Consequently, reducing the metadata communication complexity of DAG-based protocols is crucial for system scalability. This leads to a key research question: Can we reduce the metadata communication complexity of DAG-based protocols while maintaining the desired latency and throughput? Our solution. To achieve this goal, we design Clownfish, a partially synchronous DAG-based protocol built upon the state-of-the-art Sailfish [40] protocol. Clownfish’s key insight is that in DAG-based protocols, only leader vertices are directly committed and responsible for establishing paths to the ordered history, whereas non-leader vertices serve primarily to reference the leader vertex to enable its commitment. Based on this observation, Clownfish introduces a novel reference format termed the leader edge. This allows a nonleader vertex to reference only a single leader vertex via a leader edge, while the standard 𝑛 − 𝑓 references is maintained exclusively by leader vertices. Since each round contains one leader vertex and 𝑂 (𝑛) non-leader vertices, this approach effectively reduces the overall communication complexity.

Leveraging this core design, Clownfish further incorporates several enhancements. (i) Clownfish requires replicas to immediately broadcast a “no-vote” message upon a timeout. Coupled with an optimized round advancement rule, this reduces additional latency under failure cases. (ii) We extend Clownfish to Multi-leader Clownfish, which supports multiple leaders per round. By redesigning leader edges, Multi-leader Clownfish further reduces average latency while maintaining lower communication complexity. (iii) In addition to the standard RBC-based protocol, we also provide a CBC-based variant of Clownfish1 . This addresses a theoretical gap in prior DAG-based protocols, whose correctness under this weaker broadcast primitive is often not formally proved. In summary, Clownfish offers the following advantages: • Lower communication complexity. When using a latencyoptimal RBC [1], Clownfish achieves a per-round communication complexity of 𝑂 (𝜆𝑛 3 ), yielding a reduction factor of 𝑛𝜆 over state-of-the-art protocols. When using Narwhal’s CBC [19], it achieves 𝑂 (𝜆𝑛 2 ) communication per round, reducing the complexity by a factor of 𝑛. • Reduced additional latency under failures. By optimizing round advancement rule, Clownfish effectively minimizes the additional commit latency induced by faulty leaders or network asynchrony. • Broader compatibility. We design Clownfish and Multileader Clownfish based on both RBC and CBC. This compatibility stems from the fact that Clownfish’s core design is generically applicable to various broadcast primitives. 1 More precisely, this variant is built on the Narwhal’s CBC [19], which combines CBC with a random pulling mechanism.

Clownfish : Scaling DAG-based BFT Consensus via Sparse Edges

Table 1 presents a detailed comparison of the theoretical performance of Clownfish against other partially synchronous DAG-based protocols. Under the same broadcast primitive, Clownfish demonstrates advantages in both communication complexity and latency over existing protocols. Our empirical evaluation consists of both simulation and deployment studies. The simulation results show that Clownfish provides better scalability than existing DAG-based protocols at large system sizes. The deployment results under medium-scale systems and bandwidth-limited networks demonstrate that Clownfish achieves lower latency by reducing metadata communication. Organization. The rest of this paper is organized as follows. Section 2 introduces the model and background information on DAGbased BFT. Section 3 provides a technical overview of Clownfish. Section 4 and Section 5 detail and analyze Clownfish and Multileader Clownfish, respectively. Section 6 presents the results of our evaluation. We summarize the paper and provide further discussion in Section 7. Finally, we review related work in Section 8.

2 Preliminaries 2.1 Model We consider a system consisting of a fixed set of 𝑛 = 3𝑓 + 1 replicas. Let 𝑝𝑖 denote a specific replica, where 𝑖 ∈ {1, 2, . . . , 𝑛}. At most 𝑓 replicas are Byzantine and can act arbitrarily. The remaining replicas are referred to as honest. We assume the existence of an adversary capable of controlling all Byzantine replicas. We consider the standard partial synchrony model [21]. Specifically, there exists an unknown Global Stabilization Time (GST) and a known upper bound Δ on network delay, such that any message sent by an honest replica at time 𝑡 is guaranteed to arrive at its recipient by time max(𝐺𝑆𝑇 , 𝑡) + Δ. We further assume that after GST, the actual network delay 𝛿 satisfies 𝛿 ≤ Δ. Regarding cryptographic primitives, we assume the availability of a Public Key Infrastructure (PKI), cryptographic hash functions, and threshold/aggregate signatures [10]. We denote a message 𝑚 signed by 𝑝𝑖 as ⟨𝑚⟩𝑖 . We assume a computationally bounded adversary and let 𝜆 denote the security parameter for these primitives. Throughout this paper, we consider the setting where log 𝑛 < 𝜆 < 𝑛.

2.2

DAG-based BFT Consensus

We focus exclusively on certified DAG protocols under the partial synchrony model. The term “certified” implies that a vertex in the DAG must be delivered via Reliable Broadcast (RBC) or Consistent Broadcast (CBC), these primitives are introduced subsequently. Typically, DAG-based BFT protocols operate in rounds [19]. In each round, each replica can create a vertex containing a batch of transactions and a set of edges. To be deemed valid, a vertex in round 𝑟 is required to reference at least 2𝑓 + 1 delivered vertices from round 𝑟 −1. Upon the completion of RBC or CBC, the corresponding vertex is added to the DAG. Each replica maintains a local DAG view, which may differ from that of other replicas. However, both RBC and CBC guarantee non-equivocation, implying that vertices appearing at the same position within the DAG are identical. The edges in the DAG are utilized to commit and order vertices. We

define the causal history of a vertex as the subgraph originating from it, encompassing all predecessor vertices reachable via a path. Under the partial synchrony model, a pre-defined leader vertex is designated every few rounds (e.g., every round in Sailfish [40] and every two rounds in Bullshark [44]). Only leader vertices can be directly committed. The remaining non-leader vertices are ordered as part of the causal history of the committed leader vertices. To directly commit a leader vertex, a replica must observe sufficient “votes” for it. In the context of a DAG, edges from vertices in round 𝑟 + 1 to a leader vertex in round 𝑟 are interpreted as votes for it. Distinct protocols impose varying requirements regarding the quantity and format of these votes. For instance, Sailfish requires 2𝑓 + 1 first messages2 for 2𝑓 + 1 vertices, whereas Bullshark requires 𝑓 + 1 delivered vertices. Upon committing a leader vertex, a replica traverses its causal history based on the local DAG view and recursively checks for the existence of any uncommitted leader vertices reachable via a path. If such vertices exist, the replica must first indirectly commit the corresponding leader vertices. This ensures that all replicas derive the same committed-leader sequence and thus the same transaction order.

2.3

Problem Definition

In the context of DAG-based BFT, we focus on Byzantine Atomic Broadcast (BAB) problem. We use 𝑎_𝑏𝑐𝑎𝑠𝑡 (𝑚, 𝑟 ) to denote the event of a replica broadcasting a message 𝑚 with sequence number 𝑟 . We use 𝑎_𝑑𝑒𝑙𝑖𝑣𝑒𝑟 (𝑚, 𝑟, 𝑝𝑖 ) to denote the event of a replica delivering a message 𝑚 with sequence number 𝑟 originating from 𝑝𝑖 . Definition 1 (Byzantine atomic broadcast [33]). Each honest replica 𝑝𝑖 can call 𝑎_𝑏𝑐𝑎𝑠𝑡𝑖 (𝑚, 𝑟 ) and output 𝑎_𝑑𝑒𝑙𝑖𝑣𝑒𝑟𝑖 (𝑚, 𝑟, 𝑝𝑘 ). A Byzantine atomic broadcast protocol satisfies the following properties: - Agreement. If an honest replica 𝑝𝑖 outputs 𝑎_𝑑𝑒𝑙𝑖𝑣𝑒𝑟𝑖 (𝑚, 𝑟, 𝑝𝑘 ), then every honest replica 𝑝 𝑗 eventually outputs 𝑎_𝑑𝑒𝑙𝑖𝑣𝑒𝑟 𝑗 (𝑚, 𝑟, 𝑝𝑘 ). - Integrity. For every 𝑟 ∈ N and replica 𝑝𝑘 , an honest replica 𝑝𝑖 outputs 𝑎_𝑑𝑒𝑙𝑖𝑣𝑒𝑟𝑖 (𝑚, 𝑟, 𝑝𝑘 ) at most once regardless of 𝑚. - Validity. If an honest replica 𝑝𝑘 calls 𝑎_𝑏𝑐𝑎𝑠𝑡𝑘 (𝑚, 𝑟 ), then every honest replica eventually outputs 𝑎_𝑑𝑒𝑙𝑖𝑣𝑒𝑟 (𝑚, 𝑟, 𝑝𝑘 ). - Total order. If an honest replica 𝑝𝑖 outputs 𝑎_𝑑𝑒𝑙𝑖𝑣𝑒𝑟𝑖 (𝑚, 𝑟, 𝑝𝑘 ) before 𝑎_𝑑𝑒𝑙𝑖𝑣𝑒𝑟𝑖 (𝑚 ′, 𝑟 ′, 𝑝𝑘 ′ ), then no honest replica 𝑝 𝑗 outputs 𝑎_𝑑𝑒𝑙𝑖𝑣𝑒𝑟 𝑗 (𝑚 ′, 𝑟 ′, 𝑝𝑘 ′ ) before 𝑎_𝑑𝑒𝑙𝑖𝑣𝑒𝑟 𝑗 (𝑚, 𝑟, 𝑝𝑘 ). We also introduce the two fundamental broadcast primitives employed in DAG construction: Reliable broadcast (RBC). Let 𝑟 _𝑏𝑐𝑎𝑠𝑡 (𝑚, 𝑟 ) and 𝑟 _𝑑𝑒𝑙𝑖𝑣𝑒𝑟 (𝑚, 𝑟, 𝑝𝑘 ) denote the events of broadcasting and delivering a message 𝑚 with round number 𝑟 , respectively. The RBC primitive satisfies the Agreement, Integrity, and Validity properties defined in Definition 1. We outline the properties satisfied by an RBC protocol after GST in Property 1. Note that 𝑘 1 and 𝑘 2 are RBC-related parameters that vary across different RBC protocols [1, 2, 11, 20]. Property 1. Let 𝑡 and 𝑡 ′ be times after GST. (i) If an honest replica reliably broadcasts a vertex 𝑣 at time 𝑡, then all honest replicas will deliver 𝑣 by time 𝑡 + 𝑘 1 Δ. (ii) If an honest replica delivers a vertex 𝑣 ′ at time 𝑡 ′ , then all honest replicas will deliver 𝑣 ′ by time 𝑡 ′ + 𝑘 2 Δ. 2 Here, a “first message” denotes the message broadcast in the first stage of the under-

lying RBC or CBC. At this stage, the vertex is not yet considered delivered.

Feifan Wang, Jingfan Yu, Zixi Cai, and Zhixuan Fang

Consistent broadcast (CBC). CBC is a broadcast primitive weaker than RBC [14]. It satisfies the Validity and Integrity properties defined in Definition 1, but substitutes the Agreement property with the following Consistency property: - Consistency. If an honest replica 𝑝𝑖 outputs 𝑐_𝑑𝑒𝑙𝑖𝑣𝑒𝑟𝑖 (𝑚, 𝑟, 𝑝𝑘 ) and another honest replica 𝑝 𝑗 outputs 𝑐_𝑑𝑒𝑙𝑖𝑣𝑒𝑟 𝑗 (𝑚 ′, 𝑟, 𝑝𝑘 ), then 𝑚 = 𝑚′ . A CBC protocol satisfies only the part (i) of Property 1.

2.4

Efficiency Measure

Communication complexity. We focus on metadata communication complexity, where metadata consists of DAG edges and other consensus messages, excluding the transaction payload. The reasons are twofold. First, metadata communication complexity asymptotically dominates the overall communication complexity and thus reflects the protocol’s scalability. Second, since blocks in many practical systems contain only a small transaction payload [5, 47] or merely lightweight transaction availability certificates or batch digests [19, 26], metadata still accounts for a substantial portion of communication and computation overhead. Therefore, we evaluate the total number of metadata bits transmitted by all honest replicas per round, which more fundamentally reflects the protocol’s scalability. Latency. We focus on the latency measured from the time a vertex is broadcast until it is committed by an honest replica. We exclude the queuing latency as it depends on whether using a worker layer and assumptions regarding transaction batch sizes and arrival rates.

3

Technical Overview of Clownfish

Building upon the foundation of Sailfish [40], Clownfish employs several techniques to improve protocol performance. We outline the key idea, the challenges, and our solutions in this section. The key idea. The high communication complexity of DAG-based BFT protocols stems from the requirement that every vertex— whether a leader vertex or not—needs to carry at least 𝑛 − 𝑓 references to vertices from the previous round. However, a key observation is that the commit and ordering process in DAG-based BFT protocols is driven primarily by leader vertices. This implies that the edges in the vast majority of non-leader vertices are redundant. Leveraging this insight, Clownfish decreases the number of edges in non-leader vertices from 𝑂 (𝑛) to 𝑂 (1). Since there is at most one leader vertex among 𝑛 vertices in each round, this strategy effectively reduces the communication complexity. The main technical challenge. The safety of DAG-based BFT protocols hinges on the guarantee that a path exists between any committed leader vertex 𝐿𝑉𝑟 in round 𝑟 and a subsequent leader vertex 𝐿𝑉𝑟 ′ in round 𝑟 ′ > 𝑟 . In the safety proofs of Sailfish [40], once the base cases where 𝑟 ′ ≤ 𝑟 + 2 are established, the existence of paths for cases where 𝑟 ′ > 𝑟 + 2 follows straightforwardly from transitivity. However, this property ceases to hold when we naively restrict non-leader vertices to reference only the leader vertex of the previous round. To illustrate this, consider a possible execution depicted in Figure 1. Suppose that due to network asynchrony or Byzantine behavior, the leader vertices 𝐿𝑉𝑟 +1 and 𝐿𝑉𝑟 +2 are not

delivered in the view of all replicas. This implies that the vertices created by all non-leader replicas in round 𝑟 + 2 will not contain any edges3 . This causes the DAG to become structurally “disconnected” (indicated by the red line in the figure). Consequently, the leader vertices in round 𝑟 +3 and subsequent rounds are unable to establish a path to 𝐿𝑉𝑟 (except potentially via non-essential weak edges). Our main solution: Ensuring connectivity via leader edge. To address the above challenge, Clownfish introduces the concept of leader edge. Specifically, a leader edge allows a replica to reference the leader vertex that was most recently delivered locally before the creation of its current vertex, rather than being restricted to the leader vertex of the previous round. With each non-leader vertex referencing a single leader via a leader edge, Clownfish efficiently guarantee paths between leader vertices (see Figure 2 for an illustration). Intuitively, the leader edge plays a role analogous to the “highest lock” in leader-based BFT protocols [37, 50]. Reducing additional latency under failure cases. In Sailfish [40], replicas are required to sequentially transmit timeout and no-vote messages upon a timeout, incurring two additional message delays. To overcome this limitation, Clownfish consolidates the timeout and no-vote messages found in Sailfish. In Clownfish, upon a timeout, a replica can immediately broadcast a no-vote message to signal that it will not reference the corresponding leader vertex via a leader edge. However, such a direct merger poses a threat to liveness (see Section 4.1 for further discussion). Clownfish addresses this issue through the fast-vote message. Intuitively, fast-vote permits replicas to cast lightweight votes for leader vertices in skipped rounds to help ensure they are committed. Clownfish also provides more efficient round-skipping rules that enable lagging replicas to leverage messages from fast replicas to advance to the latest round. Utilizing different broadcast primitives for protocol design. We first design the Clownfish prsotocol built upon standard RBC. It is intuitive and allows for flexible tradeoffs between latency and communication depending on the specific RBC implementation used. We further design a CBC-based Clownfish, which fills the theoretical gap in existing DAG-based protocols that lack a corresponding correctness proof. It utilizes an explicit round synchronization mechanism to ensure that the critical path of consensus is not obstructed by data fetching. In conjunction with a delayed timer design, it maintains a short timeout duration. It can achieve amortized linear complexity without batching Ω(𝑛) transactions in vertices. Supporting multiple leaders per round. Consistent with recent protocols [6, 40, 51], we extend Clownfish to a multi-leader variant (Multi-leader Clownfish) to reduce average latency. We adopt a strategy that differentiates between main leader and secondary leader to balance waiting times against leader quantity. Under this strategy, only a main leader is responsible for establishing paths to previous leader vertices, while secondary leaders share the same structure as non-leader vertices. This allows for a seamless adaptation of the leader edge design. By interpreting a single leader edge as a vote for multiple leader vertices, we modify the commit rules to enable committing multiple leader vertices within the same round. 3 This arises because we require vertices to reference exclusively the previous leader.

Clownfish : Scaling DAG-based BFT Consensus via Sparse Edges

Figure 1: Illustration of the challenge. Here, 𝑛 = 4 and 𝑓 = 1, with a pre-designated leader assigned for each round. A strong edge denotes a reference to a vertex in the previous round. According to the commit rule in Sailfish [40], 𝐿𝑉𝑟 is committed as it receives 2𝑓 + 1 votes. (1) The left side depicts an execution in Sailfish. Since all vertices reference at least 2𝑓 + 1 vertices from the previous round, a path exists from 𝐿𝑉𝑟 +3 to 𝐿𝑉𝑟 . (2) The right side depicts an execution where non-leader vertices are restricted to reference only the leader vertex of the previous round. In this case, 𝐿𝑉𝑟 +3 fails to establish a path to 𝐿𝑉𝑟 . Consequently, Multi-leader Clownfish improves average latency while preserving low communication complexity.

4

The Clownfish Protocol

In this section, we present the Clownfish protocol. We provide a detailed description of Clownfish in Section 4.1, analyze its theoretical properties in Section 4.2, and finally discuss the CBC-based variant of Clownfish in Section 4.3.

4.1

Protocol Description

In Clownfish, the DAG is partitioned into a sequence of numbered rounds. Each round is assigned a designated leader, which is selected via a deterministic mechanism. We denote the leader of round 𝑟 as 𝐿𝑟 , and the vertex created by 𝐿𝑟 as 𝐿𝑉𝑟 . DAG components. The data structures and basic utilities of Clownfish are presented in Algorithm 1, with our modifications over Sailfish [40] highlighted in magenta. In each round, each replica is permitted to propose one vertex containing a block of transactions (which may be empty). Each vertex must also include a set of edges to integrate into the DAG. All vertices are disseminated via RBC. Crucially, only leader vertices are required to reference at least 2𝑓 + 1 vertices from the previous round via strong edges. A leader vertex may also references up to 𝑓 vertices from earlier rounds to which a path has not yet been established via weak edges. All vertices must reference a leader vertex via a leader edge. Optionally, a vertex may also reference vertices previously created by its creator via self edges. In particular, a leader vertex may additionally be required to carry a no-vote certificate (𝑁𝑉𝐶) regarding the leader of the previous round via 𝑣.𝑛𝑣𝑐. We elaborate on these elements in the DAG construction subsection. We define a path as a connection between two vertices established via any of the aforementioned four types of edges (Line 1). A

Figure 2: Illustration of Clownfish. 𝐿𝑉𝑟 −1 and 𝐿𝑉𝑟 are directly committed. The vertices created by replicas 𝑝 1 and 𝑝 4 in round 𝑟 +2 reference 𝐿𝑉𝑟 via leader edges. In addition to 2𝑓 +1 strong edges, 𝐿𝑉𝑟 +3 provides 𝑁𝑉𝐶𝑟 +2 to prove that 𝐿𝑉𝑟 +2 cannot be directly committed. Together, strong edges and leader edges constitute a leader path between 𝐿𝑉𝑟 +3 and 𝐿𝑉𝑟 . leader path specifically denotes a path between two leader vertices consisting of leader edges and strong edges (Line 3). Each replica maintains a local view of the DAG. Upon the completion of the RBC, the replica adds the vertex and its edges to its local DAG based on the corresponding source and round. Although the DAG views of all replicas may differ at any specific point in time, the RBC primitive guarantees their eventual consistency. In addition to vertices, Clownfish introduces a struct called fastvote. A fast-vote specifies the round, the source, and the target leader

Feifan Wang, Jingfan Yu, Zixi Cai, and Zhixuan Fang

Algorithm 1 Clownfish’s data structures and basic utilities for replica 𝑝𝑖 Local variables: struct vertex 𝑣 : ⊲ The struct of a vertex in the DAG 𝑣.𝑟𝑜𝑢𝑛𝑑 - the round of 𝑣 in the DAG 𝑣.𝑠𝑜𝑢𝑟𝑐𝑒 - the replica that broadcasts 𝑣 𝑣.𝑏𝑙𝑜𝑐𝑘 - a block of transactions 𝑣.𝑠𝑡𝑟𝑜𝑛𝑔𝐸𝑑𝑔𝑒𝑠 - a set of vertices in 𝑣.𝑟𝑜𝑢𝑛𝑑 − 1 that represent strong edges ⊲ Only leader vertices need to contain 𝑣.𝑤𝑒𝑎𝑘𝐸𝑑𝑔𝑒𝑠 - a set of vertices in rounds < 𝑣.𝑟𝑜𝑢𝑛𝑑 − 1 that represent weak edges ⊲ Only leader vertices need to contain 𝑣.𝑙𝑒𝑎𝑑𝑒𝑟 𝐸𝑑𝑔𝑒 - a leader vertex in round ≤ 𝑣.𝑟𝑜𝑢𝑛𝑑 − 1 that represents a leader edge 𝑣.𝑠𝑒𝑙 𝑓 𝐸𝑑𝑔𝑒𝑠 - a set of vertices in rounds ≤ 𝑣.𝑟𝑜𝑢𝑛𝑑 − 1 that represent self edges (created by 𝑝𝑖 ) 𝑣.𝑛𝑣𝑐 - a no-vote certificate for 𝑣.𝑟𝑜𝑢𝑛𝑑 − 1 (if any) ⊲ Only leader vertices need to contain struct fast-vote 𝑓 𝑣 : ⊲ The struct of a fast-vote for a previous leader vertex 𝑓 𝑣.𝑟𝑜𝑢𝑛𝑑 - the round of 𝑓 𝑣 𝑓 𝑣.𝑠𝑜𝑢𝑟𝑐𝑒 - the replica that broadcasts 𝑓 𝑣 𝑓 𝑣.𝑙𝑒𝑎𝑑𝑒𝑟 - leader vertex that the replica votes for 𝐷𝐴𝐺𝑖 [ ] - An array of sets of vertices (indexed by rounds) 𝐹𝑉𝑖 [ ] - An array of sets of fast-votes (indexed by rounds) 𝑏𝑙𝑜𝑐𝑘𝑠𝑇 𝑜𝑃𝑟𝑜𝑝𝑜𝑠𝑒 - A queue, initially empty, 𝑝𝑖 enqueues valid blocks of transactions from clients 𝑙𝑎𝑠𝑡𝐿𝑒𝑎𝑑𝑒𝑟 - The most recent delivered leader vertex for which a no-vote has not been sent 𝑜𝑙𝑑𝑉 𝑒𝑟𝑡𝑖𝑐𝑒𝑠 - The own vertices (created by 𝑝𝑖 ) that have been delivered but not yet referenced 1: procedure path(𝑣, 𝑢 ) ⊲ Check if exists a path consisting of all kinds of edges in the DAG 2: return exists a sequence of 𝑘 ∈ N, vertices 𝑣Ð 1 , . . . , 𝑣𝑘 s.t. 𝑣1 = 𝑣 , 𝑣𝑘 = 𝑢 , and ∀ 𝑗 ∈ [2, .., 𝑘 ] : 𝑣 𝑗 ∈ 𝑟 ≥1 𝐷𝐴𝐺𝑖 [𝑟 ] ∧ (𝑣 𝑗 ∈ 𝑣 𝑗 −1 .𝑤𝑒𝑎𝑘𝐸𝑑𝑔𝑒𝑠 ∪ 𝑣 𝑗 −1 .𝑠𝑡𝑟𝑜𝑛𝑔𝐸𝑑𝑔𝑒𝑠 ∪ 𝑣 𝑗 −1 .𝑙𝑒𝑎𝑑𝑒𝑟 𝐸𝑑𝑔𝑒 ∪ 𝑣 𝑗 −1 .𝑠𝑒𝑙 𝑓 𝐸𝑑𝑔𝑒𝑠 ) 3: procedure leader_path(𝑣, 𝑢 ) ⊲ Check if exists a path consisting of leader edges and strong edges from leader vertex 𝑣 to leader vertex 𝑢 4: return exists a sequence of 𝑘 ∈ N, vertices 𝑣Ð 1 , . . . , 𝑣𝑘 s.t. 𝑣1 = 𝑣 , 𝑣𝑘 = 𝑢 , and ∀ 𝑗 ∈ [2, .., 𝑘 ] : 𝑣 𝑗 ∈ 𝑟 ≥1 𝐷𝐴𝐺𝑖 [𝑟 ] ∧ (𝑣 𝑗 ∈ 𝑣 𝑗 −1 .𝑙𝑒𝑎𝑑𝑒𝑟 𝐸𝑑𝑔𝑒 ∪ 𝑣 𝑗 −1 .𝑠𝑡𝑟𝑜𝑛𝑔𝐸𝑑𝑔𝑒𝑠 ) 5: procedure set_weak_edges(𝑣, 𝑟 ) 6: 𝑣.𝑤𝑒𝑎𝑘𝐸𝑑𝑔𝑒𝑠 ← { } 7: for 𝑟 ′ = 𝑟 − 2 down to 1 do 8: for every 𝑢 ∈ 𝐷𝐴𝐺𝑖 [𝑟 ′ ] s.t. ¬path(𝑣, 𝑢 ) do 9: 𝑣.𝑤𝑒𝑎𝑘𝐸𝑑𝑔𝑒𝑠 ← 𝑣.𝑤𝑒𝑎𝑘𝐸𝑑𝑔𝑒𝑠 ∪ {𝑢 } 10: procedure set_self_edges(𝑣 ) 11: 𝑣.𝑠𝑒𝑙 𝑓 𝐸𝑑𝑔𝑒𝑠 ← { } 12: for every 𝑢 ∈ 𝑜𝑙𝑑𝑉 𝑒𝑟𝑡𝑖𝑐𝑒𝑠 s.t. ¬path(𝑣, 𝑢 ) do 13: 𝑣.𝑠𝑒𝑙 𝑓 𝐸𝑑𝑔𝑒𝑠 ← 𝑣.𝑠𝑒𝑙 𝑓 𝐸𝑑𝑔𝑒𝑠 ∪ {𝑢 } 14: 𝑜𝑙𝑑𝑉 𝑒𝑟𝑡𝑖𝑐𝑒𝑠 ← 𝑜𝑙𝑑𝑉 𝑒𝑟𝑡𝑖𝑐𝑒𝑠\{𝑢 }

15: procedure set_leader_edge(𝑣 ) 16: 𝑣.𝑙𝑒𝑎𝑑𝑒𝑟 𝐸𝑑𝑔𝑒 ← 𝑙𝑎𝑠𝑡𝐿𝑒𝑎𝑑𝑒𝑟 17: procedure get_vertex(𝑝, 𝑟 ) 18: if ∃𝑣 ∈ 𝐷𝐴𝐺𝑖 [𝑟 ] s.t. 𝑣.𝑠𝑜𝑢𝑟𝑐𝑒 = 𝑝 then 19: return 𝑣 20: return ⊥ 21: procedure get_leader_vertex(𝑟 ) 22: return get_vertex(𝐿𝑟 , 𝑟 ) 23: procedure a_bcast𝑖 (𝑏 ) 24: 𝑏𝑙𝑜𝑐𝑘𝑠𝑇 𝑜𝑃𝑟𝑜𝑝𝑜𝑠𝑒.enqueue(𝑏 )

vertex for which the vote is intended. As detailed in the subsequent subsection, this type of message is created exclusively during roundskipping scenarios. Their objective is to help committing the leader vertices from preceding rounds.

The leader vertex 𝐿𝑉𝑟 is required to include at least 2𝑓 + 1 strong edges referencing vertices from round 𝑟 − 1 (Line 61). To ensure safety, 𝐿𝑉𝑟 must either reference 𝐿𝑉𝑟 −1 via a strong edge or provide 𝑁𝑉𝐶𝑟 −1 to prove that 𝐿𝑉𝑟 −1 failed to obtain sufficient votes for being committed (Line 63). In addition, 𝐿𝑉𝑟 may reference vertices from rounds prior to 𝑟 − 1 via weak edges to ensure their eventual inclusion in the DAG (Line 64). We prohibit non-leader vertices from setting weak edges to maintain their size. This results in a sparser DAG, implying that straggling vertices may experience increased latency before being included in the causal history of a leader vertex. To mitigate this issue, we permit a replica to reference a constant number of delivered vertices created by itself via self edges (Line 65). This ensures that once the new vertex is referenced, these historical vertices are included in the causal history. These vertices are tracked in the 𝑜𝑙𝑑𝑉 𝑒𝑟𝑡𝑖𝑐𝑒𝑠 set and are removed upon being referenced. Note that self edges serve solely as a practical optimization and are not required for the protocol’s correctness.

DAG construction protocol. The DAG construction protocol of Clownfish is presented in Algorithm 2. Upon delivering 2𝑓 + 1 vertices in round 𝑟 (Line 35), replica 𝑝𝑖 advances to round 𝑟 + 1 and creates a new vertex if it has delivered 𝐿𝑉𝑟 or received a no-vote certificate for round 𝑟 (denoted as 𝑁𝑉𝐶𝑟 ). A no-vote certificate is composed of 2𝑓 + 1 no-vote messages (which can be aggregated using threshold signature). Upon entering a new round, 𝑝𝑖 starts a timer of duration 𝜏 (Line 87). If 𝑝𝑖 times out while waiting for 𝐿𝑉𝑟 in round 𝑟 , it broadcasts a ⟨no-vote, 𝑟 ⟩𝑖 message (Line 43). When 𝑝𝑖 receives 𝑁𝑉𝐶𝑟 , it forwards the certificate to all replicas (Line 47). Any replica that has broadcast ⟨no-vote, 𝑟 ⟩ is prohibited from referencing 𝐿𝑉𝑟 via a leader edge (Line 49), as a no-vote represents a commitment to withhold its vote for 𝐿𝑉𝑟 . To create a vertex 𝑣 for round 𝑟 , 𝑝𝑖 first include a block of transactions. Crucially, 𝑣 must reference the most recently delivered leader vertex via a leader edge for which 𝑝𝑖 has not previously broadcast a no-vote message (Line 59). This state is tracked using the 𝑙𝑎𝑠𝑡𝐿𝑒𝑎𝑑𝑒𝑟 variable (Line 50). Specifically, if 𝑣 references 𝐿𝑉𝑟 −1 via leader edge, it constitutes a “vote" for 𝐿𝑉𝑟 −1 . The vote can be used to commit 𝐿𝑉𝑟 −1 , as we will elaborate shortly. If 𝑣 references a leader vertex from a round prior to 𝑟 − 1, the leader edge serves solely to establish the leader path to subsequent leader vertices.

Round synchronization. To ensure liveness, partially synchronous DAG-based protocols require that, all honest replicas enter the same round within a bounded time [7, 38, 40] after GST. We refer to this property as round synchronization. To achieve this, we must enable straggling replicas to advance directly to the latest round, a mechanism we term round-skipping. In Algorithm 2, we present two distinct rules for round-skipping. The first rule is the same as Sailfish [40]. When a replica 𝑝𝑖 delivers 2𝑓 + 1 vertices from round 𝑟 , and has delivered 𝐿𝑉𝑟 or received

Clownfish : Scaling DAG-based BFT Consensus via Sparse Edges

Algorithm 2 Clownfish’s DAG construction protocol for replica 𝑝𝑖 Local variables: 𝑟𝑜𝑢𝑛𝑑 ← 1; buffer ← { } 25: upon r_deliver𝑖 (𝑣, 𝑟, 𝑝 ) do 26: if 𝑣.𝑠𝑜𝑢𝑟𝑐𝑒 = 𝑝 ∧ 𝑣.𝑟𝑜𝑢𝑛𝑑 = 𝑟 ∧ is_valid (𝑣) then 27: if ¬try_add_to_dag(𝑣 ) then 28: buffer ← buffer ∪ {𝑣 } 29: else 30: for 𝑣 ′ ∈ buffer : 𝑣 ′ .𝑟𝑜𝑢𝑛𝑑 ≥ 𝑟 do 31: try_add_to_dag(𝑣 ′ ) 32: upon receiving ⟨ 𝑓 𝑣, 𝑟, ⟩𝑝 do 33: if 𝑓 𝑣.𝑟𝑜𝑢𝑛𝑑 = 𝑟 ∧ is_valid ( 𝑓 𝑣) then 34: 𝐹𝑉𝑖 [𝑟 ] ← 𝐹𝑉𝑖 [𝑟 ] ∪ { 𝑓 𝑣 } 35: upon |𝐷𝐴𝐺𝑖 [𝑟 ] | ≥ 2𝑓 + 1 ∧ (∃𝑣 ′ ∈ 𝐷𝐴𝐺𝑖 [𝑟 ] : 𝑣 ′ .𝑠𝑜𝑢𝑟𝑐𝑒 = 𝐿𝑟 ∨ 𝑁𝑉 𝐶𝑟 is received ) for 𝑟 ≥ 𝑟𝑜𝑢𝑛𝑑 do 36: if 𝑟 > 𝑟𝑜𝑢𝑛𝑑 then ⊲ Skip to a higher round (rule 1) 37: send_fast_vote(𝑟𝑜𝑢𝑛𝑑 + 1, 𝑟 ) 38: advance_round(𝑟 + 1) 39: upon receiving a set M of ≥ 𝑓 + 1 first messages for round 𝑟 + 1 vertices ∧ ( ∃𝑣 ′ ∈ 𝐷𝐴𝐺𝑖 [𝑟 ] : 𝑣 ′ .𝑠𝑜𝑢𝑟𝑐𝑒 = 𝐿𝑟 ∨ 𝑁𝑉 𝐶𝑟 is received) for 𝑟 ≥ 𝑟𝑜𝑢𝑛𝑑 do 40: if 𝑟 > 𝑟𝑜𝑢𝑛𝑑 then ⊲ Skip to a higher round (rule 2) 41: send_fast_vote(𝑟𝑜𝑢𝑛𝑑 + 1, 𝑟 ) 42: advance_round(𝑟 + 1) 43: upon timeout in 𝑟𝑜𝑢𝑛𝑑 do 44: if š𝑣 ′ ∈ 𝐷𝐴𝐺𝑖 [𝑟𝑜𝑢𝑛𝑑 ] : 𝑣 ′ .𝑠𝑜𝑢𝑟𝑐𝑒 = 𝐿𝑟𝑜𝑢𝑛𝑑 then 45: broadcast ⟨no-vote, 𝑟𝑜𝑢𝑛𝑑 ⟩𝑖 46: upon receiving 𝑁𝑉 𝐶𝑟 for 𝑟 ≥ 𝑟𝑜𝑢𝑛𝑑 do 47: broadcast 𝑁𝑉 𝐶𝑟 48: upon r_deliver𝑖 (𝐿𝑉𝑟 , 𝑟, 𝐿𝑟 ) for 𝑟 > 𝑙𝑎𝑠𝑡𝐿𝑒𝑎𝑑𝑒𝑟 .𝑟𝑜𝑢𝑛𝑑 do 49: if haven’t sent ⟨no-vote, 𝑟 ⟩𝑖 before then 50: 𝑙𝑎𝑠𝑡𝐿𝑒𝑎𝑑𝑒𝑟 ← 𝐿𝑉𝑟 51: procedure broadcast_vertex(𝑟 ) 52: 𝑣 ← create_new_vertex(𝑟 ) 53: try_add_to_dag(𝑣 ) 54: r_bcast𝑖 (𝑣, 𝑟 )

55: procedure create_new_vertex(𝑟 ) 56: 𝑣.𝑟𝑜𝑢𝑛𝑑 ← 𝑟 57: 𝑣.𝑠𝑜𝑢𝑟𝑐𝑒 ← 𝑝𝑖 58: 𝑣.𝑏𝑙𝑜𝑐𝑘 ← 𝑏𝑙𝑜𝑐𝑘𝑠𝑇 𝑜𝑃𝑟𝑜𝑝𝑜𝑠𝑒 .dequeue() 59: set_leader_edge(𝑣 ) 60: if 𝑝𝑖 = 𝐿𝑟 then 61: 𝑣.𝑠𝑡𝑟𝑜𝑛𝑔𝐸𝑑𝑔𝑒𝑠 ← 𝐷𝐴𝐺𝑖 [𝑟 − 1] 62: if š𝑣 ′ ∈ 𝐷𝐴𝐺𝑖 [𝑟 − 1] : 𝑣 ′ .𝑠𝑜𝑢𝑟𝑐𝑒 = 𝐿𝑟 −1 then 63: 𝑣.𝑛𝑣𝑐 ← 𝑁𝑉 𝐶𝑟 −1 64: set_weak_edges(𝑣, 𝑟 ) 65: set_self_edges(𝑣 ) 66: return 𝑣 67: procedure create_fast_vote(𝑟 ) 68: 𝑓 𝑣.𝑟𝑜𝑢𝑛𝑑 ← 𝑟 69: 𝑓 𝑣.𝑠𝑜𝑢𝑟𝑐𝑒 ← 𝑝𝑖 70: 𝑓 𝑣.𝑙𝑒𝑎𝑑𝑒𝑟 ← 𝐿𝑟 −1 71: return 𝑓 𝑣 72: procedure send_fast_vote(𝑠𝑡𝑎𝑟𝑡, 𝑒𝑛𝑑 ) 73: start 𝑡𝑖𝑚𝑒𝑟 for fast-vote ⊲ Start fast-vote timer 𝜏 ′ 74: for 𝑟 ′ = 𝑠𝑡𝑎𝑟𝑡 up to 𝑒𝑛𝑑 simultaneously do 75: if r_deliver𝑖 (𝐿𝑉𝑟 ′ −1 , 𝑟 ′ − 1, 𝐿𝑟 ′ −1 ) before timeout ∧ 𝑁𝑉 𝐶𝑟 ′ −1 is not received ∧ haven’t sent ⟨no-vote, 𝑟 ⟩𝑖 before then 76: 𝑓 𝑣 ← create_fast_vote(𝑟 ′ ) 77: broadcast ⟨𝑓 𝑣, 𝑟 ′ ⟩𝑖 78: procedure try_add_to_dag(𝑣 ) 79: if ∀𝑣 ′ ∈ 𝑣.𝑠𝑟𝑜𝑛𝑔𝐸𝑑𝑔𝑒𝑠 Ð∪ 𝑣.𝑤𝑒𝑎𝑘𝐸𝑑𝑔𝑒 ∪ 𝑣.𝑙𝑒𝑎𝑑𝑒𝑟 𝐸𝑑𝑔𝑒 ∪ 𝑣.𝑠𝑒𝑙 𝑓 𝐸𝑑𝑔𝑒𝑠 : 𝑣 ′ ∈ 𝑘 ≥1 𝐷𝐴𝐺𝑖 [𝑘 ] then 80: 𝐷𝐴𝐺𝑖 [𝑣.𝑟𝑜𝑢𝑛𝑑 ] ← 𝐷𝐴𝐺𝑖 [𝑣.𝑟𝑜𝑢𝑛𝑑 ] ∪ {𝑣 } 81: buffer ← buffer \ {𝑣 } 82: return true 83: return false 84: procedure advance_round(𝑟 ) 85: if 𝑝𝑖 = 𝐿𝑟 then 86: wait until |𝐷𝐴𝐺𝑖 [𝑟 − 1] | ≥ 2𝑓 + 1 87: 𝑟𝑜𝑢𝑛𝑑 ← 𝑟 ; start 𝑡𝑖𝑚𝑒𝑟 for 𝑟𝑜𝑢𝑛𝑑 ⊲ Start round timer 𝜏 88: broadcast_vertex(𝑟𝑜𝑢𝑛𝑑 )

𝑁𝑉𝐶𝑟 , 𝑝𝑖 can directly enter round 𝑟 + 1 (Line 35). The second rule is slightly different. When 𝑝𝑖 receives the first message of the RBC for round 𝑟 + 1 from at least 𝑓 + 1 distinct replicas, and either delivered 𝐿𝑉𝑟 or reveived 𝑁𝑉𝐶𝑟 , 𝑝𝑖 can skip to round 𝑟 + 1 (Line 39). The intuition is that among the earliest set of 𝑓 + 1 first messages, at least one must be sent by an honest replica. This honest replica must have necessarily delivered 2𝑓 + 1 vertices from round 𝑟 and possesses either 𝐿𝑉𝑟 or 𝑁𝑉𝐶𝑟 . Given that non-leader vertices in Clownfish are only required to provide a leader edge, they can proceed to round 𝑟 + 1 immediately. This rule allows slow replicas to catch up faster, and in particular, it significantly reduces the timeout duration in the CBC-based version (see Section 4.3). Fast-votes are triggered after round-skipping (Lines 37, 41). Although a replica skipping from round 𝑟 ′ to 𝑟 does not propose vertices for the intermediate rounds, it needs to create and broadcast fast-votes for these rounds when necessary. Specifically, after skipping rounds, the replica starts a timer of duration 𝜏 ′ (Line 73). For any leader vertex of a skipped round, the replica must await its delivery prior to the timeout, unless the corresponding 𝑁𝑉𝐶 has already been received or no-vote has been sent. If the replica delivers a 𝐿𝑉 within this duration, it broadcasts a fast-vote for that leader (Lines 75–77). A fast-vote is also treated as a vote for the leader vertex and is utilized in the commit process. This mechanism is pivotal for guaranteeing liveness, as discussed later.

DAG commit rule. The commit rule of Clownfish is presented in Algorithm 3. Only leader vertices are explicitly committed. Nonleader vertices appearing in the causal history of a committed leader are ordered according to a specified deterministic rule (Line 105). When 𝑝𝑖 receives at least 2𝑓 + 1 “votes” for the leader vertex of round 𝑟 , it directly commits 𝐿𝑉𝑟 . A valid vote comprises either the first message (of the RBC) for a round 𝑟 + 1 vertex that references 𝐿𝑉𝑟 , or a fast-vote from round 𝑟 + 1 (Line 89). Since 𝑝𝑖 may deliver a vertex prior to its corresponding first message, we also recognize the delivered vertex as a valid vote. The intuition behind the threshold of 2𝑓 + 1 votes is that at least 𝑓 + 1 of these votes must originate from honest replicas. This sufficiently precludes the existence of 𝑁𝑉𝐶𝑟 . Together with the constraints imposed on leader vertices, this guarantees that any subsequent leader vertex will establish a leader path to the committed 𝐿𝑉𝑟 . Prior to directly committing a leader vertex, 𝑝𝑖 recursively commits all uncommitted leader vertices from earlier rounds that are connected via a leader path (Lines 97–103). This indirect committing rule is essential for preserving total order property. The Necessity of fast-votes. We illustrate how fast-votes resolve the liveness issue through the following example (Figure 7 in Appendix A). Consider an execution where 𝑓 + 1 honest replicas and 𝑓 Byzantine replicas have advanced to round 𝑟 + 1, while the remaining 𝑓 honest replicas lag behind at round 𝑟 ′ ≤ 𝑟 . In Clownfish, Byzantine replicas can deliberately omit references to 𝐿𝑉𝑟 in their round 𝑟 + 1 vertices. Once the 𝑓 Byzantine replicas and the 𝑓 + 1 fast

Feifan Wang, Jingfan Yu, Zixi Cai, and Zhixuan Fang

Algorithm 3 Clownfish’s commit rule for replica 𝑝𝑖 Local variables: 𝑐𝑜𝑚𝑚𝑖𝑡𝑡𝑒𝑑𝑅𝑜𝑢𝑛𝑑 ← 0 𝑑𝑒𝑙𝑖𝑣𝑒𝑟𝑒𝑑𝑉 𝑒𝑟𝑡𝑖𝑐𝑒𝑠 ← { } 𝑙𝑒𝑎𝑑𝑒𝑟𝑆𝑡𝑎𝑐𝑘 ← initialize empty stack 89: upon receiving a set M of first messages for round 𝑟 + 1 vertices s.t. ′ ∀𝑣 ∈ M : (∃𝑣 ∈ (𝑣 ′ .𝑙𝑒𝑎𝑑𝑒𝑟 𝐸𝑑𝑔𝑒 ∪ 𝑣 ′ .𝑠𝑡𝑟𝑜𝑛𝑔𝐸𝑑𝑔𝑒𝑠 )∧ 𝑣.𝑟𝑜𝑢𝑛𝑑 = 𝑟 ∧ 𝑣.𝑠𝑜𝑢𝑟𝑐𝑒 = 𝐿𝑟 ) ∧ ( | M | + |𝐹𝑉𝑖 [𝑟 + 1] | ≥ 2𝑓 + 1) do 90: if 𝑐𝑜𝑚𝑚𝑖𝑡𝑡𝑒𝑑𝑅𝑜𝑢𝑛𝑑 < 𝑟 then 91: 𝑣 ← get_leader_vertex(𝑟 ) 92: commit_leader(𝑣 ) 93: procedure commit_leader(𝑣 ) 94: 𝑙𝑒𝑎𝑑𝑒𝑟𝑆𝑡𝑎𝑐𝑘.push(𝑣 ) 95: 𝑟 ← 𝑣.𝑟𝑜𝑢𝑛𝑑 − 1 96: 𝑣′ ← 𝑣 97: while 𝑟 > 𝑐𝑜𝑚𝑚𝑖𝑡𝑡𝑒𝑑𝑅𝑜𝑢𝑛𝑑 do 98: 𝑣𝑠 ← get_leader_vertex(𝑟 ) 99: if leader_path(𝑣 ′ , 𝑣𝑠 ) then 100: 𝑙𝑒𝑎𝑑𝑒𝑟𝑆𝑡𝑎𝑐𝑘.push(𝑣𝑠 ) 101: 𝑣 ′ ← 𝑣𝑠 102: 𝑟 ←𝑟 −1 103: 𝑐𝑜𝑚𝑚𝑖𝑡𝑡𝑒𝑑𝑅𝑜𝑢𝑛𝑑 ← 𝑣.𝑟𝑜𝑢𝑛𝑑 104: order_vertices() 105: procedure order_vertices() 106: while ¬𝑙𝑒𝑎𝑑𝑒𝑟𝑆𝑡𝑎𝑐𝑘.isEmpty() do 107: 𝑣 ← 𝑙𝑒𝑎𝑑𝑒𝑟𝑆𝑡𝑎𝑐𝑘.pop() Ð 108: 𝑡𝑜𝐷𝑒𝑙𝑖𝑣𝑒𝑟 ← {𝑣 ′ ∈ 𝑟 >0 𝐷𝐴𝐺𝑖 [𝑟 ] | 𝑝𝑎𝑡ℎ (𝑣, 𝑣 ′ )∧ 𝑣 ′ ∉ 𝑑𝑒𝑙𝑖𝑣𝑒𝑟𝑒𝑑𝑉 𝑒𝑟𝑡𝑖𝑐𝑒𝑠 } 109: for every 𝑣 ′ ∈ 𝑡𝑜𝐷𝑒𝑙𝑖𝑣𝑒𝑟 in some deterministic order do 110: output a_deliver𝑖 (𝑣 ′ .𝑏𝑙𝑜𝑐𝑘, 𝑣 ′ .𝑟𝑜𝑢𝑛𝑑, 𝑣 ′ .𝑠𝑜𝑢𝑟𝑐𝑒 ) 111: 𝑑𝑒𝑙𝑖𝑣𝑒𝑟𝑒𝑑𝑉 𝑒𝑟𝑡𝑖𝑐𝑒𝑠 ← 𝑑𝑒𝑙𝑖𝑣𝑒𝑟𝑒𝑑𝑉 𝑒𝑟𝑡𝑖𝑐𝑒𝑠 ∪ {𝑣 ′ }

honest replicas complete the RBC for round 𝑟 + 1, they proceed to round 𝑟 + 2. At this time, if the Byzantine replicas help deliver these vertices to the lagging replicas, these stragglers will immediately skip to round 𝑟 + 2. Without fast-votes, 𝐿𝑉𝑟 would fail to attain the required 2𝑓 + 1 votes for being committed. This process could repeat forever, preventing any leader vertex from being directly committed even after GST, thereby violating liveness. The fast-vote mechanism in Clownfish allows the 𝑓 lagging honest replicas to cast votes for 𝐿𝑉𝑟 in such scenarios. Together with our commit rule, this ensures that 𝐿𝑉𝑟 receives sufficient votes to be committed.

4.2

Correctness and Efficiency Analysis

Correctness. Due to space limitations, the full correctness proof of Clownfish is deferred to Appendix C.1. Communication complexity. We analyze the per-round metadata communication complexity. Metadata refers to the edges (references) in vertices and consensus messages such as no-votes and fast-votes. The edges may take the form of indices, cryptographic hashes, or signatures. Under the assumption of threshold signatures, the broadcasting of consensus messages incurs at most 𝑂 (𝜆𝑛 2 ) communication per round. In Clownfish, only the leader vertex contains 𝑂 (𝑛) edges and potentially a 𝑁𝑉𝐶, while each non-leader vertex contains only 𝑂 (1) edges. Consequently, the total number of edges per round is 𝑂 (𝑛). By contrast, Sailfish have 𝑂 (𝑛 2 ) edges per round. In both protocols, disseminating these edges through RBC or CBC dominates the overall communication complexity. With Bracha’s RBC [11], Clownfish incurs 𝑂 (𝑛 3 log 𝑛) communication complexity4 compared with 𝑂 (𝑛 4 ) for Sailfish. When using CCBRB [2], the communication complexity for both Clownfish

and Sailfish is 𝑂 (𝜆𝑛 3 ). Although Clownfish cannot utilize erasure coding to reduce the asymptotic complexity, the reduced number of references still saves both computation and communication overhead. When using latency-optimal RBC [1], Clownfish incurs 𝑂 (𝜆𝑛 3 ) communication complexity, compared with 𝑂 (𝑛 4 ) for Sailfish. When using Narwhal’s CBC [19], Clownfish incurs 𝑂 (𝜆𝑛 2 ) communication complexity in the good case and 𝑂 (𝜆𝑛 3 ) in the bad case, whereas the corresponding communication complexity of Sailfish is 𝑂 (𝜆𝑛 3 ) and 𝑂 (𝜆𝑛 4 ), respectively. Latency. In Clownfish and Sailfish, the commit latency for an honest leader vertex (after GST) is the latency of a single RBC instance plus 1𝛿. In good case, the commit latency for non-leader vertices incurs an additional RBC latency, as they need to be referenced by a subsequent leader vertex. Consequently, for a generic RBC protocol, these two latencies equal to (𝑘 1 + 1)𝛿 and (2𝑘 1 + 1)𝛿, respectively. We now evaluate the additional latency incurred by a Byzantine leader. In Clownfish, the timeout parameter is configured as 𝜏 = (𝑘 1 + 𝑘 2 )Δ. Consider a scenario where Byzantine 𝐿𝑟 remains silent and the first honest replica enters round 𝑟 at time 𝑡. By Lemma 2 and the responsiveness of the RBC protocol, all honest replicas are guaranteed to enter round 𝑟 within 𝑘 2𝛿. Consequently, by time 𝑡 + 𝜏 + (𝑘 2 + 1)𝛿, all honest replicas will receive the 𝑁𝑉𝐶𝑟 and advance to round 𝑟 + 1. If 𝐿𝑟 +1 is honest, all non-leader vertices from round 𝑟 − 1 referenced by 𝐿𝑟 +1 will be committed within the subsequent (𝑘 1 + 1)𝛿. Therefore, the presence of a single Byzantine leader results in an increase in the commit latency for non-leader vertices of 𝜏 + (𝑘 2 + 1)𝛿 + (𝑘 1 + 1)𝛿 − [𝑘 2𝛿 + (𝑘 1 + 1)𝛿] = 𝜏 + 𝛿 5 . In comparison, Sailfish incurs an additional latency of 𝜏 + 2𝛿 (for a single failure) or 𝜏 +𝑘 2 Δ +2𝛿 (for consecutive failures), as it requires an extra round of timeout message dissemination and collection.

4.3

Clownfish with Consistent Broadcast

In this section, we present the CBC-based version of Clownfish protocol. Specifically, we build on Narwhal’s CBC [19], which combines Signed Echo CBC [14] with a randomized pull mechanism. Narwhal’s CBC optimizes communication complexity in the good case by eliminating the all-to-all broadcast. The feasibility of this approach hinges on the existence of availability certificates, which moves data synchronization off the critical path [6, 19]. To the best of our knowledge, existing proofs for Narwhal-based protocols often directly invoke RBC’s property ( Property 1) [6, 42, 51], which do not align with the weaker properties provided by Narwhal’s CBC. Our goal is to directly design a protocol whose security relies exclusively on the properties of Narwhal’s CBC. The main challenge in designing the protocol is to guarantee round synchronization. We address this challenge through an explicit round synchronization mechanism. Specifically, upon entering a new round, a replica sends a set of certificates to the corresponding leader (which we call a new-round message) to ensure that the leader can enter that round. The round-skipping rules must also be modified to avoid blocking round advancement. To prevent the timeout from becoming too long, we further optimize the protocol by delaying the start of the round timer. The details of protocol are presented in Appendix B. 5We subtract 𝑘 𝛿 here because the commit latency calculation in the good case does 2

4 The log 𝑛 factor arises because each reference can be encoded as a replica index.

not account for the additional latency caused by round synchronization.

Clownfish : Scaling DAG-based BFT Consensus via Sparse Edges

5

Multi-leader Clownfish

In Clownfish, non-leader vertices incur at least one additional RBC latency over leader vertices. To further minimize the average latency, we extend Clownfish to support multiple leaders per round. Our objective is to ensure that, in the good-case scenario, all leader vertices are committed within a latency of one RBC plus 1𝛿. This aligns with other state-of-the-art protocols [6, 7, 40, 51]. We designate this extended protocol as Multi-leader Clownfish. Multiple leaders with different types. Drawing inspiration from Multi-leader Sailfish [40], we classify the leaders in each round into one main leader and a set of secondary leaders. The main leader is analogous to the leader in Clownfish. It is responsible for establishing paths to potentially committed leader vertices or providing 𝑁𝑉𝐶s to certify that some are not committed. Secondary leaders are largely identical to non-leaders, with the exception that the new commit rule enables their vertices to be committed earlier. We assume that the sequence of leaders for a given round is selected by a deterministic mechanism. Let 𝑀𝐿𝑟 denote the leader sequence for round 𝑟 . Specifically, ML𝑟 [𝑥] represents the 𝑥-th leader (main leader if 𝑥 = 1, secondary leader if 𝑥 > 1). Additionally, we define ML𝑟 [: 𝑥] and ML𝑟 [𝑥 + 1 :] to denote the first 𝑥 leaders and the set of all subsequent leaders in round 𝑟 , respectively. For notational convenience, let 𝐿𝑟 = ML𝑟 [1] denote the main leader of round 𝑟 and 𝐿𝑉𝑟 denote the main leader vertex. Let MLV 𝑟 [𝑥] denote the delivered vertex corresponding to ML𝑟 [𝑥]. We further define MLV 𝑟 [𝑥].𝑖𝑛𝑑𝑒𝑥 = 𝑥 (used in the pseudocode). DAG construction protocol. We begin by outlining the modifications in the DAG construction of Multi-leader Clownfish relative to Clownfish. The pseudocode for Multi-leader Clownfish is presented in Algorithm 4. Text highlighted in magenta explicitly denotes the differences relative to both Clownfish and multi-leader Sailfish [40]. Sharing the fundamental design philosophy of Clownfish, Multileader Clownfish aims to reduce the number of references in a non-main leader vertex to 𝑂 (1). However, the multi-leader setting necessitates that vertices cast “votes” for secondary leaders to directly commit them. To accomplish this, we extend the meaning of the leader edge. Specifically, a leader edge references the “highest” leader vertex in the corresponding round. Here, the term “highest” implies that all leader vertices with lower indices have already been delivered (Lines 121 and 155). In essence, a leader edge referencing the 𝑘-th leader serves as a vote for all leaders with indices 1 through 𝑘 in that round. This design circumvents the need for non-main leader vertices to include 𝑂 (𝑛) references for voting, a requirement that would otherwise arise given the presence of 𝑂 (𝑛) leaders. Since a leader edge references only the highest leader vertex, the main leader needs to establish direct paths to other leader vertices from preceding rounds to guarantee safety. To facilitate this, we introduce auxiliary edges within the main leader vertex (denoted as 𝑎𝑢𝑥𝐸𝑑𝑔𝑒𝑠 in Algorithm 4). We explain this design by considering the main leader 𝐿𝑟 of round 𝑟 . When 𝐿𝑟 enters round 𝑟 via the delivery of 𝐿𝑉𝑟 −1 (Lines 156– 157), 𝑎𝑢𝑥𝐸𝑑𝑔𝑒𝑠 are omitted. In this scenario, we adopt the same constraints as in multi-leader Sailfish [40]. Specifically, let 𝑁𝑉𝐶𝑟ℓ denote the no-vote certificate for leader ℓ in round 𝑟 . Additionally, we use 𝑁𝑉𝐶𝑟 to denote 𝑁𝑉𝐶𝑟𝐿𝑟 . 𝐿𝑉𝑟 is required to establish strong

edges to all leader vertices corresponding to ML𝑟 −1 [: 𝑥] (for some 𝑥 > 0), and include the 𝑁𝑉𝐶 of 𝑀𝐿𝑟 −1 [𝑥 + 1] (Lines 129–133). If all vertices of 𝑀𝐿𝑟 −1 are referenced, the inclusion of 𝑁𝑉𝐶 is omitted. When 𝐿𝑟 enters round 𝑟 via 𝑁𝑉𝐶𝑟 −1 (Lines 158–161), 𝐿𝑟 is responsible for establishing paths to leader vertices preceding round 𝑟 − 1. To achieve this, 𝐿𝑟 scans the leader edges of all vertices referenced by its strong edges and identifies the one with the highest round 𝑟 ∗ and subsequently the highest index 𝑥 ∗ (Lines 136–137). In the pseudocode, the arg max notation succinctly captures this search process. Subsequently, 𝐿𝑟 references the vertices of ML𝑟 ∗ [: 𝑥 ∗ ] via 𝑎𝑢𝑥𝐸𝑑𝑔𝑒𝑠 (Line 138). By properties of RBC, the eventual delivery of these vertices is guaranteed. Consistent with Clownfish, a replica broadcasts a no-vote for 𝐿𝑟 if it fails to deliver 𝐿𝑉𝑟 before timeout. Upon entering a new round, a replica sends no-vote messages for all undelivered leader vertices from the previous round to the main leader (Line 153). This ensures that the main leader of the new round can successfully include an 𝑁𝑉𝐶 (if necessary) and create a valid vertex. We denote the no-vote message for leader ℓ in round 𝑟 as ⟨no-vote, ℓ, 𝑟 ⟩. DAG commit rule. The primary distinction between the DAG commit rules of Multi-leader Clownfish and Clownfish stems from the interpretation of the leader edge. Specifically, a vertex in round 𝑟 + 1 referencing MLV 𝑟 [𝑥] via its leader edge constitutes a vote for the entire set MLV 𝑟 [: 𝑥]. For the main leader 𝐿𝑉𝑟 , any round 𝑟 + 1 vertices containing a leader edge to round 𝑟 is regarded as a vote (Line 164). After directly committing the main leader, replicas invoke commit_leaders to attempt to directly commit secondary leaders within the same round. Given that fast-votes are issued exclusively for the main leader, we consider only first messages as votes for secondary leaders. MLV 𝑟 [𝑥] is directly committed upon receiving at least 2𝑓 + 1 first messages from round 𝑟 + 1 with leader edge indices ≥ 𝑥 (Line 171). Upon completion of the aforementioned procedure, replicas recursively and indirectly commit all leader vertices MLV 𝑟 ′ [: 𝑥 ′ ] (for some 𝑥 ′ > 0) in rounds 𝑟 ′ < 𝑟 for which a leader path exists from 𝐿𝑉𝑟 (Lines 174–184). Finally, replicas invoke order_vertices to totally order the entire causal history in accordance with the sequence of committed leaders (Line 186). This indirect commit process leverages the existence of leader paths to ensure safety. We present an illustration of Multi-leader Clownfish in Appendix A and provide its correctness proof in Appendix C.3. Communication complexity. In Multi-leader Clownfish, the number of edges in non-main leader vertices remains unchanged. Since the number of auxiliary edges is at most 𝑂 (𝑛), the main leader vertex still contain 𝑂 (𝑛) edges. Within each round, all replicas are required to send up to 𝑂 (𝑛) additional no-vote messages to the main leader, which results in a total communication overhead of 𝑂 (𝜆𝑛 2 ). Consequently, across the various RBC implementations considered, Multi-leader Clownfish maintains the same metadata communication complexity as Clownfish. Latency. In the best-case scenario, all leader vertices are directly committed. Consequently, the commit latency for each leader vertex is the one 𝑅𝐵𝐶 plus 1𝛿. In a non-optimal case, the main leader vertex may require an additional 𝛿 to collect the 𝑁𝑉𝐶 of a previous secondary leader. Thus, the direct commit latency for leader vertices

Feifan Wang, Jingfan Yu, Zixi Cai, and Zhixuan Fang

Algorithm 4 Multi-leader Clownfish’s pseudocode for replica 𝑝𝑖 Local variables: struct vertex 𝑣 : 𝑣.𝑙𝑒𝑎𝑑𝑒𝑟 𝐸𝑑𝑔𝑒 - a leader vertex in round ≤ 𝑣.𝑟𝑜𝑢𝑛𝑑 − 1 that represents a leader edge with highest index 𝑣.𝑛𝑣𝑐 - a no-vote certificate of a leader vertex in 𝑣.𝑟𝑜𝑢𝑛𝑑 − 1 𝑣.𝑎𝑢𝑥𝐸𝑑𝑔𝑒𝑠 - a set of leader edges in round < 𝑣.𝑟𝑜𝑢𝑛𝑑 − 1 that represent auxiliary leader edges 𝑙𝑎𝑠𝑡𝐿𝑒𝑎𝑑𝑒𝑟 - The most recent delivered leader vertex with the highest round and index

⊲ The struct of a vertex in the DAG ⊲ Only main leader vertices need to contain ⊲ Only main leader vertices need to contain

112: procedure get_leader(𝑟, 𝑥 ) 113: return get_vertex( M L𝑟 [𝑥 ], 𝑟 ) 114: procedure leader_path(𝑣, 𝑢 ) 115: return exists a sequence of 𝑘 ∈ N, vertices 𝑣Ð 1 , . . . , 𝑣𝑘 s.t. 𝑣1 = 𝑣 , 𝑣𝑘 = 𝑢 , and ∀ 𝑗 ∈ [2, .., 𝑘 ] : 𝑣 𝑗 ∈ 𝑟 ≥1 𝐷𝐴𝐺𝑖 [𝑟 ] ∧ (𝑣 𝑗 ∈ 𝑣 𝑗 −1 .𝑙𝑒𝑎𝑑𝑒𝑟 𝐸𝑑𝑔𝑒 ∪ 𝑣 𝑗 −1 .𝑠𝑡𝑟𝑜𝑛𝑔𝐸𝑑𝑔𝑒𝑠 ∪ 𝑣 𝑗 −1 .𝑎𝑢𝑥𝐸𝑑𝑔𝑒𝑠 ) 116: upon timeout in 𝑟𝑜𝑢𝑛𝑑 do 117: if š𝑣 ′ ∈ 𝐷𝐴𝐺𝑖 [𝑟𝑜𝑢𝑛𝑑 ] : 𝑣 ′ .𝑠𝑜𝑢𝑟𝑐𝑒 = 𝐿𝑟𝑜𝑢𝑛𝑑 then 118: broadcast ⟨no-vote, 𝐿𝑟𝑜𝑢𝑛𝑑 , 𝑟𝑜𝑢𝑛𝑑 ⟩𝑖 119: upon r_deliver𝑖 (𝐿𝑉𝑟 , 𝑟, 𝐿𝑟 ) for 𝑟 > 𝑙𝑎𝑠𝑡𝐿𝑒𝑎𝑑𝑒𝑟 .𝑟𝑜𝑢𝑛𝑑 do 120: if haven’t sent ⟨no-vote, 𝐿𝑟 , 𝑟 ⟩𝑖 before then 121: 𝑙𝑎𝑠𝑡𝐿𝑒𝑎𝑑𝑒𝑟 ← 𝐿𝑉𝑟 122: procedure create_new_vertex(𝑟 ) 123: 𝑣.𝑟𝑜𝑢𝑛𝑑 ← 𝑟 124: 𝑣.𝑠𝑜𝑢𝑟𝑐𝑒 ← 𝑝𝑖 125: 𝑣.𝑏𝑙𝑜𝑐𝑘 ← 𝑏𝑙𝑜𝑐𝑘𝑠𝑇 𝑜𝑃𝑟𝑜𝑝𝑜𝑠𝑒.dequeue 126: set_leader_edge(𝑣 ) 127: if 𝑝𝑖 = 𝐿𝑟 then 128: 𝑣.𝑠𝑡𝑟𝑜𝑛𝑔𝐸𝑑𝑔𝑒𝑠 ← 𝐷𝐴𝐺𝑖 [𝑟 − 1] 129: if ∃𝑣 ′ ∈ 𝐷𝐴𝐺𝑖 [𝑟 − 1] : 𝑣 ′ .𝑠𝑜𝑢𝑟𝑐𝑒 = 𝐿𝑟 −1 then 130: for ℓ ∈ M L𝑟 −1 do 131: if š𝑣 ′ ∈ 𝐷𝐴𝐺𝑖 [𝑟 − 1] : 𝑣 ′ .𝑠𝑜𝑢𝑟𝑐𝑒 = ℓ then 132: 𝑣.𝑛𝑣𝑐 ← 𝑁𝑉 𝐶𝑟ℓ −1 133: break 134: else 135: 𝑣.𝑛𝑣𝑐 ← 𝑁𝑉 𝐶𝑟 −1 136: 𝑣 ∗ ← arg max𝑣 ′ ∈𝐷𝐴𝐺𝑖 [𝑟 −1] {𝑣 ′ .𝑙𝑒𝑎𝑑𝑒𝑟 𝐸𝑑𝑔𝑒 } 137: (𝑟 ∗ , 𝑥 ∗ ) ← (𝑣 ∗ .𝑟𝑜𝑢𝑛𝑑, 𝑣 ∗ .𝑖𝑛𝑑𝑒𝑥 ) 138: 𝑣.𝑎𝑢𝑥𝐸𝑑𝑔𝑒𝑠 ← { get_leader(𝑟 ∗ , 𝑥 ) for 𝑥 ≤ 𝑥 ∗ } 139: set_weak_edges(𝑣, 𝑟 ) 140: set_self_edges(𝑣 ) 141: return 𝑣 142: procedure order_vertices() 143: while ¬𝑙𝑒𝑎𝑑𝑒𝑟𝑆𝑡𝑎𝑐𝑘.isEmpty() do 144: C M V ← 𝑙𝑒𝑎𝑑𝑒𝑟𝑆𝑡𝑎𝑐𝑘.pop() 145: for 𝑣 ∈ C M V do ⊲ iterate over C M V in order Ð 146: 𝑡𝑜𝐷𝑒𝑙𝑖𝑣𝑒𝑟 ← {𝑣 ′ ∈ 𝑟 >0 𝐷𝐴𝐺𝑖 [𝑟 ] | 𝑝𝑎𝑡ℎ (𝑣, 𝑣 ′ ) ′ ∧ 𝑣 ∉ 𝑑𝑒𝑙𝑖𝑣𝑒𝑟𝑒𝑑𝑉 𝑒𝑟𝑡𝑖𝑐𝑒𝑠 } 147: for every 𝑣 ′ ∈ 𝑡𝑜𝐷𝑒𝑙𝑖𝑣𝑒𝑟 in some order do 148: output a_deliver𝑖 (𝑣 ′ .𝑏𝑙𝑜𝑐𝑘, 𝑣 ′ .𝑟𝑜𝑢𝑛𝑑, 𝑣 ′ .𝑠𝑜𝑢𝑟𝑐𝑒 ) 149: 𝑑𝑒𝑙𝑖𝑣𝑒𝑟𝑒𝑑𝑉 𝑒𝑟𝑡𝑖𝑐𝑒𝑠 ← 𝑑𝑒𝑙𝑖𝑣𝑒𝑟𝑒𝑑𝑉 𝑒𝑟𝑡𝑖𝑐𝑒𝑠 ∪ {𝑣 ′ }

150: procedure advance_round(𝑟 ) 151: for ℓ ∈ M L𝑟 −1 do ⊲ iterative over M L𝑟 −1 in order 152: if š𝑣 ′ ∈ 𝐷𝐴𝐺𝑖 [𝑟 − 1] : 𝑣 ′ .𝑠𝑜𝑢𝑟𝑐𝑒 = ℓ then 153: send ⟨no-vote, ℓ, 𝑟 − 1⟩𝑖 to 𝐿𝑟 154: if 𝑙𝑎𝑠𝑡𝐿𝑒𝑎𝑑𝑒𝑟 = 𝐿𝑉𝑟 −1 ∧ ℓ.𝑖𝑛𝑑𝑒𝑥 > 2 then 155: 𝑙𝑎𝑠𝑡𝐿𝑒𝑎𝑑𝑒𝑟 ← get_leader(𝑟 − 1, ℓ.𝑖𝑛𝑑𝑒𝑥 − 1) 156: if 𝑝𝑖 = 𝐿𝑟 and ∃𝑣 ′ ∈ 𝐷𝐴𝐺𝑖 [𝑟 − 1] : 𝑣 ′ .𝑠𝑜𝑢𝑟𝑐𝑒 = 𝐿𝑟 −1 then 157: wait until ( (∃𝑣 ′ ∈ 𝐷𝐴𝐺𝑖 [𝑟 − 1] : 𝑣 ′ .𝑠𝑜𝑢𝑟𝑐𝑒 = ℓ ) for ∀ℓ ∈ ′ M L𝑟 −1 [: 𝑥 ] ) ∧ (𝑁𝑉 𝐶𝑟ℓ −1 is received for ℓ ′ = M L𝑟 −1 [𝑥 + 1] ) 158: if 𝑝𝑖 = 𝐿𝑟 and 𝑁𝑉 𝐶𝑟 −1 is received then 159: 𝑣 ∗ ← arg max𝑣 ′ ∈𝐷𝐴𝐺𝑖 [𝑟 −1] {𝑣 ′ .𝑙𝑒𝑎𝑑𝑒𝑟 𝐸𝑑𝑔𝑒 } 160: (𝑟 ∗ , 𝑥 ∗ ) ← (𝑣 ∗ .𝑟𝑜𝑢𝑛𝑑, 𝑣 ∗ .𝑖𝑛𝑑𝑒𝑥 ) 161: wait until r_deliver𝑖 (∗, 𝑟 ∗ , ℓ ) for ∀ℓ ∈ M L𝑟 ∗ [: 𝑥 ∗ ] 162: 𝑟𝑜𝑢𝑛𝑑 ← 𝑟 ; start 𝑡𝑖𝑚𝑒𝑟 for 𝑟𝑜𝑢𝑛𝑑 163: broadcast_vertex(𝑟𝑜𝑢𝑛𝑑 ) 164: upon receiving a set M of first messages for round 𝑟 + 1 vertices s.t. ∀𝑣 ′ ∈ M : (∃𝑣 ∈ 𝑣 ′ .𝑙𝑒𝑎𝑑𝑒𝑟 𝐸𝑑𝑔𝑒 ∪ 𝑣 ′ .𝑠𝑡𝑟𝑜𝑛𝑔𝐸𝑑𝑔𝑒𝑠 ∧ 𝑣.𝑟𝑜𝑢𝑛𝑑 = 𝑟 ) ∧ ( | M | + |𝐹𝑉𝑖 [𝑟 + 1] | ≥ 2𝑓 + 1) do 165: if 𝑐𝑜𝑚𝑚𝑖𝑡𝑡𝑒𝑑𝑅𝑜𝑢𝑛𝑑 < 𝑟 then 166: commit_leaders(𝑟 ) 167: procedure commit_leaders(𝑟 ) 168: C L S ← [𝐿𝑉𝑟 ] 169: for 𝑥 = 2 to | M L𝑟 | do 170: 𝑣 ← get_leader_vertex(𝑟, 𝑥 ) 171: if have received a set S of first messages for round 𝑟 + 1 vertices s.t. (∀𝑣 ′ ∈ S : 𝑣 ′ .𝑙𝑒𝑎𝑑𝑒𝑟 𝐸𝑑𝑔𝑒.𝑟𝑜𝑢𝑛𝑑 = 𝑟 ∧ 𝑣 ′ .𝑙𝑒𝑎𝑑𝑒𝑟 𝐸𝑑𝑔𝑒.𝑖𝑛𝑑𝑒𝑥 ≥ 𝑥 ) ∧ ( | S | ≥ 2𝑓 + 1) then 172: CLS ← CLS ∥ 𝑣 173: else break 174: 𝑙𝑒𝑎𝑑𝑒𝑟𝑆𝑡𝑎𝑐𝑘.push( C L S ); 𝑣 ′ ← C L S [0] ; 𝑟 ′ ← 𝑣 ′ .𝑟𝑜𝑢𝑛𝑑 − 1 175: while 𝑟 ′ > 𝑐𝑜𝑚𝑚𝑖𝑡𝑡𝑒𝑑𝑅𝑜𝑢𝑛𝑑 do 176: CMV ← [] 177: for 𝑥 = 1 to | M L𝑟 ′ | do 178: 𝑣 ← get_leader(𝑟 ′ , 𝑥 ) 179: if leader_path(𝑣 ′ , 𝑣 ) then 180: CMV ← CMV ∥ 𝑣 181: else break 182: if C M V ≠ [ ] then 183: 𝑣 ′ ← C M V [0] ⊲ main leader vertex for round 𝑟 ′ 184: 𝑙𝑒𝑎𝑑𝑒𝑟𝑆𝑡𝑎𝑐𝑘.push( C M V ); 𝑟 ′ ← 𝑟 ′ − 1 185: 𝑐𝑜𝑚𝑚𝑖𝑡𝑡𝑒𝑑𝑅𝑜𝑢𝑛𝑑 ← C L S [0].𝑟𝑜𝑢𝑛𝑑 186: order_vertices()

becomes one 𝑅𝐵𝐶 plus 2𝛿. Assuming there are 𝑛 − 𝑓 delivered vertices per round, the average latency of Multi-leader Clownfish 𝑛−𝑓 +𝑘 1 outperforms that of Clownfish as long as 𝑥 > , where 𝑥 𝑘1 denotes the number of directly committed leader vertices. The CBC-based version of Clownfish also supports a multi-leader extension. See Appendix B.3 for details.

achieves lower latency under failure case. (iii) Multi-leader Clownfish can further reduce average latency while preserving scalability. Our empirical evaluation is based on two complementary implementations. First, we use a Rust-based simulator to study protocol scalability at large system sizes. The simulator abstracts away implementation-specific overheads, allowing us to focus on metadata communication and capture the scalability gap between different protocols. Second, we build a Go-based prototype and deploy it on geo-distributed servers to measure real throughput-latency performance. The deployment results demonstrate the practical benefits of reducing metadata communication under medium-scale systems and bandwidth-limited settings.

6

Evaluation

We evaluate the performance of Clownfish under varying numbers of replicas and different failure scenarios, and compare it against Sailfish [40] and Sparse Bullshark [4]. Sailfish is the state-of-the-art certified-DAG protocol and serves as the basis of Clownfish. Sparse Bullshark is a scalable DAG protocol, which reduces the metadata communication overhead of Bullshark [43]. Our evaluation aims to demonstrate that (i) Clownfish provides better scalability and maintains strong performance at large numbers of replicas. (ii) Clownfish

Implementation details. For simulation, we modify the Rustbased discrete-event simulator used by Sparse Bullshark [4] to implement Clownfish and Multi-leader Clownfish. Consistent with the original implementations of Sailfish and Sparse Bullshark, we

Clownfish : Scaling DAG-based BFT Consensus via Sparse Edges

(a) Latency

(b) Throughput

(c) Metadata communication

Figure 3: Performance comparison under failure-free case with varying numbers of replicas. use Narwhal’s CBC [19] to minimize communication overhead. We focus on metadata communication and only consider consensus over empty blocks without transactions. To ensure a fair comparison, we also re-implement Sailfish, Multi-leader Sailfish, and Sparse Bullshark in the simulator according to their protocol descriptions6 . For deployment, we implement the above protocols in Go7 . We implement the primary-worker architecture of Narwhal [19]. Specifically, workers are responsible for broadcasting transactions from clients in batches. After receiving 𝑛 − 𝑓 acknowledgments from other workers, a worker provides the digest of the corresponding batch to its primary. The primary then uses these digests as payloads in the consensus protocol. Experimental setup. For simulation, we set the maximum number of replicas to 1000. To capture the bandwidth bottlenecks that arise from large volumes of metadata transmission, we limit the network bandwidth of each replica to 1Gbps. To make latency more realistic, we simulate replicas evenly distributed across five geodistributed regions. We use historical RTT measurements from Google Cloud [28] and model the latency of each directed region pair with a normal distribution. We measure latency as the average time from vertex creation to its commitment. Since transactions are not modeled in the simulator, throughput is measured as the average number of committed vertices per second, which should ideally scale linearly with the number of replicas. Each simulation runs for 180 simulated seconds. We conduct the deployment experiments on geo-distributed servers across five AWS regions: us-east-1, us-west-1, eu-west-2, ap-northeast-1, and ap-southeast-2. Replicas are evenly distributed across these regions. The round-trip time between different regions ranges from 59ms to 264ms. Each replica runs on an AWS EC2 c5a.2xlarge instance with 8 vCPUs and 16 GB of memory, running Ubuntu 22.04. We limit the bandwidth of each machine to 100Mbps to emulate settings where communication is affected by metadata transmission. Each replica consists of one primary and one worker, which share the same bandwidth limit. The worker 6We set the sample size (number of strong edges) of Sparse Bullshark to 128 to achieve

safety comparable to that of Sailfish and Clownfish, while preserving sparsity. 7 Since our deployment considers medium-scale systems with 𝑛 < 𝜆 , we use Bullshark

instead of Sparse Bullshark, as Sparse Bullshark cannot be sparsified in this regime without affecting safety.

generates dummy transactions of 256 random bytes according to the specified rate. Each experiment runs for 30 seconds after several warm-up rounds with 50 replicas. The timeout parameter is set to 2.5 seconds. End-to-end latency is measured as the average time from transaction creation to commitment. Throughput is measured as the number of committed transactions per second. Performance of Clownfish under failure-free case. We first compare the scalability of Clownfish against other protocols under the common case where there are no failures. Since the leader in vanilla Clownfish can still become a bottleneck due to the large size of leader vertices, we optimize it using Balanced Multicast from [2]. Specifically, we replace the first broadcast of each leader vertex with Balanced Multicast, which uses error-correcting codes to distribute the leader’s sending load evenly across all replicas. Notably, this optimization does not reduce the total communication overhead and may introduce additional message delay. It is therefore ineffective for Sparse Bullshark and Sailfish, where the sending load is already balanced because all vertices have the same metadata size. In simulation, we vary the number of replicas from 100 to 1000 and measure the latency, throughput, and metadata volume per round of each protocol. The results are shown in Figure 3, where Clownfish and Balanced Clownfish denote vanilla Clownfish and Clownfish optimized with Balanced Multicast, respectively. In Figure 3a, all protocols experience higher latency as the number of replicas increases. When 𝑛 ≤ 300, Clownfish and Sailfish have nearly identical latency and both outperform Sparse Bullshark. However, Sailfish’s latency increases rapidly once 𝑛 > 300, as its cubic metadata communication causes the bandwidth bottleneck to appear earlier. Vanilla Clownfish delays this bottleneck until 𝑛 > 500 and suffers a smaller increase, since only the leader carries a large vertex. Nevertheless, this leader bottleneck eventually makes vanilla Clownfish slower than Sparse Bullshark when 𝑛 > 700, despite its lower metadata complexity. Balanced Clownfish removes this bottleneck by distributing the leader’s sending load, and therefore achieves the best scalability: its latency remains almost unchanged up to 𝑛 = 1000 (from 724ms to 729ms). The throughput results in Figure 3b show the same trend. Sailfish and vanilla Clownfish first benefit from having more vertices per round, but their throughput eventually drops as metadata transmission saturates the network. Sparse Bullshark also begins to

Feifan Wang, Jingfan Yu, Zixi Cai, and Zhixuan Fang

reach a turning point at 𝑛 = 1000. In contrast, Balanced Clownfish continues to scale almost linearly with the number of replicas.

Performance of Clownfish under crash failures. We evaluate the throughput-latency of Clownfish and Sailfish in  performance  the presence of 𝑓 = 𝑛−1 crash failures. We distribute the crashed 3 replicas evenly across the five regions. We use round-robin leader rotation, where a crash leader appears every three rounds. As depicted in Figure 5, the average latency of both protocols is substantially higher than in the failure-free case, due to the need of waiting for all honest replicas as well as the timeout caused by crash leaders. Before saturation, Sailfish’s latency stays around 3850ms to 4050ms, whereas Clownfish maintains a latency of around 3450ms to 3650ms. The enlarged latency gap comes from Clownfish’s optimized round-advancement rule: replicas in Clownfish only need one round of message dissemination after a timeout, whereas Sailfish requires two sequential rounds. As a result, non-leader vertices in Clownfish incur one less additional message delay.

Figure 4: Throughput / latency at 𝑛 = 50 without failures.

(a) Latency result of simulation.

Figure 5: Throughput / latency at 𝑛 = 50 with 16 crash failures. Figure 3c summarizes the per-round metadata communication of different protocols, where each signature is counted as one unit of metadata. The dashed lines show polynomial fits of appropriate degree. Consistent with the theoretical analysis, Sailfish exhibits cubic communication complexity, while Sparse Bullshark and Clownfish both exhibit quadratic communication complexity, with Sparse Bullshark incurring an additional Θ(𝜆) factor (here 𝜆 = 128). Due to the use of error-correcting codes, Balanced Clownfish incurs slightly higher communication overhead than vanilla Clownfish. We further evaluate the throughput-latency performance of the protocols in deployment, with the results shown in Figure 4. Under the given bandwidth limit, all protocols achieve comparable throughput in the tens of thousands, while Clownfish and Balanced Clownfish achieve similar latency, both lower than Sailfish and Bullshark. The latency gap of about 10% (180ms) between Clownfish and Sailfish comes from the saved metadata processing and communication overhead. These results show that metadata reduction provides practical latency benefits even at medium system sizes. This advantage is expected to become more pronounced as the ratio between metadata communication volume and available bandwidth increases, and can extend to larger-scale systems and higher-bandwidth settings.

(b) Throughput / latency result of deployment.

Figure 6: Performance of Multi-leader protocols at 𝑛 = 50 without failures. Performance of Multi-leader Clownfish under failure-free case. We compare the performance of Multi-leader Clownfish and Multileader Sailfish in the failure-free case (Sparse Bullshark does not support multiple leaders). We adopt the same implementation strategy as Multi-leader Sailfish [40], where replicas wait for all leader vertices before entering the next round. Figure 6a shows the simulation latency under different numbers of replicas and leaders, where MLCF denotes Multi-leader Clownfish and MLSF denotes Multi-leader Sailfish. Figure 6b shows the throughput-latency performance of these protocols in deployment.

Clownfish : Scaling DAG-based BFT Consensus via Sparse Edges

As shown in the figures, Multi-leader Clownfish reduces latency in a manner similar to Multi-leader Sailfish, with larger improvements as the number of leaders increases. More importantly, Multileader Clownfish preserves the scalability advantage of Clownfish: its latency remains relatively stable as the number of replicas grows. The deployment results further show that Multi-leader Clownfish reduces average latency in practice while retaining the advantage brought by lower communication overhead.

7

Discussion

In Clownfish, leader vertices carry more metadata compared to non-leader vertices. To balance the workload, one could employ a load-balanced broadcast specifically for leader vertices [2], as in our implementation. Another orthogonal optimization involves utilizing a leader reputation mechanism [17, 48] to select the fastest leaders. Since Clownfish requires leaders to perform more work compared to other replicas, the benefits of such an approach would be particularly pronounced. Finally, an interesting direction is extending Clownfish to a signature-free variant. Sailfish++ [41] provides a signature-free implementation of Sailfish; their methodology could be directly adapted to Clownfish. We also aim to explore more efficient and concise implementation approaches in future work.

8

Related Work

Leader-based BFT. Numerous BFT protocols over the past two decades have adopted the leader-based paradigm [13, 15, 16, 35, 50]. This paradigm relies on a leader to disseminate data and drive consensus progress, utilizing a view-change mechanism to periodically rotate the leader. Building upon the optimal latency achieved by PBFT [15] and the linear complexity achieved by HotStuff [50], subsequent protocols aim to achieve a superior latency-communication tradeoff [25, 37], as well as to enhance performance under specific scenarios [27, 29, 31]. However, the primary drawbacks of leaderbased BFT are the complexity of view change [12, 39] and the throughput bottleneck imposed by a single leader. Towards high throughput BFT. To improve throughput, it is crucial to utilize the available network bandwidth for data transmission. One approach involves running multiple leader-based BFT instances in parallel [30, 45, 46]. Since distinct replicas can serve as leaders across different instances and broadcast data concurrently, this results in a substantial throughput improvement in good case. However, this method is susceptible to stragglers and necessitates complex coordination for combining outputs and view changes [36]. Another strategy involves decoupling data transmission from consensus logic [19, 24, 26, 49]. This approach recognizes that consensus serves solely as an ordering mechanism, whereas data availability can be achieved in a fully parallel and asynchronous manner. Consequently, replicas can allocate bandwidth to the underlying data dissemination layer while executing the consensus protocol. DAG-based BFT. DAG-based protocols offer a natural approach to achieving high throughput. In this paradigm, all replicas concurrently broadcast vertices containing both data payloads and references, collectively constructing a DAG structure. By interpreting specific references as votes and leveraging path relationships,

replicas can achieve a total ordering of the data without incurring additional communication overhead. DAG-based BFT protocols are initially designed for asynchronous networks. Hashgraph [8] and Aleph [23] introduce unstructured and structured DAG constructions, respectively. Subsequently, a series of protocols (DAG-Rider [33], Tusk [19], and Bullshark [43]) introduce more efficient designs, serving as templates for subsequent DAG-based protocols. More recently, works such as GradedDAG [18] and MAHI-MAHI [32] have further reduced the latency of asynchronous DAG protocols by employing different broadcast primitives and commit rules. To circumvent the FLP impossibility result [22], these protocols necessitate the use of a common coin for retrospective leader election. Starting with Bullshark [44], DAG-based protocols begin to focus on efficient designs under partial synchrony networks. Bullshark introduces designated leaders and timeout to provide better performance during periods of synchrony. Since Bullshark designates a leader vertex every two rounds and requires all vertices to use RBC, a latency of at least 2 RBCs is necessary to commit a vertex. To improve latency, Shoal [42] introduces the concept of “pseudopipelining”, interpreting the DAG as multiple Bullshark instances to achieve the effect of having a leader vertex in every round. Shoal also proposes employing a leader reputation mechanism [17, 48] to select the fastest leaders. Shoal++ [6] further interprets the DAG as more Bullshark instances to achieve multiple leaders per round. Additionally, Shoal++ extends Bullshark’s commit rules to reduce the commit latency of leader vertices. To support a leader vertex in every round while maintaining safety, Sailfish [40] introduced additional consensus messages (such as no-vote), along with extra requirements for leader vertices. Furthermore, Sailfish also provides faster commit rules and support for multiple leaders per round. The aforementioned protocols focus on latency rather than communication complexity. They rely on batching Ω(𝑛) transactions within each vertex to amortize the high communication overhead. Sparse Bullshark [4] highlights the limitations of this approach and reduces metadata communication complexity by requiring each vertex to include only 𝑂 (𝜆) edges. We share a similar objective; however, we adopt a strategy that differentiates the treatment of leader vertices from that of non-leader vertices. Another concurrent work, Angelfish [51], offers a more flexible proposal mechanism building upon Sailfish. In their protocol, replicas can freely choose to execute RBC or merely cast a vote. Consequently, the protocol’s communication complexity depends on the number of replicas performing RBC, which is distinct from our method. Uncertified DAG. Recently, several works have proposed DAGbased protocols that operate without relying on RBC or CBC. Prominent examples include Cordial Miner [34] and Mysticeti [7], which rely on best-effort broadcast for vertex dissemination. While this approach achieves ideal latency in good cases, the inherent tradeoff is the requirement for immediate data fetching to retrieve missing data. This process inevitably incurs additional latency and communication overhead under failures. BBCA-CHAIN [38] proposes that leaders employ BBCA (a single-shot PBFT) for broadcasting to facilitate rapid commitment, while other replicas utilize best-effort broadcast. Its philosophy of hybridizing DAG and leader-based BFT paradigms provides a new perspective on protocol design.

Feifan Wang, Jingfan Yu, Zixi Cai, and Zhixuan Fang

References [1] Ittai Abraham, Kartik Nayak, Ling Ren, and Zhuolun Xiang. 2021. Good-case latency of byzantine broadcast: A complete categorization. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing. 331–341. [2] Nicolas Alhaddad, Sourav Das, Sisi Duan, Ling Ren, Mayank Varia, Zhuolun Xiang, and Haibin Zhang. 2022. Balanced byzantine reliable broadcast with near-optimal communication and improved computation. In Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing. 399–417. [3] Salem Alqahtani and Murat Demirbas. 2021. Bottlenecks in blockchain consensus protocols. In 2021 IEEE International Conference on Omni-Layer Intelligent Systems (COINS). IEEE, 1–8. [4] Michael Anoprenko, Andrei Tonkikh, Alexander Spiegelman, and Petr Kuznetsov. 2025. DAGs for the Masses. arXiv preprint arXiv:2506.13998 (2025). [5] Aptoscan. 2026. Aptoscan: Blocks Explorer. Retrieved Accessed: 2026-01-31 from https://aptoscan.com/blocks [6] Balaji Arun, Zekun Li, Florian Suri-Payer, Sourav Das, and Alexander Spiegelman. 2025. Shoal++: High Throughput { DAG } { BFT } Can Be Fast and Robust!. In 22nd USENIX Symposium on Networked Systems Design and Implementation (NSDI 25). 813–826. [7] Kushal Babel, Andrey Chursin, George Danezis, Anastasios Kichidis, Lefteris Kokoris-Kogias, Arun Koshy, Alberto Sonnino, and Mingwei Tian. 2025. MYSTICETI: Reaching the Latency Limits with Uncertified DAGs. In Network and Distributed Systems Security Symposium (NDSS). [8] Leemon Baird. 2016. The swirlds hashgraph consensus algorithm: Fair, fast, byzantine fault tolerance. Swirlds Tech Reports SWIRLDS-TR-2016-01, Tech. Rep 34 (2016), 9–11. [9] Sam Blackshear, Andrey Chursin, George Danezis, Anastasios Kichidis, Lefteris Kokoris-Kogias, Xun Li, Mark Logan, Ashok Menon, Todd Nowacki, Alberto Sonnino, et al. 2024. Sui lutris: A blockchain combining broadcast and consensus. In Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security. 2606–2620. [10] Dan Boneh, Ben Lynn, and Hovav Shacham. 2004. Short signatures from the Weil pairing. Journal of cryptology 17, 4 (2004), 297–319. [11] Gabriel Bracha. 1987. Asynchronous Byzantine agreement protocols. Information and computation 75, 2 (1987), 130–143. [12] Manuel Bravo, Gregory Chockler, and Alexey Gotsman. 2022. Making byzantine consensus live. Distributed Computing 35, 6 (2022), 503–532. [13] Ethan Buchman, Jae Kwon, and Zarko Milosevic. 2018. The latest gossip on BFT consensus. arXiv preprint arXiv:1807.04938 (2018). [14] Christian Cachin, Rachid Guerraoui, and Luís Rodrigues. 2011. Introduction to reliable and secure distributed programming. Springer Science & Business Media. [15] Miguel Castro, Barbara Liskov, et al. 1999. Practical byzantine fault tolerance. In OSDI (99, 1999). 173–186. [16] Benjamin Y Chan and Rafael Pass. 2023. Simplex consensus: A simple and fast consensus protocol. In Theory of Cryptography Conference. Springer, 452–479. [17] Shir Cohen, Rati Gelashvili, Lefteris Kokoris Kogias, Zekun Li, Dahlia Malkhi, Alberto Sonnino, and Alexander Spiegelman. 2022. Be aware of your leaders. In International Conference on Financial Cryptography and Data Security. Springer, 279–295. [18] Xiaohai Dai, Zhaonan Zhang, Jiang Xiao, Jingtao Yue, Xia Xie, and Hai Jin. 2023. GradedDAG: An asynchronous DAG-based BFT consensus with lower latency. In 2023 42nd International Symposium on Reliable Distributed Systems (SRDS). IEEE, 107–117. [19] George Danezis, Lefteris Kokoris-Kogias, Alberto Sonnino, and Alexander Spiegelman. 2022. Narwhal and tusk: a dag-based mempool and efficient bft consensus. In Proceedings of the Seventeenth European Conference on Computer Systems. 34–50. [20] Sourav Das, Zhuolun Xiang, and Ling Ren. 2021. Asynchronous data dissemination and its applications. In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security. 2705–2721. [21] Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. 1988. Consensus in the presence of partial synchrony. Journal of the ACM (JACM) 35, 2 (1988), 288–323. [22] Michael J Fischer, Nancy A Lynch, and Michael S Paterson. 1985. Impossibility of distributed consensus with one faulty process. Journal of the ACM (JACM) 32, 2 (1985), 374–382. [23] Adam Gągol, Damian Leśniak, Damian Straszak, and Michał Świętek. 2019. Aleph: Efficient atomic broadcast in asynchronous networks with byzantine nodes. In Proceedings of the 1st ACM Conference on Advances in Financial Technologies. 214–228. [24] Yingzi Gao, Yuan Lu, Zhenliang Lu, Qiang Tang, Jing Xu, and Zhenfeng Zhang. 2022. Dumbo-ng: Fast asynchronous bft consensus with throughput-oblivious latency. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. 1187–1201. [25] Rati Gelashvili, Lefteris Kokoris-Kogias, Alberto Sonnino, Alexander Spiegelman, and Zhuolun Xiang. 2022. Jolteon and ditto: Network-adaptive efficient consensus with asynchronous fallback. In International conference on financial cryptography and data security. Springer, 296–315.

[26] Neil Giridharan, Florian Suri-Payer, Ittai Abraham, Lorenzo Alvisi, and Natacha Crooks. 2024. Autobahn: Seamless high speed BFT. In Proceedings of the ACM SIGOPS 30th Symposium on Operating Systems Principles. 1–23. [27] Neil Giridharan, Florian Suri-Payer, Matthew Ding, Heidi Howard, Ittai Abraham, and Natacha Crooks. 2023. Beegees: stayin’alive in chained bft. In Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing. 233–243. [28] Google Cloud. 2026. Performance Dashboard Overview. Retrieved March 24, 2026 from https://docs.cloud.google.com/network-intelligence-center/docs/ performance-dashboard/concepts/overview [29] Guy Golan Gueta, Ittai Abraham, Shelly Grossman, Dahlia Malkhi, Benny Pinkas, Michael Reiter, Dragos-Adrian Seredinschi, Orr Tamir, and Alin Tomescu. 2019. SBFT: A scalable and decentralized trust infrastructure. In 2019 49th Annual IEEE/IFIP international conference on dependable systems and networks (DSN). IEEE, 568–580. [30] Suyash Gupta, Jelle Hellings, and Mohammad Sadoghi. 2021. Rcc: Resilient concurrent consensus for high-throughput secure transaction processing. In 2021 IEEE 37th International Conference on Data Engineering (ICDE). IEEE, 1392– 1403. [31] Mohammad M Jalalzai, Jianyu Niu, Chen Feng, and Fangyu Gai. 2023. Fasthotstuff: A fast and robust bft protocol for blockchains. IEEE Transactions on Dependable and Secure Computing 21, 4 (2023), 2478–2493. [32] Philipp Jovanovic, Lefteris Kokoris-Kogias, Bryan Kumara, Alberto Sonnino, Pasindu Tennage, and Igor Zablotchi. 2025. Mahi-mahi: Low-latency asynchronous bft dag-based consensus. In 2025 IEEE 45th International Conference on Distributed Computing Systems (ICDCS). IEEE, 549–559. [33] Idit Keidar, Eleftherios Kokoris-Kogias, Oded Naor, and Alexander Spiegelman. 2021. All you need is dag. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing. 165–175. [34] Idit Keidar, Oded Naor, Ouri Poupko, and Ehud Shapiro. 2023. Cordial Miners: Fast and Efficient Consensus for Every Eventuality. In 37th International Symposium on Distributed Computing (DISC 2023). Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 26–1. [35] Ramakrishna Kotla, Lorenzo Alvisi, Mike Dahlin, Allen Clement, and Edmund Wong. 2007. Zyzzyva: speculative byzantine fault tolerance. In Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles. 45–58. [36] Hanzheng Lyu, Shaokang Xie, Jianyu Niu, Chen Feng, Yinqian Zhang, and Ivan Beschastnikh. 2025. Ladon: High-Performance Multi-BFT Consensus via Dynamic Global Ordering. In Proceedings of the Twentieth European Conference on Computer Systems. 226–242. [37] Dahlia Malkhi and Kartik Nayak. 2023. Hotstuff-2: Optimal two-phase responsive bft. Cryptology ePrint Archive (2023). [38] Dahlia Malkhi, Chrysoula Stathakopoulou, and Maofan Yin. 2024. Bbca-chain: Low latency, high throughput bft consensus on a dag. In International Conference on Financial Cryptography and Data Security. Springer, 51–73. [39] Oded Naor, Mathieu Baudet, Dahlia Malkhi, and Alexander Spiegelman. 2021. Cogsworth: Byzantine view synchronization. (2021). [40] Nibesh Shrestha, Rohan Shrothrium, Aniket Kate, and Kartik Nayak. 2025. Sailfish: Towards improving the latency of dag-based bft. In 2025 IEEE Symposium on Security and Privacy (SP). IEEE, 1928–1946. [41] Nibesh Shrestha, Qianyu Yu, Aniket Kate, Giuliano Losa, Kartik Nayak, and Xuechao Wang. 2025. Optimistic, signature-free reliable broadcast and its applications. In Proceedings of the 2025 ACM SIGSAC Conference on Computer and Communications Security. 3780–3794. [42] Alexander Spiegelman, Balaji Arun, Rati Gelashvili, and Zekun Li. 2024. Shoal: Improving dag-bft latency and robustness. In International Conference on Financial Cryptography and Data Security. Springer, 92–109. [43] Alexander Spiegelman, Neil Giridharan, Alberto Sonnino, and Lefteris KokorisKogias. 2022. Bullshark: Dag bft protocols made practical. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. 2705–2718. [44] Alexander Spiegelman, Neil Giridharan, Alberto Sonnino, and Lefteris KokorisKogias. 2022. Bullshark: The partially synchronous version. arXiv preprint arXiv:2209.05633 (2022). [45] Chrysoula Stathakopoulou, Tudor David, and Marko Vukolic. 2019. Mir-bft: High-throughput bft for blockchains. arXiv preprint arXiv:1906.05552 92 (2019). [46] Chrysoula Stathakopoulou, Matej Pavlovic, and Marko Vukolić. 2022. State machine replication scalability made simple. In Proceedings of the Seventeenth European Conference on Computer Systems. 17–33. [47] SuiScan. 2026. Suiscan: Transaction Blocks Explorer. Retrieved Accessed: 2026-01-31 from https://suiscan.xyz/mainnet/txs/tx-blocks [48] Giorgos Tsimos, Anastasios Kichidis, Alberto Sonnino, and Lefteris KokorisKogias. 2024. Hammerhead: Leader reputation for dynamic scheduling. In 2024 IEEE 44th International Conference on Distributed Computing Systems (ICDCS). IEEE, 1377–1387. [49] Lei Yang, Seo Jin Park, Mohammad Alizadeh, Sreeram Kannan, and David Tse. 2022. { DispersedLedger } : { High-Throughput } byzantine consensus on variable bandwidth networks. In 19th USENIX Symposium on Networked Systems Design and Implementation (NSDI 22). 493–512.

Clownfish : Scaling DAG-based BFT Consensus via Sparse Edges

[50] Maofan Yin, Dahlia Malkhi, Michael K Reiter, Guy Golan Gueta, and Ittai Abraham. 2019. HotStuff: BFT consensus with linearity and responsiveness. In Proceedings of the 2019 ACM symposium on principles of distributed computing. 347–356. [51] Qianyu Yu, Giuliano Losa, Nibesh Shrestha, and Xuechao Wang. 2025. Angelfish: Leader, DAG, or Anywhere in Between. arXiv preprint arXiv:2509.15847 (2025).

A

Additional Illustrations

Figure 7 provides an illustration of the fast-vote mechanism in Section 4.1. The left side illustrates the liveness violation. Since replica 𝑝 3 skips from round 𝑟 to round 𝑟 + 2 and the Byzantine replica 𝑝 4 does not reference 𝐿𝑉𝑟 , 𝐿𝑉𝑟 fails to receive sufficient votes to be committed. Similarly, as replica 𝑝 1 skips from round 𝑟 + 1 to round 𝑟 + 3 (or higher), 𝐿𝑉𝑟 +1 also fails to be committed. The right side shows the efficacy of the fast-vote. Despite skipping rounds, replicas 𝑝 3 and 𝑝 1 still cast fast-votes for 𝐿𝑉𝑟 and 𝐿𝑉𝑟 +1 respectively, enabling them to be committed. Figure 8 provides an illustration of Multi-leader Clownfish. All replicas are configured as leaders. In the left side, according to the commit rule, all leader vertices in round 𝑟 are directly committed. In round 𝑟 + 1, since 𝐿3 has not been delivered, only 𝐿1 and 𝐿2 are directly committed. The main leader 𝐿1 in round 𝑟 + 2 need to 3 provide 𝑁𝑉𝐶𝑟𝐿+1 . Due to the presence of 𝐿𝑉𝑟 +1 , auxiliary edges are omitted. In the right side, no leader vertex in round 𝑟 + 1 can be directly committed in the absence of 𝐿𝑉𝑟 +1 . The main leader 𝐿1 in round 𝑟 + 2 is required to provide 𝑁𝑉𝐶𝑟 +1 and connect to the leader vertices 𝐿1, 𝐿2 and 𝐿3 in round 𝑟 via auxiliary edges.

B

Clownfish with Consistent Broadcast

We consider the CBC implementation presented in Narwhal [19] (referred to as Narwhal’s CBC), which is adopted by many DAGbased protocols. Specifically, to broadcast a vertex 𝑣 for round 𝑟 , the sender 𝑝𝑖 first broadcasts 𝑚 := ⟨𝑣, 𝑟, 𝑖⟩𝑖 to all replicas. Upon receiving the valid 𝑚, a replica 𝑝 𝑗 signs it and sends ⟨ℎ𝑎𝑠ℎ(𝑣), 𝑟, 𝑖⟩ 𝑗 back to 𝑝𝑖 . Once 𝑝𝑖 collects at least 2𝑓 + 1 valid signatures, it aggregates them into a certificate 𝑐𝑒𝑟𝑡 (𝑣) and broadcasts it to all replicas. As described in Narwhal [19], if a replica receives 𝑐𝑒𝑟𝑡 (𝑣) but lacks the content of 𝑣, it can fetch it from other replicas via random pulling. We provide a detailed specification of CBC-based Clownfish in Section B.1, analyze its theoretical properties in Section B.2, and finally discuss the multi-leader version in Section B.3.

B.1

Protocol Description

The DAG structure of CBC-based Clownfish is the same as basic Clownfish. Since the data fetching process is off the critical path, we omit the details of data fetching from the consensus protocol description. Briefly, any replica that misses the data associated with a specific certificate can retrieve it from other replicas within an expected constant number of requests (guaranteed by the fact that at least 𝑓 + 1 honest replicas possess the data). Unless stated otherwise, we adopt the notation established in basic Clownfish. We denote the availability certificate corresponding to 𝐿𝑉𝑟 as 𝐿𝐶𝑟 . The pseudocode of CBC-based Clownfish are presented in Algorithm 5. To minimize redundancy, we present only the lines of code that differ from basic Clownfish. Text highlighted in magenta explicitly denotes the modifications relative to basic Clownfish.

Leveraging certificates. By employing CBC, a vertex is considered delivered immediately upon the receipt of its corresponding certificate (Line 1). Due to network asynchrony or Byzantine senders, a replica might possess only the certificate of a vertex. Prior to the completion of data fetching, the replica may remain unaware of the transactions and references within the vertex. We reiterate that not hinder the protocol from committing the vertex or advancing to subsequent rounds. A crucial distinction between CBC-based Clownfish and basic Clownfish is that a replica can add a vertex into its local DAG prior to retrieving its content and causal history (Lines 4–6). The sole trade-off is that the ordering of its causal history (which is off the critical path) may need additional waiting time, since some references might be temporarily unknown.

Explicit round synchronization. Given that CBC lacks Property 1, ensuring round synchronization in CBC-based Clownfish is more challenging than in basic Clownfish. First, we mandate that all replicas broadcast the certificate 𝐿𝐶𝑟 upon delivering it (Line 13). This serves to prevent a Byzantine leader from disrupting round synchronization by selectively sending certificates to only a subset of replicas (since replicas are required to await the leader vertex). Merely relying on the broadcasting of 𝐿𝐶𝑟 and 𝑁𝑉𝐶𝑟 is insufficient to ensure that 𝐿𝑟 +1 enters round 𝑟 + 1, since a valid 𝐿𝑉𝑟 +1 is required to reference at least 2𝑓 + 1 vertices from round ≥ 𝑟 via strong edges (Line 51). The reason for considering vertices in rounds > 𝑟 will be explained in the following paragraphs. The primary issue here is that Byzantine replicas can refuse to send certificates to 𝐿𝑟 +1 . Even if an honest replica has received 2𝑓 + 1 certificates from rounds ≥ 𝑟 and entered round 𝑟 + 1, we cannot guarantee that 𝐿𝑟 +1 has also received these certificates (as some may originate from Byzantine senders). To address this problem, we mandate that any replica possessing a sufficient number of certificates sends a new-round message to 𝐿𝑟 +1 (Lines 10–11). A new-round message for round 𝑟 + 1 encapsulates a set of at least 2𝑓 + 1 certificates from rounds ≥ 𝑟 (Line 31). Leveraging these certificates, 𝐿𝑟 +1 can successfully create a valid new vertex (Line 37). The round-skipping rules in CBC-based Clownfish also differ from basic Clownfish (Lines 7, 15, 19). The intuition behind this is that CBC does not guarantee the timely synchronization of local DAG views across replicas, even after GST. By permitting replicas to consider CBC from higher rounds, we prevent honest replicas from being stalled due to the inability to timely retrieve certificates from Byzantine senders (see the proof of Lemma 7 and Lemma 18 to understand its specific role). Under these rules, a scenario may arise where the total number of vertices in a specific round falls below 2𝑓 + 1. Assuming that 𝑓 Byzantine replicas have not broadcast vertices for round 𝑟 . Upon receiving 𝐿𝐶𝑟 and 𝑓 + 1 certificates in round 𝑟 , these Byzantine replicas (provided they are not 𝐿𝑟 +1 ) can immediately broadcast vertices for round 𝑟 + 1. If these vertices complete CBC before 𝑓 lagging honest replicas enter round 𝑟 , honest replicas will advance to round 𝑟 + 1 in accordance with Line 7. This results in only 𝑓 + 1 vertices existing in round 𝑟 . Consequently, we permit 𝐿𝑉𝑟 +1 to reference vertices from rounds higher than 𝑟 via strong edges to satisfy the 2𝑓 + 1 threshold.

Feifan Wang, Jingfan Yu, Zixi Cai, and Zhixuan Fang

Figure 7: Illustration of Clownfish’s fast-vote mechanism.

Figure 8: Illustration of Multi-leader Clownfish. Delay the round timer. Existing DAG-based protocols (including basic Clownfish) initiate the timer immediately upon entering a round [40, 43]. In CBC-based Clownfish, this approach may cause a long timeout duration. The intuition is that when the first honest replica enters round 𝑟 +1, the remaining replicas are only guaranteed to enter round 𝑟 within Δ (after GST). Consequently, in the worstcase, the timeout duration must account for the latency required for lagging honest replicas to complete the CBC for round 𝑟 and subsequently advance to round 𝑟 +1. To reduce the timeout duration, a replica in CBC-based Clownfish defers the initialization of the timer until it has received the first message of CBC from 2𝑓 + 1 distinct replicas for the corresponding round or higher (Line 54). This strategy effectively leverages the presence of at least 𝑓 + 1 first messages from honest replicas, which guarantees that the remaining replicas can directly enter round 𝑟 + 1 within Δ (by Line 15). We analyze the benefits of this design in Section B.2.

B.2

Correctness and Efficiency Analysis

The correctness proof is presented in Appendix C.2 Communication complexity. When using Narwhal’s CBC, the size of each reference is 𝑂 (𝜆) (assuming threshold signatures). Consequently, the delivery of a leader vertex incurs a communication overhead of 𝑂 (𝜆𝑛 2 ), whereas the delivery of a non-leader vertex incurs 𝑂 (𝜆𝑛). The all-to-all broadcasting of the leader certificate necessitates 𝑂 (𝜆𝑛 2 ) additional communication. Furthermore, each replica is required to transmit a new-round message of size 𝑂 (𝜆𝑛) to the leader, resulting in a total communication overhead of 𝑂 (𝜆𝑛 2 ). In summary, the total per-round metadata communication complexity of CBC-based Clownfish is 𝑂 (𝜆𝑛 2 ). Although data fetching is off the critical path, it impacts the communication complexity in bad case. Specifically, 𝑂 (𝑛) replicas may request a total of 𝑂 (𝜆𝑛) data (the sum of metadata contained

Clownfish : Scaling DAG-based BFT Consensus via Sparse Edges

Algorithm 5 CBC-based Clownfish’s pseudocode for replica 𝑝𝑖 Local variables: struct vertex 𝑣 ; struct fast-vote 𝑓 𝑣 struct new-round 𝑛𝑟 : 𝑛𝑟 .𝑟𝑜𝑢𝑛𝑑 - the round to be entered by 𝑛𝑟 𝑛𝑟 .𝑠𝑜𝑢𝑟𝑐𝑒 - the replica that sends 𝑛𝑟 𝑛𝑟 .𝑐𝑒𝑟𝑡𝑠 - a set of certificates in round ≥ 𝑛𝑟 .𝑟𝑜𝑢𝑛𝑑 − 1 𝐷𝐴𝐺𝑖 [ ] - An array of sets of certificates (indexed by rounds) 𝑙𝑎𝑠𝑡𝐿𝑒𝑎𝑑𝑒𝑟 - The most recent delivered leader vertex’s certificate

⊲ The struct of a new-round message for the leader

⊲ Ensure the leader of 𝑛𝑟 .𝑟𝑜𝑢𝑛𝑑 can receive 2𝑓 + 1 certificates

1: upon c_deliver𝑖 (𝑣, 𝑟, 𝑝 ) do ⊲ Receive 𝑣 ’s certificate 2: set 𝑣𝑐 ← 𝑣 ’s certificate 3: if is_valid (𝑣𝑐 ) then 4: 𝐷𝐴𝐺𝑖 [𝑟 ] ← 𝐷𝐴𝐺𝑖 [𝑟 ] ∪ {𝑣𝑐 } 5: if missing the content of 𝑣 then 6: start the data fetching of 𝑣 Ð 7: upon | 𝑟 ′ ≥𝑟 −1 𝐷𝐴𝐺𝑖 [𝑟 ′ ] from different sources | ≥ 2𝑓 + 1 ∧ (𝐿𝐶𝑟 or 𝑁𝑉 𝐶𝑟 is received ) for 𝑟 ≥ 𝑟𝑜𝑢𝑛𝑑 do 8: if 𝑟 > 𝑟𝑜𝑢𝑛𝑑 then ⊲ Skip to a higher round (rule 1) 9: send_fast_vote(𝑟𝑜𝑢𝑛𝑑 + 1, 𝑟 ) 10: 𝑛𝑟 ← create_new_round(𝑟 + 1) ⊲ Explicit round synchronization 11: send ⟨new-round, 𝑛𝑟 ⟩𝑖 to 𝐿𝑟 +1 12: if 𝐿𝐶𝑟 is received then 13: broadcast 𝐿𝐶𝑟 14: advance_round(𝑟 + 1) 15: upon receiving a set M of ≥ 𝑓 + 1 first messages for round ≥ 𝑟 + 1 from different sources ∧ (𝐿𝐶𝑟 or 𝑁𝑉 𝐶𝑟 is received) for 𝑟 ≥ 𝑟𝑜𝑢𝑛𝑑 do 16: if 𝑟 > 𝑟𝑜𝑢𝑛𝑑 then ⊲ Skip to a higher round (rule 2) 17: send_fast_vote(𝑟𝑜𝑢𝑛𝑑 + 1, 𝑟 ) 18: advance_round(𝑟 + 1) 19: upon receiving 𝐿𝐶𝑟 for 𝑟 > 𝑟𝑜𝑢𝑛𝑑 do ⊲ Skip to a higher round (rule 3) 20: send_fast_vote(𝑟𝑜𝑢𝑛𝑑 + 1, 𝑟 ) and advance_round(𝑟 + 1) 21: upon receiving 𝐿𝐶𝑟 for 𝑟 > 𝑙𝑎𝑠𝑡𝐿𝑒𝑎𝑑𝑒𝑟 .𝑟𝑜𝑢𝑛𝑑 do 22: if haven’t sent ⟨no-vote, 𝑟 ⟩ before then 23: 𝑙𝑎𝑠𝑡𝐿𝑒𝑎𝑑𝑒𝑟 ← 𝐿𝐶𝑟 24: procedure broadcast_vertex(𝑟 ) 25: 𝑣 ← create_new_vertex(𝑟 ) 26: try_add_to_dag(𝑣 ) 27: c_bcast𝑖 (𝑣, 𝑟 )

28: procedure create_new_round(𝑟 ) 29: 𝑛𝑟 .𝑟𝑜𝑢𝑛𝑑 ← 𝑟 30: 𝑛𝑟 .𝑠𝑜𝑢𝑟𝑐𝑒 ←Ð𝑝𝑖 31: 𝑛𝑟 .𝑐𝑒𝑟𝑡𝑠 ← 𝑟 ′ ≥𝑟 −1 𝐷𝐴𝐺𝑖 [𝑟 ′ ] from different sources 32: return 𝑛𝑟 33: procedure create_new_vertex(𝑟 ) 34: (𝑣.𝑟𝑜𝑢𝑛𝑑, 𝑣.𝑠𝑜𝑢𝑟𝑐𝑒, 𝑣.𝑏𝑙𝑜𝑐𝑘 ) ← (𝑟, 𝑝𝑖 , 𝑏𝑙𝑜𝑐𝑘𝑠𝑇 𝑜𝑃𝑟𝑜𝑝𝑜𝑠𝑒.dequeue ) 35: set_leader_edge(𝑣 ) 36: if 𝑝𝑖 = 𝐿𝑟 then Ð 37: 𝑣.𝑠𝑡𝑟𝑜𝑛𝑔𝐸𝑑𝑔𝑒𝑠 ← 𝑟 ′ ≥𝑟 −1 𝐷𝐴𝐺𝑖 [𝑟 ′ ] from different sources 38: if š𝑣 ′ ∈ 𝐷𝐴𝐺𝑖 [𝑟 − 1] : 𝑣 ′ .𝑠𝑜𝑢𝑟𝑐𝑒 = 𝐿𝑟 −1 then 39: 𝑣.𝑛𝑣𝑐 ← 𝑁𝑉 𝐶𝑟 −1 40: set_weak_edges(𝑣, 𝑟 ) 41: set_self_edges(𝑣 ) 42: return 𝑣 43: procedure send_fast_vote(𝑠𝑡𝑎𝑟𝑡, 𝑒𝑛𝑑 ) 44: start a new 𝑡𝑖𝑚𝑒𝑟 45: for 𝑟 ′ = 𝑠𝑡𝑎𝑟𝑡 up to 𝑒𝑛𝑑 simultaneously do 46: if c_deliver𝑖 (∗, 𝑟 ′ − 1, 𝐿𝑟 ′ −1 ) before timeout ∧ 𝑁𝑉 𝐶𝑟 ′ −1 is not received ∧ haven’t sent ⟨no-vote, 𝑟 ⟩𝑖 before then 47: 𝑓 𝑣 ← create_fast_vote(𝑟 ′ ) 48: broadcast ⟨𝑓 𝑣, 𝑟 ′ ⟩ 49: procedure advance_round(𝑟 ) 50: if 𝑝𝑖 = 𝐿𝑟 then Ð 51: wait until | 𝑟 ′ ≥𝑟 −1 𝐷𝐴𝐺𝑖 [𝑟 ′ ] from different sources | ≥ 2𝑓 + 1 52: 𝑟𝑜𝑢𝑛𝑑 ← 𝑟 53: broadcast_vertex(𝑟𝑜𝑢𝑛𝑑 ) 54: upon receiving 2𝑓 + 1 first messages for 𝑟 ′ ≥ 𝑟𝑜𝑢𝑛𝑑 do 55: start 𝑡𝑖𝑚𝑒𝑟 for 𝑟𝑜𝑢𝑛𝑑 ⊲ Delay the timer

in all vertices) from 𝑂 (𝑛) other replicas per round. This results in a communication complexity of 𝑂 (𝜆𝑛 3 ). This scenario manifests only in the presence of 𝑂 (𝑛) Byzantine replicas and upon consecutive failures of the random pull. As noted in previous studies, such a bad case rarely occurs in practice [6, 7]. Even if the bad case occurs, the communication complexity of CBC-based Clownfish remains lower than 𝑂 (𝜆𝑛 4 ) complexity incurred by other protocols under identical conditions.

𝜏 = 4Δ would be insufficient. According to the proof of Lemma 7, the first replica to enter a new round would require to wait for an additional CBC latency for round synchronization. Consequently, 𝜏 must be set to 7Δ. After delaying the timer, although the interval between entering round and initiating the timer still necessitates waiting for round synchronization, this wait becomes responsive, incurring a delay proportional to the actual network latency 𝛿. This is significantly shorter than the timeout duration (proportional to Δ), given that typically 𝛿 ≪ Δ.

Latency analysis. In CBC-based Clownfish, the post-GST commit latency for an honest leader vertex is one CBC latency plus 1𝛿. In good case, the commit latency for non-leader vertices incurs an additional CBC latency. For Narwhal’s CBC, these corresponding latencies equal to 4𝛿 and 7𝛿, respectively. Next, we evaluate the additional latency incurred by a Byzantine leader. Analogous to basic Clownfish, each Byzantine leader incurs an additional latency of 4Δ + 𝛿. Regarding Sailfish, we assume it operates under RBC properties with parameters (𝑘 1, 𝑘 2 ) = (3, 1) 8 . Under this favorable assumption, Sailfish incurs latencies of 4Δ + 2𝛿 and 5Δ + 2𝛿 in the presence of a single Byzantine leader and consecutive Byzantine leaders, respectively. A comprehensive comparison with other protocols is provided in Table 1. Finally, we analyze the benefits yielded by delaying the timer, which is not captured in Table 1. In the absence of this design, setting 8 In Narwhal’s CBC, only honest senders satisfy this property.

B.3

Multi-leader Clownfish with Consistent Broadcast

With the same objective as Multi-leader Clownfish, we extend CBCbased Clownfish to a multi-leader variant. However, given that Property 2 of CBC is weaker than Property 1 of RBC, implementing a multi-leader version that guarantees both safety and liveness proves to be more intricate. In the subsequent description, we delineate the specific challenges encountered and the corresponding solutions. The pseudocode for CBC-based Multi-leader Clownfish is presented in Algorithm 6, with the differences relative to both CBC-based Clownfish and Multi-leader Clownfish highlighted in magenta. The key challenges without reliable broadcast. Recall that in Multi-leader Clownfish, a leader edge implicitly represents a vote for all leaders with indices preceding it (in the same round). Since

Feifan Wang, Jingfan Yu, Zixi Cai, and Zhixuan Fang

Figure 9: Illustration of CBC-based Multi-leader Clownfish. Due to the absence of 𝐿𝑉𝑟 +1 , 𝐿𝑉𝑟 +2 is required to provide 𝑁𝑉𝐶𝑟 +1 and auxiliary edges. Among the vertices in round 𝑟 + 1 referenced via 𝐿𝑉𝑟 +2 ’s strong edges, 𝐿3 (originating from 𝑝 4 ) contains the highest leader edge. The Byzantine replica 𝑝 4 references 𝐿4 of round 𝑟 via this leader edge, even though 𝐿3 in round 𝑟 does not exist. Consequently, 𝐿𝑉𝑟 +2 is required to connect to 𝐿1 and 𝐿2 in round 𝑟 via auxiliary edges, and 𝑝 provide the 𝑁𝑉𝐶𝑟 3 to prove that 𝐿3 has not been committed.

the properties of RBC guarantee that these leaders will be delivered by all replicas (within a fixed time after GST), within the underlying RBC protocol, all replicas implicitly validate the leader edge by awaiting the delivery of all preceding leader vertices in the same round. Consequently, for any delivered vertex, all leaders represented by its leader edge are guaranteed to be deliverable by the main leader referencing said vertex. However, in the context of CBC, relying solely on the leader edge proves inefficient. Even considering a leader edge within a vertex created by an honest replica, a certificate with lower index may originate from a Byzantine leader. If we persist in requiring replicas to await all certificates to validate the leader edge in the underlying CBC protocol, Byzantine replicas can exploit this to stall the critical path of the consensus. This is primarily because replicas would need to first acquire these certificates via data fetching, incurring additional latency and communication overhead. To address this problem, a straightforward approach is to require replicas to validate only the leader edge in the underlying CBC process. While this strategy eliminates additional waiting periods and does not require the inclusion of additional edges in the vertex, it introduces the risk of the non-existence of certificates with lower indices9 . In such scenarios, the main leader might be unable to provide the requisite auxiliary edge (in accordance with the rules of Multi-leader Clownfish). This poses a significant challenge to ensuring the existence of a leader path. Solve the challenges through additional components. Within the underlying CBC protocol, we require replicas to validate only 9 For instance, a Byzantine replica might intentionally reference a leader edge with

a high index, while a Byzantine leader with a lower index doesn’t initiate the CBC process.

the leader edge and await the receipt of the main leader’s certificate of the same round before deeming the vertex valid (which is not explicitly depicted in the pseudocode). The rationale for awaiting the latter is to prevent Byzantine replicas from referencing a leader vertex in a round where the main leader vertex does not exist, as such a leader edge is invalid. Since a single certificate cannot reflect the leader edge of its corresponding vertex, the main leader might be unable to obtain the leader edges of the referenced vertices (potentially used for creating auxiliary edges). To address this, we require replicas to additionally include the leader edges of vertices in the new-round message (Line 90). Correspondingly, the delivery rule for a vertex is also modified to require the receipt of both the vertex and the certificate of its leader edge (Lines 58–59). Building upon these, we modify the requirements for auxiliary edges. Regarding 𝐿𝑉𝑟 , we consider the highest leader edge (with round 𝑟 ∗ and index 𝑥 ∗ ) within all vertices referenced by its strong edges, as in Multi-leader Clownfish (Line 112). Given that such an edge may originate from a Byzantine replica and it may not send new-round messages as required, 𝐿𝑟 does not necessarily possess all certificates for ML𝑟 ∗ [: 𝑥 ∗ ]. In this case, we merely mandate that the main leader includes a 𝑁𝑉𝐶 with an index ≤ 𝑥 ∗ to prove that subsequent leader vertices cannot be directly committed (Lines 79– 84, 113). Figure 9 provides a illustration of this scenario. To ensure that the main leader receives the 𝑁𝑉𝐶s and certificates to create vertex, we mandate that replicas transmit additional messages to the main leader upon entering a new round (even via skipping). Specifically, replicas are required to send certificates for all leader vertices preceding 𝑙𝑎𝑠𝑡𝐿𝑒𝑎𝑑𝑒𝑟 within its respective round (Line 96). Furthermore, replicas must send no-vote messages for all leaders after 𝑙𝑎𝑠𝑡𝐿𝑒𝑎𝑑𝑒𝑟 (Lines 97–100). Note that we require replicas to transmit these messages to multiple main leaders after 𝑙𝑎𝑠𝑡𝐿𝑒𝑎𝑑𝑒𝑟 , rather than solely to the main leader of the new round. Intuitively, this aims to prevent any main leader from failing to meet the requirements for entering a new round, which could further block the round synchronization (see Lemma 18). We demonstrate in the proofs that the main leader is capable of leveraging these messages to establish valid 𝑎𝑢𝑥𝐸𝑑𝑔𝑒𝑠 and create a new vertex. We provide the complete correctness proof for CBC-based Multileader Clownfish in Appendix C.4.

Communication complexity. The number of references within a vertex is identical to that in CBC-based Clownfish. Upon entering a new round, the total number of certificates sent by each replica to the main leader remains 𝑂 (𝑛). In the good or average case, the number of no-vote and certificates sent by each replica is 𝑂 (𝑛). This is because the average number of rounds between 𝑙𝑎𝑠𝑡𝐿𝑒𝑎𝑑𝑒𝑟 and the current round is 𝑂 (1). In the bad case, the number of no-vote and certificates sent by each replica may reach 𝑂 (𝑛 2 ). This arises because, in the event of 𝑂 (𝑛) consecutive failures, the number of rounds between 𝑙𝑎𝑠𝑡𝐿𝑒𝑎𝑑𝑒𝑟 and the current round extends to 𝑂 (𝑛). The communication overhead of this scenario is equivalent to requiring replicas to broadcast all (𝑂 (𝑛)) no-vote messages and certificates, resulting in a total communication complexity of 𝑂 (𝜆𝑛 3 ) per round. In summary, the per-round metadata communication complexity of CBC-based Multi-leader Clownfish is 𝑂 (𝜆𝑛 2 ) in the good (or

Clownfish : Scaling DAG-based BFT Consensus via Sparse Edges

Algorithm 6 CBC-based Multi-leader Clownfish’s pseudocode for replica 𝑝𝑖 Local variables: struct vertex 𝑣 : 𝑣.𝑛𝑣𝑐 - a no-vote certificate of a leader vertex in 𝑣.𝑟𝑜𝑢𝑛𝑑 − 1 𝑣.𝑛𝑣𝑐 ′ - a no-vote certificate of a secondary leader vertex in round < 𝑣.𝑟𝑜𝑢𝑛𝑑 − 1 56: upon c_deliver𝑖 (𝑣, 𝑟, 𝑝 ) do ⊲ Receive 𝑣 ’s certificate 57: set 𝑣𝑐 ← 𝑣 ’s certificate 58: set 𝑙𝑐 ← 𝑣.𝑙𝑒𝑎𝑑𝑒𝑟 𝐸𝑑𝑔𝑒 59: if is_valid (𝑣𝑐 ) ∧ is_valid (𝑙𝑐 ) then 60: 𝐷𝐴𝐺𝑖 [𝑟 ] ← 𝐷𝐴𝐺𝑖 [𝑟 ] ∪ {𝑣𝑐 } 61: if missing the content of 𝑣 then 62: start the data fetching of 𝑣 63: procedure create_new_vertex(𝑟 ) 64: 𝑣.𝑟𝑜𝑢𝑛𝑑 ← 𝑟 65: 𝑣.𝑠𝑜𝑢𝑟𝑐𝑒 ← 𝑝𝑖 66: 𝑣.𝑏𝑙𝑜𝑐𝑘 ← 𝑏𝑙𝑜𝑐𝑘𝑠𝑇 𝑜𝑃𝑟𝑜𝑝𝑜𝑠𝑒.dequeue 67: set_leader_edge(𝑣 ) 68: if 𝑝𝑖 = 𝐿𝑟 then Ð 69: 𝑣.𝑠𝑡𝑟𝑜𝑛𝑔𝐸𝑑𝑔𝑒𝑠 ← 𝑟 ′ ≥𝑟 −1 𝐷𝐴𝐺𝑖 [𝑟 ′ ] ′ 70: if ∃𝑣 ∈ 𝐷𝐴𝐺𝑖 [𝑟 − 1] : 𝑣 ′ .𝑠𝑜𝑢𝑟𝑐𝑒 = 𝐿𝑟 −1 then 71: for ℓ ∈ M L𝑟 −1 do 72: if š𝑣 ′ ∈ 𝐷𝐴𝐺𝑖 [𝑟 − 1] : 𝑣 ′ .𝑠𝑜𝑢𝑟𝑐𝑒 = ℓ then 73: 𝑣.𝑛𝑣𝑐 ← 𝑁𝑉 𝐶𝑟ℓ −1 74: break 75: else 76: 𝑣.𝑛𝑣𝑐 ← 𝑁𝑉 𝐶𝑟 −1 ′ {𝑣 ′ .𝑙𝑒𝑎𝑑𝑒𝑟 𝐸𝑑𝑔𝑒 } 77: 𝑣 ∗ ← arg max𝑣 ′ ∈ Ð ′ 𝑟 ≥𝑟 −1 𝐷𝐴𝐺𝑖 [𝑟 ] 78: (𝑟 ∗ , 𝑥 ∗ ) ← (𝑣 ∗ .𝑟𝑜𝑢𝑛𝑑, 𝑣 ∗ .𝑖𝑛𝑑𝑒𝑥 ) 79: for ℓ ∈ M L𝑟 ∗ [: 𝑥 ∗ ] do 80: if š𝑣 ′ ∈ 𝐷𝐴𝐺𝑖 [𝑟 ∗ ] : 𝑣 ′ .𝑠𝑜𝑢𝑟𝑐𝑒 = ℓ then 81: 𝑣.𝑛𝑣𝑐 ′ ← 𝑁𝑉 𝐶𝑟ℓ ∗ 82: 𝑙 ∗ ← 𝑙 .𝑖𝑛𝑑𝑒𝑥 − 1 83: break 84: 𝑣.𝑎𝑢𝑥𝐸𝑑𝑔𝑒𝑠 ← { get_leader_vertex(𝑟 ∗ , 𝑥 ) for 𝑥 = 1 to min(𝑙 ∗ , 𝑥 ∗ ) } 85: set_weak_edges(𝑣, 𝑟 ) 86: set_self_edges(𝑣 ) 87: return 𝑣

average) case and 𝑂 (𝜆𝑛 3 ) in the bad case. This remains consistent with CBC-based Clownfish. Latency analysis. In the best-case scenario, the commit latency for every leader vertex is 4𝛿. In a non-optimal case, the main leader vertex requires an additional 𝛿 to gather 𝑁𝑉𝐶s and certificates. Consequently, the direct commit latency for all leader vertices becomes 5𝛿. Analogous to the reasoning presented for Multi-leader 𝑛−𝑓 +3 Clownfish, provided that 𝑥 > leader vertices are directly 3 committed, the average commit latency of CBC-based Multi-leader Clownfish outperforms that of CBC-based Clownfish.

C Proofs C.1 Correctness Proof of Clownfish For the sake of brevity, throughout all our proofs, we implicitly use the following fact guaranteed by the properties of RBC and CBC. Fact 1. Any vertex appearing at the same position (i.e., the same round and the same source) within the DAG views of all honest replicas must be identical. The core of safety. As highlighted in the discussion of main challenges, the cornerstone of the protocol’s safety is ensuring that a path exists between a leader vertex committed by any honest replica and all subsequent leader vertices. We formalize this property through the following lemma.

⊲ The struct of a vertex in the DAG ⊲ Only main leader vertices need to contain

88: procedure create_new_round(𝑟 ) 89: 𝑛𝑟 .𝑟𝑜𝑢𝑛𝑑 ←Ð𝑟 𝑛𝑟 .𝑠𝑜𝑢𝑟𝑐𝑒 ← 𝑝𝑖 Ð ′ 90: 𝑛𝑟 .𝑐𝑒𝑟𝑡𝑠 ← 𝑟 ′ ≥𝑟 −1 𝐷𝐴𝐺 Ð 𝑖 [𝑟 ] {𝑣 ′ .𝑙𝑒𝑎𝑑𝑒𝑟 𝐸𝑑𝑔𝑒 | 𝑣 ′ ∈ 𝑟 ′ ≥𝑟 −1 𝐷𝐴𝐺𝑖 [𝑟 ′ ] } 91: return 𝑛𝑟 92: procedure advance_round(𝑟 ) 93: if 𝑙𝑎𝑠𝑡𝐿𝑒𝑎𝑑𝑒𝑟 .𝑟𝑜𝑢𝑛𝑑 < 𝑟 − 1 then 94: (𝑟 ∗ , 𝑥 ∗ ) ← (𝑙𝑎𝑠𝑡𝐿𝑒𝑎𝑑𝑒𝑟 .𝑟𝑜𝑢𝑛𝑑, 𝑙𝑎𝑠𝑡𝐿𝑒𝑎𝑑𝑒𝑟 .𝑖𝑛𝑑𝑒𝑥 ) 95: for ∀ℓ ∈ M L𝑟 ∗ [: 𝑥 ∗ ] , ∀𝑟 ′′ = 𝑟 ∗ + 1 to 𝑟 do ⊲ additional certificates 96: send get_vertex(ℓ, 𝑟 ∗ ) to 𝐿𝑟 ′′ 97: for ∀ℓ ∈ M L𝑟 ∗ [𝑥 ∗ + 1 :] , ∀𝑟 ′′ = 𝑟 ∗ + 1 to 𝑟 do ⊲ additional no-votes 98: send ⟨no-vote, ℓ, 𝑟 ∗ ⟩ to 𝐿𝑟 ′′ 99: for ∀𝑟 ′ = 𝑟 ∗ + 1 to 𝑟 − 2, ∀ℓ ∈ M L𝑟 ′ :, ∀𝑟 ′′ = 𝑟 ∗ + 1 to 𝑟 do 100: send ⟨no-vote, ℓ, 𝑟 ′ ⟩ to 𝐿𝑟 ′′ 101: for ℓ ∈ M L𝑟 −1 do ⊲ iterative over M L𝑟 −1 in order 102: if š𝑣 ′ ∈ 𝐷𝐴𝐺𝑖 [𝑟 − 1] : 𝑣 ′ .𝑠𝑜𝑢𝑟𝑐𝑒 = ℓ then 103: send ⟨no-vote, ℓ, 𝑟 − 1⟩𝑖 to 𝐿𝑟 104: if 𝑙𝑎𝑠𝑡𝐿𝑒𝑎𝑑𝑒𝑟 = 𝐿𝐶𝑟 −1 ∧ 𝑙 .𝑖𝑛𝑑𝑒𝑥 > 2 then 105: 𝑙𝑎𝑠𝑡𝐿𝑒𝑎𝑑𝑒𝑟 ← get_leader(𝑟 − 1, ℓ.𝑖𝑛𝑑𝑒𝑥 − 1) 106: if 𝑝𝑖 = 𝐿𝑟 then Ð 107: wait until | 𝑟 ′ ≥𝑟 −1 𝐷𝐴𝐺𝑖 [𝑟 ′ ] from different sources | ≥ 2𝑓 + 1 108: if 𝑝𝑖 = 𝐿𝑟 and c_deliver𝑖 (𝐿𝑉𝑟 −1 , 𝑟 − 1, 𝐿𝑟 −1 ) then 109: wait until ( (∃𝑣 ′ ∈ 𝐷𝐴𝐺𝑖 [𝑟 − 1] : 𝑣 ′ .𝑠𝑜𝑢𝑟𝑐𝑒 = ℓ ) for ∀ℓ ∈ ′ M L𝑟 −1 [: 𝑥 ] ) ∧ (𝑁𝑉 𝐶𝑟ℓ −1 is received for ℓ ′ = M L𝑟 −1 [𝑥 + 1] ) 110: if 𝑝𝑖 = 𝐿𝑟 and 𝑁𝑉 𝐶𝑟 −1 is received then ′ {𝑣 ′ .𝑙𝑒𝑎𝑑𝑒𝑟 𝐸𝑑𝑔𝑒 } 111: 𝑣 ∗ ← arg max𝑣 ′ ∈ Ð ′ 𝑟 ≥𝑟 −1 𝐷𝐴𝐺𝑖 [𝑟 ] 112: (𝑟 ∗ , 𝑥 ∗ ) ← (𝑣 ∗ .𝑟𝑜𝑢𝑛𝑑, 𝑣 ∗ .𝑖𝑛𝑑𝑒𝑥 ) 113: wait until (∃𝑥 < 𝑥 ∗ : ( (∃𝑣 ∗ ∈ 𝐷𝐴𝐺𝑖 [𝑟 ∗ ] : 𝑣 ∗ .𝑠𝑜𝑢𝑟𝑐𝑒 = ℓ ) for ′ ∀ℓ ∈ M L𝑟 ∗ [: 𝑥 ] ) and (𝑁𝑉 𝐶𝑟ℓ ∗ is received for ℓ ′ = M L𝑟 ∗ [𝑥 + 1] ) ) or ( (∃𝑣 ∗ ∈ 𝐷𝐴𝐺𝑖 [𝑟 ∗ ] : 𝑣 ∗ .𝑠𝑜𝑢𝑟𝑐𝑒 = ℓ ) for ∀ℓ ∈ M L𝑟 ∗ [: 𝑥 ∗ ] ) 114: 𝑟𝑜𝑢𝑛𝑑 ← 𝑟 ; start 𝑡𝑖𝑚𝑒𝑟 for 𝑟𝑜𝑢𝑛𝑑 115: broadcast_vertex(𝑟𝑜𝑢𝑛𝑑 )

Lemma 1. If an honest replica 𝑝𝑖 directly commits the leader vertex 𝐿𝑉𝑟 , then for any valid leader vertex 𝐿𝑉𝑟 ′ in round 𝑟 ′ > 𝑟 , there exists a leader path from 𝐿𝑉𝑟 ′ to 𝐿𝑉𝑟 . Proof. Since 𝑝𝑖 has directly committed 𝐿𝑉𝑟 , there must exist at least 2𝑓 + 1 votes (either first messages or fast-votes) for 𝐿𝑉𝑟 . Among these, at least 𝑓 + 1 originate from honest replicas. Let H denote this set of honest replicas. According to Lines 48–50 of the protocol, the round associated with the 𝑙𝑎𝑠𝑡𝐿𝑒𝑎𝑑𝑒𝑟 variable for any replica in H must satisfy 𝑙𝑎𝑠𝑡𝐿𝑒𝑎𝑑𝑒𝑟 .𝑟𝑜𝑢𝑛𝑑 ≥ 𝑟 . Furthermore, these replicas will not broadcast a ⟨no-vote, 𝑟 ⟩ message (by Line 49 and Line 75). Consequently, any leader edge created by these replicas in subsequent rounds is guaranteed to reference a leader vertex from a round no less than 𝑟 . We now proceed by induction on 𝑟 ′ . Case 𝑟 ′ = 𝑟 + 1: Since |H | ≥ 𝑓 + 1, the property of quorum intersection guarantees that an 𝑁𝑉𝐶𝑟 cannot be formed. Therefore, 𝐿𝑉𝑟 +1 must reference 𝐿𝑉𝑟 via a strong edge. Case 𝑟 ′ ≥ 𝑟 + 2: We assume the inductive hypothesis holds for all leader vertices in rounds 𝑟 ′′ such that 𝑟 < 𝑟 ′′ < 𝑟 ′ . Since 𝐿𝑉𝑟 ′ references at least 2𝑓 + 1 vertices from round 𝑟 ′ − 1 via strong edges, quorum intersection implies that at least one of these vertices originates from a replica in H . We denote one such replica as 𝑝𝑘 . The vertex created by 𝑝𝑘 in round 𝑟 ′ − 1 references a leader vertex 𝐿𝑉𝑟 ∗ via a leader edge. Based on the property of set H derived earlier, we have 𝑟 ∗ ≥ 𝑟 . If 𝑟 ∗ = 𝑟 , the leader path is directly established.

Feifan Wang, Jingfan Yu, Zixi Cai, and Zhixuan Fang

If 𝑟 ∗ > 𝑟 , the inductive hypothesis guarantees that a leader path exists between 𝐿𝑉𝑟 ∗ and 𝐿𝑉𝑟 . By transitivity, a leader path must exist between 𝐿𝑉𝑟 ′ and 𝐿𝑉𝑟 . □ The core of liveness. Given that only leader vertices can be committed, the key of liveness lies in showing that a leader vertex created by an honest replica after GST will receive sufficient votes. We formalize this property through two lemmas. Specifically, Lemma 2 guarantees round synchronization, and Lemma 3 ensures that an honest leader vertex is directly committed.

Next, we prove that Clownfish satisfies the four properties required by BAB (as defined in Section 2.2). We say that a leader vertex 𝐿𝑉 is directly committed by 𝑝𝑖 if 𝑝𝑖 invokes commit_leader(𝐿𝑉 ). A leader vertex is indirectly committed if it is pushed onto the 𝑙𝑒𝑎𝑑𝑒𝑟𝑆𝑡𝑎𝑐𝑘. Furthermore, we say that 𝑝𝑖 consecutively directly commits leader vertices 𝐿𝑉𝑟 and 𝐿𝑉𝑟 ′ if 𝑝𝑖 directly commits both 𝐿𝑉𝑟 and 𝐿𝑉𝑟 ′ without directly committing any leader vertex between 𝑟 and 𝑟 ′ . The Integrity property is straightforward: Theorem 1. Clownfish satisfies Integrity.

Lemma 2. Let 𝑡 be a time after GST. If the first honest replica 𝑝𝑖 enters round 𝑟 at time 𝑡, then all honest replicas will enter round 𝑟 or higher by time 𝑡 + 𝑘 2 Δ. Proof. Since 𝑝𝑖 is the first honest replica to enter round 𝑟 , it could not have advanced via round-skipping. Consequently, 𝑝𝑖 must have delivered 2𝑓 + 1 vertices from round 𝑟 − 1. By Property 1, all honest replicas are guaranteed to deliver these vertices within 𝑘 2 Δ. We proceed by considering the two cases regarding how 𝑝𝑖 entered round 𝑟 . If 𝑝𝑖 enters round 𝑟 by delivering 𝐿𝑉𝑟 −1 , then all honest replicas will deliver 𝐿𝑉𝑟 −1 within 𝑘 2 Δ and subsequently enter round 𝑟 (or higher). If 𝑝𝑖 enters round 𝑟 via 𝑁𝑉𝐶𝑟 −1 , it must have broadcast 𝑁𝑉𝐶𝑟 −1 by time 𝑡. Consequently, all honest replicas will receive 𝑁𝑉𝐶𝑟 −1 within Δ. Given that 𝑘 2 ≥ 1 holds for all known RBC protocols, it follows that all honest replicas will enter round 𝑟 within 𝑘 2 Δ (unless they have already advanced to a higher round). □ Lemma 3. If the first honest replica enters round 𝑟 at time 𝑡 after GST, and the timeout parameters are configured such that 𝜏 = (𝑘 1 + 𝑘 2 )Δ and 𝜏 ′ = 𝑘 2 Δ, then 𝐿𝑉𝑟 is guaranteed to be directly committed before 𝑡 + 𝜏 + Δ provided that 𝐿𝑟 is honest. Proof. The first honest replica to enter round 𝑟 initiates the timer at time 𝑡. By Lemma 2, all honest replicas (including 𝐿𝑟 ) are guaranteed to enter round 𝑟 or higher by time 𝑡 + 𝑘 2 Δ. It is obvious that no honest replica will broadcast ⟨no-vote, 𝑟 ⟩ before 𝑡 + 𝜏. Consequently, 𝑁𝑉𝐶𝑟 cannot exist before 𝑡 + 𝜏. The definition of 𝑡 also ensures that 𝑁𝑉𝐶 corresponding to higher round cannot exist before 𝑡 +𝜏. Thus, honest replicas cannot enter a round higher than 𝑟 via 𝑁𝑉𝐶. Consider an honest replica 𝑝𝑖 . If 𝑝𝑖 has not entered a round higher than 𝑟 by time 𝑡 + 𝜏, then by Property 1, it is guaranteed to deliver at least 2𝑓 + 1 vertices from round 𝑟 (including 𝐿𝑉𝑟 ) by time 𝑡 + 𝜏. Subsequently, it will enter round 𝑟 + 1 and create a vertex referencing 𝐿𝑉𝑟 via leader edge. If 𝑝𝑖 enters round 𝑟 + 1 before 𝑡 + 𝜏, since 𝑁𝑉𝐶𝑟 does not exist, the vertex it creates for round 𝑟 + 1 must reference 𝐿𝑉𝑟 . The last case is that 𝑝𝑖 enters a round higher than 𝑟 + 1 before 𝑡 + 𝜏. If it does not enter round 𝑟 + 1 (i.e., it skips round 𝑟 + 1), it must have invoked the send_fast_vote procedure covering round 𝑟 + 1. Since the first honest replica to enter round > 𝑟 + 1 must have delivered 𝐿𝑉𝑟 (given the non-existence of 𝑁𝑉𝐶𝑟 and 𝑁𝑉𝐶𝑟 +1 ), it follows from Property 1 that 𝑝𝑖 will deliver 𝐿𝑉𝑟 within 𝜏 ′ = 𝑘 2 Δ and consequently broadcast a fast-vote for it. In summary, all honest replicas will cast a vote for 𝐿𝑉𝑟 (via either a first message or a fast-vote) by time 𝑡 + 𝜏. This guarantees that 𝐿𝑉𝑟 is directly committed by all honest replicas before 𝑡 +𝜏 + Δ. □

Proof. An honest replica 𝑝𝑖 outputs a_deliver𝑖 (𝑣.𝑏𝑙𝑜𝑐𝑘, 𝑣 .𝑟𝑜𝑢𝑛𝑑, 𝑣.𝑠𝑜𝑢𝑟𝑐𝑒) only if vertex 𝑣 is already in 𝐷𝐴𝐺𝑖 . This implies that 𝑝𝑖 has already output r_deliver𝑖 (𝑣, 𝑣.𝑟𝑜𝑢𝑛𝑑, 𝑣.𝑠𝑜𝑢𝑟𝑐𝑒). Consequently, the theorem follows directly from the Integrity property of RBC. □ We now proceed to establish the Total order property by leveraging Lemma 1. Lemma 4. If an honest replica 𝑝𝑖 directly commits leader vertex 𝐿𝑉𝑟 , and an honest replica 𝑝 𝑗 directly commits leader vertex 𝐿𝑉𝑟 ′ with 𝑟 ′ ≥ 𝑟 , then 𝑝 𝑗 either directly or indirectly commits 𝐿𝑉𝑟 . Proof. The case where 𝑟 ′ = 𝑟 is trivial. When 𝑟 ′ > 𝑟 , by Lemma 1, there exists a leader path from 𝐿𝑉𝑟 ′ to 𝐿𝑉𝑟 . Based on the pseudocode for commit_leader, 𝑝 𝑗 indirectly commits 𝐿𝑉𝑟 if it has not yet directly committed any 𝐿𝑉𝑟 ′′ such that 𝑟 ≤ 𝑟 ′′ < 𝑟 ′ . Otherwise, by an inductive argument, 𝑝 𝑗 has already committed 𝐿𝑉𝑟 when directly committing 𝐿𝑉𝑟 ′′ . □ Lemma 5. If an honest replica 𝑝𝑖 consecutively directly commits leader vertices 𝐿𝑉𝑟𝑖 and 𝐿𝑉𝑟𝑖′ with 𝑟𝑖′ > 𝑟𝑖 , and an honest replica 𝑝 𝑗 consecutively directly commits leader vertices 𝐿𝑉𝑟 𝑗 and 𝐿𝑉𝑟 ′𝑗 with 𝑟 ′𝑗 > 𝑟 𝑗 , then 𝑝𝑖 and 𝑝 𝑗 commit the same leader vertices between rounds max(𝑟𝑖 , 𝑟 𝑗 ) and min(𝑟𝑖′, 𝑟 ′𝑗 ) in the same order. Proof. Without loss of generality, we only need to consider the non-trivial case where 𝑟𝑖 ≤ 𝑟 𝑗 < 𝑟𝑖′ ≤ 𝑟 ′𝑗 . By Lemma 4, both 𝑝𝑖 and 𝑝 𝑗 will commit 𝐿𝑉𝑟𝑖′ . Based on the pseudocode for commit_leader and Lemma 1, upon committing 𝐿𝑉𝑟𝑖′ , both 𝑝𝑖 and 𝑝 𝑗 will indirectly commit all leader vertices that have a leader path to 𝐿𝑉𝑟𝑖′ from rounds 𝑟𝑖′ down to 𝑟 𝑗 . Due to the deterministic logic of commit_leader, 𝑝𝑖 and 𝑝 𝑗 will commit these vertices in the same order. □ Theorem 2. Clownfish satisfies Total order. Proof. By inductively applying Lemma 5 to every pair of honest replicas, we can deduce that all honest replicas commit same leader vertices in the same order. Based on the pseudocode for order_vertices, all honest replicas will traverse the causal histories of these leader vertices in the same deterministic manner, and consequently a_deliver all vertices in the same order. □ Next, we rely on Lemma 2 and Lemma 3 to establish the Validity property. Lemma 6. All honest replicas continuously enter higher rounds.

Clownfish : Scaling DAG-based BFT Consensus via Sparse Edges

Proof. Assume that all honest replicas have entered round 𝑟 or higher. If an honest replica 𝑝𝑖 enter round 𝑟 ′ > 𝑟 at any time, then due to the finiteness of GST and Lemma 2, all honest replicas will eventually enter round 𝑟 ′ or higher. Otherwise, if all honest replicas remain in round 𝑟 , they will invoke broadcast_vertex(𝑟 ) and eventually deliver at least 2𝑓 +1 vertices from round 𝑟 . If any honest replica r_delivers 𝐿𝑉𝑟 before the timeout, then all honest replicas will satisfy the condition to enter round 𝑟 + 1 upon delivering 𝐿𝑉𝑟 . Otherwise, all honest replicas will broadcast ⟨no-vote, 𝑟 ⟩ and receive 𝑁𝑉𝐶𝑟 , which also satisfies the condition to enter round 𝑟 + 1. □ Theorem 3. Clownfish satisfies Validity. Proof. Suppose an honest replica 𝑝𝑖 calls a_bcast(𝑏), which implies that it pushes 𝑏 into the 𝑏𝑙𝑜𝑐𝑘𝑇𝑜𝑃𝑟𝑜𝑝𝑜𝑠𝑒 queue. By Lemma 6, 𝑝𝑖 continuously enters higher rounds and creates new vertices. Consequently, 𝑝𝑖 will eventually create a vertex 𝑣 in some round 𝑟 that contains 𝑏. Due to the Validity property of RBC, all honest replicas will eventually add 𝑣 to the DAG. According to Lemma 3, all honest leader vertices created after GST will be committed by all honest replicas. Facilitated by the weak edges, an honest leader will eventually create a leader vertex that has a path to 𝑣, and this leader vertex will be committed. Based on the pseudocode for order_vertices, all honest replicas will eventually output a_deliver(𝑏, 𝑟, 𝑝𝑖 ). □ Finally, we directly establish the Agreement property: Theorem 4. Clownfish satisfies Agreement. Proof. If an honest replica 𝑝𝑖 outputs a_deliver𝑖 (𝑣.𝑏𝑙𝑜𝑐𝑘, 𝑣.𝑟𝑜𝑢𝑛𝑑, 𝑣.𝑠𝑜𝑢𝑟𝑐𝑒), then 𝑣 must be in the causal history of some committed leader vertex 𝐿𝑉𝑟 . Based on the reasoning in Theorem 3, any honest replica 𝑝 𝑗 will eventually commit a leader vertex 𝐿𝑉𝑟 ′ with 𝑟 ′ ≥ 𝑟 . According to the pseudocode for order_vertices and Lemma 1, 𝑝 𝑗 will eventually output a_deliver 𝑗 (𝑣.𝑏𝑙𝑜𝑐𝑘, 𝑣.𝑟𝑜𝑢𝑛𝑑, 𝑣.𝑠𝑜𝑢𝑟𝑐𝑒) when traversing the causal history of 𝐿𝑉𝑟 . □

C.2

Correctness Proof of CBC-based Clownfish

We first give the key arguments of safety and liveness. The key safety argument. Observe that the commit rules and the format of leader vertices in CBC-based Clownfish- are basically identical to those in basic Clownfish. The sole distinction lies in the fact that references take the form of certificates and may have higher rounds, which provides same guarantees. Consequently, the proof remains identical to Lemma 1 and we omit it here. The key liveness argument. Without Property 1, we must reestablish two key liveness lemmas. The core intuition relies on leveraging the explicit round synchronization and round-skipping rules. We begin by outlining the properties satisfied by CBC[19] after GST. Property 2. Let 𝑡 be a time after GST. If an honest replica consistently broadcasts a vertex 𝑣 at time 𝑡, then all honest replicas will receive the certificate of 𝑣 by time 𝑡 + 3Δ. The following two lemmas correspond to Lemma 2 and Lemma 3 in basic Clownfish.

Lemma 7. Let 𝑡 be a time after GST. If the first honest replica 𝑝𝑖 enters round 𝑟 at time 𝑡, then all honest replicas will enter round 𝑟 or higher by time 𝑡 + 4Δ. Proof. Since 𝑝𝑖 is the first honest replica to enter round 𝑟 , it could not have advanced via skipping. Consequently, 𝑝𝑖 must have received certificates for at least 2𝑓 +1 vertices from different sources in rounds ≥ 𝑟 − 1. Among these, at least 𝑓 + 1 originate from honest replicas (let H denote this set). By virtue of Line 13 and the no-vote mechanism, all replicas are guaranteed to receive either 𝐿𝐶𝑟 −2 or 𝑁𝑉𝐶𝑟 −2 and either 𝐿𝐶𝑟 −1 or 𝑁𝑉𝐶𝑟 −1 within Δ. Given that 𝑝𝑖 sends a new-round message to 𝐿𝑟 , 𝐿𝑟 is guaranteed to obtain at least 2𝑓 +1 certificates from different sources in rounds ≥ 𝑟 − 1 and satisfy the conditions specified in Line 51 within Δ. Furthermore, all replicas will receive the first messages from H within Δ. Since the first honest replica to enter round 𝑟 − 1 must have done so before time 𝑡 and sent a new-round message to 𝐿𝑟 −1 , 𝐿𝑟 −1 is also guaranteed to satisfy the conditions specified in Line 51 within Δ. In conjunction with Line 15, this ensures that all honest replicas will enter round 𝑟 − 1 (or higher) within Δ. After a subsequent latency of 3Δ, all honest replicas will complete the CBC for rounds ≥ 𝑟 − 1 and advance to round 𝑟 (or higher) by Line 7. □ Lemma 8. If the first honest replica enters round 𝑟 at time 𝑡 after GST, and the timeout parameters are configured such that 𝜏 = 4Δ and 𝜏 ′ = Δ, then 𝐿𝑉𝑟 is guaranteed to be directly committed before 𝑡 + 10Δ provided that 𝐿𝑟 is honest. Proof. We begin by establishing a bound on the time at which the timer for round 𝑟 is started. By Lemma 7, all honest replicas are guaranteed to enter round 𝑟 or higher by time 𝑡 + 4Δ. If no honest replica has advanced to a higher round by time 𝑡 + 5Δ, it is certain that all honest replicas will receive 2𝑓 + 1 first messages for round 𝑟 and start the timer for round 𝑟 by time 𝑡 + 5Δ. Conversely, consider the scenario where the first honest replica does advance to a higher round. This replica must have delivered 2𝑓 + 1 vertices from rounds ≥ 𝑟 , implying that it must have initiated the timer prior to this advancement. Let 𝑡 ∗ ≤ 𝑡 + 5Δ denote the time when the first honest replica 𝑝𝑖 initiates the timer for round 𝑟 . Since the set of 2𝑓 + 1 first messages received by 𝑝𝑖 for round ≥ 𝑟 must contain at least 𝑓 + 1 messages from honest replicas, it follows from Line 15 that all honest replicas will enter round 𝑟 or a higher round by time 𝑡 ∗ + Δ. Analogous to Lemma 3, no honest replica can enter a higher round via 𝑁𝑉𝐶 before 𝑡 ∗ +𝜏. We proceed by considering an arbitrary honest replica 𝑝 𝑗 and discussing the following cases: If 𝑝 𝑗 has not entered a round higher than 𝑟 by time 𝑡 ∗ +𝜏, then by Property 2 and the preceding argument, it is guaranteed to receive at least 2𝑓 + 1 certificates from rounds ≥ 𝑟 (including 𝐿𝐶𝑟 ) by 𝑡 ∗ + 𝜏. Consequently, 𝑝 𝑗 will enter round 𝑟 + 1 and create a vertex referencing 𝐿𝐶𝑟 . If 𝑝 𝑗 enters round 𝑟 + 1 before 𝑡 ∗ + 𝜏, given the non-existence of 𝑁𝑉𝐶𝑟 , the vertex it creates for round 𝑟 + 1 must reference 𝐿𝐶𝑟 . If 𝑝 𝑗 enters a round higher than 𝑟 + 1 before 𝑡 ∗ + 𝜏 and skips round 𝑟 + 1, it must have invoked the send_fast_vote procedure covering round 𝑟 + 1. Since the first honest replica to enter round 𝑟 +2 possesses 𝐿𝐶𝑟 and has not sent ⟨no-vote, 𝑟 ⟩, 𝑝 𝑗 will receive 𝐿𝐶𝑟 within 𝜏 ′ = Δ and subsequently broadcast a fast-vote for it.

Feifan Wang, Jingfan Yu, Zixi Cai, and Zhixuan Fang

In summary, all honest replicas will cast a vote for 𝐿𝑉𝑟 (either via a first message or a fast-vote) by time 𝑡 ∗ + 𝜏. This guarantees that 𝐿𝑉𝑟 is directly committed by all honest replicas before 𝑡 ∗ + 𝜏 + Δ ≤ 𝑡 + 10Δ. □ Since CBC also satisfies the Integrity property, CBC-based Clownfish satisfies the Integrity property, and the proof is therefore omitted. Theorem 5. CBC-based Clownfish satisfies Integrity. Regarding the Total order property, based on the argument in Section B.2, all lemmas and their corresponding proofs from basic Clownfish can be directly applied to CBC-based Clownfish. Consequently, we directly obtain the following theorem: Theorem 6. CBC-based Clownfish satisfies Total order. By substituting the application of Lemma 2 with Lemma 7 in the proof of Lemma 6, we obtain the following lemma. Lemma 9. All honest replicas continuously enter higher rounds. By substituting the application of Lemma 6 with Lemma 9, and the application of Lemma 3 with Lemma 8 in the proof of Theorem 3, we establish the Validity property, and further obtain the Agreement property. Theorem 7. CBC-based Clownfish satisfies Validity. Theorem 8. CBC-based Clownfish satisfies Agreement.

C.3

Correctness Proof of Multi-leader Clownfish

For rounds 𝑟, 𝑟 ′ and indices 𝑥, 𝑥 ′ , we define the ordering (𝑟 ′, 𝑥 ′ ) ⪰ (𝑟, 𝑥) if and only if (𝑟 ′ = 𝑟 ∧ 𝑥 ′ ≥ 𝑥) ∨ (𝑟 ′ > 𝑟 ) is true. When we refer to a leader edge 𝑣 ∗ as being the “highest” within a specific set of leader edges, it implies that the tuple (𝑣 ∗ .𝑟𝑜𝑢𝑛𝑑, 𝑣 ∗ .𝑖𝑛𝑑𝑒𝑥) associated satisfies the aforementioned relation ⪰ with respect to the corresponding tuples of all other leader edges in the set. We say that a leader vertex MLV 𝑟 [𝑥] is directly committed by 𝑝𝑖 if 𝑝𝑖 invokes commit_leader(𝑟 ) and MLV 𝑟 [𝑥] is present in the corresponding CLS (Line 168). A leader vertex is indirectly committed if it is pushed onto the 𝑙𝑒𝑎𝑑𝑒𝑟𝑆𝑡𝑎𝑐𝑘 within CMV (Line 176). The argument for the Integrity property is identical to Theorem 1 and is therefore omitted. Theorem 9. Multi-leader Clownfish satisfies Integrity. Next, we establish the Total order property. The overall approach aligns with the proof for Clownfish. Lemma 10. If an honest replica 𝑝𝑖 directly commits a leader vertex MLV 𝑟 [𝑥], then for any valid main leader vertex 𝐿𝑉𝑟 ′ in round 𝑟 ′ > 𝑟 , there exists a leader path from 𝐿𝑉𝑟 ′ to MLV 𝑟 [𝑥]. Proof. Since 𝑝𝑖 directly commits MLV 𝑟 [𝑥], there must exist at least 2𝑓 + 1 votes for MLV 𝑟 [𝑥]. These votes comprise first messages from vertices in round 𝑟 + 1 with leader edges higher than (𝑟, 𝑥), as well as fast-votes. The latter exist only for 𝐿𝑉𝑟 . Among these, at least 𝑓 + 1 originate from honest replicas. Let H denote this set of honest replicas. According to Lines 121 and 155 of the protocol, the 𝑙𝑎𝑠𝑡𝐿𝑒𝑎𝑑𝑒𝑟 variable held by any replica in

H must satisfy (𝑙𝑎𝑠𝑡𝐿𝑒𝑎𝑑𝑒𝑟 .𝑟𝑜𝑢𝑛𝑑, 𝑙𝑎𝑠𝑡𝐿𝑒𝑎𝑑𝑒𝑟 .𝑖𝑛𝑑𝑒𝑥) ⪰ (𝑟, 𝑥). Furthermore, these replicas will not broadcast ⟨no-vote, ML𝑟 [𝑦], 𝑟 ⟩ for any 𝑦 ≤ 𝑥. Consequently, any leader edge 𝑙 of the vertices created by these replicas in subsequent rounds is guaranteed to satisfy (𝑙 .𝑟𝑜𝑢𝑛𝑑, 𝑙 .𝑖𝑛𝑑𝑒𝑥) ⪰ (𝑟, 𝑥). We now proceed by induction on 𝑟 ′ . Case 𝑟 ′ = 𝑟 + 1: Since |H | ≥ 𝑓 + 1, the property of quorum intersection guarantees that for any ℓ ∈ ML𝑟 [: 𝑥], an 𝑁𝑉𝐶𝑟ℓ cannot be formed. Therefore, if a valid leader vertex 𝐿𝑉𝑟 +1 exists, it must reference MLV 𝑟 [𝑥] via a strong edge. Case 𝑟 ′ ≥ 𝑟 + 2: We assume the inductive hypothesis holds for all leader vertices in rounds 𝑟 ′′ such that 𝑟 < 𝑟 ′′ < 𝑟 ′ . Since 𝐿𝑉𝑟 ′ references at least 2𝑓 + 1 vertices from round 𝑟 ′ − 1 via strong edges, quorum intersection implies that at least one of these referenced vertices originates from a replica in H . We denote one such replica as 𝑝𝑘 . Based on the property of set H derived earlier, the leader edge 𝑙 of the vertex created by 𝑝𝑘 in round 𝑟 ′ − 1 satisfies (𝑙 .𝑟𝑜𝑢𝑛𝑑, 𝑙 .𝑖𝑛𝑑𝑒𝑥) ⪰ (𝑟, 𝑥). If 𝐿𝑉𝑟 ′ references 𝐿𝑉𝑟 ′ −1 via strong edge (Lines 156–157), then by inductive hypothesis and transitivity, a leader path exists from 𝐿𝑉𝑟 ′ to MLV 𝑟 [𝑥]. If 𝐿𝑉𝑟 ′ does not reference 𝐿𝑉𝑟 ′ −1 (Lines 158–161), the highest leader edge 𝑣 ∗ of round 𝑟 ′ −1 vertices referenced by 𝐿𝑉𝑟 ′ must satisfy (𝑣 ∗ .𝑟𝑜𝑢𝑛𝑑, 𝑣 ∗ .𝑖𝑛𝑑𝑒𝑥) = (𝑟 ∗, 𝑥 ∗ ) ⪰ (𝑟, 𝑥) (since it is higher than or equal to 𝑝𝑘 ’s leader edge). If 𝑟 ∗ = 𝑟 , 𝐿𝑉𝑟 ′ must connect to MLV 𝑟 [𝑥] via 𝑎𝑢𝑥𝐸𝑑𝑔𝑒𝑠. If 𝑟 ∗ > 𝑟 , 𝐿𝑉𝑟 ′ must connect to 𝐿𝑉𝑟 ∗ via 𝑎𝑢𝑥𝐸𝑑𝑔𝑒𝑠. By the inductive hypothesis and transitivity, a leader path exists between 𝐿𝑉𝑟 ′ and MLV 𝑟 [𝑥]. □ By substituting the application of Lemma 1 with Lemma 10 in the proof of Lemma 4, and based on the pseudocode for commit_leaders, we directly obtain the following lemma: Lemma 11. If an honest replica 𝑝𝑖 directly commits main leader vertex 𝐿𝑉𝑟 , and an honest replica 𝑝 𝑗 directly commits main leader vertex 𝐿𝑉𝑟 ′ with 𝑟 ′ ≥ 𝑟 , then 𝑝 𝑗 either directly or indirectly commits 𝐿𝑉𝑟 . Lemma 12. If an honest replica 𝑝𝑖 directly commits leader vertices MLV 𝑟 [: 𝑥] (with 𝑥 > 0), and an honest replica 𝑝 𝑗 directly commits main leader vertex 𝐿𝑉𝑟 ′ with 𝑟 ′ > 𝑟 , then 𝑝 𝑗 either directly or indirectly commits leader vertices MLV 𝑟 [: 𝑥]. Proof. By Lemma 10, any main leader vertex in a round higher than 𝑟 has a leader path to MLV 𝑟 [: 𝑥]. Based on the pseudocode for commit_leaders, 𝑝 𝑗 will indirectly commit MLV 𝑟 [: 𝑥] if it has not yet directly committed any 𝐿𝑉𝑟 ′′ such that 𝑟 < 𝑟 ′′ < 𝑟 ′ . Otherwise, by an inductive argument, 𝑝 𝑗 has already committed MLV 𝑟 [: 𝑥] when directly committing 𝐿𝑉𝑟 ′′ . □ Lemma 13. If an honest replica 𝑝𝑖 consecutively directly commits the leader vertices in rounds 𝑟𝑖 and 𝑟𝑖′ , and an honest replica 𝑝 𝑗 consecutively directly commits the leader vertices in rounds 𝑟 𝑗 and 𝑟 ′𝑗 , then 𝑝𝑖 and 𝑝 𝑗 commit the same leader vertices between rounds max(𝑟𝑖 , 𝑟 𝑗 ) and min(𝑟𝑖′, 𝑟 ′𝑗 ) in the same order. Proof. Without loss of generality, we only need to consider the non-trivial case where 𝑟𝑖 ≤ 𝑟 𝑗 < 𝑟𝑖′ ≤ 𝑟 ′𝑗 . Suppose that 𝑝𝑖 directly commits MLV 𝑟𝑖′ [: 𝑥] in round 𝑟𝑖′ . If 𝑟 ′𝑗 = 𝑟𝑖′ , by Lemma 11, 𝑝 𝑗 commits at least 𝐿𝑉𝑟𝑖′ . Otherwise, by Lemma 12, 𝑝 𝑗 indirectly commits MLV 𝑟𝑖′ [: 𝑥]. Based on the pseudocode for commit_leaders

Clownfish : Scaling DAG-based BFT Consensus via Sparse Edges

and Lemma 10, the remainder of the proof is identical to that in Lemma 5. □

In summary, all honest replicas will cast a vote for 𝐿𝑉𝑟 by time 𝑡 + 𝜏 + Δ. This guarantees that 𝐿𝑉𝑟 is directly committed by all honest replicas before 𝑡 + 𝜏 + 2Δ. □

By substituting the application of Lemma 5 with Lemma 13 in the proof of Theorem 2, we obtain the Total order property:

Lemma 16. All honest replicas continuously enter higher rounds.

Theorem 10. Multi-leader Clownfish satisfies Total order. Next, we rely on following lemmas to establish the Validity property. Lemma 14. Let 𝑡 be a time after GST. If the first honest replica 𝑝𝑖 enters round 𝑟 at time 𝑡, then all honest replicas will enter round 𝑟 or higher by time 𝑡 + 2𝑘 2 Δ. Proof. We distinguish two cases based on whether the replica is the main leader. (i) Replicas other than 𝐿𝑟 . Following the same argumentation as in Lemma 2, all honest replicas are guaranteed to deliver 2𝑓 + 1 vertices from round 𝑟 − 1, including either 𝐿𝑉𝑟 −1 or 𝑁𝑉𝐶𝑟 −1 , within 𝑘 2 Δ. Consequently, all replicas other than 𝐿𝑟 will enter round 𝑟 (or higher) by time 𝑡 + 𝑘 2 Δ. (ii) The main leader 𝐿𝑟 . Based on the argumentation in Lemma 3, if there exists an honest replica that enters round 𝑟 ′ > 𝑟 before 𝑡 + 2𝑘 2 Δ < 𝑡 + 𝜏, it must have delivered 𝐿𝑉𝑟 . This implies that 𝐿𝑟 has already entered round 𝑟 by time 𝑡 + 2𝑘 2 Δ. Otherwise, by Case (i), any honest replica will send ⟨no-vote, ℓ, 𝑟 − 1⟩ to 𝐿𝑟 before 𝑡 + 𝑘 2 Δ for all ℓ ∈ ML𝑟 −1 if it has not delivered the corresponding leader vertex by that time. If no honest replica has delivered the vertex of ℓ in round 𝑟 − 1 by 𝑡 + 𝑘 2 Δ, 𝐿𝑟 will obtain 𝑁𝑉𝐶𝑟ℓ −1 by 𝑡 + (𝑘 2 + 1)Δ. Conversely, by Property 1, 𝐿𝑟 will deliver the vertex of ℓ by 𝑡 + 2𝑘 2 Δ. Therefore, for any ℓ ∈ ML𝑟 −1 , 𝐿𝑟 receives either the corresponding leader vertex or the 𝑁𝑉𝐶 by 𝑡 + 2𝑘 2 Δ. If 𝐿𝑟 has not delivered 𝐿𝑉𝑟 −1 by 𝑡 + 𝑘 2 Δ, let (𝑟 ∗, 𝑥 ∗ ) denote the round and index of the highest leader edge among the 2𝑓 + 1 vertices delivered by 𝑝𝑖 at time 𝑡. By the property of RBC, 𝐿𝑟 can deliver MLV 𝑟 ∗ [: 𝑥 ∗ ] by 𝑡 + 𝑘 2 Δ. In summary, 𝐿𝑟 can satisfy the conditions in Lines 156–161 by 𝑡 + 2𝑘 2 Δ and enter round 𝑟 (or higher). □ Lemma 15. If the first honest replica enters round 𝑟 at time 𝑡 after GST, and the timeout parameters are configured such that 𝜏 = (𝑘 1 + 2𝑘 2 )Δ and 𝜏 ′ = 𝑘 2 Δ, then 𝐿𝑉𝑟 is guaranteed to be directly committed before 𝑡 + 𝜏 + 2Δ provided that 𝐿𝑟 is honest. Proof. We present only the parts of the proof that differ from Lemma 3. First, we invoke Lemma 14 in place of Lemma 2. This ensures that all honest replicas enter round 𝑟 (or higher) by time 𝑡 + 2𝑘 2 Δ. Consider an honest replica 𝑝𝑖 . If 𝑝𝑖 ≠ 𝐿𝑟 +1 , the analysis remains identical to that in Lemma 3. If 𝑝𝑖 = 𝐿𝑟 +1 , we must modify the analysis for the scenario where 𝑝𝑖 has not entered a round higher than 𝑟 by time 𝑡 + 𝜏. In this scenario, given the absence of 𝐿𝑉𝑟 +1 and 𝑁𝑉𝐶𝑟 +1 , no honest replica will enter a round higher than 𝑟 + 1 prior to 𝑡 + 𝜏. Consequently, all honest replicas will enter round 𝑟 + 1 and send no-vote messages for round 𝑟 to 𝑝𝑖 (𝐿𝑟 +1 ) by time 𝑡 + 𝜏. Thus, 𝑝𝑖 receives these no-vote messages by 𝑡 + 𝜏 + Δ and enters round 𝑟 + 1 in accordance with Line 157. At this point, 𝑝𝑖 will create a vertex referencing 𝐿𝑉𝑟 .

Proof. We first follow the same reasoning as in Lemma 6, substituting the application of Lemma 2 with Lemma 14. At this point, all honest replicas except 𝐿𝑟 +1 can enter round 𝑟 + 1. By the finiteness of GST and Lemma 14, 𝐿𝑟 +1 will eventually enter round 𝑟 + 1 as well. □ By substituting the application of Lemma 6 with Lemma 16, and the application of Lemma 3 with Lemma 15 in the proof of Theorem 3, we establish the Validity property: Theorem 11. Multi-leader Clownfish satisfies Validity. By substituting the application of Lemma 1 with Lemma 10 in the proof of Theorem 4, we obtain the Agreement property: Theorem 12. Multi-leader Clownfish satisfies Agreement. Finally, we demonstrate through the following theorem that in the optimistic scenario where all replicas cast votes for a certain number of secondary leaders, these secondary leaders can also be directly committed. This suffices to fulfill the design objectives of the multi-leader protocol. Theorem 13. If the first honest replica enters round 𝑟 at time 𝑡 after GST and all leaders within ML𝑟 [: 𝑥] are honest, then in the optimistic scenario where all replicas vote for MLV 𝑟 [: 𝑥], the leader vertices in MLV 𝑟 [: 𝑥] are guaranteed to be directly committed before 𝑡 + 𝜏 + 2Δ. Proof. Obviously, no honest replica can enter a round higher than 𝑟 via 𝑁𝑉𝐶𝑟 prior to 𝑡 + 𝜏. By Lemma 14, all honest replicas will enter round 𝑟 (or higher) by time 𝑡 + 2𝑘 2 Δ. Consider an honest replica 𝑝𝑖 . If 𝑝𝑖 enters a round higher than 𝑟 + 1 before 𝑡 + 𝜏, then some honest replica must have delivered 2𝑓 + 1 vertices from round 𝑟 + 1. By the inductive hypothesis, the leader edges of these vertices must have a round of 𝑟 and an index of at least 𝑥. If 𝑝𝑖 enters round 𝑟 + 1 before 𝑡 + 𝜏, then, under the assumption, its vertex for round 𝑟 + 1 must provide a leader edge with round 𝑟 and index ≥ 𝑥. If 𝑝𝑖 does not enter a round higher than 𝑟 before 𝑡 + 𝜏, then according to the assumption, it is guaranteed to deliver 2𝑓 + 1 vertices from round 𝑟 (including MLV 𝑟 [: 𝑥]) by time 𝑡 + 𝜏. Combining this with the reasoning in Lemma 15, 𝑝𝑖 will enter round 𝑟 + 1 by 𝑡 + 𝜏 + Δ and create a vertex referencing MLV 𝑟 [𝑦] where 𝑦 ≥ 𝑥. In summary, all honest replicas will cast a vote for MLV 𝑟 [: 𝑥] (via either a first message or a fast-vote) by time 𝑡 + 𝜏 + Δ. This guarantees that MLV 𝑟 [: 𝑥] are directly committed by all honest replicas before 𝑡 + 𝜏 + 2Δ. □

C.4

Correctness Proof of CBC-based Multi-leader Clownfish

The Integrity property remains straightforward: Theorem 14. CBC-based Multi-leader Clownfish satisfies Integrity. Next, we proceed to prove the Total order property.

Feifan Wang, Jingfan Yu, Zixi Cai, and Zhixuan Fang

Lemma 17. If an honest replica 𝑝𝑖 directly commits a leader vertex MLV 𝑟 [𝑥], then for any valid main leader vertex 𝐿𝑉𝑟 ′ in round 𝑟 ′ > 𝑟 , there exists a leader path from 𝐿𝑉𝑟 ′ to MLV 𝑟 [𝑥]. Proof. Observe that the commit rules and the format of leader vertices in CBC-based Multi-leader Clownfish are basically identical to those in basic Multi-leader Clownfish. The sole distinction lies in the fact that references take the form of certificates, and the strong edges of a main leader vertex may reference certificates from rounds higher than the previous round. This distinction does not impact the quorum intersection argument and the conditions satisfied by the highest leader edge as presented in Lemma 10. Consequently, with the exception that describing the references of 𝐿𝑉𝑟 ′ requires considering 2𝑓 + 1 vertices from distinct replicas in rounds ≥ 𝑟 ′ − 1, the remainder of the logic is entirely consistent with Lemma 10. □ By applying Lemma 17 and following the same reasoning as in basic Multi-leader Clownfish, we directly establish the Total order property: Theorem 15. CBC-based Multi-leader Clownfish satisfies Total order. Next, we rely on following lemmas to establish the Validity property. The proof is notably more intricate, primarily due to the difficulties introduced by CBC’s weaker property. Lemma 18. Let 𝑡 be a time after GST. If the first honest replica 𝑝𝑖 enters round 𝑟 at time 𝑡, then all honest replicas will enter round 𝑟 or higher by time 𝑡 + 6Δ. Proof. We distinguish two cases based on whether the replica is the main leader. (i) Replicas other than 𝐿𝑟 . Following the same argumentation as in Lemma 7, 𝑝𝑖 is guaranteed to have received at least 2𝑓 + 1 certificates for rounds ≥ 𝑟 − 1, as well as either 𝐿𝐶𝑟 −1 or 𝑁𝑉𝐶𝑟 −1 . Among these, at least 𝑓 + 1 originate from honest replicas (let H denote this set). Within Δ, all honest replicas (with the exception of 𝐿𝑟 −1 ) will receive the first messages from H along with either 𝐿𝐶𝑟 −2 or 𝑁𝑉𝐶𝑟 −2 , subsequently entering round 𝑟 − 1 or higher. Since the first honest replica to enter round 𝑟 − 1 must have done so before time 𝑡 and sent a new-round message to 𝐿𝑟 −1 , 𝐿𝑟 −1 is also guaranteed to satisfy the conditions specified in Line 107 within Δ. We now demonstrate that 𝐿𝑟 −1 will satisfy the conditions stipulated in Line 109 or Line 113 by time 𝑡 + 2Δ, thereby entering round 𝑟 − 1 (or higher). Based on the preceding argument, at least 2𝑓 + 1 honest replicas will initiate the message transmission described in Lines 97–100 for rounds ≥ 𝑟 − 1 by time 𝑡 + Δ. Consider the values of 𝑙𝑎𝑠𝑡𝐿𝑒𝑎𝑑𝑒𝑟 held by each honest replica at the exact moment it initiates the ˆ 𝑥) ˆ denote the highest round and index among transmission. Let (𝑟, these values. Consider all vertices that can be referenced by 𝐿𝑉𝑟 −1 via strong edges by time 𝑡 + Δ. Let (𝑟 ∗, 𝑥 ∗ ) denote the round and index of the highest leader edge contained within these vertices (which may originate from a Byzantine replica). It suffices to consider the case where 𝑟 ∗ < 𝑟 − 1 and 𝑟ˆ < 𝑟 − 1, since otherwise 𝐿𝑟 −1 would have already completed the CBC or could advance to a higher round via 𝐿𝐶𝑟 ∗ or 𝐿𝐶𝑟ˆ (by Line 19). In this scenario, all honest replicas will send all no-vote messages and certificates for round 𝑟 − 2 to 𝐿𝑟 −1 before time 𝑡 + Δ, in accordance with Lines 97–100.

Consequently, for any ℓ ∈ ML𝑟 −2 , 𝐿𝑟 −1 is guaranteed to receive either the certificate or the 𝑁𝑉𝐶𝑟ℓ −2 . If 𝑟 ∗ = 𝑟 − 2, based on the preceding argument, 𝐿𝑟 −1 satisfies the condition in Line 109 by time 𝑡 + 2Δ. The same condition holds if 𝑟 ∗ < 𝑟 − 2 and 𝑟ˆ = 𝑟 − 210 . If 𝑟 ∗ < 𝑟 − 2 and 𝑟ˆ < 𝑟 − 2, we require ˆ 𝑥), ˆ 𝐿𝑟 −1 will collect all further case analysis. When (𝑟 ∗, 𝑥 ∗ ) ⪰ (𝑟, corresponding certificates or 𝑁𝑉𝐶s for ML𝑟 ∗ [: 𝑥 ∗ ] by time 𝑡 + 2Δ. Thus, 𝐿𝑟 −1 satisfies the condition in Line 113 by 𝑡 + 2Δ. When ˆ 𝑥) ˆ ⪰ (𝑟 ∗, 𝑥 ∗ ), 𝐿𝑟 −1 will collect all certificates for ML𝑟ˆ [: 𝑥] ˆ by (𝑟, time 𝑡 + 2Δ, thereby satisfying the condition in Line 113. In summary, all honest replicas will initiate the CBC for rounds ≥ 𝑟 −1 by 𝑡 +2Δ and complete it by 𝑡 +5Δ. Consequently, all replicas other than 𝐿𝑟 will enter round 𝑟 (or higher) by time 𝑡 + 5Δ. (ii) The main leader 𝐿𝑟 . The new-round message sent by 𝑝𝑖 to 𝐿𝑟 is guaranteed to arrive by time 𝑡 +Δ. According to Case (i), all honest replicas will send all relevant no-vote messages or certificates to 𝐿𝑟 by time 𝑡 + 5Δ. Similar to the reasoning presented regarding 𝐿𝑟 −1 , 𝐿𝑟 will satisfy the conditions in Line 109 or Line 113 and enter round 𝑟 (or higher) by time 𝑡 + 6Δ. □ Lemma 19. If the first honest replica enters round 𝑟 at time 𝑡 after GST, and the timeout parameters are configured such that 𝜏 = 5Δ and 𝜏 ′ = Δ, then 𝐿𝑉𝑟 is guaranteed to be directly committed before 𝑡 + 14Δ provided that 𝐿𝑟 is honest. Proof. We present only the parts of the proof that differ from Lemma 8. First, we invoke Lemma 18 in place of Lemma 7. Based on the same argumentation as in Lemma 8, the first honest replica 𝑝𝑖 is guaranteed to initiate the timer for round 𝑟 by time 𝑡 ∗ ≤ 𝑡 + 7Δ. Since the set of 2𝑓 + 1 first messages received by 𝑝𝑖 for round ≥ 𝑟 must contain at least 𝑓 + 1 messages from honest replicas, in accordance with the round-skipping rule, all honest replicas other than 𝐿𝑟 will enter round 𝑟 (or a higher round) by time 𝑡 ∗ + Δ. If any of these replicas enters a round higher than 𝑟 , then, given that 𝑁𝑉𝐶𝑟 cannot exist prior to 𝑡 ∗ + 𝜏, 𝐿𝑟 must have already completed the CBC for round 𝑟 . Otherwise, 𝐿𝑟 will receive sufficient no-vote messages and certificates by time 𝑡 ∗ + 2Δ, subsequently entering round 𝑟 . The subsequent reasoning remains consistent with Lemma 15, with the exception that 𝑡 is substituted by 𝑡 ∗ . In summary, all honest replicas will cast a vote for 𝐿𝑉𝑟 (via either a first message or a fast-vote) by time 𝑡 ∗ +𝜏 +Δ. This guarantees that 𝐿𝑉𝑟 is directly committed by all honest replicas before 𝑡 ∗ + 𝜏 + 2Δ ≤ 𝑡 + 14Δ. □ By substituting the application of Lemma 18 with Lemma 14 in the proof of Lemma 16, we obtain the following lemma. Lemma 20. All honest replicas continuously enter higher rounds. By substituting the application of Lemma 6 with Lemma 20, and the application of Lemma 3 with Lemma 19 in the proof of Theorem 3, we establish the Validity property: 10 In fact, when 𝑟ˆ > 𝑟 ∗ , the set of vertices referenced by strong edges might not include

the honest replica holding the highest 𝑙𝑎𝑠𝑡𝐿𝑒𝑎𝑑𝑒𝑟 . However, we emphasize that by referencing certificates for the higher M L𝑟ˆ [: 𝑥ˆ ] , 𝐿𝑟 −1 satisfies a condition strictly stronger than that in Line 113. This is because 𝐿𝑉𝑟ˆ is sufficient to provide the safety guarantee for establishing a leader path to the leader vertex in round 𝑟 ∗ . We omitted this scenario—where certificates from a round higher than the highest leader edge are provided—from the pseudocode to maintain clarity.

Clownfish : Scaling DAG-based BFT Consensus via Sparse Edges

Theorem 16. CBC-based Multi-leader Clownfish satisfies Validity. By substituting the application of Lemma 1 with Lemma 17 in the proof of Theorem 4, we obtain the Agreement property: Theorem 17. CBC-based Multi-leader Clownfish satisfies Agreement. The final theorem corresponds to the optimistic scenario described in Theorem 13. Under the given assumptions, certificates from honest leaders are guaranteed to be received by all honest

replicas within Δ. As the modifications to the remainder of the proof relative to Lemma 19 are analogous to those in the RBC case, we omit the proof. Theorem 18. If the first honest replica enters round 𝑟 at time 𝑡 after GST and all leaders within ML𝑟 [: 𝑥] are honest, then in the optimistic scenario where all replicas vote for MLV 𝑟 [: 𝑥], the leader vertices in MLV 𝑟 [: 𝑥] are guaranteed to be directly committed before 𝑡 + 14Δ.