Pangolin: Efficient DAG-based BFT State-Machine Replication with TEE-Accelerated Commitment

arXiv:2610.26295v1 [cs.DC] 19 Oct 2026

Pangolin: Efficient DAG-based BFT State-Machine Replication with TEE-Accelerated Commitment Paul Franke-Bergmann

Maya Kuhlmann

Alexander Heß

paul.bergmann@fau.de Friedrich-Alexander-Universität Erlangen-Nürnberg Erlangen, Germany

maya.kuhlmann@student.kit.edu Karlsruhe Institute of Technology (KIT) Karlsruhe, Germany

alexander.hess@uni-ulm.de Ulm University Ulm, Germany

Marc Leinweber

Rüdiger Kapitza

Hannes Hartenstein

marc.leinweber@kit.edu Karlsruhe Institute of Technology (KIT) Karlsruhe, Germany

ruediger.kapitza@fau.de Friedrich-Alexander-Universität Erlangen-Nürnberg Erlangen, Germany

hannes.hartenstein@kit.edu Karlsruhe Institute of Technology (KIT) Karlsruhe, Germany

Franz J. Hauck

Christian Berger

franz.hauck@uni-ulm.de Ulm University Ulm, Germany

christian.g.berger@fau.de Friedrich-Alexander-Universität Erlangen-Nürnberg Erlangen, Germany

Abstract Currently many Byzantine fault-tolerant (BFT) protocols use directed acyclic graphs (DAGs) to let replicas propose blocks of requests in parallel for improved throughput. Yet, the existing DAG-based designs mainly consider the atomicbroadcast layer: They typically do not describe an efficient client interaction layer, their garbage collection is either unspecified or relies on trusted external storage, and the lowest-latency designs rely on timing assumptions that may be violated in geo-distributed deployments. In this paper, we propose the Pangolin protocol: It introduces a novel low-latency DAGs-based atomic broadcast layer and completes it into an efficient state-machine replication (SMR) framework. To preserve system throughput, clients issue requests to a single replica and verify replies efficiently via compact execution proofs. Furthermore, Pangolin introduces a new garbage-collection scheme for DAGs which bounds memory usage even under full asynchrony. Pangolin leverages trusted execution environments to tolerate 𝑓 Byzantine faults with only 𝑛 ≥ 2𝑓 + 1 replicas and accelerates vertex commitments significantly: Broadcasting certified vertices requires only a single communication step, and commit rules are refined to commit both frequently and early without revealing the coin-elected anchor. This way, Pangolin overtakes the fastest partially synchronous DAG protocols while being live under asynchrony: In our evaluation, Pangolin achieves an average 1.27× (up to 1.52×) latency speedup over Mysticeti. Keywords: Byzantine Fault Tolerance, State-Machine Replication, Directed Acyclic Graphs, Trusted Execution, Consensus, Low-Latency, Scalability, Efficiency, Geo-Replication

You can check out a visualization of the Pangolin protocol here: https:// pangolin-protocol.netlify.app!

1

Introduction

Byzantine fault-tolerant (BFT) state-machine replication (SMR) provides clients with the illusion of a single, correct service even if an adversary controls up to 𝑓 out of 𝑛 replicas [20, 48, 57]. Moreover, BFT SMR is used in intrusion-tolerant systems such as firewalls [35, 36] and critical infrastructure [8, 14, 47], and most prominently distributed ledgers [7, 9, 11, 16, 37, 39, 53, 72]. To support generic services, BFT SMR protocols must provide two fundamental guarantees [20]: safety, which ensures that clients observe the replicated service as a centralized implementation that executes operations invoked by clients, and liveness, which guarantees clients eventually receive valid responses even in the presence of faults. Building correct BFT SMR systems is inherently difficult: agreement on a total order of requests, client-replica interaction and garbage collection must work correctly together [31]. Solving scalability and the rise of DAG BFT protocols. Traditional BFT SMR relied on a dedicated leader and coupled request dissemination with request ordering [3, 13, 20, 21, 22, 23, 40, 44, 69]. As the number of replicas 𝑛 grows, the leader’s bandwidth is increasingly exhausted by forwarding request data, and becomes the dominating bottleneck for scalability [53, 65, 25]. To overcome the leader bottleneck, a recent line of works proposes BFT protocols based on directed acyclic graphs (DAGs) [9, 25, 63, 64, 43, 60, 54]. Rather than routing all requests through a single leader, these

protocols achieve scalability by decoupling dissemination from ordering: All replicas can propose blocks of client requests in parallel, referencing previously seen blocks to form a DAG that encodes causal relationships [25, 45]. The DAG induces a partial order on requests. Subsequently, the total order is derived by selecting shared anchor blocks (e.g., randomly, using a common coin) and then applying deterministic topological sorting with the anchor as starting point [45]. This parallelism allows DAG-based BFT protocols to achieve high throughput, and has driven their adoption in major blockchain platforms such as Aptos [6, 63] and Sui [9, 52], with both combined over $880M total value locked [29, 30].

While they seem like isolated concerns, these three gaps – client interaction, garbage collection and low latency under asynchrony – share one root cause: existing DAG protocols stop at the atomic-broadcast layer and never close the loop into full state-machine replication. We therefore treat them as related and present a DAG-based BFT protocol that provides complete SMR: parallel atomic broadcast, efficient client interaction, garbage collection with bounded memory, and a TEE-accelerated commit path under full asynchrony. Completing DAG-based BFT towards SMR: Pangolin. To address these challenges, we propose Pangolin, a DAGbased BFT protocol designed explicitly as a complete SMR system. To make interactions with clients more efficient, Pangolin introduces a client-handler mechanism that exploits threshold signatures to preserve the throughput benefits of parallel request dissemination and satisfies SMR execution guarantees: The client validates a correctness proof of the execution result and enjoys exactly-once semantics. Furthermore, Pangolin presents a practical garbage-collection scheme that bounds resource usage under full asynchrony. Pangolin also shows that TEEs not only improve the resilience bound to 𝑛 ≥ 2𝑓 + 1 but can also enable a substantially faster commit path in a DAG protocol. On average, Pangolin achieves latency gains of 1.27× over Mysticeti, the fastest partially synchronous DAG protocol, and 1.64× over Fides [70], an asynchronous TEE-based DAG BFT protocol. Depending on the deployment, the gain over Mysticeti reaches up to 1.52×. To the best of our knowledge, this makes Pangolin the lowest-latency DAG BFT protocol to date. Our contributions are as follows:

Completing atomic broadcast to SMR: The challenges. Despite their adoption in large-scale blockchain deployments, existing DAG-based designs primarily address the Byzantine atomic broadcast (BAB) problem [9, 25, 45, 63, 64, 68] — making all correct replicas agree on the same total order of requests — while further components required for complete SMR received considerably less attention. We identify three concrete challenges that existing protocols fail to address: Efficient client-replica interaction. Existing DAG-based SMR protocols do not specify a client interaction layer. Their evaluations typically measure latency only until the moment the replicas locally commit the request, before the client has received any reply or can tell the request has completed [9, 25, 64]. In classical BFT SMR systems, clients wait for 𝑓 + 1 matching replies to ensure at least one correct replica has executed the request [20]. Clients might also need to broadcast requests to prevent censorship [20, 31]. Naively applying this approach to DAG-based protocols reduces the effective throughput by up to 93%, as we show in § 2.1. Garbage Collection. Current DAG protocols do not bound memory usage within the BFT fault model. Many protocols do not specify garbage collection (GC) at all [9, 45, 63, 68], while those that do offload old vertices to external storage such as Amazon S3, thereby introducing a trusted component outside the BFT fault model [25, 64]. Moreover, their GC mechanism remains incomplete as the memory usage for buffering vertices is unbounded during periods of asynchrony (see § 2.2). However, the underlying problem is fundamental: Recovering old vertices requires either external storage or complete SMR (this work). Low latency under asynchrony and (2𝑓 + 1)-resilience. Obtaining low latency is a key challenge for asynchronous DAG-based protocols [43, 70]. To avoid the problem, some approaches adopt partial synchrony to shorten their commit paths [9, 63, 64]. However, partial synchrony requires careful timeout configuration that can be violated under adversarial network conditions [67]. Pangolin explores an alternative path, in which it leverages trusted execution environments (TEEs) to improve both latency and resilience of the protocol while still operating in full asynchrony.

• Low latency and high resilience – We show how (2𝑓 + 1)-resilience and low latency without relying on timing assumptions can be achieved using TEEs (§ 4.3 – § 4.4). • Completing BAB to SMR – We design and implement an efficient client interaction mechanism for DAG-based BFT to preserve benefits of parallel request dissemination while fulfilling SMR guarantees (§ 4.5). • GC under asynchrony – We introduce a novel garbage collection scheme that bounds resource usage under full asynchrony without any external storage (§ 4.6). • Extensive Evaluation – We conduct experiments that show that Pangolin commits up to 1.52× faster than the fastest DAG-based protocols and can maintain high throughput (92–97% of the maximum possible throughput) with full BFT SMR guarantees for clients.

2

Analysis of Existing Approaches

Despite achieving substantial throughput, existing DAGbased BFT protocols are designed around the ByzantineAtomic-Broadcast (BAB) layer and translating them into complete SMR systems raises three practical challenges. 2

Throughput [kOp/s]

120 90

72.5

60 30

to contact a possibly distant replica [65]. Pangolin’s mechanisms instead let clients choose the contact replica.

No Client Guarantee Classical BFT Client

120

13

2.2

GC in DAG-based protocols requires bounding memory usage while ideally providing fairness by ensuring that all correct replicas’ vertices are eventually totally ordered.

5

0 20 40 Number of replicas 𝑛

Dilemma between fairness and garbage collection. To achieve ideal fairness, no unordered vertex can be deleted from the storage of all replicas because this vertex would never be totally ordered. At the same time, DAG-based protocols do not provide an upper bound on the time required to order a vertex. While, in expectation, it does not take more than a fixed number of rounds to order some vertices, slow replicas’ vertices can take longer and can even be excluded under network partitions. Therefore, a garbage-collection algorithm must either delete unordered vertices and continue, or wait for the network partition to pass. Both options hinder fairness, as slow replicas are disadvantaged either by having their vertices deleted or by being forced to wait for better network conditions before proposing new ones. Thus, providing fairness in asynchrony is effectively impossible. Narwhal decides to remove unordered vertices from the DAG and thereby accepts fairness violations, which can occur even in a synchronous network [64, Sec. 1, 4th paragraph]. Bullshark [64] addresses Narwhal’s fairness problems by relying on weak edges combined with a timestamp-based garbagecollection scheme that guarantees timely fairness (fairness after global stabilization time (GST) [32]).

Figure 1. Sustained throughput of Narwhal/Tusk [25] with a baseline client without guarantees and a classical client that sends requests to all replicas and waits for 𝑓 + 1 replies.

2.1

Garbage Collection

Efficient Client Interaction & SMR Guarantees

Practical SMR systems must provide liveness, i.e., clients eventually receive replies to their requests [19]. However, many recent DAG-based designs focus solely on BAB. Their evaluations typically observe a request only from the time of submission until it is locally committed by the replicas [9, 25, 64], when the client has not yet received a reply. In classical BFT SMR, clients wait for 𝑓 + 1 matching replies, so that at least one correct replica confirms the result, and clients broadcast requests, directly or as a fallback, to prevent censorship [20, 31, 55]. Replicas cannot easily tell apart a correct client evading censorship from a spamming Byzantine one, so without intervention replicas include every request they receive. Since every replica proposes blocks, this allows the same request to be included up to 𝑛 times, each copy consuming ordering capacity [65].

Garbage-collection limitations in existing works. DAGbased protocols have the advantage of decoupling request dissemination (reliable broadcast) from ordering (atomic broadcast). However, while DAG-based atomic broadcasts are strictly round-based, reliable broadcasts are typically not. Consequently, under unfortunate network conditions, the reliable broadcast might deliver vertices for future rounds that a slow replica has not yet reached.1 Neither Narwhal’s [25] nor Bullshark’s [64] GC addresses the memory usage of these vertices that are stored in the so-called vertex buffer, which makes their garbage collection mechanism unsafe in the general case.2 Additionally, both algorithms offload old (“garbage collected”) vertices to external storage such as Amazon S3 since memory must be freed, but old vertices may still be required to support other replicas during the reliable broadcast, a mechanism referred to as backfilling. Backfilling from external storage implicitly introduces a trusted third party that lies outside the BFT failure model. The last two problems are inherent: Bounding the vertex buffer requires discarding vertices whose causal history is still incomplete.

Client interaction significantly impacts throughput. Fig. 1 measures the sustainable throughput of Narwhal [25] with a classical client (requests to all replicas, 𝑓 + 1 matching replies). Only 𝑓 + 1 designated replicas include each request, the minimum for one to be correct. Compared to a baseline client (one replica, one reply, no guarantees), the classical client loses 88–93% of throughput (§ 5.2). Client interaction in Pangolin’s design. Pangolin retains high throughput, by making a single contact replica sufficient while providing full SMR guarantees (§ 4.5). The client waits for a single reply from its contact replica, which carries a threshold signature [15] that certifies 𝑓 + 1 replicas have executed the request. If no reply arrives, the client resubmits to another replica, which answers immediately if the request was already executed (kept in a response storage), or eventually re-injects it otherwise. A round-based cooldown keeps a spamming client from repeated inclusion this way, while still letting a censored one eventually get through. Prior work also used threshold signatures to cut client communication, but falls back to broadcasting if no timely response arrives [39, 42]. Mir-BFT avoids multiple inclusions via consistent hashing, at the cost of forcing clients

1 This also affects the partially synchronous model (before GST is reached). 2 An explicit attack against the above protocols can be found in Appendix B.4.

3

2,000 Latency [ms]

Since all correct replicas may have discarded the same vertices, recovering them later requires either external storage or a complete SMR approach. Pangolin’s SMR approach to garbage collection. Pangolin addresses these challenges by using an SMR execution layer instead of treating GC as a pure DAG-level concern. First, we delete and thereby ignore the transactions of unordered vertices not when a DAG round is deemed old by some timestamp heuristic, but after a fixed number of DAG-rounds, which bounds memory consumption and provides timely fairness. Second, Pangolin employs the SMR approach to periodically build checkpoints, which are certified snapshots of the replicated state that are signed by a quorum of replicas. A vertex can be safely deleted once a stable checkpoint 𝑐𝑘𝑝𝑡𝑖 covering the execution or ignorance of its transactions exists, as any replica that missed the vertex recovers by performing a state transfer to the most recent stable checkpoint 𝑐𝑘𝑝𝑡 𝑗 , 𝑗 ≥ 𝑖, rather than relying on backfilling. Third, to prevent unbounded growth of the vertex buffer during asynchrony, Pangolin enforces a bounded receiving window, which can discard all incoming vertices whose rounds fall too far ahead of the local progress. Importantly, if such a vertex is later needed, the same state-transfer mechanism covers its content. As a result, both the DAG and the vertex buffer are bounded at all times, even under full asynchrony, with the timely fairness [64] guarantee preserved and without the need for external storage outside the BFT failure model.

asynchronous partially synchronous

1,500 1,000 500 0

l r 5 k + ide rwha lshar ahi- oal+ l a M Sh N Bu ahiM

GR DA

es eti in Fid ystic ngol M Pa

Figure 2. Mean block decision latency across DAG-based BFT protocols. Although Pangolin is fully asynchronous, it is even faster than the partially synchronous Mysticeti. Pangolin attacks latency with TEEs. With TEEs Pangolin achieves the (𝑛 ≥ 2𝑓 + 1)-resilience bound, but TEEs can also reduce the latency of atomic broadcast: First, as TEEs can prevent equivocation, they can be used to realize a reliable broadcast primitive with fewer communication steps. Second, the TEE assumption enables proportionally smaller quorums (of size ⌈ 𝑛+1 2 ⌉) which can be collected faster in a WAN than the usual Byzantine dissemination quorums. Third, a TEE-based common coin can be used to check if commit rules apply earlier without revealing the randomly selected anchor. We show how TEEs reduce latency in the asynchronous network model. Moreover, in our evaluation Pangolin is faster than the partially synchronous Mysticeti, the fastest DAG protocol known to us [9]. Fig. 2 shows Pangolin overtakes Mysticeti with a latency of 284 ms vs. 372 ms at 𝑛 = 13 (and using the same 13 regions that the evaluation setup of Mysticeti employs [9]). The details on our evaluation method for Fig. 2 are provided in Sect. 5.4 and App. C.4.

2.3 Asynchrony, Low Latency and (2𝑓 + 1)-Resilience Early asynchronous designs such as DAG-Rider [45] select leaders (anchor vertices) retrospectively by requiring a shared random coin to circumvent the impossibility of deterministic, fault-tolerant consensus under asynchrony [34].

3

System Model

Adversary model. We consider a system of 𝑛 replicas, of which a static adversary may control up to 𝑓 replicas chosen before execution and where 𝑛 ≥ 2𝑓 + 1. Furthermore, corrupted replicas are Byzantine: They may deviate from the protocol and coordinate with one another. Replicas communicate over authenticated perfect point-to-point links [17]. The adversary cannot break cryptographic primitives such as employed hash functions and digital signature algorithms.

Low-latency DAG protocols. After Narwhal [25], many research works aimed to reduce DAG protocol commit latency [64, 7, 60, 54, 46, 9, 43], often assuming partial synchrony [32], which sidesteps this impossibility by bounding message delays after GST and allows pre-defined leaders [64, 7, 60, 54, 9]. Mysticeti [9] achieves fast commit latency by using a novel commit rule and an uncertified DAG, an idea that Mahi-Mahi-5 transfers to the asynchronous network setting [43]. Mahi-Mahi-5 needs additional rounds compared to Mysticeti at the cost of slightly increased commit latency. Partial synchrony is a widely used assumption in practice [20, 72], but it requires careful timeout selection and misconfigured or temporarily violated timeouts can slow or stall progress under adversarial network conditions [67]. We show that the trade-off between low latency and a partial synchrony assumption is not fundamental: Asynchronous DAG-based protocols can be accelerated by cleverly leveraging TEEs in the protocol design, while at the same time offering 𝑛 ≥ 2𝑓 + 1 resilience.

Network model. The network is asynchronous: messages may be reordered and delayed, but not dropped. We make no timing assumptions and place no bounds on message delays. TEE model. We assume each replica is equipped with an enclave-based TEE that provides integrity, confidentiality, and remote attestation. Table 1 shows the abstract interface of our assumed TEE, its enclave state and the guarantees that are given for the BFT protocol execution. TEE assumptions. We assume the TEE fails only by crashing. Upon a crash, its internal state is lost and is not recoverable. The untrusted host, including the operating system 4

Trusted state

Guarantee

setup() → (𝑝𝑘 , 𝑠𝑘 ), 𝑐𝑠

key pair, coin seed

attested identity; coin agreement via the shared seed

enclave_sign(𝑣) →𝜎 | ⊥ check_commit(𝑣) →𝑢 | ⊥

𝑟 max

sup, CPRNG

certify, fetch, or forward checkpoints

Replica-Replica Channels

Method

non-equivocation: at most one well-formed vertex per round, rounds are strictly increasing commit-gated coin reveal: the wave’s anchor is disclosed when the direct commit rule first holds, which requires sufficient support (sup)

SMR Framework

SMR Execution Manager

Checkpoint Manager checkpoint

State Transfer

§ 4.6

ClientHandler

§ 4.5

Execution Proofs Client Management

requests

Atomic Broadcast

invoke

results

signature share exchange

Garbage Collection

§ 4.6

TEE-RB

§ 4.3

Table 1. Pangolin’s abstract TEE interface. Each method guards a piece of enclave state and provides one guarantee.

GC

Commit Rules

§ 4.4

check

Bounded

Vertex Creation

