arXiv CSopen access

Tilikum: Transaction Fair Ordering on a DAG without Weak Edges

Tilikum: Transaction Fair Ordering on a DAG without Weak Edges Giulio Segalini*

Yigit Çolakoğlu

Marko Putnik

Jérémie Decouchant

arXiv:2606.27250v1 [cs.CR] 25 Jun 2026

Université de Neuchâtel Delft University of Technology Delft University of Technology Delft University of Technology [email protected] [email protected] [email protected] [email protected]

Abstract—Decentralized Finance (DeFi) applications rely heavily on the order in which transactions are executed, making them susceptible to reordering attacks that enable adversaries to extract Blockchain Extractable Value (BEV). While linear blockchain systems such as Ethereum have inspired extensive research into fair ordering mechanisms, DAG-based consensus protocols have remained largely unprotected despite their growing adoption for scalability and performance. In this paper, we introduce Tilikum, a DAG-based ledger protocol that ensures fair transaction ordering without relying on weak edges. Tilikum achieves ordering linearizability by leveraging median-based timestamp aggregation, or batch order fairness, while maintaining low data redundancy and robust garbage collection. We implemented Tilikum in Rust and evaluated it against representative baselines, namely Narwhal/Tusk, Pompē, Themis and FairDAG. Our results show that Tilikum achieves up to 39× higher throughput than other fair-ordering baselines, while fully blocking state-of-the-art DAGspecific reordering attacks. Index Terms—Order-Fair Consensus, Transaction Ordering, DAG-based Consensus, Blockchains.

I. I NTRODUCTION Since Bitcoin [1], cryptocurrencies and blockchain technology have remained a continuous focus of academic research and industrial development. Ethereum [2] introduced smart contracts, which allow generalized applications to run on top of blockchains, achieving strong security guarantees, such as integrity, transparency, and decentralization. One particular application of smart contracts that has gained traction is Decentralized Finance (DeFi) systems that offer traditional financial services without the need for trusted intermediaries [3]. Transactions executed through a DeFi smart contract are often order-dependent, as the state and outcome of a transaction are dictated by those that precede it. This dependency enables transaction reordering attacks, where actors extract value by manipulating the order in which transactions are committed or by inserting their own at strategic positions. Because block producers (i.e., miners or validators) have the final authority over block content and ordering, this extracted profit is known as Blockchain Extractable Value (BEV).1 Simple transactions and exchanges between two parties are not susceptible to these attacks, but other applications are. Some major examples are lending protocols, which dynamically adjust interest rates depending on previous interactions, and

decentralized exchanges, where buyers and sellers of different tokens are automatically matched based on previous market interactions. EigenPhi2 reports more than $2M extracted from Ethereum DeFi in a single week (snapshot, June 2024), and Flashbots’ MEV-Explore platform [4] measured monthly extraction rates around $100M throughout 2022. These numbers result in an opaque tax paid by users directly or indirectly through higher fees or worse exchange rates [5]. BEV mitigation solutions typically follow one of two philosophies. They might first democratize the extraction process by allowing everyone to reap profits from positioning their transactions favorably. A second approach enforces fair transaction ordering guarantees. Fair ordering involves computing what would be a fair way to order transactions based on the order in which different replicas receive them [6, 7]. These systems define order fairness either using absolute time indicators (i.e., timestamps) or relative pair-wise orderings to derive a final sequence from replica proposals. Transaction fair-ordering mechanisms have been mainly designed for linear blockchain structures, where blocks of transactions are committed in a single chain, produced by algorithms such as PBFT [8] or HotStuff [9]. Linear blockchains are also the main support for smart contract platforms like Ethereum [2]. However, there is a growing shift toward alternative architectures. In particular, the latest generation of consensus algorithms increasingly utilizes Directed Acyclic Graphs (DAGs) to organize transactions and blocks [10–14]. By decoupling transaction dissemination from ordering, these DAG-based approaches achieve orders-of-magnitude higher throughput without compromising security. One might assume that the high performance of DAG-based algorithms would naturally mitigate BEV attacks by narrowing the window of opportunity for attackers. Zhang et al. [15] and Mahe et al. [16] show otherwise: DAG-based ledgers remain susceptible to sophisticated reordering exploits. Currently, the intersection of DAG-based consensus and fair ordering remains largely unexplored. To the best of our knowledge, the only existing solution is FairDAG [17]. However, FairDAG relies on full transaction redundancy across replicas and on weak edges, both of which preclude garbage collection and limit its practical deployment. It is also vulnerable to malicious clients

* Work performed while at TU Delft. 1 BEV is a more general term than MEV, which specifically refers to blockchains utilizing Proof-of-Work.

2 https://eigenphi.io/

Reliable broadcast and Certificates of Availability. When a validator creates a block, it broadcasts it; peers reply with a digital signature once they have validated the block and its 2f + 1 parent certificates. Collecting 2f + 1 signatures forms a Certificate of Availability (CoA), which guarantees that the block’s data is stored by at least f + 1 honest parties and is retrievable even if the original sender fails. Primary-worker architecture. For horizontal scalability, each party splits responsibilities between a primary that processes block metadata and several workers that reliably broadcast transaction batches and feed their hashes to the primary. Tusk consensus. Tusk groups DAG rounds into three waves: proposal, voting via references, and a shared coin that elects a leader block. A leader is committed once it receives at least f + 1 references in the next round, and its uncommitted causal history is then ordered deterministically. Clients submit transactions to multiple parties so that, as long as one honest validator receives a transaction, it is eventually included in the total order.

that can halt execution by broadcasting transactions to a subset of replicas. We discuss these limitations in detail in Appx. A. We introduce Tilikum, a novel blockchain consensus framework that benefits from the performance of the DAG-based paradigm, supports fair-ordering properties and overcomes FairDAG’s limitations. We implement two variants of Tilikum, Tilikum-OL and Tilikum-BOF, that respectively implement ordering linearizability [7] and γ-batch-order fairness [18]. As a summary, this work makes the following contributions. • Tilikum: ordering linearizability and γ-batch-orderfairness on a DAG. We introduce two variants of Tilikum. Tilikum-OL establishes fair transaction ordering directly within a DAG by combining a dual-timestamping mechanism with sealed batches: a Logical Table tracks sequence holes, which are synchronized using metadata-rich Hole Fillers, and medianbased execution thresholds define safe points for finalizing and executing transactions fairly. Tilikum-BOF extends this core design to γ-batch-order-fairness using dependency graphs and digests to resolve ordering cycles, with batch-unspooling and continuity mechanisms to keep overhead low. • First weak-edge-free DAG-based fair-ordering protocol. Tilikum is, to the best of our knowledge, the first DAGbased fair-ordering protocol that does not rely on weak edges, thus restoring garbage collection, a prerequisite for production deployment. We formally prove that Tilikum-OL and Tilikum-BOF guarantee execution safety and liveness, and respectively ensure ordering linearizability and γ-batch-order fairness. We implement Tilikum in Rust as an extension of Narwhal/Tusk [11], the foundation of subsequent DAG-based algorithms [12, 19–21]; the source code will be open-sourced upon acceptance. • Liveness attack on FairDAG with malicious clients. We identify performance and liveness attacks on FairDAG [17] in which malicious clients selectively broadcast transactions to a subset of replicas, harming or halting execution (see Appx. A). Tilikum is not vulnerable to this attack by design. • Evaluation, including under attack. We benchmark TilikumOL and Tilikum-BOF against state-of-the-art fair-ordering protocols: Themis [18], Pompē [7] and FairDAG [17]. TilikumOL sustains 14,000 tx/s at N =10 with 1.2 s latency, 39× Pompē’s throughput at the same scale and still 4× faster than Pompē at N =25. Tilikum-BOF doubles Themis’ throughput at every evaluated system size. Under the reordering attacks of Zhang et al. [15], which succeed on vanilla Narwhal/Tusk between 14% and 95% of the time, Tilikum-OL drops the success rate to 0%.

III. S YSTEM M ODEL AND O BJECTIVES A. Blockchain Consensus We consider a system of n parties that communicate via message passing. Together, the parties run a Byzantine faulttolerant state-machine replication (BFT-SMR) protocol that provides a total ordering service for clients. Clients broadcast their transactions to all parties so that they can be ordered as soon as possible to limit the risk of BEV attack. We consider a computationally bounded and static adversary that can corrupt up to f parties, which are then said to be faulty or Byzantine. Faulty parties can deviate from the protocol in unrestricted ways and collude, while others are said to be correct. We assume that clients may also be faulty, e.g., they may send a transaction to a subset of the parties. Parties have access to a collision-resistant hashing scheme and to an unforgeable digital signature scheme. Each party has a unique private key that allows them to sign messages, and every party knows all public keys and is able to verify all valid signatures. We assume that the parties are running an asynchronous DAG-based algorithm, which has been shown to ensure high performance. We build our algorithm, Tilikum, on top of Narwhal/Tusk [11] because it has been deployed in production, its code has been publicly released and it has been the basis of several further works [12, 14, 19]. Network model. Tilikum is designed for asynchronous but eventually reliable communication links among correct parties, which means that there is no bound on message delays and that an unknown but finite number of messages can be lost. We evaluate Tilikum on random delay networks [22], which are a subcategory of asynchronous networks, by setting parameter K (see §IV-A) to f + 1. Supporting any asynchronous network would simply require setting parameter K to 2f + 1, which results in slightly lowered performance (see §VII-C).

II. BACKGROUND ON NARWHAL /T USK Narwhal/Tusk [11] decouples transaction dissemination from ordering, addressing the bandwidth bottleneck of leader-based BFT. Narwhal serves as the mempool, organizing transactions into a Directed Acyclic Graph (DAG) through a round-based reliable broadcast. Tusk runs on top of Narwhal as the consensus layer.

2

