MANTA: Unlocking DAG Flexibility in Asynchronous BFT

M ANTA: Unlocking DAG Flexibility in Asynchronous BFT

DAG-based BFT protocols marked a shift in consensus design by replacing single-leader proposal paths with concurrent block proposals linked through a shared graph, where references encode consensus evidence. However, under heterogeneous wide-area networks (WANs), existing designs suffer from prolonged rounds and degraded performance due to straggler effects. The root cause is rigid round advancement: replicas move in synchronized rounds, waiting for enough references from the previous round before advancing. We propose a flexible DAG growth framework for asynchronous BFT consensus. Our key observation is that while reference quorums are necessary for safety and liveness, they need not block every round advancement. Instead, the connectivity required for commitment can be accumulated across rounds. Within the framework, we instantiate M ANTA, which combines flexible DAG growth to advance by relaxing round synchronization and flexible coin to trigger leader election and finality earlier. Experiments on heterogeneous WAN deployments show that M ANTA reduces latency by approximately 30%–70% in our evaluation.

1

Low heterogeneity High heterogeneity

3 2 1

20

40 60 Throughput (KTps)

(a) Latency and TPS.

80

Collected vertices (%)

4

Abstract Latency (s)

arXiv:2610.34419v1 [cs.DC] 25 Oct 2026

Mohan Yu1,† , Chenlin Wu2,† , Jianyu Niu2,‡ , Cong Wang2 , Chenyuan Wu2 1 Southern University of Science and Technology 2 City University of Hong Kong

100 80

Prolonged round

60 40 Low heterogeneity High heterogeneity

20 0

200

250 300 Time (ms)

350

(b) Prolonged round.

Figure 1: Performance degradation in heterogeneous WANs.

Recent DAG-based protocols have made asynchronous consensus practical at high throughput by alleviating the bottlenecks of earlier designs [7, 11]. Examples such as DAGRider [10] and Tusk [12] organize protocol execution as a Directed Acyclic Graph (DAG), where replicas continuously propose blocks, referred to as vertices. Each vertex carries transaction payloads and typically references a quorum of at least 2 f + 1 previously delivered vertices, forming directed edges that connect vertices. This minimum number of references, called the reference threshold, governs round advancement and the connectivity of the growing DAG. Consensus is derived from the graph structure: once sufficient connectivity emerges, randomized leader election (e.g., common coin), combined with local DAG observations, derives a final total order and commits the causal history of selected leaders. Yet the performance of existing DAG protocols still degrades sharply in heterogeneous WAN deployments, where cross-region links vary widely, transient slowdowns are common, and replicas often differ in bandwidth and responsiveness [13]. A few lagging replicas can slow system-wide progress, increasing commit latency and reducing throughput. Fig. 1 shows that under such heterogeneity, latency increases by around 40%, throughput drops accordingly, and round duration grows by more than 25%. The root cause is a hidden synchronization barrier in round advancement: replicas must gather a quorum of references before moving to the next round [10, 12, 14, 15]. This rule strengthens graph connectivity and increases the likelihood

Introduction

Byzantine Fault-Tolerant (BFT) consensus underpins modern distributed systems, particularly geo-distributed services such as shared databases [1], distributed storage [2], and blockchains [3, 4]. It enables mutually untrusted nodes to agree on a common sequence of transactions despite Byzantine failures [5, 6]. In such geo-distributed settings, asynchronous BFT protocols [7–11] have emerged as an attractive choice, as they guarantee liveness without timing assumptions and remain robust under variable message delays, transient congestion, and WAN dynamics [11]. † These authors contributed equally. ‡ Part of the work was done when Jianyu Niu visited the Research Institute

of Trustworthy Autonomous Systems of SUSTech.

1

that elected leaders can commit even under adversarial schedules. Yet it also serializes progress: proposals are parallelized, but rounds still wait for stragglers. Simply lowering the synchronization barrier is not enough. Reducing the reference threshold below 2 f + 1 may shorten rounds, but in asynchronous adversarial settings, an adversary can selectively delay blocks, causing honest replicas to observe inconsistent structures and fail to guarantee liveness [10]. More fundamentally, existing designs conflate two distinct goals: using the same per-round barrier both to establish connectivity and to regulate progress. This raises a key question: if strong connectivity is needed for safe commitment, must every round wait for it before making progress? Our answer is no. The synchronization barrier should serve as a condition for safety and liveness, not a blocking condition for round advancement. A high barrier preserves the connectivity required for stable commits, but enforcing it in every round is unnecessarily restrictive. In heterogeneous WANs, repeatedly waiting for slow previous-round vertices inflates latency and allows a few stragglers to dictate system progress. Guided by this insight, we develop a flexible DAG growth framework for asynchronous BFT consensus. The framework makes explicit a fundamental tradeoff in DAG protocols: lowering the per-round barrier speeds up progress, yet can weaken the connectivity needed for commitment under adversarial schedules. It characterizes how reference threshold and connectivity accumulation affect commit latency, and derives liveness bounds that explain when aggressive designs with low threshold can fail. Building on this analysis, the framework introduces a coverage-based abstraction that decouples how much connectivity is required from how it is formed. Concretely, it provides boost edges that allow connectivity to accumulate across rounds, rather than being rebuilt in each round. Finally, the framework defines a four-dimensional parameter space that abstracts the generic DAG growth process, enabling systematic analysis of existing protocols and the discovery of new ones. Within the framework, we instantiate M ANTA, a concrete asynchronous DAG-based protocol that converts alreadyformed connectivity into faster progress and earlier commits. M ANTA is enabled by two complementary design elements: flexible growth and flexible coin. Flexible growth allows replicas to advance with lower reference thresholds while preserving worst-case liveness through cross-round coverage. Flexible coin then exploits locally emerged connectivity to trigger the common coin as soon as commitment becomes likely, enabling earlier leader election and finalization instead of waiting for fixed wave boundaries. If early commitment is unavailable, execution safely falls back to the normal path without affecting correctness or performance. We built a prototype of M ANTA and evaluated it against four state-of-the-art asynchronous counterparts: Tusk [12], Chitu [15], Mahi-Mahi [14], and DAG-Rider [10]. We conducted experiments under diverse conditions on Cloud-

Lab [16] and AWS platforms with up to 50 replicas. Results show that M ANTA consistently outperforms other baselines under fault-free heterogeneous deployments. Contributions. This paper makes four contributions: • We identify a fundamental limitation of existing asynchronous DAG-based protocols: rigid per-round synchronization barriers unnecessarily gate progress and inflate commit latency under heterogeneous WANs. • We develop a unified framework for asynchronous DAG growth that formalizes the tradeoff between fast progress and sufficient connectivity for commitment, and explains the liveness limits of aggressive low-threshold designs. • We design M ANTA, a novel asynchronous DAG-based BFT protocol that decouples connectivity from round advancement. Through flexible growth and flexible coin, M ANTA achieves faster progress and earlier commitment while preserving worst-case safety and liveness. • We implement M ANTA and evaluate it against state-of-theart protocols under realistic heterogeneous WANs. M ANTA reduces latency by up to 70%, improves throughput by up to 18% at scale, and remains performant under faults.

2

Background and Motivation

2.1

DAG-Based BFT Consensus

DAG-based BFT protocols proceed in rounds, where consecutive rounds are grouped into waves. In each round, every replica proposes a block, referred to as a vertex. Each vertex references at least 2 f + 1 vertices from the previous round via directed edges (often called strong edges), resulting in a growing directed acyclic graph (DAG). Vertices are disseminated using reliable broadcast (RBC) [17], ensuring that all honest replicas eventually obtain a consistent view of the DAG (details in Appendix A). As references accumulate, later-round vertices gain multi-hop reachability to earlier vertices, increasing the shared visibility needed for common core formation [18]. If a subset of vertices from some round becomes reachable in the local DAGs of all honest replicas, these vertices form the common core of that wave, meaning they are sufficiently observed for subsequent commitment logic (formalized in Sec. 4.1). At the end of each wave, replicas invoke a common coin [19, 20] to elect a leader vertex from the first round of the wave. If the elected leader belongs to the common core, it commits its causal history, i.e., all vertices reachable from it, according to a deterministic rule. Existing DAG-based BFT protocols can be broadly categorized into two architectures: coupled and decoupled. In coupled designs, DAG vertices carry both transaction payloads and ordering information, so DAG growth directly determines transaction latency. In decoupled designs, data dissemination 2

is separated from consensus, and vertices mainly carry metadata or certificates. Representative examples include DAGRider [10] and Chitu [15] for coupled designs, and Tusk [12] and Autobahn [21] for decoupled designs. In this paper, we primarily focus on the coupled architecture by following prior asynchronous BFT protocols [10, 15], while noting that our framework and evaluation also extend to decoupled settings.

2.2

Existing protocols, however, enforce rigid quorum requirements within each round, forcing replicas to wait for all required vertices before proceeding. Under heterogeneous networks, many vertices often arrive early and already provide substantial partial connectivity before a wave fully completes. Since safety and liveness ultimately depend on whether enough vertices become sufficiently observed to form the common core, rather than on the exact timing of round completion, there is room to relax rigid round synchronization. Allowing connectivity to continue accumulating across rounds enables replicas to make progress earlier while preserving the guarantees required for safety and liveness.

Dissecting DAG-Based BFT Performance

Heterogeneity in WAN deployments. Modern distributed systems like blockchains are typically deployed in wide-area networks, where replicas operate under highly heterogeneous conditions. Differences in networking (e.g., bandwidth), computation (e.g., CPU), and storage capabilities lead to uneven processing and dissemination speeds across replicas. In addition, client requests are often highly skewed [22, 23], leading to substantial load imbalance across replicas [24–27]. These effects are further amplified by heterogeneous network environments, where replicas are geographically distributed but unevenly placed, forming dense clusters alongside sparsely connected peripheral nodes [28,29]. This results in highly variable network paths and message delays across replicas, as also observed in production blockchain systems such as Aptos [30], Solana [31], and Sui [32].

• Commit rules should adapt to flexible connectivity. Relaxing round-based progression changes the structure of the DAG, as vertices are no longer aligned within strict rounds. As a result, commit rules that rely on consecutive-round connectivity become overly restrictive. To fully exploit flexible connectivity, commit conditions must be adapted to account for connectivity formed across rounds. Guided by these two observations, Sec. 4 develops a flexible DAG growth framework that theoretically characterizes and quantifies how rigid round-boundary constraints limit connectivity accumulation. Sec. 5 then presents M ANTA, a concrete protocol instantiation that exploits the resulting DAG flexibility to accelerate commitment.

