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.

First and foremost I wanted to thank you all for joining and forming this community, for the interest, excitement, and involvement around the project. Seeing my PhD obsession — POW DAG consensus — realize itself into a live network and a spontaneous community is thrilling yet humbling. Thank you, Todah!

I’m definitely going to start valuing members-count over citation-count, so please bring more crypto friends to the party!

Every few years a new fair-launched POW cryptocurrency captures the excitement of the community — Litecoin, Monero, Grin, and now Kaspa. May the force be with us.

Since we didn’t anticipate this rapid growth, I didn’t prepare accessible answers to several FAQs. I hope to write a longer post about all this in the coming days, but for now here are some answers:

1. Monetary policy will be deflationary. Halving will be more aggressive than Bitcoin’s since market conditions are different (order-of-magnitude faster market discovery). When the deflationary scheduling will be activated, and what would be the initial block reward (compared to the current avg of 500) — TBD. We will try to seal this next week or so. These numbers will imply the finite cap on supply. BTW we should rebase the term Kaspa to refer to today’s 1000 Kaspa, say; the current representation feels not so scarce 🙂
2. Our proof-of-work is a Kaspa variant of heavy-hash, let’s call it k-heavy-hash. My goal here was to create a CapEx heavy POW function, since I believe this concept is both energy-efficient and provides more miner-commitment (stronger than ASIC since less OpEx burnt). Whether k-heavy-hash is actually CapEx heavy, and whether a different POW function will better serve this goal for Kaspa — is a question I’m open to discuss.
3. The project is maintained by a few devs, all of which have other full time dealings, and some of which are funded by DAGlabs (but totally self managed). In particular, there’s no company or entity behind the project that is responsible for your wallet, full node, funds, miners. We are here during our spare time. I, for one, am a full time postdoc at Harvard university, and while this project is my PhD baby, I am at the same time dedicated to my postdoc baby. So this is a purely community project, please take that into consideration. What can you do to help? Arrange for more dev-power to learn the codebase and join the efforts; DAGlabs can potentially fund additional devs, as long as they have the ability to manage themselves, open issues, fix bugs, manage PRs, etc.
4. Roadmap. There is no official roadmap as there’s no organized development. I can write down what devs should be working on IMO, post bug fixing and version updates (HFs). In short, IMO priorities should be accelerating gradually to 10 blocks per second, then implementing an amazing upgrade to the consensus protocol, pending theoretical research results of Michael Sutton. In parallel, if someone can promote a privacy gadget (e.g., bulletproofs) and implementation for Kaspa that would definitely leap us forward.
5. Next week there will be a hard fork (HF) in order to fix a bug and decrease header size. Tune in on this, especially if you are running a mining full node. A few weeks later there will be a HF to embed said monetary policy.
6. Will we list the coin on exchanges? There is no “we”, there’s “you”. And I suggest waiting for the community to grow more organically before bringing retail.
7. When is it recommended to stress test for utxo throughput? You are free to stress test as you wish. However, note that even if bugs are discovered, some time will pass before the devs can make themselves available to fix them. Therefore, I suppose better wait for the current system to prove itself stable for more than two weeks, say.
8. What about block explorer? I believe next week devs will deploy one.
9. Feel free to follow me here or on Twitter https://twitter.com/hashdag where I hope to post more Kaspa related material in the coming weeks.

The post Kaspa launch plan (responding to reality) – Pt-2 appeared first on Kaspa.

• launch Kaspa in gamenet mode, a research oriented experimental network
• inject deliberate fragility into Kaspa launch via random semi-scarce monetary policy
• construct battlefield for reward-based and MEV-based reorgs
• as community matures and hashrate grows, go full scarcity mode, transition from game- to main- net mode, rendering early (gamenet) stage miners profitable in retrospect
• gamenet 2.0 requires developing Ethereum bridge to simulate and practice MEV-reorgs, in order to test and demonstrate DAG consensus’ antifragility

Why Kaspa shouldn’t launch as an ordinary cryptocurrency

[L1, POW, lack of EVM]

There seems to be little room now for a new L1, especially one powered by PoW such as Kaspa. The market has matured, and with it the scope of attacks and manipulations has expanded from direct attacks on block ordering (eg double spends via reorgs, liveness attacks) to attacks that regard txn content — typically in the zero-to-one-confirmations phase — by miners or bots (aka flashbots). Moreover, Kaspa lacks as of now EVM support, rendering it significantly less relevant to the current market.

Gamenet: A proposal to launch Kaspa in a novel experimental mode

Kaspa may be launched as a research-oriented consensus engine that is focused on experimentation, novel testing of dynamics, and a vibrant battlefield for real world cryptoeconomics attacks. I call it gamenet mode.

Cryptoeconomics phase 1

[CPU/GPU mining, uncertain scarcity, low hashrate and security, non-commercializable]

The platform should be CPU/GPU-mineable, to facilitate the base activity; I believe Ethash is a neutral candidate that fits our needs. However, its token should be deliberately unfit for commercialization, in order to penetrate hardcore communities, individuals, and zones that refrain from cooperating with non-BTC or non-ETH tokens. Accordingly, the token’s supply should challenge the ordinary notion of scarcity, and should be unfit for exchange listing. This implies that the platform will obtain low hashrate and low security, at the initial stages.

