26,848 reads

The Power of Kaspa BlockDAGs: Go Beyond the Blockchain

by Mickey MalerNovember 29th, 2022

Too Long; Didn't Read

This article is about something that is unreachable on Proof-of-Stake blockchains, and starts by revisiting the early days of Bitcoin, followed by the invention of Ethereum. Afterwards, it recounts the challenges that today’s blockchain networks face and how they can be overcome with the current Kaspa GHOSTDAG PoW consensus, invented as a generalization and extension of the original Nakamoto Consensus used in Bitcoin.

People Mentioned

Companies Mentioned

Coins Mentioned

featured image - The Power of Kaspa BlockDAGs: Go Beyond the Blockchain

Available translations provided by the Kaspa community:

The following article will introduce you to BlockDAG - a technology that can go hand-in-hand with blockchain but also acts as a new meta-technology that challenges it. By storing blocks as graphs while being protected by the power of Proof-of-Work, it seeks to overcome the shortcomings that stem from the linear nature of the traditional blockchain. Project Kaspa and their BlockDAG solve the blockchain trilemma issues when delivering high block creation and transaction verification speed while not sacrificing security and decentralization.

Welcome to Kaspa.

Preface

This article has been written out of pure excitement. It was more than a play of coincidences that the results of the 8 years-worth of work that this article will be about, were announced and presented on the 31st of October 2022, on the 14th anniversary of the Bitcoin whitepaper written by Satoshi Nakamoto.

Now, to the source of my excitement.

Yonatan Sompolinsky and Michael Sutton of Kaspa core contributors published a second PoW consensus protocol called DAGKNIGHT (DK), which challenges the original Nakamoto consensus and solves the blockchain trilemma.

DK is not currently used as a consensus, but it is a protocol that, in theory, surpasses anything we know as limits in blockchain, allowing the creation of many blocks per second (BPS) while remaining secure and decentralized and allowing instant transaction confirmations.
The use of such a protocol is a dream of every PoW enthusiast.

DK’s older brother, GHOSTDAG, authored by Yonatan Sompolinsky, Shai Wyborski, and Aviv Zohar, posted online as early as 2016 and published at the Advances in Financial Technologies (AFT)’ 21 conference in 2021, is the protocol that will play the central role in this article. Even if it lacks one feature in comparison to its recently published successor, GHOSTDAG is the fastest blockchain trilemma-solving PoW as of today, capable of achieving a robust amount of BPS without sacrificing decentralization, 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, however, is the set of confluences and the fact that Kaspa increases BPS while maintaining the non-decreasing confirmation times.

GHOSTDAG, a protocol from the PHANTOM family, assumes an explicit upper bound on the network latency, whereas DAGKNIGHT doesn't. Both allow similar BPS, but DK utilizes those BPS with better security and better confirmation times. You will read about this comparison in more detail and improved technical accuracy in the later chapter of this article.

Videos to watch:

"PHANTOM GHOSTDAG: A Scalable Generalization of Nakamoto Consensus" by Shai Wyborski at AFT'21.

SPECTRE - BPASE '18, Yonatan Sompolinsky

It all started with inspiration from the protocol that started the blockchain era, followed by the desire to solve the most crucial blockchain issues as time passed. Now let's get back to Nakamoto.

NOTE: If this is the first time you are reading about Proof-of-Work (PoW) and want to know more, please read the following article, in which I explain all you need to know to understand its context in this article:

Learn the blockchain basics - Part 2: "Mining", "Miners", and the Proof of Work Algorithm

Where it all began

In 2008, Satoshi Nakamoto and their Nakamoto Consensus brought to life Bitcoin.
The proof of work (PoW)-based cryptocurrency, now secured by the efforts of Bitcoin miners, was developed to provide a peer-to-peer transaction system. As a part of the implementation, Nakamoto also devised the first blockchain database. It was fascinating enough to inspire Vitalik Buterin to design another blockchain, Ethereum, which challenges Bitcoin and takes different trade-offs. In particular, it trades off simplicity for expressibility since expressibility is the area where Bitcoin is lacking.

Ethereum, with its eight thousand nodes spread worldwide, allows people to create decentralized applications and provides space for technological booms such as:

Decentralized finance (DeFi), with the current value locked in ETH DeFi products equal to $50.99B,
Non-fungible tokens (NFTs), where anything you can own can be represented, traded, and put to use
The fundamentals of metaverse ecosystems

The price of success

Heavy is the head that wears the crown.

The popularity and global adoption of blockchains have shown that every system has its limits and brought challenges that must be overcome if the system wants to remain usable for all. Ethereum became too expensive for normal people to operate daily due to network transaction congestion, in which you need to bribe miners to prioritize your transactions. Bitcoin is painfully slow by design, no matter how secure it is and how much computation power the Bitcoin network has. After all, the same applies to all PoWs in general - throughputs are decoupled from hashrates.

This inevitably led to efforts to replace these systems. For example, we have seen the rise and fall of Bitcoin Cash, which was faster thanks to bigger block size, but sacrificed security in favor of speed. As a consequence, miners turned away from it and returned to the original fork of Bitcoin. BitcoinCash argued that Bitcoin takes too much margin of error, choosing a very careful approach, and stated that increasing throughput by reducing block delays, or increasing block sizes, would not have a meaningful adverse effect, meaning larger blocks remain safe.

The problem is that when you try to upscale the throughput of the network (by either increasing the block rate or the block size), you unavoidably increase the orphan rate, thereby decreasing the security of the network.

