Draft:BlockDAG
Graph-based distributed ledger data structure
From Wikipedia, the free encyclopedia
A blockDAG (block Directed Acyclic Graph) is a data structure used in distributed ledger technology where blocks can reference multiple predecessor blocks, forming a directed acyclic graph rather than a linear blockchain.[1] This structure allows multiple blocks to be created in parallel and incorporated into the ledger simultaneously, potentially increasing transaction throughput compared to single-chain architectures.
 | Review waiting, please be patient.
This may take 8 weeks or more, since drafts are reviewed in no specific order. There are 2,917 pending submissions waiting for review.
Where to get help
How to improve a draft
You can also browse Wikipedia:Featured articles and Wikipedia:Good articles to find examples of Wikipedia's best writing on topics similar to your proposed article. Improving your odds of a speedy review To improve your odds of a faster review, tag your draft with relevant WikiProject tags using the button below. This will let reviewers know a new draft has been submitted in their area of interest. For instance, if you wrote about a female astronomer, you would want to add the Biography, Astronomy, and Women scientists tags. Editor resources
Reviewer tools
|
Overview
In a traditional blockchain, blocks form a linear chain where each block references exactly one parent. When multiple blocks are produced simultaneously (a common occurrence at high block rates due to network propagation delay), only one block is accepted into the canonical chain; the others become orphan blocks — wasted computational work in proof-of-work systems.[2]
In a blockDAG, each block references all known unreferenced blocks (tips of the DAG) as parents, forming a directed acyclic graph. Parallel blocks are all included in the data structure. A consensus protocol then determines a total ordering over all blocks to resolve transaction conflicts.[1]
The orphan rate in a blockchain is approximately:
where is the block production rate and is the network propagation delay. In a blockDAG, this formula does not apply because parallel blocks are incorporated rather than discarded.[1]
History
The concept of using DAG-aware structures for cryptocurrency consensus was explored through several protocols by Yonatan Sompolinsky and collaborators:
- GHOST (2013/2015) — proposed by Sompolinsky and Zohar. The Greedy Heaviest-Observed Sub-Tree protocol modified Bitcoin's longest-chain rule by weighing the entire sub-tree of blocks rather than just the longest path, improving security under high block rates. While still a blockchain (not a DAG), GHOST laid the theoretical groundwork for DAG-based consensus. It influenced Ethereum's fork-choice rule (LMD-GHOST).[2]
- SPECTRE (2016) — proposed by Sompolinsky, Lewenberg, and Zohar. The first full blockDAG protocol, providing fast confirmation but only a partial ordering (pairwise ordering of transactions rather than a total order over all blocks).[3]
- PHANTOM (2018) — proposed by Sompolinsky, Wyborski, and Zohar. Provides a total ordering over all blocks by finding the maximum k-cluster in the DAG, but the optimization problem is NP-hard.[1]
- GHOSTDAG (2018/2021) — a greedy polynomial-time approximation of PHANTOM. Deployed in the Kaspa cryptocurrency.[1]
- DAG-KNIGHT (2022) — proposed by Sompolinsky and Sutton. A parameterless generalization that infers network conditions from the DAG topology.[4]
Other DAG-based distributed ledger systems include IOTA's Tangle, which uses a different DAG structure without discrete blocks.[5]
Consensus protocols
PHANTOM
PHANTOM introduces the concept of k-clusters to separate honest blocks from adversarial blocks in a DAG. A subset S of the DAG is a k-cluster if for every block B in S, the number of blocks in B's anticone (blocks with no ordering relationship to B) that are also in S is at most k.[1]
The parameter k represents the expected number of parallel blocks during one network propagation delay: k ≈ 2Dλ, where D is propagation delay and λ is block rate. Honest miners reference all known blocks as parents, so honest parallel blocks have small anticones (≤ k). Adversarial blocks, typically withheld and released later, have large anticones.[1]
Finding the maximum k-cluster is NP-hard, making PHANTOM impractical for direct implementation.[1]
GHOSTDAG
GHOSTDAG (Greedy Heaviest Observed Sub-Tree DAG) is a polynomial-time greedy approximation of PHANTOM. The algorithm:[1]
- Each block selects the parent with the highest blue score (accumulated count of "blue" blocks in its past)
- The algorithm greedily builds a "blue set" following the selected parent chain
- All blocks are ordered: chain blocks by the selected parent chain, non-chain blocks interleaved at merge points
- Transaction conflicts are resolved by ordering (first in order wins)
GHOSTDAG is deployed in the Kaspa cryptocurrency, running at 10 blocks per second.[6]
DAG-KNIGHT
DAG-KNIGHT eliminates the static k parameter by analyzing the DAG structure to infer current network conditions. It is described as the first permissionless proof-of-work protocol with no a priori bound on network latency.[4] The protocol was published through Harvard's Center for Research on Computation and Society.[7]
Comparison with blockchain
| Property | Blockchain | BlockDAG |
|---|---|---|
| Block references | Single parent | Multiple parents (all tips) |
| Parallel blocks | Orphaned (discarded) | Incorporated (ordered) |
| Orphan rate | Increases with block rate | Zero (by design) |
| Throughput scaling | Limited by orphan rate | Limited by node/network capacity |
| Ordering | Inherent (linear chain) | Requires consensus protocol |
Implementations
- Kaspa — proof-of-work blockDAG using GHOSTDAG consensus; 10 blocks per second[6]
- IOTA — uses a different DAG model (Tangle) without discrete blocks; currently transitioning from a coordinator-based model to proof-of-stake
- Conflux — proof-of-work tree-graph structure combining DAG and tree; also supports proof-of-stake finality
- Nano — uses a block-lattice DAG where each account has its own chain; secured by delegated proof-of-stake (Open Representative Voting)