still be ordered before tx1 . Execution latency is lower-bounded by the earliest point in time at which a transaction becomes executable, which can be measured. Execution throughput is the rate at which transactions become executable. In fair-ordering systems, execution latency and throughput matter more than consensus ones, with execution throughput always being lower than consensus throughput and execution latency always being higher than consensus latency.

B. Fair-Ordering Objectives The location of a transaction in the ledger may impact its successful execution or its outputs. To protect correct clients against transaction reordering attacks, our goal is to ensure transaction fair-ordering. We aim at supporting (separately) the two state-of-the-art fair ordering properties: ordering linearizability and γ-batch-order-fairness. Definition 1 (Ordering linearizability [7]). Let tx1 and tx2 be two client transactions. If the highest timestamp provided by a correct party for tx1 is lower than the smallest timestamp provided by a correct party for tx2 , then all correct parties order (and execute) tx1 before tx2 .

D. Challenges Ensuring ordering linearizability and γ-batch-order-fairness on a DAG while maintaining high performance is challenging for several reasons. Unlike in leader-based protocols [7, 18, 23], no single party can be tasked with collecting and committing enough local timestamps or relative orderings. FairDAG [17] has each party commit each transaction in one of its blocks, but since a round only commits 2f +1 DAG blocks and weak edges must be avoided for garbage collection, there is no guarantee that enough information is ever committed per transaction. Finally, a malicious client may send a transaction to fewer than 2f +1 parties: with too few timestamps to compute a median, execution of later transactions with potentially larger timestamps stalls indefinitely.

Ordering linearizability requires committing, for each transaction, 2f + 1 physical-clock timestamps from different parties. Once 2f + 1 such timestamps are committed for a transaction, all correct parties deterministically order it using the median of those timestamps. Definition 2 (γ-batch-order-fairness [6, 18]). Given a parameter 12 < γ ≤ 1, if a fraction γ of honest parties receive transaction tx1 before transaction tx2 , then tx1 is ordered no later than tx2 . If these preferences form a cycle, the involved transactions are grouped into a single batch and delivered together.

IV. T ILIKUM : C ORE D ESIGN FOR O RDERING L INEARIZABILITY

γ-batch-order-fairness therefore requires correct parties to This section details the core design of Tilikum, which share the order in which they received transactions, and to supports ordering linearizability. agree on how cyclic dependencies are resolved. System size. The number of replicas required by our A. Giving Physical Clock Timestamps to Transactions algorithm, Tilikum, depends on the fairness property being In Tilikum, censorship-resistance is guaranteed as soon as a enforced. For ordering linearizability, Tilikum-OL assumes client sends its transaction to at least f + 1 parties: eventually, n ≥ 3f + 1, which matches the minimum need for consensus. the transaction would be communicated to one or several correct For γ-batch-order-fairness, Tilikum-BOF requires n > f (2γ+1) 2γ−1 , parties that would commit it (details in Sec. IV-B). However, which simplifies to n ≥ 3f + 1 when γ = 1. For comparison, we assume that correct clients send their transactions to all Tilikum-BOF requires the same number of replicas as FairDAGthe parties so that each of them gives it a timestamp as early RL [17] to ensure γ-batch-order-fairness, whereas Themis [18] as possible for more robust front-running resistance. When a f (2γ+2) 3 assumes n > 2γ−1 (i.e., at least 4f + 1 when γ = 1) . party learns about a new transaction tx, it verifies whether it is well-formed and correctly signed, and if so it associates it C. Execution-Ready Performance with a timestamp pair, made of the value of its local counter To evaluate the performance of a fair-ordering consensus lc(tx) and its UNIX physical clock value ϕ(tx). Afterwards, algorithm, it is necessary to distinguish between consensus and the party increments its local counter value. Note that parties execution performance. In DAG-based protocols, consensus give a timestamp to a transaction the first time they see it, latency is the time required for a transaction to be committed which happens either when they receive it from the client or in the DAG, which is lower-bounded by its first commit at from another replica. The full per-party state machine is given any party. Consensus throughput is the average number of in Alg. 3 (Appx. B). Since every timestamp pair is signed, transactions committed per time unit. However, in fair-ordering two conflicting pairs at the same logical counter expose the systems, commitment does not imply immediate execution. We equivocator and are rejected by correct parties. call the execution latency of a transaction tx1 at party P the time from its emission by a client until it is committed in P ’s B. Including Transactions in Blocks with 2f + 1 Timestamps DAG and safe to execute, i.e., when no other transaction tx2 can Redundancy degree. In a DAG, there are two ways to commit transactions and collect 2f +1 local timestamps. 3 As Themis is a leader-based protocol, per-round leaders can only wait to receive n − f local orderings, out of which f might be Byzantine, thus to First, all parties may be instructed to include all transactions accommodate the solid edge direction threshold of 2f + 1 (for γ = 1.0) it in their blocks along with their own timestamp. Then, the first is required to have N > 4f . On the other hand, FairDAG and Tilikum-BOF utilize the validity property of the DAG which guarantees n − f honest local 2f +1 timestamps associated to a transaction that are committed orderings upon commit, thus strengthening the threshold to N > 3f . in the DAG can be used to compute its final timestamp. This

3

approach requires parties to resubmit a block in a round until it is included in the DAG, or the use of weak edges so that 2f +1 blocks from different parties that contain the transaction are always eventually committed, which limits its applicability to some protocols, such as DAG-Rider [10]. Second, K parties, where 0<K≤n−1, can be tasked with including a subset of the transactions in their blocks along with 2f +1 timestamps that they collect from other parties. Parties that are tasked with including a transaction in one of their blocks are deterministically selected based on the hash of the transaction. Depending on the value of K, two subcases need to be distinguished. If K ≥ f + 1, then at least one correct party will be tasked with including the transaction in the DAG, will collect 2f +1 timestamps from other correct parties and eventually commit a block with the transaction. If K ≤ f , then it might be possible for a transaction to not be included in the DAG by the original K parties, which might all be faulty. Assuming a correct client, then all parties will eventually learn about the transaction, and can start a pertransaction timer when they receive it. If they do not observe the transaction committed in a block before this timer expires, then they attempt to collect 2f +1 timestamps and commit the transaction in the DAG themselves. The first approach, where K ≤ f , leads to a lower data redundancy but, in the bad case, its use of timeouts increases execution latency. Tilikum uses K = f + 1 in random delay networks, and K = 2f +1 in asynchronous networks.

Fig. 1: Structure of Tilikum’s DAG. Each round contains a set of blocks, represented by large rectangles, while smaller rectangles denote certificates. The DAG excludes weak edges, i.e., references from a block at round rb to a block at round ra < rb − 1, enabling efficient garbage collection and practical deployment.

Creating batches and blocks. Parties that are proposing a batch of transactions need to collect 2f +1 timestamps per transaction. As in Narwhal, blocks only contain hashes of transaction batches. For a batch to be included in a block, a party first broadcasts it and waits for 2f +1 signed replies. Each such reply contains a vector of timestamp pairs from the sending replica. Signatures on timestamps cover the transaction executed and when a block of transactions is committed. Along digest, its timestamp, and the associated logical counter. The with these transactions, a party stores their 2f +1 timestamp party then broadcasts its batch with the 2f +1 timestamp vectors pairs in the Logical Table: a map from each party’s public it collected for reliable storage, and waits for 2f +1 signed key to a list of the timestamp pairs emitted by that party, kept acknowledgments. A batch is sealed once its proposer has sorted by logical-counter value. collected 2f +1 timestamp vectors and 2f +1 acknowledgments The main role of the Logical Table is to track which of reliable storage; only sealed batches can be included in a timestamp pairs are still missing for each other party. A missing block. From here onward, parties operate an instance of the pair (an entry whose logical counter has not yet been observed Narwhal [11] protocol normally. Alg. 4 (Appx. B) formalises in a committed block) is called a hole. The head of each row the two-round batch-sealing procedure and how a sealed batch’s is then the earliest timestamp for which the party has seen all hash is then assembled into a DAG block alongside parent predecessors but not the immediate successor. certificates and hole fillers.

Parties collect, for each other party, the smallest pair that does not miss any precedent value (i.e., the head of the list), they obtain a list of 3f +1 timestamp pairs that can always be executed. This is because, for each party, parties have also committed all transactions seen by that party with a smaller timestamp than the one in the list. Parties take the 2f +1 smallest associated UNIX timestamps and compute their median, they then obtain a threshold value until which transaction execution is safe. This computation is given in Alg. 5 (Appx. B) and is invoked by Alg. 1.

C. Executing Transactions Committed transactions are eventually executed according to the order determined by the median of their 2f +1 timestamps contained in the first block where they appear. To execute a transaction, a party needs to know for sure that there is no other transaction that has been assigned timestamps by other parties and might be ordered before it. Each party therefore maintains a list of transactions that are pending execution, which is updated when transactions are

4

Algorithm 1 Logical Table Update & Transaction Execution at party pi

Algorithm 2 Hole Filler Computation & Application 1: function C OMPUTE H OLE F ILLERS( ) 2: F ←[] 3: head ← head of Li [pi ]

1: Initialization: 2: Li [ ] ← map from party id to sorted list of (lc, φ) pairs ▷

σ ← S IGN head .lc, head .φ
F.A PPEND pi , head .lc, head .φ, σ for all (pj , lc j , φj , σj ) ∈ pending_fillers i do ▷ Include signed fillers from other parties, collected at block receival
8: F.A PPEND pj , lc j , φj , σj 9: end for 10: return F 11: end function

Logical Table 3: pending i ← ∅

4: 5: 6: 7:

▷ transactions committed but not yet

executed 4: upon block B is committed by Tusk do 5: for all sealed batch sb referenced by B do

for all tx ∈ sb do pairs ← extract 2f +1 timestamp pairs from sb
tx .final _ts ← M EDIAN {φ | (lc, φ) ∈ pairs} for all (pj , lc j , φj ) ∈ pairs do Li [pj ].I NSERT(lc j , φj ) end for 12: pending i ← pending i ∪ {tx } 13: end for 14: end for