In theory, increasing block size to obtain more speed results in increasing hardware requirements, which then causes a lesser cardinality of nodes that can reach or maintain the Full-node status, thus decreasing decentralization and security. However, even with larger blocks, the transaction volume is very low, so even validating ten times as many transactions is not a real issue. The problem is that more transactions => longer validation time => higher latency (since nodes only retransmit blocks after they were validated), so increasing block size has a similar effect to decreasing block delay. And that's the problem that needs to be solved.

The security of any blockchain relies on the fact that the delay between blocks is larger by orders of magnitude than the time it takes the entire network to learn of a new block. Parallel blocks are orphaned, whereby they decrease the growth rate of the honest chain. Overcoming this throughput/security trade-off is the main motivation behind the Kaspa GHOSTDAG protocol, which allows for parallel blocks, and orders blocks in a DAG, not a chain.

The same applies to other GHOSTDAG-related protocols mentioned in this article.

Things have been tempestuous around Ethereum as well. We have seen many purported "Ethereum killers" that failed in delivering what Ethereum was capable of without sacrificing decentralization, security, and in some cases, even functionality or the capability to handle a similar amount of users. Although some of these projects delivered a great product, big corporations still tend to build on Ethereum if they are not financially motivated to do otherwise, and Bitcoin is still the main cryptocurrency and declaration of a store of value.

As a result, many now understand that it is vital to develop a revolutionary solution that can act as a meta technology and challenge well-established blockchain projects. At the same time, such a solution should keep the doors open to the possibility of working side-by-side with blockchains like Bitcoin or Ethereum.

In addition, while keeping the blockchain trilemma trade-offs in mind, Bitcoin and Ethereum implemented upgrades to keep pace with growing demand.

Scalability solutions from Layer 1:

Bitcoin SegWit

To solve the malleability issue for all future transactions (to avoid malleability attacks)

To increase block size

Ethereum - Consensus protocol changes from PoW to PoS

Changing the core rules that nodes must follow to be admitted into the network and changing the network's mechanisms to find consensus among the nodes.

A major overlooked detail regarding the change to PoS is that, in general, PoSs are centralized because the coins are not well spread. Ethereum interestingly counterbalanced this by using a decade of PoW to spread their coin before switching. However, it is still unclear if that suffices, and we do see some disconcerting phenomena, as detailed in the following article: More Than Half of Ethereum Network is Excluding U.S.-Sanctioned Wallets.

Scalability solutions from Layer 2:

Application of a rollup or state channels and state chains

BTC

Lightning network

Ethereum

Sharding for Ethereum

The use of:
Polygon - Decentralized Ethereum scaling platform that enables developers to build scalable user-friendly dApps
Arbitrum - The Ethereum rollup scaling solution
etc.

If this is the first time you are reading about blockchain scalability layers and want to know more, please read the following article, in which I try to illustrate these terms on simplified examples.

Layers - The Bedrock of Blockchain | HackerNoon

Nevertheless, it is more important than ever to challenge what used to be revolutionary, make a generalization of it, and push the limits even further.

Talking about the limits of today's blockchains, there is much to tackle:

Scalability issues during traffic peaks
Not enough transaction throughput (measured as the number of transactions per second - TPS) where we do not sacrifice verification for speed
The insufficient speed of transaction verifications that proves that our transaction was not front-run by bots (caused by slow blockchain confirmation)
Rising hardware requirements of full nodes

Orphan blocks - the obstacle to optimization in blockchain systems

Now, let's get to the explanation of why the previous limitations exist in traditional blockchains.

Every once in a while, two honest miners will create blocks at approximately the same time, and these blocks will compete with one another until one of them is discarded and not accepted by the blockchain. Such discarded blocks are often called orphan blocks, and even the most conservative approximations claim that at least one in every 150 Bitcoin blocks is orphaned. Most of the time, this is because there need to be more blocks generated from that block for the network to recognize it as the longest fork.

Many blockchain assumptions force miners to choose one block to point to instead of pointing to them all, and this causes the creation of orphan blocks. The hashrate waste generated by producing orphan blocks leads to the main point of why today's blockchains need inclusive protocols such as GHOSTDAG of Kaspa, which ensures no blocks are orphans to begin with.

Kaspa solves the problems recounted in the previous section by allowing parallel blocks to co-exist and resolving conflicts by a provably secure ordering rule. To do this, Kaspa uses the PoW model enhanced by the results of successful challenges of the Nakamoto consensus.

As opposed to how the linear structure of blockchain works, Kaspa stores transactions in blocks that don't create a chain but form a directed acyclic graph (DAG) of blocks, which references multiple predecessors instead of a single parent, thus solving the high orphan blocks problem. The same consensus protocol also provides the answer to the long-unanswered question:

“Is your consensus protocol, given with a certain Target and fixed block creation rate, secure enough for any latency?”

Breaking new ground - academia & DAGlabs

Kaspa is an open-community-driven project, which was started by the ex-members of the directed acyclic graph (DAG) PoW protocol company called DAGlabs.

DAGlabs was formed as a university initiative. With the help of Guy Corem and later Sizhao Yang, Yonatan raised roughly 8 million dollars from a crypto VC called Polychain Capital, which became the initial DAGlabs funding. Needless to say, this was hardly a significant amount in terms of the crypto market in 2018.

