Kaspa — What are We Actually Doing Here?
(if you are unfamiliar with Kaspa you are still welcome to read the post, or you can first check out our website and Discord server)
It is astonishing to see how fast the Kaspa community is growing. But as Kaspa gains more traction and popularity, it becomes obvious to me that most people don’t know what Kaspa actually is. This is by no fault of their own, since we have neglected to explain the core technology Kaspa is based on in an accessible manner. Sure, the information exists in technical papers and conference talks, but these are not written with the common user in mind. My goal in this post is to rectify this.
Kaspa is a broad term which describes a complicated system with many components and aspects. But at its core, Kaspa is an implementation of the GHOSTDAG protocol, which was first conceptualized by Yonatan Sompolinsky and Aviv Zohar in 2016 (I joined the efforts two years later) . The entire following post is dedicated to describing this particular aspect of Kaspa.
Cryptocurrencies are often very complicated, and a lot of users tend to forgo on fully understanding the promise of one coin or another, which is fine. But I think the true power of GHOSTDAG is in its simplicity: GHOSTDAG is a very gentle generalization of Nakamoto consensus, and unlike many coins, I believe that anyone who understands Bitcoin can easily understand GHOSTDAG, what it achieves, and how it achieves it.
Furthermore, I hope I can convince you that GHOSTDAG offers a simple (though very hard to implement) solution to the core scaling issue present in Nakamoto consensus (i.e. in any PoW based blockchain), whereby it might have the potential to replace Bitcoin and Ethereum as the layer one framework which could carry a decentralized global scale economy (and with that goal in mind, Kaspa is planned to provide tools which will make it easy to develop layer two applications, but that is a story for another post, probably by another person).
This post assumes basic familiarity with Nakamoto consensus (e.g. with Bitcoin), the uninitiated can fill in the gaps with this wonderful video.
The Nakamoto Consensus Scaling Problem
Bitcoin, and other blockchains, purport a 51% security. That is, they claim that as long as most of the hashes in the network are created by honest miners, the network is protected from adversaries who wish to revert arbitrarily old transactions. But is this actually true? Only approximately. In this section I will explain why this is only approximately true, and why this issue is at the crux of all blockchain scaling issues.
Imagine that you are an adversary who wishes to revert a transaction which took place 10 blocks ago. Lets say that you intended to do so since the block was created, so you started making preparations since.
Bitcoin works on a longest chain rule (well, it actually works on a heaviest chain rule, but I am sweeping this detail under the rug for simplicity), which means that in order for you to convince the network to switch to a different chain, where this transaction never happened, you would have to create a longer alternative chain faster than the network. If you have less than the computational power of the rest of the network, the probability that you manage to crank out say 12 blocks before the honest network does is ridiculously small.
But here comes the crux: this only happens if the honest network blocks are always arranged in a chain. However, this is not always the case! Every once in a while two honest miners will create blocks at approximately the same time. These blocks will compete with one another until one of them is discarded. 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.
This means that in order to revert a transaction, the attacker only need to create slightly less blocks than the honest network: for every 150 honest blocks, the attacker needs to create more than 149 blocks, for which %49.9 of the global hash rate suffices.
This doesn’t seem like a big deal, and indeed there is little difference between a 50.1% attacker and a 49.9% attacker. 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, whereby decreasing the security of the network.
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 tradeoff is the main motivation behind the GHOSTDAG protocol.
So How Can We Allow Parallel Blocks?
The core idea is very simple: instead of having any block point to a single parent block, allow it to point to many parents, thus giving the blocks in the network the structure of a DAG rather than a chain.
The first natural question about this approach is: what about double spends? If we allow two parallel blocks to coexist, how do we handle the possibility that they contain contradicting transactions?
Very roughly, the solution we are working towards is to choose some ordering of the blocks. That is, we take the DAG structure and arrange it in a chain somehow. We then traverse the chain and include all transactions which do not contradict previous transactions.
But how do we choose this ordering? Well, this is where things get complicated. Choosing an ordering rule is what can make or break a blockDAG. The GHOSTDAG (and its computationally unfeasible precursor PHANTOM) protocols are basically that — means to order blocks in a DAG.
Before we go into these protocols, let us list some of the properties we expect of a good ordering:
- It has to be topological: a block can not appear in the ordering before any of its parents
- It has to be 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
- It has to be secure: a computationally inferior adversary can not revert the ordering of blocks retroactively
- It has 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
- It has to be 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
An ordering with the properties above might pose a solution to the scaling problem of ordinary blockchains, by removing the need for a large block delay. And indeed, the GHOSTDAG protocol is provably secure regardless of the ratio between the block delay and block round trip time. That is the central promise of GHOSTDAG.
For a more detailed account of how orphaned blocks affect Bitcoin security read this post.
PHANTOM — GHOSTDAG In an Ideal World
Before diving into GHOSTDAG, it is instructive to consider a scenario where efficiency is not a concern. That is, we assume that any combinatorial calculations, even NP complete ones, are feasible (though we still assume there exists a hash function which is hard to invert, or else the entire PoW paradigm crumbles). In such a world, how would you design a good ordering of the blocks?
The core idea is that the honest network blocks should be well connected in some way. Since all honest miners are communicating with each other and are not withholding blocks, their honest work should form a well connected DAG. An attacker working on a side chain would seem very disconnected from the main chain.
Translating this imprecise idea into an actual algorithm goes by the mathematical notion of a k-cluster.
Given a block B, its past is the set of blocks which are reachable from B. Similarly, its future is the set of all blocks B is reachable from (equivalently the set of all blocks which have B in their past). The remaining blocks are called B’s anticone.
A k-cluster in a DAG is a subset with the property that no block in the subset has an anticone larger than k (when only counting blocks within this subset). We say that a k-cluster is maximal if there are no k-clusters with more blocks.
With this concept in hand, we are ready to describe the PHANTOM ordering almost formally:
- Choose k so that most of the time the honest network does not create more than k+1 parallel blocks
- Find a maximal k-cluster (choose some arbitrary tie-breaking rule if there are several maximal k-clusters)
- Order the blocks in the maximal k-cluster via an arbitrary topological order with the following property: a block outside the chosen k-cluster will appear as late as possible, that is, either after all blocks inside the k-cluster appeared, or when the ordering reached a block in the k-cluster which has this block in its past (this leaves open to interpretation what should be done with the blocks outside the k-cluster, or whether they should appear at all)
(Of course some details are swept under the rug here, like what does “most of the time” means, and how does the fact that the honest network sometime does create more than k parallel blocks does affect the security of the protocol, etc.. All these details are thoroughly discussed in the paper).
An interesting thing to note is that this approach is actually a direct generalization of Nakamoto consensus. If we choose k=0, and discard blocks outside of the maximal k-cluster, we remain with the longest chain.
From PHANTOM to GHOSTDAG
There are two issues with the PHANTOM protocol as it is presented above:
- It could not be implemented efficiently: Indeed, the problem of finding a maximal k-cluster in a given DAG is NP-complete.
- It is not incremental: Every time the DAG updates, the entire computation must be restarted. In particular, it requires storing the entire DAG structure.
GHOSTDAG is a greedy variant of PHANTOM which solves both these issues. The idea is that the (now approximate) k-cluster is maintained incrementally. Each block has a number called its blue score which indicates how many blocks in its past are in the k-cluster. Given a particular block, its selected parent is the parent with the highest blue score. When a new block is created, it is not required to calculate the entire k-cluster. Instead, it inherits most of the k-cluster from its selected parent. The rest is chosen from the anticone of the selected parent. However, since this is a k-cluster, at most k-elements from this set could be included (since all of them are in the anticone of the selected parent. Recall the definition of a k-cluster).
This means that any block should only track at most k additional blocks: those that are in its blue past (that is, the k-cluster from the point of view of that block) but not in the blue past of its selected parent.
From this point of view, the generalization of Nakamoto consensus is even clearer: choosing k=0, the blue score is the length of the longest chain, and the selected chain (that is, the chain starting from the block with the highest blue score and traversing the selected parents) is the original Nakamoto chain.
For a more detailed account of GHOSTDAG you can read this post
But Why Should GHOSTDAG Be Secure?
One would hope that the security of GHOSTDAG would be immediately implied from the security of Nakamoto consensus. But the reality of the matter is that a few more steps are needed.
Since we allow parallel blocks and multiple parents, this creates a phenomenon called freeloading which does not exist in Bitcoin. Freeloading is when the attacker allows their blocks to point to honest blocks in order to increase their own blue score. This way, an attacker can use the work done by the honest network to boast the score of their own chain, and it is ostensibly unclear why their capacity to do so does not imply that they could rearrange the block structure without having to create as many blocks as the honest network.
Fortunately, the GHOSTDAG ordering has a special property called the freeloading bound (which appears as Lemma 12 in the paper). It essentially means that an attacker which wishes to revert arbitrarily old blocks can not use honest blocks in a meaningful way. The amount of blocks they could freeload from is bound by a constant (namely 4k blocks). This means that any attack which seeks to change the ordering of arbitrarily old blocks will run very soon into a race where freeloading does not actually provide the attacker with any advantage. With careful argumentation, this could be used to reduce the security of GHOSTDAG to the security of Bitcoin.
Following this reasoning, we can prove the security property of GHOSTDAG: a computationally inferior attacker can not revert arbitrarily old blocks, regardless of the ratio between the block delay and the block propagation time.
In other words, GHOSTDAG achieves the same security as bitcoin, but without any constraints on the block rate, whereby alleviating the Blockchain scaling problem. It also affords nearly immediate confirmation times (in the order of seconds).
From GHOSTDAG To Kaspa — Concluding Remarks
GHOSTDAG is an interesting protocol, but implementing it is a challenge by its own right. To describe Kaspa as a straightforward implementation of GHOSTDAG would be a huge understatement. In practice, many engineering and theoretical challenges had to be solved before a usable implementation was within reach (for example, it is extremely non-trivial to implement an efficient way to even tell whether two blocks are in the anticones of each other).
Other than that, Kaspa includes many other aspects which 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.
Kaspa still has a long way to go. For example, at this point we have not yet stress tested the network to see how many transactions it could hold (though we have seen it supporting 40 tps, which is higher than the theoretical limit of Bitcoin and Ethereum combined, without breaking a sweat, cf. chapter 6 of the paper).
Nobody knows what the future holds, but I believe there is a non-negligible chance that Kaspa might become the most resilient, robust and fast PoW blockchain (or rather, blockDAG) in the world.