(This post is part of the Understanding GHOSTDAG series)

Part 2: Setting the Stage for GHOSTDAG

We are finally set to face the actual GHOSTDAG algorithm, but before that, we should face back and look at the distance we have made so far. How marvelous it is that in a book dedicated to understanding GHOSTDAG, the GHOSTDAG protocol is only explained 35 thousand words in? That’s about as long as Hemingway’s The Old Man and the Sea.

The reason for that is, of course, that the purpose of the book is not just knowing what GHOSTDAG it, but also understanding it. This goes much deeper than just remembering the (eventually quite straightforward) rules of the protocol. We have developed tools that could be used to understand the properties of this protocol, define quantitative terms and apply them to our proposed algorithm to understand not just how it works, but what it achieves.

I could have presented the algorithm itself in the first page of the book, and, on a shallow level, most readers would have been able to follow. But that would have been a dry and technical feat, devoid of deep insights. I am hopeful that by approaching GHOSTDAG primed to appreciate it, you would have the same feeling of revelation I had when it first clicked for me.

We will explore the intricacies of GHOSTDAGs from top-to-bottom, following these steps:

• Computing the GHOSTDAG ordering given that we know how to pick blue blocks recursively.

• Picking the blue blocks, given that we can efficiently implement something called reachability queries

• Implementing reachability queries

• Explaining how GHOSTDAG handles reorgs

• Implementing the UTXO set over Kaspa and using it to incentivize rational miners to be honest

In the next chapter, we will explore the security properties of GHOSTDAG.

Recursive Algorithms

The GHOSTDAG algorithm is recursive, this means that it’s output on a given input is defined in terms of previous inputs. Complicated? An example should clear it up.

Most chances you have heard of the Fibonacci sequence $1,1,2,3,5,8,\ldots$. The $n$th Fibonnaci number $F_n$ is defined as follows:
$$F_n = \begin{cases}1 & n=1\\1 & n=2\\F_{n-1}+F_{n-2} & n>2\end{cases}$$

What should draw your eyes here is that $F_n$ is defined in terms of previous Fibonacci number.

Indeed, if we wanted to write a function that computes the Fibonacci number, we could write it like this:

def fibonacci(n):
  if n == 1:
    return 1
  if n == 2:
    return 2
  return fibonacci(n-1) + fibonacci(n-2)

This is a bad implementation, for many reasons (mostly because it is easy to find a closed formula $$F_n = \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^{n}\right]\text{,}$$ see here for example), but it works and demonstrates the point: the fibonacci function calls itself.

The GHOSTDAG protocol is given a block $B$ in a DAG, and has to compute $BluePast(B)$: that is, all the blocks in $Past(B)$ that $B$ thinks are blue. Recall that in GHOSTDAG, blocks can disagree on what blocks are blue. Indeed, it is possible that $C \in Past(B_1) \cap Past(B_2)$ and $C\in BluePast(B_1)$, yet $C\notin BluePast(B_2)$.

This seems highly problematic, since it means that to even track all this information, we have to store the entire blue set of each block, which would take huge amounts of space. Worse yet, we have to keep the entire history to compute the blue past of any incoming block.

That’s where recursion comes to the rescue! Instead of computing the entire past, we a block can inherit the blue past of one of its children, and only add to it whatever it thinks should be added.

Some Preparation

Before diving into the details, we need to set up some terminology. For each block we compute its blue past, denoted $B.BluePast$. We also often talk about the blue score of a block, $C.BlueScore$. The blue score of a block is just the size of its blue past.

Remark: in practice, we can’t just look at the size of the blue past. Since there is difficulty adjustment, we have to consider the weight of each blocks in terms of the amount of work required to create it, exactly like we had to for Bitcoin. Hence, in the actual implementation we use another metric called blue accumulated work (BAW).

Given any block $B$, we say that $C$ is the selected parent of $B$, and denote $C = B.SP$, if $C$ is the parent of $B$ with the highest blue score (if there are several possible choices for $C$, use a tie breaking rule, the Kaspa implementation goes by higher hash).

Given a block $B$, its merge set is the set of all blocks in its past that are not in its selected parents closed past: $$B.MergeSet = B.Past\setminus B.SP.\overline{Past}\text{.}$$

