# Tilikum: Transaction Fair Ordering on a DAG without Weak Edges

Crypto.world

> DeFi transactions are order-dependent, so whoever controls ordering can extract BEV; Ethereum-style linear chains have attracted many fair-ordering designs, but DAG-based consensus protocols, despite…

**arXiv**: 2606.27250

**Published**: 2026-06-25

**Authors**: Giulio Segalini, Yigit Çolakoğlu, Marko Putnik, Jérémie Decouchant

## AI summary

## Overview

**Research area:** Blockchain consensus and transaction fair ordering, specifically DAG-based Byzantine fault-tolerant ledgers and Blockchain Extractable Value (BEV) mitigation.

**Technical level:** Advanced. The paper assumes familiarity with BFT state-machine replication, Narwhal/Tusk-style DAG mempools, quorum thresholds, and the definitions of ordering linearizability and γ-batch-order fairness.

**Scope (one sentence):** The paper presents Tilikum, a DAG-based fair-ordering ledger protocol with two variants (Tilikum-OL for ordering linearizability and Tilikum-BOF for γ-batch-order fairness) that eliminates weak edges, restores garbage collection, and is evaluated against Narwhal/Tusk, Pompē, Themis and FairDAG.

## What This Paper Is About

DeFi transactions are order-dependent, so whoever controls ordering can extract BEV; Ethereum-style linear chains have attracted many fair-ordering designs, but DAG-based consensus protocols, despite their throughput advantages, remain largely unprotected apart from FairDAG. FairDAG, however, requires full transaction redundancy across replicas and relies on weak edges, which prevents garbage collection, and it can be stalled by malicious clients that broadcast transactions to only a subset of replicas. The paper's goal is a DAG-based fair-ordering protocol that keeps the performance of the DAG paradigm while dropping weak edges entirely and remaining live under malicious clients.

## Key Contributions

1. **Two fair-ordering variants on a DAG.** Tilikum-OL enforces ordering linearizability and Tilikum-BOF enforces γ-batch-order fairness, built from a dual-timestamping mechanism (a logical counter plus a UNIX physical clock value per party) combined with sealed batches, a Logical Table that tracks sequence holes, and median-based execution thresholds that define safe points for execution.
2. **The first weak-edge-free DAG-based fair-ordering protocol.** By removing references from a block at round r_b to a block at round r_a < r_b − 1, the design restores garbage collection, which the authors describe as a prerequisite for production deployment. The paper formally proves execution safety and liveness for both variants, along with ordering linearizability and γ-batch-order fairness respectively.
3. **A liveness attack on FairDAG with malicious clients.** The authors identify performance and liveness attacks in which malicious clients selectively broadcast transactions to a subset of replicas, harming or halting execution; Tilikum is claimed not to be vulnerable to this attack by design.
4. **An implementation and evaluation, including under attack.** Tilikum is implemented as an extension of Narwhal/Tusk, with source code to be open-sourced upon acceptance, and benchmarked against Themis, Pompē and FairDAG.

## Main Findings

- **Throughput at N = 10:** Tilikum-OL sustains 14,000 tx/s at N = 10 with 1.2 s latency, which the paper describes as 39× Pompē's throughput at the same scale.
- **Scaling advantage:** Tilikum-OL remains 4× faster than Pompē at N = 25.
- **Batch-order fairness variant:** Tilikum-BOF doubles Themis' throughput at every evaluated system size.
- **Resistance to DAG reordering attacks:** Under the reordering attacks of Zhang et al., which succeed on vanilla Narwhal/Tusk between 14% and 95% of the time, Tilikum-OL drops the success rate to 0%.
- **System-size requirements:** Tilikum-OL assumes n ≥ 3f+1, matching the minimum need for consensus. Tilikum-BOF requires n > f(2γ+1)/(2γ−1), which simplifies to n ≥ 3f+1 when γ = 1; this equals the requirement of FairDAG-RL, whereas Themis assumes n > f(2γ+2)/(2γ−1), i.e., at least 4f+1 when γ = 1.
- **Redundancy parameter:** Tilikum sets K = f+1 in random delay networks and K = 2f+1 in asynchronous networks, where 0 < K ≤ n−1 parties are tasked with including each transaction based on the hash of the transaction.
- **Consensus-level expectation:** The paper proves that, in expectation, a leader is committed every 7 rounds in a network with an asynchronous adversary (a 1/3 chance of committing a valid block, consensus run every 3 rounds, giving 9 rounds before accounting for the shared round between waves).
- **BEV motivation figures cited:** EigenPhi reports more than $2M extracted from Ethereum DeFi in a single week (snapshot, June 2024), and Flashbots' MEV-Explore measured monthly extraction rates around $100M throughout 2022.