Using this starting capital, they purchased mining devices and implemented PHANTOM family protocols into a working platform. The rest of the raised money went into research and development.

DAGlabs developed code based on a fork of the BTCD full-node codebase. The primary objective was to keep the design of the system as close to Bitcoin’s architecture and assumptions as possible: PoW, blocks, UTXO, transactions fees, etc. The codebase underwent significant refactoring by the core devs, who then adapted it to a blockDAG governed by the GHOSTDAG protocol. Kaspa's birth was around the corner.

NOTE: The project's initial business plan was to develop OPoW-like ASICs and sell and distribute their hashrate.

From a university project to an open-source community-driven excellence

Kaspa launched with zero allocations or pre-mine, with the key vision of being a decentralized, pure, and open initiative. The original Kaspa contributors are composed of ex-DAGLabs developers and researchers who actively contribute to the advancement and maintenance of Kaspa and its codebase, and are just a group of people whom the open Kaspa community holds in high regard.

The seeds of DAGLabs members and future Kaspa core contributors were sown long before the projects themselves emerged. The GHOST protocol from 2013 - an invention of Dr. Yonatan Sompolinsky (who is now part of the Kaspa core contributors) and professor Aviv Zohar - was mentioned by Vitalik Buterin in the original Ethereum WhitePaper. Buterin leveraged the research of Dr. Sompolinsky and Professor Aviv Zohar, and used it to establish certain security measures for the Ethereum network.

Even though Ethereum did not implement GHOST per se, they did end up implementing a variant of Inclusive Blockchain Protocols, also published in Financial Crypto that year (authored by Yoad Lewenberg, Yonatan Sompolinsky, and Aviv Zohar). This paper first proposed the directed acyclic graph structure for blocks, the blockDAG, but its focus was on increasing throughput while not decreasing security, and linearizing the block rewards across miners.

BlockDAGs are the technological heart of the Kaspa project. They are a different structure than blockchain, and as we already know, the developer team that stood behind the application of DAGs in Proof-of-Work consensuses was initially DAGlabs.

Dr. Yonatan Sompolinsky participated in the creation of the following protocols, either in cooperation with his academic peers in or outside of DAGlabs, or with the open-source community under Kaspa in this chronological order:

1. Secure High-Rate Transaction Processing in Bitcoin
1.5 GHOST (appendix of the above paper)
2. Inclusive Blockchain Protocols
3. SPECTRE