Rigid round progression constraint. Existing DAG-based BFT protocols couple round advancement with quorum collection: to enter round r, a replica must first gather at least 2 f + 1 vertices from round r−1 (see Sec. 2.1). While this rule helps preserve connectivity and common-core formation, it also creates a per-round synchronization barrier. Under heterogeneous WANs, progress is dictated by the slowest quorum vertices rather than the fastest available ones. As a result, fast replicas remain idle with their resources underutilized, and prolonged rounds delay transaction admission and increase commit latency. Fig. 1 compares DAG-based protocols under low- and highheterogeneity WAN deployments with the same average RTT (80 ms) and total input workload (20K–120K tx/s). In the former, all replica pairs have the same RTT and workloads are evenly distributed. In the latter, replicas are distributed across three continents and workloads are unevenly assigned, resulting in heterogeneous network delays and workload distribution. Under heterogeneity, delayed cross-region arrivals prolong round duration by over 25%, with commit latency around 40% higher.

3

System Model

We consider a set of n = 3 f + 1 replicas, denoted by Π = {p1 , p2 , ..., pn }. Among them, up to f replicas may be Byzantine, behaving arbitrarily under the control of a computationally bounded adversary, while the remainder are honest and faithfully follow the protocol. We assume replicas communicate over authenticated, reliable channels as in prior BFT works [11]: messages sent by correct replicas are eventually delivered to all correct receivers without forgery. We assume a public key infrastructure (PKI) for identity verification. We assume a fully asynchronous network model as prior works [7, 10], where message delays are unbounded, and delivery order is arbitrary. In particular, message delays may vary significantly across replicas, capturing heterogeneous network conditions in practice. We also assume standard reliable broadcast (RBC) primitives [17] that ensure agreement, integrity, and validity properties [33], and a shared random coin [19, 20] (e.g., instantiated via threshold signatures) to support randomized coordination under asynchrony.

Key observations. The above bottleneck stems from the coupling of round advancement with quorum collection. Breaking it reveals new opportunities for improving performance under heterogeneous conditions due to two key observations:

We focus on state machine replication (SMR) [34], where replicas agree on a total order of transactions. The protocol should satisfy two properties: (i) Safety: no two correct replicas commit different transactions at the same position in the total order; and (ii) Liveness: every transaction issued by a correct client is eventually committed by honest replicas.

• Connectivity should not be constrained by round boundaries. As discussed in Sec. 2.1, references accumulated over time progressively increase reachability to earlier vertices. 3

4

Flexible DAG Growth Framework

Case A Common core exists

To unlock flexible DAG growth, we present a unified analytical framework that formalizes the key design trade-offs: while lowering the per-round synchronization barrier can shorten round duration, it also weakens connectivity and thus affects the chance of successful commitment. To this end, we first model commit probability and latency that are jointly determined by protocol design parameters and network conditions (Sec. 4.1), and then analyze worst-case protocol behaviors (Sec. 4.2), showing that DAG structures that perform well in practice may fail to guarantee liveness under adversarial settings. These insights not only reveal the limitations of existing DAG protocols, but also guide the design of more flexible and robust DAG frameworks (Sec. 4.3).

4.1

𝑣11

Case B No common core

𝑣13

𝑣11

𝑣21

𝑣21

𝑣31

𝑣31

𝑣41

𝑣41

vertex in common core

𝑣13

vertex outside common core

Figure 2: Common core example for k = 3 rounds in a wave with 4 replicas ( f = 1). A first-round vertex is observed if there exists a path from a third-round vertex to it. Hence, v31 observes v12 via the dashed path. Left: With re f = 2 f + 1, vertices v12 , v13 , and v14 are observed by all honest replicas and thus form the common core, whereas v11 is observed by only one replica and lies outside the common core. Right: With re f = f + 1, no first-round vertex is observed by all honest replicas, resulting in an empty common core.

Modeling DAG Performance

To analyze the commit latency of DAG-based BFT protocols, we begin by examining how vertices propagate and become visible across replicas.

is guaranteed to be committable. Thus, the commit probability is given by Φ(re f , k) P≥ . n

Common core (S). In DAG-based protocols, the leader vertex can be committed only if it is sufficiently well disseminated so that all honest replicas observe it. Specifically, consider a replica p proposing a vertex v in round r. We say that p observes a vertex u in round r′ (where r′ < r) if there exists a path from v to u. Furthermore, we have a key abstraction for reasoning about commit decisions.

Wave duration (W ). A replica advances after collecting re f references from the previous round. Let {d1 , . . . , dn } denote the propagation delays of vertices from different replicas. The time required to complete a round is determined by the arrival of the re f -th fastest vertex, i.e., the re f -th order statistic D = d(re f ) . Over a wave of k rounds, the total time spent in accumulating connectivity is denoted as W (re f , k).

Definition 1 (Common core [18]). Let Vi denote the set of the first-round vertices that are observed by replica pi after a wave. A set S is called a common core if S ⊆ Vi for every honest replica pi .

Latency (L). Since a successful commit occurs with probability P, the latency estimate until commitment is

Example. Consider a wave where each replica observes a slightly different subset of vertices due to heterogeneous delays. A common core is a set of vertices observed by all honest replicas. Fig. 2 shows how different reference thresholds can change this shared visible set. For a vertex in the common core, its commit status can therefore be evaluated consistently across replicas. In contrast, a vertex outside the common core is not guaranteed to be observed by some honest replica at the decision point. We next identify two key protocol parameters that govern how connectivity forms. The reference threshold re f determines how many vertices must be collected before a replica advances to the next round, while the wave length k determines how long connectivity is allowed to accumulate before a commit decision is made. We use Φ(re f , k) to characterize the effective visible set size by the end of round k under reference threshold re f ; together with Byzantine behavior, it characterizes the size of S (see Appendix B.1).

L≈ 4.1.1

W (re f , k) . P

Optimistic Analysis under Heterogeneity

Using the above formulation, we next analyze the performance of DAG-based BFT protocols under benign conditions without adversarial interference. We model d as a log-normal random variable to capture different levels of heterogeneity and then derive the theoretical latency. Due to space constraints, detailed proof is provided in Appendix B.1. Fig. 3 shows the theoretical commit probability and latency under different choices of re f and k. We instantiate the distribution of d using representative network-delay distributions with mean/std of 50/5 ms and 100/50 ms for the favorable and unfavorable settings, respectively. The results reveal a clear trade-off between round latency and connectivity accumulation. When heterogeneity is high, long-tail delays from slow replicas make large re f prohibitively expensive. Although

Commit probability (P). With the leader selected uniformly at random from the first round, any leader in the common core 4

2.5

0.8

2.0

Latency (s)

Commit Probability P

1.0

0.6 0.4 k = 2 (Low) k = 2 (High)

0.2 0.0 1

3

5

7

9

k = 3 (Low) k = 3 (High)

11

Reference ref

13

k = 2 (Low) k = 2 (High)

Case A

k = 3 (Low) k = 3 (High)

Case B

1.5 High Heterogeneity Optimal: Small ref

1.0

Low Heterogeneity Optimal: Large ref

0.5

15

(a) Commit probability.

2

4

6

8

10

Reference ref

12

14

16

coin flipping

(b) Latency. 𝑟𝑟𝑟𝑟𝑟𝑟 = 𝑓𝑓 + 1

Figure 3: DAG performance under different re f and k.

coin flipping 𝑟𝑟𝑟𝑟𝑟𝑟 = 2𝑓𝑓 + 1

Figure 4: A worst-case two-round example with f = 2. increasing re f improves commit probability, this gain is insufficient to offset the increased round duration. In contrast, a smaller re f allows replicas to advance earlier, and the saved time can be used to accumulate connectivity across additional rounds. As a result, connectivity can emerge through temporal accumulation rather than strict per-round synchronization, leading to lower latency. In summary, we observe distinct optimal configurations under different levels of heterogeneity: • Low heterogeneity. A larger re f with a smaller k minimizes latency by maximizing per-round connectivity.

Worst-case liveness guarantees. To formalize these limitations, we analyze the worst-case behavior of DAG-based BFT protocols. Let R1 , . . . , Rk denote the sets of vertices generated in each round of a wave. For a fixed decision round Rk , the key question is which vertices in R1 remain committable under any admissible adversarial DAG topology, since these vertices determine the protocol’s worst-case liveness guarantee. Since short-wave DAG protocols, e.g., those that check commitment after two rounds, may not form a common core even when some first-round vertices remain committable [35], we characterize liveness directly through these committable vertices. We therefore generalize the notion of common core and let Gk ⊆ R1 denote the set of first-round vertices that are guaranteed to satisfy the commit rule (with threshold f + 1) in the worst case, and let Uk = R1 \ Gk denote the remaining vertices, whose committability is topology-dependent and thus not guaranteed in the worst case.

• High heterogeneity. A smaller re f combined with a larger k achieves better performance by leveraging cross-round accumulation.

4.2

Liveness Constraints

The above optimistic analysis may motivate adopting aggressive configurations such as re f = f + 1 to minimize protocol latency across heterogeneous networks. However, such configurations cannot be directly applied as explained below. The following analysis examines the liveness issue behind these configurations and motivates the solid vertex mechanism introduced in Sec. 4.3.

Theorem 1 (Worst-case common-core bound). Consider a DAG-based BFT protocol with n = 3 f + 1 replicas, wave length k, and reference threshold re f . Under adversarial scheduling, the size of Gk is lower-bounded as summarized in Table 1. In particular: (i) when re f = f + 1, we have |Gk | = 0 for f > 1; and (ii) when re f ≥ n − f , the Gk remains non-empty, with the guaranteed size increasing with k.

Why optimistic configurations fail. The limitation arises because reducing re f may leave insufficient connectivity under adversarial timing. The right side of Fig. 2 (Case B) shows a case in asynchronous networks where an adversary can delay message delivery such that no first-round vertex is observed by all honest replicas within a fixed wave length. In this case, the honest replicas share no common visible first-round vertex, so the common core is empty. As a result, no vertex is guaranteed to be committed, and progress depends on DAG topology and message timing, preventing convergence and threatening liveness. The liveness issue is exacerbated in practical two-round designs. As illustrated in Case A of Fig. 4, when re f = f + 1, an adversary can prevent every first-round vertex from receiving at least f + 1 supporting edges, which is the weakest possible commit condition. Hence, the wave contains no committable vertex, and liveness fails. In contrast, in Case B with re f = 2 f + 1, some first-round vertices satisfy the commit rule, preserving liveness.

Proof Sketch. The proof partitions the first-round vertices into the guaranteed set Gk and the uncertain set Uk . It then lowerbounds |Gk | by counting the support to R1 that is unavoidable under adversarial scheduling. It first identifies when a vertex in R1 must enter Gk : for k = 2, we first maximize the references that can be absorbed while keeping all R1 vertices outside G2 . The remaining references must force some vertices into G2 , yielding the lower bound on |G2 |. For k = 3, a vertex enters G3 once it has at least n − re f + 1 supporters in R2 , ensuring that any choice of re f parents in R3 includes at least one such supporter. We then maximize the references that can be absorbed while keeping vertices outside G3 ; any remaining references must force some vertices into G3 , yielding the stated bounds. The full proof is deferred to Appendix B.3. Theorem 1 shows that naively reducing re f to improve latency fundamentally compromises liveness. For example, if 5

