(This post is part of the Understanding GHOSTDAG series)

Armed with the blockChain paradigm, we can now easily manufacture many blockChain protocols. All we need to do is specify a chain selection rule, and voila! The blockchain paradigm will transform it into a protocol. The next natural step is to develop means to measure how good a blockChain protocol is. In other words, we need to define security notions for a blockChain.

We will do this in the next chapter. Before that, we present the most ubiquitous chain selection rules: the Heaviest Chain Rule and the GHOST. Equipped with these examples, we could probe our security definitions.

Heaviest Chain Rule

Satoshi Nakamoto introduced the heaviest chain rule (HCR) in a paper you possibly heard of. As the name suggests, HCR looks at all the tips and, for each tip, computes the weight of the chain going from this tip to genesis. What does “weight” mean? This means blocks with larger difficulty count more: HCR doesn’t choose the chain that contains the most blocks but the chain that requires the most work to create. If we ignore this for now and assume a constant hash rate, the heaviest chain and longest chain rules become equivalent.

GHOST

The greedy heaviest observed subtree (GHOST) rule, introduced by Yonatan Sompolinsky and Aviv Zohar in 2013, furnished a completely new approach for chain selection. While HCR looks at the past, GHOST looks at the future.

For any block $B$, the subtree rooted at $B$ is the set of all blocks that that $B$ can be reached from (including $B$ itself). We often say that a block $C$ is above $B$ to mean that it is in the subtree rooted at $B$.

The GHOST rule starts from the genesis block and works its way up greedily. At each block, the next block is the child with the heaviest subtree. This keeps going until a tip is reached, and that is the selected tip.

Let us follow an example:

Say GHOST is currently at block $A$. It examines the children $B_1$ and $B_2$ and proceeds to $B_1$, as it has a heavier tree above it. Similarly, GHOST will proceed to $C_2$, $D_2$ and eventually $E_1$.

Note that HCR would have selected the block $F_1$ instead, as it is the tip of the heaviest chain.

To conclude the discussion, there are a few common misconceptions about GHOST that need to go away. First, the purpose of GHOST is not to pay block rewards to so-called uncle blocks (blocks that are not on the selected chain). Ethereum indeed planned to add this feature to their GHOST implementation, but it is not a part of the original design. In fact, the GHOST paper explicitly recommends against it. Second, Ethereum used GHOST for a very short while before switching to a variation of the Inclusive protocol proposed by Lewenberg, Sompolinsky, and Zohar (this paper also provides a deep analysis of fee markets in blockDAGs, which will be the topic of part 3 of the book). Finally, and I cannot say this emphatically enough, GHOSTDAG is not a DAG version of GHOST. In fact, one could argue it is one of the first DAG protocols that is not a DAG version of GHOST, which is why it works. Protocols like Tangle 1.0 and Conflux actually fit into the “DAGified GHOSTDAG” rubric much better, whereas GHOSTDAG is actually a “DAGified HCR”. We will discuss this at great length when we introduce blockDAGs and GHOSTDAG, but I had to get this out of my system ASAP.

What’s that? Are you asking why call it GHOSTDAG and confuse anyone? Well, the answer is, obviously, because Yonatan Sompolinsky likes the movie Ghost Dog.

Why Heaviest and Not Longest?*

We stressed as we introduced the rules that they take into account the weight of blocks and not just their count. We justified it by saying that this way, we choose the chain with the most work put into it. Philosophically, this makes sense, but is it really crucial?

To convince you that it is, we describe a concrete attack that would be possible on Bitcoin if they used the longest chain rule. Naturally, this attack abuses the difficulty adjustment algorithm (DAA), a topic we will dive into in a future post. For now, we will introduce the few details we need about how difficulty adjustment works in Bitcoin.

Bitcoin adjusts its difficulty once every 2016 blocks. Each such 2016 block period is called an epoch. The time it takes to create 2016 blocks should take two weeks. The difficulty adjustment algorithm (DAA) looks at how long it “actually” took and adjusts the difficulty target accordingly. (I say “actually” in air quotes because this time is read off of timestamps, and these could be manipulated. But we’ll ignore that for now.) For example, if it only took a week the difficulty is doubled.

Knowing this, we already see one obvious attack: an adversary can start a new chain forking from a very early block where the difficulty is very low and never increase the difficulty. Quite fast, they will be able to create a much longer alternative chain while spending almost no work at all. Will this attack work? Actually, it would not. To keep the difficulty fixed, the attacker must use time stamps in the future. The DAA increases the difficulty because of consistently witnessing epochs less than two weeks long. If the adversarial chain insists that all epochs took two weeks, the timestamps would have to accumulate a steadily increasing gap. For illustration: this post was written 5708 days after the Bitcoin genesis block was created. Assuming an average block delay of 10 minutes, the blockchain today should have 821952 blocks. However, we are at block 8583200. That means the average block delay over Bitcoin‘s entire history is almost as low as nine minutes (due to increasing difficulty). In other words, an attacker making such an attack will find that the tip of his chain is about 250 days into the future. The Bitcoin nodes will ignore his chain until the clock catches up. By then, their chains will be longer (since the average block delay is lower).

However, this could be fixed: once the attacker has a much longer (but much lighter) chain, they could start creating blocks with constantly decreasing block delays (remember that the adversary can put whatever timestamp they want inside the block, regardless of how long it actually took to create it). This will close the gap at the cost of causing the difficulty to increase, but that is not really a problem since the adversary has made enough cheap blocks for the gap to close long before the honest network has more blocks.

The math is a bit contrived, but it is not difficult to show that such an attack requires unreasonable short times for unreasonably small attackers: a 1% attacker could revert the entire chain in less than a year, and a 25% attacker in a matter of a few weeks.