Vertex Buffer

insert

DAG § 4.2

deliver

request

Client

commit

TEE-Coin § 4.3

GC

broadcast response

§ 4.4 4.5

Execution & State Management

Backfilling vertices

Replica-Replica Channels

Figure 3. Architecture of Pangolin. and application layer, could be under adversary control: it may omit or delay messages to and from the enclave, but cannot read or tamper with its internal state. We assume the TEE hardware itself is not compromised. Furthermore, side-channel attacks and hardware-level exploits are outside our threat model.

also provide a visualization of Pangolin that may help in understanding its commit rules and comparing it with other DAG protocols3 . 4.1

Threshold signatures. A (𝑡, 𝑛)-threshold signature scheme involves 𝑛 participants, whereby each participant 𝑖 holds a private key share 𝑠𝑘𝑖 , and any subset of 𝑡 participants can collaborate to create a threshold signature, which is verifiable using a single public key. Previous work has primarily used RSA-based threshold signatures [4, 55, 58], or BLS-based threshold signatures [15], which are favored in recent systems [39, 42, 53] due to their shorter signatures. TEE-based threshold signatures. In contrast to previous work, Pangolin builds on the SpliTEE [41] approach, which utilizes a trusted execution environment to produce efficient threshold signatures. We make use of the common key variant: A common EdDSA key-pair [12] is encapsulated by the TEEs of all participating nodes, and the public key is used as the common verification key. In addition, each node holds an individual EdDSA key pair, whose public key is known in advance by the TEEs. A TEE creates a threshold signature for some data 𝑑 using the common private key, if it is provided with valid signature shares for 𝑑 from 𝑡 distinct nodes.

4

Architectural Overview

Fig. 3 illustrates Pangolin at a single replica. Clients submit their requests to a contact replica of their choice, typically selecting one that is geographically close. The client handler (§ 4.5) receives these requests, buffers them, and forwards them to the atomic broadcast (AB) layer, which periodically includes them in a newly created vertex, which is reliably broadcast to all replicas as soon as a new DAG-round can begin (details follow in § 4.4). When the reliable broadcast layer delivers a vertex, it is placed in the vertex buffer; If it corresponds to the current round and its causal history is available, it is inserted into the DAG. If some references to a delivered vertex are missing, backfilling is used to request the missing dependencies directly from other replicas. Vertex insertion may trigger an evaluation of the commit rules (which we describe in § 4.4), which may commit several vertices at once. The resulting sequence of committed vertices is then passed from the AB layer to the execution and state management layer, where the requests contained in these vertices are filtered for duplicates before execution. After execution, responses are passed back to the client handler, which attaches compact execution proofs based on threshold signatures (§ 4.5) and stores the most recent response for each client. Whenever a replica acts as a client’s contact, it responds directly to that client. In addition, the SMR execution manager periodically creates checkpoints that drive the garbage-collection scheme, enabling vertices to be removed from both the vertex buffer and the DAG (see § 4.6). To become stable, checkpoints need to be certified by 𝑓 + 1 replicas by collecting threshold signature shares and forming a valid (𝑓 + 1)-threshold signature. Stable checkpoints can then be forwarded to stale replicas, allowing them to recover

Design of Pangolin

Pangolin’s design follows our objectives of leaderless operation, low-latency commitment, and efficient client handling to maintain high SMR throughput. These goals are achieved by composing several components into a complete SMR system: two TEE-based building blocks (a reliable broadcast and a common coin (§ 4.3)), a novel, asynchronous DAGbased AB-layer that leverages them for fast vertex commitment (§ 4.4), a client handler that supports load-balancing of clients across several replicas via compact execution proofs (§ 4.5), and a checkpoint-driven garbage collection scheme that bounds memory usage under full asynchrony (§ 4.6). We

3 See https://pangolin-protocol.netlify.app/ to visualize Pangolin

5

by installing the most recent application state and invoking their garbage collection routine. 4.2

DAG Construction

In this subsection, we briefly recap the core concepts of DAG construction and explain how they are applied in Pangolin.

𝒑1

𝒑2

𝒑2

𝒑3

𝒑3

𝒑4

Vertices, rounds, and edges. All replicas propose vertices in parallel, each containing a payload of client requests and references to previous vertices. Each replica maintains a local view of the DAG as a two-dimensional array indexed by round and producer. An example local view is shown in Fig. 6. A vertex 𝑣 has a round 𝑣.𝑟 ∈ N, a producer 𝑣.𝑝 ∈ 𝑃, a payload 𝑣.block of client requests, a signature 𝑣.𝜎, and a set of edges 𝑣 .edges that reference vertices from previous rounds. Strong edges only reference one vertex per producer from the last round 𝑣 .𝑟 −1 that the creator of 𝑣 observed, while weak edges include vertices from two or more rounds in the past.

𝑛 2 vertex

𝑟 𝑛 2 vertex

𝑛 2 ack

𝑟 +1

𝑛 2 cert

𝑟 (a) Narwhal: 3𝑛 2

𝑟 +1 (b) Pangolin: 𝑛 2

Figure 4. Common-case communication of one broadcast round in the DAG, shown for 𝑓 = 1. Black lines delimit broadcast rounds, blue lines the communication steps within a round and an arrow’s color is the originator of its payload. Narwhal’s quorum-based reliable broadcast needs three steps and 3𝑛 2 messages to complete a round, certifying 𝑛 vertices whereas Pangolin’s TEE-based reliable broadcast finishes a broadcast round in a single step with 𝑛 2 messages only.

Round advancement. Edges capture causal dependencies and act as votes for the referenced vertices. Because a TEE never signs more than one vertex per (𝑝, 𝑟 )-pair, Byzantine broadcasters cannot equivocate. Two correct replicas therefore never observe conflicting vertices at any (𝑝, 𝑟 ). A replica advances from round 𝑟 to 𝑟 +1 once a quorum of ⌈ 𝑛+1 2 ⌉ vertices in round 𝑟 is in its local DAG, including its own. The next vertex it produces will reference this quorum as edges.

highest round it has signed a vertex for so far, and refuses to sign a vertex if its round 𝑣 .𝑟 is not higher than 𝑟𝑚𝑎𝑥 . Thus, every replica, correct or faulty, can receive at most one valid signature per round, and the rounds of the signed vertices are strictly monotonically increasing. As a consequence, two correct replicas never see conflicting vertices for the same (𝑝𝑟𝑜𝑑𝑢𝑐𝑒𝑟, 𝑟𝑜𝑢𝑛𝑑)-slot, and the misbehavior a faulty broadcaster can cause is reduced from Byzantine to just omission. From RB delivery to DAG insertion. Verifying a vertex 𝑣 does not make it immediately usable, because the commit rules (see § 4.4) reason over paths, so 𝑣 can be included in the DAG only when its causal history is available. Thus, a replica puts a verified vertex 𝑣 into the vertex buffer (Alg. 3, l. 5) and inserts it in the DAG once (1) it has reached round 𝑣 .𝑟 and (2) every vertex referenced by 𝑣 .edges is either present in the DAG or already stale (Alg. 1, ll. 10–12). Vertices of rounds ahead of the local round can arrive at any time and remain buffered until they become insertable. Note that the insertion rule is applied transitively, so the ancestry of an inserted vertex must be part of the DAG down to the garbagecollection boundary. We detail how Pangolin’s garbage collection scheme can bound memory in § 4.6. Backfilling. When a replica receives a vertex 𝑣 whose referenced vertices are neither in the DAG nor in the vertex buffer, then it requests the missing vertices from other replicas (Alg. 3, l. 3 and ll. 14–17). Pangolin adopts a pull-based recovery like Narwhal [25]: Retrieving the history of a vertex only costs extra messages when a vertex overtakes it or when omissions occur, so the common case is still a single communication step. In case a requested vertex was already garbage collected, then the request is replied to with a state transfer (Alg. 3, ll. 9–10) that updates the asking replica to a state in which the vertex is no longer needed. Because a vertex can be garbage collected before every correct replica has added it, our instantiation does not provide RB-Totality

Waves, anchors and slots. Rounds are grouped into waves of four consecutive rounds and round (𝑤, 𝑘) ≜ 4𝑤 + 𝑘 − 1 denotes the 𝑘-th round of wave 𝑤. For every wave 𝑤, the common coin toss randomly elects a single anchor replica. In the DAGRider protocol [45], the anchor slot of wave 𝑤 is then only the round (𝑤, 1)-vertex produced by the anchor replica. In contrast, Pangolin uses multiple anchor slots per wave. The vertices the anchor replica produces in 𝑤’s first three rounds – (𝑤, 1), (𝑤, 2), (𝑤, 3) – are the anchor slots. 4.3

𝒑1

Instantiation of the Building Blocks

Next, we briefly explain how the two main building blocks of Pangolin can be instantiated with the assistance of a TEE and how the TEE support helps to improve latency. 4.3.1 The TEE-based Reliable Broadcast. The RB-layer of Pangolin broadcasts one vertex per replica and round. We instantiate it as a Byzantine Consistent Broadcast [17] that is completed by a backfilling mechanism: The enclave prevents equivocation, so that dissemination itself only costs a single communication step, and causal history that a replica is missing is fetched reactively from others. Pangolin integrates the TEE-based RB from [49, § 4.2]. We compare Pangolin’s communication pattern with the quorum-based certification of Narwhal [25] in Figure 4. Ensuring non-equivocation via the enclave. Before broadcasting a vertex 𝑣, a replica 𝑝𝑖 invokes the enclave to get a signature 𝑣 .𝜎 (Alg. 4, ll. 5–11). The enclave guards 𝑟𝑚𝑎𝑥 , the 6

TEE enclave anchor hidden 𝑝 ← CPRNG (𝑤 )

in its unrestricted form at the broadcast layer. Instead, we prove the weaker property that a vertex added by one correct replica is eventually added by every correct replica or becomes irrelevant to it (Theorem B.7), and show in § 4.6 that this suffices for the atomic broadcast layer.

anchor revealed due to commit of 𝑝 2

anchor revealed due to next wave

𝑝1 𝑝2

1 𝑣𝑤

𝑝3 (𝑤, 1)

4.3.2 The TEE-assisted Common Coin. The coin has one task: Elect one anchor replica in every wave and let all correct replicas observe the same result, yet the result needs to be unpredictable to the adversary and disclosed only after the wave has passed or an anchor slot of that wave can be committed. Commonly, asynchronous protocols use a coin based on threshold signatures that is revealed after the wave has passed, which requires both an initial distributed key setup and an exchange of signature shares per coin toss. Because Pangolin already leverages the TEE for the broadcast, we might as well use it to derive the coin from a cryptographically secure pseudo-random generator (CPRNG) that runs inside the enclave of each replica. Enclaves are seeded with the same value during setup (see Table 1), so each enclave outputs the same anchor for the same wave and thus replicas agree on it without a single message exchange.

(𝑤, 2) (𝑤, 3) (𝑤, 4) 1 ⌈ 𝑛+1 2 ⌉ support for 𝑣𝑤 ⇒ commit ⇒ 𝑝 2 revealed

(𝑤 + 1, 1)

Figure 5. Commit-gated disclosure of the common coin over one wave 𝑤. Each enclave computes the wave’s anchor replica from its CPRNG immediately, but withholds it until an anchor slot commits or the next wave begins. Inserting the ( ⌈ 𝑛+1 2 ⌉)-th vertex of round (𝑤, 2) that supports the anchor 1 fulfills the commit rule: Now the enclave returns the slot 𝑣 𝑤 anchor replica and unveils the coin results of decided waves. 4.4

DAG-based Consensus

Pangolin’s atomic broadcast layer is a DAG-based BAB in the lineage of DAGRider [45], but leverages the TEE to redesign DAGRider’s commit rules to improve latency. Committing in DAGRider. In DAGRider, a replica directly commits the anchor slot 𝑣 𝑤 of wave 𝑤 once its local DAG contains a quorum of vertices in round (𝑤, 4) with a strong path to 𝑣 𝑤 . It then retrospectively commits every earlier anchor reachable from 𝑣 𝑤 by a strong path, walking back from wave 𝑤−1 to the last decided wave. Earlier anchors are ordered first. By quorum intersection, an anchor that any replica directly committed in an earlier wave has a path to 𝑣 𝑤 and is ordered before it. Thus all correct replicas commit the same anchors in the same order.

Commit-gated disclosure. If an anchor replica is disclosed too early by the common coin, then an adversarial scheduler can prevent the anchor from being committed: The adversary would delay the anchor replica’s vertices so that they are not referenced by sufficiently many other replicas and then fail to collect the quorum support. For this reason, other asynchronous protocols hide the anchor replica until the corresponding wave has passed, implying that commits can be checked in the subsequent wave at the earliest. To prevent such delay, the TEE evaluates the commit rules itself: Once a replica inserts a vertex 𝑣 in the DAG, it invokes check_commit(𝑣) (Alg. 1, l. 13). The enclave verifies 𝑣 .𝜎, computes the anchor replica of wave 𝑣.𝑤 from the CPRNG without returning it, and tests for each of the wave’s three anchor slots whether 𝑣 supports that slot, either by referencing it directly or by referencing a vertex that already supports it (Alg. 4, ll. 12–20). The commit rules follow in § 4.4; here it is only relevant that the supporting vertices accumulate in the enclave state sup. Only when an anchor slot commits does the enclave return that slot and unveil it to the outside. At the latest, the anchor is revealed once the next wave starts.

Pangolin commit rules. Pangolin keeps DAGRider’s wave structure, but commits both more frequently and earlier, and exploits smaller quorums the TEE permits (𝑓 + 1 out of 𝑛 = 2𝑓 +1 or ⌈ 𝑛+1 2 ⌉ in general). Three things change. First, all three vertices of the anchor replica in rounds (𝑤, 1) − (𝑤, 3) 1 , 𝑣 2 , 𝑣 3 , so almost every round are potential anchor slots: 𝑣 𝑤 𝑤 𝑤 offers an opportunity to commit, instead of only one anchor slot per wave as in DAGRider. Second, the direct commit rule broadens the support window: an anchor slot (𝑤, 𝑘) is directly committed as soon as a quorum of ⌈ 𝑛+1 2 ⌉ vertices of any later round of the same wave have a path to it, not only the last round as in DAGRider. Support is counted round by round until this quorum is first reached. This improvement makes use of the commit-gated disclosure provided by the TEE to preserve liveness. Third, support is counted along all edges, strong and weak, and propagates transitively: A vertex supports an anchor slot if one of its edges references the anchor slot itself, or if it references any vertex already supporting it. Each change makes commitment easier to reach than in DAGRider, while preserving correctness (as we prove in the Appendix). If a new vertex completes the quorum for several slots of its wave at once, only the highest commits directly; the lower slots resolve retrospectively as described next.

Probing the enclave. One might think that since the method check_commit(𝑣) accepts any well-formed vertex, Byzantine replicas could probe their own enclave with candidate vertex sets to learn whether a slot is already committable, thereby trying to narrow down the anchor replica before the protocol commits it. In the Appendix, we prove in Lemma B.2 Hidden Common Coin that such a strategy is not useful to break liveness: The expected number of waves until a correct replica observes the direct commit rule to be fulfilled remains below two. 7

𝑓 +1 support in (𝑤, 2) 1 ⇒ direct commit of 𝑣 𝑤

vertices referenced by anchor slots. Vertices older than the GC offset are ignored during this ordering step and must be handled by the checkpointing scheme instead (§ 4.6).

commit path traverses a weak edge 3 (path, not strongPath) ⇒ retrospective commit of 𝑣 𝑤 1 𝑣 𝑤+1

𝑝1

2 𝑣 𝑤+1

3 𝑣 𝑤+1

Correctness. We sketch an intuition for safety and liveness here, while providing full proof in the Appendix. Two of the above changes could plausibly break safety: (1) Commits now originate from three anchor slots per wave instead of one, and (2) the support is counted along all edges of any later within-wave round instead of just the wave’s last round. Neither breaks the property safety relies on: any two ⌈ 𝑛+1 2 ⌉ ⌉ ≥ 𝑓 + quorums intersect, and since ⌈ 𝑛+1 1 replicas support 2 a direct commit of an anchor, every vertex after the support round must indirectly reference the anchor. Together with the self-reference that the enclave enforces, this yields anchor connectivity (Lemma B.1): Once an anchor slot is directly committed, every anchor slot that may be committed later (in this or a future wave) still has a path to it. Hence correct replicas make identical commit-or-skip decisions during the retrospective walk and deliver the same total order (see Theorem B.3). Liveness rests on the coin: Because the enclave reveals a wave anchor only after an anchor slot commits, an adversary probing check_commit() cannot prevent the commit and a correct replica observes the direct commit rule fulfilled after fewer than two waves in expectation (Lemma B.2).

𝑝2

𝑝3

1 𝑣𝑤

2 𝑣𝑤

3 𝑣𝑤

𝑘

1

2

3

4

1

2

wave 𝑤 ordered strong edge

3

4

wave 𝑤+1

direct commit weak edge

retrospective

not yet ordered

1 support quorum for 𝑣 𝑤

Figure 6. Pangolin’s commit rules on an example DAG of 𝑛 = 3 replicas (𝑓 = 1, quorum ⌈ 𝑛+1 2 ⌉ = 2) over two waves. Every vertex references ⌈ 𝑛+1 ⌉ vertices of the previous round, 2 always including its own predecessor (solid strong edges, the arrow pointing to the referenced older vertex); weak edges (dashed) point to further-back rounds. Each wave has three anchor slots produced by a single coin-elected replica in every round of the wave but the last (𝑝 3 in wave 𝑤, 𝑝 1 in wave 𝑤+1). Direct commit: an anchor is committed as soon as ⌈ 𝑛+1 2 ⌉ vertices of a later within-wave round have a path to it, and support is counted only until that quorum 1 already collects its ⌈ 𝑛+1 ⌉ support in the is first reached. 𝑣 𝑤 2 next round (𝑤, 2) (the two highlighted supporters), so the TEE uncovers the coin and commits it one round after it was proposed — the support need not reach the wave’s last 2 likewise commits in (𝑤, 3), as do all three slots of round. 𝑣 𝑤 3 ’s only later withinwave 𝑤+1. Retrospective commit: 𝑣 𝑤 wave round is (𝑤, 4), where fewer than ⌈ 𝑛+1 2 ⌉ vertices reach it, so it is not directly committed; it is committed retrospec1 tively when 𝑣 𝑤+1 commits, along a path that traverses the 1 3 . In contrast, DAGRider’s commit rules weak edge 𝑣 𝑤+1 →𝑣 𝑤 traverse only strong edges. A vertex is colored green once it lies in a committed leader’s causal history.

4.5

Client Interaction Model

Contact Replicas. A client sends its request to a single contact replica, which buffers it and includes it in the payload of its next vertex (𝑣.𝑏𝑙𝑜𝑐𝑘). However, a crashed contact replica might never propose the request and a Byzantine one could censor it. In both cases, the client receives no timely reply and re-issues its request to the next replica of its preference list of all 𝑛 ≥ 2𝑓 + 1 replicas (e.g., based on geographical proximity/latency [33]). As at most 𝑓 replicas are faulty, each faulty contact replica can delay a request, but not suppress it, so the order of the list is a latency choice rather than a correctness one and can be dynamically adjusted. Since a replica cannot tell such a failover from a spamming client (§ 2.1), replica 𝑝𝑖 applies a round-based cooldown: it rejects a request of client 𝑐 while a vertex of another replica from the last 𝜅 rounds carries a not-yet-ordered request of 𝑐. For censored clients, no such vertex exists, since their request was never included, and 𝜅 ensures that a vertex which is never ordered cannot block 𝑐 forever. Multi-inclusion nonetheless remains briefly possible, since concurrently proposed vertices may not yet reference each other; but as each round requires a quorum of vertices from the previous one, later vertices are quickly forced to (indirectly) reference every vertex already carrying the request, closing the window within a few rounds. Selecting 𝜅 thus trades off this residual multi-inclusion against how quickly a censored client can