6: 7: 8: 9: 10: 11:

12: procedure A DVANCE ROW (L, author , lc h , φh , σh )

cur ← head of L[author ] if lc h > cur .lc then advance L[author ] head to (lc h , φh ) signed by author 16: end if 17: end procedure 13: 14: 15:

15: ▷ Process hole fillers from B’s metadata 16: for all (author , lc h , φh , σh ) ∈ B.fillers do 17: A DVANCE ROW(Li , author , lc h , φh , σh ) 18: end for

▷ safe:

head of the just updated row. When processing a committed block, parties can safely advance the logical table row of a block’s author such that the new head is equivalent to the hole filler’s value. In case the row is already ahead enough, the value can be simply ignored. Fig. 1 illustrates Tilikum’s DAG and highlights in gray the additional information that Tilikum commits compared to Narwhal/Tusk: 2f + 1 timestamp pairs per transaction, and a list of hole fillers.

19: ▷ Compute execution threshold and execute 20: τ ← T HRESHOLD(Li ) 21: ready ← {tx ∈ pending i | tx .final _ts ≤ τ } 22: sort ready by final _ts (break ties deterministically) 23: for all tx ∈ ready in sorted order do 24: E XECUTE(tx ) 25: pending i ← pending i \ {tx } 26: end for

V. T ILIKUM -BOF: E XTENSION FOR BATCH - ORDER - FAIRNESS Tilikum-BOF reuses Tilikum-OL’s dual-timestamping, sealed batches, and Logical Table, and adds a per-commit dependency graph (§V-C) and enriched Hole-Fillers carrying transaction digests. These yield γ-batch-order-fairness via batch-unspooling, as in Themis [18].

D. Hole Fillers Rows of the Logical Table can stay incomplete. When a transaction is sealed with 2f +1 timestamps, the remaining parties’ timestamps never reach the row, leaving holes. Without weak edges, the blocks carrying those timestamps are not guaranteed to be committed either: a certificate of availability may arrive too late to be referenced in the next round and is dropped. Danezis et al. [11] address this by re-injecting batches of uncommitted blocks so that every batch is eventually committed in expectation, but the missing Logical Table entries remain. Since the execution threshold is the median of row heads, a single stuck row halts every later transaction. To prevent this, we introduce Hole Fillers: metadata added to blocks that allow other parties to catch up on the missing values and advance their Logical Table. After a block is committed, parties verify for which transactions in the blocks their assigned Timestamp Pair was not included. All these values should be retrieved from the local storage and included in their own row in the Logical Table. Parties then add as metadata in the next block the current

A. Inferring Local Orderings Each transaction tx is bundled with the local counter lc(tx) assigned to that transaction by 2f +1 parties. Once a transaction is committed, this information is used to populate the logical table, which is a mapping from each party to its logical vector. The logical vector v is an ordered list such that v(i) ∈ T ∪ ∅ where T is the set of all transactions and ∅ represents a missing transaction. When the protocol first starts, all logical vectors are initialized at ∅. We denote the logical vector of party p at round r as vpr . As the logical table is updated each round, Tilikum uses it to build the transaction dependency graph, since it details the order in which each party received each transaction. However, the entire logical table cannot be used directly to construct the dependency graph, as it may contain holes (i.e., ∅ entries) that

5

need to be accounted for. Instead, we define the local ordering of a party p at a given round r as Lrp = {tx ∈ T | ∀i ≤ lc(tx) : vpr (i) ̸= ∅}. This method to infer the local ordering for each party ensures that if a transaction tx does not appear in Lrp , then it is not possible for p to claim that it received a different transaction tx′ ̸= tx before tx, at a later round. This is similar to the FIFO broadcast primitive used in Aequitas [6], and plays a key role in implementing batch unspooling.

fillers, while still allowing the optimization to operate when the publication sequence is intact. C. Building the Dependency Graph Our graph building and unrolling approach follows that of Themis [18], with modifications inspired by FairDAG-RL [17]. Similar to Themis and FairDAG-RL we instantiate a fresh dependency graph upon commit and bound its scope to the transactions admitted at that commit, releasing its memory once the graph is sequenced.

B. Modified Hole Fillers

Because the logical table is the main source of information Ordering Notation. Given a set of local orderings L, we used to infer local orderings, the holes in the logical table use tx ∈k L to denote that transaction tx is present in at need to be filled fully to ensure the protocol’s liveness. For least k orderings in L. Notation tx ≺(L,k) tx′ indicates that this, we rely on the hole-fillers introduced in Sec. IV-D, with tx appears before tx′ in at least k orderings in L. Finally, some modifications to their content. For γ-batch-order fairness, WeightL (tx, tx′ ) represents the maximum value k such that we need to know the transaction associated with each logical tx ≺(L,k) tx′ . We define Lp (lc) as party p’s transaction with counter so that we can correctly compute ordering preferences logical counter lc (or ∅ if none exists) and Lp (lc, lc′ ) as all between transaction pairs. Therefore, we modify hole-fillers to transactions in Lp with logical counters in [lc, lc′ ]. include the transaction’s digest alongside the logical counter. Unlike in the ordering-linearizability case, a party must Per-commit graphs. Each time a leader vertex Lr is supply fillers for all missing logical counters, not just the committed and its sub-DAG Ar is delivered to the fairness head of its logical vector. This imposes additional overhead layer, we instantiate a new graph Gr (Alg. 6). Transactions are and makes it harder for lagging parties to publish new local admitted to Gr when they have first been seen by enough parties, orderings that contribute to the ordering graph. However, many that is when tx ∈n(1−γ)+f +1 L(F ), and remain assigned to Gr missing counters may correspond to transactions that are for the remainder of their lifetime. For each pair of admitted already finalized, and publishing fillers for them is unnecessary. transactions tx, tx′ ∈ Gr we add the edge tx → tx′ once To address this, we introduce an optimization that reduces WeightL(F ) (tx, tx′ ) ≥ n(1 − γ) + f + 1 and the reverse edge redundant filler publication. does not already exist. Pairs whose weights have not yet crossed threshold in either direction are tracked separately and revisited Hole-Filler Continuity and Optimization. First, we adjust only when new local orderings affect them, restricting per-round the protocol such that the hole-fillers published by a party work to pairs whose status could plausibly change. in two consecutive rounds r, r + 1 are for strictly increasing logical counters and there are no holes between the largest Lockstep processing. We process local orderings for each counter in round r and the smallest logical counter in round party in lockstep. For each party p we maintain a monotonically r + 1. This enables a significant optimization: a party can increasing frontier Fp initialized at 0, representing the last omit fillers for all logical counters associated with already logical counter we have processed for that party. We define finalized transactions and only publish fillers starting from the L(F ) = {Lp (0, Fp ) | Fp ∈ F } as the set of local orderings unfinalized transaction onward. This makes it easier for a party at the given frontiers. The frontier of party p advances that is lagging behind to catch up. only when its contiguous prefix reaches the next counter, which is the mechanism by which hole-fillers contribute to Handling Unreachable Blocks. The correctness of this count growth. The function Order(L(F ), G, γ) processes optimization is void if a block carrying hole-fillers is not transactions in L(F ), admits them to the current graph if included in the chain. To ensure safety under such conditions, their count has crossed the admission threshold, and adds we introduce a two-part sequence identifier for blocks carrying edges between admitted pairs whose weights cross threshold. hole-fillers: (retry_count, seqnum), where seqnum represents Order is invoked after every leader commit and proceeds the position of the block in the party’s filler publication across unfinalized graphs in round order. sequence, while retry_count is incremented whenever a block is not committed. Finalization with live count re-evaluation. A graph Gr is When processing a block, a party applies the optimization finalizable once it is a tournament. We then condense it via only if no seqnum values for that party have been skipped, Tarjan’s algorithm and topologically sort the SCCs. Themis and the retry_count is at least as large as the latest retry count and FairDAG-RL freeze the solid classification at admission observed for that party. If either condition fails, the optimization time, but we instead re-evaluate the live count at finalization, is disabled for that block, and no assumptions can be made so a transaction admitted with a count just above the admission about earlier holes. When a party detects that a block containing threshold can promote to solid as additional parties’ prefixes its hole-fillers was not committed, it continues publishing fillers advance through it via hole-fillers. We locate the last SCC starting from the missing sequence number but increments its containing a transaction whose live count satisfies tx ∈2f +1 L retry_count. This ensures eventual delivery of all required and finalize all SCCs at or before this cutoff. Transactions in

6

SCCs after the cutoff have their graph membership cleared and are re-classified against the next leader commit’s graph. This live-count check is necessary to preserve liveness for transactions admitted before enough parties’ prefixes reach them.

the next round. Assuming the worst case where every block in the first round has exactly f connections to blocks in S, the remaining number of links is still (2f +1)2 − f (3f +1) = f 2 + 3f + 1. Each block in S has at most 2f +1 connections to 2 +1 block in the first round. This means there are at least f2f+3f +1−f blocks with more than f +1 connections to the next one.

VI. C ORRECTNESS P ROOF

Throughout this section we assume the system model of §III: Lemma 4. In expectation, a leader is committed every 7 rounds an asynchronous, eventually reliable network of n ≥ 3f + 1 in a network with asynchronous adversary. parties of which up to f are Byzantine, with all messages signed Proof. By Lemma 3, there are at least f +1 committable blocks under a PKI. We first state the safety and liveness properties of for each new instance of consensus. As the random coin is the consensus layer (Tusk), following the original proofs [11]. unpredictable, there is a 1 chance of committing a valid block. 3 Referring to these proofs, we then prove that Tilikum ensures As consensus is run every 3 rounds, this gives an expected ordering fairness, execution safety and liveness. value of 9 rounds. However, the last round of each consensus wave is the same as the first round of the next wave, giving A. Safety and Liveness of Consensus us an expectation of 7. Safety. Any two honest validators will commit the same sequence of blocks during the consensus step. B. Fairness Properties Lemma 1. If an honest validator commits block b as leader in wave i, then any leader block b′ committed by honest validators in waves after i has a path to b.

