(This post is part of the Understanding GHOSTDAG series)

Your mental image of Bitcoin probably goes something like this: miners discover blocks either by creating them or hearing about them from other miners, whenever a miner discovers a block they broadcast it to their peers and start mining over it, if two competing blocks are created, the miners keep mining above the block they heard about first, unless the chain above the other block becomes longer, and then they switch. (If you don’t have any mental image of Bitcoin, and don’t feel like unpacking this condensed description, I recommend this video).

This description is completely reasonable but pretty clumsy. It requires considering several entities responding to a process that evolves through time. If you try to write a similar description to, say, how GHOST works, you will find two annoying things: first, the description becomes considerably more cumbersome, and second, most of it is identical to the description of Bitcoin. If you zoom in a bit, you will find that the only part of the description above that is actually unique to Bitcoin is this: “unless the chain above the other block becomes longer.”

The idea is this: the entire protocol completely relies on how conflicts are resolved. If we are guaranteed no conflicts, we do not need a protocol. That miners retransmit blocks, mine over the top of the chain they chose, and so on, is by no means trivial, but it is an assumption common to all blockchain algorithms. We will see how this assumption is justified a bit later.

The next conceptual step is to realize that, while conflicting blocks occur regularly, we can zoom in on how this choice is made. It makes sense to consider all blocks known to the miner at the time the choice was made. This set of blocks (that contains all previous conflicts) is not arranged in a chain, but rather in a tree. This leads us to the following:

Definition: a chain selection rule is an algorithm that is given a tree, and outputs a tip. We call this tip the selected tip, and the chain from this tip to the genesis the selected chain. Blocks outside the selected chain are called orphan blocks.

The blockchain paradigm transforms a chain-selection rule into the following consensus mechanism:

• Miners mine above the selected tip

• Whenever a miner discovers a new valid block (from mining or from a peer) they send it to their peers and recompute the selected tip

Since a chain of valid blocks can always be computed into a state, if the entire network agrees on the chain it also agrees on the state, and consensus is established. However, due to network delays, it is not true, and unreasonable to expect, that all nodes agree on the same chain.

This leads to introducing the notions of security and confirmation times. Roughly speaking, a chain selection rule is secure if the network agrees on all “sufficiently old” blocks, and the confirmation times describe how old is “sufficiently” old. We discuss both concepts in the following sections.

Breaking Ties

In the following, we will only describe chain selection rules up to ties. The heaviest chain rule, for example, does not tell us what to do when there are two tips whose selected chains are of the same weight. Consider, for example, the following input.

We haven’t introduced any actual chain selection rules yet, but it does not take a huge stretch of the imagination to see that the symmetry of $A$ and $B$ might pose an issue. Indeed, both rules we will see in the next post can not discriminate between $A$ and $B$. So how should this be resolved?

The idea is to have each node arbitrarily select either A or B. This splits the network temporarily, but in a good chain selection rule, this split will be resolved soon, usually after a single more block emerges.

While choosing a tie-breaking rule seems innocuous enough, a bad tie-breaking rule could have an adverse effect. The reason for that is, again, this subtle thing called “selfish mining” that we will touch upon in the next post. It is important that the tie-breaking rule is not gameable: that the block producer can't increase their chance of winning. So, for example, always choosing the block with the highest transaction volume is a bad choice, as an adversarial miner can always pay a large amount to themselves to gain an advantage.

Bitcoin breaks ties using the “first-seen rule”, it instructs its miners that in case of a tie they should mine over the block they saw first. Note that this is subjective as it depends on the order of block arrivals, which could differ for different nodes. Consequently, it is not enforceable: it is impossible to detect a miner deviating from this rule. There are some objections to this rule, such as arguing that it prefers better-connected nodes, giving them more power to perform a selfish mining attack. An alternative suggestion is to always choose the block with the lowest hash. This is essentially equivalent to randomizing in consensus the winner of the tie. The problem with that is opposite of the problem of the first-seen rule: it gives poorly connected nodes the same chances as highly connected nodes. There are many other suggestions for tie-breaking rules, and the best way is still under discussion. The only point I am trying to make here is that, like many things in blockchain theory, is that it is much subtler than it seems.

In the rest of the discussion, we assume that a good tie-breaking mechanism is in place and Ignore this issue altogether.

Deferred Block Data Validation*

The protocol above will validate any candidate block. This seems like a reasonable solution, but in practice, it can sometimes lead CPU attacks.

Imagine that I create a ton of blocks pointing directly to the Genesis block. Since the difficulty at Genesis was very low, I can do it for free. These blocks will never be a part of the selected chain, but their data will be validated according to the description above. If I create enough blocks this could easily suffocate nodes and create outages.

One approach to deal with such issues is deferred validation. The idea is that we “assume” all blocks with valid headers also have valid data, and we only validate the block if it ever happens to be on the selected chain. This way, blocks that will never be a part of the consensus will never be validated, either.

The disadvantage of this approach is that it makes the logic more complicated, and the most common solution seems to validate all blocks unless they split too early from the current selected chain. That is, we look for the splitting point, the latest block in the selected chain that is reachable from the new block, and if it is, say, two days older than the current tip, we defer the validation. This approach on the one hand protects us from spamming attacks (assuming the difficulty two days ago was already considerable), and on the other maintains simplicity.

This is the first example of privileges reserved for blockChains. In blockDAGs, this “protection” can be overridden: an attacker can create many cheap blocks pointing at Genesis, followed by a single block pointing at all these cheap blocks and the current selected tip. This will trigger the validation of all the cheap blocks.

Properly deferring block data validation in DAGs is a bit tricky but not impossible. We will review it in a future post.