Note that all of the blocks in $B.MergeSet$ are also in $B.SP.AntiCone$ which means that we can color at most $k$ of them blue if we want the blue set of $B$ to be a $k$-cluster. This is very nice, because it puts a constant limit on how many blue blocks each block is adding, making the storage required for each block fixed.

Once GHOSTDAG computed what blocks it should add to the blue set, we can use that information to output a topological sorting, whereby making GHOSTDAG into an ordering rule. The way it does so is by following the template for iterative topological sorting we described in the last chapter: it computes a topological sorting of $MergeSet(B)$ that gives precedence to blue blocks, and appends it to the topological sorting of $Past(B)$.

The $k$ Parameter

We keep saying that GHOSTDAG returns a $k$-cluster, but we never specified what $k$ actually is. Other thing eerily missing from the discussion so far are the block rate and network delay. How is it possible that the operation of GHOSTDAG does not rely on the block rate and network delay? The answer is that it does, it is just encoded into the choice of $k$, along with another parameter $\delta$ called the confidence.

Remember that when we discussed blockChains we surmised that none is actually secure against $0.5$ attackers. In practice, there is only security against $(1-\delta)/2$ attackers for some $\delta$ that is hopefully small. In the blockChain world $\delta$ is implicit. We can observe the orphan rates and try to conclude what the actual security is (which is not too easy, given that orphans are not retransmitted to the entire network), but it is not dictated a-priori.

A small difference between Bitcoin and GHOSTDAG is that it makes the choice of $\delta$ explicit. We first define how much confidence we require from the protocol, and then, we ask ourselves how to choose $k$ such that the honest network produces a $k$-cluster $1-\delta$ of the time.

In other words, given $\delta$, as well as the block rate $\lambda$ and the network delay bound $D$, we ask ourselves: how large does $k$ has to be such that a network producing $\lambda$ blocks per second and transmitting them with a delay $D$ seconds will create more than $k$ parallel blocks at most $\delta$ of the time. There is an explicit formula for $k$, but it is not very pleasant:

$$k=\min\left\{ m\in\mathbb{N}\mid e^{-2D\lambda}\sum_{j=m+1}^{\infty}\frac{\left(2D\lambda\right)^{j}}{j!}<\delta\right\} \text{,}$$ the point is that we can easily compute $k$ from $\delta, D, \lambda$.

Remark: In practice, the correct choice of $k$ is even more complicated, because there is another phenomenon we have to bound that rises from a certain non-monotonocity property of GHOSTDAG. We will not get into this here.

The GHOSTDAG security proof establishes that if $k$ is chosen as we prescribed, as long as the actual network delay stays below $D$, the network is secure against $(1-\lambda)/2$ attackers. For example, for $\lambda = 1 Block/Sec$, $D = 10 Sec$ and $\delta = 0.05$ we get $k=18$. That is, assuming a latency bound of $10$ seconds we can operate at one block per second with $k=18$.

We will defer a deeper discussion of the confirmation times to a future post, but for now we mention that this $k$ is exactly the reason increasing block rates does not decrease confirmation times: the number of required confirmations grows with $k$, and $k$ grows with the block rate.

Deeper Look Into $k$*

The formula for $k$ is actually not so bad once you understand what it is all about.

In the appendix we examined the distribution of block creation and concluded that if we create a block once per $\lambda’$ seconds, then the probability to see $n$ blocks within $D’$ seconds is $$p_n = \mathbb{P}\left[Poi\left(\frac{D'}{\lambda'}\right)\right]=\frac{\left(D'/\lambda'\right)e^{-D'/\lambda'}}{n!}\text{.}$$

In the appendix, we did math like probability theorists, so we used $\lambda’$ to indicate the block delay whereas in the GHOSTDAG paper, and in this post so far, we used $\lambda$ for the block rate. This two values are obviously reciprocals of each other, that is $\lambda = 1/\lambda’$.

The time period $D’$ that we want to look at is not the network delay, but the round trip time, which is just another fancy name for the network delay twice. It’s the time it would take the network to learn of the new block and report back their own parallel blocks to the originator. We want to consider this back-propagation time as well, so we set $D’=2D$. The reshaped formula becomes: $$\mathbb{P}\left[Poi\left(2D\lambda\right)\right]=\frac{\left(2D\lambda\right)e^{-2D\lambda}}{n!}\text{.}$$