This section first discusses the fairness properties that Tilikum-OL guarantees. These are the ordering property, i.e., ordering linearizability or γ-batch-order-fairness, and the concepts of execution safety and execution liveness.

Proof. Honest validators commit block b in wave i only if it has f +1 parties in the wave with paths to b. All blocks in the first round of wave i + 1 have 2f +1 paths to previous blocks. By Quorum intersection, at least one of the paths of the leader block of the wave starting from this round will go to b. By induction, we can show that every block in every round after wave i has a path to b.

Ordering Linearizability. As Tilikum-OL adopts the same ordering property and underlying timestamping mechanism as Pompē [7], their proofs follow a similar logical structure. Lemma 5. The median of 2f +1 values, of which up to f can be malicious, is always both upper- and lower-bound by correct values.

Lemma 2. If b is the leader block of wave i and b′ is the leader block of wave i′ , if an honest validator commits b before b′ , then no other honest validator commits b′ without committing first b.

Proof. For a set of 2f +1 values, we can see the median as the values sandwiched between f smaller (or equal) values and f higher (or equal) values. The f malicious values can be spread in three ways: all in the smaller set, all in the higher set or spread between them. In the first 2 cases, we have that the median itself is a correct value and that the other set is fully composed of correct values, bounding the median between honest numbers. In the last case, we have that each set contains at least one correct element, which is smaller or equal for the left-side and higher or equal on the right-side, again bounding the median between these two correct entries.

Proof. If an honest validator committed b before b′ , then there is no path from b to b′ . Assume by absurd that a different validator committed b′ before b there would also be no path between b′ and b. But by Lemma 1 at least one of these paths must exist, making a contradiction. The safety property is a direct consequence of Lemma 2. Liveness. The liveness property informally says that something is always happening, so that the system is always progressing towards new correct events. In Tusk, we want to show that we expect new blocks to be committed in a finite amount of time. This liveness property is enforced only for the consensus step and not for the ordering phase. That concept of liveness is defined and proven later.

Lemma 6. Transactions ordered by the median of 2f +1 collected timestamps respect ordering linearizability (Definition 1). Proof. Let us take two transactions tx1 and tx2 with the respective median timestamps t1 and t2 . If the maximum timestamp from a correct party for tx1 is tm1 and the minimum timestamp from a correct party for tx2 is tm2 , we know that t1 <= tm1 and t2 >= tm2 . Hence, if tm1 < tm2 , the first condition of Definition 1, we know that t1 ≤ tm1 < tm2 ≤ t2 and so t1 < t2 , which will make correct parties order, and so execute, tx1 before tx2 .

Lemma 3. In every wave w there are at least f +1 blocks in the first round that can be committed. Proof. Let’s consider any set S of blocks in the second round of wave w. There are then at least (2f +1)2 connections to blocks in the first round. There also at most 3f +1 blocks in the first round. For each of these blocks to be not allowed for commit, they need to have at most f connections to blocks in

γ-batch-order fairness. Tilikum-BOF’s graph layer mirrors that of FairDAG-RL [17], so its γ-batch-order-fairness theorem

7

Lemma 10. The assigned timestamp t of a transaction tx is not greater than the threshold value that would be calculated if tx is the first hole for every party.

transfers once we establish that our input local orderings and our admission rule coincide with theirs. Lemma 7 (Local-ordering soundness). For every correct party p and round r, the hole-free prefix of vpr equals a prefix of the order in which p first observed transactions, and each (p, ℓ) pair binds to exactly one transaction.

Proof. The assigned timestamp t is the median of the timestamp assigned to tx by 2f +1 parties. The threshold computed by the Logical Table in case this transaction is the smallest hole for all parties is the median of the smallest 2f +1 timestamps assigned by parties. This value cannot then be bigger than t.

Proof. A correct party p runs Alg. 3, where lc is incremented monotonically and a counter is assigned only on first sight, so the mapping ℓ 7→ tx at p is injective and the resulting sequence is by construction p’s reception order. Hole fillers carry p-signed (ℓ, tx) records (Alg. 2), so no party can inject a counter on p’s behalf, and any (p, ℓ) entry that reaches the logical table is exactly the one p assigned.

Theorem 11. Taking an arbitrary uncommitted transaction tx with assigned timestamp t, the threshold tr cannot be larger than t. Proof. An uncommitted transaction will always result in a hole for every entry in the Logical Table. According to Lemma 10, the threshold resulting from the situation where this is the smallest hole for each party, results in the threshold being valid for future execution of this transaction. In case this transaction is not the first hole for some or all parties, we know that the threshold will then be committed over smaller holes, which always have smaller or equal timestamps, as parties increase their timestamps monotonically. Theorem 11 shows that it is impossible for the threshold to be larger than the timestamp of an uncommitted transaction, showing Execution Safety. Liveness. Remember that transactions are first committed through a consensus mechanism (Tusk) and execution is delayed until the threshold value is high enough for safe execution. The following lemma first shows that on average and with random network latencies/delays, the threshold is always increasing and so some transaction is always eventually executed.

Lemma 8 (Logical-table agreement). At every round r, all correct parties observe identical logical tables. Proof. By Lemma 2, correct parties commit identical sequences of leader blocks and therefore identical causal sub-DAGs. The logical table is a deterministic function of the committed blocks’ sealed batches and hole fillers (Alg. 1), and identical input yields identical state. Theorem 9 (γ-batch-order-fairness). Tilikum-BOF satisfies γ-batch-order-fairness.

Proof. Suppose at least γ(n − f ) correct parties received tx before tx′ . By Lemma 7, this is reflected in the local orderings Lp each correct p contributes. By Lemma 8, every correct party runs the graph builder on the same logical table L. On this shared input, Tilikum-BOF admits tx to graph Gr when its count reaches n(1 − γ) + f + 1 and adds the edge tx → tx′ once WeightL (tx, tx′ ) ≥ n(1−γ)+f +1. Both rules and the per-commit graph structure coincide with FairDAGRL’s graph construction approach. Finalisation emits an SCC Lemma 12. Assuming random network latencies and that every proposes one block per round, each proposed only once it contains a transaction satisfying tx ∈2f +1 L, i.e., (correct) party 2 block has a probability of getting approved in the current 3 passed the solid threshold, after which it processes SCCs in round. topological order of the condensation and defers transactions in later SCCs to subsequent rounds, which is FairDAG-RL’s Proof. Having random network delays implies that the order a O RDER F INALIZATION rule [17]. party receives blocks is random. If 3f +1 blocks are submitted Tilikum-BOF differs from FairDAG-RL only in that we each round and each party waits for 2f +1 certificates before evaluate the solid predicate against the live count(tx) at progressing, then from the point of view of each party 2f +1 > 3f +1 finalisation rather than against the type frozen at admission. 2 blocks will be included in the current round. 3 Since count grows monotonically, this admits exactly the FairDAG-RL finalisations plus those where a transaction Lemma 13. The expected value of committed blocks per party has reached ∈2f +1 L between admission and tournament and per wave of consensus is 3. completion, so any ordering FairDAG-RL would produce on Proof. From Lemma 4 we know that on average consensus L is also produced by Tilikum-BOF. FairDAG-RL’s Theorem happens every 7 rounds. From Lemma 12 we get that 7 · 2 3 8.18 [17] applies, yielding γ-batch-order-fairness. blocks per author are in a wave. Moreover, by 2/3-Causality 2 3 of these blocks will be committed, giving us an expectation C. Safety and Liveness of Execution of 7 · ( 23 )2 ≈ 3.11. Safety. We now prove that the threshold computed through the Logical Table is always safe, which means that it is always lower than the assigned timestamp of any transaction that may still possibly be committed.

Lemma 14. Every time a leader block is committed, the logical table row of at least f +1 correct parties is updated. Proof. If a leader block is successfully committed, then from 1/2-Chain Quality we know that at least of half the blocks in

8

the causal history are from correct authors. These blocks will include timestamps from 2f +1 unique sources and so at least f +1 will be correct.

block and fills the corresponding entry. By Lemma 14 every committed leader updates the row of at least f +1 correct parties, and by Lemma 5 the median of the 2f +1 smallest hole timestamps is bounded by correct values. The threshold is therefore monotonically increasing. By Lemma 10 it eventually surpasses tx’s assigned timestamp, and tx is executed.

Lemma 15. In expectation, each round of consensus will update the local logical clock of each correct party. Proof. As in expectation 3 blocks per party will be committed and these blocks will definitely contain at least 1 timestamp pair from its author, then their entry in the logical table will be updated. Lemmas 14 and 15 give us that on average, the logical table of all correct processes, with a minimum of f +1 per wave, will be updated. These two lemmas together prove the final theorem that guarantees execution liveness:

VII. P ERFORMANCE E VALUATION A. Setup We implemented Tilikum starting from Narwhal/Tusk’s Rust original implementation4 . Our modifications span a total of 4, 000 LOCs, while our experimental scripts required 2, 500 additional LOCs. We backported some features of the production-ready implementation of Narwhal by Sui5 , namely the re-transmission of uncommitted certificates and the order in which batches are added to a block. Except when indicated otherwise (i.e., in §VII-C), we deploy the random delay network version of Tilikum in which K = f + 1 parties are tasked with including a transaction in one of their block.

Theorem 16. In expectation, the threshold computed locally by each party is always increasing, and new transactions are always being executed. Proof. By the safety property, each correct party will commit the same sequence of blocks and so have the same internal status for the Logical Table. The threshold is updated by taking the median value of the 2f +1 smallest timestamps for which we miss the successive value in the logical table. From lemma 5, this value is both lower- and upper-bound by correct values and if all correct values are getting updated, then the threshold also gets updated. As timestamps cannot decrease, the threshold is always increasing. This guarantees Execution Liveness in the average case, i.e., in random delay networks. We can also show that it holds in the general case by exploiting the fact that every block can be resubmitted and will therefore eventually be committed [11]. As a consequence, since every correct party will try to include in their blocks every transaction they have been assigned together with hole fillers, then every value in the Logical Table of correct parties will eventually be committed, and the execution threshold will regularly increase. This second way of looking at Execution Liveness gives us the guarantee that the threshold will eventually catch up, but does not allow us to perform any theoretical analysis on the additional latency.