PHANTOM family of protocols
1. GHOSTDAG (Kaspa's current consensus, greedy version of the PHANTOM paradigm)
2. DAGKNIGHT (the first consensus released under Kaspa, ultimate PoW achieving parameterlesnes, linear oredring, and utilizing the GHOSDAG security and speed with better results)

Now, let's take a look at how this all started.

Yonatan was a Ph.D. student of Prof. Aviv Zohar at the Hebrew University of Jerusalem. Under this fruitful advisory, they (and several other collaborators) provided the first formal security proof for the Nakamoto consensus and invented GHOST, SPECTRE, and PHANTOM GHOSTDAG (later renamed to just GHOSTDAG).

Now is also a good time to mention another important core contributor, Shai Wyborski.

Although Yonatan Sompolinsky and Aviv Zohar invented GHOSTDAG (GD) well before Shai entered the picture, the GD authors encountered an obstacle in proving GD security.

The original paper thus needed new proof that needed to be bulletproof indeed. That was one of the first tasks Shai Wyborksi had in DAGLabs: fixing what was wrong and finding better security proof. This is also why Shai is mentioned as a co-author of the GD paper.

Everybody involved thought proving GD security would take a month at most, but It turned out to be a huge task that took Shai the better part of a year, and it required him to invent a new technique, which was then leveraged/extended by another core contributor, Michael Sutton, to prove the security of the latest protocol, DAGKNIGHT (DK). More about this important task later in this article.

But the long searched-for security proof was not the outcome of one man’s work. Rather, it was a fruitful cooperation of a cryptographic expert and great researcher with a math technician to realize the ideas into a coherent proof on the one hand, and a computer scientist of great mind and intuition with vast DAG analysis experience on the other hand - Shai and Yonatan.

The purpose of DAGlabs, then, was to implement one of the available protocols or a combination thereof to a PoW model, where Kaspa eventually settled on implementing GHOSTDAG and forgoing SPECTRE. DAGKNIGHT was an unexpected byproduct of working on another problem and was only published long after DAGlabs was dissolved.

DAGlabs aimed to challenge what already works and develop enhanced versions or completely new protocols. However, DAGlabs was dissolved before the Kaspa launch in 2021, with most of DAGlabs' ex-members now contributing to Kaspa through volunteering/grants from the community.

Kaspa is the result of over eight years of theoretical research & design into blockDAGs. Starting from GHOST, each implementation underwent numerous series of modifications & improvements, finalizing with the current advanced GHOSTDAG protocol, which was translated from theory into a functioning permissionless ledger for Kaspa.

Theoretical Research & Development

Dr. Yonatan Sompolinsky

2013 - GHOST Protocol
2016 - SPECTRE Protocol

Dr. Yonatan Sompolinsky, Dr. Shai Wyborski, Professor Aviv Zohar

2018 - PHANTOM paper

DAGlabs/Kaspa (2018-2021)

2018 - PHANTOM Protocol & Kaspa future consensus development
2021 - GHOSTDAG, which originated from the PHANTOM paper, is applied as the Kaspa consensus

Kaspa (Since 2021)

November 7th, 2021 - Release of Kaspa mainnet
October 1st, 2022 - DAGKNIGHT Protocol (GHOSTDAG successor and future consensus of Kaspa)
November of 2023 - Kaspa tested 3 and 10 BPS while finalizing the Rust rewrite for their nodes

Some notes on the mentioned protocols

SPECTRE and PHANTOM GHOSTDAG (or just GHOSTDAG) are somewhat parallel because they both have properties that other protocols do not. GHOSTDAG has linear ordering, SPECTRE is parameterless, but only DAGKNIGHT achieves both, thus acting as a technological diamond in terms of flow.

PHANTOM can be considered a family of consensus protocols, where GHOSTDAG and DAGKNIGHT are two instantiations of it.

PHANTOM and GHOSTDAG are essentially the same and were both introduced together in the same paper. However:

PHANTOM acts as a paradigm, an idealized version that can not exist in reality, creating a theoretical precursor to GHOSTDAG.

GHOSTDAG is the realization of PHANTOM or a practical approximation of the theoretical groundwork.

Kaspa’s current consensus is GHOSTDAG (GD) (2021), an improved realization of the PHANTOM paradigm (2018), another consensus co-founded by Kaspa's core contributors and Aviv Zohar. Still, it did not seem good enough for Kaspa, since they already aimed towards a future upgrade of the current Kaspa consensus, which is now capable of 1 block per second (BPS) and 300 transactions per second (TPS), with the currently released DAGKNIGHT (DK), which would take the game to even higher levels. Not by improving throughput, since the throughput can deteriorate a little bit as DK will be more computationally taxing than GD, but definitively by better utilizing GD attributes and providing even higher security standards. But for now, the main focus of Kaspa is GD, where DK's moment of glory will come next.

So, where the current GD does assume an upper bound on the network latency, its most recent successor, DK, doesn't. However, both consensus brothers, DK and GD, are responsive asynchronous divisive consensus protocols based on PoW, resilient to up to 50% of attackers (which is also true of vanilla Nakamoto Consensus).

Also, as Dr. Sompolinsky said during the , when we are talking about a solution that bears in mind the latency responsiveness, none of this would be possible without PoW.

If we look back to Bitcoin, Satoshi didn't innovate new technologies, but what was innovative was the combination of technologies put together to create something unique. The same goes with Kaspa.

Even though the DAGs are not a breakthrough on their own, the BlockDAG technology solution designed by the Kaspa developers represents the next leap beyond legacy blockchain implementations. Kaspa’s pioneering blockDAG is a fully decentralized, intrinsically scalable solution that adheres to the highest security standards through a generalization of the Nakamoto Consensus model.

Nakamoto's consensus model, however, was not the only inspiration Kaspa took. They also highly respect Bitcoin’s open-community-contribution mindset and approach to development.

Look at the following Kaspa Improvement Proposal (KIP), Rust rewrite, as an example, written similarly to Bitcoin's improvement proposals, BIPs.

Kaspa has neither a team nor a roadmap and will never have one.
Just like Bitcoin.

Development is done in an open-source fashion, which means devs work on what they see fit and then coordinate through open R&D weekly or biweekly meetings. If a developer has a substantial project to propose, they write a grant request and collect KAS from the community; community treasurers then handle the funds.

Every future movement is openly discussed on Kaspa Discord.
So, to push for your wishlist to be implemented, join Discord and voice your agenda.

Kaspa - The crypto silver’s ledger

The vision behind this project is to build a Nakamoto-like service that operates on internet speed. We wanted to build a system that surpasses the limits of Satoshi’s v1 protocol (aka the Nakamoto Consensus) yet adheres to the same principles embedded in Bitcoin.

- Yonatan Sompolinsky

Kaspa is the world’s first blockDAG - a ledger architecture enabling parallel blocks & instant transaction finality. Propagated by a robust proof-of-work engine with rapid single-second block intervals, Kaspa is an open-source, decentralized, and fully scalable Layer-1.

Kaspa was developed to solve the trilemma in the usage of digital assets: Security, Scalability, and Decentralization. Utilizing a revolutionary blockDAG as opposed to blockchain, Kaspa allows the fastest, most scalable, and most secure transactions with absolutely no sacrifice to decentralization.

With its current speed of 1 block per second (BPS) and 300 transactions per second (TPS), Kaspa is 600 times faster than Bitcoin and figuratively replaces Litecoin as “the silver of crypto.”

The Kaspa core devs

Kaspa core contributors mainly include ex-DAGlabs developers and researchers from academic backgrounds who actively contribute to the advancement and maintenance of Kaspa and its codebase and are simply a group of people whom the open Kaspa community holds in high regard.

Michael Sutton - Researcher and Core Developer

Computer Science Masters from The Hebrew University, Distributed Systems Researcher & Developer

Ori Newman - Core Developer

Cryptocurrency and Distributed Systems Developer

Yonatan Sompolinsky - Researcher, Founder

Postdoctoral in Computer Science at Harvard University

Shai Wyborski - Researcher

Ph.D. Candidate Researching Classical & Quantum Cryptography

Elichain Turkel - Core Developer

Applied Cryptographer and High-Performance Systems Developer

Mike Zak - Core Developer

Cryptocurrency and Distributed Systems Developer

Kaspa and their Go beyond the blockchain approach

The purpose

Kaspa, technically not a Nakamoto consensus but a generalization of it, works on a proposal from 2017 to develop DAG into a separate PoW-based cryptocurrency and try to push the limits of Nakamoto's consensus from the outside while keeping the generalization in mind.

The goal of the generalization is to preserve the key aspects of the Nakamoto consensus security-wise while allowing for more scaling.

The above-mentioned DAG is not a consensus mechanism but a mathematical structure with directed edges and no cycles (i.e., there's no path from a vertex, the fundamental unit of which graphs are formed, back to itself).

In the context of distributed ledgers, a blockDAG is a DAG whose vertices represent blocks and whose edges represent references from blocks to their predecessors.

In a blockDAG ledger, new blocks reference all tips of the graph (blocks that have not yet been referenced) that their miners see locally. So, in a blockchain or BlockDAG, blocks are published immediately.

Refer to the actual real-time DAG visualization created by the Kaspa core contributors to fill in the picture.

Kaspa's main scalability feature is by allowing higher TPS and BPS without sacrificing security. In addition to that, you can also gain some scale by simultaneously validating parallel blocks (this is part of the goals of the Kaspa Rust rewrite sprint, the status of which is 80/100% by the middle of November 2022).

While doing so, Kaspa sticks with the PoW model that consists of PoW block creation, transaction fees, involvement of miners, roles of full nodes, and the use of the UTXO model and deflationary block rewards. However, Kaspa replaces the constraining longest-chain rule, also known as the heaviest valid chain with the most cumulative proof of work (measured in difficulty) rule, with a rule that allows reaching a rapid consensus about the precedence of parallel blocks and, consequently, on what transactions are considered valid.

From a miner's point of view, things are largely the same in terms of the mining process. Mining, regardless of Kaspa or Bitcoin, is always done in parallel. If a miner hears about a new block while mining, they drop the current block and start mining a new one.

Then, the longest-chain rule makes projects vulnerable to history rewrites if an attacker mines a chain that is longer than the honest chain after the fact. The 51% block reorganization attack is a fundamental flaw in all proof-of-work systems: because the longest-chain rule cannot differentiate between honest and malicious miners, a malicious miner with enough computational power can rewrite history to its own needs. This is why any proof-of-work system needs to assume that at least 50% of the mining power belongs to honest participants.

NOTE: If this is the first time you are reading about the 51% attack and want to know more, please read the following article, in which I explain all you need to know to understand its context in this article:

Learn the Blockchain Basics - Part 4: The 51% Attack

Still, this is a matter of philosophical position whether this is a flaw at all. If a majority of the network wants to roll back the chain, should the protocol prevent them from doing so?

However, this can be solved with Kaspa and their already-present 49% hashrate attack resistance gained from Nakamoto Consensus, the best security a consensus protocol could have. Then, what Kaspa achieves is to scale up without losing that property.

Kaspa GHOSTDAG recognizes that honest blocks would be very well connected to each other but not to adversarial blocks (even though the adversarial blocks could be well connected among themselves), so, as long as an attacker is computationally inferior, the honest network will look like a highly connected lump of blocks which includes most blocks in the network. By finding this clump and giving precedence to blocks therein, attacking the network while only controlling a minority of the block production becomes infeasible.

This mechanism has been described in the PHANTOM paper, and as we already know, Kaspa uses the GHOSTDAG protocol, the realization of the PHANTOM paradigm.

If you would like to delve deeper into this concept, I recommend starting with the following materials:

Kaspa and their blockchain trilemma solving consensus protocols, GHOSTDAG and DAGKNIGHT

Let's start with a concise executive summary of what DK does. To reiterate, GHOSTDAG is a version of PHANTOM, and GHOSTDAG’s improved follow-up is DAGKNIGHT. Therefore, since this all starts with PHANTOM, we can start this comparison with the definition of the PHANTOM rule, followed by some mathematical vocabulary used in Kaspa papers.

NOTE: To read about the path that led from PANTHOM to GHOSTDAG, read the article by Shai (Deshe) Wyborski, Kaspa — What are We Actually Doing Here?, the From PHANTOM to GHOSTDAG section.

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.

A PHANTOM generalization of the Bitcoin longest chain rule 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 that were unknown to the block's miner at its creation and of blocks that were created before the miner of the block finished its propagation.
The PHANTOM optimization rule is to return max k-connected clusters.
An honest set of blocks is a set that is the largest k-connected set of blocks that are mostly fully connected.

In GHOSTDAG, we set the parameters D and k, such that it holds most of the time that no more than k blocks are produced within D seconds. The k parameter quantifies how "connected" a "well-connected" chunk is. A "well-connected" chunk is just a collection of blocks, such that each block is parallel to at most k other blocks. We call this a k-cluster.

The observation behind DK is that instead of choosing k in advance, we look for the smallest k such that the largest k-cluster covers more than half of the blocks. Thus, instead of choosing k in advance, we use network conditions to determine the best current k. This removes the need to hardwire an a priori bound on network latency.

Now, back to the comparison of both protocols.

In GD and DK, the confirmation times scale with the network latency. The difference is that GD scales like a hardwired bound on network latency, while DK scales like observed network latency. In GD, we have to decide a bound D on the latency in advance, and worse, we have to take a large margin of error to maintain security (currently set to 10 seconds). This means two things:

1. If latency improves much below D, the confirmation time becomes suboptimal.

2. If the latency degrades to be above D, then security degrades with it.

So, if the latency, for example, becomes 12 seconds for a long period, then during this period, a 45% attacker could take over the network; and if it becomes 60 seconds, then a 25% attacker could take over the network (speaking only in rough gauges to drive the point). Note that this holds for all PoW chains.

DK solves both of these issues. That is, it does not require that margin of error, so confirmation times can be very close to the limits of the network without taking a risk because if network conditions degrade, conf times will automatically increase to compensate.

The evolution of DAGKNIGHT (DK) from GHOSTDAG (GD)

With Yonatan’s help, Shai proved the security of GD by creating a conclusive mathematical proof. This proof was then upgraded and extended by Michael Sutton to form a proof for DK.

However, the DK proof was far from a simple extension. Michael and Yonatan did not like that a hypothetical attacker could utilize the worst-case apriori assumption of higher latency to gain some advantage when they observed a low-latency DAG.

A low-latency DAG is simply a narrow DAG where all blocks are well connected. Analogically, a DAG that looks like a chain is "maximally connected." Also, there cannot be any parallel blocks when all blocks are connected.

At first, they tried several methods to tweak GD into a coloring method that can give an edge to a well-connected DAG representing lower actual latency. They ruled out several options, finding an attack for each. Then, the initial DK idea came to them in one spark of thought: "The min-max optimization definition in the DK paper," based on which they realized they could reach a completely new realm: "parameterless-ness."

For the following three years, Yonatan advised Michael on building a proof, they ran into challenge after challenge, and each one required a major enhancement to the original idea. By doing so, layer after layer, they built a unique solution, which you can read about in the DK paper.

During that time, Yonatan provided many insights based on his vast DAG analysis experience, obtained mainly while analyzing SPECTRE.

Kaspa in points

1) BlockDAG 101

Fast async PoW; graph of blocks; consensus here is an agreement to an order of blocks.

The single role of a DAG protocol is to output a linear ordering on the DAG so that we are sure that all nodes understand what block precedes what block and know that all other topological relationships between blocks do not need to be explicitly ordered.

2) The Kaspa goal

