A major challenge for blockchain technology has been ensuring that independent nodes reach a consensus on the correct blockchain, thereby agreeing on the correct transaction history. When faced with multiple forks of the chain, nodes must come to a local conclusion as to which one to follow. This algorithm is known as the fork choice rule.

The GHOST fork choice rule was introduced in a 2013 paper as a suggested modification of the original Bitcoin design, claiming to improve its transaction throughput. In time, modified versions of GHOST have become adopted by other blockchains, including Ethereum since 2022. These versions have been noted to support faster finality times, making GHOST a compelling choice for Nomos to incorporate into its Cryptarchia consensus protocol.

How GHOST works, its advantages compared to Bitcoin’s longest-chain rule, why the Nomos Team chose not to use GHOST for Cryptarchia, and why the longest-chain rule may be the best fork choice rule in its class are discussed in the remainder of this article.

Defining Blockchain Security

Before getting into the details of GHOST and its derivatives, it is important to have a proper definition of the security of a blockchain protocol. Such a definition is necessary to be able to compare the different fork choice rules, and to point out their strengths and weaknesses. The security of a consensus protocol is defined as its ability to maintain the basic properties of a blockchain in the face of adversarial activity. These are:

• Liveness: An honest transaction will be included in the blockchain without undue delay.
• Persistence: Once a transaction is in the blockchain for some time, it cannot be changed or removed.

In particular, modern blockchains operating in the permissionless setting are typically expected to be able to preserve their persistence and liveness in the event that some participants go offline or do not participate in the protocol. This scenario, which is meant to represent the way that a variety of participants with different network conditions may engage in validating a permissionless blockchain, is referred to as dynamic participation. Because Cryptarchia is designed to be a Proof of Stake (PoS) protocol, this article will focus on the security of GHOST in the PoS context.

What is GHOST?

Bitcoin’s Latency Problem

Bitcoin’s fork choice rule, which has remained unchanged since its introduction by Satoshi Nakamoto in 2009, is based on the properties of the Proof of Work (PoW) consensus mechanism. Because any adversary has less computational power than the combination of all the honest participants (as per Bitcoin’s security assumptions), it is infeasible for the adversary to build an alternative blockchain that is longer than the honest chain. Therefore, the longest blockchain available at any given moment can be assumed by participants to be the main, or canonical, chain. While there is a risk of a chain reorganisation - when a branch previously not on the canonical chain receives more blocks and thereby becomes the longest chain - this risk is negligible after a certain finality period.

The longest-chain rule has proven to be resilient and is now used in a variety of different blockchain contexts, including variants adapted for Proof of Stake (PoS) consensus. However, its security is dependent on blocks being dispersed across the network faster than new blocks can be created. Using large blocks that take longer to transmit, or shorter block times, will violate this security assumption and make blockchains that use the longest-chain rule susceptible to double-spend attacks. Therefore, using the longest-chain rule introduces an inherent limit to transaction throughput that depends on the network latency.

The intuition behind this assumption is that any adversarial chain must grow at a slower rate than the canonical chain in order for the consensus protocol to avoid accepting adversarial activity. However, if blocks are created faster than they can be broadcast (i.e. the protocol has high transaction throughput), most nodes will not have received the latest honest blocks in time to determine the most up-to-date canonical chain. Instead, nodes will attach blocks they create to the longest chain they know of, which is more likely to be a non-canonical branch due to the network delay. This results in more forks being created by honest participants, reducing the growth rate of the true longest chain. If this rate ever dips below the adversarial block production rate, an adversary would be able to construct a malicious longest chain even with a minority of the computational power.

The GHOST Rule

GHOST, short for Greedy Heaviest Observed SubTree, is a fork choice rule originally designed to address the throughput limitations of the longest-chain rule. In its basic form, GHOST is a recursive algorithm that begins from the first (”genesis”) block and chooses the branch that has the most blocks building off of it at every fork in the chain. Unlike the longest-chain rule, GHOST uses uncle blocks - valid blocks that were ultimately not included in the canonical chain - to determine the canonical chain. An example scenario illustrating the difference between the longest-chain rule and the GHOST rule is shown in Figure 1.