Baselines. We compare Tilikum’s throughput and latency against those of Pompē [7], Themis [18], the FairDAG variants [17] and the vanilla Narwhal/Tusk [11]. Pompē implements ordering linearizability on top of HotStuff [9]. FairDAG-AB and FairDAG-RL respectively support ordering linearizability and γ-batch-order-fairness on top of any DAG-based algorithms that uses weak edges. We use FairDAG’s code6 , which we slightly adapted for a fair comparison against Tilikum. Our changes are described at the end of the section together with a theoretical comparison of Tilikum and FairDAG [17], focusing in particular on maximum theoretical throughput, real-life feasibility and design decisions. FairDAG is built on top of ResilientDB [24] and has a different concept of batches. A batch is a collection of transactions from the same client and is assigned a single timestamp. To fairly compare against Tilikum and Pompē [7], the batch size was set to 1. This value indicates the amount of client-submitted transactions that are treated as a single one in the system, which also mean a single timestamp is assigned to this batch. The released implementation of FairDAG does not support Theorem 17. Under full asynchrony, if K = 2f +1 (Sec. IV-A), the simulation of faulty parties. Consequently, we did not then the threshold computed by each correct party strictly evaluate it under this scenario. FairDAG’s numbers may increases infinitely often, and every submitted transaction is underrepresent its potential because of ResilientDB overhead; eventually executed. we contacted the authors to confirm our setup. Either way, Proof. Each transaction tx is assigned to 2f +1 parties, of its reliance on weak edges and high redundancy (Appx. A) which at least f +1 are correct. A round is certified when would have to be removed for production use, which would 2f +1 block authors are included, so it excludes the blocks only lower its throughput further. of at most f authors. By pigeonhole, at least one of the f +1 Experimental settings. All experiments were run on the correct parties tasked with tx has its block certified in every round following tx’s submission, hence tx appears in at least DAS5 distributed cluster [25]. Each individual run lasted 60 s one certified block of a correct party. By the eventual-commit and each experiment is repeated 5 times. Clients are assigned property of the DAG [11], this block is eventually committed, their own machine, while a party’s workers and primary are so the system has no infinite holes due to missing transactions. 4 https://github.com/asonnino/narwhal/ Each committed tx is bundled with 2f +1 timestamp pairs, 5 https://github.com/MystenLabs/sui/blob/narwhal-votes/narwhal and any correct party whose pair is not among them triggers 6 https://github.com/apache/incubator-resilientdb/commit/ a hole filler (Sec. IV-D) that is inserted in a subsequent 9e6c46f6f1d56ed88aae1034699c12d2097b1313

9

Tilikum-OL Pompe FairDAG-AB

Tilikum-OL Pompe FairDAG-AB

35000 30000

103

25000

Latency (ms)

Throughput (tx/s)

104

102

20000 15000 10000

101

5000 0

102

103

104

102

105

104

105

Fig. 3: Ordering Linearizability — Execution latency (↓) depending on transaction input rate (n = 16)

Fig. 2: Ordering Linearizability — Execution throughput (↑) depending on transaction input rate (n = 16)

Tilikum-BOF Themis FairDAG-RL

30000

25000

Latency (ms)

103

Throughput (tx/s)

103

Client input rate (tx/s)

Client input rate (tx/s)

20000

15000

10000

102

Tilikum-BOF Themis FairDAG-RL

5000

0

102

103

104

102

105

103

104

105

Client input rate (tx/s)

Client input rate (tx/s)

Fig. 5: γ-batch-order-fairness— Execution latency (↓) depending on transaction input rate (n = 16)

Fig. 4: γ-batch-order-fairness— Execution throughput (↑) depending on transaction input rate (n = 16)

colocated. Transactions have a fixed size of 128 bytes. Pompē’s implementation is based on libhotstuff which does not exchange transactions, it instead reaches consensus on their 32 bytes cryptographic hash digest, assuming that the actual transaction is sent for execution when confirmed. FairDAG’s implementation is based on ResilientDB [24] and operates analogously. Having the transaction size to be around the same size of the exchanged hash values in these protocols makes the comparison with Tilikum as fair as possible.

fixed parameters, clients sent 13,000 transactions per second, with 10 clients deployed; this rate sits at Tilikum-OL’s saturation point in Figs. 2 and 3, so the system runs under full load while we measure attack effects. Block and batch sizes were left unchanged. Two sets of experiments were performed, one with no faulty (silent) parties and varying number of arbitragers from 1 to 5 and another with a fixed amount of 3 arbitragers and varying the number of silent parties from 0 to 3. It is important to note that while the sluggish and speculative Workers build batches of 2, 000 bytes (around 16 transacattack do not imply that the party deviates from the protocol, the tions) or after a 1 s timeout. Primaries build blocks containing Fissure attack might lead to that happening. The experiments 256 bytes of payload, which is equivalent to 8 batches (each executing the fissure attack were carried out with the total batch is represented by a 32 bytes hash). A block can also be number of malicious parties (arbitragers + silent) below 1/3 built after a timeout of 2 seconds. of the total. In Tilikum, transactions are broadcast by clients to all parties and when a worker receives a transaction an extra B. Throughput and Latency Depending on Injection Rate communication step to the primary is required to assign a We first ran a set of experiments with N = 16 parties where Timestamp Pair. We kept the Narwhal/Tusk experiment code we aimed at finding the maximum achievable input rate for in which clients send transactions to only one party so that the each algorithm. We progressively increased the input rate until maximum achievable throughput can be showcased. the effective throughput stopped increasing or a substantial The security and fairness evaluation was performed with

increase in latency was observed. Latency and throughput are

10

Fig. 7: Execution throughput (↑) depending on the actual number of faulty parties (n = 16, with respectively up to 5 and 3 faults with OL and BOF)

Fig. 6: Ordering Linearizability — Consensus and execution throughput (↑, downward trend curves) and latency (↓, upward trend curves) as a function of redundancy degree K (n = 16)

reported in Figs. 2–5. Note that with transaction input rate we mean the amount of unique transactions inserted in the system, which results in at least f + 1 messages for each one. Most protocols follow a similar pattern: inserting more transactions increases throughput linearly until a stall point is reached. The system becomes saturated and we see an increase in latency and a decrease or flattening of throughput. All of Tilikum’s versions have higher latency at low input rates. This is a consequence of the system waiting for enough transactions to fill batches and blocks, so latency is mainly driven by the timeout settings.

Fig. 8: Execution latency (↓) depending on the number of faulty parties (n = 16)

C. Evaluating Data Redundancy

Fig. 6 reports the latency, consensus and execution throughput of Tilikum’s variants when changing the number K of parties that are assigned to include a transaction. We run these data needs to be exchanged more times, is reduced on average experiments with 16 parties, all parties behaving honestly, and by a factor of 4 when compared to Narwhal/Tusk [11]. Tilikum-OL remains faster than Pompē [7], with throughput varying the number K from 4 to 10. Execution throughput of 14,000 tx/s at N = 10, around 39 times higher on average, starts at approximately 9,500–10,000 tx/s for redundancy levels and 4,600 tx/s at N = 25, 81 times higher. Pompē’s runs between f +1 and f +3, then drops sharply to about 5,300 tx/s vary by an order of magnitude in both throughput and latency at 2f , and further decreases to roughly 3,000–4,000 tx/s near (latency from < 1 s to > 10 s), likely due to its time-slotted 2f +2–3f +1. In contrast, consensus throughput decreases more consensus stalling on bad timestamp clusters. gradually, from around 6,700 tx/s at f + 1 to approximately FairDAG’s consensus and execution throughput are always 4,000 tx/s at 3f + 1. Latency exhibits the opposite trend. Consensus latency increases steadily from roughly 200–400 ms identical, showing how the combination of redundancy and at low redundancy levels to approximately 13,000–14,000 ms weak edges allows transactions to be executed quickly. This is at 3f + 1. Execution latency grows even more sharply, rising also showcased by the low latency of the system. from around 2,000–3,000 ms at f + 1 to nearly 20,000 ms at The execution throughput of Tilikum-OL is, on average, 66 3f + 1. times higher than FairDAG-AB’s at N = 10 and 12 times higher at N = 25, although this might just be a consequence D. Throughput and Latency Depending on System Size of the underlying consensus protocol, the fact that the We now evaluate the throughput and latency of Tilikum-OL Tusk [11] implementation in ResilientDB [24] does not employ and Tilikum-BOF, benchmarking them against existing a worker-primary architecture, transaction redundancy and state-of-the-art fair ordering protocols. weak edges. The results for γ-batch-order-fairness show that Tilikum-BOF achieves a consensus and execution throughput Consensus and Execution Throughput. Figs. 9 and 11 around 8 times higher than FairDAG-RL at N = 10 and 41 report throughput when increasing the number of total parties. times higher at N = 25. Tilikum-BOF also exhibits throughput We can notice that the overhead incurred by Tilikum, as more around 2 times higher than Themis for all system sizes. Silent

11

Fig. 9: Ordering linearizability — Execution throughput (↑) depending on system size

Fig. 10: Ordering linearizability — Execution latency (↓) depending on system size

Fig. 11: γ-batch-order-fairness — Execution throughput (↑) depending on system size

Fig. 12: γ-batch-order-fairness — Execution latency (↓) depending on system size

parties have a very limited impact on the throughput of Tilikum-OL, as seen in Fig. 7. This can be mostly explained by transactions now being proposed by multiple parties.

