# LMD GHOST Fork Choice Algorithm

LMD GHOST(Latest Message Driven Greedy Heaviest Observed Sub-Tree) fork choice algorithm is part of the actual consensus mechanism used in ethereum. In a real world scenario, we don't always have block "chains" but have something called block "trees".


This algorithm lets a node decide which branch to follow. For example, we might have a scenario as shown below. How will the validator node decide which branch to follow? The node can follow **A<-B<-C<-E o**r it can follow **A<-B<-D<-G**.

The algorithm is divided into 2 parts.

## LMD *(Latest Message Driven)*
Messages, in this context, are the head block votes found in attestations. Every validator makes an attestation once per epoch. This attestation consists of the head vote the particluar validator in the form of `beacon_block_root`. This points to the root of the sub-tree that, according to the validator, should be part of the canonical chain.

pub struct AttestationData {
    pub slot: Slot,
    pub index: u64,

    // LMD GHOST vote
    pub beacon_block_root: Hash256,

    // FFG Vote
    pub source: Checkpoint,
    pub target: Checkpoint,
}

Typical attestation data

After receiving attestations, the node performs some basic checks to see if the attestation is valid. Only the most latest attestation is stored for each validator. That is why, it is called "Latest" Message Driven.

Only the most latest attestation is stored for each validator. That is why, it is called "Latest" Message Driven.

## GHOST *(Greedy Heaviest Observed Sub-Tree)*

Every node maintains its view of the world. This consists of

* The block tree, which is just a list of blocks.
* The list of latest messages from validators.
* The list of validator balances.

This part can further be broken down into 2 parts.

### **Get Weight**

The first things to do is to **calculate the weight of each branch in the block tree**. We basically sum up all votes for all the blocks in a particular branch.The weight of a vote is the balance of the validator making that vote. And the weight of the branch is the sum of all those votes.

### **Get Head**

Once we have the weight of each branch or subtree, the algorithm proceeds recursively. Given a block, we select the heaviest branch descending from it. We then repeat the process with the block at that branch's root. If a block has only one child, then the choice is obvious and there is no work to do. If two or more branches have equal weight, we arbitrarily choose the branch rooted at the child block with the highest block hash value. Eventually we will reach a block with no children. This is a leaf block and will be the output of the algorithm.

## Example
Lets try to understand all that with an example.


Lets say we have the above scenario and assume that a new block B is the new block. So, in order to find which branch the new block B will follow we apply the algorithm.(Bn here is the sum of weight votes for each block 'n')

* **First we find the weight of all branches in the block tree.**


Here I have calculated the weight of all branches in the block tree. **Note that:**

W1 = Be
W2 = Bc + W1 = Bc + Be
W5 = Bd + W3 + W4 = Bd + Bf + bg
[Basically Wb = Bk(some block) + sum of weight of all branches descending from it]

* **Now we try to find the head of the chain.**
To find the head, we apply the recursive process to greedily select the heaviest branch in the sub tree.


In the first step we choose the branch going from B->D as it is heavier thean the branch going from B->C. In the next step we will choose the branch D->G. So in the end **G->D->B** becomes the canonical chain.

## Rewards and Penalties

The open ecosystem of ethereum secures itself rewarding good behaviour and penalising wrong behaviour.

Validators are for proposing blocks that get included in canonical chain. So block proposers may propose multiple blocks in the hope that one of them gets included in the chain. But this behaviour is penalised by the protocol (***proposer slashing***). This algorithm comes in handy in these situations as identifies the for that has the most chances of being included in the canonical chain.

Similarly, validators are rewarded for producing attestations towards the head of the chain. Attestors run LMD GHOST to and vote for the head block they think is best.
Producing multiple attestations is also penalised(**attester slashing**).