Directed Acyclic Graph
A Directed Acyclic Graph (DAG) is a data structure used in some distributed ledgers where transactions are linked directly to one another rather than grouped into discrete, linear blocks. In a DAG, each new transaction must reference and validate one or more previous transactions, creating a web of interconnected nodes. Because there is no sequential block production, multiple transactions can be processed in parallel, significantly increasing scalability and allowing for feeless or low-fee microtransactions in highly active networks.
Explain Like I'm 12
Imagine a family tree where every person is a transaction. In a normal blockchain, you have a line of blocks like a chain. In a DAG, it is more like a web where every new person needs to mention their parents to join the family tree. This allows everyone to join the web at the same time, making the network much faster.
Why It Matters
DAGs represent a major departure from the traditional linear blockchain, offering a solution to network congestion and high transaction fees. They are particularly well-suited for IoT (Internet of Things) and micropayment use cases that require rapid, high-volume processing.
How It Works
A user initiates a transaction by pointing to multiple prior transactions to confirm their validity. This decentralized verification process removes the need for dedicated 'miners' or 'stakers' in the traditional sense, as the entire community performs validation as they use the network.
Real-World Example
IOTA and Nano are well-known projects that utilize DAG-based structures for transaction processing.
Advantages
- Massive parallel processing power
- Zero or near-zero fees
- High efficiency for micropayments
Limitations
- Increased difficulty in achieving global consensus
- Higher vulnerability to network attacks
- Complex wallet and node software
Common Misconceptions
- Many assume DAGs are not blockchains at all, despite their inclusion in distributed ledger technology. People often wrongly believe that all DAGs are inherently insecure compared to linear chains.
Knowledge Explorer
Explore This Concept in the Knowledge Graph
See how Directed Acyclic Graph connects to other concepts, books, research, and developer resources.
Related Terms
Ledger
A ledger is a systematic record of all financial or data transactions within a network. In the context of blockchain, it is a distributed ledger, meaning that every node participating in the network maintains an identical copy of the database. This ledger is updated in real-time through consensus, ensuring transparency and accountability. It provides a chronological, immutable record of every action taken within the system, replacing the need for traditional, centralized bookkeeping.
Avalanche Consensus
Avalanche consensus is a revolutionary, leaderless, and probabilistic consensus mechanism based on metastable sub-sampled voting. Instead of relying on a single leader or traditional proof-of-work, nodes repeatedly query a small, random subset of their peers to determine the network state. Through repeated rounds of sampling, the network quickly converges on a single outcome with high probability. This approach allows for massive throughput, extremely fast finality, and high decentralization, providing an alternative to classical BFT algorithms that often struggle with scalability.
BFT
BFT, or Byzantine Fault Tolerance, refers to the ability of a distributed computer network to function correctly and reach a consensus even when some nodes are malicious or fail to communicate properly. In a Byzantine environment, nodes may provide conflicting information, remain silent, or act maliciously to prevent the system from reaching a valid state. BFT systems employ specific algorithms to ensure that as long as the proportion of faulty nodes remains below a certain threshold—usually one-third—the network maintains integrity.
HotStuff
HotStuff is a BFT-based consensus protocol that simplifies the leader-based consensus process into a 'pipelined' structure. It addresses the complexity and performance bottlenecks found in traditional protocols like PBFT by making the leader rotation and communication pattern linear rather than quadratic. HotStuff is known for its responsiveness—meaning it performs as fast as the network latency allows—and its ability to handle leader changes without stalling the entire network.
Tendermint
Tendermint is a high-performance, open-source engine for building blockchains that provides an instant-finality BFT consensus. It packages both the networking and consensus layers into a single, modular framework. Developers can focus on building the application logic (the 'state machine') without needing to worry about the complexities of peer-to-peer communication or consensus algorithms. Tendermint uses a strict, leader-based round-robin rotation, ensuring that every block is final as soon as it is committed.