manageable, but for the smallest system size this is 9 times slower than Pompē and 2 times slower than FairDAG-AB, while for the largest it’s 5 times slower than FairDAG-AB and 4 times faster than Pompē. For γ-batch-order-fairness, Tilikum-BOF’s latency is below 8s for N = 10 and below 5.5s for N = 25. This positions it at around 10 times slower than Themis. Tilikum-BOF is 9 times slower than FairDAG-RL at N = 10, but 3 times faster for the largest system size.

Consensus and Execution Latency. Figs. 10 and 12 report latency when increasing the system size. Latency is affected by the extra communication rounds required to collect timestamps, which is noticeable in the consensus latency. Execution latency is also impacted, as the threshold needs to reach specific values to allow committed transactions to be executed. The cost of managing the Logical Table is also not negligible. We notice that in the case of f = 5, shown in Fig. 8, when all correct parties are able to successfully insert a block in every round there is a slight decrease in execution latency, moving it closer to the maximum theoretical value of the consensus latency. FairDAG’s [17] usage of weak edges allows for the execution threshold to grow at a more consistent and reliable pace. This is visible in the low and consistent latency values. The time between receiving a transaction and it being included in a batch is slightly higher, as Tilikum requires two rounds of reliable broadcast. This results in latency being 1.2s at N = 10 and 2.9s at N = 25. The value remains

12

E. Reordering Attack Resistance. We evaluate the susceptibility of Tilikum, and Narwhal/Tusk to the fissure, sluggish and speculative attacks proposed by Zhang et al. [15]. In these attacks, a malicious party attempts to front-run a transaction included within a correct party’s block by generating a competing adversarial block. To achieve this, the attacker deviates from the standard consensus algorithm to ensure that their transaction is ordered before the victim transaction. In the context of Tilikum-OL, where the execution order is determined by timestamps rather than by the order in which transactions appear in blocks, we consider a frontrunning attack to be successful if the attacker successfully commits an attacking block and if at least one transaction from

TABLE I: Front-running success rate. Protocol

# Parties

# Faults

Fissure

Sluggish

Speculative

7 7 7

0 1 2

26.32% 14.29% 0.00%

36.59% 46.15% 43.75%

42.86% 63.89% 93.55%

provided through mechanisms such as median for leader-based systems or quorum conditions in leaderless cases.

Reordering attacks on DAG-based algorithms. Zhang et al. [15] identified the fissure, sluggish, and speculative front-running attacks on Narwhal/Tusk. In the fissure attack, 10 0 27.81% 44.77% 75.46% 10 1 36.11% 31.71% 66.67% attackers disconnect a victim’s block from the rest of the DAG, Tusk 10 2 50.00% 50.00% 57.58% forcing it to be ordered later by reducing its connectivity. In 10 3 – 60.00% 95.24% the speculative attack, attackers speculatively construct blocks Tilikum 10 – 25 0–5 0.00% (Resistant) with higher ordering priority to ensure their transactions precede the victim’s. Finally, in the sluggish attack, attackers deliberately create blocks in lower rounds that the ordering rule its block is executed before a transaction from a victim block. assigns higher priority, allowing them to be ordered ahead of Despite adopting this broad success criterion, our results (Tab. I) newer victim blocks. Mahe et al. [16] showed a similar attack confirm that Zhang and Kate’s attack are effective against the on DAG-Rider. The Ambush attack [39] targets γ-batch-order standard Narwhal/Tusk, with success rates ranging from 14% fairness and has been demonstrated on single-leader protocols. to 95% depending on the system configuration (system size Our experiments show that Tilikum perfectly defends against and number of active malicious parties), but they also exhibit the fissure, sluggish and speculative attacks. Authors of the a 0% success rate against Tilikum. ambush attack propose a defensive strategy, i.e., immediate transaction dissemination upon receival, which is what Narwhal VIII. R ELATED W ORK already does. Evaluating the impact of the ambush attack on DAG-based protocols. Recent DAG-based consensus DAGs is future work as it requires significant computing power. protocols improve block dissemination and reduce latency. DAG-Rider [10] builds a DAG via reliable broadcast and Commit-reveal. Commit-reveal schemes [40, 41] hide uses a shared coin to order blocks. Narwhal/Tusk [11] block contents (e.g., via threshold encryption) to mitigate separate mempool and consensus, enabling garbage collection front-running. While compatible with fair-ordering, they are by removing weak edges and outperforming DAG-Rider. orthogonal solutions and do not fully prevent reordering, since Bullshark [12] adds a synchronous fast path, while attackers can still exploit metadata or sender information. Mysticeti [19] leverages threshold clocks for pipelined IX. C ONCLUSION commits. Shoal [20] and Shoal++ [21] further reduce latency This paper presented Tilikum, a DAG-based fair-ordering through leader reputation, optimized commit rules, and parallel protocol that advances the state of the art by providing strong DAGs. Mahi-Mahi [13] introduces an uncertified DAG to fairness guarantees without sacrificing scalability or resilience. reduce delay, and Starfish [14] achieves linear communication Unlike prior works, Tilikum avoids reliance on weak edges, complexity via erasure coding. thereby enabling efficient garbage collection and reducing data Order fairness. Fair-ordering properties aim to prevent redundancy, while maintaining robustness against malicious adversarial reordering. Pompē [7] introduced ordering lineariz- clients. We proved that Tilikum ensures safety and liveness. ability using median timestamps. Aequitas [6] introduced γ- We presented two versions of Tilikum, namely Tilikum-OL batch-order fairness, which Themis [18] and Lyra [23] later and Tilikum-BOF, that respectively guarantee the ordering extended. Wendy [26] proposed probabilistic and timed fairness linearizability and γ-batch-order fairness ordering properties. to guarantee termination. Other designs include AOAB [27] Our experimental evaluation confirmed that Tilikum matches (threshold signatures), Alpos et al. [28] (anti-sandwiching), or outperforms existing fair-ordering systems: Tilikum-OL SpeedyFair [29] (decoupling ordering and consensus). Subse- sustains 14,000 tx/s at N =10 with 1.2 s latency (39× Pompē’s quent leader-based fairness work has explored data-dependent throughput) and stays 4× faster than Pompē at N =25, while ordering [30], weight-based sorting [31], position fairness [32], Tilikum-BOF doubles Themis’ throughput at every evaluated cross-round graph maintenance [33], bounded unfairness [34], system size. Tilikum also fully prevents the reordering attacks and minimal batch variants [35], but these target linear of Zhang et al. [15], dropping their success rate from 14%–95% on vanilla Narwhal/Tusk to 0%. blockchains and are orthogonal to this work. Tusk

FairDAG [17] adds γ-batch-order fairness to DAG protocols that use weak edges, we compare extensively against FairDAG in this paper. TEE-based approaches [36] and κ-differential fairness schemes [37] have also been explored. Amores-sesar et al. [38] proposed a timestamping mechanism to equip generic consensus protocols with the concept of time. This approach uses local timestamps provided by parties, which is protocol independent, while byzantine fault tolerance is

R EFERENCES [1] [2] [3]

13

S. Nakamoto. “Bitcoin: A peer-to-peer electronic cash system”. In: (2008). G. Wood et al. “Ethereum: A secure decentralised generalised transaction ledger”. In: Ethereum project yellow paper 151.2014 (2014), pp. 1–32. P. Schueffel. “DeFi: Decentralized finance-an introduction and overview”. In: Journal of Innovation Management 9.3 (2021), pp. I–XI.

[4] [5]

[6]

[7]

[8] [9]

[10]

[11]

[12]

[13]

[14]

[15]

[16] [17] [18]

[19]

[20]

Flashbot. Flashbot MEV Explore. 2024. URL: https://explore. flashbots.net/ (visited on 06/12/2024). P. Daian, S. Goldfeder, T. Kell, Y. Li, X. Zhao, I. Bentov, L. Breidenbach, and A. Juels. “Flash boys 2.0: Frontrunning, transaction reordering, and consensus instability in decentralized exchanges”. In: arXiv preprint arXiv:1904.05234 (2019). M. Kelkar, F. Zhang, S. Goldfeder, and A. Juels. “Orderfairness for byzantine consensus”. In: Advances in Cryptology– CRYPTO 2020: 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17–21, 2020, Proceedings, Part III 40. Springer. 2020, pp. 451–480. Y. Zhang, S. Setty, Q. Chen, L. Zhou, and L. Alvisi. “Byzantine ordered consensus without byzantine oligarchy”. In: 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20). 2020, pp. 633–649. M. Castro and B. Liskov. “Practical Byzantine Fault Tolerance”. In: OSDI. 1999. M. Yin, D. Malkhi, M. K. Reiter, G. G. Gueta, and I. Abraham. “HotStuff: BFT consensus with linearity and responsiveness”. In: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing. 2019, pp. 347–356. I. Keidar, E. Kokoris-Kogias, O. Naor, and A. Spiegelman. “All you need is DAG”. In: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing. 2021, pp. 165–175. G. Danezis, L. Kokoris-Kogias, A. Sonnino, and A. Spiegelman. “Narwhal and tusk: a dag-based mempool and efficient bft consensus”. In: Proceedings of the Seventeenth European Conference on Computer Systems. 2022, pp. 34–50. A. Spiegelman, N. Giridharan, A. Sonnino, and L. KokorisKogias. “Bullshark: Dag bft protocols made practical”. In: Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. 2022, pp. 2705–2718. P. Jovanovic, L. Kokoris-Kogias, B. Kumara, A. Sonnino, P. Tennage, and I. Zablotchi. “Mahi-mahi: Low-latency asynchronous bft dag-based consensus”. In: 2025 IEEE 45th International Conference on Distributed Computing Systems (ICDCS). IEEE. 2025, pp. 549–559. N. Polyanskii, S. Mueller, and I. Vorobyev. “Starfish: A high throughput BFT protocol on uncertified DAG with linear amortized communication complexity”. In: Cryptology ePrint Archive (2025). J. Zhang and A. Kate. “No fish is too big for flash boys! frontrunning on DAG-based blockchains”. In: 2025 IEEE Annual Computer Security Applications Conference (ACSAC). IEEE. 2025, pp. 1065–1080. E. Mahe and S. Tucci-Piergiovanni. “Order Fairness Evaluation of DAG-based ledgers”. In: arXiv preprint arXiv:2502.17270 (2025). D. Kang, J. Chen, T. T. A. Dinh, and M. Sadoghi. “FairDAG: Consensus Fairness over Multi-Proposer Causal Design”. In: VLDB. 2026. M. Kelkar, S. Deb, S. Long, A. Juels, and S. Kannan. “Themis: Fast, strong order-fairness in byzantine consensus”. In: Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security. 2023, pp. 475–489. K. Babel, A. Chursin, G. Danezis, A. Kichidis, L. KokorisKogias, A. Koshy, A. Sonnino, and M. Tian. “Mysticeti: Reaching the Latency Limits with Uncertified DAGs”. In: 32nd Annual Network and Distributed System Security Symposium, NDSS 2025, San Diego, California, USA, February 24-28, 2025. The Internet Society, 2025. A. Spiegelman, B. Arun, R. Gelashvili, and Z. Li. “Shoal: Improving dag-bft latency and robustness”. In: International Conference on Financial Cryptography and Data Security. Springer. 2024, pp. 92–109.