## Methodology in Plain English

The authors start from Narwhal/Tusk, a DAG-based protocol where blocks of transaction batches are disseminated separately from the ordering step. Their central problem is that fair ordering needs many independent parties to timestamp or locally order each transaction, and a DAG gives no single leader that can collect this information.

Their answer is to have each party stamp every transaction it sees with a signed pair made of a local logical counter and a UNIX clock value. A transaction is bundled into a "sealed batch" only after its proposer has collected 2f+1 signed timestamp vectors and 2f+1 acknowledgments of reliable storage; sealed batches are the only thing that can enter a DAG block. Each party maintains a Logical Table that maps each party to its sorted list of timestamp pairs and exposes "holes" — counters not yet seen in a committed block. Because a DAG without weak edges can drop blocks carrying late timestamps, blocks also carry "hole fillers": signed metadata that let other parties advance the stuck rows. Execution safe points come from taking the head of each row, extracting 2f+1 of the smallest UNIX timestamps, and computing their median as a threshold; transactions with a final timestamp at or below the threshold are executed in sorted order.

For the batch-order-fairness variant, hole fillers are extended to carry transaction digests, and a dependency graph is instantiated fresh at each leader commit, following Themis with modifications inspired by FairDAG-RL. Edges are added between transactions whose pairwise weighting crosses n(1−γ)+f+1, and a graph is finalized once it is a tournament, condensed with Tarjan's algorithm and topologically sorted, with a live-count re-evaluation at finalization to preserve liveness. The protocol is then proven correct using the Tusk safety and liveness lemmas plus lemmas on the median of 2f+1 values, and benchmarked against Narwhal/Tusk, Pompē, Themis and FairDAG.

## Why This Matters

**Impact on research.** The paper connects two previously separate lines of work — DAG-based consensus and fair transaction ordering — and shows that fairness does not have to come at the cost of weak edges or full transaction redundancy. It also documents a concrete liveness attack surface (malicious clients broadcasting to a subset of replicas) that prior DAG fair-ordering work did not address, which reframes how such protocols should be specified and evaluated.

**Real-world applications.**

- Decentralized exchanges where buyers and sellers are matched based on prior market interactions and ordering determines who trades at what price.
- Lending protocols that dynamically adjust interest rates based on preceding interactions, making the position of a transaction economically significant.
- High-throughput DeFi infrastructure built on DAG-based consensus, which the paper argues is being adopted for scalability and performance.
- Validator and mempool operators who need garbage collection to make a ledger deployable in production, which weak-edge-based designs preclude.

**Industry relevance.** The evaluation is against production-adjacent systems (Narwhal/Tusk is described as deployed in production and as the basis of several further works), the implementation is an extension of Narwhal/Tusk, and the reported throughput and latency figures are framed as execution-level metrics rather than only consensus-level ones — the numbers operators actually care about.

## Future Directions

- Extending support from random delay networks to fully asynchronous networks, which the paper says only requires setting K to 2f+1 and results in slightly lowered performance; the magnitude of that cost is an open evaluation question.
- Reducing the overhead of hole-filler publication in Tilikum-BOF, where a party must supply fillers for all missing logical counters rather than just the head, which the authors note makes it harder for lagging parties to publish new local orderings.
- Hardening and testing the design against adversarial clients and other DAG-specific reordering strategies beyond the attacks of Zhang et al. and the FairDAG liveness attack identified in the appendix.
- Deployment experience with garbage collection in a live DAG ledger, since the weak-edge-free property is argued as a prerequisite for production but is evaluated in a benchmark setting.

## Target Audience

Consensus-protocol researchers and graduate students working on BFT and DAG-based ledgers; protocol engineers at blockchain infrastructure and DeFi teams who need fair ordering without giving up throughput or garbage collection; and readers already familiar with Narwhal/Tusk, Pompē, Themis or FairDAG who want to understand how fairness guarantees can be reconstructed without weak edges.

## Authors’ 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…

[The full abstract on arXiv](https://arxiv.org/abs/2606.27250)

[Read the original paper](https://arxiv.org/abs/2606.27250)

---

Canonical: https://crypto.world/paper/tilikum-transaction-fair-ordering-on-a-dag-without-weak-edges-2606.27250
