DAGs are hard. I want my chain back!

(This article explores one of the key concepts in Kaspa — A BlockDAG-based cryptocurrency.
If you are not at all familiar with the BlockDAG concept, I suggest you first read someone235’s excellent post introducing BlockDAGs)

The BlockChain is a complicated concept. I remember myself re-reading the Bitcoin whitepaper back in 2013, over and over again, taking more then a year to fully grasp how these things work.

Well, I’m sorry to say, but BlockDAGs are much harder.

Many assumptions that we take for granted in a blockchain are simply not true in a BlockDAG: Time is not linear. Who gets the fees for a transaction that was included in multiple blocks? How can a block get a reward, if its miner can’t know for sure whether it’s going to be red or blue? We can’t even assume that a transaction included in a block is valid.

All this complexity is hard to manage. It’s very easy to find a solution to one problem, while making all other problems even harder.
What if we had some sort of trick, that will make everything as “simple” as it is in Bitcoin? What if we could have our Chain back?

Yes we can!

Fortunately, GHOSTDAG, as well as any other conceivable PHANTOM algorithm, defines for every block B in the DAG a SelectedParent among B’s parents.

The mechanism of choosing said SelectedParent might differ between different PHANTOM algorithms, and is of no significance in our current context. As long as every block has a SelectedParent, we can construct a simple method to reduce the hard-to-reason-about BlockDAG, into something that closely resembles a relatively simple BlockChain.

Introducing the Selected-Parent-Chain

Since every block in the DAG has a SelectedParent, we can start from any block B and follow the SelectedParent path all the way down to the Genesis block.
We shall call this path B.SelectedParentChain.

Similarly, the Virtual block — an imaginary block that points to all the DAG’s tips, has a SelectedParentChain as well.
We shall call this chain the DAG’s SelectedParentChain, and sometimes, just The SelectedParentChain with a capital T (Sometimes also called the Virtual SelectedParentChain).

In this example, The SelectedParentChain is Virtual -> F -> E -> B -> Genesis

Now that we have defined The SelectedParentChain, lets see how we can make it resemble a BlockChain.

However, before doing that, we have to define yet another construction:

Accepted Blocks and Accepted Transactions

Let me side-step for a moment, and discuss how are UTXO-Sets calculated in Kaspa.

We define a block B’s MergeSet as all the blocks in B.Past, but not in B.SelectedParent.Past.

When we construct block B’s UTXOSet, we start from B.SelectedParent’s UTXOSet, then go over B’s blue MergeSet, and apply all blocks (and respectively— their transactions) in order, assuming those don’t break any rules.

We call this process “Accepting blocks” and “Accepting Transactions” respectively.
Any block or transaction applied this way will be “Accepted by B”, or “B is their Accepting Block”.

Note: Accepting transactions from Red blocks is somewhat complicated, and it’s a bit ambiguous whether a red block is “Accepted” or not. Said ambiguity should be covered in a future article.

In this example, A is accepting C, D and E. It’s not accepting G, because it’s in B’s past. Acceptance of B is ambiguous, since it’s red.

Getting to know the Selected-Parent-Chain

Finally! We can start exploiting the selected parent chain for gain and profit!

Reducing the complicated BlockDAG into a relatively simple BlockChain is now trivial:

1. The nodes in our chain are the same blocks that build up The DAG’s SelectedParentChain (The one starting with the Virtual block)
2. The transactions in every block in our chain, however, are not the ones included in said block.
   Rather, they are the transactions Accepted by said block.

That’s it! No conflicts possible. No double spends. No red blocks. Only valid transactions are allowed into our chain!

Now, lets try answer some of the hard questions in the beginning of this article, using the SelectedParentChain construction.

Coinbase, Block Rewards and Fees

In BlockChain-based cryptocurrencies, every block contains a Coinbase transaction, which pays the miner his block reward, as well as any fees applicable.

In BlockDAG-based cryptocurrencies such as Kaspa, no miner mining block B knows ahead of time whether B is going to be red or blue (and thus whether he deserves a block reward or not), and which transactions are going to be accepted (and thus, doesn’t know how much fees he deserves).

On the other hand, any miner that mines a block C that Accepts B, can answer those questions, at least from C’s point of view.

Therefore, any block in Kaspa contains a Coinbase transaction, similar to a BlockChain-based Coinbase transaction.
However, instead of paying rewards and fees to its own miner, the Coinbase transaction in Kaspa has predetermined outputs: one output per Blue block D in B’s MergeSet (or in other words, per block B Accepts), paying rewards and fees for D’s transactions.

To make the picture complete, however, we’ll have to add one more simple rule: when going over a B.MergeSet and Accepting transactions, the only Coinbase transaction Accepted, is B.SelectedParent’s coinbase.
This way, we guarantee that only Coinbases of SelectedParentChain blocks are Accepted, paying rewards and fees to all blocks in the DAG, exactly once per block and once per transaction.

Back to this example, only the coinbases of F, E, B and Genesis will be accepted, the coinbases for A, C, D and G are ignored. F’s coinbase will be paying fees and block rewards to A’s, D’s and E’s miners.

Further discussion and reading

If you want to discuss this blog post, or ask more about blockDAG, you are more than welcome to post a reply here or join Kaspa’s Discord Server or take a look at the GitHub repository for kaspad- Kasa’s first full node implementation . The Kaspa project is working on implementing fast and scalable money based on BlockDAGs.