14

[21]

[22]

[23]

[24] [25]

[26]

[27]

[28]

[29] [30] [31]

[32] [33] [34]

[35] [36] [37] [38] [39]

B. Arun, Z. Li, F. Suri-Payer, S. Das, and A. Spiegelman. “Shoal++: High Throughput {DAG}{BFT} Can Be Fast and Robust!” In: 22nd USENIX Symposium on Networked Systems Design and Implementation (NSDI 25). 2025, pp. 813–826. G. Danezis, J. Komatovic, L. Kokoris-Kogias, A. Sonnino, and I. Zablotchi. “Byzantine Consensus in the Random Asynchronous Model”. In: 39th International Symposium on Distributed Computing (DISC 2025). Vol. 356. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025, 28:1–28:22. P. Zarbafian and V. Gramoli. “Lyra: Fast and scalable resilience to reordering attacks in blockchains”. In: 2023 IEEE International Parallel and Distributed Processing Symposium (IPDPS). IEEE. 2023, pp. 929–939. S. Gupta, S. Rahnama, J. Hellings, and M. Sadoghi. “Resilientdb: Global scale resilient blockchain fabric”. In: arXiv preprint arXiv:2002.00160 (2020). H. Bal, D. Epema, C. De Laat, R. Van Nieuwpoort, J. Romein, F. Seinstra, C. Snoek, and H. Wijshoff. “A medium-scale distributed system for computer science research: Infrastructure for the long term”. In: Computer 49.5 (2016), pp. 54–63. K. Kursawe. “Wendy, the Good Little Fairness Widget: Achieving Order Fairness for Blockchains”. In: AFT ’20: 2nd ACM Conference on Advances in Financial Technologies, New York, NY, USA, October 21-23, 2020. ACM, 2020, pp. 25–36. V. Gramoli, Z. Lu, Q. Tang, and P. Zarbafian. “AOAB: optimal and fair ordering of financial transactions”. In: 2024 54th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN). IEEE. 2024, pp. 377–388. O. Alpos, I. Amores-Sesar, C. Cachin, and M. Yeo. “Eating Sandwiches: Modular and Lightweight Elimination of Transaction Reordering Attacks”. In: 27th International Conference on Principles of Distributed Systems (OPODIS). 2024. K. Mu, B. Yin, A. Asheralieva, and X. Wei. “Separation is good: A faster order-fairness Byzantine consensus”. In: (2024). H. Nagda, S. P. Singhal, M. J. Amiri, and B. T. Loo. “Rashnu: Data-Dependent Order-Fairness”. In: Proc. VLDB Endow. (2024). W. Chen, Y. Feng, J. Zhang, Z. Cai, H.-N. Dai, and Z. Zheng. “Auncel: Fair Byzantine Consensus Protocol with High Performance”. In: IEEE INFOCOM 2024 - IEEE Conference on Computer Communications. 2024. Y. Wang, X. Xing, G. Wang, Y. Zhang, and P. Li. “Dikaios: Position-anchored group ordering with reputation for fair and efficient Byzantine consensus”. In: Comput. Netw. (2025). P. Ren, H. Dong, N. Sohrabi, Z. Tari, and P. Zhang. ProofCarrying Fair Ordering: Asymmetric Verification for BFT via Incremental Graphs. 2025. eprint: 2510.14186. A. Kiayias, N. Leonardos, and Y. Shen. “Ordering Transactions with Bounded Unfairness: Definitions, Complexity and Constructions”. In: Advances in Cryptology – EUROCRYPT 2024: 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2024. G. Ramseyer and A. Goel. Fair Ordering in Replicated Systems via Streaming Social Choice. 2024. arXiv: 2304.02730 [cs.CR]. M. Ciampi, A. Kiayias, and Y. Shen. “Universal composable transaction serialization with order fairness”. In: Annual International Cryptology Conference. Springer. 2024, pp. 147–180. C. Cachin, J. Mićić, N. Steinhauer, and L. Zanolini. “Quick order fairness”. In: International Conference on Financial Cryptography and Data Security. Springer. 2022, pp. 316–333. I. Amores-Sesar and M. Yeo. Rethinking Consensus with Time as a Primitive. Cryptology ePrint Archive, Paper 2025/1975. 2025. E. Park, T. Yoon, H. Nam, D. Maram, and M. S. Kang. “On Frontrunning Risks in Batch-Order Fair Systems for

[40] [41] [42]

Blockchains (Extended Version)”. In: Cryptology ePrint Archive (2025). D. Malkhi and P. Szalachowski. “Maximal extractable value (mev) protection on a dag”. In: arXiv preprint arXiv:2208.00940 (2022). R. Fernando, G.-V. Policharla, A. Tonkikh, and Z. Xiang. “TrX: Encrypted Mempools in High Performance BFT Protocols”. In: Cryptology ePrint Archive (2025). M. A. Vafadar and M. Khabbazian. “Condorcet Attack Against Fair Transaction Ordering”. In: 5th Conference on Advances in Financial Technologies. 2023.

A PPENDIX A D ETAILED C OMPARISON WITH FAIR DAG In this section we discuss limitations of FairDAG [17], whether they could be mitigated and explain why Tilikum does not share them. The first part discusses the disadvantages of using weak edges and having redundant transactions in the DAG. Finally, we propose three attack scenarios where a single malicious client can break liveness for the system, and how to prevent this. Table II summarizes the main difference between Tilikum and FairDAG. A. Weak Edges & Redundancy FairDAG [17] relies on weak edges for its implementation. As a transaction needs to appear 2f +1 times in the DAG to be executed, losing the strong theoretical guarantees given by the Validity property is not permissible. As explained by Danezis et al. [11], maintaining weak edges comes at the cost of losing garbage collection. Without garbage collection, the system is unusable in practice, which we believe is a big design shortcoming. The solution adopted by Narwhal/Tusk to achieve validity in the absence of weak edges is to retransmit the payload (i.e., transactions) of blocks that were not committed [11] together with the payload of the block for the round where this is detected. This approach cannot be easily adapted to FairDAG. The execution threshold relies on the assumption that the timestamps in the block created in round r by a replica are always smaller than the ones in future rounds (i.e., r + i for i > 0). If we allow the retransmission of the uncommitted payload of a block created in round r during r + i, the blocks of rounds r < r′ < r + i will effectively include ordering indicators that are larger than the ones in the block for r + i, breaking the assumption. Removing the need for weak edges is then not trivial and reduces the applicability of FairDAG in a realistic scenario. To remove weak edges, replicas should rely on a way to detect the actual exact order of block’s payloads and detect missing ones that might be retransmitted. A mechanism similar to Tilikum’s logical clocks could be employed. Apart from disallowing garbage collection, the way in which FairDAG computes the execution threshold and its reliance on weak edges does not allow for transactions to be inserted into the DAG in a different order than the one shown by their timestamps. This assumption is relatively strong and can be problematic when paired with an asynchronous network. Tilikum does not require transactions to appear more than once in the DAG for it to be executed, as all necessary information is bundled in the batch’s metadata. As now the DAG will have redundant information, if we assume that no other factor is bottlenecking the system, its throughput should be at most the one achieved by the underlying DAG layer divided by the amount of (correct) parties. This does not seem to be the case in the plots provided by the authors [17]. The author re-implemented Narwhal/Tusk [11] on the same framework they used for FairDAG [17], ResilientDB [24]. We think that the reason for this discrepancy is found in the way transactions are treated.

15

TABLE II: Comparison between DAG-based fair ordering approaches

FairDAG [17]

Mempool time complexity Consensus time complexity Garbage collection Expected tx redundancy in DAG Expected # signs per tx in DAG

Execution Liveness with f faulty fast replicas Robust against malicious clients Transaction Insertion Order Rebroadcasts

Tilikum (this work)

NA unmodified (full blocks of transactions) % 3f + 1

Narwhal/Tusk with full redundancy (FairDAG’s approach without weak edges) 2 unmodified (blocks of batch digests) ! 3f + 1

3f + 1

3f + 1

!

%

K(2f + 1), or K with BLS aggregate signatures (not implemented) !

%(!with perf. degradation) In-order None

%(!with perf. degradation) Out-of-order Full block of transactions

4 unmodified (blocks batch digests) ! K ∈ [f + 1, 3f + 1]

of

! Out-of-order Hole Fillers + Batch digests