Case A

Table 1: Common Core Size. re f k 2 3 4

≥ n− f f +1 1.5 f 2f +1

≥ 1.8 f + 1 1 f +1 1.8 f + 1

≥ 1.5 f + 1 – 1 1.5 f + 1

𝑣𝑣11

≥ f +1 – – –

𝑣𝑣11

𝑣𝑣21

𝑣𝑣21

𝑣𝑣31

𝑣𝑣31

𝑣𝑣13

Figure 5: Redundant connectivity in DAG structures. Different reference patterns yield the same commit probability P when the guaranteed set Gk is identical. Dashed lines in Cases A and B illustrate example reference patterns to the same round-1 vertices.

a protocol aims to use a two-round wave, i.e., to start commitment checking at the end of round 2, the reference threshold must remain above the corresponding worst-case bound to ensure that at least one first-round vertex satisfies the commit condition. More generally, if a protocol aims for stronger worst-case liveness, so that more honest replicas can make progress concurrently, it needs a larger common core, which in turn requires a larger re f and k according to Table 1.

4.3

Case B 𝑣𝑣13

the commit probability. Therefore, the advancement conditions can be safely adjusted through the following mechanism. Definition 2 (Solid Vertex). For a target round rcov , let I(v, rcov ) denote the set of target-round vertices visible to v through its parents, and let B(v, rcov ) denote the additional target-round vertices reached via boost edges. A vertex v is solid with respect to round rcov if

From Rigidity to Flexibility

The worst-case analysis above suggests that liveness fundamentally depends on whether sufficient connectivity is formed to preserve a non-empty Gk , rather than on how such connectivity is physically constructed. In other words, different reference patterns could induce the same effective connectivity, and thus yield identical commit probability and liveness guarantees. For example, Fig. 5 shows two different reference patterns (the dashed lines in Cases A and B) with the same guaranteed set Gk = {v11 , v12 , v13 }, whose vertices satisfy the commit rule, and thus the same commit probability P. Inspired by this observation, we seek to preserve the connectivity required for a non-empty Gk without enforcing a fixed reference pattern. To this end, we introduce a more general notion of coverage for DAG, denoted as cov, which represents the number of vertices in a target round that are reachable from a given future vertex, regardless of the specific reference paths. Under this abstraction, the protocol no longer needs to enforce a monolithic reference rule (e.g., every vertex references 2 f + 1 in the previous round); instead, connectivity can be flexibly constructed as long as the required coverage is achieved. Specifically, consider a vertex v in round rcur , and its goal is to reference at least cov vertices in round rcov (where rcov ≤ rcur − 1). To achieve this, v establishes two types of edges:

|I(v, rcov ) ∪ B(v, rcov )| ≥ cov. Rather than constraining the DAG to specific reference patterns, we could guarantee liveness by verifying whether vertices are solid, shifting the focus to coverage (cov): the total number of vertices in a target round rcov reached by a vertex in the current round. To illustrate, consider k = 2 and re f = 2 f + 1 in Table 1, where at least f + 1 vertices in the first round are guaranteed to satisfy the commit rule. After introducing cov, preserving this guarantee only requires preserving the same effective support to the target round. Therefore, setting cov = re f = 2 f + 1 is sufficient: even if the support is realized through different topologies, the resulting worst-case liveness bound remains unchanged. Fig. 6 shows that this support can indeed be achieved through multiple topology patterns: • Case A: Round 2 vertices establish re f = 2 f + 1 progress edges to round 1. Consequently, round 3 vertices only require a minimum re f = 1 to round 2 to satisfy the cov requirement for round 1.

Progress edges. They reference vertices in the previous round (rcur − 1). These edges allow v to inherit references to rcov from its parents.

• Case B: Round 2 vertices maintain a minimal re f = 1 to round 1. Round 3 vertices must utilize progress and boost edges to collectively reference at least cov vertices from round 1.

Boost edges. They reference vertices in any historical round r′ < rcur − 1 within the same wave, increasing coverage over the target round when the inherited view from parent vertices is insufficient (e.g., directly referencing vertices in rcov that are not covered by the parents). Boost edges facilitate cross-round integration to improve

• Case C: Round 2 vertices provide partial coverage with re f = f + 1. Round 3 vertices then supplement this by referencing additional vertices via progress or boost edges until the cov requirement for round 1 is fully met. Although the three cases utilize different edge compositions, they all render the vertices in round 3 solid. Therefore, 6

Case A

1

Case B

2

3

1

Solid Vertex

2

round

𝑓𝑓 + 1

3

Progress Edge

1

𝑓𝑓 + 1

2

solid step

3

1

Boost Edge

3

4

solid step

5

round

6

solid step

7

solid vertex w.r.t round 3/round 7

8

9

elected leader

Figure 7: The wave structure in M ANTA. A wave consists of κ = 2 solid steps, each spanning σ = 2 rounds.

3

of Ω correspond to5 different levels of liveness guarantees. Specifically, to optimize for latency under heterogeneous settings, we instantiate M ANTA by setting cov = 2 f + 1, σ = 2, and κ = 2, as shown in Fig. 7. Thus, a wave spans five rounds and contains two solid steps. Every honest replica must propose at least one solid vertex per step. The parameters cov and κ are chosen to ensure worst-case liveness, as characterized in Table 1. We set σ = 2 to support flexible DAG growth and choose re f = f + 1, which is identified by the analysis in Sec. 4.1 as the favorable design point for high heterogeneity environments. Moreover, it leaves room for the flexible coin design without making every round trivially solid.

they all guarantee the same worst-case liveness outcome: by round 3, at least f + 1 vertices in round 1 satisfy the commit rule. In this way, the protocol can preserve liveness when the direct reference threshold re f is reduced in some rounds for faster round progression, effectively decoupling the required reference pattern from the physical DAG construction.

M ANTA Design

We present M ANTA, a DAG-based BFT protocol instantiated from the previous framework with flexible DAG growth to reduce latency while preserving liveness. We first establish a unified parameter space for DAG design and use it to instantiate M ANTA (Sec. 5.1), then present the detailed protocol specification (Sec. 5.2), provide the correctness analysis (Sec. 5.3), and map existing DAG protocols to the design space behind M ANTA (Sec. 5.4).

5.1

2

solid step

solid vertex w.r.t round 1/round 5

Figure 6: Multiple edge configurations achieving equivalent cov thresholds. For a fixed wave length k, different reference patterns can satisfy the same coverage requirement.

5

wave

wave

Case C

2𝑓𝑓 + 1

1

1

2𝑓𝑓 + 1

5.2

Protocol in Detail

Algorithm 1 shows the core utilities of M ANTA, which leverages the flexible parameter space Ω to optimize performance in heterogeneous networks. ❶Vertex construction. Each vertex carries a batch of transactions together with references to earlier vertices, which are interpreted as progress or boost edges. To advance to the next round, a replica must propose a vertex that either references at least re f vertices from the immediately preceding round or constitutes a solid vertex for the current step (Lines 3-9). ❷ DAG construction. As in prior DAG-based BFT protocols, vertices are disseminated via reliable broadcast. Replicas accept at most one vertex from each sender in a given round, vote for a valid proposal, and certify a vertex after collecting n − f votes. Once certified, the vertex may be referenced by subsequent proposals (details in Appendix D). ❸ Ordering and commitment. Each replica locally interprets its DAG view to establish a consistent total order. To achieve consensus, replicas use a common coin at the end of the wave (i.e., in round 5 in Fig. 7) to elect a leader from the first round of that wave. The commitment decision is then made by checking votes on the leader in round 3: if the elected leader in round 1 is observed by at least f + 1 vertices in round 3, it

Instantiation of M ANTA

We instantiate M ANTA based on the analysis in Sec. 4. To better support flexible DAG growth, we first define solid step that comprises multiple rounds. Definition 3 (Solid Step). A sequence of rounds [r, r + σ] is termed a Solid Step of span σ if every honest replica proposes at least one vertex within these rounds that is a Solid Vertex regarding round r. We then define a parameter space Ω = (re f , cov, σ, κ) that abstracts the DAG growth process. Specifically, replicas propose a vertex in each round, and a wave consists of κ consecutive solid steps; each solid step spans σ rounds to achieve the target commit coverage cov. Subsequent proposals preserve the same coverage by causally extending the solid vertex. The choice of cov for each solid step and the number of solid steps κ per wave determine the resulting common core size in the worst case, suggesting that different configurations 7

Case A

Case B

Algorithm 1 M ANTA Core Utilities / round ← 1 1: Local variables: DAG[∗] ← 0, / committedRound ← 0 2: committed[∗] ← 0, 3: function PROPOSE V ERTEX() do 4: P ← GET PARENTS(round − 1) 5: if |P| ≥ re f or IS S OLID C ANDIDATE(round, P) then 6: v ← MAKE V ERTEX(round, P) 7: BROADCAST (v) 8: round ← round + 1 9: end if

coin flipping

coin flipping

commit-satisfied vertex

Round 1

2

3

4

1

2

3

4

Figure 8: Early leader finalization via flexible coin.

10: function NEXT C OMMITTEDV ERTICES() do 11: r ← committedRound + 1 12: if r + 1 ≤ round then 13: TRY FAST C OIN 6 (r) 14: end if 15: if r > committedRound and r + 2 ≤ round then 16: TRY F LEXIBLE C OIN (r) 17: end if 18: if r > committedRound and r + 2 ≤ round then 19: TRY R EGULAR (r) 20: end if 21: if committedRound ≥ r then 22: return committed[r] 23: end if 24: return 0/

is committed together with its causal history (Lines 33-34). Specifically, there are two commitment cases: • Direct commit. Let vl be the leader of wave w determined by the recovered coin. We use robs to denote the observation round, i.e., the round whose vertices are used to check whether vl has sufficient support for commitment. An honest replica commits vl if it is revealed by the recovered coin and is observed by enough vertices in round robs . In the regular path, we set robs = 3, which aligns with the default end-of-wave schedule (Lines 33-34). • Recursive commit. Leader vl is recursively committed if there exists a leader vertex v′l from a subsequent wave w′ > w that is directly committed and has a path to vl .

25: function TRY FAST C OIN(r) do 26: if CANDIDATES(r, r + 1) ≥ τcand then 27: TRY C OMMIT (r, r + 1) 28: end if

Flexible coin optimization. Since the connectivity required for commitment may emerge at different speeds under different network conditions, revealing common coin shares only at fixed round boundaries can introduce unnecessary delay. To address this, M ANTA designs a flexible coin mechanism: beyond the default end-of-wave schedule, a replica may piggyback its threshold-signature share onto its next vertex once its local DAG view indicates sufficient connectivity for commitment. If enough shares are collected early, replicas recover the common coin sooner and elect the first-round leader earlier; otherwise, the shares remain available for later recovery along the regular path. The early-release trigger is controlled by a parameter τcand , which affects only how aggressively early recovery is attempted and does not affect correctness. The resulting commitment check may either use the regular observation round robs = 3 (Lines 29-32) or, in a more aggressive fast-coin case, further advance the observation round to robs = 2 (Lines 25-28); to preserve safety in this case, M ANTA requires an extended solid step from round 2 to round 5 (details in Appendix C).