The reason GHOST takes uncle blocks into account is in order to obtain a better measure of computational work invested in a chain. Every block, whether or not it is included in the canonical chain, represents the decision of a node to build off of that block’s parent. Under the assumption that honest parties control most of the computational power, the chain extended by the most blocks can be safely assumed to be the honest one.

In fact, the authors of the GHOST paper prove that the above property holds even in protocols with high throughput - and a corresponding high rate of forks. Rather than "wasting" the security contributions of these uncle blocks, GHOST incorporates them into its calculation of the heaviest chain. This approach allows the network to maintain security even when a significant portion of blocks end up off the canonical chain. As a result, protocols using GHOST should (according to the paper’s authors) be able to support shorter block times and/or larger blocks than those using the longest-chain rule.

Security

While GHOST is considered secure in PoW, it is vulnerable to several basic attacks in the PoS context. One such attack is known as the avalanche attack, in which an attacker that wins block proposal rights proposes several blocks in the same slot, each extending the same honest block. This tree is hidden at first, and then released when the honest chain has reached a length equal to the number of concurrent adversarial blocks. These blocks shift the GHOST subtree weight to the adversarial tree, prompting honest proposers to build off of it, instead. This attack can be repeated several times by reusing some of the previously-created adversarial blocks to continue causing chain reorganisation events.

Actually, even in the PoW context, GHOST has been found to be less secure than the longest-chain Nakamoto consensus. This result is described in this 2024 paper and is discussed at the end of this article.

GHOST for PoS

Several variants of the original GHOST rule have been proposed or implemented since 2013 for use in PoS consensus protocols. Much of this work has focused on adapting GHOST to assign weight to branches based on temporary “votes”, or attestations, rather than a count of blocks. Nodes vote for a block that they claim is their “head of the chain”, and the branch carrying the greatest attestation weight is deemed to be canonical.

The use of attestations is what allows these GHOST variants to be used for PoS consensus protocols. If the combined number of blocks in a subtree is understood as a proxy for the total computational power invested in it, then using attestations as stake-weighted votes effectively adapts the GHOST rule to the PoS context. In both cases, the canonical chain is chosen based on the assumption that the majority of the consensus-making power (work or stake) is held by honest parties.

LMD GHOST (Ethereum)

Most notable among the GHOST derivatives is LMD GHOST. Short for Latest Message Driven GHOST, it was adopted by Ethereum as part of its Gasper consensus protocol - used for PoS Ethereum since 2022. In Gasper, validators are randomly divided into equal-size committees every epoch, with every committee assigned to one slot in the epoch. In each committee, one validator is chosen at every slot to propose a new block, and the other members broadcast an attestation indicating the head of their local chain. Each attestation has a weight based on the validator’s stake, and only the latest attestation from each validator is considered. While a dishonest validator may attest to an incorrect block or to several blocks at a time, this behaviour is punished by slashing the its stake.

To select the canonical chain, the LMD GHOST rule proceeds from the genesis block, recursively selecting the branch with the greatest attestation weight at every fork. An illustration of this process is depicted in Figure 2.

To make it more resilient against certain attacks, patches have been made to the LMD GHOST rule used on Ethereum. These include proposer boosting (where a current block proposal temporarily holds extra weight compared to other attestations), as well as equivocation discounting (ignoring multiple votes from the same validator in the same round).

Security