From the user's perspective:

To make Kaspa the fastest possible P2P cash system

To create a fair system in which:

a user’s transaction is not front run
rewarding all blocks without discriminating between on-chain and off-chain blocks.

The core idea behind using a PoW-based DAG is to replace the mining paradigm of the Nakamoto Consensus, in which miners propagate and extend the winning chain only, with the more informative paradigm, in which miners propagate and extend the entire history of blocks-each new block points at all recent blocks in the history, rather than to the winning one.

From the technology perspective:

Most of the Kaspa developers are currently focused on the Rust rewrite to improve TPS and BPS.

Kaspa can choose the follow-up focus from the two options below, but also both approaches can be applied simultaneously:

Option 1)

Make Kaspa a data availability layer for Ethereum

To build into Ethereum - instead of creating a solitary standalone product. For this purpose, Kaspa designed the network to order transactions to the Ethereum ecosystem.

Option 2)

Add smart contract functionality directly to Kaspa and have Kaspa support smart contracts natively.

3) What is Kaspa trying to accomplish?

To enhance blockchain scalability and allow cheap and fast peer-to-peer (P2P) transactions.

To improve confirmation times, to fix a problem of today's blockchains by alleviating and removing as many assumptions on the network as possible, meaning you don't have to assume a bound-on network latency. This is reachable by application of the DK protocol's parameterlessness.

