By: Michael Sutton, Core Developer

This is a blog series explaining the fundamentals of Kaspa in simple and short language. I will assume the least possible prior knowledge, although some fundamentals in blockchain theory, specifically bitcoin, may benefit the reader.

What is Kaspa?

Kaspa is a pure PoW engine which generalizes and scales bitcoin’s blockchain paradigm.

Block-DAG vs. Blockchain

The first change Kaspa introduces is the block-DAG mining paradigm. In bitcoin, miners first select the longest (or to be precise, the heaviest) chain and mine over its top-most block, aka the selected tip. Thus essentially miners do not share the full information they have – they do not share the knowledge of other non-selected chains they know of and chose not to mine over.

In contrast, in the block-DAG paradigm, all information is revealed. We call it “the revelation principle”. The miner references all tips he knows of. Following, any protocol can be ran to make choices over this knowledge, including for instance the longest chain rule, however the maximization of shared knowledge opens many more opportunities.

In essence, by each miner mining over all known blocks, a maximal amount of time relations (e.g. this block was mined “after” this block) is revealed and shared.

Having each miner mine over many block tips (referencing all their hashes in its header), creates a directed graph of blocks with a link pointing from a block to each of the referenced blocks. The cryptographic irreversibility of the PoW function implies that no cycles can be created in this directed graph, making it a Directed Acyclic Graph.

Some block-DAG terminology

The set of blocks referenced by block B are parents(B). The set past(B) is the set of blocks reachable from block B through a chain of parent links (coined “past” because we know they existed before B). Note that past(B) is never empty since it always contains genesis which is the initial block defining the begining of the DAG. Likewise, future(B) is the set of blocks which B is reachable from. The set anticone(B) is the set of blocks “parallel” to B, i.e., not in its past nor in its future. Essentially no time causality information is known between B and blocks in anticone(B). We call it “anticone” because both past and future can be seen as “cones” from B’s perspective.

Ordering a block-DAG

Before delving into the specifics of the GHOSTDAG protocol, which is the ordering protocol used by Kaspa, I’ll describe a general structure for ordering a block-DAG based on any parent selection rule.

Assume a parent selection function f mapping from each block B to one of its parents P. The sub-DAG containing only these special “selected” links (from every block B to its selected parent) is in fact a tree. Let’s name a special non-existing block called “virtual”, which always points at all DAG tips/leaves. This virtual block represents the next mined block in the eyes of the local node.

The mapping function f can be applied on virtual in order to select a specific DAG tip. We can then walk down starting from this tip through the “selected parent” links until reaching genesis. So a mapping f can be translated to selecting a chain C of blocks starting from virtual and ending at genesis.

This chain can be used to deterministically order the complete DAG structure.

To accomplish this task we need one more definition. Let’s define the mergeset of B, mergeset(B), to be the set of blocks that B merged into the DAG. Formally this is the set of blocks which are in past(B) but not in the past of B’s selected parent as chosen by the mapping function f. It’s called a merge-set because it’s the set of blocks that B merged into the DAG from his perspective relative to its selected parent perspective.

Given a chain C and the definition of a mergeset, we are ready to describe a complete ordering rule based on f. The idea is to start from genesis and walk up this chain, where at each chain-block we add his merge-set to the ordering. Intuitively, the chain here acts as a spine of the DAG, where the merge-sets are layers added one after the other. To see this more clearly note that from the definition of a mergeset and its relation to the proceeding chain block, it follows that all mergesets are disjoint sets and that their union covers the entire DAG.

The simple pseudo-code below describes exactly this and is brought here for reference.

function Order-DAG(G):

• let C be the chain obtained by applying f on DAG G as described
• ordering = []
• for block B in C walking up from genesis up to virtual
  • ordering.Add(mergeset(B))
• return ordering

Chain security implies robust DAG ordering

Understanding the relation between a chain and DAG ordering helps reasoning about the relation between a chain selection protocol and the security properties required from a secure ordering protocol.

For a block-DAG representing a transaction ledger, we’d like that the ordering of the DAG is “robust” in the sense that only a small set of blocks near the tips of the DAG might change their order. In other words, we want the ordering to “stabilize” for any block mined “enough” time ago, where enough depends on the amount of certainty required.

Because ordering is governed by a chain, it follows that if the chain is “robust”, i.e., does not change up to a suffix, then the DAG ordered by it is robust as well. Thus all we need now is a secure way to find a robust chain – a secure parent mapping function f.

Next post in this series

In the following post I’ll write about the special parent selection function f = GHOSTDAG and will give more rigorous definitions for related terms used in Kaspa such as “blue score”, “blue work”, etc.

I chose to explain about the chain structure first, because I think it’s crucial to understand this decomposition for getting a clear understanding of the Kaspa system. Regardless of the f used, this chain structure is used by our UTXO algebra infrastructure and also plays a role in the framework we implemented for supporting DAG reachability queries.

The post Core Developer Series: Kaspa 101 – Part 1 appeared first on Kaspa.

Kaspa is the fastest, open-source, decentralized & fully scalable Layer-1 digital asset in the world, utilizing the world’s first blockDAG- a digital ledger enabling parallel blocks and instant transaction confirmation.  Kaspa, with rapid single-second block intervals, solves the speed, scalability and security trade-off which currently limits the usage of digital assets. Built by industry pioneers, led by the people.  For more information, please visit our website at www.kaspa.org or contact-us at a@kaspa.org

The post Top-Tier Exchange Community Fundraising Complete! appeared first on Kaspa.

The post Getting up to Speed on Kaspa appeared first on Kaspa.

Shai (Deshe) Wyborski

(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

and 

 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:

1. It has to be topological: a block can not appear in the ordering before any of its parents
2. 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
3. It has to be secure: a computationally inferior adversary can not revert the ordering of blocks retroactively
4. 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
5. 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:

1. Choose k so that most of the time the honest network does not create more than k+1 parallel blocks
2. Find a maximal k-cluster (choose some arbitrary tie-breaking rule if there are several maximal k-clusters)
3. 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:

1. It could not be implemented efficiently: Indeed, the problem of finding a maximal k-cluster in a given DAG is NP-complete.
2. 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.

The post Kaspa — What are We Actually Doing Here? appeared first on Kaspa.