Directed Acyclic Graph (DAG)

A Directed Acyclic Graph (DAG) is a data structure made of points, called vertices or nodes, joined by one-way links, called edges, arranged so that following the links can never lead back to where you started. "Directed" means each link points one way; "acyclic" means there are no loops. DAGs are used throughout computing to represent anything that has dependencies or an order of events, from software builds to version histories.

In crypto, the term usually refers to distributed ledger technology (DLT) designs that record transactions or blocks in a DAG rather than in a single chain. Examples include the original Tangle of IOTA (IOTA), the hashgraph behind Hedera and the blockDAG of Kaspa. A conventional blockchain is itself the simplest kind of DAG, a single line, so the difference is one of shape: DAG ledgers allow many branches to grow side by side and later be woven together.

Think of a family tree drawn with arrows from parents to children. You can follow the arrows down through the generations, but you can never follow them and arrive back at your own great-grandmother. Many people can share the same ancestors, and branches can merge when cousins marry, yet the arrows always run forward in time.

A DAG ledger works like that family tree. Each new entry points back to one or more earlier entries it builds on. Because many entries can be added at once on different branches, the ledger does not have to wait for one block at a time, but every entry still has a clear history behind it.

Because a DAG has no loops, its vertices can always be placed in at least one order, called a topological order, in which every link points forward. That is why DAGs suit scheduling: a build tool can compile files in topological order so that each one is built after the files it depends on.

A DAG with $n$ vertices can contain at most this many edges:

• $E_{\max}$ is the largest possible number of one-way links.
• $n$ is the number of vertices.

Worked example: with 5 vertices, $E_{\max} = \frac{5 \times 4}{2} = 10$. That limit is reached when every vertex links to every vertex that comes later in a fixed order; adding any further link would create a loop.

Familiar examples outside finance include the commit history of a version-control system such as Git, the chain of cell references in a spreadsheet, and task plans in which some jobs cannot start until others finish. Hash-linked structures are DAGs too: a Merkle tree links each parent hash to its children, and no hash can refer back to itself.

DAGs appear in crypto in several ways:

• Transaction graphs. In Bitcoin's Unspent Transaction Outputs (UTXOs) model, each transaction spends outputs of earlier ones, so the web of transactions forms a DAG even though blocks form a single chain.
• DAG-based ledgers. In IOTA's original Tangle, each new transaction approved two earlier ones instead of being packed into a block. Nano's block-lattice gives every account its own chain, and transfers link those chains together.
• BlockDAGs. Kaspa keeps proof-of-work blocks but lets blocks reference several parents, using the GHOSTDAG protocol to order blocks that would be discarded as stale blocks on a single chain.
• DAG-based consensus. Some newer Byzantine Fault Tolerance (BFT) protocols, such as the Mysticeti design used by Sui and by IOTA's 2025 "Rebased" network, have validators exchange messages arranged as a DAG and derive the final order of transactions from it.

The name also turns up in an unrelated sense: Ethereum's former proof-of-work algorithm, Ethash, used a large dataset that miners called "the DAG".

Supporters argue that DAG ledgers improve scaling because many participants can add entries in parallel, and that some designs can work without mining or fees, which suits microtransactions and machine-to-machine payments on the Internet of Things (IoT).

The trade-offs are significant. Without a single chain, the ledger still needs a way to agree on order and to resolve conflicting spends, the double-spend problem; designs that solve it often rely on extra mechanisms, such as the coordinator node IOTA ran for years, or on a validator committee. Security analysis is less mature than for Proof of Work (PoW) and Proof of Stake (PoS) chains, and low-traffic DAG networks can be easier to attack. Many projects therefore combine DAG structures with familiar consensus methods rather than replacing them.

• NIST Dictionary of Algorithms and Data Structures: directed acyclic graph
• IOTA documentation