29: function TRY F LEXIBLE C OIN(r) do 30: if CANDIDATES(r, r + 2) ≥ τcand then 31: TRY C OMMIT (r, r + 2) 32: end if 33: function TRY R EGULAR(r) do 34: TRY C OMMIT (r, r + 2) 35: function TRY C OMMIT(r, robs ) do 36: vl ← GET L EADERV ERTEX(r) ▷ using the common coin 37: if vl ̸= ⊥ and |{v ∈ DAG[robs ] : PATH(vl , v)}| ≥ f + 1 then 38: COMMIT C AUSAL H ISTORY (vl , r) 39: end if 40: function CANDIDATES(r, robs ) do 41: return |{u ∈ DAG[r] : |{v ∈ DAG[robs ] : PATH(u, v)}| ≥ f + 1}| 42: upon receiving certified vertex v do 43: DAG.ADDV ERTEX(v)

Example. Consider a 4-round wave structure where the leader is elected in the fourth round, as shown in Fig. 8. In Cases A and B, sufficient connectivity already emerges by the second round, so releasing coin shares at that point allows replicas to recover the common coin and commit the leader earlier, whereas waiting until the default wave boundary would only add latency without improving commit probability.

5.3

Correctness Analysis

We sketch the safety and liveness arguments of M ANTA here and defer full proofs to Appendix C. 8

Safety. Along the regular path, a leader vertex vl of wave w (at round 1) can be committed if it is observed by at least f + 1 vertices in round 3. By the solid step structure, every vertex in round 5 must reference a quorum of at least 2 f + 1 round-3 vertices. Since n = 3 f + 1, quorum intersection guarantees that these 2 f + 1 referenced vertices and the f + 1 round-3 observers share at least one common vertex. Hence, every round-5 vertex (the first round of wave w + 1) must observe vl and include it in its causal history. Therefore, every leader committed in a later wave contains all earlier committed leaders in its causal history. Since replicas linearize each leader’s causal history using a deterministic ordering rule, all honest replicas derive the same total order of committed vertices.

under partial synchrony. We focus on its DAG-style data layer, modeling σ as a dynamic variable to capture nonuniform lane advancement. cov denotes the lane coverage required to form a consensus cut, typically 2 f + 1.

6

We build a prototype of M ANTA and compare it against four state-of-the-art counterparts: Tusk [12], Chitu [15], MahiMahi [14], and DAG-Rider [10], under various conditions. Our evaluation aims to answer three questions: • Q1: How do protocol parameters in the unified design space trade off with each other, and do the results align with our theoretical insights? (Sec. 6.2)

Liveness. M ANTA uses randomness to elect a leader in round 5. A round-1 leader vl is committed once it is observed by at least f + 1 round-3 vertices. Because each round-3 vertex must observe a quorum of 2 f + 1 round-1 vertices, quorum intersection ensures that, even under worst-case scheduling, there exists a non-empty set of at least f + 1 round-1 candidates satisfying the commitment condition. Thus, in each wave, the probability that the random coin selects a committable leader is at least ( f + 1)/(3 f + 1). Since this probability is strictly positive and waves repeat indefinitely, a leader is eventually committed with probability 1.

5.4

Evaluation

• Q2: How does M ANTA compare with existing DAG-based protocols under heterogeneous networks, and how resilient is it to node faults? (Sec. 6.3) • Q3: How effective is each component of M ANTA under heterogeneous networks, and what resource utilization does it incur? (Sec. 6.4)

6.1

Implementation and Experimental Setup

Implementation. We implement M ANTA on top of the public Tusk codebase [12], which is written in Rust and uses Tokio [36] for asynchronous networking1 . The implementation uses ed25519-dalek for signature generation and verification, TCP for reliable peer-to-peer communication, and RocksDB [37] for persistent storage of consensus data. For fair comparison, we also implement four stateof-the-art asynchronous counterparts on the same platform, following their open-source designs. The key configurations are as follows.

Encoding Existing DAG-BFT Protocols

M ANTA provides a unified abstraction for DAG-based BFT constructions. Using the four-dimensional parameter space Ω = {re f , cov, σ, κ}, we map five representative DAG-based protocols to discrete design points within a common framework. Although these systems differ in consensus logic and network assumptions, their DAG growth patterns can be interpreted as specific instantiations of our abstraction. • Tusk [12] and DAG-Rider [10]: Both protocols use σ = 1 with dense references re f = cov = 2 f + 1, so each round forms a solid step. In our framework, Tusk corresponds to κ = 2, while DAG-Rider uses κ = 3 to improve liveness at the cost of one additional round.

• Tusk and DAG-Rider. We instantiate these protocols by reconfiguring the common framework parameters. Tusk is obtained by setting re f = 2 f + 1, while DAG-Rider is obtained by setting κ = 3 and re f = 2 f + 1.

• Chitu [15]: Chitu introduces a leaderless fast path to avoid unnecessary fallback to more expensive consensus procedures. Structurally, it uses σ = 1 and re f = cov = 2 f + 1, making each round a solid step. Within our framework, Chitu dynamically switches between two wave configurations: a fast path with κ = 1 when observations are sufficiently aligned, and a normal path with κ = 3 when views diverge, and randomized leader selection is needed.

• Chitu. Chitu is built on DAG-Rider with fast-path optimizations in the consensus layer. It is configured with κ = 3 and re f = 2 f + 1, and further incorporates an adaptive waiting mechanism to ensure that the fast path is triggered under normal conditions. • Mahi-Mahi. Mahi-Mahi is configured with κ = 3 and re f = 2 f + 1. We also replace reliable broadcast with besteffort broadcast to construct an uncertified DAG, and reimplement the consensus layer accordingly.

• Mahi-Mahi [14]: Mahi-Mahi operates over an uncertified DAG with σ = 1 and re f = cov = 2 f + 1. Depending on the network model and desired commit probability, it can be represented with either κ = 3 or κ = 4 solid steps per wave.

Experimental setup. We deploy M ANTA on the CloudLab platform [16] using C6220 instances with 8 CPUs,

• Autobahn [21]: Autobahn adopts a decoupled architecture in which data lanes and consensus progress independently

1 The source code is at https://github.com/michaelwcl323/manta

-nsdi27.

9

0.9

2

4 Reference ref

1.1

0.9

7

2

4 3 2

σ=1 σ=2 σ=3

σ=4 σ=5 σ=6

1

4 Reference ref

7

0

(a) Effect of σ and ref under N1. (b) Effect of σ and ref under N2. κ=2 κ=4 κ=5

2.0 1.0 0.0

1.5

2.0

Latency (s)

Latency (s)

Latency (s)

3.0

1.5 1.0

40

60 Time (s)

cov = 7 cov = 10

1.0

0.5

0.5 2

4 7 Coverage cov

(d) κ, cov under N1.

10

0.0

80

100

120

(c) κ, cov with adversaries.

κ=2 κ=4 κ=5

2.5

20

2.5 Latency (s)

1.1

Attack Window

κ = 2, cov = 4 κ = 2, cov = 7 κ = 3, cov = 7 κ = 3, cov = 10

5 1.3 Latency (s)

Latency (s)

σ=4 σ=5 σ=6

Latency (s)

σ=1 σ=2 σ=3

1.3

cov = 7 cov = 10

2.0 1.5 1.0 0.5

2

4 7 Coverage cov

0.0

10

(e) κ, cov under N2.

(1, 2)(1, 4)(2, 2)(2, 4)(4, 1)(4, 2) (σ, κ)

0.0

(1, 2)(1, 4)(2, 2)(2, 4)(4, 1)(4, 2) (σ, κ)

(f) σ, κ for diverse cov under N1. (g) σ, κ for diverse cov under N2.

Figure 9: Impact of framework parameters under benign and Byzantine settings. N1 and N2 represent homogeneous and geographically heterogeneous node deployments, respectively. 64 GB RAM, and Ubuntu 22.04.2 LTS. To approximate realistic deployments, we refer to the validator distributions of Sui [32] and Aptos [30], two representative DAG-based public blockchains, and construct a WAN with three clusters: Cluster A containing 60% of nodes, Cluster B 30%, and Cluster C 10%. Inter-cluster latency and jitter are emulated using Linux tc-netem. The one-way delays are configured as follows: A–B: 51.3 ms (1.0 ms jitter), B–C: 76.6 ms (1.5 ms jitter), and A–C: 117.15 ms (2.5 ms jitter). We do not inject additional delay within clusters. Due to limited availability of C6220 instances on CloudLab, experiments requiring 50 nodes are conducted on AWS EC2 [38] using t3.2xlarge instances with 8 vCPUs, 30 GB memory, and Ubuntu 22.04.4 LTS. Nodes and clients are deployed across three regions: Frankfurt (eu-central-1, 60%), Hong Kong (ap-east-1, 10%), and Ohio (us-east-2, 30%), with RTTs between regions ranging from 99 ms to 203 ms. Each node is paired with a client that submits a fixed number of 512 B transactions every 50 ms. Nodes batch received transactions into newly generated vertices. Following standard blockchain benchmarking methodology, we define consensus latency as the time from when a transaction is first received by a node until it is successfully ordered. Unless otherwise stated, we use (σ = 2, re f = f +1, cov = 2 f +1, κ = 2) as the default configuration of M ANTA.

6.2

network conditions and examine the trade-offs among them. The first two parameters shape DAG growth and progression, and therefore primarily affect latency. The latter two govern the robustness of the commit condition and are introduced to preserve safety and liveness in the worst case. The impact of σ and re f . We fix cov = 2 f + 1 and κ = 2, and evaluate configurations with σ ∈ {1, 2, 3, 4, 5, 6} and re f ∈ {2, 4, 7} under n = 10 and f = 3. Fig. 9b shows that under network heterogeneity, σ > 1 achieves lower latency than σ = 1, as a larger span enables more flexible DAG progression and better exploits the flexible coin; a smaller re f further reduces synchronization delay. In the homogeneous setting (Fig. 9a), this advantage becomes smaller as inter-replica delay variation decreases. Latency remains similar for σ > 2 because increasing the span does not introduce additional serial coverage dependencies once the solid step is formed. The impact of κ and cov. The parameters cov and κ govern worst-case robustness and the number of solid steps within a wave, respectively. We vary cov ∈ {2, 4, 7, 10} and κ ∈ {2, 4, 5} under both network settings, first fixing σ = 1, where re f = cov. Figs. 9d and 9e show that latency generally increases with κ, while at low cov, additional solid steps can improve accumulated connectivity and reduce latency. In the homogeneous setting, latency varies little with cov, whereas under network heterogeneity, a large cov increases latency by requiring more slow replicas. We further vary σ and κ with re f = 4 and cov ∈ {7, 10}. For example, (σ, κ) = (1, 4), (2, 2), (4, 1) have the same number of rounds per wave but different internal constructions. Figs. 9f and 9g

