Before discussing the BlockDAG paradigm, we need to talk about DAGs. A directed acyclic graph is an abstract mathematical notion explored by mathematicians, computer scientists, and even physicists long before anyone ever thought of decentralized consensus.
Formal Definition
In Chapter 1B, we defined a (simple directed) graph as a bunch of vertices with arrows between them. Here are a few examples:
A cycle in a graph is any way to start traveling from one vertex, moving along the arrows in their direction, and ending up where you started. Technically, this is always possible with the trivial cycle, that is, by never leaving the starting point, so we add the requirement that a cycle must traverse at least one arrow. In the left graph above, there are two cycles:
Definition: A directed acyclic graph (DAG) is a (simple directed) graph with no cycles.
According to this definition, the following graph is a DAG:
However, this DAG is a bit weird: it has these two vertices A and B that are both “sinks”, you can get to them but you can never leave. Since we plan to use DAGs to model a ledger with a unique genesis block, we add the requirement that the DAG is rooted: it only has one sink (are DAGs with zero sinks possible?). We will always implicitly assume that all DAGs have a unique sink.
We have already seen an important family of DAGs called trees. In fact, any rooted DAG can be obtained from a tree by adding arrows in any way that does not create a circle, though the way to do it is not unique:
Conversely, given a (rooted) DAG, there are many ways to remove arrows (but not vertices) such that we are left with a rooted tree. Such trees are called spanning trees and they play an important role in this book.
Given a vertex in a DAG, most literature will refer to the blocks it is pointing it as its “children”. This makes sense since in most cases DAGs describes processes that evolve with time in the direction of the arrows (e.g. each vertex represents a quest in some computer game, and we draw arrow to each quest from all quests that must be completed before it is open). However, our case is a bit different. When we define the blockDAG paradigm, vertices will represent blocks and arrows will be pointers from newly created blocks to previously existing blocks. That is, the arrows go back in time. For that reason, in blockDAG literature we adopt an inverse standard in which vertices point to their parents.
The Anatomy of a DAG
Given a DAG $G$ and some vertex $B$ in this DAG, we can define a few sets that describe the “point of view” of $v$ in $G$.
Given two vertices in a DAG, $A$ and $B$, we say that $A$ is reachable from $B$ if we can get from $A$ to $B$ by following the arrows. For example, in the following DAG, $A$ is reachable from $B$ and $B’$, and $A’$ is reachable from $B’$, but $A’$ is not reachable from $B$:
The past of $B$ is the set of all blocks reachable from $B$, and the future of $B$ is the set of all blocks from which $B$ is reachable. The cone of $B$ is the union of its past and future, and the anticone is anything not in the cone. When it matters, we can refer to each of these sets as open (closed) to indicate that they (do not) include $B$ itself:
Note that in a rooted DAG, the anticone of the genesis $Anticone(G)$ is necessarily empty.
Topological Sorting
Given a DAG, a topological sorting is a list of its vertices that respects the arrows. That is, if $A$ is in $Past(B)$ then $A$ appears before $B$ in the list.
A nice and silly example is that of getting dressed. You obviously cannot put on your shoes before you put on socks, but you can put on your shirt before or after you put both (or in-between). The “dressing rules” DAG can look like this:
(in this drawing I went with the standard arrows go forward in time convention)
A topological sorting of this graph is one of many ways to properly get dressed, for example:
Underpants, socks, pants, belt, shirt, suspenders, shoes, hat
Socks, shirt, underpants, pants, hat, belt, suspenders, shoes
and so on.
Iteratively Computing Topological Sorting
There are many algorithms for computing topological sorting. We will now see one tailored to our preferences. Well, we will not exactly see one, but a layout for one. Filling in this layout is what GHOSTDAG is all about. Note that this algorithm assumes the DAG is rooted.
The iterative process goes through using a set called a merge set. This set is defined with respect to a selected parent. Given a block $B$ with a selected parent $B’$, we have that $B.MergeSet = B.Past \cap B’.Anticone$:
Assume we know how to do four tasks:
Select a selected tip
For each block, choose a selected parent
Given a vertex $B$, provide a topological sorting of $B.MergeSet$
Provide a topological sorting of $SelectedTip.AntiCone$
Then we can define the following topological sorting algorithm:
Let $B_1,\ldots,B_n$ such that $B_1$ is the genesis block, $B_n$ is the selected tip, and $B_{n-1}$ is the selected parent of $B_n$
For $i=1,\ldots\,n$:
Order $B_i.MergeSet$ and append it to the ordering
Append $B_i$ to the ordering
Order $B_n.AntiCone$ and append it to the ordering.
Visually, the algorithm looks like this:
This is by far not the simplest approach to topological sorting. However, it has the huge benefit of being incremental. It allows us to easily update the ordering as vertices are added on top (which is the case that interests us), and slight changes to the selected chain only induce slight changes to the ordering: if $B_n$ and $B_{n-1}$ are replaced for some reason by other vertices, we will not have to reorder anything from $B_{n-2}$ and below (note that $B.MergeSet$ is a subset of $B.Past$ and so it never changes, so the only way to change the ordering below a block on the selected chain is to have it removed from the selected chain).