4) What problems do today’s blockchain projects have, and how can Kaspa solve them?

Today's world needs:

1) Increasing BPS while maintaining the non-decreasing confirmation times:
Since confirmation times do not scale with block times, Kaspa increases the BPS while the confirmation times, determined by network latency - not protocol, remain the same.

2) High throughput: currently, it's ~300 TPS, and Kaspa is working to increase it significantly.

3) Near constant disk space requirements and constant time for bootstrapping a new node from scratch: Kaspa provides a new node to sync trustlessly from scratch just by downloading the full history of the last two days and some near-constant size proof of the past. No need to even download block headers of the full history. Currently, Kaspa is the only DAG-based technology with a pruning feature. And just to mention, designing a pruning procedure for DAGs is generally very, very difficult.

5) How does Kaspa want to solve current blockchain issues?

By removing the assumption that blocks form a chain so that if two blocks are created at the same time, the next miner doesn't need to choose one blockDAG to point to, but instead, they can choose to point to both of them at the same time. This creates a DAG of blocks, or a BlockDAG.

This is possible because of a change made to a PoW mining protocol in order to yield a blockDAG, which means that blocks may reference multiple predecessors instead of a single parent.

6) What will Kaspa deliver?

I. Transaction sequencing

Kaspa wants to target the infrastructure layer of the DeFi stack, the transaction sequence layer, and become a prominent sequencer for DeFi users, utilizing the Kaspa services that order the transactions and communicate with the Ethereum mainchain in a more limited manner.

II. Transaction ordering with manipulation resistance

Kaspa aims to circumvent the public mempool (the network’s publicly visible waiting area for pending transactions) and ensure that miners cannot collude in time and cannot extract value from users, which means Kaspa wants to defeat the front-running bots and miners.

Kaspa's approach to significantly increased transaction security here would be applying:

cryptographic challenges and encryption features
at least 10, and ideally 100, blocks per second (BPS)
high block weight - combined with the extreme block-per-second rate, which would be coming out of those 100 BPS