Gamenet activity

[battle-field, simulation, real world game, selfish mining, reorgs, MEV]

The theme of gamenet’s activity can be thought of as a continuous hackathon over a live network which serves as a battle-test field for simulating real world attacks, manipulations, and dynamics of a multi-player network. The block rewards will incentivize occasional reorg/selfish-mining attacks by strategic and sophisticated miners of the gamenet, whereas transactions in the network will implicitly or directly reflect MEV exploits from real world DeFi systems such as Ethereum.

Community

[R&D groups and individuals, testbed for innovation, recognition by broad crypto community]

The goal is to attract research and dev groups (e.g., flashbots fans) to play, compete and/or collude over the live system, and to extract insights on the real-world dynamics of other live systems such as Ethereum. Further, commercial L2 projects that propose solutions to certain exploits, such as using cryptographic primitives for MEV, can implement those over Kaspa gamenet and prove the robustness of their solution, while others may attempt to refute it. I hope Kaspa will become a center of a vibrant R&D community, and that the general community will look to Kaspa gamenet as a credible source of insights regarding cryptoeconomic dynamics in the wild.

An example for the community’s interest around the topic may be found in this recent summit http://reorg.wtf/

Cryptoeconomics phase 2

[monetary policy solidification, recover scarcity, compensate early community]

As the community and the platform matures, we will want to transition to a solid monetary policy, regulate the supply, and trade over exchanges. To this end, we may set an automatic trigger in consensus that will eliminate the randomness in the monetary policy, and the uncertainty of the supply, once a certain hashrate is reached. This will automatically compensate early participants — the early miners of the network — by rendering the mined tokens scarce in retrospect. See below for specifics. See https://fc21.ifca.ai/papers/222.pdf by Lucianna Kiffer for a related design.

Kaspa development and support

[community+product management, further development and support]

As a continuous real-world hackathon, Kaspa gamenet can significantly enjoy some product and community management, conveying and demonstrating to the community the rules of the game and example dynamics. Community members are welcome to take the lead on these fronts.

On the development side, and closer to the backend, explicit MEV activity can be simulated via a bridge from Ethereum. While not necessary for gamenet, I believe gamenet+MEV will make the platform much more attractive a battle-field.

Individuals capable and willing to take upon themselves some of these efforts, and who require funding, may DM me.

Timeline

[Kaspad ready mid October, Kaspa launch end of October, full gamenet activity TBD]

Kaspad — the core consensus component of Kaspa — will be production ready (though untested) by mid October. The remaining features are (1) implementation of the monetary policy described below, (2) plugging in the chosen PoW function.

The execution of components that enhance gamenet activity depends on community engagement.

Monetary policy and block rewards

Requirements

The block reward should incorporate randomness so as to:

1. Test selfish mining and reorg attacks,
2. Introduce uncertainty regarding the supply,
3. Incentivize extending the main chain, 95% of the time (say),
4. Incentivize forking the chain when the reward — or the MEV opportunity — is exceptionally high.

Concrete proposal

Have each block mint a random amount of Kaspa, where the randomness is a function of the last $M$ blocks. The result of the randomness, the “sampling”, should depend on the block’s hash, to ensure that it cannot be gamed. The randomness should not be a function of the previous block only ($M=1$) because that will lend itself to frequent forking attacks. At the same time, it should be responsive to recent blocks, to ensure a sufficient degree of uncertainty with respect to the supply (so $M=10¹²$ won’t do, as well). I propose $M=~100$ blocks.

Formal description

Given a DAG $G$, GHOSTDAG outputs a chain $C(G) \subseteq G$. For each block $B ∈ G$, let $merging(B)$ be the earliest block in $C(G)$ that contains $B$ in its past. For each block $B ∈ G$, $B.selectedParent$ is the tip of the chain $C(past(B))$. For each block $B ∈ G$, $mergeSet(B,G)$ is defined as $past(B)∖ past(B.selectedParent)$ if $B$ is in $C(G)$, and the emptyset otherwise.

The reward of blocks in G, $rew(*)$, is defined by:

• $rew(genesis) = const_1$
• $rew(B) = const_2*avg_{D \in prvs M blocks of B}rew(D)*4^x + const_3*sum_{D\in mergeSet(B)}(rew(D))$

where $x$ is a random variable drawn from the normal distribution (mean 0, std 1), and which is uncontrollable by the miner (it is the result of the block hash). $const_1=1$, and $0<const_2,const_3<1$ should be in the order of $0.9$ and $0.1$ respectively; $M$ should be in the order of 100 as mentioned.

Hashrate trigger

Once the network reaches a meaningful hashrate, one that corresponds to operational expenses of $I=250k USD$ per week (say), the randomness should be eliminated, and then each block should mine a block reward of $rew(B) = const_3$ (const_3=1, say). This could be triggered automatically in consensus and requires no soft/hardfork.

Finality parameter

In phase 1, due to the expected low security, the finality parameter of the system should probably be set to be in the order of minutes rather than hours. In case of netsplits, the conflict should be resolved manually, which is a legitimate practice in a non-mainnet platform.

The post Kaspa launch plan (proposal) Pt-1 appeared first on Kaspa.