A significant weakness of LMD GHOST is the fact that an adversary can secretly accumulate attestations from older slots and release them all together to influence the fork choice rule in a given slot. This property can be used in attacks such as the balancing attack, a version of which was described in a 2022 paper. This attack can be initiated by an adversary who is selected as the block proposer for some slots. The adversary proposes two conflicting blocks in each of those slots, initially keeping them hidden from the other participants and producing equal amounts of attestations for each chain. Once they have amassed enough blocks in two competing chains, the adversaries reveal the chains and their attestations in a controlled way: half of the slot’s validator committee are sent one chain first, and the other half receives the other chain first. This ensures that the honest votes are split between the two conflicting blocks, since the attestations received second are discarded.

Even when a proposer adds a block to their view of the canonical chain and gains extra attestation weight for their block due to proposer boosting, it is possible for a weak adversary to create chains over several slots with greater attestation weight than the proposal weight. This is because the adversary, by hiding attestations and releasing them later, can effectively accumulate weight from previous slots and use it when needed. The authors of the paper note that a proposal weight can only overcome this effect if it can also overpower an entire slot committee, which defeats the purpose of having committees and attestations in the first place.

As a result of this and similar attacks, LMD GHOST (even with proposer boosting) cannot be considered secure in the dynamic participation setting.

Goldfish

Goldfish is a provably-secure consensus protocol that was designed in 2022 as an alternative to Gasper, and is considerably more secure in an environment with dynamic validator participation. Goldfish also features fast finality times - a major advantage over the slow finality of longest-chain consensus. The fork choice rule used in Goldfish is similar to LMD GHOST in that it organises rounds of attestations by validator committees in each slot. Validators decide on the canonical chain by selecting the branch with the most attestation weight at each fork. Goldfish’s reliance on frequent attestations allows it provide faster finality than longest-chain protocols, as there is more input from honest parties that can be used to determine the canonical chain.

Despite their similarities, Goldfish differs from LMD GHOST in two major respects:

1. The first distinctive feature of Goldfish is message buffering. Also known as view-merge, this process involves delaying the use of attestations received from other validators, while prioritising the attestations known to the block proposer in a slot. Since attestations are shared in a peer-to-peer manner, message buffering ensures that every validator who receives a block proposal instantly merges the proposer’s view of the attestations into their own, giving this view more weight compared to the delayed attestations received from other validators. While it has a similar effect to proposer boosting in LMD GHOST, message buffering provides resilience against malicious chain reorganisation and ensures that all honest voters in a slot will attest to a new honest block.
2. Goldfish also introduces vote expiry - attestations are only valid for one slot after they are created. This is unlike the Latest Message Driven approach, where an attestation never expires unless the validator that made it replaces it with another one. Vote expiry prevents adversaries from accumulating attestations across different slots and using them to create reorganisations.

The Goldfish fork choice rule involves three stages in every slot:

1. Propose: The block proposer selected for the slot incorporates its attestation buffer into its tree, and proposes a new block building on top of the canonical chain selected based only on the attestations from the previous slot.
2. Vote: All validators merge the proposer’s attestation tree into their own without delay. Validators in the slot’s committee submit votes for the canonical chain (which was just extended by the proposer) and are placed in every validator’s vote buffer.
3. Confirm: At the end of the epoch, each validator includes the attestations from their buffer into their attestation tree. Validators identify the canonical chain based only on the attestations from the current slot.

Security

Goldfish was designed to address the vulnerabilities of LMD GHOST to reorganisations by adversarial parties. Message buffering is an improvement of proposal boosting and ensures that validators can synchronise the attestation view of honest proposers with their own, avoiding the split views created when adversaries send different information to different committee members. Vote expiry, on the other hand, is used to protect against attestations being accumulated over time.

Despite this, Goldfish suffers from persistence problems if new votes are not received for even one slot. Since the older votes expire after one slot, any asynchrony event can result in catastrophic failure as the weights of all blocks drop to zero. Therefore, Goldfish is not considered a viable alternative to LMD GHOST for practical purposes.

RLMD-GHOST