We want to make sure that the probability that at least $k$ blocks are generated in time $2D$ is at most $\delta$.

For any $m$ we have that the probability that at least $m$ blocks were created, is just the sum of the probabilities that exactly $j$ blocks were created, where $j$ goes over all values at least $m$. In other words, we want to find the least $m$ such that $$\sum_{j=m}^\infty p_j < \delta\text{.}$$

Since the values $p_j$ are probabilities of events that are disjoint (it is impossible that during the last minute, both exactly three blocks and exactly four blocks were created ) and exhaustive (the number of blocks created in the last minute must be some natural number, possibly zero), we get that $p_j\ge 0$ for any $k=0,1,\ldots$, and that $$\sum_{j=0}^\infty p_j = 1\text{,}$$ which imply together that $$\lim_{m\to\infty}\sum_{j=m}^{\infty}p_{j}=0$$ and in particular, that we can find such $m$.

Part 3: High-Level View of GHOSTDAG

We now deliberate on the recursive structure of GHOSTDAG.

Recall that GHOSTDAG has two purposes: determine what blocks are blue, and use the coloring to derive an ordering.

The recursive structure of the first task is quite simple: say that we have a function $ComputeBlueAntiCone(B)$ that is given a block $B$ and populates $B.BlueAntiCone$, then we can define that $B.BluePast = B.BlueAntiCone \cup B.SP.\overline{BluePast}$, with $Genesis.BluePast = \emptyset$ as the base of recursion. So for example, given that we know how to populate $B.BlueAntiCone$, a function that checks whether $C$ is in $B.BluePast$ could look like this:

inBluePast(C, B): #highly inefficient
  if C in B.BlueMergeSet:
    return True
  if B is Genesis:
    return False
  return inBluePast(C, B.SP)

This function is very straightforward:

• If $C$ is in $B.BlueMergeSet$ then $B$ thinks its blue so we return True.

