Gasper : Under the Hood

Let's learn about the consensus algorithm powering the Beacon Chain.

Gasper is a consensus protocol that participants of a proof-of-stake blockchain must follow in order to obtain a consensus history of their state, even when the network is unreliable or many validators are malicious. Gasper was designed keeping in mind the Beacon Chain’s sharding design, but it can also be used for a PoS blockchain with no sharding.

It is a combination of:

• Casper-FFG or Casper the Friendly Finality Gadget : It is a finality gadget (not a fully-specified protocol) that works on top of any blockchain, irrespective of whether it uses PoW or PoS).

• LMD GHOST or Latest Message Driven Greedy Heaviest Observed SubTree: It is a fork choice rule where participants attest to blocks to signal support for those blocks (like voting).

What Gasper does

Gasper sits atop any PoS blockchain where participants (validators) provide a stake as a security deposit that can be destroyed if they behave maliciously while proposing or validating blocks. It also specifies:

• how validators get rewarded.

• decide which blocks to accept or reject.

• which fork of the blockchain to build on.

Gasper is speedy and safe when the network is behaving normally, and remains safe even when the network is being attacked. This only becomes possible by using a hybrid of two mechanisms, and couldn’t have been achieved by using either of them alone.

FLP Impossibility

Fischer, Lynch, and Paterson (FLP) Impossibility is fundamental result in the distributed computation field. It states that it is impossible to simultaneously have these 3 properties in a system without making some unreasonable assumptions:

• Safety: the decisions made cannot be undone.

• Liveness: new decisions can be made.

• Full asynchrony: there is no upper bound on how long a message may take to get delivered.

If all the nodes in the system would always follow the protocol honestly, never crash and could communicate in a reliable manner– then consensus would be easy. But making these assumption would be unrealistic. When these assumptions get compromised, FLP Impossibility proves that at least one of the three– safety, liveness or full asynchrony– must be compromised.

Fork Choice Rules

Forks occur in a blockchain if the nodes publish two or more blocks that reference the same parent block (the same previous state). Forks might be accidental, for instance, when two blocks are published roughly at the same time. They can also be intentional– a malicious actor might attempt to create a fork to “remove” a payment from the popularly accepted chain. Nodes have to select only one of these blocks as canonical– conflicting blocks might contain mutually exclusive transactions. How do nodes make this choice? Enter “fork choice rule”.

Every blockchain provides a fork choice rule that nodes must follow. Fork choice rules are essential for the proper functioning of any blockchain. Fork choice rules determine which chain is to be widely accepted and, hence, which block producers must be rewarded. A poorly designed fork choice rule can quickly lead to unexpected, undesired behaviour by both users and block producers.

There are a few qualities a fork choice rule must have in order to be desirable. It must be open, accessible and easy to compute. It must also have limited reliance on external parties. Nodes should be able to follow the rule without having the rely on any “trusted” entity. The most crucial, perhaps, is reinforcing the economic incentives within the system as a whole.

PoW Ethereum uses the Longest Chain Rule or LCR. Under LCR, the canonical chain is the one with the highest total difficulty. Difficulty here is the target PoW value of each block. Since difficulty essentially acts as a proxy for resource expenditure, so the chain chosen by LCR generally follows whichever parties control the majority of the total current hash power.

One shortcoming of the LCR: it favours smaller groups with more hash power per participant over larger groups with the same total hash power. This originates from the fact that a group working on multiple blocks on the same chain can only produce a single block to be considered by the LCR. A large number of these blocks become ommer blocks (or uncle blocks) and are hence ignored by the LCR. The LCR only takes into consideration the “winning” block, as if only its producer had worked to extend the target chain.

How GHOSTs see forks

Greedy Heaviest Observed Subtree (GHOST), as the name suggests, selects the chain with the highest total difficulty. But when computing the PoW score for each block, GHOST sums the difficulty of all chains that stem from the block (not only the heaviest one). This ensures that a majority group will always outpace a minority one, even when there is poor coordination among the majority. This increases decentralization among miners.

GHOST is better than LCR because while an attacker might keep adding blocks to their own chain to make it the longest, GHOST will choose the chain with more work done on it. This reduces the chances of attacks during periods of high network latency, and also minimizes the depth of chain reorganisations.

GHOSTS adapted for PoS

A primitive GHOST implementation for PoS selects the head of the chain by choosing the “heaviest” fork, i.e. the fork with the most number of votes. Each time the network forks, GHOST chooses the fork where there are a greater number of latest messages supporting that block’s subtree– that is, votes supporting the blocks or one of its descendants. This is done until the algorithm reaches a leaf block, or a block with no children.

The Beacon Chain uses a variation of GHOST specifically designed for PoS, called LMD GHOST. The idea behind LMD GHOST is that only the latest vote made by each validator is taken into consideration when calculating the head of the chain. None of the votes made in the past are counted. This massively reduces the computation required when running GHOST as the number of plausible forks cannot be greater than the number of validators.

In accordance with the GHOST rules:

• validators can always try to add new blocks to the chain (liveness),

• at any point in the chain’s history (asynchronous).

So, the blockchain is live and fully asynchronous. But following the FLP Impossibility, it cannot be safe. The absence of safety gives birth to the possibility of chain reorgs of any depth. This is a problem.

A blockchain that is not safe is good for nothing– no decisions can be made and nobody would agree on the state of the chain. Casper-FFG comes to rescue.

The PBFT adaption comes to rescue

The classic Practical Byzantine Fault Tolerance was adopted to suit the crypto-economic scenario, and the result was Casper FFG. It has phases where nodes first signal that would like to agree on something (justification), and then agree that they saw each other agreeing (finalisation). Casper FFG favours safety over liveness when making decisions. The decisions are final, but no decisions might be made under poor network conditions.

Justification and finalisation do not take place every slot (a slot is the expected time it takes a block to be produced). They take place only every 32 slots, or an epoch. Validators first digitally sign that the agree with all the 32 blocks in an epoch. If more than two-thirds of the validators do this, the epoch is finalised and becomes a part of the blockchain forever.

FFG puts a pretty smart trick into play– it divides votes into two sub-votes. One is for the epoch that is attempting to be justified, and the other is for an earlier epoch waiting to be finalised. This saves a lot of extra work by reducing the amount of communication between nodes and, in turn, helps scale to millions of validators.

When two ghosts help each other

Beacon Chain’s consensus relies on:

• LMD GHOST to add new blocks and decide the head of the chain. GHOST allows the quick and efficient addition of blocks to the chain.

• Casper FFG to decide which blocks will permanently be a part of the chain, and which to reject. FFG provides safety by finalising epochs.

The two are fused together by running GHOST from the last finalised block, which is decided by FFG. The last finalised block will always be a part of the chain, which means that GHOST doesn’t have to consider earlier blocks.

Under normal conditions, the produced blocks are added to the head of the chain by GHOST when more than 2/3rds of the validators are voting on them. The blocks are then justified and finalised by FFG.

If the network is under attack, and a large number of validators go offline, then GHOST keeps adding new blocks. But GHOST is live, and not safe, it might change its mind about the head of the chain. This happens because nodes keep learning new information as blocks are continuously added to the chain.

FFG gives preference to safety over liveness, so it stops finalising blocks until the network recovers and validators can consistently vote again.