Design Parameter Trade-off

We next evaluate the four key parameters (σ, re f , cov, κ) in the framework under both homogeneous and heterogeneous 10

Chitu

DAG-Rider

4.0

Mahi-Mahi

Manta

10

3.5

6

2.5 2.0 1.5

Latency (s)

Latency (s)

Latency (s)

3.0 5 4 3

1.0

40

50

60

70

80

Throughput (KTps)

90

100

(a) n=10, fault-free.

110

1

8 6 4 2

2

0.5 0.0

Tusk

7

0 50

60

70

80

90

100

Throughput (KTps)

110

120

60

(b) n=50, fault-free.

70

80

90

Throughput (KTps)

100

110

(c) n=10, 3 faults.

Figure 10: Throughput vs. latency in fault-free and fault settings. complete

6.3

Performance of M ANTA

6.3.1

Fault-Free Performance

100 75 50 25 0

no flexible coin

Latency (s)

Throughput (KTps)

show that fewer, longer solid steps achieve lower latency than more, shorter solid steps. In the homogeneous setting, increasing cov can further reduce latency by improving connectivity with little additional synchronization cost. We also evaluate a Byzantine scenario, where faulty replicas selectively delay messages to reduce shared DAG connectivity. Fig. 9c shows that when cov = f + 1, latency increases sharply under attack, while the degradation gradually decreases as cov and κ increase and is nearly neutralized at κ = 3, cov = 10. This is because larger cov and κ can yield a larger common core under this adversarial schedule, leaving less room for the attacker to disrupt commitment. Based on these observations, in heterogeneous networks, the selected configuration of M ANTA captures most of the flexibility benefit while satisfying correctness requirements.

80000 100000 120000 Input Rate (tx/s)

1.0

0.5

0.0

(a) Throughput.

80000 100000 120000 Input Rate (tx/s)

(b) Latency.

Figure 11: Ablation of flexible coin. 6.3.2

Performance under Faults

Fig. 10c evaluates the resiliency of M ANTA under silent faults, where up to f nodes are silent (i.e., crash or intentionally stop participating). We focus on silent faults because they directly stress DAG progression and are a common practical source of slowdown in WAN deployments. As shown in Fig. 10c, M ANTA shows performance comparable to the other protocols under faults. The remaining replicas can form more complete connectivity, potentially making it easier for baseline protocols to follow their fast paths and leaving less room for M ANTA to benefit from faster progression.

Figs. 10a and 10b compare M ANTA against DAG-Rider, Tusk, Chitu, and Mahi-Mahi under fault-free settings (i.e., all nodes remain active throughout execution) at two system scales: n = 10 and n = 50 replicas. M ANTA achieves the lowest latency at n = 10, reducing latency by 30%–70%. Two mechanisms drive this gain. First, flexible DAG growth allows M ANTA to progress with smaller quorums and form useful connectivity earlier, rather than waiting for rigid per-round thresholds. This is particularly beneficial in heterogeneous WANs with uneven cross-region delays. Second, the flexible coin enables commitment as soon as sufficient connectivity emerges, allowing earlier finalization. Although Chitu and Mahi-Mahi also partially mitigate rigid waiting through optimistic paths or lightweight dissemination, uneven delays can still enlarge divergence in local DAG views, making their commit conditions slower or more expensive to satisfy. Fig. 10b shows that the advantage of M ANTA persists at a larger scale. It reduces latency by around 70% compared with Chitu, Tusk, and DAG-Rider. Compared to Mahi-Mahi, the second-best baseline in this experiment, M ANTA delivers around 30% lower latency and 18% higher throughput, demonstrating robust scalability in larger deployments.

6.4

Breakdown and Resource Utilization

Fig. 11 compares M ANTA with a variant that disables the flexible coin. The results show that the flexible coin consistently reduces latency by enabling replicas to check commitment as soon as sufficient connectivity emerges, rather than waiting until the completion of a wave. Its benefit becomes more pronounced as the input rate increases. Under heavier workloads, faster replicas generate additional vertices while waiting to advance to the next solid step, which can be committed by the flexible coin once they become sufficiently connected. We further measure the effect of flexible DAG growth on round duration. Flexible DAG growth introduces more rounds within a wave but shortens each round from about 139.4 ms to 75.8 ms. The flexible coin complements this progression by allowing replicas to commit before the final round. Together, flexible DAG growth speeds up round progression, and the flexible coin converts this progress into earlier commitment. 11

Table 2: Resource utilization under system breakdown. Variants

Complete

No flexible coin

Tusk

CPU Avg. BW Avg.

8.744% 45.908%

8.831% 45.955%

8.272% 38.313%

Uncertified DAG-based BFT. Some recent systems build DAGs using uncertified vertices [14, 42] and replace reliable broadcast with best-effort dissemination to reduce overhead. While efficient in favorable environments, such designs are more sensitive to packet loss and delay variation in WANs, where replicas may miss data and must fetch it later. The data recovery can block the critical path and degrade end-toend performance. Accordingly, we focus on certified DAG constructions as prior designs [10, 12, 15].

Resource Utilization. Table 2 reports the resource usage of M ANTA. The flexible coin incurs negligible additional cost, with CPU utilization and bandwidth consumption remaining nearly unchanged compared with the variant without it. The complete protocol uses slightly more resources than Tusk, mainly due to the metadata required for solid-step tracking. In addition, Boost edges introduce additional cross-round references and may incur DAG state management overhead. Overall, the average per-vertex metadata is 1,465.8 B for M ANTA, compared with 388.0 B for Tusk.

Flexibility in DAG-based BFT. Several works introduce flexibility into DAG-based consensus. Angelfish [47] adapts vertex and vote reference rules, while Sparse DAG [48] reduces metadata through sparse references. These designs explore different forms of flexibility, while M ANTA focuses on relaxing round progression under asynchrony. Lemonshark [49] adopts a Narwhal-style DAG and uses key-space sharding for early finality, which is orthogonal to M ANTA. Avalanche [50] avoids explicit round boundaries and progresses through probabilistic sub-sampling, with safety characterized through probabilistic convergence. Round-based protocols use explicit rounds and waves, simplifying safety analysis and commit reasoning but coupling progress to round boundaries. M ANTA follows this model while relaxing round advancement conditions.

Limitations and Trade-offs. Beyond these results, several limitations and open directions remain. A lower reference threshold may disadvantage slow replicas, while τcand introduces a trade-off between early recovery and worst-case latency under Byzantine behavior. Dynamic adaptation would require coordinated updates, e.g., through observation-driven mechanisms [39] or BFT reconfiguration [40]. Overall, these limitations motivate dynamic parameter adaptation and finergrained coin scheduling as future work.

7

8

Conclusion

We revisit a core assumption in asynchronous DAG-based BFT consensus: connectivity must accumulate through rigid round-by-round progression. We show that this rigidity becomes a major bottleneck in heterogeneous WANs. We present a flexible DAG growth framework that decouples commit requirements from round advancement. Based on it, we design M ANTA, which combines flexible growth for earlier connectivity and a flexible coin for earlier commitment. Experiments show that M ANTA consistently outperforms prior asynchronous DAG-based BFT protocols under fault-free heterogeneous deployments, reducing latency by at least 30% while preserving robustness.

Related Work

Asynchronous BFT. Asynchronous BFT protocols, such as HoneyBadgerBFT [11] and the Dumbo family [7, 41], avoid timing assumptions by leveraging randomization to achieve consensus in asynchronous environments and are therefore robust to WAN uncertainty. More recently, asynchronous DAGbased protocols [10, 12, 14, 15] further improve performance through structured parallelism. DAG-Rider [10] is the first to realize asynchronous BFT over a DAG. Tusk [12] extends this direction with a mempool layer that decouples metadata from data dissemination. Chitu [15] adds a fast path that directly commits under favorable conditions. Mahi-Mahi [14] further improves performance through uncertified DAG construction and lightweight dissemination. However, these systems largely retain fixed DAG progression rules, whereas M ANTA focuses on redesigning DAG progression itself to better exploit heterogeneity in WANs. Partially synchronous DAG-based BFT. Another line of DAG-based protocols [21, 42–46] assumes partial synchrony networks and uses designated leaders to accelerate commitment, often through optimistic paths. These protocols perform well when underlying timing assumptions hold, but can suffer performance degradation under highly heterogeneous WAN conditions [11]. By contrast, M ANTA operates under a fully asynchronous model without synchrony assumptions. 12

References

[13] Vitor Enes, Carlos Baquero, Tuanir França Rezende, Alexey Gotsman, Matthieu Perrin, and Pierre Sutra. State-machine replication for planet-scale systems. In Proc. of EuroSys, 2020.

[1] Florian Suri-Payer, Matthew Burke, Zheng Wang, Yunhao Zhang, Lorenzo Alvisi, and Natacha Crooks. Basil: Breaking up BFT with ACID (transactions). In Proc. of SOSP, 2021.

[14] Philipp Jovanovic, Lefteris Kokoris-Kogias, Bryan Kumara, Alberto Sonnino, Pasindu Tennage, and Igor Zablotchi. Mahi-Mahi: Low-latency asynchronous BFT DAG-based consensus. In Proc. of ICDCS, 2025.

[2] Dennis Trautwein, Aravindh Raman, Gareth Tyson, Ignacio Castro, Will Scott, Moritz Schubotz, Bela Gipp, and Yiannis Psaras. Design and evaluation of IPFS: a storage layer for the decentralized web. In Proc. of SIGCOMM, 2022.

[15] Rongji Huang, Xiangzhe Wang, Xiaofeng Yan, Lei Fan, Guangtao Xue, and Shengyun Liu. Chitu: Avoiding unnecessary fallback in Byzantine consensus. In Proc. of USENIX ATC, 2025.

[3] Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos, and Nickolai Zeldovich. Algorand: Scaling Byzantine agreements for cryptocurrencies. In Proc. of SOSP, 2017.

[16] Dmitry Duplyakin, Robert Ricci, Aleksander Maricq, Gary Wong, Jonathon Duerig, Eric Eide, Leigh Stoller, Mike Hibler, David Johnson, Kirk Webb, et al. The design and operation of CloudLab. In Proc. of USENIX ATC, 2019.

[4] Timo Hanke, Mahnush Movahedi, and Dominic Williams. Dfinity technology overview series, consensus system. arXiv preprint arXiv:1805.04548, 2018.

[17] Gabriel Bracha. Asynchronous Byzantine agreement protocols. Information and computation, 75(2):130–143, 1987.

[5] Miguel Castro and Barbara Liskov. Practical Byzantine fault tolerance. In Proc. of OSDI, 1999.

[18] Danny Dolev and Eli Gafni. Some garbage insome garbage out: Asynchronous t-Byzantine as asynchronous benign t-resilient system with fixed t-trojanhorse inputs. arXiv preprint arXiv:1607.01210, 2016.