• Otherwise, if $B$ is $Genesis$ then return False, since from the point of view of $Genesis$, no block but $Genesis$ is blue. (Note that if $C = Genesis$ then we have $C \in Genesis.BlueMergeSet$ (because every block is in its own blue merge set), so the previous line will return True.

• If none of the above hold, we need to dive deeper to answer the question, so we replace $B$ with $B.SP$ and repeat the process

The recursive nature is that we are allowed to switch $B$ with $B.SP$: since $B$ inherits $B.SP.BluePast$, if we find out that $B.SP$ thinks $C$ is blue, we can conclude that so does $B$. We can apply this deeper and deeper to $B.SP.SP$, $B.SP.SP.SP$ and so on until we find the blue merge set accommodating $C$, or hit $Genesis$.

This implementation might work, but it is extremely inefficient. The worst offense is that if $C$ happens to be red, the algorithm will make its way all the way down to genesis, regardless of how high $C$ is up the DAG. This means that the worst case for this code will increase linearly with time, which is very undesirable.

With some reflection we realize that we’ve actually done a lot of unnecessary work because we did not use all the information we had. In particular, for any block $B$ we can check if $C \in B.MergeSet$ and if it is, check if it is blue. This will prevent us from going below the first block on the selected chain of $B$ that knows of $C$. This would look something like this:

inBluePast(C, B): #somewhat inefficient
  if not C in B.Past:
    return False
  if C == B:
    return True
  if C in B.MergeSet:
    return (C in B.BlueMergeSet)
  if B is Genesis:
    return False
  return inBluePast(C, B.SP)

In this implementation, we first put a stop to the entire thing if $C$ in $B.Past$, as we should. This implies that the recursion will never go deeper than $C$, since it will terminate as soon as we hit a chain block that is parallel to $C$. This is still not a very good implementation, since there are edge cases that can cause it to run linearly long. For example, consider running inBluePast(C,B) on the following DAG:

There are better implementations still that can alleviate the problem, but we do not concern ourselves with them. Why not? Because they do not happen, either organically or maliciously. Checking whether a block is in the blue past of another block is not an operation that can be triggered by an adversary for arbitrary blocks, and in the honest majority setting, the depth difference between $B$ and $C$ is bound.

There is actually a much more important yet nuanced detail here, it is hiding in plain sight in the very first line of the function: if not C in B.Past. We are so used at this point to statements like “well, if $C$ is in the past of $B$ then…” that I presume most readers did not stop to ask themselves: “wait… how do we actually check this?” And the answer is that it is very hard to do correct. In my years on board the Kaspa wagon, I have talked to several teams who tried to implement GHOSTDAG but couldn’t make an implementation that’s even remotely adequate in terms of efficiency. A typical attempt at implementing GHOSTDAG chokes completely when trying to compute the ordering for a DAG of width $5$ and $k=18$, and the performance bottleneck is exactly that: checking whether one block is in the past of the other. We call such a check a reachability query. GHOSTDAG is very dense in reachability queries, with the number of such queries as high as $O(k^2)$ for each incoming block. Devising a clever way to implement them efficiently is key to efficiently implementing a DAG protocol.

In the next post, we will see how to compute blue merge sets reasonably efficiently given that we know how to implement efficient reachability queries, and further down the episode we explain how reachability queries are implemented.

Extracting the Topological Sorting

The block $B$ doesn’t only inherit the blue blocks in $B.SelectedParent.Past$, but also the topological sorting of $B.Past$. We can then compute a topological sorting of $B.MergeSet$ and append it to the inherited topological ordering to obtain an ordering of $B.Past$, as we explained in detail in the previous chapter.

There is actually a lot of freedom in choosing the ordering, the only property we require of the ordering is that if a blue block can appear before a red block then it has to. So how can we pick such an ordering?

A common mistake is to try and sort “layer by layer”: start with the blocks whose parents are all outside $B.MergeSet$, and place the blue ones before the red ones. Now take the blocks whose parents were already sorted and do the same thing. This will provide a topological sorting, but it might not give precedence to a blue block even though it could. For example consider this DAG:

The “layer-by-layer” approach will start with the layer $A,B,C,D$, since $D$ is red, it will place it last, say it sorted them as $A\prec B\prec C \prec D$, it would then move to the next layer (containing only $E$) and then to the last one (containing only $F$), and we’ll end up with the ordering $A\prec B\prec C\prec D\prec E\prec F$.

The problem with that is that $A\prec B\prec C\prec E\prec D\prec F$ is also a topoloical sorting, but one that prefers $E$ to $D$, as we want. The blue block $E$ is parallel to the red block $D$, and yet it appears after it in the ordering, deprived of its precedence simply because its parents are in the anticone.

A correct approach will be something like this: start with the blue blocks in the first layer, then go on to all blue blocks whose parents were already sorted, and so on. Keep doing so until you are stuck, that is, when all unsorted blue blocks have unsorted parents. Once you get stuck, add a single red block, and go back to working on blue blocks. Keep going until all blocks are sorted.

So in the example above, we would start with the blocks $A,B,C$ and sort them somehow. We would then notice that all of $E$’s parents are sorted, so we can add $E$ to the ordering. We are now stuck, as the only unsorted blue block is $F$, but $F$ has an unsorted parent $D$. So we add $D$ to the ordering and keep going. The resulting ordering is indeed possibly $A\prec B\prec C\prec E \prec D\prec F$. We ensured that no blue blocks are deprived their precedence by only adding red blocks when we absolutely have to.

This is not a very interesting example, and I recommend that you try to manually compute the ordering for more complicated cases, a few are provided in the exercises.

What makes the algorithm above ambiguous is the order we traverse the blocks. Different traversal orderings can provide one of many different topological orderings that all admit the required blue-precedence property. For example, the ordering $B\prec A\prec C\prec E \prec D\prec F$ is equally valid.

There is a very important nuance here: from a theoretical perspective, the security argument for GHOSTDAG will work for any ordering that fits the mould. However, when designing an actual network all of the above must be specified exactly. All implementations in the same network must follow the same ordering. Otherwise, nodes will not agree on which blocks are blue, and the network will split. In other words, if you want to implement your own network that uses the GHOSTDAG protocol, feel free to choose any suitable ordering. However, if you want to implement your own Kaspa client, you will have to comply with the exact ordering used in the Kaspa reference implementations.

Part 4: Picking Blue Blocks

We reduced computing GHOSTDAG to sampling blue blocks out of the merge set, which is the next problem on our list.

I have stated several times that “GHOSTDAG is a greedy algorithm”. Well, this is the greedy part. The way we choose the blocks in $B.BlueMergeSet$ is by traversing $B.MergeSet$ and, for each block, ask ourselves “can we color this block blue without destroying the $k$-cluster property?”. We do not ask ourselves “would we have managed to add more blocks if we traversed them in a different ordering?”.

This means that, at the highest level, computing $B.BlueMergeSet$ looks like this:

def computeBlueMergeSet(B):
  B.BlueMergeSet = {B.SelectedParent}
  for C in B.MergeSet:
    if canAdd(B,C):
       B.BlueMergeSet.add(C)

First note that we go over $B.MergeSet$ in some arbitrary order. We do not need to specify exactly what this order is. In the Kaspa implementation this freedom was leveraged to choose an ordering that makes implementation as efficient as possible.

Obviously, we encapsulated most of the heavy lifting into the canAdd function. The rest of this post will deal with figuring out this function.

Checking Blue Candidates

So to reiterate, we want to create a function canAdd(B, C) that is given a block $B$ and a block $C$ and tells us if $C$ can be added to $B.BlueMergeSet$ without violating the $k$-cluster property.

To do so, we need to do two checks. First, we need to check that there aren’t already $k$ blue blocks in $C.AntiCone$. Second, we need to check that if $D$ is a blue block in $C.AntiCone$ then there aren’t already $D$ blue blocks in $C.AntiCone$.

The first step is demonstrated here for $k=2$:

The block $C$ cannot be added because there are $k+1$ blue blocks in its anticone.

For the second step, consider this similar situation:

Here $A$ is the only blue block in $C.AntiCone$, so $C$ can be blue without violating the $k$-cluster property. However, since $C \in A.AntiCone$ and there are already blue blocks in $A.AntiCone$ other than $C$, adding $C$ will cause $A$ to violate the $k$-cluster property.

On the surface this doesn’t seem very complicated: we can traverse $B.AntiCone$ and for each block colored blue, keep track of how many blue blocks are already in its anticone, never letting their amount suppress $k$. Since there could be at most $k$ blue blocks, this will require at most $k^2$ reachability queries, and the complexity is fine, right?

So here’s the problem: we can’t just look inside the anticone. There are situations where we have to look into $B.SP.Past$. Consider this scenario:

Here (for $k=2$) we obviously are not allowed to color $C$ blue. However, we cannot learn this from $B.MergeSet$ alone.

Checking how many blue blocks are in $C.AntiCone$ is a reasonable task, it is the other way around that makes things cumbersome. So now we have to go through blue blocks in $B.SP.Past$ and check how much blue blocks they have in their anticone (including those outside $B.SP.Past$? That doesn’t bode well.

This becomes much easier if we break the work further into two steps: First, implement the function under the assumption that for any blue block $C \in B.Past we can magically know how many blue blocks are both in$B.BluePast$and in$C.AntiCone$. Second, find a nice way to track this quantity that does not rely on magic.

The template

Part 5: UTXO Over GHOSTDAG

(create cryptographic appendix where I introduce digital signatures, random oracles and hashes, and Merkle trees.

The UTXO Algebra

The Additional Merkle Hash

Delayed Coinbase Processing

Reorgs

Part 6: GHOSTDAG Complexity and the Reachability Problem*

Having defined our algorithm, the next logical step is to compute its complexity, and how it asymptotically grows with the various constants and conditions. We will do this more tightly further down the line, but a cursory discussion is due to present on of the more fascinating challenges in implementing GHOSTDAG.

The key observation is that one operation that repeats quite often is the following: given two blocks $B,C$ determine whether they are in each other’s anticones. We can rephrase the question a bit differently: given two blocks $B$ and $C$, we say that they are reachable if one of them can be reached from the other by only moving from blocks to their parents. It is clear that two blocks are reachable if and only if they are not in each other’s anticones. For this reason, we call each such operation a reachability query.

For new, assume that the sizes of all anticones are $O(k)$ (that is, there is some number $m$ that does not grow with $k$ such that anticones are never larger than $m\cdot k$). (In practice we cannot make this assumption, but it turns out we only need a weaker assumption that we can justify.) Note that the process of determining whether $C$ can be colored blue requires at most $k$ reachability queries (once for any block in $B.BlueAntiCone$