NOTE: Currently, Kaspa operates with 3 BPS, which will be increased by the Rust rewrite sprint to 10! The ultimate goal for Kaspa is to reach 100 BPS.
Currently (18 November 2022), they are testing 30 BPS during their Rust rewrite sprint.

From the testing:
The plot shows block processing rates as a function of network-produced blocks-per-second (BPS). The benchmarks were executed on an AMD Ryzen 9 3900X 12-Core node. Blocks contain ~100-200 transactions.

The red line marks the scenario where the number of blocks we can process is smaller than the number of blocks produced. Hence, we want to choose a block number for which there is some safety margin between the red and green lines (to account for IBD, hardware variance, network hiccups, and other unexpected problems). The parameter region marked by the blue area indicates a safety margin of 3x.

Note how the green line initially increases; this is the power of parallelization kicking in as the graph widths grow. However, as we keep increasing the block rate, the parallel cores become saturated, and the combinatoric aspects of computation become more dominant, whereby the performance deteriorates.

III. An equivalent to the blockchain double-spent protection based on proper DAG ordering, which also proposes a solution to the scaling problem of ordinary blockchains by removing the need for a large block delay.

The following description is taken from an article by Shai Deshe Wyborski, in which he describes one of the main purposes of the Kaspa GHOSTDAG consensus protocol, which is secure regardless of the ratio between the block delay and block round trip time.

The proper ordering delivered by GD is:

Topological: a block cannot appear in the ordering before any of its parents
In consensus: at any point in time, all of the nodes in the network must agree on the ordering of all but a constant number of new blocks
Secure: a computationally inferior adversary cannot revert the ordering of blocks retroactively
Able to offer liveness: there should be a clear criterion for when a block is “finalized” in the sense that it will never change its place in the ordering, and every block should satisfy this criterion within a constant amount of time
Efficient: the problem of determining, calculating and maintaining the order should be feasible for today’s computers even in light of an ever-growing DAG

IV. The Freeloading bound feature (Lemma 12 of GD paper)

A feature provided by GHOSTDAG ordering to solve the issue that originates from the design in which we allow parallel blocks and multiple parents.

This special property restricts the attacker’s blocks to point to the honest blocks and uses the work of honest blocks to improve its credibility. This phenomenon is called Freeloading, and Lemma 12 simply means that an attacker who wishes to revert arbitrarily old blocks cannot use honest blocks in a meaningful way to perform a rearranged attack.

V. A miner extractable value (MEV) resistance feature, which involves encryption in a more sophisticated manner

MEV is sometimes referred to as an “invisible tax” that miners can collect from users – essentially, the maximum value a miner can extract from moving-around transactions when producing a block on a blockchain network. MEV was first used in the context of proof-of-work, where miners control the order and inclusion of transactions in a block but also exist in PoS.

VI. Pruning historical data by default tradeoff

Gain: faster sync for new nodes.
Loss: new nodes sync in SPV mode by default, or, if they wish to validate the entire history, through resource-heavy (hence more centralized) archival nodes

VII. Have instant speed of TX confirmation, which would be great, for example, for new versions of Uniswap and similar projects that will then:

Confirm that your transaction is valid
Inform that the transaction entered the agreed sequence of transactions, so you know you were not front-run
And clarify what exactly the effect on the current transaction state is, and I mean the status of things that your transaction initiated even after the decryption phase

All this while:

Remaining PoW security
Operating with almost zero fees

7) What is the purpose of the Kaspa cryptocurrency, KAS?

Kaspa (KAS) is the name of the cryptocurrency token that acts as an engine, or gas, if you want, for the whole ordering and sequencing layer. The name originates from the Aramaic term for silver or money.

Use case:

I. Gas

II. Auctioning the transaction ordering in the block

The transaction order is defined by the order of blocks. In a case where we have two parallel blocks, which include conflicting transactions, we systematically ignore the transaction from the block that has a lower `past size`. The past size then refers to the cardinality of blocks that precede the current block. The past size of a block is the number of blocks in its past - the number of blocks it points to directly or indirectly.

8) What major enhancements can users of Kaspa look forward to in the future?

The ability to deliver smart contracts in the form of service in leading projects that allow for more expressive preferences of blockchain users. An example of such an improvement would be the possibility of having triggered execution conditions for DeFi users - the ability to say when a user transaction wants to be triggered in, for example, 20 blocks if and only if another set of conditions happens. These kinds of expressive references would allow users to specify the allowed slippage and similar things that cover for the asynchronicity and the uncertainty of what happens with the transaction when it gets actually mined and allow something that allows users to be much more general and expressive in their preference.

9) What major improvements will Kaspa core contributors deliver with the application of DAGKnight consensus instead of the currently used GHOSTDAG protocol?

Long story short, the DAGKNIGHT consensus will create the groundwork for even faster transaction and confirmation times, making KASPA the ultimate L1 PoW coin in existence.

DAGKNIGHT (DK) is a new consensus protocol written by the authors of this KIP that achieves responsiveness while being 50%-byzantine tolerant. It is, therefore, faster and more secure than GHOSTDAG (GD), which governs the current Kaspa network. In DK, there's no a priori hardcoded parameter k; consequently, it can adapt to the "real" k in the network. In DK, clients or their wallets should incorporate k into their local confirmation policy of transactions (similarly to some clients requiring six confirmations in Bitcoin and some 30 confirmations).

Goals

Complete the R&D work necessary to implement DK for Kaspa.
Implement DK on Kaspa as a consensus upgrade.
Add support and API for wallets' transaction acceptance policy to correspond to DK's confirmation speed.

