Draft:BlockDAG

Submission declined on 6 June 2026 by MediaKyle (talk). This draft appears to contain text generated by a large language model (such as ChatGPT). You cannot use LLMs to generate article content. LLM-generated pages with certain obvious signs of being machine generated may be deleted without notice. Instead, only summarize in your own words a range of independent, reliable, published sources that discuss the subject. See the advice page on large language models for more information. If you would like to continue working on the submission, click on the "Edit" tab at the top of the window. If you have not resolved the issues listed above, your draft will be declined again and potentially deleted. If you need extra help, please ask us a question at the AfC Help Desk or get live help from experienced editors. Please do not remove reviewer comments or this notice until the submission is accepted. Where to get help If you need help editing or submitting your draft, please ask us a question at the AfC Help Desk or get live help from experienced editors. These venues are only for help with editing and the submission process, not to get reviews. If you need feedback on your draft, or if the review is taking a lot of time, you can try asking for help on the talk page of a relevant WikiProject. Some WikiProjects are more active than others so a speedy reply is not guaranteed. How to improve a draft Wikipedia:Contributing to Wikipedia – a basic overview on how to edit Wikipedia. Help:Wikitext – how to use the markup Help:Referencing for beginners – how to include references Wikipedia:Article development – how to develop your article Wikipedia:Writing better articles – how to improve your article Wikipedia:Verifiability – make sure your article includes reliable third-party sources 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. Add tags to your draft Editor resources Easy tools: Citation bot (help) | Advanced: Fix bare URLs Declined by MediaKyle 2 months ago. Last edited by MediaKyle 2 months ago. Reviewer: Inform author. Resubmit Please note that if the issues are not fixed, the draft will be declined again.

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.

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:

${\displaystyle r_{\text{orphan}}\approx 1-e^{-\lambda \cdot D}}$

where ${\displaystyle \lambda }$ is the block production rate and ${\displaystyle D}$ is the network propagation delay. In a blockDAG, this formula does not apply because parallel blocks are incorporated rather than discarded.^[1]

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]

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 the propagation delay and λ is the 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 anticons.^[1]

Finding the maximum k-cluster is NP-hard, making PHANTOM impractical for direct implementation.^[1]

GHOSTDAG (Greedy Heaviest Observed Sub-Tree DAG) is a polynomial-time greedy approximation of PHANTOM. The algorithm:^[1]

1. Each block selects the parent with the highest blue score (accumulated count of "blue" blocks in its past)
2. The algorithm greedily builds a "blue set" following the selected parent chain
3. All blocks are ordered: chain blocks by the selected parent chain, non-chain blocks interleaved at merge points
4. 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 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]

• 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)

• Blockchain
• Directed acyclic graph
• Consensus (computer science)
• Proof of work
• Nakamoto consensus

Category:Distributed computing Category:Directed acyclic graphs Category:Cryptocurrency Category:Data structures Category:Blockchain