[6] Maofan Yin, Dahlia Malkhi, Michael K Reiter, Guy Golan Gueta, and Ittai Abraham. Hotstuff: BFT consensus with linearity and responsiveness. In Proc. of PODC, 2019.

[19] Benoît Libert, Marc Joye, and Moti Yung. Born and raised distributively: Fully distributed non-interactive adaptively-secure threshold signatures with short shares. In Proc. of PODC, 2014.

[7] Bingyong Guo, Zhenliang Lu, Qiang Tang, Jing Xu, and Zhenfeng Zhang. Dumbo: Faster asynchronous BFT protocols. In Proc. of CCS, 2020. [8] Minghang Li, Qianhong Wu, Zhipeng Wang, Bo Qin, Bohang Wei, Hang Ruan, Shihong Xiong, and Zhenyang Ding. Tockowl: Asynchronous consensus with fault and network adaptability. In Proc. of USENIX Security, 2025.

[20] Dan Boneh, Ben Lynn, and Hovav Shacham. Short signatures from the Weil pairing. In Proc. of ASIACRYPT, 2001. [21] Neil Giridharan, Florian Suri-Payer, Ittai Abraham, Lorenzo Alvisi, and Natacha Crooks. Autobahn: Seamless high speed BFT. In Proc. of SOSP, 2024.

[9] Sisi Duan, Michael K Reiter, and Haibin Zhang. BEAT: Asynchronous BFT made practical. In Proc. of CCS, 2018.

[22] Xingda Wei, Sijie Shen, Rong Chen, and Haibo Chen. Replication-driven live reconfiguration for fast distributed transaction processing. In Proc. of USENIX ATC, 2017.

[10] Idit Keidar, Eleftherios Kokoris-Kogias, Oded Naor, and Alexander Spiegelman. All you need is DAG. In Proc. of PODC, 2021.

[23] Zaoxing Liu, Zhihao Bai, Zhenming Liu, Xiaozhou Li, Changhoon Kim, Vladimir Braverman, Xin Jin, and Ion Stoica. DistCache: Provable load balancing for LargeScale storage systems with distributed caching. In Proc. of FAST, 2019.

[11] Andrew Miller, Yu Xia, Kyle Croman, Elaine Shi, and Dawn Song. The Honey Badger of BFT protocols. In Proc. of CCS, 2016. [12] George Danezis, Lefteris Kokoris-Kogias, Alberto Sonnino, and Alexander Spiegelman. Narwhal and Tusk: a DAG-based mempool and efficient BFT consensus. In Proc. of EuroSys, 2022.

[24] Brian F Cooper, Adam Silberstein, Erwin Tam, Raghu Ramakrishnan, and Russell Sears. Benchmarking cloud serving systems with YCSB. In Proc. of SoCC, 2010. 13

[25] Jialin Li, Jacob Nelson, Ellis Michael, Xin Jin, and Dan RK Ports. Pegasus: Tolerating skewed workloads in distributed storage with In-Network coherence directories. In Proc. of OSDI, 2020.

[40] Xuanji Meng, Xiao Sui, Zhaoxin Yang, Kang Rong, Wenbo Xu, Shenglong Chen, Ying Yan, and Sisi Duan. Rondo: Scalable and reconfiguration-friendly randomness beacon. In Proc. of NDSS, 2025.

[26] Qizhen Weng, Wencong Xiao, Yinghao Yu, Wei Wang, Cheng Wang, Jian He, Yong Li, Liping Zhang, Wei Lin, and Yu Ding. MLaaS in the wild: Workload analysis and scheduling in Large-Scale heterogeneous GPU clusters. In Proc. of NSDI, 2022.

[41] Bingyong Guo, Yuan Lu, Zhenliang Lu, Qiang Tang, Jing Xu, and Zhenfeng Zhang. Speeding Dumbo: Pushing asynchronous BFT closer to practice. In Proc. of NDSS, 2022. [42] Kushal Babel, Andrey Chursin, George Danezis, Anastasios Kichidis, Lefteris Kokoris-Kogias, Arun Koshy, Alberto Sonnino, and Mingwei Tian. Mysticeti: Reaching the latency limits with uncertified DAGs. In Proc. of NDSS, 2025.

[27] Fangyu Gai, Jianyu Niu, Ivan Beschastnikh, Chen Feng, and Sheng Wang. Scaling blockchain consensus via a robust shared mempool. In Proc. of ICDE, 2023. [28] Shashank Motepalli and Hans-Arno Jacobsen. Analyzing geospatial distribution in blockchains. In Proc. of DAPPS, 2023.

[43] Nibesh Shrestha, Rohan Shrothrium, Aniket Kate, and Kartik Nayak. Sailfish: Towards improving the latency of DAG-based BFT. In Proc. of IEEE S&P, 2025.

[29] Shashank Motepalli, Naman Garg, Gengrui Zhang, and Hans-Arno Jacobsen. Gpos: Geospatially-aware proof of stake. ACM Transactions on the Web, 20(1):1–20, 2026.

[44] Balaji Arun, Zekun Li, Florian Suri-Payer, Sourav Das, and Alexander Spiegelman. Shoal++: High throughput DAG BFT can be fast and robust! In Proc. of NSDI, 2025.

[30] Aptos Labs. Aptos validators explorer (mainnet). http s://explorer.aptoslabs.com/validators/all? network=mainnet, 2026. Accessed: 2026-03-22.

[45] Alexander Spiegelman, Neil Giridharan, Alberto Sonnino, and Lefteris Kokoris-Kogias. Bullshark: DAG BFT protocols made practical. In Proc. of CCS, 2022.

[31] Validators.app. Validator data center distribution (mainnet). https://www.validators.app/map?locale= en&network=mainnet, 2026. Accessed: 2026-03-22.

[46] Nibesh Shrestha and Aniket Kate. Towards improving throughput and scalability of DAG-based BFT SMR. In Proc. of EuroSys, 2026.

[32] BlockVision. Sui validators explorer. https://suivis ion.xyz/validators, 2026. Accessed: 2026-03-22.

[47] Qianyu Yu, Giuliano Losa, Nibesh Shrestha, and Xuechao Wang. Angelfish: Leader, DAG, or anywhere in between. In Proc. of CCS, 2026.

[33] Rachid Guerraoui, Petr Kuznetsov, Matteo Monti, Matej Pavlovic, and Dragos-Adrian Seredinschi. Scalable Byzantine reliable broadcast. In Proc. of DISC, 2019.

[48] Michael Anoprenko, Andrei Tonkikh, Alexander Spiegelman, and Petr Kuznetsov. Brief announcement: DAGs for the masses. In Proc. of DISC, 2025.

[34] Fred B Schneider. Implementing fault-tolerant services using the state machine approach: A tutorial. Acm Computing Surveys, pages 299–319, 1990.

[49] Michael Yiqing Hu, Alvin Hong Yao Yan, Yihan Yang, Xiang Liu, and Jialin Li. Lemonshark: Asynchronous DAG-BFT with early finality. In Proc. of NSDI, 2026.

[35] Victor Shoup. Blue fish, red fish, live fish, dead fish. In Proc. of ICBC, 2025.

[50] Team Rocket, Maofan Yin, Kevin Sekniqi, Robbert van Renesse, and Emin Gün Sirer. Scalable and probabilistic leaderless BFT consensus through metastability. arXiv preprint arXiv:1906.08936, 2019.

[36] Tokio. Tokio: Rust asynchronous runtime. https: //tokio.rs/, 2026. Accessed: 2026-04-22. [37] RocksDB. Rocksdb. https://rocksdb.org, 2026. Accessed: 2026-04-22.

[51] Michael J Fischer, Nancy A Lynch, and Michael S Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM (JACM), 32(2):374– 382, 1985.

[38] Amazon Web Services. Amazon web services. https: //aws.amazon.com, 2026. Accessed: 2026-04-22. [39] Zeno De Angeli, Alexandru Ianov Vitanov, Philipp Jovanovic, Lefteris Kokoris-Kogias, Alberto Sonnino, Pasindu Tennage, and Igor Zablotchi. Barnacle: Adaptive multi-leader scheduling for DAG-Based consensus. arXiv preprint arXiv:2609.03978, 2026.

[52] Ittai Abraham, Gilad Asharov, Arpita Patra, and Gilad Stern. Perfectly secure asynchronous agreement on a core set in constant expected time. IACR Cryptol. ePrint Arch., 2023:1130, 2023. 14

A A.1

Building Blocks

A.3

We follow the common core abstraction used in prior works [18, 52]. Each replica pi starts with an input xi , and outputs a set of received values. Let Vit denote the set held by replica pi after round t, for t = 1, 2, ..., k. The common core protocol proceeds in k rounds, with each round aggregating the sets/inputs received from the preceding round: Round 1. Each replica broadcasts its input xi using reliable broadcast. Vi1 = {xi }. Round 2. Upon collecting at least re f inputs x j from round S 1, pi unions them into a set Vi2 = V j1 and sends it to all replicas. Round t (t ≥ 3). Upon collecting at least re f sets from round S t − 1, pi unions them into a set Vit = V jt−1 , and sends it to all replicas. Output. After completing round k, each replica outputs Vik . The key property of this abstraction is that there exists a set S such that S ⊆ Vik for every honest replica pi . We refer to such a set S as a common core. The size of the common core, i.e., |S|, captures how many first-round input values are guaranteed to be commonly visible at the end of the protocol. As we mentioned in Sec. 4.1, |S| determines the commitment probability of a wave. We model the latency under the following three scenarios (Heterogeneous Network B.1, Random-delay Network B.2, and Adversarial Network B.3).

Reliable Broadcast (RBC)

RBC [17] is a fundamental primitive in consensus protocol designed to ensure non-equivocation. It guarantees that even under a Byzantine sender, all honest parties eventually deliver the same message or none at all. Formally, each replica pk can broadcast messages by calling Bcast(m, r), where m is the message, and r ∈ N is a round number. By running the protocol, every pi has an output Deliver(m, r, pk ), where m is the message, r is a round number, and pk is the replica that invoked the corresponding Bcast(m, r). RBC typically satisfies the following properties: Agreement. If an honest replica pi outputs Deliver(m, r, pk ), then every other honest replica p j eventually outputs Deliver(m, r, pk ). Integrity. For each round r, an honest replica pi outputs Deliver(m, r, pk ) at most once regardless of m. Validity. If an honest replica pk calls Bcast(m, r), then every honest replica pi eventually outputs Deliver(m, r, pk ).

A.2

Common Core Abstraction

Global Perfect Coin

B

