DAGs: Neither Chain Nor Tree, But a Structure for Causality

Git's commit history, the Merkle DAG that IPFS uses to bind content together, and ledgers like the Tangle or GHOSTDAG that try to stretch a blockchain from a single "chain" into a "mesh," all of them rest on the same structure: the DAG (Directed Acyclic Graph). One simple constraint, "following edges never leads back to where you started," turns out to be the natural language for expressing causality in distributed systems. Here is the full story, from definition to real-world examples.

What is a DAG: definitions and topological sorting

A DAG (Directed Acyclic Graph) is exactly what its name says: a directed graph (edges between nodes have a direction) that is also acyclic (following edges, no matter how far, can never lead back to a node you started from). There is never a path where chasing a node's descendants eventually brings you back to that same node; that is what "acyclic" means, and it forces every edge in a DAG to flow, in some sense, only "forward."

The difference from a tree comes down to whether a node can have more than one parent. In a tree, every node has exactly one parent (the root has zero), so paths can branch but never merge back together. A DAG lifts that restriction and allows multiple paths to converge on a single node. A tree is really just a special case of a DAG, which is another way of saying a DAG is a strictly more expressive structure than a tree.

• A topological ordering always exists: a directed graph admits a topological ordering (a linear arrangement of nodes where every edge points from earlier to later) if and only if it is acyclic. Any DAG is guaranteed to have at least one such ordering.
• Reachability defines a partial order: define A ≤ B when B is reachable from A by following edges. This relation satisfies reflexivity, antisymmetry, and transitivity: a partial order. Acyclicity is exactly what makes antisymmetry hold (if A ≤ B and B ≤ A, then A = B).
• Why it is only a "partial" order: unlike a total order, a partial order does not require every pair of nodes to be comparable. Two nodes with no ancestor/descendant relationship to each other are said to be concurrent: neither one can be said to come "before" the other.
• A topological ordering is not unique: a given DAG can admit several valid topological orderings. Whenever a scenario demands "the one true order," an additional ordering rule has to be supplied on top of the DAG itself.

Why distributed systems reach for DAGs: causality as a partial order

Distributed systems have no shared physical global clock, so there is no principled way, without an outside observer, to pin down a single total order for "the order in which every event occurred." What can be defined, however, is whether one event could possibly have caused another: causality. Leslie Lamport formalized this in his 1978 paper "Time, Clocks, and the Ordering of Events in a Distributed System" as the happened-before relation (written →). It is a partial order, not a total order: if A and B are not related by happened-before in either direction, they are said to be concurrent.

The mechanism that actually computes the happened-before relation is the vector clock (Fidge and Mattern, both 1988). Each node maintains a vector of "how many events I have observed from each other node," updated on every message send and receive. What this machinery implicitly builds is nothing other than a DAG, with events as nodes and direct causal dependencies as edges. In other words, the DAG is not some special invention for expressing causality in distributed systems; it is simply a visualization of the mathematical structure that the happened-before relation already has.

• No forced serialization of independent work: enforcing a total order makes genuinely unrelated operations wait on each other, and leaves the system stuck during a network partition. A DAG orders only the parts that actually depend on each other and leaves independent parts concurrent.
• A natural fit for gossip: with gossip protocols propagating information asynchronously, each node can assemble the causal graph directly from the order in which it happens to receive updates, with no need to wait for everything to line up into a total order.

DAGs in the wild

Git: the commit DAG

Every commit holds a pointer to its parent commit's hash. Usually there is one parent, but a merge commit has two (or more), folding the separately-evolved histories of multiple branches into a single node. A "branch" is not an independent structure at all; it is just a mutable pointer (a ref) to a particular commit. What git log --graph renders is precisely this commit DAG made visible.

IPFS's Merkle DAG

As covered in Merkle Trees, IPFS splits content into chunks and binds them together with links that point to a child by its hash. It is precisely this "link by hash" mechanism that makes cycles structurally impossible: for node B to become a child of node A, B's hash must already be fixed at the moment A is constructed, so B can never later point back at A and close a cycle. Because identical content always hashes to the same value, treating the structure as a DAG that permits multiple parents (rather than a tree) also yields natural deduplication.

DAG-based ledgers: stretching a blockchain from "chain" to "mesh"

