A directed acyclic graph (DAG) is a set of nodes joined by one-way links, with no path that leads back to its start. This page explains the structure, shows where software uses DAGs, and then covers DAG-based ledgers and how they compare with blockchains.
What a directed acyclic graph is
A graph is a set of nodes, also called vertices, joined by edges. In a directed graph, each edge has a direction and points from one node to another. A directed acyclic graph is a directed graph with no cycle, so if you start at any node and follow the edges in their direction, you never return to that node.
The rule against cycles gives DAGs three useful properties:
- Topological order. The nodes of a DAG can be placed in a line so that every edge points forward, and a directed graph has such an order only if it has no cycle. A DAG often has more than one valid order.
- Fast path calculations. Processing the nodes in topological order finds the longest path and the shortest path in linear time, while in a general graph finding the longest path is NP-hard.
- Clear reachability. Each DAG has exactly one smallest graph with the same reachability, called its transitive reduction. A build tool or scheduler can use it to drop dependency links that add nothing.
A small example
Take four tasks: A, B, C and D. Task B and task C each need A to finish first, and D needs both B and C. The edges run A→B, A→C, B→D and C→D, and no edge leads from D back to A, so the graph is acyclic. The orders A, B, C, D and A, C, B, D are both valid topological orders, so B and C can run in parallel.
Where directed acyclic graphs are used
| Field | What the nodes are | What an edge means |
|---|---|---|
| Build systems such as Make and Bazel | Source files and build targets | One target needs another before it can build. |
| Workflow schedulers such as Apache Airflow | Tasks in a data pipeline | A task runs only after the tasks it depends on. |
| Version control such as Git | Commits | A commit points to its parent commits. A merge commit has two parents. |
| Spreadsheets | Cells | A formula cell reads another cell, so the program recalculates in dependency order. |
| Bayesian networks | Random variables | One variable directly influences another. |
| Neural networks and compilers | Operations | The output of one operation is the input of the next. |
| Citation graphs | Papers or court decisions | A newer document cites an older one. |
| Distributed ledgers | Transactions, blocks or events | A new unit references earlier units. |
DAG blockchain vs chain of blocks
A classic blockchain is a DAG with one strict rule: each block points to exactly one parent, so history is a single line. When two miners produce blocks at the same time, the network keeps one block and discards the other, and the discarded work limits how many blocks the network can safely produce per second.
A DAG ledger drops the one-parent rule. A new unit can reference several earlier units, so units produced in parallel can all stay in the ledger, but the network then has to agree on one order for the whole graph. The hard question moves from "which chain wins" to "in what order do the graph's units count".
DAG crypto networks compared
Several networks use a DAG directly, and others use one inside their consensus engine.
| Network | Structure | How the order is agreed |
|---|---|---|
| Hedera | Hashgraph. Each event records which node told which other node about new transactions. | Nodes use the shared gossip history to run "virtual voting", an asynchronous Byzantine fault tolerant algorithm. A governing council runs the consensus nodes. The code is open source as Hiero, a project of LF Decentralized Trust. |
| IOTA | Started as the Tangle, where each transaction approved two earlier ones | Early versions depended on a central Coordinator run by the IOTA Foundation. IOTA has since been rebuilt. IOTA now uses delegated proof of stake. IOTA validators run the Starfish consensus protocol, and the network supports Move smart contracts. |
| Nano | Block-lattice. Each account has its own chain of blocks. | Representatives vote only when two blocks conflict. Nano calls this Open Representative Voting. |
| Kaspa | BlockDAG of proof-of-work blocks | The GHOSTDAG protocol orders parallel blocks, so the network can produce blocks much faster than Bitcoin's one block per ten minutes. |
| Sui and similar chains | Users see ordinary blocks, and a DAG is used inside consensus | DAG-based BFT protocols from the Narwhal and Bullshark family, such as Sui's Mysticeti, spread data first and order it second. |
The last row shows where DAG research has had the widest effect. In these protocols, each validator broadcasts batches of transactions in parallel, and the batches form a DAG of signed certificates that the protocol then orders. The result combines high throughput with Byzantine fault tolerance. Users of these chains do not see the DAG, only transactions that become final within seconds.
Claimed benefits of DAG ledgers
- Throughput. A DAG keeps parallel units instead of discarding them, but throughput also depends on networking, execution and storage, so a DAG alone does not produce very high numbers.
- Low or zero fees. Some DAG networks charge tiny fees or none, which suits micropayments. A fee-free network needs another defense against spam, and Nano, for example, requires a small proof of work for each transaction.
- Fast finality. DAG-based BFT protocols reach finality in seconds, but so do many BFT chains with a single line of blocks.
- Decentralization. Decentralization varies widely between DAG networks. Several early DAG networks depended on a coordinator or a small permissioned set of nodes for years, so check who runs consensus on a network today.
How DAG ledgers prevent double spending
Units arrive in parallel, so two conflicting transactions that spend the same funds can both appear in the graph, so every DAG ledger needs a rule that picks one of the two.
- Hashgraph orders all events by virtual voting, and the first transaction in consensus order wins.
- Nano's representatives vote only on the two conflicting blocks.
- Kaspa's GHOSTDAG ordering decides which of two conflicting blocks counts.
When a project says its DAG "prevents double spending", the ordering rule does that work, not the graph alone.
Where DAG ledgers fit
DAG networks were long promoted for IoT and machine-to-machine payments, because devices could send many tiny transfers. That use remains possible for data integrity and micropayments, but most IoT products still need no ledger at all, as the guide to blockchain IoT development explains.
Enterprises often choose Hedera for its council governance and fixed US-dollar fees. The guides to Hedera development and the hashgraph algorithm cover that network.
Building on a DAG-based network
For developers, the platform usually matters more than the data structure. Check these points before you build:
- Smart contracts. Hedera runs EVM contracts through its smart contract service. Sui and IOTA use Move. Nano has no general smart contracts.
- Finality and ordering. Find out how long a transaction takes to become final, and whether anyone can influence the order of transactions.
- Tooling. Look for SDKs, explorers, indexers, wallets and auditors who know the platform.
- Governance. Find out who controls protocol upgrades and who approves new validators.
- Ecosystem. If the product needs liquidity, stablecoins or existing users, check that the network has them.
When another design fits better
EVM chains and their rollups have the deepest DeFi liquidity and the widest tooling. The article on scaling with layer 2s explains that path. A tamper-evident log inside one company needs no distributed ledger, because a database with signed, hash-chained records does that job, as the guide to private blockchain development discusses.
Frequently asked questions
What does "acyclic" mean in a directed acyclic graph?
Acyclic means the graph has no cycle: following the edges in their direction from any node never leads back to that node.
Is a DAG a blockchain?
A blockchain is a special DAG in which each block has one parent. In everyday crypto use, "DAG ledger" means a design where a unit can reference several parents, so parallel activity stays in the ledger.
What is DAG crypto?
DAG crypto refers to cryptocurrencies whose ledger is a directed acyclic graph instead of a single chain of blocks. Hedera (HBAR), Nano (XNO) and Kaspa (KAS) are common examples.
Are DAG ledgers more scalable than blockchains?
A DAG removes one bottleneck, the single chain of blocks, but scalability also depends on networking, execution and the growth of stored state. Chains that use DAG-based consensus inside get similar benefits.
Is Hedera a blockchain?
Hedera reaches consensus with the hashgraph algorithm, a DAG of gossip events, instead of a chain of blocks. For developers it works like a fast public ledger with tokens, consensus messages and EVM smart contracts.