In this article, we will explore a series of blockDAG protocols authored or coauthored by Yonatan Sompolinsky. This chronological investigation examines the foundational GHOST protocol, which played a significant role in developing Distributed Acyclic Graphs (DAGs) within the blockchain and crypto realm. Subsequently, we will delve into DAGKnight, the ultimate Proof-of-Work (PoW) protocol.

The objective of the article is to provide a concise and informative overview, serving as a starting point for understanding the world of blockDAG. Join us on this journey as we uncover the contributions of Yonatan Sompolinsky and his academic peers, including Michael Sutton, Shai Wyborski, and Aviv Zohar, who have significantly influenced the blockDAG landscape and were involved in solving blockchain limitations.

During the writing, I tried to be in contact with Kaspa core developers, who provided me with much useful feedback. However, this article is the best version of my interpretation of it.

Secure High-Rate Transaction Processing in Bitcoin

Yonatan Sompolinsky, Aviv Zohar — 2013

The Secure High-Rate Transaction Processing in Bitcoin paper aimed to analyze the longest chain rule of Bitcoin in scenarios with high latency or throughput.

The final two sections of the paper introduced the GHOST protocol, which proposes an alternative approach to Bitcoin's longest chain rule. This protocol utilizes the proof of work present in off-chain blocks by navigating the tree structure resulting from forks at high speed. By selecting the main chain differently, the GHOST protocol aims to overcome limitations caused by network latency.

GHOST

The appendix of the above-mentioned SHTPB paper introduced new analysis techniques and ideas for Bitcoin and the Nakamoto consensus. GHOST was used in Ethereum for a few days right after its launch, but the non-ideal implementation of GHOST forced Ethereum founders to switch to the longest chain rule after a while.

While GHOST was later found to be insecure against liveness attacks, the long-term value of the GHOST paper remains unquestioned.