The global perfect coin [11, 19, 20] (also known as common coin) is a cryptographic primitive that allows a set of distributed nodes to reach a consensus on a common, unpredictable random value in an asynchronous network. By providing shared randomness, it serves as a critical mechanism to circumvent the FLP impossibility [51]. For each instance w ∈ N, any replica pi ∈ Π can call ChooseLeaderi (w) to identify the leader for that instance. The coin ensures that all honest replicas receive the same leader p j ∈ Π, and this outcome remains unknown to the adversary until the call is made. We denote Xw as the random variable representing the leader selection outcome for instance w. The global perfect coin provides the following guarantees:

B.1

DAG Growth Proof Heterogeneous Network Model

For analytical tractability, we assume a stable aggregate arrival trend across replicas. Vertices can be viewed as arriving in tiers, where faster tiers reach the reference quorum and become commonly visible earlier than slower tiers. This model abstracts DAG evolution into a shared arrival process, using independent quorum delays without tracking replica-specific views or cross-round causal dependencies. Despite these simplifications, the model captures the key trends in latency and connectivity as the network delay distribution and DAG parameters vary.

Agreement. If two honest replicas pi , p j ∈ Π invoke ChooseLeaderi (w) and ChooseLeader j (w) respectively, they obtain the same output, i.e., p∗ .

Assumption 1 (Network delay). Let d denote the point-topoint network delay between two replicas. We assume that d follows a Log-normal distribution:

Termination. If at least f + 1 replicas invoke ChooseLeader(w), then every invocation by an honest replica eventually returns a value.

ln d ∼ N (µ, std 2 )

Unpredictability. As long as fewer than f + 1 replicas have invoked ChooseLeader(w), the outcome Xw remains indistinguishable from a uniform random distribution to the adversary, except with negligible probability ε.

Let f (x) be the probability density function (PDF) and F(x) = P(d ≤ x) be the cumulative distribution function (CDF), representing the probability that a vertex from a random replica i reaches the local replica within time x.

Fairness. The coin is unbiased such that for every instance w ∈ N, ∀p j ∈ Π, Pr[Xw = p j ] = 1/n.

Definition 4 (Round Duration). Consider a system with n replicas. A round can advance only after collecting vertices 15

Proof. By construction, after the wave window W (re f , k − 1), at least Φ(re f , k) first-round vertices are visible with confidence c. Under the conservative assumption that only these visible vertices are safely committable, and the leader is chosen uniformly from all n candidates, the probability that the chosen leader belongs to this visible set is at least Φ(re f , k)/n.

from at least re f distinct replicas. Let d(re f ) denote the re f -th order statistic of n i.i.d. copies of d. Then d(re f ) represents the time required to complete one logical round. Lemma 1 (Distribution of Round Duration). The CDF of the round duration d(re f ) is n   n Fd(re f ) (x) = ∑ [F(x)] j [1 − F(x)]n− j j j=re f

Theorem 3 (Latency under heterogeneous delay). Let W (re f , k) denote the c-quantile of the wave duration covering k rounds. Under the above model, the protocol latency is approximated by

Proof. The event d(re f ) ≤ x is equivalent to saying that at least re f among the n delays are no larger than x. Since each delay is at most x with probability F(x), the result follows from the Binomial distribution.

L≈

Definition 5 (Single-round window). For a target confidence level c ∈ (0, 1), define

W (re f , k) . P

Using the lower bound on P from Theorem 2, this yields a latency estimate in terms of W (re f , k) and Φ(re f , k).

Wstep (c) = inf{t : Fd(re f ) (t) ≥ c}.

B.2

This is the minimum physical time within which one round completes with confidence at least c.

In the random network model, we assume that in each round r, an honest replica references a uniformly random subset of re f replicas from the preceding round r − 1. Let xr ∈ {0, . . . , n} be the number of vertices in round r who possess a causal path to the leader v. The growth of leader visibility depends on the probability qr that a vertex in round r hits at least one successful vertex (i.e., those with a path to v) from the preceding round. We define qr as a piecewise function: ( ref /n, r=2 qr = n−xr−1
 n
1 − ref ref , r > 2

Definition 6 (Wave window). For a wave consisting of k rounds, let k−1

Random-Delay Network Model (Stochastic case).

(i)

Hk−1 = ∑ d(re f ) , i=1

(1) (k−1) where d(re f ) , . . . , d(re f ) are independent copies of d(re f ) . Intu-

itively, a vertex that is observed at the decision point in round k has undergone propagation for k − 1 rounds. Accordingly, the distribution of Hk−1 is determined by the (k − 1)-fold convolution of the distribution of d(re f ) . For a target confidence level c ∈ (0, 1), we define the wave window as W (re f , k − 1) = inf{t : FHk−1 (t) ≥ c},

To formalize the recursive transition, we define the Propagation Operator Br as the binomial probability mass function:

where FHk−1 denotes the cumulative distribution function of Hk−1 .

Br = Bin(xr ; Nr , qr )

Definition 7 (Effective visible set size). For any physical time t, define

where the trial size Nr is n for intermediate propagation rounds (r < k) and ref for the final decision round (r = k). A leader is committed if its support in the final decision round k satisfies the threshold xk ≥ f + 1. Using the law of total probability, the commit probability P is derived by marginalizing over all possible intermediate states: 1) Two-round wave (k = 2): In a 2-round wave, round 2 is the decision round. Each vertex in round 2 has re f parents, and there is exactly 1 leader in round 1. The probability that a round-2 vertex connects to the leader is q2 = re f /n:

Count(t) = max{ j ∈ {1, . . . , n} : Fd( j) (t) ≥ c} which represents the number of replicas whose vertices are visible within time t with confidence at least c. At the end of round k, define the effective visible set size as Φ(re f , k) = max (re f , Count(W (re f , k − 1))) Theorem 2 (Commit probability under heterogeneous delay). Under the above model, the number of effectively visible firstround vertices after a wave is lower bounded by Φ(re f , k). If the leader is selected uniformly at random from the n firstround vertices, then the commit probability admits the lower bound Φ(re f , k) P≥ . n

ref

P(2) =

∑ B2

x2 = f +1

2) Three-round (k = 3): In a 3-round wave, round 2 acts as a propagation layer, and the decision is made in round 3 based on the accumulated visibility x2 : 16

"

n

ref

P(3) = ∑ B2 x2 =0

To evaluate the liveness of the protocol under adversarial scheduling, we categorize the vertices in the first round (R1 ) into two disjoint sets based on their guaranteed visibility from the decision round Rk :

#

∑ B3

x3 = f +1

3) Generalized Multi-round Model (k ≥ 4): For a wave of length k, the leader propagates through k − 2 intermediate rounds before the final quorum check: n

n

n

P(k) = ∑ B2 ∑ B3 · · · x2 =0

x3 =0

• Guaranteed set (Gk ): the set of vertices in R1 that are guaranteed to satisfy the commit rule under any admissible adversarial DAG topology; let gk = |Gk | denote its size.

ref

• Uncertain set (Uk ): the set of remaining vertices in R1 , whose committability depends on the realized topology and is therefore not guaranteed in the worst case. For the purpose of establishing a lower bound, we conservatively treat these vertices as non-committable.

∑ Bk−1 ∑ Bk

xk−1 =0

xk = f +1

In this random delay model, we quantify the expected latency by the number of rounds required for a vertex to be committed, expressed as: E(rounds) =

Lemma 2. Under the adversarial model with n = 3 f + 1 and a wave length of k = 2, if each vertex references re f ≥ n − f parents, then there are at least f + 1 vertices in R1 guaranteed to satisfy the commit rule.

k P(k)

We evaluate the commit probability P(k) and the expected rounds E[rounds] required across various f under two typical configurations, as summarized in Table 3 and Table 4.

Proof. Given that each vertex has a minimum reference count re f and n1 ranges within [2 f + 1, 3 f + 1]. Consider any set of re f vertices in R2 , the total number of links from the set to the first round vertices is at least re f · re f . If a vertex is in Gk , it receives ≥ f + 1 links, while a vertex in Uk receives ≤ f links. The maximum number of links from vertices in the set to each vertex in the first round is re f ; therefore, a vertex in Gk receives at most re f links, while a vertex in Uk receives at most f links. Therefore, the total link balance is expressed as gk · re f + (n1 − gk ) · f ≥ re f · re f . To find the minimum bound, we set n1 = 3 f + 1. Substituting re f ≥ n − f :

Table 3: P(k) for different re f configurations. re f

f

k=2

k=3

k=4

2f +1

1 3 10

0.8437 0.8739 0.9555

0.9887 0.9999 0.9999

0.9955 0.9999 0.9999

f +1

1 3 10

0.2500 0.0256 ≈0

0.6354 0.6614 0.9279

0.8284 0.9744 0.9999

gk ≥

This completes the proof. Similarly, we observe how gk varies with different values of re f under k = 2: 1) If re f ≥ f + 1, then gk ≥ −2 f 2 + f + 1 ≤ 0 for f ≥ 1, providing no liveness guarantee. 2) If re f ≥ 1.8 f + 1, then gk ≥ 1, which is the minimum requirement for liveness.

Table 4: E(rounds) for different re f configurations.

B.3

re f

f

k=2

k=3

k=4

2f +1

1 3 10

2.37 2.28 2.09

3.03 3.00 3.00

4.01 4.00 4.00

f +1

1 3 10

8.00 78.12 –

4.72 4.53 3.23

4.82 4.10 4.00

f2 +3f +1 ≥ f +1 f +1

Lemma 3. Under the adversarial model with n = 3 f + 1 and a wave length of k = 3, if each vertex references re f ≥ n − f parents, then there are at least 1.5 f vertices in R1 guaranteed to satisfy the commit rule. Proof. Given that each vertex has a minimum reference count re f and the round sizes n1 , n2 range within [2 f + 1, 3 f + 1], the total number of links from R2 to R1 is n2 · re f . In a wave of length k = 3, a vertex v ∈ R1 belongs to the set Gk if it receives ≥ n2 − re f + 1 links from R2 . Since each vertex in R3 references at least re f parents from R2 , the principle of quorum intersection dictates that any selection of re f vertices in R2 must include at least one supporter of v. This ensures the existence of a causal path from every vertex in R3 to v.

Adversarial Network Model (Worst case)

In the adversarial network model, an asynchronous scheduler may manipulate the DAG topology to minimize the visibility of vertices. We define n = 3 f + 1 as the total number of replicas, and re f as the number of references per vertex; the number of vertices in round i is defined as ni . A vertex v ∈ R1 is committable if it is reachable from at least f + 1 distinct vertices in the decision round Rk . 17

Conversely, if a vertex receives ≤ n2 −re f links, it is classified into the set Uk . A vertex in Gk receives at most n2 links, while a vertex in Uk receives at most n2 − re f links. Therefore, the total link balance is expressed as gk · n2 + (n1 − gk ) · (n2 − re f ) ≥ n2 · re f . Solving for gk yields the general bound: gk ≥ n 1 + n 2 −

