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 announced today a partnership with Flux (https:www.runonflux.io), a leading provider of decentralized cloud solutions, to launch Kaspa network nodes on their cloud infrastructure.  Launching the Kaspa network on Flux’s decentralized and reliable node infrastructure allows Kaspa to further decentralize and heighten the security & scale of our network.  Currently there are 13,500+ Flux nodes that are hosted around the world by the community, with redundancy as a key feature. If an instance goes down, one gets redeployed on another node in the network. They can be hosted anywhere from bare metal dedicated servers, to VPS’s, to home hosted solution.

Kaspa wants to thank Flux for supporting us in our mission to be the fastest, open-source, decentralized, and fully scalable Layer 1 digital ledger in the world.  Acceptance by Flux, a world-leading provider of decentralized Web3 infrastructure, serves to further validate the Kaspa mission and goals.

The post Kaspa Partners with Flux to Deploy Decentralized Kaspa Nodes appeared first on Kaspa.

Starting in July, the Kaspa development team, led by Michael Sutton, has undertaken an effort to rewrite Kaspad in Rust. This codebase rewrite will allow Kaspa to be in a “Space Code” system and reach maximal BPS and TPS through a high-performance well-designed implementation. The rust rewrite will take approximately 4-6 months to be completed and is fully funded by community member donations. To view the codebase foundation, progress on the project, or participate in the code-rewrite, please see our github page and reach out to us on Discord.

Background: In order to reach physical throughput limits and higher block rates, we believe Kaspa needs to be rewritten in a performance-oriented programming language and with a performance-oriented mindset. The current codebase carries on its back years of R&D efforts. Now that we have a proven, stable and working real-world and world-scale network, it is time to put the pieces back together in their purest form. As Kaspa seeks to be a world-leading financial system, the codebase should also transform to the ultimate level of quality and performance.

The main goals of such a rewrite:

1) Higher efficiency and tighter performance. The Rust programming language has the right balance for writing a system like Kaspad, with low-level memory management on the one hand (contrary to the currently used go-lang which is Garbage Collection based), and high expressiveness on the other hand (e.g., async-await etc.), not to mention the large and mature crypto-rust ecosystem.

2) Max BPS and TPS. Given the above some concrete numbers, I believe a goal of 32 BPS is definitely possible, and even 100 BPS is a reasonable target. With our current block-size this would translate to 6400 – 20000 TPS. But block-size can also theoretically be increased to find a sustainable amount of TPS, where the only limiting factor becomes the internet connection itself.

3) Simplified and modularized codebase. Rewriting will make the codebase more approachable for newcomers. My feeling is that the core of the current Kaspad codebase is hard to figure out for newcomers and is a bit obfuscated. Up until now, all code contributions to Kaspad from non-core members are still in the external realms of the codebase, such as the RPC API and related services.

4) Incorporation of pending features. New features and upgrades can be taken into consideration without the overhead of making many changes to an existing codebase. Examples include RPC API redesign; Archival nodes (and possibly P2P support for a subnet of such); Header Pruning; Smart-contract ground laying work, and more.

5) Documentation. Throughout the rewrite process, we can define and follow a standard for high-level documentation of the various sub-protocols and algorithms in the system. This can make it possible to outsource the effort of completing other technical writing to other members of the community, relieving the burden from developers alone.

The post Kaspa on RUST appeared first on Kaspa.