ResilientDB [24] allows client to batch transactions. These completely blocking the system. We then suggest two mitigation batches are then treated by the underlying protocol (in this strategies which might have consequences on the scalability case FairDAG on top of Narwhal/Tusk) as a single transaction. of the system. The last attack strategy is more inherent to the This results in a batch of transactions being assigned a single system’s assumptions. timestamp, removing fairness between them. Moreover, the The main way clients can misbehave is by not actually throughput values were effectively multiplied by the batch size. broadcasting their transactions, but instead send them to a The default value available in the code was of 400, which means subset of replicas. This has negative outcomes for the client, that each 400 transactions were assigned a single timestamp. as also pointed out by the authors, as malicious replicas could We also noticed that the script extracting the throughput censor or delay the inclusion of transactions in their blocks. and latency values from the execution logs was intentionally However, the system makes no assumption that correct replicas excluding values lower than 1, 000. While we do not know will try to include transactions that have not been sent directly the rationale behind this decision, we think it is not a correct by a client. behavior. Both Tilikum and FairDAG’s execution speeds depend A transaction received only by a subset of parties will then on a threshold which might not grow or grow particularly be included only by that same subset of replicas. We will now slowly in periods of network asynchrony or other types of see how different sizes of this subset impact the system, with faults. We think that measuring the system’s behavior under two main types of attacks. these circumstances is more correct, and we did so in our Let us start with the simple case where a client sends a experiments. transaction to S < f +1 parties. In this case, those parties will use some of their block space to include this transaction, B. Attacks on Liveness with Malicious Clients thus reducing throughput. The LPAOI of this transaction will FairDAG assumes that “clients generate and submit transac- however always increase. The entry in lp_ois for the S tions to replicas, then await execution results in response”, and parties that received it will be constant, but for all other parties that “there is no assumption that clients always behave cor- it will keep increasing as the DAG expands. Given that the rectly; they may exhibit arbitrary or malicious behavior” [17]. LPAOI is the (f +1)th lowest value in the array and there are This however clashes with the later assumption that “clients less than f +1 constant values, then it will always be changing. The only consequence of this attack is reduced throughput, broadcast their transactions to all replicas” [17]. If we actually assume arbitrary client behavior, the system as block space is taken by this unexecutable transaction, and suffers from some of its design choices. We now propose three higher resource usage for the parties that need to keep track scenarios in which malicious clients can halt the system and of the Ordering Indicators for this transaction. break liveness. The first two scenarios are slight variations The second possibility for clients is more impactful. If a of each other, but they achieve different results. The first one malicious client sends a transaction t to f +1 < S < 2f +1 leads to an overall slowdown in throughput, while the second parties, the LPAOI will be eventually computed to a constant can potentially stop the execution threshold from advancing, value, but the transaction will never be executed. As the rest of

16

the DAG grows, the LPAOI of t will eventually be the smallest Algorithm 3 First-Sight Timestamping at party pi and become the execution threshold for the system. The 1: Initialization: 2: lc i ← 0 ▷ local logical counter transaction t will never receive enough ordering indicators for 3: known i ← ∅ ▷ set of already-timestamped transactions execution and so it will always remain in the set of transactions 4: store i ← {} ▷ map: tx 7→ (lc, φ) without AOI, and always be the transaction determining the execution threshold. The system will then fully come to a halt, 5: upon receive transaction tx from client or replica do with the DAG continuing to expand, but no new transaction 6: if tx ∈ known i then 7: return ▷ timestamp only on first sight being executed. 8: end if There are two ways in which this issue can be solved, and 9: lc (tx ) ← lc i ▷ assign current counter value they both have some impact on the overall throughput of 10: φ i(tx ) ← C LOCK () ▷ record physical time i the system. The simpler way requires correct replicas to re- 11: lc i ← lc i + 1 broadcast all transactions they receive to all other replicas, 12: known i ← known i ∪ {tx }
similarly to the third mitigation proposed by Vafadar et al. [42]. 13: store i [tx ] ← lc i (tx ), φi (tx ) The second attack scenario is fully stopped by this mitigation. At least one correct replica will receive the transaction and broadcast it to all other replicas, making it eventually executable. first-sight timestamping (Alg. 3, Sec. IV-A), batch sealing and The first attack scenario is still possible, but its impact was DAG block creation (Alg. 4, Sec. IV-B), execution-threshold computation for Tilikum-OL (Alg. 5, Sec. IV) and per not as severe as the second one to begin with. If we want to fully stop the first attack as well, we can sub-DAG commit graph processing for Tilikum-BOF (Alg. 6, introduce a way for replicas to include transactions in their Sec. V-C). The notation below is shared by all algorithms. blocks even if they were not received by a client (or by another replica during the re-broadcasting step described above). A Algorithm 4 Batch Sealing (proposer side) and DAG block correct replica that receives a valid block including a transaction creation (round r) at party pi digest d that was not received by any client, can consider the 1: procedure S EAL BATCH(batch) ▷ batch: list of transactions to receipt of this block as seeing the transaction for the first propose time, thus assigning its own ordering indicator and adding d to its next block. This is similar to what Tilikum does. A 2: ▷ Round 1: collect 2f +1 timestamp vectors request for timestamps for a specific batch may include unseen 3: broadcast ⟨T S R EQUEST, batch⟩ to all parties 4: replies ← {} transactions, which are then assigned a Timestamp Pair on the 5: wait until |replies| ≥ 2f +1 spot. 6: upon receive ⟨T S R EPLY, batch, ⃗vj , σj ⟩ from pj do The last way malicious clients can influence the system 7: if V ERIFY S IG(σj ,pj ) then  has to do with how FairDAG stores transactions in the 8: replies[pj ] ← (lc j (tx ), φj (tx )) tx ∈batch DAG. Transactions are actually not stored in the ledger, but 9: end if a cryptographically secure digest is used instead to reduce ▷ Round 2: reliable storage of sealed batch network and storage usage. This works correctly assuming that 10: 11: sealed ← (batch, replies) all replicas have access to all transactions, and have a fast way 12: broadcast ⟨S TORE R EQ, sealed ⟩ to all parties to match the committed digest to the actual transaction content. 13: acks ← {} A malicious client partially sending a transaction, enough times 14: wait until |acks| ≥ 2f +1 upon receive ⟨S TORE ACK, h, σj ⟩ from pj do to allow execution (i.e., 2f +1), can stop parties that did not 15: if V ERIFY S IG(σj , pj ) then receive it from knowing its contents, stopping their ability to 16: 17: acks[pj ] ← σj maintain the correct state. 18: end if This attack is fully mitigated by the first strategy described 19: return h ← H ASH(sealed ) ▷ ready for inclusion in DAG above. If at least one correct replica sees the transaction, they block will broadcast it allowing every other correct party to store it. 20: end procedure Note that Tilikum does not suffer from any of the above  B LOCK(r) issues, all information required for executing a transaction 21: procedure C REATE 22: payloads ← H ASH(sb) | sb ∈ pi .sealedReady is available in any block including the transaction and the 23: parents ← collect 2f +1 certificates from round r−1 execution threshold always grows, at least at the same speed 24: fillers ← C OMPUTE H OLE F ILLERS( ) ▷ Alg. 2 block ← (pi , r, parents, payloads, fillers) as the slowest correct node. We believe that one of the above 25: proceed with Narwhal consensus protocol mitigations should be implemented in FairDAG [17], so that 26: 27: end procedure their impact on the performance metrics can be measured. A PPENDIX B A DDITIONAL P SEUDOCODE

Notation. Each party pi maintains a monotonically increasing local counter lc i and has access to a UNIX physical clock For completeness, this appendix collects pseudocode for φi (·). A timestamp pair for transaction tx at party pi is procedures of Tilikum that were deferred from the main text: (lc i (tx ), φi (tx )). The set of K parties responsible for in-

17

cluding tx in a block is determined by H(tx ) (a deterministic hash-based assignment). Algorithm 5 Execution Threshold via Logical Table (TilikumOL) 1: function T HRESHOLD(L) 2: H←[] ▷ collect head timestamps 3: for all party pj do 4: head j ← smallest lc in L[pj ] where lc+1 is absent 5: H.A PPEND(head j .φ)

Algorithm 6 Per-commit graph processing (Tilikum-BOF) 1: State (long-lived): 2: graphs ← [ ] 3: node[tx] with fields count, seqnums, graph 4: Fp ← 0 for every party p

6: end for 7: sort H in ascending order
8: return M EDIAN H[1..2f +1] 9: end function

5: procedure P ROCESS S UBDAG(Lr , Ar ) 6: Gr ← N EW G RAPH(r); graphs.P USH(Gr ) 7: 8: 9: 10: 11: 12: 13:

▷ Advance frontiers and grow count for all (p, tx , ℓ) ∈ Ar ∪ HoleFillers(Ar ) do U PDATE LVEC(p, tx , ℓ) if Fp advanced past tx for the first time then node[tx].count += 1 end if end for

▷ Admit transactions to Gr for all tx updated this round do if node[tx].graph = ⊥ and node[tx].count ≥ n(1−γ)+ f + 1 then 17: Gr .nodes.A DD(tx) 18: node[tx].graph ← Gr 19: end if 20: end for 14: 15: 16:

21: 22: 23: 24: 25: 26: 27:

▷ Aggregate pairwise weights and add edges for all newly admitted tx ∈ Gr , tx′ ∈ Gr .nodes do update WeightL (tx, tx′ ) from new contributors if Weight ≥ n(1−γ) + f + 1 and no edge exists then add edge in direction of larger weight end if end for

28: ▷ Finalize tournaments in round order 29: for all G ∈ graphs in round order do 30: if G is not a tournament then break 31: end if 32: [S1 , . . . , Ss ] ← TARJAN SCC(G) 33: j ∗ ← max{j | ∃ tx ∈ Sj , node[tx].count ≥ 2f +1} 34: for j = 1, . . . , j ∗ do 35: append Sj to final ordering 36: end for 37: for j = j ∗ +1, . . . , s do 38: node[tx].graph ← ⊥ for tx ∈ Sj 39: end for 40: release G from graphs 41: end for 42: end procedure

18