r3 . Under the flexible coin mechanism, replicas may observe and commit vl from r2 , r3 , or r4 . Case 1: Observation at r3 or r4 . We treat both as observation at r3 . Since the r3 to r5 interval constitutes a solid step, every vertex at r5 (the first round of wave i + 1) must have at least 2 f + 1 links to r3 . By quorum intersection (n = 3 f + 1), these 2 f + 1 referenced vertices and the f + 1 observers at r3 share at least one common vertex. Thus, every vertex in the first round of wave i + 1 has a path to vl . Case 2: Observation at r2 . When the r2 -r5 solid step is active, the protocol allows observation at r2 . Following the same logic, every vertex at r5 has at least 2 f + 1 links to r2 . Quorum intersection ensures that every vertex in the first round of wave w + 1 has a path to vl . By a simple inductive argument, every vertex in every round of any wave higher than w must contain a path to vl .

n1 · n2 re f

To find the minimum bound, we set n1 = n2 = 3 f + 1. Substituting re f ≥ n − f : gk ≥

(3 f + 1)( f + 1) ≥ 1.5 f 2f +1

This completes the proof. Similarly, we observe how gk varies with different values of re f under k = 3: f) 1) If re f ≥ f + 1, then gk ≥ (3 f +1)(1− ≤ 0 for f ≥ 1, f +1 providing no liveness guarantee. 2) If re f ≥ 1.5 f + 1, then gk ≥ 1, which is the minimum requirement for liveness. 3) If re f ≥ 1.8 f + 1, then gk ≥ f + 1.

Theorem 4. Any two honest replicas commit the same sequence of vertex leaders. Proof. Suppose an honest replica pi commits leader vertex v of wave w. Another honest replica p j commits leader vertex v′ of wave w′ , where w < w′ , but has not yet committed v. According to Lemma 5, there must exist a path from v′ to v. This implies that v is already in the causal history of v′ and must be committed by p j indirectly. This contradicts the assumption that p j could commit v′ while skipping v. Therefore, if a leader vertex is committed by one honest replica, no other replica can skip it, ensuring all honest replicas commit leader vertices in the same sequence.

Lemma 4. Under the adversarial model with n = 3 f + 1 and a wave length of k = 4, if each vertex references re f ≥ n − f parents, then there are at least 2 f + 1 vertices in R1 guaranteed to satisfy the commit rule. Proof. We treat vertices in R1 as the input to R2 , and the subsequent process from R2 to R4 as a wave of length k = 3. According to Lemma 3, when re f ≥ n − f , there are at least gk ≥ 1.5 f vertices in R2 that are guaranteed to be part of the common core. Let this set of vertices be S ⊂ R2 , where |S| ≥ 1.5 f . Each vertex v ∈ S references at least re f parents from R1 . To find the minimum number of vertices in R1 that are included in the common core, we consider the worst-case scenario where the reference sets of all vertices in S overlap maximally. Even if all 1.5 f vertices in S reference the exact same set of parents in R1 to minimize the total count, they collectively guarantee the availability of at least re f vertices. Given re f = 2 f + 1, this ensures that at least 2 f + 1 vertices in R1 are causally connected to the common core of the k = 4 wave. This completes the proof.

C C.1

C.2

Liveness Proof

Lemma 6. For every wave w, there are at least f + 1 vertices in the first round of w that satisfy the commit rule. Proof. In the regular process, consider an arbitrary set of 2 f + 1 vertices at round 3 in wave w. According to the solid step rule, each vertex must reference at least 2 f + 1 vertices from round 1, resulting in a total number of links from round 3 to round 1 of at least (2 f + 1)(2 f + 1). There are at most n = 3 f + 1 vertices in round 1. Let h be the number of vertices that satisfy the commitment condition (receiving ≥ f + 1 links) and l be the number of vertices that do not. To find the minimum h, we construct a worst-case scenario where each non-committable vertex receives the maximum possible f links, while each committable vertex receives up to 2 f + 1 links. The total number of links satisfies h(2 f + 1) + l · f ≥ (2 f + 1)2 , where l = n − h. Therefore, we have h ≥ f + 1, proving that at least f + 1 vertices at round 1 satisfy the commitment condition.

M ANTA Correctness Analysis Safety Proof

Lemma 5. If an honest replica commits a leader vertex v in a wave i, then any leader vertex v′ committed by any honest replica p in a future wave has a path to v. Proof. Let r j denote the j-th round relative to the considered wave. In the standard process, a leader vl of wave i is eligible for commitment if it is observed by at least f + 1 vertices at

Theorem 5. Every transaction issued by a correct client is eventually committed. 18

𝑟

1

1

1

1

𝑟

1

2

𝑟

𝑟

𝑟

2

3

𝑟

𝑟

3

1

1

1

1

1

2

2

1

2

2

(a) Rigid data integration.

1

𝑟

1

𝑟

𝑟

𝑟

2

𝑡𝑥 2 𝑡𝑥

𝑡𝑥 𝑡𝑥 𝑡𝑥 𝑡𝑥

2

2 𝑡𝑥

𝑡𝑥

𝑡𝑥

𝑡𝑥 3

𝑟

and its PVA, they can include the Tblock digest in their own vertices. For example, vertex Blue 3 incorporates two orange Tblock s into the DAG. Without this decoupled design, these Tblock s would have to wait until Replica 3 issues its designated vertex (Orange 3) before entering the DAG. In WAN settings, if Orange 3 is delayed by transient network fluctuations, the Tblock s incur substantial queuing delay. With our flexible construction, they join the DAG as soon as they are authenticated, reducing the chance of excessive delays caused by straggling replicas or unstable networks.

3

1

1

1

𝑡𝑥

2

𝑡𝑥

2

(b) Flexible data allocation.

Figure 12: Flexible data structure in M ANTA.

10

10 Proof of Verifiable Availability (PVA). The replica broadcasts Tblock to all other replicas, and replicas vote to acknowledge delivery (ACKs). f + 1 ACKs constitute a PVA that guarantees that Tblock has been delivered by at least one honest replica. If a replica receives Tblock and its PVA, the replica can include the Tblock in its vertex (by including the digest and PVA of the Tblock ). By using PVA, if a vertex contains valid PVAs for each referenced Tblock , it can be voted for in the RBC phase without waiting for Tblock contents. All missing Tblock can be fetched in the background.

Proof. Lemma 6 ensures that at least f + 1 vertices satisfy the commitment condition. When the flexible coin is employed, its prerequisite is that a replica has already locally observed at least τcand vertices from the first round that meet the commitment criteria; thus, committable vertices are guaranteed to exist. While τcand can be configured based on the system’s optimism, any τcand ≥ 1 is sufficient to guarantee liveness. This completes the proof.

D

Optimizations

Reliable Broadcast (RBC). In M ANTA, vertices reference the certified vertex from the preceding round. Each replica proposes and certifies at most one candidate per round. To certify a vertex, a replica follows a simplified RBC:

M ANTA introduces a flexible DAG growth mechanism to provide significant latency advantages in heterogeneous networks. Beyond this, however, high network heterogeneity further exacerbates other inherent inefficiencies in traditional DAG-based BFT designs. Specifically, inconsistent replica speeds often cause slower replicas to block faster ones, leading to substantial bandwidth underutilization. Furthermore, as illustrated in Fig. 12a, transactions not promptly included in block 2 must wait for the subsequent proposal block 3, which increases queuing delays. While the flexible growth mechanism alleviates these issues by relaxing round advancement, a more fundamental solution is required to eliminate these barriers. To this end, we propose a flexible data structure specifically tailored for heterogeneous environments, which further decouples transaction dissemination from consensus metadata. The data structure is categorized into two types:

1. To initiate the broadcast, a replica constructs and signs a vertex v as its proposal. This vertex incorporates two key components: (1) a collection of Tblock digests along with their corresponding PVA harvested from the local mempool, and (2) several vertex certificates from preceding rounds that serve as boost or progress edges. 2. Upon receiving a vertex from another peer, a replica first performs an equivocation check to ensure it is the first proposal received from that specific sender in the current round; if it is not, the vertex is discarded. If valid, the replica further verifies the included PVAs. Once the vertex passes all checks, the replica broadcasts a signed vote. 3. The proposer of vertex v waits until it collects n − f votes for v, aggregates them into a vertex certificate, and then broadcasts this certificate to all replicas. Finally, a replica formally incorporates v into its local DAG once it receives either the certificate for v or at least 2 f + 1 votes for v, provided that all certificates referenced by v are already present in its local storage.

Tblock : Transaction Blocks, represented as squares in Fig. 12b, contain the raw transaction data and are disseminated via best-effort broadcast. Vertex: Represented as circles in Fig. 12b, these contain the digest of a Tblock and its Proof of Verifiable Availability (PVA), disseminated via Byzantine Reliable Broadcast (RBC). This design improves bandwidth utilization across replicas. A Tblock can be proposed immediately after broadcast, without waiting for the next vertex window or a designated proposer. To illustrate, consider a transaction arriving at Replica 3 (highlighted in orange in Fig. 12). Replica 3 packages it into a Tblock and broadcasts it. After collecting f + 1 acknowledgments (ACKs), it aggregates them into a PVA and redisseminates it. Once other replicas receive both the Tblock

E Performance under Heterogeneous Network Modern distributed systems, especially blockchains, operate over highly heterogeneous wide-area networks (WANs), where geographically distributed nodes experience diverse latencies, bandwidth asymmetries, and transient workload fluctuations. Prior studies [7, 11] show that partially synchronous 19

15.0

Latency (s)

12.5

livery assumptions. This challenge has motivated a line of asynchronous DAG-based BFT protocols [10,15], which seek stronger robustness while retaining high performance. To further evaluate this robustness, we compare a representative asynchronous protocol (Tusk) with a partially synchronous protocol (Autobahn) under highly heterogeneous conditions. We inject large communication delays between selected node clusters to emulate partition-like WAN environments. Fig. 13 shows that Tusk exhibits a moderate throughput drop of about 13% and a 4.5× increase in average latency. By contrast, Autobahn maintains similar throughput, but its latency rises far more sharply, by over 30× on average. These results highlight the stronger robustness of asynchronous designs under highly heterogeneous WAN conditions.

Tusk (No Network Partition) Tusk (Network Partition) Autobahn (No Network Partition) Autobahn (Network Partition)

10.0 7.5 5.0 2.5 0.0 25

50

75

100

125

150

175

Throughput (KTps)

200

225

Figure 13: Asynchronous vs. partially synchronous DAGbased BFT under partition WAN conditions. BFT protocols can suffer severe latency inflation or stalled progress when network conditions deviate from timely de-

20

Related documents

• MANTA: Unlocking DAG Flexibility in Asynchronous BFT#1457573
• Hydrozoan: Latency-Adaptive DAG Consensus under Mixed Byzantine and Crash Faults#1061825
• Hydrozoan: Latency-Adaptive DAG Consensus under Mixed Byzantine and Crash Faults#1043024
• RW-LoRA: Communication-Efficient Decentralized LoRA Fine-Tuning via Random Walks#819555
• RW-LoRA: Communication-Efficient Decentralized LoRA Fine-Tuning via Random Walks#809559