Retrospective commits and total order. As in DAGRider, upon directly committing anchor slot (𝑤, 𝑘), the replica revisits all undecided anchor slots below it: First the lower-round slots of the same wave 𝑤, from (𝑤, 𝑘−1) down to (𝑤, 1), then the slots of earlier waves, down to the last decided anchor slot. If an anchor slot is present in the local DAG and reachable over a path from the most recently committed anchor, it is committed as well. Otherwise, the slot is skipped. Both outcomes are final because a decided slot is never revisited. This procedure creates a total order on all reachable anchor slots. The committed anchors are then delivered in ascending slot order, and each anchor deterministically delivers the vertices of its causal history that no earlier anchor has delivered, so all correct replicas can deterministically linearize all 8

𝑝1

2

𝜎 over ℎ𝑟 , 𝑓 +1 shares

3

to the root of the Merkle tree (𝜎, ℎ𝑖 , . . . , ℎ 𝑗 ) (Fig. 7(b)). A client verifies the proof in three steps: (1) It employs the received response to hash its own tuple (c, rid, request, response) into a leaf, then (2) re-computes the path in the Merkle tree from the leaf up to the root using the received sibling hashes (in the order given by the position in the batch), and (3) checks 𝜎 against the computed root with the common public key. If the client’s verification succeeds, the result is guaranteed to be correct, as at least one out of the 𝑓 +1 replicas that contributed to the threshold signature has to be benign.

ℎ𝑟

𝑝2 𝑝3

1

2

3

1 𝑣𝑤

2 𝑣𝑤

3 𝑣𝑤

3

(𝑤, 1)

(𝑤, 2)

(𝑤, 3)

(a) batches 2 anchor slots

ℎ 34

ℎ 12 ℎ1

ℎ2

ℎ3

ℎ4

proof: 𝜎 , ℎ 1 , ℎ 34 3 ’s batch (b) proof from 𝑣𝑤

Figure 7. From DAG commits to execution proofs, for 𝑛 = 3, 𝑓 = 1 and anchor replica 𝑝 2 . (a) Anchor slots carry a gold ring: Every anchor delivers the part of its causal history that no earlier anchor slot committed, so batches are disjoint. A vertex carries the number and color of the anchor that committed it. White means uncommitted. Edges along which vertices commit are gold and the remaining ones grey. Edges 3 ’s into later rounds are omitted. (b) The 𝑚 requests of 𝑣 𝑤 batch form the leaves ℎ𝑖 = hash(c, rid𝑖 , request𝑖 , response𝑖 ) of a Merkle tree whose root is certified by a threshold signature 𝜎. The client receives a response, and a proof (𝜎 and the shaded siblings on its path to the root, log2 𝑚 = 2 hashes).

Why no broadcast is needed. In Pangolin, a client whose contact replica is faulty never needs to broadcast its request, but can simply retry at another contact replica. If the re-issued request was already ordered (and executed), it is served from the response storage. Otherwise, the client keeps retrying until the cooldown passes, at which point any replica can simply propose it, since every replica can propose vertices in the DAG. Because all correct replicas execute identical batches, build the same Merkle trees, and collect signature shares over the same results, any of them can serve the client a valid response and proof.

rejoin. Since 𝜅 counts logical DAG rounds rather than time, it further needs no network-specific tuning. Execution and response storage. After committing vertices from the DAG, replicas forward the requests, included as payload, to their local state machine in total order (see §4.4) for execution. Each request includes an identifier 𝑟𝑖𝑑 that is unique per client, and the execution manager discards already executed requests. This way, Pangolin provides exactly-once semantics, despite re-submission attempts resulting from the client-failover mechanism. Replicas hold the most recent response (and associated proof) per client in a response storage (Alg. 2, l. 4), which is queried to answer re-submitted requests. The response storage becomes part of the replica state, so it must be included into checkpoints (Alg. 1, l. 40) so that a replica which recovered through a state transfer can still serve re-issued requests. Execution proofs. When an anchor slot commits, it delivers the part of its causal history that no earlier anchor slot has delivered in a deterministic order (Alg. 1, ll. 33–35), shown in Fig. 7(a). Pangolin batches exactly this set (all vertices committed by the same anchor slot) for proof generation. This means that up to three batches are delivered per wave. After executing a batch, the client handler constructs a Merkle tree [51] whose leaves are the hashes of the tuples (c, rid, request, response), and certifies its root with the threshold scheme of § 3: (1) Each replica creates a signature share, (2) and distributes it in a single all-to-all broadcast, subsequently (3) the enclave can use 𝑡 = 𝑓 +1 valid shares to create a threshold signature over the root, which can be verified using a single common public key. Verification. The proof a client receives comprises the threshold signature and the sibling hashes on the path from its leaf

4.6

Garbage Collection

DAG-based protocols produce two data structures that may grow without bound: the DAG itself and the vertex buffer. Bounding the DAG with a GC barrier. To restrict DAG memory usage, vertices that could not be ordered before a configured number of rounds must be deleted. However, agreement requires that if one correct replica deletes a vertex instead of ordering it, every other correct replica ignores it during ordering as well. Since BAB inherently ensures that commits occur in the same order at every correct replica, one can enforce a GC offset 𝑔 that moves with each commit, ensuring that it has the same effect on every replica (Theorem B.8). More precisely, after a commit (direct or retrospective) in wave 𝑤 the GC barrier is increased to wave 𝑤 − 𝑔, which determines that every unordered vertex before wave 𝑤 − 𝑔 will never be ordered and hence can be ignored (Alg. 1, l. 33). Backfilling without external storage. When a vertex is ignored or delivered, the content of the vertex is no longer required by the AB-layer of the replica that already decided the vertex’s fate. Furthermore, references to the vertex can be ignored and are therefore irrelevant (Alg. 1, l. 11). However, the vertex’s content is still required by the RB-layer to achieve a memory-bounded and performant request dissemination. Such a reliable broadcast requires replicas to help and recover other replicas, a mechanism we refer to as backfilling. For instance, a replica that delivered a vertex 𝑣 must still be able to provide the vertex to a replica that has fallen behind, such that this replica can also deliver 𝑣. While Narwhal [25] can still access garbage collected vertices from the external storage for backfilling purposes, Pangolin 9

DAG protocol to maintain high throughput (§ 4.5) (2) Our garbage collection scheme that bounds memory consumption under asynchrony (§ 4.6). Latency gains and (𝑛 ≥ 2𝑓 +1)resilience rely on the TEE assumption. In Appendix § D.1 we explain how to realize Pangolin without TEEs.

leverages the overlying SMR layer to build consecutive check𝑡ℎ wave, which are certified snapshots of the points every 𝐼 ckpt RSM state that are signed by 𝑓 +1 replicas. A state transfer to a certified checkpoint can replace the answer to a backfilling request for a vertex that was already deleted (Alg. 3, l. 10). Consequently, to answer backfilling requests, a vertex 𝑣 is not deleted already when it is ignored or delivered, but only when a checkpoint covering the ignorance or delivery of the vertex gets stable. This stable checkpoint therefore must be at least in wave 𝑣 .𝑤 + 𝑔 such that the checkpoint proves that the GC barrier already caught up to the vertex, which implies that either the vertex transactions are applied to the state of the stable checkpoint, or the vertex is ignored. Both options render the vertex’s content irrelevant to the requester once the state transfer is complete (see Lemma B.5).

5

Evaluation

We implement Pangolin in Rust on top of ABCperf [62], using Tokio for asynchronous networking, TCP and TLS for communication, Intel SGX with the Teaclave SDK [5] for the TEE, and SpliTEE common-key threshold signatures [41] for the client mechanism. Pangolin’s trusted computing base consists of 238 LOC and the protocol-agnostic client interaction layer of 505 LOC. 5.1

Checkpoint stabilization and active waiting. If a replica made more than 𝑔 waves of progress without stabilizing a checkpoint, it must ‘carefully’ wait for validation signatures from correct replicas, as otherwise, faulty replicas could prevent all checkpoint stabilization (Alg. 1, ll. 10–14). These signatures eventually arrive, because a replica continues to check for commits whenever a new vertex is added to the DAG (active waiting). Hence, commits and checkpoint validation can occur even during active waiting, ensuring that the procedure cannot lead to deadlocks. Moreover, if we set 𝑔 proportional to the expected latency ratio between the 𝑓 + 1 fastest replicas and the slowest, replica progress differs by less than 𝑔 waves and active waiting never takes place (see Theorem B.9 and Lemma B.11).

Setup and Claims

We evaluate two claims: (C1) a naive BFT client interaction significantly lowers the maximum achievable throughput of a DAG protocol, whereas our single-contact threshold-signature client interaction sustains near-baseline throughput with full BFT SMR guarantees (C2) Pangolin commits substantially faster than Mysticeti [9], the fastest DAG BFT consensus protocol we are aware of, with and without faults. Setup. We use 20 machines with 64 GB of memory and 10 Gbps links running Ubuntu 22.04, ten of them with an Intel Xeon E-2288G and ten with an Intel Xeon E-2388G CPU. We emulate the geo-distributed AWS deployment of Mysticeti [10] with netem [50] across the same 13 regions [2], halving the 𝑝 50 round-trip times reported by Cloudping [1] to obtain one-way delays between 6 ms and 140 ms (full config in § C.1). Replicas are spread evenly across regions, with at most one replica per machine for 𝑛 ≤ 20 and as even a colocation as possible beyond that. Clients run on 4 additional machines, without additional emulated latency. Requests are 64 B. Each configuration runs 4 times for 5 min and we exclude 30 s of warm-up and cooldown from each run.

Bounding the vertex buffer. Pangolin bounds the memory consumption of the vertex buffer by limiting it to vertices that lie at most 𝑔 waves in the future, creating a bounded receiving window (Alg. 3, ll. 4–5). If a vertex does not fit into the receiving window, it is discarded and backfilled by other replicas later, which ensures the agreement of the RB-layer (Alg. 3, ll. 6–7). The receiving window algorithm is sufficient (cf. Lemma B.6) and does not affect Pangolin’s performance, since replica progress is at most 𝑔 waves apart.

Baselines. To demonstrate generality of our client interaction layer and evaluate it with our implementation, we reimplement Narwhal/Tusk [25] in ABCperf. For the commit speed comparison, we use Mysticeti’s open-source implementation [61] with the default configuration, which designates two proposer slots per round. We test with equal 𝑛 and varying 𝑓 , i.e. Pangolin tolerates 𝑓 ≤ ⌊ 𝑛−1 2 ⌋ faults while both baselines tolerate only 𝑓 ≤ ⌊ 𝑛−1 ⌋. 3

Resulting memory bound. With GC and checkpointing, Pangolin consumes a fixed amount of memory even during |𝑆 | asynchrony, on the order of 𝑂 ((𝑛|𝑣 | + 𝐼𝑐𝑘𝑝𝑡 ) (𝑔 +𝐼𝑐𝑘𝑝𝑡 )) where |𝑣 | and |𝑆 | denote the sizes of a vertex and a checkpoint, respectively (for the derivation and constraints on the choice of 𝑔 and 𝐼𝑐𝑘𝑝𝑡 see Prop. B.13). Regarding timely fairness [64]: When 𝑔 is set proportionally to the relative latencies of replicas that hold during periods of synchrony, then during those periods vertices are neither ignored nor out of the receiving window, and no active waiting for checkpoint stabilization is required (see Prop. B.11, B.12, B.13).

5.2

Client Interaction

We compare three client mechanisms over Pangolin and Narwhal/Tusk at committee sizes 𝑛 ∈ {20, 40}. Classically, clients submit requests to all 𝑛 replicas and wait for 𝑓 + 1 matching replies. For each request, 𝑓 + 1 of 𝑛 replicas are deterministically designated responsible, the minimum needed for at least one to be honest. Replicas include any request they are responsible for, since they cannot tell whether a client is

Pangolin without TEEs. Two of the three main contributions we make do not depend on the availability of TEEs: (1) The efficient client interaction layer which enables our 10

𝑛 = 10

Narwhal/Tusk

Commit latency [ms]

Throughput [kOp/s]

Pangolin 120 90 60 30 0 𝑛=20 𝑛=40 No Client Guarantee (Baseline)

𝑛=20 𝑛=40 Classical Client

Ours

No Client Guarantee (Baseline) Classical Client Ours

Narwhal/Tusk

349.29±61.69 272.62±59.77 394.01±31.97

1189.88±8.37 1063.83±27.59 1260.78±22.16

𝑛 = 50

Pangolin Mysticeti

Figure 9. Commit latency [ms] at 12 500 requests/s. Boxes span 𝑝 25 –𝑝 75 , whiskers 𝑝 5 –𝑝 95 ; line is 𝑝 50 , marker is the mean. Crashed replicas: 0, 10% · 𝑛 (1/4/5) and 33% · 𝑛 (3/13/16)

Table 2. 𝑝 50 end-to-end latency [ms] at 𝑛 = 20 for the three client mechanisms of Fig. 8. ± intervals are t-based 95% confidence intervals across runs. Pangolin

𝑛 = 40

0% 10% 33% 0% 10% 33% 0% 10% 33% Induced crash faults (ratio of 𝑛)

Figure 8. Maximum sustained throughput of Pangolin and Narwhal/Tusk for the three client mechanisms.

Client

1 400 1 200 1 000 800 600 400 200 0

only the threshold client, by 121 ms (Pangolin) and 197 ms (Narwhal/Tusk), but also the baseline. 5.3

Commit Latency

In this experiment, we compare commit latency, the time between a request being received and it being committed by the replicas. We do not compare end-to-end latency, since the open-source Mysticeti implementation has no real clients: load is generated synthetically at the replica, so there is no client path. We also do not compare throughput, which is not meaningful across codebases given differences in optimizations and implementation choices. Each replica calculates the mean and percentiles of commit latency across the transactions it commits, which are then averaged across replicas to yield one of each statistic per configuration. Following Mysticeti, we run both systems at 12 500 requests/s, below either system’s maximum and roughly ten times the combined rate of current real-world blockchains [9]. We evaluate committee sizes 𝑛 ∈ {10, 40, 50}.

recovering from censorship or spamming. Our mechanism lets a replica decide this using the round-based cooldown of § 4.5, so only a single replica needs to include the request; a single threshold-signed reply then suffices as proof, and the client contacts only that replica and waits for its reply. As a reference for the maximum achievable throughput, we add a client that submits to a single replica and accepts a single reply without any client-side guarantee. Replicas propose transactions as soon as they transition rounds, to exclude batching effects. Throughput and end-to-end latency are both measured at the clients once they accept a reply. Requests proposed by multiple replicas are counted once. Fig. 8 reports the highest load at which the system keeps pace with the offered request rate (within 5%) while median end-to-end latency stays within 1.5× its minimum, both required at that load and at every lower one. With the naive client, both systems sustain 7–12% of their baseline throughput: 15 kOp/s against 122 kOp/s for Pangolin and 13 kOp/s against 120 kOp/s for Narwhal/Tusk at 𝑛 = 20, and 5 kOp/s against 72.5 kOp/s for both at 𝑛 = 40. Our client instead reaches 92–97% of the baseline (115 kOp/s and 110 kOp/s at 𝑛 = 20, 70 kOp/s for both at 𝑛 = 40). This confirms C1. Table 2 reports the corresponding end-to-end latencies for 𝑛 = 20. The threshold client is 45 ms slower than the baseline for Pangolin and 71 ms slower for Narwhal/Tusk, reflecting the cost of the signature share exchange and the Merkle tree generation. With clients directly connected at near-zero latency, this signature exchange dominates the 𝑓 + 1 replicaclient paths. Waiting for the fastest 𝑓 +1 of 𝑛 replies beats not

Without faults. Pangolin’s mean commit latency is 249 ms at 𝑛 = 10, 316 ms at 𝑛 = 40 and 321 ms at 𝑛 = 50, against 316 ms, 476 ms and 489 ms for Mysticeti, a speedup of 1.27×, 1.51× and 1.52× (Fig. 9). We attribute the difference to three mechanisms: the single-step TEE-based reliable broadcast (Fig. 4), the commit rules of § 4.4, which let an anchor slot commit one round after it was proposed, and the smaller ⌈ 𝑛+1 2 ⌉ quorum. At 𝑝 95 the margin is 1.15×, 1.15× and 1.08×. Under crash faults. We evaluate two failure scenarios, crashing 10 % and 33 % of the replicas in both systems before the measurement window opens, so the measurement covers the faulty steady state; 33 % is 𝑓 = ⌊ 𝑛−1 3 ⌋, the most Mysticeti tolerates. The set of crashed replicas is selected at random, but the same for both algorithms. Pangolin keeps its mean advantage at every point: 1.31×, 1.27× and 1.47× with 10 % crashed and 1.49×, 1.15× and 1.19× with 33 % crashed, at 𝑛 = 10, 40 and 50. With a significant speedup both with and 11

Pangolin (f=9)

all protocols. Each deployment places 𝑛 = 20 replicas in regions drawn independently, and with replacement, from a 34-region AWS latency matrix (see Fig. 12), so a deployment may co-locate replicas. Runs are fault-free and cover 600 s of simulated time each. Each replica computes the mean, 𝑝 50 , 𝑝 90 and 𝑝 99 block decision latency over the blocks it commits. We average each statistic separately across replicas, yielding one deployment-level mean, 𝑝 50 , 𝑝 90 and 𝑝 99 .

Median 352 ms

Mysticeti (f=6) Median 446 ms

Fides (f=9) Median 576 ms

Mahi-Mahi-5 (f=6) Median 604 ms

Shoal++ (f=6) Median 635 ms

Bullshark (f=6) Median 1,109 ms

Observations. Fig. 10 shows, for each protocol, the distribution across deployments of this deployment-level mean. In a direct, paired comparison, Pangolin has lower block decision latency than every baseline in all 100 deployments. Taking the median of the deployment-level means, Pangolin decides blocks in 352 ms against 446 ms for Mysticeti, 576 ms for Fides, 604 ms for Mahi-Mahi-5, 635 ms for Shoal++, 1,109 ms for Bullshark, 1,444 ms for Narwhal/Tusk and 2,070 ms for DAGRider, which means speedups of 1.27×, 1.64×, 1.72×, 1.80×, 3.15×, 4.10× and 5.88×, further confirming C2. The speedup ratio depends considerably on the concrete deployment chosen: for Pangolin against Mysticeti, the speedup never drops below 1.16× but can also reach 1.51×. The speedup also narrows in the tail (𝑝 90 : 1.12×, 𝑝 99 : 1.02× for Pangolin vs. Mysticeti), consistent with our finding in § 5.3, that attributes tail latency to the randomized leader election necessary in the asynchronous setting. Compared to Fides [70], another asynchronous TEE-DAG protocol with 2𝑓 + 1 replicas and 𝑓 + 1 previous-round references, Pangolin achieves an average speedup of 1.64× (𝑝 90 : 1.58×, 𝑝 99 : 1.76×). Fides’ trusted coin releases one firstround anchor per four-round wave upon presentation of a fourth-round certificate. Direct commitment requires support from 𝑓 + 1 fourth-round vertices. Both protocols share the same reduced quorum size, but Pangolin’s three anchor slots per wave and relaxed commit rules yield far more commitment opportunities. Appendix C.3 additionally reports paired comparisons and cumulative latency distributions.

Narwhal/Tusk (f=6) Median 1,444 ms

DAG-Rider (f=6) Median 2,070 ms

0

500

1000

1500

2000

2500

Mean block decision latency [ms]

