# Agreeing on state of things: Consensus Protocol for Fork-choice After a new block has been authored and broadcasted within the network by the selected block author, the next problem is how to ensure that all participants in the network update their own copy of the state based on this new block. This updating needs to be done in a consistent way such that after a while, all participants in the network should arrive at the same current state. That is, participants need to come to a consensus on the current state of things. The protocol that makes this happen is the consensus protocol. In centralized systems, the consensus problem is trivial or nonexistent. The updating of the state is managed by the centralized system which operates in a controlled network environment, hence it is trivial to ensure that state update is consistent. Blockchain systems run in a peer-to-peer network environment. This means that messages are propagated in an ad-hoc manner. A consequence of this is that messages arrive at different parts of the network at different times. Messages could, and are often delivered out of order, messages could be conflicting or can even be bogus or malicious. Yet in this environment, nodes receiving authored blocks need to be able to pick the valid ones and use them to update their state. The consensus protocol needs to have the property that, if all honest participants run the protocol, they will reach a consensus and eventually arrive at the same state. There are two common aspects of coming to a consensus in most blockchain systems. Fork-choice and Finality. The first is referred to as the fork-choice rule which is the protocol for selecting conflicting blocks in order to determine the canonical one. The second aspect is called finality, this is the guarantee that once a block has been added as part of the canonical chain, it will always be part of the canonical chain and won’t be reverted. We look at fork-choice rule in this section. Finality will be discussed in next section. Given the peer-to-peer nature of the network in which blockchain systems operate, it is the case that a node can receive multiple blocks and hence would have to decide which one to pick to update its state. It is also possible that messages a node receives forms a tree. That is instead of only one block building on a preceding block to form a straight chain of blocks, there are multiple blocks building on preceding blocks, hence forming a tree of block chains. In such a scenario, the node also needs to decide which of the chains is the canonical chain that represents the true progression of the blockchain. This problem of having to make a choice of what is the right chain is fork choice, and the protocol that helps to resolve this is referred to as The fork choice rule. The fork-choice rule in consensus protocol is a very essential part of Blockchain systems. There have been various protocols researched, designed, and implemented to enable participating nodes in a blockchain system to reach consensus. In this guide, I give a quick overview of how the consensus protocol works in Bitcoin, Ethereum, and Polkadot. We start by looking at the fork-choice rule protocols and then follow with finality protocols. ### Consensus Protocol In Bitcoin for fork-choice The consensus protocol in Bitcoin is usually called the **Nakamoto consensus protocol**, and it builds on the concept of Proof Of Work used in selecting block authors. The Nakamoto consensus protocol states that the node should always pick the block or the longest chain which has had the highest amount of work done in building that chain. The question then is how is it possible to determine the chain which has had the highest amount of work invested into it? It is possible to tell the amount of work that was spent to produce a block based on the count of the preceding zeros in the hash that accompany the block. The logic is, the larger the preceding zeros, the smaller is the set of possible numbers that can be found that satisfies the requirement, and hence more guesses need to be made, which leads to more brute force, which leads to more work being done. As an example, if the space of possible hash can be seen as numbers from 0000 to 9999, but the required hash should have 3 preceding 0s. This means only 0001 till 0009 is valid. That means there exist only 9 answers out of 10,000 possibilities (0000 to 9999 inclusive). Compare this to a situation where the required hash should have only 1 preceding 0s. This means there exist 899 possible answers i.e. from 0100 to 0999. It is going to be harder to find 9 answers out of 10,000 possibilities compared to finding 899 out of 10,000 possibilities. This information then allows a node that is correctly following the protocol to tell which block or chain of blocks has had the highest amount of work invested in creating it. Once such a block or chain is identified, the node picks this as the correct one. If this protocol is run by all honest participants of the network, then they will eventually settle in the same state as they will all pick the chain with the highest proof of work. ### Consensus Protocol In Ethereum for fork-choice When Ethereum used Proof of Work its protocol for reaching consensus was similar to what exists in Blockchain, but since the switch to Proof of Stake, Ethereum now has a different fork-choice rule that it uses to reach consensus. The protocol is referred to as Latest Message Driven GHOST or LMD Ghost for short. Proof of Stake systems also works on the concept of attestations. That is, apart from having a validator node that produces blocks, the protocol also selects a subset of validator nodes that are responsible for casting votes that the block produced is valid. This vote is usually called attestations and the LMD GHOST fork-choice rule works based on these attestations. The general idea behind LMD GHOST is this: when faced with potential chains that fork at a block, to form a tree, always pick the branch with the highest number of attestations, counting from the leaf of the branches. An example of the LMD-GHOST fork-choice rule. In the image above, the number in each block is the weight based on the votes, with all attestations, i.e. votes in circles having weight 1 in our A validator presented with the fork at point F, will conclude the blue chain to be the canonical chain, even though there are branches with longer nodes. The selected branch won, even though it is not the longest chain, it is the heaviest chain based on the latest cumulative attestations. This is the fork-choice protocol for Ethereum for coming into consensus on the canonical chain and hence the current state. If all honest nodes follow this protocol, then eventually they all arrive at the same state. ### Consensus Protocol In Polkadot for fork-choice Polkadot does not have a standalone protocol for dealing with the problem of resolving forks and selecting the canonical chain. The mechanism used in selecting the canonical chain in Polkadot in the case of multiple options is based on a combination of BABE, its block production protocol, and another consensus-related concept called Finality. We look at finality next and then when discussing finality as it is handled in Polkadot we will see how combining it with BABE, the problem of fork choice is resolved. {% hint style="info" %} * Combining GHOST and Casper\ * Longest chain\ * Analysis of Nakamoto consensus\ {% endhint %} --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://geekabyte.gitbook.io/blockchain-protocol-development-guide/agreeing-on-state-of-things-consensus-protocol-for-fork-choice.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.