(This post is part of the Understanding GHOSTDAG series)

One way to define the contrast between safety and liveness is that the former means “nothing bad happens,” and the latter means “good things eventually happen.” The ”bad thing” is a double-spend, so what is the good thing? Arriving at a situation where a double-spend is very unlikely, of course.

In the previous post, we used $S(\alpha,\varepsilon)$ to denote the time a transaction has to be on the selected chain to gain a confidence of $\varepsilon$ against an $\alpha$ adversary. The liveness property concerns how long we would have to wait for that to happen. Say that a transaction indeed was on the selected chain for a period of $S(\alpha,\varepsilon)$, then we call $L(\alpha,\varepsilon)$ the (expected) time it took since the transaction was included in the blockchain and until this period started. All and all, the expected time it takes to gain confidence since inclusion is $L(\alpha,\varepsilon)+S(\alpha,\varepsilon)$.

Note that the period of time $L(\alpha.\varepsilon)$ is not the period of time since the transaction was included and until it was on the selected chain. It could be that during that time the selected chain changed several times between a chain that contains the transaction and a chain that does not, for example:

The time $L$ is the time before it was included in the selected chain for the last time before being accepted:

Liveness is defined like safety, just with $L$ instead of $S$…

The Antichain Condition*

…except it isn’t.

The definition provided above typically holds, and honestly provides all the intuition we need, but there are edge-cases we must consider if we want the definition to be truly accurate.

A transaction may wait forever to be in the selected chain, for example:

Worse yet, if there are two conflicting transactions, tx and tx’, then only one of them should be eventually accepted. Our definition does not allow this. The definition we gave for liveness is true only given that there are no conflicts and that the transaction tx appears on any possible selected chain.

We do not have the leisure to make the first assumption, namely that no contradiction appears. Any owner of a UTXO can easily create two conflicting transactions that spend it, so this scenario must be considered in the definition.

The second requirement, however, actually makes a lot of sense. Typically, when someone posts a transaction, it is transmitted to the entire network. Hence, if it does not conflict any other transaction and not starved in the mempool for some reason, it will eventually appear on any chain. If it is not in the selected chain from the point of view of some miner, she will include it in a future block. Hence, we can bake it into the definition.

A set of blocks is called an antichain if it satisfies that the chain from any tip goes through it exactly once:

We call a set of transactions unavoidable if the set of blocks that contain them is an antichain. For example, the two transactions tx and tx’ are unavoidable in the following setting:

With this term in hand, we can define liveness as the requirement that for any $\alpha,\varepsilon$ there exists some number $L(\alpha,\varepsilon)$ satisfying the same properties as $S(\alpha,\varepsilon)$ in the definition of safety, such that for any unavoidable set of transactions, the expected time the transaction appears on the selected chain and remains there for a period of at least $S(\alpha,\epsilon)$ is $L(\alpha,\varepsilon)$.

Phew! The good news is that, untypically, defining liveness in blockDAGs is easier.

Liveness of GHOST

We did not discuss the safety of GHOST, but it follows in a very similar way to that of HCR. What is interesting is that GHOST remains safe even in high block rates. Even if there are many orphans, they contribute to the weight of the selected chain, making it equally hard to revert. For that reason, it was initially believed that GHOST could solve the scalability problem.

However, when we try to increase the block rates too much we run into a balancing attack. An adversary can post two conflicting transactions, and then each time add weight to the losing side, causing the network to switch between the sides perpetually. The reason they could keep doing it indefinitely is because the high block rates create a situation where the network is divided between the two sides. This is in contrast to the clean chain we know from Bitcoin where the network has a lot of time to synchronize between blocks.

So what is the saving grace of GHOST? What is it good for if it has a liveness issue at high speeds?

The answer is that while GHOST can’t handle an arbitrary number of orphans, it still can handle some orphans. In HCR, we need to make the fraction of orphans negligible if we want most of the miner’s work to contribute to the security. In GHOST, we just need the orphan rates to be small enough so that we regularly get stretches of chains without orphans.

For example, consider this blocktree:

It just happened by chance that the honest network created four consecutive blocks chained together, gaining an advantage over the adversary in resolving the conflict between tx and tx’. In fact, we do not even have to have a chain. We don’t care if a tree was formed, if the entire tree is over the same side of the conflict, like here:

As long as there was a stretch of time during which sufficiently more blocks accumulated in the heaviest tree above one side of the conflict, it will remain resolved.

We stress that we must have the entire tree over the same branch of the conflict. In the drawing above, the adversary needs five blocks to shift the selected chain back to tx’. However, if the block tree would have looked like this:

then even though the last five blocks created by the honest network keep building over tx, they are split over two branches, so the adversary only needs three blocks to shift the selected chain back to tx’.

In conclusion, the block delays for Bitcoin must be very long, as the orphans degrade the protocol's safety. In GHOST, this is no longer the case, but increasing the rates too much causes liveness issues. Hence, GHOST allows a moderate amount of orphans that would have been prohibitive for HCR.

So if a typical HCR block tree looks like this:

a typical GHOST block tree would look more like this:

Yet, if they contain the same amount of block, the GHOST tree will actually be heavier despite having more orphans. This concludes how GHOST can improve dramatically on HCR in terms of throughput, but still falls short of solving the scalability problem in full.