A single-chain blockchain, when multiple blocks are proposed concurrently, ultimately keeps just one of them via a fork-choice rule such as longest-chain and discards the rest. DAG-based ledgers invert that idea: instead of discarding concurrently proposed blocks or transactions, they fold all of them into the graph, and rely on a separate ordering rule to decide which portion counts as the canonical history.

• IOTA's Tangle: each new transaction, on issuance, verifies and approves two preceding transactions. By linking directly into the DAG per-transaction instead of batching into blocks, the design aimed for throughput that would increase as more participants joined.
• GHOSTDAG (Kaspa): a protocol proposed by Yonatan Sompolinsky and Aviv Zohar. It folds in every block concurrently mined under proof-of-work (a blockDAG) instead of discarding any of them, and supplies an ordering rule that recursively selects a "main chain" out of the relationships between blocks. The goal is to shorten block intervals and raise throughput while preserving a Nakamoto-style proof-of-work security model.
• Hashgraph: a scheme devised by Leemon Baird that builds the propagation history of events itself into a DAG via "gossip about gossip," then reconstructs voting virtually from that DAG structure alone (virtual voting) to reach aBFT (asynchronous Byzantine fault tolerant) consensus.

The main goal of all of these is higher throughput: letting work that would have queued up behind a single chain proceed in parallel instead. But that comes at the cost of more complex consensus. Analyzing the safety of the ordering rule that decides "which sub-DAG counts as the canonical history" is far more involved than a simple longest-chain rule, and it raises the bar for designing and verifying distributed consensus.

CRDTs and the causal DAG of operations

Collaborative editing systems that let multiple people edit simultaneously even while offline (CRDTs, Conflict-free Replicated Data Types) record each edit operation along with its causal dependency (which operation it came after) and treat the result as a DAG. Merging means taking the union of two replicas' operation DAGs and, for operations with no ancestor/descendant relationship between them (i.e., concurrent operations), resolving conflicts with a deterministic tie-breaking rule. Replica synchronization that efficiently reconciles this causal DAG is often implemented alongside the anti-entropy mechanism of gossip protocols. The repositories of AT Protocol (Bluesky), a decentralized social-networking protocol, also form a DAG-like history, in which each commit points to its parent commit's hash in a chain, combined with a Merkle Search Tree (a search tree whose nodes are also content-addressed by hash) that stores the actual records.

DAGs are not confined to distributed ledgers or collaborative editing, either. Build systems such as make and Bazel represent task dependencies as a DAG and use topological sorting to determine build order. Package managers such as npm and apt likewise resolve dependency relationships as a DAG, and reject an installation outright when they detect a cycle. DAGs live in plenty of everyday places.

Comparing chains, trees, and DAGs

Common misconceptions and caveats

• "A DAG is always better than a blockchain" is a misconception: DAGs can win on throughput and concurrency, but analyzing the safety of the consensus rule that decides which sub-DAG counts as the canonical history tends to be more complex than a simple single chain. In practice, some early DAG-based ledgers leaned on centralized mechanisms for their safety for a time.
• "A DAG means tamper-proof" is also a misconception: tamper-evidence does not come from the graph's shape itself but from hash-function collision resistance, signatures, and distributed consensus or finality mechanisms. A DAG is only a container for expressing causal relationships; it does not, by itself, guarantee any security property.
• "A topological ordering is uniquely determined" is another misconception: a given DAG can admit multiple valid topological orderings. Wherever "the one true history" is required, an additional rule, such as GHOSTDAG's ordering rule, is needed on top of the DAG.
• "A Merkle DAG and a DAG-based ledger are the same thing" is a further misconception: a Merkle DAG that binds data together with hashes, as in IPFS or Git (used as a data structure), and a DAG-based ledger like the Tangle or GHOSTDAG (used as a consensus architecture), draw on the same graph-theoretic concept but differ in purpose and design, and they should not be conflated.

Related pages

The DAG structure surfaces throughout the other technologies covered on this site. The idea of linking data together by hash is precisely the Merkle DAG and Merkle Search Tree of Merkle Trees, and the difficulty of deciding "which history counts as canonical" sits at the center of distributed consensus. The machinery for propagating and converging a causal DAG asynchronously connects directly to the anti-entropy of gossip protocols, and the idea of pointing at content uniquely by its hash carries over to the content addressing of DHTs. And the repository structure that combines a commit history with a Merkle Search Tree is covered concretely in AT Protocol.