Figure 10. Distribution of mean block decision latency across 100 deployments (𝑛 = 20, 600 s each). For each protocol, the curve shows the distribution over deployments; each dot marks one deployment’s mean latency. The bar spans the interquartile range, and the white circle marks the median. without faults, we can confirm C2. With 33 % crashed, Pangolin’s 𝑝 95 reaches 1242 ms at 𝑛 = 40 and 1238 ms at 𝑛 = 50, against 853 ms and 846 ms for Mysticeti. Pangolin elects its anchors by coin toss, and with fewer correct replicas the coin is more likely to land on a crashed one, causing commits to be postponed to the next wave, whereas Mysticeti’s fixed leader schedule avoids this at the cost of a timing assumption. 5.4

Generality across Deployments

The metrics of §§ 5.2 and 5.3 assume a single deployment setting, using 13 hand-selected AWS regions (the regions used by Mysticeti’s evaluation [10]). To show that Pangolin’s latency improvements do not depend on this concrete deployment scenario, we use a discrete-event network simulator to evaluate Pangolin across 100 independently sampled deployments, and extend our evaluation to more DAG protocols. The simulator abstracts cryptography and models the network using replica-replica one-way delays, so it reproduces the protocol structure rather than an implementation; in particular, it does not model transaction submission or queueing at a replica. We therefore report block decision latency, the time from a block being proposed to it being committed, rather than the commit latency of § 5.3. Commit latency additionally includes the time a transaction spends queued until it is included in a vertex. Block decision latency isolates the protocol’s message-passing cost, which dominates commit latency in a real WAN. Appendix C.3 details the simulator for the interested reader.

6

Related Work

Scalability. SBFT [39] also uses Merkle proofs and threshold signatures to reduce client communication to a single reply in the common case, although here the application state is used to construct the proof, rather than a per-batch tree of responses. In SBFT, a replica sends its signature share only to a small designated group of replicas called collectors, which combine the shares into the threshold signature before distributing it but if no collector’s reply arrives in time, then the client must fall back to broadcasting its request to all replicas and collecting 𝑓 +1 responses. Mir-BFT and ISS [66, 65] parallelize the proposing of batches of requests among several leaders. Raptr [68] combines votes for replicas’ locally available proposal prefixes to enable commitment without retrieving the entire proposal. Autobahn [38] disseminates batches along per-replica chains and orders their prefixes

Setup. We simulate Pangolin against seven baselines: DAGRider [45], Narwhal/Tusk [25], Bullshark [64], Shoal++ [7], Mahi-Mahi-5 [43], Mysticeti [9] and the TEE-based Fides [70]. A deployment sampler creates 100 deployments, reused across 12

through compact proposals containing certified chain tips. Raptr and Autobahn scale leader-driven ordering under partial synchrony, whereas Pangolin uses TEEs to order DAG causal histories with randomized asynchronous progress. Shrestha and Kate [59] use sampled committees to reduce payload replication and partition transaction execution in a DAG protocol. This reduces dissemination and execution work, complementary to Pangolin’s faster ordering. Finally, the Chop Chop [18] architecture uses untrusted brokers to amortize input authentication and ordering. Its delivery certificates concern broadcast completion, whereas Pangolin certifies execution results and does not necessitate brokers.

Fides [70] is a close asynchronous TEE-assisted DAG protocol with 2𝑓 + 1 replicas and 𝑓 + 1 previous-round references. Pangolin provides three anchor slots per wave, more support opportunities, and checks commitment inside the enclave, revealing an anchor once sufficient support exists. This permits commitment before the wave ends and significantly accelerates it without losing liveness. Pallas and Aegis [28] address trusted-state rollback after crashes or cloning, which can complement Pangolin’s application-state recovery.

7

Conclusion

Pangolin is an asynchronous DAG-based BFT SMR protocol that combines low-latency commitment with efficient client interaction and garbage collection. It requires only 𝑛 ≥ 2𝑓 +1 replicas and is probabilistically live under asynchrony. To speed up commitments, Pangolin uses a single broadcast step per round that leverages trusted non-equivocation and can commit early via enclave-protected checks. Furthermore, Pangolin integrates batched execution proofs to let clients verify execution results through a single reply, including after retrying at another replica. Pangolin limits protocol state through the use of checkpoint-driven garbage collection and bounded receiving windows. Certified checkpoints let lagging replicas recover even when they miss the DAG history. In an emulated 13-region WAN, Pangolin commits up to 1.52× faster than Mysticeti and keeps its lead with a third of the replicas crashed; in simulation, it decides blocks faster than seven DAG protocols in all 100 sampled deployments. Clients retain 92–97% of the maximum possible throughput, whereas a classical client that sends to all replicas and waits for 𝑓 +1 replies achieves only 7–12%. Pangolin’s architecture shows that trusted components and coordinated design across ordering, client interaction, and recovery can make asynchronous DAG-based replication practical for BFT SMR.

Progress and resource management. Aardvark [22] isolates communication resources and schedules request processing to prevent Byzantine replicas from starving useful work. Pangolin addresses a related problem of reclaiming DAG history while preserving recovery for lagging replicas. DispersedLedger [71] lets asynchronous agreement advance ahead of payload retrieval and discusses suspending proposals when retrieval falls too far behind. This is similar to Pangolin’s use of progress-dependent throttling, but Pangolin binds throttling to checkpoint certification and uses certified snapshots to recover replicas that require history. Trusted components. MinBFT [56] introduced a trusted counter to prevent equivocation and tolerate 𝑓 faults with only 2𝑓 + 1 replicas. CheapBFT [44] further reduced normalcase work by only requiring 𝑓 + 1 active replicas to agree on and execute requests while 𝑓 passive replicas receive state updates. Damysus [26] extends HotStuff [72] with trusted services, requires 2𝑓 + 1 replicas, saves one protocol phase compared to HotStuff and also assumes partial synchrony. OneShot [27] improves on Damysus by shortening it by another protocol phase in the normal case while needing a smaller trusted computing base. Its key idea is to adapt each view to what its leader knows about previously prepared blocks, which allows OneShot to decide in just four instead of six communication steps in the normal case. Furthermore, the leaderless set Byzantine consensus protocol of RedBelly [24] was adapted with trusted components to 𝑛 ≥ 2𝑓 +1 [73]. This approach assumes partial synchrony and employs a trusted counter and a trusted collector service: Each replica broadcasts a proposal through a two-step hybrid verified reliable broadcast, after which one binary agreement per proposal decides if the proposal can be included. In contrast, Pangolin orders all proposals through a single DAG without per-proposal agreement and remains live under asynchrony. Pangolin uses the TEE-based reliable broadcast from [49, § 4.2] as a building block to construct a fast DAG-based SMR protocol that operates under asynchrony: The trusted non-equivocation allows fast vertex certification, while backfilling retrieves missing causal dependencies.

Acknowledgments This work is funded by Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – 446811880 (BFT2Chain). This work was supported by funding from the topic Engineering Secure Systems of the Helmholtz Association (HGF).

References [1] [2]

[3]

13

Matt Adorjan. [n. d.] AWS latency monitoring. Retrieved Sept. 1, 2026 from https://cloudping.co/. Amazon Web Services. 2026. AWS region billing codes. Retrieved Sept. 1, 2026 from https://docs.aws.amazon.com/global-infrastructu re/latest/regions/aws-region-billing-codes.html. Yair Amir, Brian Coan, Jonathan Kirsch, and John Lane. 2010. Prime: byzantine replication under attack. IEEE Trans. Dep. & Sec. Comp., 8, 4. doi:10.1109/TDSC.2010.70.

[4]

[5] [6] [7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16] [17]

[18]

[19]

[20]

[21]

