Directed Acyclic Graph (DAG)

What Is a Directed Acyclic Graph (DAG)?

A directed acyclic graph is a data structure from graph theory that consists of vertices (nodes) connected by edges (links) where every edge has a direction and no sequence of edges forms a closed loop. In mathematical terms, a DAG is a finite directed graph G = (V, E) such that for any vertex v, there is no path that starts and ends at v. This property guarantees that the graph can always be arranged in a topological order: a linear sequence where every edge points forward.

In cryptocurrency and distributed ledger technology, DAGs provide an alternative to the linear chain-of-blocks structure used by Bitcoin and other blockchains. Instead of grouping transactions into sequential blocks that reference exactly one predecessor, a DAG-based ledger allows each transaction to reference multiple previous transactions directly. This creates a web-like structure where many transactions can be added simultaneously, enabling parallel validation rather than waiting for the next block.

A traditional blockchain is technically a special case of a DAG: a linear graph where each block points to exactly one parent. DAG-based protocols generalize this by allowing multiple parents per transaction, trading the simplicity of linear ordering for potential throughput gains.

How It Works

In a DAG-based distributed ledger, the process of adding transactions differs fundamentally from blockchain systems:

1. A user creates a transaction and selects one or more previous unconfirmed transactions to reference (approve)
2. The user performs a small amount of computational work to validate the referenced transactions
3. The transaction is broadcast to the network and becomes part of the graph, available for future transactions to reference
4. As more transactions reference a given transaction (directly or indirectly), its confirmation confidence increases

This means every participant simultaneously acts as a user and a validator. There are no dedicated miners or validators competing to produce blocks. Transaction throughput scales with network activity: the more transactions being submitted, the faster each one gets confirmed.

Graph Structure and Topological Ordering

The directed edges in a DAG establish a partial ordering of transactions. Unlike a blockchain where every transaction has a clear position in a linear sequence, a DAG only guarantees that if transaction A references transaction B, then B came before A. Two transactions that do not reference each other (directly or indirectly) have no defined relative order.

This ambiguity in ordering is both the source of DAGs' performance advantages and their primary technical challenge. A topological sort can produce a valid linear ordering of all transactions, but multiple valid orderings may exist, and different nodes may disagree on which one is canonical.

# Blockchain: linear ordering
Block 1 → Block 2 → Block 3 → Block 4

# DAG: parallel ordering
       → Tx C → Tx E →
Tx A →              → Tx G
       → Tx B → Tx D →
              → Tx F →

In the DAG example above, transactions B through F can all exist concurrently, while in the blockchain model, every transaction must wait for its block's turn in the chain.

Consensus Without Blocks

DAG-based protocols must solve consensus differently from blockchains. Without discrete blocks and a longest-chain rule, DAGs use alternative mechanisms to determine which transactions are valid and in what order:

• Cumulative weight: each transaction accumulates weight as more subsequent transactions reference it, and higher-weight transactions are considered more confirmed
• Tip selection algorithms: rules for choosing which unconfirmed transactions (tips) a new transaction should reference, influencing convergence toward consensus
• Virtual voting: nodes infer how others would vote on transaction ordering based on the graph structure, without explicit voting rounds
• Representative voting: delegated nodes vote on conflicting transactions using stake-weighted authority

DAG-Based Cryptocurrencies

Several cryptocurrency projects have adopted DAG structures, each with distinct approaches to consensus, ordering, and security.

IOTA (The Tangle)

IOTA's Tangle is one of the earliest and most well-known DAG implementations. Each transaction in the Tangle must approve two previous transactions, creating a web of interconnected validations. The protocol uses a tip selection algorithm to determine which transactions a new transaction should reference, favoring transactions with higher cumulative weight.

IOTA was designed for Internet of Things (IoT) micropayments with zero transaction fees: since every user validates two transactions when submitting one, the network is self-sustaining without miner rewards. However, the original Tangle required a centralized Coordinator node to issue periodic milestone transactions that finalized the ledger state. IOTA 2.0 introduced a decentralized consensus protocol to remove this dependency, using a committee-based approach for transaction ordering and finality.

Hedera Hashgraph

Hedera uses a patented hashgraph consensus algorithm that achieves asynchronous Byzantine Fault Tolerance (aBFT) through two mechanisms: gossip-about-gossip and virtual voting.

In gossip-about-gossip, nodes share not only transactions but also the history of which nodes communicated with which, building a DAG of communication events. From this shared knowledge of the communication graph, every node can independently determine how every other node would vote on transaction ordering, without actually exchanging votes. This virtual voting mechanism enables consensus with minimal network overhead.

Hedera reports throughput capacity of 10,000 or more transactions per second for its consensus service, with finality typically achieved within 3 to 5 seconds. The network is governed by a council of up to 39 organizations, making it a permissioned network with known validator identities rather than a fully permissionless system.

Nano (Block-Lattice)

Nano uses a unique DAG variant called a block-lattice, where each account has its own blockchain (account-chain). A send transaction on the sender's chain and a corresponding receive transaction on the recipient's chain together form a complete transfer. This structure means transactions on different account-chains can be processed entirely in parallel.

For consensus on conflicting transactions (such as double-spend attempts), Nano uses Open Representative Voting (ORV). Account holders delegate their voting weight to representative nodes, which vote on conflicting transactions in real time. Nano achieves sub-second confirmation times and charges zero transaction fees, as the minimal computational cost of validating transactions replaces the need for fee-based incentives.