Deliverables

Applied research:

Adapt the consensus algorithm to enforce a global maximum bound on network latency (can be taken with a huge safety margin; does not affect confirmation times), which is necessary for difficulty and minting regulation, pruning, and more.
Devise efficient algorithms to implement the DK procedures — the current pseudocode is highly inefficient. The implementation will partially utilize the optimized GHOSTDAG codebase, as the latter is a sub-procedure of DK.
Research the optimal bps regarding confirmation times, and provide a recommendation. (optional)

Implementation:

Implement DK on the Kaspa Rust codebase as a consensus upgrade.
Design a transaction confirmation policy API and implement the supporting functionality in the node.

Backward compatibility

It breaks consensus rules, thus requiring hardfork.
It adds (and potentially breaks) RPC API.

Outro

Kaspa has the potential to stand side-by-side with Bitcoin and Ethereum as the third most used Layer 1 framework or even a replacement for one of the two, and I also believe Kaspa is able to carry a decentralized global scale economy. With that goal in mind, Kaspa is planning to provide tools that will make it easy to develop Layer 2 applications right after the implementation of the Rust rewrite KIP (Kaspa Improvement Proposal) is finished and tested.

Other than that, Kaspa includes many other aspects that are not discussed in the paper, such as a novel approach to difficulty adjustment, a fancy pruning mechanism, and future plans for infrastructure for layer 2 applications.

Nobody knows what the future holds, but I believe there is a non-negligible chance that Kaspa might become the most resilient, most robust, and fastest PoW blockDAG in the world.

It also becomes a home for a principled community of developers, researchers, and PoW fans, to be a vibrant testbed for new ideas, a place where innovation is welcome, and the path to the integration of tested and justified features is in sight. This agility is one of the privileges of being the self-proclaimed “little brother” to Bitcoin’s gold, and I am pretty sure Kaspa will take full advantage of it to become the true Bitcoin’s silver.

Final thoughts from the author

Kaspa's core contributors are rockstars on the academic ground and everything PoW-related. Yet, they are unknown to the wide audience of speculative markets of cryptocurrencies.

I guess this will change. Very soon.

If you want something to compare Kaspa with, compare it with Bitcoin.

If you need an approximation of Kaspa value, take it as a Litecoin replacement, Bitcoin’s true silver.

Also, I appreciate the Kaspa development approach in which they refuse to accept the narrative of other projects about why the TPS/Confirmation times are "not that important."

Kaspa and their vision to continue with what Satoshi has started motivated me to dive into the deepest research of my life and deliver this comprehensive review for you. Also, the protocols of the PHANTOM family, GHOSTDAG and DAGKNIGHT, that power the cryptocurrency represent the best realization of Satoshi’s vision yet and pave the way to fulfill their goal of electronic cash.

Epilogue

If we imagine the global interconnection as the wheel that propels modern civilization forward, TCP/IP is like the pneumatic tire added to the wheel, bringing us from the age of the electrical telegraph to the age of the Internet.

Now, the blockchain promises to add yet another layer on top of the tire, which would enhance the wheel's functionality even further. Perhaps, if things go well, BlockDAGs could be like an anti-gravity harness, giving the oft-lumbering vehicle of humanity a chance to soar into the heavens. And yes, the tickets will be paid in silver ;)

The end.

Kaspa and MEXC podcast: Kaspa the Silver of the future

Kaspa Q&A

The Kaspa resources "megathread" by Shai Deshe Wyborski

About the significance of high TPS in deflationary PoW coins, which goes well beyond throughput - by Shai Deshe Wyborski

Kaspa in a Twitter thread

Kaspa in stats

Kaspa Coingecko stats for November 2022:

Market Cap: 95.4M

Mkt Cap Rank: #222

All Time High: 0.006799

All Time Low: 0.0001711

Kaspa mining and hash rate stats:

Kaspa (KAS) Mining Profit Calculator - WhatToMine

Current Kaspa hash rate

The comparison of the Kaspa November 2022 hashrate with Ethereum Classic, Ergo, and Flux - Explanation by Shai Wyborski

Imagine that instead of calculating hashes, you are carrying a stone.
In such a scenario, Ergo miners would be hauling huge boulders, Ethereum Classic and Flux miners would be carrying tennis ball-sized rocks, and Kaspa miners would be prancing around with small pebbles.
If we only count the number of stones, then Kaspa seems to be almost leading this race. However, it is fairer to count the weight of the stones,
in which Kaspa is rather behind.

Different types of hashes require different computational capacities, and $kas's HH algorithm, despite its name, is rather light. Ethereum Classic (ETC), Ergo (ERG), and Flux use the EtHash, Autolykos, and ZelHash hashes, respectively.

Using benchmarks for RTX 3090 on @WhatToMine, we find that (In terms of the energetic cost of a single hash):

EtHash = kHH * 8, Autolykos = kHH * 4, and ZelHash = kHH * 11 million

This will provide us with the following:

ETC's global hr of 50T is equivalent to a kHH hr of ~400T
Ergo global hr of 20T is equivalent to kHH hr of ~80T
Flux global hr of 3M is equivalent to kHH of ~30T

So, in summary, in terms of computational power required, ETC is about x8 higher than KAS, ERG is about the same as KAS, and Flux is about half of KAS. Combined, they are nearly 10 times larger than KAS.