Recent Latest Message Driven GHOST, or RLMD-GHOST, is a slight modification of Goldfish introduced in 2023. The key difference between it and its predecessor is that RLMD-GHOST allows for the use of not just the attestations from the previous slot, but all the attestations from the most recent slots within a set vote expiry period. Another difference is that every validator votes in every slot of RLMD-GHOST. This places RLMD-GHOST somewhat in between LMD GHOST and Goldfish, as measured at the speed by which attestations expire.

Security

Designed to be midway between LMD GHOST and Goldfish, RLMD-GHOST is secure in the dynamic participation setting (like Goldfish) and is asynchrony resilient (like LMD GHOST) within a set bound. Extending the vote expiry compared to Goldfish is what allows RLMD-GHOST to have better security for asynchrony events shorter than its vote expiry period. At the same time, having all validators vote in every slot prevents many of the attacks to which LMD GHOST is vulnerable, as attestation accumulation can only be accomplished when validator committees are used.

The biggest problem with RLMD-GHOST is that, due to its lack of committees, every validator votes in every slot. For a network with many validators, this process necessitates extensive message exchanging, which introduces limits to a blockchain protocol’s scalability.

Why Cryptarchia Doesn’t Use GHOST

When designing Cryptarchia, the Nomos Team deemed it important to create a protocol that is secure in the dynamic participation setting and retains its safety in unpredictable network conditions. Many attempts have been made to improve on the Nakamoto consensus by making various changes to its fork choice rule, which were studied by the Nomos Team for adaptation to the Nomos environment. Claims regarding the GHOST variants’ throughput advantages over the longest-chain rule, as well as their potential to enable very fast finality, were initially considered promising.

However, the vulnerability of the GHOST variants to serious attacks - and the tradeoff space between these vulnerabilities inherent to the design - made them less likely candidates for consideration. Furthermore, a 2024 paper showed that GHOST, despite demonstrating improvements when a deterministic tie-breaking rule is used, is still strictly less secure than the longest-chain rule. The effect of different tie-breaking rules on GHOST’s security for different rates of honest and adversarial block production are shown in the left chart in Figure 3, and a comparison between the best GHOST version and the longest-chain rule is shown in the right chart below. These charts show each protocol’s security regions - that is, the range of conditions under which security is maintained - with a greater security region indicating stronger security.

Conclusion

In summary, the GHOST fork choice rule and its derivatives offer some advantages in terms of throughput and fast finality, but they come with significant security vulnerabilities. The original GHOST rule was designed for PoW systems but has been adapted for PoS through variants like LMD GHOST, Goldfish, and RLMD-GHOST. While each variant attempts to address the shortcomings of its predecessors, they all operate within the same fundamental tradeoff space between security, scalability, and resilience to network conditions.

The LMD GHOST variant used by Ethereum's Gasper protocol is vulnerable to attestation accumulation attacks, while Goldfish overcomes this vulnerability at the cost of persistence during asynchrony. RLMD-GHOST attempts to balance these concerns but introduces scalability limitations due to its requirement for all validators to vote in every slot.

Given these considerations and recent research suggesting that GHOST is generally less secure than the longest-chain rule, the Nomos Team has decided not to implement GHOST or its variants in the Cryptarchia protocol. The team also reached the conclusion that there will likely never be any improvements to Nakamoto-style consensus for single-parent blockchain protocols - that is, protocols where blocks have only one parent each. If this is true, then any improvements on Nakamoto consensus will have to be found in DAG-based designs.

Sources and Further Reading

• Secure High-Rate Transaction Processing in Bitcoin (2013)
• Combining GHOST and Casper (2020)
• Goldfish: No More Attacks on Ethereum?! (2022)
• Recent Latest Message Driven GHOST: Balancing Dynamic Availability With Asynchrony Resilience (2023)
• Two Attacks On Proof-of-Stake GHOST/Ethereum (2022)
• A Tight Analysis of GHOST Consistency (2024)
• Upgrading Ethereum | 2.3.3 LMD GHOST