Fantom (Lachesis)

Fantom developed the Lachesis consensus protocol, which uses a DAG of event blocks to achieve asynchronous Byzantine Fault Tolerance. Validator nodes create event blocks that reference previous events from both themselves and other validators, forming a DAG. The protocol extracts a final ordering of transactions from this DAG without requiring synchronous communication rounds.

Fantom has since evolved its architecture with the Sonic chain, building on the DAG-based consensus foundations while optimizing for EVM compatibility and faster finality in the one-second range.

DAG vs. Blockchain: Comparison

Use Cases

IoT and Micropayments

DAGs are well-suited for high-frequency, low-value transactions typical of IoT environments. Sensors and devices that need to exchange small amounts of data or value benefit from zero-fee transactions and the ability to process many transfers simultaneously. IOTA was specifically designed for this use case: machine-to-machine payments where traditional blockchain fees would exceed the transaction value.

High-Throughput Applications

Applications requiring thousands of transactions per second, such as supply chain tracking, data marketplaces, and real-time settlement systems, can leverage DAG architectures. The parallel processing nature of DAGs avoids the bottleneck of sequential block production that limits traditional blockchain throughput.

Feeless Value Transfer

Networks like Nano demonstrate how DAGs enable feeless transfers. By eliminating miners and block rewards, and requiring each user to contribute minimal computational work when transacting, the network sustains itself without extracting fees. This is particularly relevant for everyday micropayments and regions where even small fees create barriers.

Finality in DAG Networks

How a DAG network achieves finality is one of its most important design decisions and a key distinction from blockchain systems.

In Bitcoin, finality is probabilistic: the more block confirmations a transaction has, the less likely it is to be reversed, but the probability never reaches exactly zero. BFT-based blockchains like those using proof of stake can offer deterministic finality, where a transaction is irreversible once a supermajority of validators attests to it.

DAG networks use varied approaches. In IOTA's Tangle, finality depends on cumulative weight: a transaction is considered final when enough subsequent transactions have directly or indirectly referenced it, making it statistically impractical to reverse. Hedera achieves deterministic finality through its virtual voting mechanism once the DAG structure proves that a supermajority of stake has observed the transaction. Nano's ORV provides fast deterministic finality through explicit representative votes on any conflicting transactions.

The key tradeoff: weight-based finality models (like the original Tangle) are weaker during periods of low network activity, since fewer transactions means slower weight accumulation and longer time to finality. Vote-based models (Hedera, Nano) avoid this issue but reintroduce reliance on identified validators or representatives.

Risks and Considerations

Security at Low Network Activity

DAG protocols that rely on transaction volume for security face a bootstrapping problem. When few transactions are being submitted, the graph grows slowly, weight accumulates slowly, and an attacker with moderate resources can potentially generate enough transactions to outweigh the honest graph. This is why IOTA originally required its Coordinator: a centralized fallback to prevent attacks during periods of low throughput. The challenge of achieving robust security at low activity levels remains an active area of research in DAG protocol design.

Transaction Ordering Challenges

Without the natural ordering provided by sequential blocks, determining a canonical order of transactions in a DAG is fundamentally harder. When two conflicting transactions exist in different branches of the graph with no direct path between them, the network must resolve the conflict through additional mechanisms. Different nodes may temporarily disagree on which transaction is valid, creating consistency windows that applications must account for.

Coordinator and Centralization Concerns

Several DAG projects have relied on coordinator nodes or governing councils to provide security guarantees that the pure DAG structure could not deliver alone. IOTA's original Coordinator, Hedera's governing council, and various committee-based finality mechanisms all represent tradeoffs between decentralization and practical security. While some projects have made progress toward removing these centralized components, the pattern suggests that pure DAG structures face inherent challenges in achieving trustless consensus without supplementary mechanisms.

Double-Spend Prevention

Preventing double-spend attacks in a DAG is more complex than in a blockchain. In a linear chain, conflicting transactions cannot both be included in the same branch: miners choose one and discard the other. In a DAG, two conflicting transactions can exist in separate branches of the graph simultaneously, and the network must converge on which one is valid through weight accumulation, voting, or other resolution mechanisms. The speed and reliability of this conflict resolution directly determines the practical security of the system.

Why It Matters

DAGs represent one of the most significant architectural alternatives to traditional blockchain design. They address real limitations: Bitcoin's base layer processes roughly 7 transactions per second, and even high-throughput blockchains face fundamental constraints from sequential block production. DAGs demonstrate that distributed consensus does not require a linear chain of blocks.

However, the tradeoffs are equally real. The security properties that make blockchains robust, particularly their clear transaction ordering and well-understood finality models, are harder to achieve in DAG structures. Most production DAG networks have converged toward hybrid designs that combine DAG-based transaction processing with committee or validator-based finality layers.

For builders evaluating distributed ledger architectures, the choice between blockchain and DAG depends on the specific requirements. High-throughput, low-fee applications with tolerance for different finality models may benefit from DAG designs. Applications requiring strong ordering guarantees, proven security models, and maximum decentralization may be better served by blockchain-based systems, potentially combined with Layer 2 scaling solutions like Spark that inherit the base layer's security properties while enabling higher throughput.

This glossary entry is for informational purposes only and does not constitute financial or investment advice. Always do your own research before using any protocol or technology.