(This post is part of the Understanding GHOSTDAG series)

The blockChain paradigm reduces designing a proof-of-work consensus protocol to implementing a chain selection rule that is given a block tree and returns a tip.

In the blockDAG paradigm, the input is no longer a block tree but a blockDAG. The only difference between a block tree and a blockDAG is that in the latter, one block can point to many. I want to deliberate on that: blockDAG is not a protocol, it is not a technology, it is a problem that you solve to obtain `a consensus algorithm.

Given a blockDAG as input, what should be the output? We know that our goal is to keep all blocks, but our paradigm should provide a way to resolve conflicts. Both feats are achieved if instead of isolating a chain, we return a topological ordering. That is, the chain selection rule is replaced with an ordering rule.

Why DAGs?

Using DAGs is not just another design choice. There are deep reasons that DAGs are the correct choice. Or rather, DAGs are not a choice at all.

DAGs are the most general way there is to describe discrete causality. If we use any set of occurrences as our vertex set, and draw a arrows from any occurrence to all occurrences that directly effected it, we get a DAG. Any DAG can be obtained this way, making these ideas equivalent. (The word “discrete” reminds us that we are only dealing with an ever-growing yet finite list of occurrences, such as all the instances of a block being created. This is in contrast to continuous structures like, say, how special relativity describes the universe).

Assume each block points to all tips known to the miner at the time. Under this assumption, the DAG contains the most information possible about how interconnected miners are. This information is crucial for a fast responding algorithm. The more information we lose, the more time it takes us to build confidence with the information we kept.

How do we lose information? By imposing a structure. The blockChain paradigm loses information by only allowing each block to only point at one parent. We lose any and all information about what other blocks made their way to the miner before she produced her block. Parallel chain architectures are even worse in this regard: not only do they limit what blocks a given block can point to, but they also stall blocks until all of the relevant chains are ready, essentially wiping out information about latency across chains. Consequentially, the confirmation times of parallel chain architectures increase with the number of chains (logarithmically, but typically with abysmal constants).

If you were shown this block tree and asked which of the three tips is “better”, what would you choose?

Obviously, “better” is not well defined, but most people (as well as both chain selection rules we know) will choose A.

Now consider a similar scenario but in the blockDAG setting, and assume blocks created by honest miners point to all tips known to the miner when they were created. Consider the result is this DAG:

This draws a completely different picture! First of all, C is no longer a tip, so it is now only a competition between $A$ and $B$. Second, we note that while $A$ has the longest chain, there are more blocks “below” $B$.

One interpretation of this structure is that the chain starting from $A$ and the rest of the DAG were created in isolation of each other. And it seems that the part containing $B$ has more work put into it, so it is arguably the tip that represents the majority of the network. That information is lost when forcing the blocks to form a tree.

However, one should be careful with such conclusions. Say that indeed the chain $A$ belongs to an adversary, nothing prevents the adversary from borrowing work from the honest network. They could do something like this:

Here, the attackers block are colored red to indicate that they are withheld for the purpose of a double-spend attack. The point is that while the adversary created less blocks than the honest network, the past of $A$ still seems larger than the past of $B$. An attacker can easily take advantage of the DAG structure to mislead us. Preferring tips based on the size of their past alone seems (and as we’ll see a bit later, is) completely broken.

So this example taught us that we can learn a lot from DAGs, but we also be more careful of adversaries trying to mislead us. Our task is to find a way to use the information encoded into the DAG to find a way to gain confidence in a way which is both quick and secure. The GHOSTDAG approach is to appeal to a combinatorial structure called a k-cluster, which we will introduce further down the chapter.

Ordering Rules

An ordering rule is an algorithm that is given a DAG and outputs a topological ordering of this DAG:

Unlike a chain selection rule, the ordering rule will retain all blocks.

Recall that in the blockChain paradigm, each block must be consistent with the block they point to. Two conflicting transactions can never coexist on the same chain, so isolating a chain also removes all conflicts.

In the blockDAG paradigm, we still have the guarantee that a block cannot contradict its past. For example, this is impossible:

However, but this is not:

In the top figure, we can invalidate the block containing tx’ because the fact that tx appears in its past shows that the miner knew they were creating a contradiction. The scenario in the bottom figure, however, can happen organically. Sure, it requires the owner of some coin to try double-spending it, but we cannot blame any miner for accommodating any side of the conflict, since we can’t know from the graph if any of the miners cooperated with the adversary, or they just happened to hear of different sides of the conflict while constructing their blocks. Hence, such conflicts must be resolved in a way that does not punish the miner.

The ordering furnished by the blockDAG paradigm affords an easy solution: let the ordering decide. If the blocks containing tx appears before the block containing tx’ in the ordering, remove tx’. Otherwise, remove tx:

Note that only conflicting the transaction is removed, the rest of the transactions in the block remain.

This leads us to the following protocol:

• Miners point to all known tips

• Whenever a miner hears of a new block (from mining or from a peer) they send it to their peers and:

  • Apply the ordering rule

  • Go over all blocks in order and delete any transaction that contradicts a transaction that appears in previous blocks

At the end of the second step the miners will have a conflict free chain that they can treat the same as the selected chain obtained by the chain selection rule.

Keen readers might find this objectionable. How is this solution “fair” if one of the miners loses the fee? This is a very good question, and the answer is that in DAGs we need to be extra careful when choosing a tie-breaking rule. If the rule is not gameable, then both miners have the same chance of getting the fee, and over time, they will share the fees equally.

More annoying readers might have a stronger objection: what does a blockDAG even accomplish if parallel blocks repeat transaction? Aren’t you wasting all of the throughput you gained on redundancies? There are two things to say to this. First, the high parallelism in blockDAGs offers huge benefits besides throughput: confirmation times, better fee markets, and MEV resistance. Secondly, careful inspection shows that the amount of redundancy is very controllable, and that the throughput does increase linearly with the block rate. Understanding the effects of parallelism on fee markets is so central to the theory of blockDAGs, that part 3 of the book in its entirety will be devoted to this topic, and hopefully all your questions are answered. Another huge benefit of high BPS is its decentralizing effect on mining, which we will explore in part 5.

Objective vs. Subjective Ordering

The following nuance is probably the trickiest aspect of blockDAG protocols. I strongly advise the reader to read this section carefully, and make sure they feel comfortable with the terms introduced.

Given a block $B$, what best describes the ordering of $Past(B)$?

Well, that depends on the context. If we ask ourselves whether the transactions written in $B$ are consistent with its past, the ordering we must look at cannot rely on any information not available to $B$.

However, in the next chapter we will define the security by inspecting how long the prefix of topological sorting up to $B$ has gone without changing. This ordering obviously relies on the entire graph including blocks that are not in $Past(B)$.

To see why this is crucial, let us see an example. In this example, I assume there are four users Alice, Bob, Charlie, and Dave. We assume that initially only Alice and Charlie have any money, and Bob doesn’t. I will use the a denotation like $A\to C$ to denote a transaction where Alice pays all her money to Bob.

Say the DAG looks like this:

We first note that it is clear that the topological ordering must be $A,B,C,D$. Why? because if $C$ preceded $B$ then the transaction $A\to C$ would have preceded $A\to B$, and so, as far as $D$ knows, $B$ does not have any money and so the transaction $B\to D$ is invalid. This makes the block $D$ invalid.

However, what if the complete graph looks like this?

It is entirely possible that the ordering returned in this case is $A,C,B,E,D,F$. What happens then? Since $C$ precedes $B$ the transaction $A\to B$ is removed. Hence, the transaction $B\to D$ is also removed.

We see that as the blocks were added, the ordering up to $D$ changed from $A,B,C$ to $A,C,B,E$ and consequentially the set of transactions included from $B$ also changed.

To remove this ambiguity we introduce two definition

• The (subjective) ordering of $B$ is the one obtained by applying the ordering rule to $Past(B)$

• The (objective) ordering up to $B$ is the one obtained by applying the ordering rule to the entire graph and only taking the blocks that precede $B$

So in the example above, the ordering of $D$ is $A,B,C$ while the ordering up to $D$ is $A,C,B,E$.

This all culminates to the following super important rule-of-thumb:

1. When validating of $B$ we check that the transactions therein match the ordering of $B$, but

2. when deciding which transactions to include from $B$ we use the ordering up to $B$.