(This doesn't mean that Ethereum has a liveness problem.)

• Liveness attack: Liveness attack: If you're trying to be inclusive about transactions and not just about work, and a conflict appears before the transaction is confirmed, then it is theoretically possible (though rather impractical) to delay the confirmation of this transaction for an arbitrarily long period of time.

• GHOST rule can securely allow you to include the work put into cousin blocks without having liveness issues, but you'd still only use TXns on the GHOST CHAIN and discard TXns from cousin blocks.

Motivation:

Bitcoin is a decentralized cryptocurrency that has gained significant traction. A critical factor for its success is scalability, particularly its ability to handle a large volume of transactions.

In the Secure High-Rate Transaction Processing in Bitcoin study, authors examine the impact of increased transaction throughput on Bitcoin's security against double-spend attacks.

Their findings reveal that higher throughput can enable weaker attackers to reverse payments long after they were accepted.

To address this concern, the authors propose the GHOST rule, a modification to Bitcoin's blockchain construction and re-organization process.

Inclusive Blockchain Protocols

Yoad Lewenberg, Yonatan Sompolinsky, Aviv Zohar 2015

The Inclusive Blockchain Protocols paper first proposed the directed acyclic graph structure for blocks — the blockDAG -. Still, it focused on increasing throughput while not decreasing security and on linearizing the block rewards across miners.

A modified version of the Inclusive Blockchain Protocols was used in Ethereum and may still be used today.

Motivation:

Distributed cryptographic protocols like Bitcoin and Ethereum rely on the blockchain data structure to synchronize events across their networks. However, the current blockchain mechanics and block propagation have limitations that impact performance and transaction throughput. To address these limitations, the authors proposed an alternative structure called the blockDAG, which allows for higher transaction rates and more forgiving transaction acceptance rules.

Paper quotation:

• "We propose to restructure the blockchain into a directed acyclic graph (DAG) structure that allows transactions from all blocks to be included in the log. We achieve this using an "inclusive" rule, which selects a main chain from within the DAG and then selectively incorporates contents of off-chain blocks into the log, provided they do not conflict with previously included content. An important aspect of the Inclusive protocol is that it awards fees of accepted transactions to the creator of the block that contains them — even if the block itself is not part of the main chain."

The blockDAG incorporates a directed acyclic graph of blocks and can tolerate larger blocks with longer propagation times. Additionally, the proposed system reduces the advantage of highly connected miners and addresses security concerns related to potential malicious attacks.

This paper also describes that these attacks can be easily countered.

SPECTRE

Yonatan Sompolinsky, Yoad Lewenberg, Aviv Zohar — 2016

(parameterless; nonlinear ordering(pairwise), responsive to actual network latency)

SPECTRE was designed as a partial synchronous network model and was the first parameterless 49% resilient proof-of-work consensus protocol, making it robust against network congestion and bandwidth constraints.

However, it does not provide linear ordering, making it unsuitable for applications requiring full linearization, such as smart contracts (SC). The challenge of the SPECTRE and PHANTOM was to recover BlockDAG consistency by ordering the blocks so that attackers' blocks and conflicts are excluded.

This paper also mentions the term anticone you can read about in the papers that follow. Anticones are blocks that are neither a block's past nor future; this is a definition inside the DAG, regardless of the protocol. To recognize an honest block from a dishonest one, protocol categorizes subdags on connected and well-connected graphs. The anticone is presented in both categories, but the honest subdag is that well-connected dag mined by honest miners, the anticone of which is not bigger than the set parameter k. The k parameter is the maximum anticone size of a block in an honest network, thus acting as a parameter of tolerance.

The reason why the core team opted for GHOSTDAG as a consensus for Kaspa instead of SPECTRE was the SPECTRE's lack of linear ordering and the possibility of blocks switching positions long after confirmation (although this never invalidates transactions). While this condition is acceptable for a distributed ledger, it becomes problematic for SC.

Pros:

• Good for regular payments unless someone made a double spend

• High block creation rates

• Transactions are confirmed within seconds

• Limited primarily by network round-trip time

• No reliance on message delivery time as a protocol parameter

• Adaptation to the current network delay

• Enables efficient convergence

Cons:

• Not suitable for use with SC. In SC, you don't want to make the entire contract stuck in a pending state.

• Nonlinear ordering; pairwise.

• Not guaranteed fast confirmation times in the event of active balancing, "Liveness", attack

SPECTRE can't tell the full linear ordering of several transactions where transaction `a' comes before `b`, `b` before `c`, and `c` before `h`. SPECTRE, however, can tell you which one came first between each pair. Problematic can be a cycle, such as a <- b <- c <- a.

These cycles can occur if we let the audience prove a ranking of ordering between these transactions, and then you check the majority of votes and obtain cycles as a result.

SPECTRE uses pair-wise ordering by taking each pair of conflicting transactions, such as [x,y], where x comes before y, and we delete the y.

Motivation:

Bitcoin and other permissionless consensus protocols rely on the Nakamoto Consensus to achieve agreement in decentralized and anonymous settings. However, ensuring security becomes more challenging as transaction throughput and confirmation times increase.

In this context, the authors introduced SPECTRE, a new consensus protocol designed for cryptocurrencies that maintains security even under high throughput and fast confirmation times.

A key feature of SPECTRE is that it satisfies weaker properties than classic consensus protocols.

While traditional consensus requires agreement on the order of all transactions, SPECTRE focuses on ensuring order among transactions performed by honest users. It recognizes that dishonest users can only create conflicting payments published concurrently, allowing for delayed acceptance without compromising system usability.

This framework formalizes these relaxed requirements for a distributed ledger in a cryptocurrency, and the authors provide formal proof demonstrating that SPECTRE satisfies these requirements.

Yonatan once described this protocol to Shai W. as: " his most beautiful creation".

PHANTOM

Yonatan Sompolinsky, Shai Wyborski, Aviv Zohar — 2018

(paradigm, linear ordering)

PHANTOM is a parameterized generalization of the Nakamoto Consensus.

Please note that the PHANTOM paradigm (illustration, not a protocol) and PHANTOM-GHOSTDAG, or just GHOSTDAG (PHANTOM implementation), were both covered in the same paper.

The PHANTOM can be categorized as a family of consensus protocols, with GHOSTDAG and DAGKNIGHT being two specific instantiations of this family.

PHANTOM serves as a conceptual framework, representing an idealized version that cannot exist in reality but serves as a theoretical precursor to GHOSTDAG.

GHOSTDAG, on the other hand, represents the practical implementation or a practical approximation of the theoretical foundation laid by PHANTOM.

The PHANTOM paper presents a mechanism to prevent attackers from exploiting the work generated by honest nodes for their own advantage. To achieve this, it proposes a method to distinguish between blocks created by attackers and those created by honest miners, organized in a k-cluster composed of well-connected blocks. In other words, to recognize a cluster of honest blocks and discard or penalize (being put later in the DAG order) the rest.

PHANTOM searches for the largest k-cluster, orders its blocks using a topological ordering and iterates over blocks in the prescribed order while accepting transactions consistent with history.
In the weight of the chain, PHANTOM counts the weight of orphans that are well connected and increases the weight of the honest chain by it.

The suitable parameter k is important for those who would wish to implement a protocol from the PHANTOM family. To do so, specify your node requirements first, then decide about the desired throughput, and lastly, choose the proper parameter k.

The PHANTOM rule is a rule that differentiates between honest and attacker's DAG based on the anticone (blocks that are neither block's past nor its future) factor. We can describe the PHANTOM rule shortly as "find the biggest sub-DAG where no block has an anticone greater than k."