Yair Amir, Claudiu Danilov, Danny Dolev, Jonathan Kirsch, John Lane, Cristina Nita-Rotaru, Josh Olsen, and David Zage. 2010. Steward: scaling Byzantine fault-tolerant replication to wide area networks. IEEE Trans. Dep. & Sec. Comp., 7, 1, (Jan. 2010). doi:10.1109 /TDSC.2008.53. Apache. [n. d.] Teaclave-sgx-sdk. Retrieved Sept. 1, 2026 from https: //github.com/apache/teaclave-sgx-sdk. Aptos Foundation. 2025. Aptos. Retrieved Mar. 2026 from https://ap tosnetwork.com. 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 Symp. Netw. Syst. Des. & Impl. (NSDI). https://www.usenix.org/conference/nsdi25/presentation/arun. Amy Babay, John Schultz, Thomas Tantillo, Samuel Beckley, Eamon Jordan, Kevin Ruddell, Kevin Jordan, and Yair Amir. 2019. Deploying intrusion-tolerant SCADA for the power grid. In 49th Ann. IEEE/IFIP Int. Conf. Dep. Syst. & Netw. (DSN). 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 Netw. & Distr. Syst. Sec. Symp. (NDSS). Internet Soc. doi:10 .14722/ndss.2025.240929. Kushal Babel, Andrey Chursin, George Danezis, Anastasios Kichidis, Lefteris Kokoris-Kogias, Arun Koshy, Alberto Sonnino, and Mingwei Tian. 2025. Mysticeti: reaching the limits of latency with uncertified dags. arXiv: 2310.14821v6. Shehar Bano et al. 2019. State machine replication in the Libra blockchain. Technical Report. Calibra. [Online]. Available: https: //developers.diem.com/papers/diem-consensus-state-machine-re plication-in-the-diem-blockchain/2019-09-26.pdf. (2019). Daniel J. Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, and Bo-Yin Yang. 2011. High-speed high-security signatures. Cryptology ePrint Archive, Paper 2011/368. (2011). https://ia.cr/2011/368. Alysson Bessani, João Sousa, and Eduardo EP Alchieri. 2014. State machine replication for the masses with BFT-SMaRt. In 44th IEEE/IFIP Int. Conf. Dep. Syst. & Netw. (DSN). doi:10.1109/DSN.2014.43. Alysson Neves Bessani, Paulo Sousa, Miguel Correia, Nuno Ferreira Neves, and Paulo Verissimo. 2008. The CRUTIAL way of critical infrastructure protection. IEEE Sec. & Priv., 6, 6. doi:10.1109/MSP.20 08.158. Dan Boneh, Ben Lynn, and Hovav Shacham. 2004. Short signatures from the weil pairing. J. Cryptology, 17, 4, (Sept. 1, 2004). doi:10.1007 /s00145-004-0314-9. Ethan Buchman, Jae Kwon, and Zarko Milosevic. 2018. The latest gossip on BFT consensus. arXiv preprint arXiv:1807.04938. Christian Cachin, Rachid Guerraoui, and Luís Rodrigues. 2011. Introduction to Reliable and Secure Distributed Programming. (2nd ed.). Springer. doi:10.1007/978-3-642-15260-3. Martina Camaioni, Rachid Guerraoui, Matteo Monti, Pierre-Louis Roman, Manuel Vidigueira, and Gauthier Voron. 2024. Chop Chop: byzantine atomic broadcast to the network limit. In 18th USENIX Symp. Oper. Syst. Des. & Impl. (OSDI). https://www.usenix.org/confe rence/osdi24/presentation/camaioni. Miguel Castro. 2001. Practical Byzantine Fault Tolerance. Ph.D. Dissertation. MIT. https://dspace.mit.edu/entities/publication/9c5c3bd c-8bad-48dc-b4ac-1444fde28af4. Miguel Castro and Barbara Liskov. 1999. Practical Byzantine fault tolerance. In 3rd Symp. Oper Syst., Des. & Impl. (OSDI). http://usenix .org/publications/library/proceedings/osdi99/full_papers/castro/ca stro_html/castro.html. Allen Clement, Manos Kapritsos, Sangmin Lee, Yang Wang, Lorenzo Alvisi, Mike Dahlin, and Taylor Riche. 2009. Upright cluster services. In 22nd ACM SIGOPS Symp. Oper. Syst. Princ. (SOSP). doi:10.1145/162 9575.1629602.

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29] [30] [31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

14

Allen Clement, Edmund L. Wong, Lorenzo Alvisi, Michael Dahlin, and Mirco Marchetti. 2009. Making Byzantine fault tolerant systems tolerate Byzantine faults. In 6th USENIX Symp. Netw. Syst. Des. & Impl. (NSDI). http://usenix.org/events/nsdi09/tech/full_papers/clem ent/clement.pdf. James Cowling, Daniel Myers, Barbara Liskov, Rodrigo Rodrigues, and Liuba Shrira. 2006. HQ replication: a hybrid quorum protocol for Byzantine fault tolerance. In 7th Symp. Oper. Syst. Des. & Impl. (OSDI). http://usenix.org/event/osdi06/tech/full_papers/cowling/co wling.pdf. Tyler Crain, Christopher Natoli, and Vincent Gramoli. 2021. Red belly: a secure, fair and scalable open blockchain. In 42nd IEEE Symp. Sec. & Priv. (SP), 466–483. George Danezis, Lefteris Kokoris-Kogias, Alberto Sonnino, and Alexander Spiegelman. 2022. Narwhal and Tusk: a DAG-based mempool and efficient BFT consensus. In 17th Eur. Conf. Comp. Syst. (EuroSys). ACM, (Mar. 28, 2022). doi:10.1145/3492321.3519594. Jérémie Decouchant, David Kozhaya, Vincent Rahli, and Jiangshan Yu. 2022. DAMYSUS: streamlined BFT consensus leveraging trusted components. In 17th Eur. Conf. Comp. Syst. (EuroSys). ACM, 16 pages. doi:10.1145/3492321.3519568. Jérémie Decouchant, David Kozhaya, Vincent Rahli, and Jiangshan Yu. 2024. Oneshot: view-adapting streamlined bft protocols with trusted execution environments. In 2024 IEEE International Parallel and Distributed Processing Symposium (IPDPS). IEEE, 1022–1033. Jérémie Decouchant, David Kozhaya, Vincent Rahli, and Jiangshan Yu. 2026. Pallas and Aegis: rollback resilience in TEE-aided blockchain consensus. In Netw. & Distr. Syst. Sec. Symp. (NDSS). Internet Soc. doi:10.14722/ndss.2026.242443. DefiLlama. [n. d.] Aptos – DeFi TVL, fees, & revenue. Retrieved Mar. 24, 2026 from https://defillama.com/chain/aptos. DefiLlama. [n. d.] Sui – DeFi TVL, fees, & revenue. Retrieved Mar. 24, 2026 from https://defillama.com/chain/sui. Tobias Distler. 2021. Byzantine fault-tolerant state-machine replication from a systems perspective. ACM Comp. Surv., 54, 1, (Feb. 11, 2021). doi:10.1145/3436728. Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. 1988. Consensus in the presence of partial synchrony. J. ACM, 35, 2. doi:10.1145/4 2282.42283. Michael Eischer and Tobias Distler. 2018. Latency-aware leader selection for geo-replicated byzantine fault-tolerant systems. In 48th IEEE/IFIP Int. Conf. Dep. Syst. & Netw. Workshops (DSN-W). doi:10.11 09/DSN-W.2018.00053. Michael J Fischer, Nancy A Lynch, and Michael S Paterson. 1985. Impossibility of distributed consensus with one faulty process. J. ACM, 32, 2. doi:10.1145/3149.214121. Miguel Garcia, Nuno Neves, and Alysson Bessani. 2013. An intrusiontolerant firewall design for protecting SIEM systems. In 43rd Ann. IEEE/IFIP Conf. Dep. Syst. & Netw. Worksh. (DSN-W). doi:10 . 1109 /DSNW.2013.6615538. Miguel Garcia, Nuno Neves, and Alysson Bessani. 2016. SieveQ: a layered BFT protection system for critical services. IEEE Trans. Dep. & Sec. Comp. (TDSC), 15, 3. doi:10.1109/TDSC.2016.2593442. Rati Gelashvili, Lefteris Kokoris-Kogias, Alberto Sonnino, Alexander Spiegelman, and Zhuolun Xiang. 2022. Jolteon and Ditto: networkadaptive efficient consensus with asynchronous fallback. In Int. Conf. Fin. Crypt. & Data Sec. (FC) (LNCS). Vol. 13411. Springer. doi:10.1007 /978-3-031-18283-9_14. Neil Giridharan, Florian Suri-Payer, Ittai Abraham, Lorenzo Alvisi, and Natacha Crooks. 2024. Autobahn: seamless high speed BFT. In 30th ACM SIGOPS Symp. Oper. Syst. Princ. (SOSP). New York, NY, USA, (Nov. 15, 2024). doi:10.1145/3694715.3695942. Guy Golan Gueta, Ittai Abraham, Shelly Grossman, Dahlia Malkhi, Benny Pinkas, Michael Reiter, Dragos-Adrian Seredinschi, Orr Tamir,

[40]

[41]

[42]

[43]

[44]

[45]

[46]

[47]

[48]

[49]

[50]

[51]

[52] [53]

[54]

[55]

[56]

[57]

[58]

and Alin Tomescu. 2019. SBFT: a scalable and decentralized trust infrastructure. In 49th Ann. IEEE/IFIP Int. Conf. Dep. Syst. & Netw. (DSN). IEEE. doi:10.1109/DSN.2019.00063. Rachid Guerraoui, Nikola Knežević, Vivien Quéma, and Marko Vukolić. 2010. The next 700 BFT protocols. In 5th Eur. Conf. Comp. Syst. (EuroSys). doi:10.1145/1755913.1755950. Marius Haller, Marc Leinweber, Tilo Spannagel, Markus Raiber, and Hannes Hartenstein. 2026. Performance and security of TEE-based threshold cryptography. In 9th Worksh. Syst. Softw. for Trusted Exec. (SysTEX). ACM, 8 pages. doi:10.1145/3805690.3805725. Alexander Heß, Franz J. Hauck, and Echo Meißner. 2024. Consensusagnostic state-machine replication. In 25th Int. Middlew. Conf. ACM. doi:10.1145/3652892.3700776. Philipp Jovanovic, Lefteris Kokoris-Kogias, Bryan Kumara, Alberto Sonnino, Pasindu Tennage, and Igor Zablotchi. 2025. Mahi-Mahi: lowlatency asynchronous BFT DAG-based consensus. In 45th Int. Conf. Distr. Comp. Syst. (ICDCS). doi:10.1109/ICDCS63083.2025.00060. Rüdiger Kapitza, Johannes Behl, Christian Cachin, Tobias Distler, Simon Kuhnle, Seyed Vahid Mohammadi, Wolfgang Schröder-Preikschat, and Klaus Stengel. 2012. CheapBFT: resource-efficient Byzantine fault tolerance. In 7th ACM Eur. Conf. Comp. Syst. (EuroSys). doi:10.1 145/2168836.2168866. Idit Keidar, Eleftherios Kokoris-Kogias, Oded Naor, and Alexander Spiegelman. 2021. All you need is DAG. In ACM Symp. Princ. Distr. Comp. (PODC). (July 23, 2021). doi:10.1145/3465084.3467905. Idit Keidar, Oded Naor, Ouri Poupko, and Ehud Shapiro. 2023. Cordial miners: fast and efficient consensus for every eventuality. In 37th Int. Symp. Distr. Comp. (DISC). Vol. 281. doi:10.4230/LIPIcs.DISC.2023.26. Jonathan Kirsch, Stuart Goose, Yair Amir, Dong Wei, and Paul Skare. 2014. Survivable SCADA via intrusion-tolerant replication. IEEE Trans. Smart Grid, 5, 1. doi:10.1109/TSG.2013.2269541. Leslie Lamport, Robert Shostak, and Marshall Pease. 1982. The Byzantine generals problem. ACM Trans. Progr. Lang. & Syst. (TOPLAS), 4, 3, (July 1982), 20 pages. doi:10.1145/357172.357176. Marc Leinweber. 2026. TEE-Based Distributed Ledgers and Their Resilience. Ph.D. Dissertation. Karlsruher Inst. für Techn. (KIT). doi:10 .5445/IR/1000189670. Fabio Ludovici, Hagen Paul Pfeifer, and Stephen Hemminger. 2026. tc-netem(8) — Linux manual page. (Sept. 1, 2026). https://man7.org/l inux/man-pages/man8/tc-netem.8.html. Ralph C. Merkle. 1990. A certified digital signature. In 9th Ann. Int. Crypt. Conf. (CRYPTO ’89) (LNCS). Vol. 435. Springer. doi:10.1007/0387-34805-0_21. Mysten Labs. 2025. Sui. Retrieved Mar. 2026 from https://sui.io. Ray Neiheiser, Miguel Matos, and Luís Rodrigues. 2021. Kauri: scalable BFT consensus with pipelined tree-based dissemination and aggregation. In 28th ACM SIGOPS Symp. Oper. Syst. Princ. (SOSP). doi:10.1145/3477132.3483584. Nikita Polyanskii, Sebastian Müller, and Ilya Vorobyev. 2025. Starfish: a high throughput BFT protocol on uncertified DAG with linear amortized communication complexity. IACR Cryptol. ePrint Arch., 2025. https://nikitapolyanskii.com/writings/2025-44-starfish/prepri nt.pdf. Michael K. Reiter and Kenneth P. Birman. 1994. How to securely replicate services. ACM Trans. Progr. Lang. & Syst. (TOPLAS), 16, 3, (May 1994), 24 pages. doi:10.1145/177492.177745. Giuliana Santos Veronese, Miguel Correia, Alysson Neves Bessani, Lau Cheuk Lung, and Paulo Verissimo. 2013. Efficient Byzantine Fault-Tolerance. IEEE Trans. Comp., 62, 1. doi:10.1109/tc.2011.221. Fred B. Schneider. 1990. Implementing fault-tolerant services using the state machine approach: a tutorial. ACM Comp. Surv. (CSUR), 22, 4. doi:10.1145/98163.98167.

[59]

[60]

[61] [62]

[63]

[64]

[65]

[66]

[67]

[68]

[69]

[70]

[71]

[72]

[73]

15

Victor Shoup. 2000. Practical threshold signatures. In 19th Int. Conf. Theory & Appl. of Crypt. Techn. (EUROCRYPT). Springer, 14 pages. doi:10.1007/3-540-45539-6_15. Nibesh Shrestha and Aniket Kate. 2026. Towards Improving Throughput and Scalability of DAG-based BFT SMR. In 21st Eur. Conf. Comp. Syst. (EuroSys). ACM. doi:10.1145/3767295.3769363. Nibesh Shrestha, Rohan Shrothrium, Aniket Kate, and Kartik Nayak. 2025. Sailfish: towards improving the latency of DAG-based BFT. In IEEE Symp. Sec. & Priv. (SP). doi:10.1109/SP61157.2025.00021. Alberto Sonnino. [n. d.] Mysticeti. Retrieved Sept. 1, 2026 from http s://github.com/asonnino/mysticeti. Tilo Spannagel, Marc Leinweber, Adriano Castro, and Hannes Hartenstein. 2023. ABCperf: performance evaluation of fault tolerant state machine replication made simple: Demo Abstract. In 24th Int. Middlew. Conf.: Demos, Posters & Doct. Symp. ACM, 2 pages. doi:10.1145 /3626564.3629101. Alexander Spiegelman, Balaji Arun, Rati Gelashvili, and Zekun Li. 2024. Shoal: improving DAG-BFT latency and robustness. In 28th Int. Conf. Fin. Crypt. & Data Sec. (FC). Springer. doi:10.1007/978-3-031-7 8676-1_6. Alexander Spiegelman, Neil Giridharan, Alberto Sonnino, and Lefteris Kokoris-Kogias. 2022. Bullshark: DAG BFT protocols made practical. In ACM SIGSAC Conf. Comp. & Comm. Sec. (CCS). (Nov. 7, 2022). doi:10.1145/3548606.3559361. Chrysoula Stathakopoulou, Tudor David, Matej Pavlovic, and M Vukolić. 2022. Mir-BFT: scalable and robust BFT for decentralized networks. J. Syst. Res. (JSYS), 2, 1. doi:10.5070/SR32159278. Chrysoula Stathakopoulou, Matej Pavlovic, and Marko Vukolić. 2022. State machine replication scalability made simple. In 17th Eur. Conf. Comp. Syst. (EuroSys). ACM. doi:10.1145/3492321.3519579. Pasindu Tennage, Cristina Basescu, Lefteris Kokoris-Kogias, Ewa Syta, Philipp Jovanovic, Vero Estrada-Galinanes, and Bryan Ford. 2023. Quepaxa: escaping the tyranny of timeouts in consensus. In 29th ACM Symp. Oper. Syst. Princ. (SOSP). doi:10.1145/3600006.36131 50. Andrei Tonkikh, Balaji Arun, Zhuolun Xiang, Zekun Li, and Alexander Spiegelman. 2025. Raptr: Prefix Consensus for Robust HighPerformance BFT. (2025). arXiv: 2504.18649 [cs.DC]. doi:10.48550/a rXiv.2504.18649. Benjamin Wester, James A Cowling, Edmund B Nightingale, Peter M Chen, Jason Flinn, and Barbara Liskov. 2009. Tolerating latency in replicated state machines through client speculation. In 6th USENIX Symp. Netw. Syst. Des. & Impl. (NSDI). http://usenix.org/events/nsdi0 9/tech/full_papers/wester/wester.pdf. Shaokang Xie, Dakai Kang, Hanzheng Lyu, Jianyu Niu, and Mohammad Sadoghi. 2026. Fides: secure and scalable asynchronous dag consensus via trusted components. arXiv: 2501.01062v4. 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 Symp. Netw. Syst. Des. & Impl. (NSDI). https://www.usenix.org/conference/nsdi22 /presentation/yang. Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan Gueta, and Ittai Abraham. 2019. Hotstuff: BFT consensus with linearity and responsiveness. In ACM Symp. Princ. of Distr. Comp. (PODC), 10 pages. doi:10.1145/3293611.3331591. Liangrong Zhao, Jérémie Decouchant, Joseph K. Liu, Qinghua Lu, and Jiangshan Yu. 2024. Trusted hardware-assisted leaderless Byzantine fault tolerance consensus. IEEE Trans. Dep. & Sec. Comp., 21, 6, 5086– 5097. doi:10.1109/TDSC.2024.3357521.

Algorithm 1 Pangolin Byzantine Atomic Broadcast: Main Loop for Process 𝑝𝑖 1: state 𝑃 : set of processes 2: state DAG : array of array of vertices, DAG [0] initialized with genesis vertices 3: state 𝑟 : N, initialized with 0 4: state decidedRound : N0 , initialized with 0 5: state messageBuffer : queue of messages, initialized empty 6: state vertexBuffer : set of vertices per process of size 𝑚𝑏 , initialized empty 7: state delivered : array of round of last delivered vertex per process, initialized with 0 8: state 𝑎𝑑𝑑𝑒𝑑 : array of round of last vertex added per process, initialized with 0 9: while true do 10: for 𝑣 ∈ vertexBuffer do

if 𝑣 .𝑟 ≤ 𝑟 ∧ (∀ℎ ∈ 𝑣 .edges : DAG [ℎ.𝑟 ] [ℎ.𝑝] ≠ ⊥ ∨ irrelevant(ℎ.𝑟, ℎ.𝑝)) then 𝐷𝐴𝐺 [𝑣.𝑟 ] [𝑣.𝑝] ← 𝑣; vertexBuffer.remove(𝑣);added [v.p] ← v.r if decidedRound < 𝑣 .𝑟 ∧ 𝑢 ≔ check_commit(𝑣) ≠ ⊥ then waveReady(𝑢) if 4 · (pendingCkpts.earliestUnstable().𝑤 + 𝑔) < 𝑟 then continue ⊲ stable checkpoint should have been built by now if |DAG [𝑟 ] | < 𝑓 + 1 ∨ DAG [𝑟 ] [𝑝𝑖 ] = ⊥ then continue 𝑟 ←𝑟 +1 17: wait until ¬messageBuffer.isEmpty() ⊲ allow inserting empty vertices for progress when there is no continuous load 18: 𝑣 ← new vertex(block ≔ messageBuffer.pop(), 𝑟 ≔ 𝑟, 𝑝 ≔ 𝑝𝑖 , 𝑤 ≔ ⌊ 𝑟4 ⌋, edges ≔ added) 19: 𝑣 .𝜎 ← enclave_sign(𝑣) 20: for all 𝑝 𝑗 ∈ 𝑃 do send ⟨𝑉 𝐸𝑅𝑇 𝐸𝑋, 𝑣⟩ to 𝑝 𝑗 21: function a_broadcast(𝑚) 22: messageBuffer.insert(𝑚) 23: function waveReady(𝑢) 24: 𝑢𝑟 ← 𝐷𝐴𝐺 [𝑢.𝑟 ] [𝑢.𝑝] 25: committedAnchors ← new stack; committedAnchors.push(𝑢𝑟 ) 26: for 𝑟 ′ ← 𝑢.𝑟 − 1 down to decidedRound + 1 do 27: if 𝑟 ′ mod 4 = 3 then continue ′ 28: 𝑢𝑟 ′ ← 𝐷𝐴𝐺 [𝑟 ′ ] [CPRNG( ⌊ 𝑟4 ⌋)] ⊲ Coin is already revealed 29: if 𝑢𝑟 ′ ≠ ⊥ ∧ path(𝑢𝑟 , 𝑢𝑟 ′ ) then 30: committedAnchors.push(𝑢𝑟 ′ ); 𝑢𝑟 ← 𝑢𝑟 ′ 31: while ¬committedAnchors.isEmpty() do 32: 𝑢𝑟 ′ ← committedAnchors.pop() 33: verticesToDeliver ← {𝑣 | 𝑣 ∈ DAG : path(𝑢𝑟 ′ , 𝑣) ∧ delivered [𝑣.𝑝] < 𝑣.𝑟 ∧ ¬ignored(𝑣 .𝑟 )} 34: for 𝑣 ∈ verticesToDeliver in deterministic order do 35: a_deliver (𝑣 .𝑝, 𝑣.𝑟, 𝑣 .block); delivered [𝑣.𝑝] ← 𝑣 .𝑟 36: decidedRound ← 𝑟 ′ 37: if 𝑟 ′ mod 4 ≠ 0 then continue ⊲ build new checkpoint over commit of the first anchor in a wave ′ 38: 𝑤 ′ ← 𝑟4 ; respondCkptRequests(𝑤 ′ ) ⊲ two consecutive checkpoints are at least 𝐼𝑐𝑘𝑝𝑡 waves apart 39: if pendingCkpts.front().𝑤 + 𝐼 ckpt ≤ 𝑤 ′ then 40: ckptnew ← new checkpoint(𝑤 ′, state, responseStorage, delivered); pendingCkpts.enqueue(ckptnew ) 41: certify(ckptnew ) 11: 12: 13: 14: 15: 16:

A

Algorithms

covers the checkpoint related tasks of the SMR execution manager which are: certifying checkpoints (ll. 8–27), performing state transfers at replicas that have fallen behind (ll. 28–33), and carrying out garbage collection whenever a new stable checkpoint is available (ll. 34–36). Next, the RB-layer of Pangolin makes use of a TEE-based reliable broadcast that is contrasted to the broadcast pattern of Narwhal in Fig. 4. The functionality of the RB-layer is depicted in the third snippet (Alg. 3). The reliable broadcast receives

In this Appendix we present the logic of Pangolin split into four snippets of pseudo-code. The first snippet (Alg. 1) contains the logic of the atomic broadcast which is: receiving requests from the client handler (ll. 21–22), putting them into new vertices (ll. 17–20), receiving vertices from the RB-layer and adding them to the DAG (ll. 10–16), committing anchors once the commit rules are fulfilled (ll. 23–36) and invoking checkpoint creation (ll. 37–41). The second snippet (Alg. 2) 16

Algorithm 2 Pangolin SMR: Checkpoint Certification Logic for Process 𝑝𝑖 1: state ckptstable :

last certified checkpoint, initialized by genesis

2: state pendingCkpts : queue of uncertified checkpoints, initialized by genesis 3: state state : SMR state 4: state responseStorage : buffer of last response to client requests per client 𝑔 5: state ckptRequests : buffer of last ⌈ 𝐼 ⌉ received checkpoint requests per replica ckpt

6: state 𝐼𝑐𝑘𝑝𝑡 : N, checkpoint interval 7: state 𝑔 : N0 , garbage collection offset 8: function certify(ckpt) 9: for all 𝑝 𝑗 ∈ 𝑃 do send ⟨𝐶𝐾𝑃𝑇 _𝑆𝐼𝐺𝑁 _𝑅𝐸𝑄, h(ckpt), ckpt.𝑤⟩ to 𝑝 𝑗 10: upon ckpt_sign_req(𝑝𝑘 , ℎ, 𝑤) 11: if h(pendingCkpts.get(𝑤)) = ℎ then 12: send ⟨𝐶𝐾𝑃𝑇 _𝑆𝐼𝐺𝑁 _𝑅𝐸𝑆𝑃, ℎ, sign(ℎ), 𝑤⟩ to 𝑝𝑘 13: else if 𝑤 ≤ ckptstable .𝑤 then send ⟨𝑆𝑇 𝐴𝑇 𝐸_𝑇 𝑅𝐴𝑁 𝑆𝐹 𝐸𝑅, ckptstable ⟩ to 𝑝𝑘 14: else ckptRequests.add(ℎ, 𝑤, 𝑝𝑘 ) 15: upon ckpt_sign_resp(𝑝𝑘 , ℎ, 𝜎𝑘 , 𝑤) 16: ckpt ← pendingCkpts.get(𝑤) 17: if 𝑤 ≤ ckptstable .𝑤 ∨ ¬verify(h(𝑐𝑘𝑝𝑡), 𝜎𝑘 , 𝑝𝑘 ) then abort 18: ckpt.signatureShares.push(𝜎𝑘 )

⊲ ckpt is in the past and cannot be verified

19: if |ckpt.signatureShares| ≥ 𝑓 + 1 then 20: ckpt.cert ← global_sign(h(ckpt), ckpt.signatureShares) 21: pruneUpTo(𝑐𝑘𝑝𝑡); ckptstable ← ckpt 22: function respondCkptReqests(𝑤) 23: for (ℎ, 𝑤 ′, 𝑝𝑘 ) ∈ ckptRequests do 24: if 𝑤 = 𝑤 ′ then 25: ℎ ← ℎ(new checkpoint(𝑤 ′, state, responseStorage, delivered)) 26: send ⟨𝐶𝐾𝑃𝑇 _𝑆𝐼𝐺𝑁 _𝑅𝐸𝑆𝑃, ℎ, sign(ℎ), 𝑤⟩ to 𝑝𝑘 27: ckptRequests.remove(ℎ, 𝑤 ′, 𝑝𝑘 ) 28: upon state_transfer(𝑝𝑘 , ckpt) 29: if ckpt.𝑤 ≤ ckptstable .𝑤 ∨ ¬global_verify(ckpt.cert, ckpt) then abort 30: pruneUpTo(𝑐𝑘𝑝𝑡); ckptstable ← ckpt 31: if decidedRound < 4 · ckpt.𝑤 then 32: 𝑎𝑑𝑑𝑒𝑑 ← max(added, ckpt.delivered); delivered ← ckpt.delivered 33: state ← ckpt.state; 𝑟 ← max(4 · ckpt.𝑤, 𝑟 ) 34: function pruneUpTo(ckpt) 35: clean DAG, vertexBuffer, pendingCkpts, sup up to ckpt.𝑤 − 𝑔 36:

clean ckptRequests up to ckpt.𝑤

B

vertices, checks them for correctness (ll. 1–2), and carries out backfilling (ll. 3–17) with regards to the current progress of the garbage collection (ll. 18–25). The last code snippet describes the logic of the TEE (Alg. 4) which is: signing valid vertices (ll. 5–11), checking for commits without revealing the anchor (ll. 12–18) and revealing the anchor once it is harmless, such that commits can be checked outside the TEE (ll. 10 and 19–20). Throughout this appendix, we assume that the number of nodes 𝑛 is exactly 𝑛 = 2𝑓 + 1.

Proofs

In the following we prove the correctness of Pangolin’s commit rules and garbage collection respectively. We further provide a theoretical analysis of the impact of garbage collection on the performance of Pangolin and construct an attack against Narwhal’s existing approach of garbage collection. B.1

Pangolin’s BAB

We first show that Pangolin without garbage collection solves the Byzantine Atomic Broadcast problem (BAB problem) by deriving its correctness from DAG-Rider [45] and TEE-Rider [49]. TEE-Rider adapts DAGRider to 𝑛 ≥ 2𝑓 +1 by replacing its reliable broadcast with a TEE-based one and 17

Algorithm 3 Pangolin Reliable Broadcast: Broadcast Logic for Process 𝑝𝑖 1: upon vertex(𝑝𝑘 , 𝑣) 2: if 𝐷𝐴𝐺 [𝑣 .𝑟 ] [𝑣 .𝑝] ≠ ⊥ ∨ ¬verify(𝑣 .𝜎, 𝑣, 𝑣 .𝑝) then abort 3: for 𝑝 𝑗 ∈ 𝑃 do requestHistoryFrom(𝑣, 𝑝 𝑗 ) 4: if ¬(irrelevant(𝑣 .𝑟, 𝑣.𝑝) ∨ outOfWindow(𝑣 .𝑟 )) then 5: vertexBuffer [𝑣 .𝑝] [𝑣 .𝑟 ] ← 𝑣 6: else if ¬irrelevant(𝑣 .𝑟, 𝑣.𝑝) then 7: send ⟨𝐵𝐴𝐶𝐾𝐹 𝐼𝐿𝐿_𝑅𝐸𝑄, 𝑣 .𝑟, 𝑣.𝑝⟩ to 𝑝𝑘 ⊲ 𝑣 fits into the receiving window when it is delivered by the RB again 8: upon backfill_req(𝑝𝑘 , 𝑟 ′, 𝑝 𝑣 ) 9: if deleted(𝑟 ′ ) then 10: send ⟨𝑆𝑇 𝐴𝑇 𝐸_𝑇 𝑅𝐴𝑁 𝑆𝐹 𝐸𝑅, 𝑐𝑘𝑝𝑡𝑠𝑡𝑎𝑏𝑙𝑒 ⟩ to 𝑝𝑘 11: else 12: 𝑣 ← 𝐷𝐴𝐺 [𝑟 ′ ] [𝑝 𝑣 ] 13: if 𝑣 ≠ ⊥ then send ⟨𝑉 𝐸𝑅𝑇 𝐸𝑋, 𝑣⟩ to 𝑝𝑘 14: function reqestHistoryFrom(𝑣, 𝑝 𝑗 ) 15: for all ℎ ∈ 𝑣.edges do

⊲ the requested content can only be provided by a state transfer

16: if ¬irrelevant(ℎ.𝑟, ℎ.𝑝) ∧ 𝐷𝐴𝐺 [ℎ.𝑟 ] [ℎ.𝑝] = ⊥ ∧ ℎ ∉ vertexBuffer then 17: send ⟨𝐵𝐴𝐶𝐾𝐹 𝐼𝐿𝐿_𝑅𝐸𝑄, ℎ.𝑟, ℎ.𝑝⟩ to 𝑝 𝑗 18: function outOfWindow(𝑟 ′ ) 19: return 𝑟 + 4 · 𝑔 < 𝑟 ′ 20: function irrelevant(𝑟 ′, 𝑝𝑘 ) 21: return deleted(𝑟 ′ ) ∨ 𝑟 ′ ≤ ckptstable .delivered [𝑝𝑘 ] 22: function ignored(𝑟 ′ ) 23: return 𝑟 ′ ≤ 𝑑𝑒𝑐𝑖𝑑𝑒𝑑𝑅𝑜𝑢𝑛𝑑 − 4 · 𝑔 24: function deleted(𝑟 ′ ) 25: return 𝑟 ′ ≤ 4 · (ckptstable .𝑤 − 𝑔)

Algorithm 4 Pangolin TEE: TEE Secret and Verification for Process 𝑝𝑖 1: state 𝑠𝑘𝑖 : private key of the TEE 2: state 𝑟 max : N0 maximum round of a vertex the TEE signed, initialized with 0 3: state CPRNG : random number generator 4: state sup : set of supporters per anchor 5: function enclave_sign(𝑣) 6: if 𝑣 .𝑟 ≤ 𝑟 max then abort 7: if |{(𝑝, 𝑟 ′ ) ∈ 𝑣.𝑒𝑑𝑔𝑒𝑠 |𝑟 ′ = 𝑣.𝑟 − 1}| < 𝑓 + 1 ∨ ¬∀ℎ ∈ 𝑣 .edges : verify(ℎ.𝜎, ℎ, ℎ.𝑝) then abort 8: if ∃ℎ ∈ 𝑣.𝑒𝑑𝑔𝑒𝑠 : ℎ.𝑝 = 𝑝𝑖 ∧ ℎ.𝑟 = 𝑟𝑚𝑎𝑥 then 9: 𝑟𝑚𝑎𝑥 ← 𝑣.𝑟 𝑟

10: if 𝑟 max mod 4 = 0 then reveal sup[: 𝑟 max ], CPRNG( max ⊲ reveals commit objects from previous waves 4 − 1) 11: return sign(𝑣, 𝑠𝑘𝑖 ) 12: function check_commit(𝑣) ⊲ is calculated out of enclave if commit objects operated on are already revealed 13: if ¬verify(𝑣 .𝜎, 𝑣, 𝑣 .𝑝) then return ⊥ 14: 𝑝𝑢 ← CPRNG(𝑣.𝑤) 15: for 𝑖 = 2...0 do 16: 17: 18: 19: 20:

anchorRound ← 4 · 𝑣.𝑤 + 𝑖; 𝑢 ← (𝑝𝑢 , anchorRound) if ({𝑢} ∪ sup[anchorRound]) ∩ 𝑣 .𝑒𝑑𝑔𝑒𝑠 = ∅ then continue sup[anchorRound] ← sup[𝑎𝑛𝑐ℎ𝑜𝑟𝑅𝑜𝑢𝑛𝑑] ∪ 𝑣 if |{𝑠 ∈ sup[anchorRound] |𝑠.𝑟 = 𝑣.𝑟 }| ≥ 𝑓 + 1 then reveal sup[: 4 · (𝑣.𝑤 + 1)], CPRNG(𝑣 .𝑤); return 𝑢 ⊲ reveals commit objects up to current committable wave

18

shrinking its quorums to ⌈ 𝑛+1 2 ⌉, while leaving the commit rules unchanged. A Byzantine Atomic Broadcast fulfills the following properties [45]: Validity: If a correct replica broadcasts 𝑣, then every correct replica eventually calls a_deliver(𝑣 .𝑝, 𝑣.𝑟, 𝑣 .𝑏𝑙𝑜𝑐𝑘), where 𝑣 .𝑝 denotes the producer, 𝑣.𝑟 the round, and 𝑣.𝑏𝑙𝑜𝑐𝑘 the content of vertex 𝑣. Agreement: If a correct replica calls a_deliver(𝑣.𝑝, 𝑣 .𝑟 , 𝑣.𝑏𝑙𝑜𝑐𝑘), then every other correct replica calls a_deliver(𝑣.𝑝, 𝑣.𝑟 , 𝑣.𝑏𝑙𝑜𝑐𝑘) eventually. Integrity: For each vertex 𝑣 uniquely identified by (𝑣.𝑝, 𝑣.𝑟 ), a correct replica calls a_deliver(𝑣.𝑝, 𝑣.𝑟, ·) at most once. Total Order: If a correct process calls a_deliver(𝑣.𝑝, 𝑣 .𝑟 , 𝑣.𝑏𝑙𝑜𝑐𝑘) before a_deliver(𝑣 ′ .𝑝, 𝑣 ′ .𝑟, 𝑣 ′ .𝑏𝑙𝑜𝑐𝑘), then no correct process calls a_deliver(𝑣 ′ .𝑝, 𝑣 ′ .𝑟, 𝑣 ′ .𝑏𝑙𝑜𝑐𝑘) without first calling a_deliver(𝑣.𝑝, 𝑣.𝑟, 𝑣 .𝑏𝑙𝑜𝑐𝑘). The changes Pangolin introduces to TEE-Rider are (1) three potential anchor slots per wave, (2) checking commit rules in all later rounds within the same wave, and (3) counting support along all edges. Because integrity follows directly from TEE-Rider, we prove validity, agreement, and total order. DAG-based protocols fulfill these guaranties by relying on two properties: (a) anchor connectivity (two consecutive anchors are always connected with a path), and (b) eventual commits (commits happen eventually). We now prove that Pangolin satisfies those two properties.

may try to gain knowledge about the anchor in rounds (𝑤, 2) and (𝑤, 3) of a wave 𝑤, respectively, by querying the TEE to check whether the commit rule is already satisfied. Therefore, we have to show that the common coin is sufficiently ‘hidden’ from a Byzantine attacker. The following Lemma proves that the TEE can hide the common coin sufficiently, such that a commit happens at least with the same probability as in TEE-Rider. The proof follows a game-based security approach in which an attacker tries to prevent a commit by providing the TEE a vertex and learning some information about the anchor of this wave. The attacker faces a fundamental dilemma: if it successfully learns that a replica 𝑝 is the anchor, it inherently loses the ability to halt the commit. Alternatively, if it learns that a replica 𝑝 is not the anchor, the actions taken to gain this information carry a high risk of inadvertently committing the correct anchor, ensuring a successful commit with probability larger than a half. Lemma B.2 (Hidden Common Coin). The expected number of waves until a correct process observes the direct commit rule to be fulfilled is below 2. Proof. Let A be an attacker that tries to prevent the direct commit of an anchor 𝑢. Assume that A lets the TEE check if the direct commit rule in round (𝑤, 𝑖), 𝑖 ∈ {2, 3} is fulfilled, by providing a set of validated vertices 𝑆𝑖 from round (𝑤, 𝑖). More explicitly, 𝑆𝑖 , 𝑖 ∈ {2, 3} is the set of vertices the attacker shows to the TEE using check_commit (Alg. 4, l. 12) and which could possibly support an anchor in an earlier round. Case 1: The TEE responds with “𝑢 is the anchor”. Then 𝑆𝑖 contains at least 𝑓 + 1 vertices that have a path to 𝑢. By quorum intersection, each vertex in round (𝑤, 𝑖 + 1) ≤ (𝑤, 4) will have a path to 𝑢 and hence 𝑢 will be committed in round (𝑤, 4) at the latest. Therefore, A does not succeed in preventing the commit. Case 2: The TEE responds with “none”. Then A learns that a set of vertices 𝑈¯ , 𝑢 ∉ 𝑈¯ from round (𝑤, 1), which would have sufficient support in 𝑆𝑖 to fulfill the direct commit rule, are not the anchor. We call this operation requesting 𝑈¯ . We now show that each time 𝑡 ∈ N the attacker A requests the TEE using check_commit with a set 𝑆𝑡 = 𝑆 2𝑡 ∪ 𝑆 3𝑡 of vertices that provide sufficient support to directly commit a set of vertices 𝑈¯𝑡 , the probability that A loses by accidentally hitting case 1 instead of case 2, is sufficiently high to ensure a commit with probability > 12 . The probability that A loses at the 𝑡 th request can be modeled Ð by a bino|𝑈¯𝑡 − 𝑡 ′ <𝑡 𝑈¯𝑡 ′ | Ð mially distributed random variable 𝑋𝑡 ∼ 𝐵( 2𝑓 +1− ) | 𝑡 ′ <𝑡 𝑈¯𝑡 ′ | with a hit probability, which is the number of requested vertices 𝑈¯ not covered in previous requests divided by the number of vertices that could possibly still be the anchor. Combining Í the requests, the Í probability for A to lose the game is: 𝑡 P[𝑋𝑡 = 1] = 𝑡 P[𝑋𝑡 = 1|𝑋 1 = ... = 𝑋𝑡 −1 = Î 0] 𝑡𝑡 ′−1 =1 P[𝑋𝑡 ′ = 0] = expression ★ below. Wlog. A provides support 𝑆𝑡 such thatÐat each TEE request a single vertex is requested, hence |𝑈¯𝑡 − 𝑡 ′ <𝑡 𝑈¯𝑡 ′ | = 1 since adding multiple

Lemma B.1 (Anchor Connectivity). If a process directly commits an anchor 𝑢, then there is a path from 𝑢 to every anchor 𝑢 ′ that might be committed in a future round. Proof. Let 𝑢 be an anchor that is directly committed by a correct process 𝑝𝑐 . Let 𝑢 ′ be an anchor of a future round. Case 1: 𝑢.𝑤 = 𝑢 ′ .𝑤. Then 𝑢 and 𝑢 ′ are connected with a path, because 𝑢 and 𝑢 ′ were proposed by the same replica and the TEE guarantees that a replica always references its own vertices (Algorithm 4, l. 9). Case 2: 𝑢.𝑤 < 𝑢 ′ .𝑤. Because 𝑢 is directly committed, there is a round (𝑢.𝑤, 𝑖) in which at least 𝑓 + 1 vertices have a path to 𝑢. Therefore, because replicas reference their own vertices, starting in round (𝑢.𝑤, 4), there are 𝑓 + 1 replicas that have a path to 𝑢. A vertex from a future round must reference at least 𝑓 + 1 replicas. By quorum intersection, at least one of these replicas references 𝑢. Therefore, every vertex of future waves, including 𝑢 ′ has a path to 𝑢. □ Based on anchor connectivity, we can show that the total order property holds. Moreover, if commits happen eventually, DAG-Rider’s [45] proofs of validity and agreement in Propositions 3 and 4 apply directly. Before we show the former, we prove the latter. We therefore have to show that Pangolin commits occur with finite expectation. In TEERider [49], commits occur with probability 12 because the common coin of a wave 𝑤 is completely hidden until the end of round (𝑤, 4). However, in Pangolin a malicious replica 19

vertices to the set of committable vertices at the same time would be worse than requesting them successively. Then if A requests 𝑘 ≤ 2𝑓 + 1 vertices, it loses with probability

bounded receiving window, (2) state transfers as responses to backfilling requests for vertices that are already garbage collected, (3) ignoring vertices prior to the GC barrier during commits, and (4) actively waiting for checkpoint stabilization by checking commit rules whenever a new vertex is added to the DAG, not only when advancing to the next round. First, we show the correctness of Pangolin’s RB-layer (Alg. 3) considering changes (1) and (2). In DAG-Rider the RB-layer is responsible for disseminating and agreeing on vertices that are included in the DAG and thereby delivered by the AB-layer. Pangolin’s AB-layer does not deliver every vertex added to the DAG, only the ones that can be ordered before the GC barrier reaches them. Therefore, vertices that never reach the point of delivery do not necessarily have to reach the point of RB-Agreement. Additionally, a state transfer (2) might cause the execution of transactions from vertices that did not yet get RB-delivered, which renders receiving those vertices unnecessary. As a result, reaching RB-Agreement across all replicas might become irrelevant during runtime for the following vertices:

! 𝑡 −1 Ö 1 1 (1 − ) 2𝑓 + 1 − (𝑡 − 1) 𝑡 ′ =1 2𝑓 + 1 − (𝑡 ′ − 1) 𝑡 =1 ! 𝑡 −1 𝑘 Ö ∑︁ 2𝑓 + 1 − 𝑡 ′ 1 = 2𝑓 + 1 − (𝑡 − 1) 𝑡 ′ =1 2𝑓 + 1 − (𝑡 ′ − 1) 𝑡 =1 ! Î𝑡 −1 𝑘 ′ ∑︁ 1 𝑡 ′ =1 2𝑓 + 1 − 𝑡 = Î ′ 2𝑓 + 1 − (𝑡 − 1) 𝑡𝑡 ′−2 =0 2𝑓 + 1 − 𝑡 𝑡 =1  ∑︁ 𝑘  𝑘 ∑︁ 2𝑓 + 1 − (𝑡 − 1) 1 1 𝑘 = = = 2𝑓 + 1 − (𝑡 − 1) 2𝑓 + 1 2𝑓 + 1 2𝑓 +1 𝑡 =1 𝑡 =1

★=

𝑘 ∑︁

Therefore, every time the attacker A checks whether a vertex is the anchor by querying the TEE, A’s probability to lose the game increases. However, by Lemma 4.3 in TEE-Rider [49] regarding the common core, at least 𝑓 + 1 vertices fulfill the direct commit rule with respect to vertices in round (𝑤, 4). This fact is also true for Pangolin using the same quorum intersection argument. It follows that if A did not lose during requests to the TEE, the probability of 𝑢 to be one of the 𝑓 + 1 committable vertices is 𝑓 +1−𝑘 at least max( 2𝑓 +1−𝑘 , 0). Therefore, the probability that A

Definition B.4 (Vertex Irrelevance). A vertex 𝑣 and its content are considered irrelevant by a replica 𝑝 if one of the following conditions is met: 1. 𝑝 has a stabilized checkpoint covering the execution of 𝑣’s transactions; 2. 𝑝 has a stabilized checkpoint proving that 𝑣’s transactions will never be executed (unless resubmitted); which is equivalent to the predicate irrelevant(𝑣.𝑟, 𝑣.𝑝) ≔ 𝑣 .𝑟 ≤ ckptstable .delivered [𝑣.𝑝] ∨ 𝑣.𝑟 ≤ 4 · (ckptstable .w − 𝑔).

𝑓 +1−𝑘

will lose the game is: 2𝑓𝑘+1 + (1 − 2𝑓𝑘+1 ) max( 2𝑓 +1−𝑘 , 0) = ( 2𝑓 +1−𝑘 𝑓 +1−𝑘 𝑓 +1 𝑘 < 𝑓 + 1 : 2𝑓𝑘+1 + 2𝑓 +1−𝑘 2𝑓 +1 = 2𝑓 +1 > 12 𝑘 ≥ 𝑓 + 1 : 2𝑓𝑘+1 As a result, in each wave a commit happens with probability > 12 . Thus, the expected number of waves until a correct process observes the direct commit rule to be fulfilled is below 2. □

With this definition, we show that the TEE-based RB with changes (1) and (2) fulfills a sufficient variant of RBAgreement – the RB will deliver every vertex that is not already irrelevant – which we can then use to prove the correctness of Pangolin’s BAB-layer (Alg. 1). An illustration of the different stages that a vertex reaches before it gets irrelevant and eventually garbage collected, is given in Figure 11. First, we demonstrate that the backfilling mechanism remains functional because replicas only garbage collect irrelevant vertices. Such vertices are inherently covered by a stable checkpoint that can itself directly serve the backfilling request.

Finally, we will show that Pangolin satisfies the total order property of the BAB problem. Theorem B.3 (Total Order). If a correct process calls a_deliver (𝑣.𝑝, 𝑣.𝑟, 𝑣 .𝑏𝑙𝑜𝑐𝑘) before a_deliver(𝑣 ′ .𝑝, 𝑣 ′ .𝑟, 𝑣 ′ .𝑏𝑙𝑜𝑐𝑘), then no correct process calls a_deliver(𝑣 ′ .𝑝, 𝑣 ′ .𝑟, 𝑣 ′ .𝑏𝑙𝑜𝑐𝑘) without first calling a_deliver(𝑣.𝑝, 𝑣.𝑟, 𝑣 .𝑏𝑙𝑜𝑐𝑘). Proof. By the agreement of the common coin, each wave has only one anchor replica, hence, three anchor vertices. By Lemma B.1 if a correct process directly commits an anchor 𝑢, then there is a path to every anchor 𝑢 ′ that might be committed in a future round. Therefore, by the retrospective commit rule, anchors are committed in the same order. As the anchors’ causal histories are delivered in some deterministic order, which is identical for all correct processes, all correct processes that deliver vertices do so in the same order. □ B.2

Lemma B.5 (Backfilling Response). If a correct replica sends a vertex via message ⟨𝑉 𝐸𝑅𝑇 𝐸𝑋, 𝑣⟩, it will always be able to respond to backfilling requests regarding the vertex and its history. Proof. Let 𝑝𝑐 be a correct replica that sends a vertex 𝑣 with ⟨𝑉 𝐸𝑅𝑇 𝐸𝑋, 𝑣⟩. Then 𝑣 was either proposed by 𝑝𝑐 (Alg. 1, l. 20) or sent due to a backfilling request (Alg. 3, l. 13). In both cases 𝑝𝑐 will directly add or has already added 𝑣 to its local DAG. Every vertex, including 𝑣, is only removed (garbage collected) from the local DAG when a stable checkpoint with

Pangolin’s Garbage Collection

We now show the correctness of Pangolin’s garbage collection (GC). The changes Pangolin’s GC introduces to BAB (Algorithm 1) and RB (Algorithm 3) are (1) the use of a 20

DAG

𝑝3

not yet ordered

direct commit

decided

𝑝1

...

𝑝2

irrelevant

𝑝3

... point 4𝑔 ckptstable of deletion

4𝑔

end of receiving window

missing

future

undecided

ignored()

𝑝2

committed deleted()

vertexBuffer

𝑝1

decidedRound (latestUnstable()) 𝑟

4𝑔

...

...

...

...

outOfWindow()

GC barrier

... 4𝐺 ( 12 ) earliestUnstable()

4𝑔

wait for checkpoint stabilization

Figure 11. Example of the different stages of a vertex. For simplicity in this example 𝐼 ckpt is set to 1, so a checkpoint is created for every committed anchor in the first round of a wave. Once a valid vertex 𝑣 (𝑣.𝑟 > 𝑟 ) is received by a replica, it is put into the future of the vertexBuffer. As soon as the round of the vertex is reached (𝑣.𝑟 = 𝑟 ) and all its causal history is present (or irrelevant) in the DAG, 𝑣 is added to the DAG as undecided. When 𝑣 is in the causal history of a commit, 𝑣 gets decided, which happens in 𝑋 ∼ 4𝐺 ( 21 ) rounds (𝐺 denotes the geometric distribution). This means that 𝑣 is either delivered if the previous committed anchor is less than 4𝑔 rounds ahead (¬ignored(𝑣.𝑟 ) ⇐⇒ decidedRound − 4𝑔 < 𝑣.𝑟 ), or ignored. When the checkpoint produced at the commit that decided 𝑣 is stabilized, which must happen at most 4𝑔 rounds after the round of the checkpoint (4 · earliestUnstable().𝑤 + 4𝑔 ≤ 𝑟 ), 𝑣 gets irrelevant. Finally, once a checkpoint with a round more than 4𝑔 rounds ahead of 𝑣.𝑟 gets stabilized, the garbage collection takes effect and 𝑣 is deleted. 𝑣.𝑟 ≤ 4 · (ckpt.𝑤 − 𝑔) has been obtained (Alg. 2, l. 35). Therefore, the stable checkpoint either covers the execution of 𝑣’s transactions (𝑣 .𝑟 ≤ ckptstable .delivered [𝑣.𝑝]) or proves that 𝑣 is ignored (Alg. 1, l. 33) and its transactions are never executed ((𝑣 .𝑟 ≤ 4·(ckptstable .𝑤 −𝑔)), which is all the information to render 𝑣 irrelevant. As a result, if 𝑝𝑐 needs to respond to a backfilling request for 𝑣, 𝑝𝑐 either still stores the vertex or can respond with a checkpoint that renders 𝑣 irrelevant. Furthermore, because 𝑝𝑐 added 𝑣, every vertex in 𝑣’s causal history is either present in the local DAG of 𝑝𝑐 or irrelevant due to a stable checkpoint (Alg. 1, l. 11). Therefore, 𝑝𝑐 can also respond to backfilling requests regarding 𝑣’s history. □

eventually add the vertex to its local DAG or reach a point in which the vertex is considered irrelevant. Proof. Let 𝑝 be a correct replica that receives a vertex 𝑣 from another correct replica 𝑝𝑐 . Then, 𝑝 requests 𝑣’s missing causal history 𝐻 that is not already irrelevant from 𝑝𝑐 (Alg. 3, ll. 3, 14–17). If 𝑣 does not fit into the vertex buffer and is not already irrelevant, 𝑝 will also request 𝑣 from 𝑝𝑐 (ll. 6, 7) again. We now prove by induction that every vertex in 𝐻 ∪ {𝑣 } will eventually be added to 𝑝’s DAG or be considered irrelevant. Base Case: Let ℎ ∈ 𝐻 ∪ {𝑣 } be a vertex with the smallest round 𝑝 requests from 𝑝𝑐 . After Lemma B.5 𝑝𝑐 will respond to the backfilling request, which is why 𝑝 will either receive ℎ or receive a checkpoint that renders ℎ irrelevant. Once 𝑝 receives ℎ, ℎ can directly be added to the local DAG because ℎ’s history is either present or irrelevant as ℎ is the earliest missing vertex (Alg. 1, l. 11). Induction Assumption: Assume 𝑝 eventually adds every vertex ℎ ∈ 𝐻 ∪ {𝑣 } up to a fixed but arbitrary round 𝑟 < 𝑣.𝑟 to the local DAG or renders it irrelevant. Induction Step: Let ℎ ∈ 𝐻 ∪ {𝑣 } be a missing vertex with ℎ.𝑟 = 𝑟 + 1 that 𝑝 requested from 𝑝𝑐 . After Lemma B.5 𝑝𝑐 will respond to the backfill request, which is why 𝑝 will receive ℎ or receive a checkpoint that renders ℎ irrelevant. Once 𝑝

Next, we show that although a replica might need to discard vertices that fall too far ahead of its local progress, it will eventually recover them. Before discarding such a vertex, the replica requests its causal history—including the vertex itself—via backfilling. Eventually, the replica receives sufficient history to advance its local progress, allowing the vertex to fall within its valid receiving window. Lemma B.6 (Receiving Window Sufficiency). If a correct replica receives a vertex from another correct replica, it will 21

receives ℎ, there are three cases. Case 1: ℎ fits into the receiving window of 𝑝 and is not considered irrelevant (3, ll. 4, 5). Then ℎ will eventually be added to the local DAG or rendered irrelevant, as by induction assumption, eventually ℎ’s history will arrive or will be considered irrelevant. Case 2: ℎ does not fit into the receiving window of 𝑝 and is not considered irrelevant (3, ll. 6, 7). Then 𝑝 requests ℎ from 𝑝𝑐 again until by induction assumption eventually its history arrives or ℎ or it’s history are considered irrelevant. Case 3: ℎ is already considered irrelevant. By induction, 𝑝 will eventually add 𝑣 to its DAG or consider 𝑣 irrelevant. □

by the direct and retrospective commit rule, 𝑣 would have already been delivered. Therefore, 𝑢.𝑟 > decidedRound which is why 𝑢 will be committed. Additionally, because the commit rules ensure that correct replicas commit anchors in the same order, when 𝑝 commits 𝑢, 𝑝’s value of decidedRound equals 𝑝𝑐 ’s value of decidedRound when 𝑝𝑐 committed 𝑢. Thereby, committing 𝑢 will a_deliver 𝑣 because 𝑣 is undelivered and will not be ignored (Alg. 1, l. 33; Alg. 3, ll. 22, 23). Case 2: 𝑝 considers 𝑣 ′ irrelevant due to a state transfer. Then, the state process 𝑝 was transferred to was valid, which means that 𝑓 + 1 replicas claimed to have encountered the same checkpoint. At least 𝑓 + 1 − 𝑓 = 1 of these replicas is correct and has genuinely encountered the checkpoint. This correct replica 𝑝𝜎 has committed an anchor 𝑢 ′ with 𝑢.𝑤 ≤ 𝑢 ′ .𝑤 the checkpoint belongs to. Case 2.1: 𝑝𝜎 added 𝑣 ′ to its local DAG. Then, following case 1 𝑝𝜎 did a_deliver 𝑣 which means that 𝑣’s transactions are already applied in the state 𝑝 is transferred to. Case 2.2: 𝑝𝜎 considers 𝑣 ′ irrelevant due to a state transfer. Then this state transfer regarded a checkpoint of an anchor 𝑢 ′′ with 𝑣 ′ .𝑤 ≤ 𝑢 ′′ .𝑤 < 𝑢 ′ .𝑤. Inductively following case 2.2 down to 𝑣 ′ .𝑤, there must be a correct signer that matches case 2.1 and therefore 𝑝 was forwarded to a state in which 𝑣’s transactions are already applied to the state. Because 𝑝 is arbitrary, every correct replica will eventually a_deliver 𝑣 or reach a state in which 𝑣’s transactions are already applied to the state. □

Combining the two Lemmata we can provide a weaker form of RB-Agreement. Theorem B.7 (Partial RB-Agreement). If a correct replica adds a vertex to its local DAG, every other correct replica will either do so as well or reach a point where the vertex is considered irrelevant. Proof. Let 𝑝𝑐 be a correct replica that adds a vertex 𝑣 to its local DAG. Then 𝑝𝑐 will eventually broadcast a vertex 𝑣 ′ that references 𝑣. Let 𝑝 be a different correct replica. Because of perfect links, 𝑝 will eventually receive 𝑣 ′ . Following Lemma B.6, 𝑝 will eventually add 𝑣 ′ including its history 𝑣 to its local DAG or consider it irrelevant. Because 𝑝 is arbitrary, every correct replica will eventually add 𝑣 to their local DAG or consider 𝑣 irrelevant. □

Ultimately, Pangolin’s garbage collection does not compromise the safety of the BAB. This is because bounding the rounds ahead of local progress retains sufficient state for the RB and commit rule evaluation, while bounding the rounds behind local progress affects all replicas consistently. We now provide an intuition for the liveness of Pangolin’s AB-layer, by explaining why waiting for checkpoint stabilization (4) does not result in a deadlock. Notice that the previous scenarios sometimes required replicas to move on to the next round, which can only happen if waiting for checkpoint stabilization does not cause any deadlocks.

After proving that the RB-layer still fulfills a weaker variant of RB-Agreement, we now prove that the RB-Agreement is sufficient for the correctness of Pangolin’s BAB. Furthermore, we explain why change (3), which includes ignoring vertices before the GC offset at delivery, does not affect ABAgreement. This is because if a single correct replica decides to deliver and not ignore a vertex and thereby execute its transactions, every other correct replica will do so as well. Theorem B.8 (AB-Agreement). If a correct replica calls a_deliver(𝑣.𝑝, 𝑣.𝑟, 𝑣 .𝑏𝑙𝑜𝑐𝑘) for a vertex 𝑣, every other correct replica will either do so as well or reach a state in which 𝑣’s transactions are already applied to the state.

Theorem B.9 (Checkpoint Stabilization). A correct replica only waits for the stabilization of a checkpoint for a finite period of time.

Proof. Let 𝑝𝑐 be a correct replica that a_delivers a vertex 𝑣. Then 𝑝𝑐 directly committed an anchor 𝑢 that references 𝑣. Afterwards, 𝑝𝑐 will broadcast a vertex 𝑣 ′ that references every vertex that 𝑢 requires to fulfill the direct commit rule. Following partial RB-Agreement (Theorem B.7), every correct replica will eventually add 𝑣 ′ to its local DAG or consider 𝑣 ′ irrelevant. Let 𝑝 be another correct replica that did not already a_deliver 𝑣. Case 1: 𝑝 adds 𝑣 ′ to its local DAG. Then when receiving 𝑣 ′ , 𝑝’s DAG contains the information to directly commit 𝑢. No commit in a round further than 𝑢.𝑟 could have been triggered because otherwise, following the order properties ensured

Proof. Let 𝑝𝑐 be a correct replica that waits for the checkpoint signature for a checkpoint ckpt with wave ckpt.𝑤 of a correct replica 𝑝 (Alg. 1, l. 14). Then 𝑝𝑐 has broadcast a vertex 𝑣 that references every vertex necessary to observe the commit of ckpt.𝑤. Case 1: 𝑝 has progressed to a round 𝑟 with 𝑣 .𝑟 ≤ 𝑟 . Then, even if 𝑝 does not continue to the next round because 𝑝 itself is waiting for checkpoint stabilization, 𝑝 will eventually add 𝑣 to its local DAG or consider 𝑣 irrelevant, following RBAgreement (Theorem B.7). Case 2: 𝑝 has only progressed to a round 𝑟 < 𝑣 .𝑟 . Then 22

𝑝 will eventually progress to a round 𝑣.𝑟 ≤ 𝑟 ′ because by inductively following case 2 until the least progressed replica where only case 1 is relevant 𝑝𝑐 will not wait infinitely for checkpoint stabilization. Therefore, 𝑝 will eventually add 𝑣 to its local DAG following RB-Agreement (Theorem B.7) or consider 𝑣 irrelevant. In both cases, 𝑝 eventually adds 𝑣 to its local DAG or considers 𝑣 irrelevant. Case 1: 𝑝 considers 𝑣 irrelevant. This means that 𝑝 either encountered ckpt during execution and can answer the checkpoint request (Alg. 2, ll. 11, 12, 22–27), or has a stable checkpoint that renders 𝑣 and thereby 𝑐𝑘𝑝𝑡 irrelevant and can transfer 𝑝𝑐 to a state where stabilizing ckpt is no longer necessary (Alg. 2, l. 13). Case 2: 𝑝 adds 𝑣 to its local DAG. Then, 𝑝 will commit 𝑐𝑘𝑝𝑡 (if it has not already) and answer the checkpoint request because 𝑣 references all the vertices necessary to observe the commit (Alg. 1, l. 38). Because 𝑝 is arbitrary, every correct replica will eventually respond to 𝑝𝑐 ’s checkpoint signature request. Because there are at least 2𝑓 +1−𝑓 = 𝑓 +1 correct replicas, 𝑝𝑐 can eventually stabilize 𝑐𝑘𝑝𝑡 (Alg. 2, ll. 19–21, 36) and continue to the next round. □ B.3

replica. Then 𝑝 𝑗 receives 𝑣 at 𝑡 0 +𝑙𝑖 𝑗 . If 𝑝 𝑗 cannot directly add 𝑣 to its local DAG due to missing parts of 𝑣’s causal history, 𝑝 𝑗 requests the missing history from 𝑝𝑖 . Then 𝑝 𝑗 will receive the missing vertices until 𝑡 0 + 𝑙𝑖 𝑗 + 𝑙 𝑗𝑖 + 𝑙𝑖 𝑗 < 𝑡 0 + 2𝑅𝑇𝑇slowest . After receiving 𝑣’s causal history, which fits into the receiving window because the progress difference between replicas is below 2𝐶 < 4𝑔, process 𝑝 𝑗 will at least reach round 𝑣.𝑟 , which was the round of the fastest quorum when 𝑣 was proposed. Because broadcasting a vertex in the fastest quorum takes 𝑙 fastest , in that time the fastest quorum can slowest make ⌊ 2𝑅𝑇𝑇 𝑙 fastest ⌋ ≤ 2𝐶 rounds of progress. Therefore, 𝑝 𝑗 lags at most 2𝐶 < 4𝑔 rounds behind the fastest quorum at all times. □ As a result, receiving vertices outside of the receiving window (1) as well as state transfers (2) do not take place in times of proportional network latencies. Additionally, the probability of vertices proposed by correct replicas to be ignored before the point of delivery is negligible ("AB-Validity"), which guarantees timely fairness (3) and actively waiting for checkpoint stabilization is not required during periods of proportional network latencies (4). The last two properties will be shown in the following. Finally, combining Propositions B.11, B.12, and B.13, GC does not affect the performance of the protocol under proportional network latencies, which we refer to as the common case.

Theoretical Performance Analysis of Pangolin’s Garbage Collection

In the following, we show that under common WAN latencies, the proposed GC of Pangolin does not affect the performance of the protocol. Using the single communication step of a TEE-based RB, the difference in progress (in rounds) between replicas remains below the offset of the GC and the size of the receiving window 𝑔, when 𝑔 is appropriately dimensioned.

Proposition B.12 (Timely Fairness). Assume proportional network latencies. The vertices proposed by correct replicas are never garbage collected before the point of delivery ("ABValidity") if 4𝑔 ≥ 4𝐶 + 2. Proof. Let 𝑝𝑖 be a correct replica that proposes a vertex 𝑣 at time 𝑡 0 . Let 𝑝 𝑗 be another correct replica. Then 𝑝 𝑗 adds 𝑣 to its local DAG at 𝑡 0 + 𝑙𝑖 𝑗 + 𝑙 𝑗𝑖 + 𝑙𝑖 𝑗 < 𝑡 0 + 2𝑅𝑇𝑇slowest . Following Lemma B.11, 𝑝𝑖 lags at most 2𝐶 rounds behind 𝑝 𝑗 at 𝑡 0 . Because in a period of 2𝑅𝑇𝑇slowest process 𝑝 𝑗 can slowest only progress ⌊ 2𝑅𝑇𝑇 𝑙 fastest ⌋ ≤ 2𝐶 further rounds, 𝑝 𝑗 adds 𝑣 to its local DAG in round 𝑣.𝑟 + 4𝐶. Therefore, 𝑝 𝑗 references 𝑣 in round 𝑣.𝑟 + 4𝐶 + 1. Because 𝑝 𝑗 was arbitrary, it follows that all 𝑓 + 1 correct replicas reference 𝑣 by round 𝑣 .𝑟 + 4𝐶 + 1. By quorum intersection, this means that every vertex in round 𝑣 .𝑟 + 4𝐶 + 2 references 𝑣. Suppose 𝑣 is garbage collected before the point of delivery, then there is a stable checkpoint ckptstable with 𝑣 .𝑟 ≤ 4·(ckptstable .𝑤 −𝑔). Therefore, 4ckptstable .𝑤 ≥ 𝑣 .𝑟 + 4𝑔. Because we assume 4𝐶 + 2 ≤ 4𝑔, it holds that 4ckptstable .w ≥ 𝑣.𝑟 + 4𝐶 + 2, which means that the anchor of 𝑐𝑘𝑝𝑡𝑠𝑡𝑎𝑏𝑙𝑒 references 𝑣, and hence, 𝑣 got delivered. □

Definition B.10 (Proportional Network Latencies). Let 𝑙𝑖 𝑗 with 𝑖, 𝑗 ∈ {1, ..., 𝑛} be the latency of a message sent from replica 𝑝𝑖 to replica 𝑝 𝑗 . Then, 𝐿 = {𝑙𝑖 𝑗 ∈ R>0 |𝑖, 𝑗 ∈ {1, ..., 𝑛}, 𝑖 ≠ 𝑗 } describes the set of latencies between replicas participating in the protocol. Let 𝑙 fastest = min𝑆 ⊂ {1,...,𝑛},|𝑆 |=𝑓 +1 {max{𝑙𝑖 𝑗 |𝑖, 𝑗 ∈ 𝑆, 𝑖 ≠ 𝑗 }} be the maximum latency between replicas in the fastest quorum and 𝑅𝑇𝑇slowest = max{𝑙𝑖 𝑗 + 𝑙 𝑗𝑖 |𝑖, 𝑗 ∈ {1, ..., 𝑛}, 𝑝𝑖 , 𝑝 𝑗 are correct} the maximum round trip time (RTT) between correct replicas. Proportional network latencies ensure: slowest 1. ⌊ 𝑅𝑇𝑇 𝑙 fastest ⌋ ≤ 𝐶 ∈ N 2. 𝐶 is known to all replicas.

Proposition B.11 (Progress Difference). Assume proportional network latencies. At all times the progress difference between replicas is below 2𝐶 rounds if 4𝑔 ≥ 2𝐶 + 1.

Proposition B.13 (Expected Checkpoint Stabilization). Assume proportional network latencies. The probability of waiting for checkpoint stabilization is negligible in 𝜆 if 4𝑔 ≥ 5𝐶 +1+4𝜆.

Proof. Assume that until now the progress difference between replicas was below 2𝐶. Let 𝑣 be a vertex proposed by one of the at least 𝑓 + 1 − 𝑓 = 1 correct replicas in the fastest quorum, denoted by 𝑝𝑖 , at time 𝑡 0 . Let 𝑝 𝑗 be another correct

Proof. Let 𝑝𝑖 be a correct replica that creates a checkpoint ckpt. Then ckpt was created due to a direct commit in wave 23

𝑤 ′ ≥ ckpt.𝑤. Because a direct commit happens with probability of at least 12 , ckpt is created before wave ckpt.𝑤 + 𝑋 , where 𝑋 denotes a geometrically distributed random variable with mean at least 2. After creating ckpt, 𝑝𝑖 will broadcast a vertex 𝑣 in round 4 · (ckpt.𝑤 + 𝑋 ) + 1, which references every vertex necessary to observe the commit of ckpt. In round 4 · (ckpt.𝑤 + 𝑋 ) + 1 + 4𝐶 every correct replica will have added 𝑣 to its local DAG (see Theorem B.12), which causes the commit of ckpt and a response to the checkpoint signature request. Replica 𝑝𝑖 will receive the response of a correct replica 𝑝 𝑗 after 𝑙 𝑗𝑖 ≤ 𝑅𝑇𝑇slowest , in which 𝑝𝑖 has not progressed further than round 4 · (ckpt.𝑤 + 𝑋 ) + 1 + 4𝐶 + 𝐶. Thus, the probability of waiting for checkpoint stabilization is P[4 · (ckpt.𝑤 + 𝑔) < 4ckpt.𝑤 + 4𝑋 + 1 + 5𝐶] = P[4𝑔 < 5𝐶 + 1 + 4𝑋 ]. Therefore, the probability of process 𝑝𝑖 waiting for checkpoint stabilization scales with P[𝑋 > 𝜆] ≤ 21𝜆 which is negligible in the tolerance 𝜆 that 𝑔 offers. □

B.4

Vertex Buffer Overflow Attack

In the following, we construct adversarial network latencies that cause a correct replica operating a DAG-based consensus instance on a Narwhal based Mempool (e.g. [25], [64]) to receive messages ahead of its local progress. These messages will flood and exceed the replica’s memory bounds. Let 𝑝𝑐 be a correct replica that is cut off from all other replicas but a single faulty replica 𝑝 𝑓 due to adversarial network conditions. From now on 𝑝 𝑓 will refuse to answer 𝑝𝑐 ’s backfilling requests, but will continue to send all of its blocks to 𝑝𝑐 . Replica 𝑝𝑐 cannot add these blocks to its DAG as they are ahead of 𝑝𝑐 ’s local progress. Because garbage collection does only target the DAG structure, 𝑝 𝑓 ’s blocks will, after a finite amount of time, exceed 𝑝𝑐 ’s memory capacity. Pangolin addresses this attack by garbage collecting the vertexBuffer, which results in memory bounds that are finite in expectation at all times. Pangolin naturally enforces garbage collection for the vertexBuffer by using a bounded receiving window. By relying on backfilling and ensuring that there is a correct replica that can answer the backfilling request, blocks outside the receiving window can be safely discarded.

As a result, by choosing 𝑔 ≥ 5𝐶+1 4 + 𝜆, besides using bandwidth for checkpoint stabilization, for high enough 𝜆 the performance of Pangolin is unaffected by GC in the common case. During periods of network partitions, Pangolin maintains liveness but requires state transfers to recover replicas that have fallen behind. For example, in the AWS deployment with 13 replicas (see Table 3) we have 𝑅𝑇𝑇slowest ≈ 199.2 ms and 𝑙 fastest ≈ 57 ms which results in 𝐶 = 3, thus 𝑔 = 4 + 𝜆. For 𝜆 ≔ 20 the probability of waiting for checkpoint stabilization is below 0.0001%. Thus, setting 𝑔 ≔ 24 could be sufficient.

C

Evaluation Appendix

C.1

Deployment

Table 3 gives the delays we configure. They are derived from the 𝑝 50 round-trip times reported by Cloudping [1], aggregated over a period of a year ending 2025-12-23: for each pair we average the two measured directions and halve the result to obtain the one-way delay that netem applies.

Lemma B.14 (Memory Bounds). Pangolin’s BAB and RB |𝑆 | consume 𝑂 ((𝑛|𝑣 | + 𝐼𝑐𝑘𝑝𝑡 ) (𝑔 + 𝐼𝑐𝑘𝑝𝑡 )) memory space with overwhelming probability, where |𝑣 | denotes the size of a vertex and |𝑆 | the size of a checkpoint.

C.2

Metric Aggregation

Each replica records a latency histogram over the measurement window of a run. For a given percentile we compute that percentile per replica, average it across replicas to obtain one value per run, and average across runs. Throughput is the number of requests confirmed to clients per second, averaged over the measurement window of a run and then across runs. Confidence intervals are computed over the per-run values.

Proof. The vertexBuffer can potentially contain all vertices from the latest round that got deleted until 𝑔 waves in the future. Thus, the range of the vertex buffer is (4 · (ckptstable .𝑤 − 𝑔),𝑟 + 4𝑔]. With overwhelming probability, this range is included in (𝑟 − 4𝑔 − 4𝐼𝑐𝑘𝑝𝑡 − 𝐸 − 4𝑔,𝑟 + 4𝑔] = (𝑟 − 8𝑔 − 4𝐼𝑐𝑘𝑝𝑡 − 𝐸,𝑟 + 4𝑔] for some constant 𝐸. In conclusion, the memory consumption of the vertexBuffer is in 𝑂 (𝑛|𝑣 |(𝑔 + 𝐼𝑐𝑘𝑝𝑡 )). A similar argumentation holds for the memory consumption of the DAG. In addition, pendingCkpts stores the last stable checkpoint and all following unstable checkpoints, thus, its range is given by [4ckptstable .𝑤,𝑟 ]. Again, with overwhelming probability, the range is included in [𝑟 − 4𝑔 − 4𝐼𝑐𝑘𝑝𝑡 − 𝐸,𝑟 ] for some constant 𝐸. Due to the checkpoint interval, pend|pendingCkpts| 𝑔 ingCkpts contains at most ⌊ 4𝐼𝑐𝑘𝑝𝑡 ⌋ = 𝐼𝑐𝑘𝑝𝑡 + 1 check-

C.3

Simulated Comparison across 100 Deployments

The simulator. The evaluation in Sect. 5.4 uses a discreteevent network simulator which we originally developed to compare the latency of different DAG protocols. The simulator allows users to specify region-to-region latencies and select host regions for deployed replicas and then models message delays. The broadcast protocols, commit rules and pacemaker design of existing DAG protocols can be easily re-implemented within this framework. Since cryptography is also abstracted away, differences in observed commit latency are attributable to the protocol design itself rather than separate codebases or tuning.

𝑔

points, yielding a memory consumption of |𝑆 |( 𝐼𝑐𝑘𝑝𝑡 + 1). In summary, the total memory consumption of Pangolin’s |𝑆 | BAB and RB is in 𝑂 ((𝑛|𝑣 | + 𝐼𝑐𝑘𝑝𝑡 ) (𝑔 + 𝐼𝑐𝑘𝑝𝑡 )). □ 24

Table 3. One-way network delays [ms] configured with netem between the 13 emulated AWS regions; the diagonal applies between replicas placed in the same region. Regions are named by billing code [2], region identifier and location: USE1 (us-east-1, N. Virginia), USW2 (us-west-2, Oregon), CAN1 (ca-central-1, Canada), EUC1 (eu-central-1, Frankfurt), EU (eu-west-1, Ireland), EUW2 (eu-west-2, London), EUW3 (eu-west-3, Paris), EUN1 (eu-north-1, Stockholm), APS1 (ap-southeast-1, Singapore), APS2 (ap-southeast-2, Sydney), APS3 (ap-south-1, Mumbai), APN1 (ap-northeast-1, Tokyo), APN2 (ap-northeast-2, Seoul). USE1 USW2 CAN1 EUC1 USE1 USW2 CAN1 EUC1 EU EUW2 EUW3 EUN1 APS1 APS2 APS3 APN1 APN2

4.4 32.8 9.4 47.3 35.6 39.6 42.7 57.0 110.2 100.6 96.6 75.6 91.4

2.1 31.0 71.9 59.7 64.9 68.2 77.5 81.7 70.8 112.4 50.0 62.2

2.3 47.3 35.3 40.2 43.7 52.9 110.2 99.6 96.2 78.4 89.9

EU EUW2 EUW3 EUN1 APS1 APS2 APS3 APN1 APN2

2.3 13.9 2.2 8.8 7.2 6.4 10.6 11.9 20.2 81.0 89.1 126.3 128.2 64.3 63.4 114.4 102.4 115.9 118.6

2.1 5.9 15.6 84.9 133.4 59.0 107.7 123.8

2.2 16.3 83.4 140.4 54.9 110.9 127.2

1.7 90.6 136.1 73.9 123.7 125.4

2.2 48.0 32.6 35.9 37.3

2.0 77.8 53.5 73.2

2.0 67.7 67.6

2.3 18.4

2.4

Paired Comparison. Fig. 13 orders the deployments by Pangolin’s own latency. Pangolin wins against the baselines in all 100 deployments. The median paired difference is +99 ms against Mysticeti, +214 ms against Fides, +250 ms against Mahi-Mahi-5, +293 ms against Shoal++, +759 ms against Bullshark, +1,110 ms against Narwhal/Tusk and +1,731 ms against DAG-Rider.

Replicas use reliable point-to-point links for communication whose delay is the one-way delay between their regions, which is taken as half the round-trip time in the matrix of 34 AWS regions (see Figure 12). So two replicas placed in the same region still observe that region’s intra-region delay, usually between 1.1 and 4.4 ms, and only a replica’s message to itself is instantaneous. Delays are also constant per region pair as the simulator models neither jitter, nor loss, nor bandwidth and queuing. The simulator treats timeouts as events in the same event queue as message deliveries, so a pacemaker is driven by the same clock as communication. The simulated time only progresses on events. The simulator is deterministic, for instance, equal timestamps execute in insertion order, so an identical seed can reproduce a simulation run. A DAG protocol is implemented exactly according to its specification using the same broadcast primitive and commitment rules. Every simulation run additionally checks that the committed prefixes of all replicas agree before its measurements are recorded. As important limitations, note that all cryptographic work and execution consume no simulated time. We believe this abstraction favours no particular protocol as every system is credited with free cryptography, and the TEE operations Pangolin relies on are free in the same sense as the signature verification its baselines rely on. Setup. The comparison is paired: All eight protocols run on the same 100 deployments, even though each uses a different fault bound. The sampler picks a deployment’s regions from the seed and the replica set size alone regardless of 𝑓 . Protocol parameters follow the respective papers. For instance, Shoal++ runs three DAGs staggered by 100 ms with a 600 ms round timeout started at the beginning of each round. Additional Results. Table 4 gives the per-configuration medians behind Sect. 5.4. Every cell is the median over the same 100 deployments of the replica-summary statistic defined in § C.2.

Cumulative latency distributions. Fig. 14 shows the same comparison at two quantiles. At the median the eight protocols can be visually cleanly separated; only Mahi-Mahi5 and Shoal++ touch at the top of their distributions. When looking at the tail latency (𝑝 90 ) the gap of Pangolin to Mysticeti narrows to 1.12×, and at 𝑝 99 it closes to 1.02×, winning on 66 of 100 deployments. The advantage Pangolin holds in the median is thus larger than the advantage it holds in the tail, which matches the behaviour § 5.3 observes on the testbed for real execution. Threats to validity. The simulator abstracts cryptography and models the network as fixed per-pair delays, so these are block decision latencies for network-bound configurations and are not comparable with the end-to-end request latencies of § 5.2. Also the experiment evaluates whole protocols rather than mechanism, so it ranks protocol designs but does not attribute the ranking to individual mechanisms. All simulation runs are fault-free. C.4

Comparison on Mysticeti’s Deployment Scenario

To generate Figure 2, we use the Method of Sect. C.3 but with a single deployment scenario, which is the 13-region deployment, Mysticeti was originally evaluated in. We evaluate block commit latency of selected protocols under identical network conditions. To evaluate the average block decision latency, we replicate the experimental setup of Mysticeti [9], 25

RTT [ms] af-south-1 4 352 283 358 386 373 278 290 319 409 336 420 325 443 345 224 294 156 154 174 194 138 159 150 146 235 281 250 286 338 228 241 287 274 ap-east-1 353 3 30 53 40 50 99 81 38 129 55 141 45 162 66 205 165 194 189 213 185 206 261 203 200 244 127 132 216 318 209 198 156 146

450

ap-east-2 281 22 5 37 65 35 118 97 58 153 78 165 65 180 90 182 144 219 214 239 210 216 235 244 214 262 150 151 196 291 181 170 142 132 ap-northeast-1 358 52 38 5 37 11 135 116 72 106 88 138 78 147 100 157 114 228 223 247 219 234 205 215 222 279 171 176 167 261 151 140 109 100

400

ap-northeast-2 387 39 66 37 5 27 135 117 75 147 92 157 81 173 102 180 142 231 226 250 222 230 237 248 254 283 163 167 196 294 183 173 134 125 ap-northeast-3 373 49 36 12 27 3 139 121 78 122 95 134 85 153 106 157 120 235 230 253 226 234 215 225 232 287 167 172 173 271 161 150 111 101 ap-south-1 278 98 127 136 135 139 4 23 65 156 83 167 72 190 94 193 247 129 118 147 114 145 127 118 110 155 32 39 253 302 194 206 235 225 ap-south-2 294 82 111 120 121 125 27 8 52 143 68 154 59 178 80 212 230 149 139 167 133 157 147 138 130 170 50 56 275 320 210 220 220 209

350

ap-southeast-1 320 38 65 72 75 77 65 48 4 96 20 106 11 127 31 220 180 162 156 181 153 171 179 170 167 211 92 99 241 329 221 209 173 163 ap-southeast-2 409 129 155 108 146 122 156 139 95 4 113 15 102 31 124 200 161 252 247 272 243 273 257 267 281 303 183 190 213 313 202 195 140 142 ap-southeast-3 332 53 79 86 89 92 79 62 18 110 3 122 25 141 46 237 195 176 171 196 167 174 193 183 180 226 107 113 256 344 236 224 188 177 ap-southeast-4 419 140 165 138 156 132 166 149 105 14 123 4 112 43 134 210 173 263 258 282 253 287 267 277 291 314 193 199 223 323 212 202 150 152

300

ap-southeast-5 322 44 70 76 79 83 70 52 10 100 27 112 3 132 27 228 186 166 161 186 157 165 182 173 172 217 97 103 248 334 228 216 178 167

Source Region

ap-southeast-6 441 159 180 143 171 148 185 172 124 31 143 42 131 3 153 236 196 286 280 305 276 306 291 301 309 331 211 213 244 346 232 221 167 177 ap-southeast-7 342 64 91 99 100 103 90 74 30 121 47 133 26 153 4 251 207 188 183 207 179 186 204 195 193 238 118 124 269 356 249 236 199 190 ca-central-1 224 204 183 157 180 157 192 208 220 199 241 211 230 237 252 5 52 94 96 105 104 113 70 80 87 144 198 165 76 127 19 32 81 61

250

ca-west-1 291 162 143 112 140 117 241 222 177 159 195 170 184 196 206 49 2 160 162 172 169 177 136 147 153 212 266 256 78 193 55 44 41 23 eu-central-1 156 194 221 229 232 235 128 146 162 253 179 264 169 289 192 95 164 5 11 23 15 36 28 18 13 72 115 87 153 205 96 108 154 144 eu-central-2 153 188 216 223 226 229 116 134 156 246 174 258 163 283 185 96 164 11 4 28 8 35 29 20 13 50 113 91 152 204 94 107 153 144

200

eu-north-1 175 213 240 248 251 254 148 165 182 272 199 284 188 308 210 107 175 24 30 3 34 57 41 32 33 92 136 106 172 224 115 127 174 155 eu-south-1 195 184 214 219 222 225 113 129 153 243 170 255 160 280 182 104 172 14 9 32 4 30 37 28 23 51 110 112 163 214 104 117 163 152 eu-south-2 135 201 215 232 226 230 142 152 171 272 176 285 163 305 187 110 177 36 33 53 28 5 33 35 20 63 122 94 166 219 106 118 168 157 eu-west-1 159 261 236 205 237 215 127 143 178 256 196 268 183 295 206 71 139 28 30 40 38 34 5 14 21 79 132 101 129 180 72 84 131 119

150

eu-west-2 150 203 246 216 248 225 118 135 170 267 188 279 175 303 198 81 150 18 21 31 29 37 15 4 12 70 124 92 137 189 80 93 149 130 eu-west-3 146 199 221 222 255 232 110 126 167 281 183 293 173 312 195 88 156 13 14 32 23 21 21 12 4 56 116 88 144 196 86 99 145 136 il-central-1 228 236 256 271 274 277 142 163 204 295 222 307 211 326 233 138 207 65 43 84 48 63 71 62 55 4 145 113 195 247 136 150 195 187 me-central-1 281 125 151 170 161 165 31 46 91 182 109 193 98 214 119 198 271 114 112 133 109 123 131 122 115 149 4 15 255 306 196 210 255 257

100

me-south-1 250 131 159 177 168 172 39 55 99 190 116 200 105 218 125 165 259 87 93 105 113 99 101 92 89 121 17 3 224 276 166 178 224 264 mx-central-1 282 213 195 166 193 170 246 269 239 211 258 223 247 243 270 73 78 150 150 168 159 166 127 134 141 200 253 219 5 171 60 56 74 90 sa-east-1 338 318 293 261 293 271 301 317 329 313 348 325 337 353 359 127 196 205 204 223 213 222 179 188 196 255 307 276 174 4 116 128 175 176 us-east-1 227 208 180 151 182 160 192 205 220 200 237 212 226 230 248 19 57 93 93 113 102 106 71 78 85 140 195 166 61 115 9 18 69 65

50

us-east-2 237 194 167 137 169 147 201 216 205 188 222 200 213 218 234 28 43 104 103 123 113 117 81 89 95 148 205 174 53 125 18 8 52 49 us-west-1 287 156 143 110 134 111 234 217 173 140 191 152 180 170 203 82 43 154 154 173 163 172 131 149 145 204 257 224 74 176 71 58 4 21

0

us-west-2

us-east-2

us-west-1

sa-east-1

us-east-1

me-south-1

mx-central-1

me-central-1

eu-west-3

il-central-1

eu-west-2

eu-west-1

eu-south-2

eu-north-1

eu-south-1

eu-central-2

ca-west-1

eu-central-1

ca-central-1

ap-southeast-7

ap-southeast-6

ap-southeast-5

ap-southeast-4

ap-southeast-3

ap-southeast-2

ap-south-2

ap-southeast-1

ap-south-1

ap-northeast-3

ap-northeast-2

ap-east-2

ap-northeast-1

af-south-1 ap-east-1

us-west-2 274 146 132 100 124 101 225 206 163 142 178 152 169 178 191 63 22 144 145 155 153 158 120 130 137 187 257 264 91 176 66 53 21 4

Destination Region

Figure 12. AWS round-trip-time input matrix used to sample the 100 deployments for network simulations. The network simulator uses half of each directed RTT as its one-way delay. which covers 13 different AWS regions across North America, Europe, and Asia-Pacific within a network simulation to show how implemented variants of the protocols DAGRider [45], Narwhal [25], Bullshark [64], Shoal++ [7], MahiMahi-5 [43], Mysticeti [9], Fides [70] and Pangolin would perform in an identical network environment. Each bar is the mean over five runs that differ only in the seed of the common coin. Fig. 2 shows Pangolin overtakes Mysticeti with an average block decision latency of 284 ms vs. 372 ms.

D

Design Alternatives

D.1

Pangolin without TEEs

Pangolin can be realised without TEEs in three steps: First, substituting TEE-based primitives (reliable broadcast, common coin, threshold signature scheme) through standard variants. Second, using the (𝑛 ≥ 3𝑓 + 1)-resilience and 𝑛+𝑓 +1 standard Byzantine dissemination quorum sizes of ⌈ 2 ⌉. Third, the commit rules (see Sec. 4.4) are not checked against 26

Mean block decision latency [ms]

2500 2000 1500 1000 500

0

20

40

60

80

100

Deployment, sorted by Pangolin latency Pangolin (f=9)

Mysticeti (f=6)

Fides (f=9)

Mahi-Mahi-5 (f=6)

Shoal++ (f=6)

Bullshark (f=6)

Narwhal/Tusk (f=6)

DAG-Rider (f=6)

1.0

fraction of deployments ≤ x

fraction of deployments ≤ x

Figure 13. Per-deployment comparison, one column per deployment, columns ordered by Pangolin’s own latency. Pangolin is the connected line and is monotone by construction; every baseline mark lies above it in all 100 columns.

0.8 0.6 0.4 0.2 0.0

1.0 0.8 0.6 0.4 0.2 0.0

500

1000

1500

2000

2500

1000

Median block decision latency per deployment [ms] (a) Median (𝑝 50 ) latency. Pangolin (f=9)

Mysticeti (f=6)

Fides (f=9)

2000

3000

4000

p90 block decision latency per deployment [ms] (b) 𝑝 90 latency.

Mahi-Mahi-5 (f=6)

Shoal++ (f=6)

Bullshark (f=6)

Narwhal/Tusk (f=6)

DAG-Rider (f=6)

Figure 14. Cumulative distribution of block decision latency over the 100 deployments. A curve further to the left is faster on more deployments. In (a) Pangolin lies left of every baseline at every quantile. In (b) it still leads, but Mysticeti has moved close enough to touch it. the TEE, but are checked in the same way as in DAGRider [45] by waiting for a wave to complete.

27

Table 4. Block decision latency [ms] and round rate over 100 deployments, 𝑛 = 20, fault-free. Each protocol runs at the largest 𝑓 its own resilience bound admits. System

𝑓

quorum mean

Pangolin Mysticeti Fides Mahi-Mahi-5 Shoal++ Bullshark Narwhal/Tusk DAG-Rider

9 6 9 6 6 6 6 6

11 14 11 14 14 14 14 14

𝑝 50

𝑝 90

𝑝 99 rounds/s

352 340 471 597 446 435 529 608 576 542 742 1,050 604 588 675 752 635 638 762 802 1,109 1,154 1,437 1,577 1,444 1,435 1,912 2,643 2,070 1,993 2,743 4,121

13.1 9.3 13.1 10.4 2.3 3.4 3.5 3.5

28

Related documents

• SafarDB: FPGA-Accelerated Distributed Transactions via Replicated Data Types#821805
• Optimistic, Signature-Free Reliable Broadcast and Its Applications#1387901
• Administration Protocol for Federated File Systems#208981
• Lightweight Fault Recovery Against Transient Faults with OpenMP#1273857
• TetraBFT: Reducing Latency of Unauthenticated, Responsive BFT Consensus#139071