Notice that this is a generalization of the Bitcoin longest chain rule, where Bitcoin can be described as PHANTOM with k=0, where k > 2Dλ.

• D = network delay

• λ = the block creation rate

• k = the maximum anticone size of a block in an honest network

• A block's anticone can consist of blocks unknown to the block's miner at its creation and of blocks that were created before the block's miner finished its propagation.

• The PHANTOM optimization rule is to return max k-connected clusters.

• An honest set of blocks is a set of blocks mined by honest nodes.

• The largest k-cluster is a set that, with high probability, includes all properly and honestly mined blocks.

PHANTOM, in theory, is easy to implement efficiently, provides protocol-unlimited throughput, and remains limited only by the network. However, when conflicts are visible, it's possible to expect increased waiting times.

PHANTOM Algorithm versions:

NP-hard

The mathematically pure one

Step 1) Search for the largest k-cluster; the cluster is honest.

Greedy 

This is a more implementable one: selecting the chain with the largest weight and counting all k-uncles. This version is known as GHOSTDAG.

Step 1) Search for a chain with the largest weight (most mining hash power work put in) of uncles of degree <=k; Then the chain + uncles are honest.

Common part for NP-hard and greedy versions:

Step 2) Order its blocks by using some topological ordering.

Step 3) Iterate over blocks in the prescribed order and accept transactions consistent with history.

PHANTOM issues:

1. Being inefficient if applied in NP-complete DAG, where is the problem with finding a maximum k-cluster. [1]

• If a Directed Acyclic Graph (DAG) is NP-complete, it means that determining certain properties or solving certain problems related to the graph's structure or content is computationally challenging. NP-completeness is a complexity class in computational theory that represents problems for which no known efficient algorithm exists to find a solution.

• In the context of a DAG being NP-complete, it implies that tasks such as finding a specific path, calculating certain metrics, or solving optimization problems on the graph may require exponential time or resources to complete. This can make such tasks computationally infeasible for large and complex DAGs, and they may fall into the category of problems considered difficult to solve efficiently.

2.          Being not incremental — Every time the DAG updates, the entire computation must be restarted. In particular, it requires storing the entire DAG structure. [2]

GHOSTDAG (GD)

Yonatan Sompolinsky, Shai Wyborski, Aviv Zohar — 2020

• GD achieves Nakamoto consensus security independent of block rates (same as SPECTRE).

• GD has a rapidly converging linear ordering (the ability that SPECTRE lacks).

GD, published as a part of the PHANTOM-GHOSTDAG (PHANTOM) paper, is Kaspa's current consensus protocol, which is a practical and efficient (greedy) variant of PHANTOM and its realization and application to a PoW project.

GD greediness solves both issues [1],[2] that PHANTOM has by incrementally maintaining an approximate k-cluster. Each block is labeled with a number representing its blue score, indicating the number of past blocks in the k-cluster. When a new block is created, it inherits most of the k-cluster from its selected parent, avoiding recalculating the entire k-cluster.
The remaining portion is chosen from the anticone of the selected parent.

• Like PHANTOM, the GD protocol selects a k-cluster, which induces block coloring as Blues (blocks in the selected cluster/on the chain)and Reds (blocks outside the cluster/off the chain).

• The greedy algorithm finds the Blue set with the best tip and then adds the data from outside the set. The combination of Blues and Reds forms a chain, with the block from the selected tip coming last. The second step is to find a proper ordering of DAG within the secure Blue set.

• GD utilizes user-defined and mined data to create a topological order in the chain.

This inclusive protocol also ensures no blocks are orphans thanks to pointing to all forks instead of following the longest chain. The inclusiveness of GD assures that transactions aren't lost after a reorg attack (either organic or adversarial). That's the essence of why Kaspa provides instant confirmations.

GHOSTDAG, the first PoW protocol to enable reducing block rates on a non-sharded network, also allows for unprecedented confirmation times. However, a limitation is that it doesn't respond to network latency. An upper bound on network latency must be set (which we can assume holds 95% of the time), and the rest of the network properties, particularly confirmation times, are derived from this bound. This implies that performance doesn't improve as latency improves, and, worse, security is compromised if network latency deteriorates. This is true, however, for all existing PoW algorithms, with the only exception being SPECTRE.

Drawbacks of having a parametrized consensus, such as GD:

• If you underestimate the delay, then the system is not secure.

• If you overestimate the delay, the system is slower than it can be.

GD con vs. all other Yonatan protocols (and DG, that is Michael's :)) is that GD has a prior delay bound, which means that confirmation times are a function of the bound, not the latency.

The huge advantage of GHOSTDAG over all other PoW algorithms is that it removes the security constraints on throughput.

• SPECTRE and GHOSTDAG possess unique properties not found in other protocols.

  The key to creating an ultimate protocol thus lies within these two and will create the foundation for DAGKNIGHT.

• Shai Wyborski proved GD security.

The initial protocol setup when launching Kaspa with GD was:

• delay = 5 seconds

• k = 18

Kaspa and their BlockDAG inclusive ordering protocol, GHOSTDAG, solves the blockchain trilemma issues while delivering high block creation and transaction verification speed while not sacrificing security and decentralization — this all while taking TPS/Confirmation times deadly seriously.

GD perks not mentioned in the paper:

• A novel approach to difficulty adjustment.

• A novel approach to coloring (not ordering) and security that arises from it.

• A fancy pruning mechanism.

• An ability to provide infrastructure for layer 2 applications.

• Kaspa Proof-of-Work (PoW) function is specifically designed to be compatible with Optical ASIC chips. This unique characteristic enables PoW mining with significantly reduced electricity consumption.

DAGKNIGHT (DK)

Michael Sutton, Yonatan Sompolinsky — 2022

(parameterless, linear ordering)

DAGKNIGHT (DK)DK Is the first protocol published since the Kaspa fair launch. It is the evolution of the PHANTOM paradigm, drawing inspiration from both PHANTOM and SPECTRE.

The development has matured over the years, making it the first parameterless 49% resilient proof-of-work consensus protocol with no speed limitations beyond hardware.

One of the ideas DK draws upon from SPECTRE, to name one, is the cascade voting procedure.

Where GHOSTDAG still assumes an explicit upper bound on the network latency, DAGKNIGHT doesn't. Both these protocols allow similar BPS, but DK utilizes those BPS with better security and confirmation times.

GHOSTDAG exhibits linear ordering, while SPECTRE is parameterless. Only DAGKNIGHT combines both properties, making it a highly advanced solution.

• DK's parameterless-ness originates from the "min-max optimization" definition in the DK paper.

DK Perks:

• It achieves Nakamoto consensus security independent of block rates (same as GHOSTDAG and SPECTRE).

• It has a rapidly converging linear ordering (same as GHOSTDAG).

• Suitable for SC (same as GHOSTDAG).

• DAGKnight is responsive to actual network latency (same as SPECTRE):
  Confirmation times can approach the network limits without risk, as any degradation in network conditions will result in DK automatically increasing its confirmation times to maintain stability. This means that DK scales itself as network latency is improved.

The evolution of DAGKNIGHT (DK) from GHOSTDAG (GD) involved a collaboration between Yonatan and Shai to establish GD's security through conclusive mathematical proof.

Subsequently, Michael Sutton extended and refined this proof to apply to DK.

The challenge arose when Michael and Yonatan realized that hypothetical attackers could exploit a worst-case apriori assumption of higher latency to gain an advantage when observing a low-latency DAG. To address this, they aimed to create a coloring method that favored well-connected DAGs representing lower actual latency, leading to the concept of "parameterless-ness."

For three years, Yonatan guided Michael as they encountered numerous challenges, each requiring significant enhancements to the initial idea. This iterative process culminated in the unique DK solution, detailed in the DK paper, drawing on Yonatan's extensive DAG analysis experience gained from analyzing SPECTRE.

Table of comparison

• Weak liveness: If a conflict appears before the transaction is confirmed, then it is theoretically possible (though rather impractical) to delay the confirmation of this transaction for an arbitrarily long period of time.

Conclusion

While we still need to wait for DK to be a new Kaspa consensus and thus see this PoW diamon in real action, we can appreciate GD as the fastest blockchain trilemma-solving PoW as of today, capable of achieving a robust amount of BPS without sacrificing decentralization or security, accompanied by instant transaction confirmations determined by network latency — not by the protocol. Even though the term robust amount is not anything astonishing by itself, what makes it astonishing is the set of confluences patched by a batch of novelty features and the fact that Kaspa with GD increases BPS while maintaining the non-decreasing confirmation times.

The end

Thanks to:

1. Michale Sutton for the initial consultations

2. Shai Deshe Wyborski for the table restructuring

3. Yonatan Sompolinsky for an initial review and a lot of useful hints regarding the protocol organization and timeline

4. Jirka Herrmann for a style and grammar review