Being a Super Rookie in Blockchain — [Blockchain Overall] 3. Consensus Algorithm
Suitable for everyone to readFirst time visiting my story? Go check my previous story.
Hold tight if you googled ‘How to begin blockchain career,’ ‘How to start blockchain career,’ ‘Getting a job at blockchain,’ ‘Being a blockchain designer,’ ‘Being a blockchain financial architect,’ and ‘Being a blockchain developer.’
3. Consensus Algorithm
A ‘Consensus Algorithm’ is a manner of consensus between blockchain network participants. It is a part of a Blockchain Protocol.
Remind the Louis Network we made before. Ben is going to send 1 dollar to David. Ben will write the previous block’s hash value plus the sentence ‘Ben sent 1 dollar to David’ in a new block. Then, he will derive a new hash value from the content above and write it in the block. This entire process is called ‘Block Producing,’ ‘Block Creation,’ or ‘Block Proposal.’
Ben should copy the new block and give it to Louis Network’s participants, Louis, Tim, and Dan. Call this process ‘Block Propagation.’
3.1 Block Producing Rule
You must have a question if you are not dumb. Should only Ben create a new block to which Ben sends dollars to David? It is not essential.
Cause network participants comply with the network’s protocol, we can regulate that the participant who wants to send dollars should produce a new block. In this rule, Ben should be a network participant so that Ben can send dollars to David.
However, there was an assumption that block data and network participants are entirely independent. Because of this, there is an advantage; anyone can participate even though they don’t have money. It is a part of the ‘Louis Protocol.’
As a result, anyone in the blockchain network can produce a new block and propagate it to record that Ben sent 1 dollar to David. A problem,’ Who produces a new block?’ occurs at this point. The part of the blockchain protocol is the ‘Consensus Algorithm’ to solve the problem.
3.1.1 PoW
PoW is an abbreviation of ‘Proof of Work.’ It is the most famous consensus algorithm. BitCoin uses PoW, and past Ethereum used PoW. (Ethereum has changed its consensus algorithm to PoS)
Remind the Louis Network. When Ben wants to send 1 dollar to David, Ben can make a sentence(clearly ‘data’), ‘Ben sent 1 dollar to David’. Then send it to the network participant. (this process is not ‘propagation’ obviously.)
Then, participants Louis, Ben, Tim, and Dan put the previous block’s hash value plus the sentence, ‘Ben sent 1 dollar to David’, plus a specific number, into the hash function. The hash function will return a hash value. The new block can be propagated and accepted to the blockchain network if the hash value is lower than a particular value. You may not understand what the meaning is. Not bad. Let’s dive deep.
First, we must know the meaning of ‘What the hash value is lower than the other.’ Remind the hash value. It seems like ‘0x646e7c6e249e9a73fa8453099c7164fe713af91e.’ As we know from the first story of this series, a hash value is hexadecimal. A Hexadecimal is a kind of number. So we can compare two hexadecimal. We can easily compare if some zeros are in the head of the hexadecimal. 0x0000bcd is lower than 0x000abcd because there are four and three zeros each. You may know about the binary number. A binary number 11 is 2+1 = 3 in decimal number. A binary number 111 is 2²+2+1 = 7 in decimal number. We can add zeros at the beginning of the numbers, like 011 and 111. We can notice the former is lower than the latter.
Think from Louis’ point of view. He received the sentence, ‘Ben sent 1 dollar to David.’ Then Louis put [the previous block’s hash value] + [the received sentence] + [a specific number] into the hash function. The hash function will return a hash value. If the hash value is not lower than a particular value, retry the process with the changed specific number. We call the specific number ‘Nonce’ and the particular value ‘Target Value.’
The ‘Target Value’ seems like ‘0x000000000000ffffffffffffffffffff.’ Being lower than the target value means having more or equal zeros at the head than the target value. The number of zeros at the head is called ‘Difficulty.’ What does that mean? The number of digits of a hash value is fixed to 32. If the target value has five zeros, the number of cases of the hash value is 2^(32–5) = 2²⁷. Otherwise, if the target value has twenty zeros, the number of cases of the hash value is 2^(32–20) = 2¹². You can intuitively see finding a nonce is easier for the former than the latter. You got it. Difficulty 5 is easier than difficulty 20.
Finally, if Louis found a ‘Nonce’ that makes a hash value satisfy the ‘Difficulty,’ record [the previous block’s hash value], [received sentence], and [the Nonce] to a new block. Then propagate the block to the blockchain network.
A nonce is also hexadecimal. Remind the characteristic of the hash function. The derived hash value is entirely different if at least one single digit is changed. In this case, a hash value derived with any nonces will totally vary by nonces. So finding a nonce that complies with the ‘Difficulty’ is very hard.
We don’t need to find from 0 to get a nonce that complies with the difficulty. It can be started from any random number. Because the numbers lower than the target value are well distributed mathematically, the probabilities for finding a proper nonce are always the same wherever you start seeing.
If Dan finds a proper nonce, puts it in a new block, and propagates the block to the blockchain network, the others who received the block may stop to find a nonce and validate the block made by Dan.
Validating is to confirm whether the new block is valid or not. If it is invalid, the participants do not accept it and resume finding a nonce. We will look at how to validate blocks in a future story.
3.1.2 PoS
PoS is an abbreviation of ‘Proof of Staking.’ In September 2022, Ethereum changed its consensus algorithm from PoW to PoS. It seems to run well till now.
Remember, there are four network participants. Louis has 92 dollars, Ben has 5 dollars, Tim has 3 dollars, and Dan doesn’t have. Participants who want to create blocks at PoS need to stake their dollars. Suppose that all participants staked their whole dollars.
There is a promise to set a ‘Round’ as the duration of 100 block creations in the Louis Protocol. Participants who staked become block producer block by block. What block has to be produced by whom is represented following. Currently, there are three blocks made in the Louis Network, so the blocks that have numbers from 4 to 95 should be created by Louis. The blocks that have numbers from 96 to 100 should be created by Ben, and from 101 to 103 by Tim. Dan never makes blocks cause he didn’t stake any dollars.
What will happen if Ben creates a block when the other is allowed only to create a block? All participants know who can produce a block because of the network protocol. So if it happens, participants do not accept the block by Ben, and someone allowed to create a block includes a sentence, ‘Ben sent 2 dollars to Treasury,’ as a punishment.
3.1.3 DPoS
DPoS is an abbreviation of ‘Delegated Proof of Staking.’ Suppose Louis Network’s participants have grown to 1000, including Louis, Ben, Tim, and Dan. Louis cannot propagate a new block to the 999 participants directly. In another way, Louis propagates it to people who are near him, then they propagate it to other people. So if there are too many participants in a blockchain network, propagating blocks may take a long time.
We also should select participants who want to produce blocks in PoS. It is hard, too. DPoS arose to solve these problems.
Suppose Louis Network adopted DPoS, and Louis, Ben, Tim, and Dan insist they want to be a committee member. Committee members only can produce blocks in DPoS. All participants who have dollars in Louis Network can delegate their dollars to whom want to be committee members. We call this process ‘Delegate Staking.’
The delegated staked dollars are effective in such a way in PoS. For example, Louis, Ben, and Tim delegated their dollars themselves. Suppose Louis took delegate 102 dollars, Ben 242 dollars, Tim 124 dollars, and Dan 372 dollars. Staking ratios are the following. And they belong to how many blocks can create each.
3.2 Finality
Finality is an assurance or a guarantee that all past blocks are fixed and can not be modified or deleted. Some blockchains make a finality, and others guarantee a finality. Almost all PoW blockchains make a finality with a probability way. PoS blockchains guarantee Finality with a vote.
3.2.1 Probabilistic Finality
Two or more new blocks can be created in the PoW blockchain network. Imagine Louis Network using PoW. Internet speeds between Louis, Ben, Tim, and Dan vary. Two parts regulate the speed of the Internet. One of them is Latency. Suppose that block propagation will take time between participants, such following image.
Once Louis creates a block, sending it to Ben will take 0.3 seconds (=300ms) and Tim 0.2 seconds. Resending the received block received by Tim to Dan will take 0.25 seconds. As a result, propagating a new block to all participants will take 0.45 seconds, at least after finding a proper nonce.
If Louis found a proper nonce and Dan also found another nonce after 0.1 seconds later, Louis’ new block and Dan’s new block exist on the Louis Network.
At the time elapsed, 0.3 seconds from Louis found a proper nonce, Tim received a red block created by Louis, and Ben received a blue block created by Dan.
At the time elapsed 0.55 seconds from Louis found a proper nonce, red and blue blocks had been spread in Louis Network. In this situation, the blockchain shows a single chain becoming two branches. We call this situation ‘Fork.’
Focus on [Image 13]. As time passes, all participants will take all blocks on the blockchain network. Still, the following blocks created by someone should be connected with the block received first in the fork situation. If Tim found a proper nonce for the next block because he received the red block from Louis earlier than the blue block, he should connect a new block to the red block.
After time passed, the red block created by Tim would propagate to all participants.
When a new block connected to the blue block after a specific time passed, participants consensus that the chain with the red blocks is their canonical chain while abandoning the blue blocks.
Despite some blocks created by someone having been propagated, the blocks may become defeasance in the above consensus method. In other words, the Finality that ‘These blocks are definitive’ cannot be guaranteed.
When Tim created the fifth block, if Ben or Dan, who received the blue block first, found another proper nonce and created a new one, there would be two red blocks and two blue blocks on Louis Network. Then, after propagating the sixth block, the two red blocks or the two blue blocks will become defeasance.
Focus on the expression ‘make a finality with a probability way’ is used rather than ‘guarantee finality’ in PoW blockchains. In the above situation, there are always probabilities for making two blocks simultaneously ( before propagating completely) and continuously. But only the possibilities are such low. Probabilistic Finality is one of the characteristics of Bitcoin cause it uses PoW. Many call this consensus algorithm ‘Nakamoto Consensus,’ and Nakamoto found that the probability of making two forked chains of lengths of six blocks mathematically converges to zero. Because of it, passing six blocks should be if we want to say the block is finalized. Once you deposit or withdraw Bitcoin at the exchanges, you can see that the depositing or the withdrawal take some minutes. This duration is for waiting for the six blocks.
3.2.2 Deterministic Finality
Finality can be made by some blockchain network participants. We can see the Deterministic Finality characteristic at DPoS. Participants of the DPoS network should connect with each other. When a new block is created, all participants validate that the block producer is the one who is allowed to produce a new block and validate the contents and hash in the block. Then they can vote on whether it is valid or not. If there are positive votes for more than 2/3 participants, the block will be accepted by all network participants.
Imagine Louis created a block, Ben and Tim voted the block was good, but Dan voted the block was abnormal, like [Image 19].
3 of the network participants, Louis, Ben, and Tim, voted the block was good. Because 3/4 is more significant than 2/3, the block was accepted.
The whole process of accepting a new block to the blockchain network is called ‘Block Finalization.’ We can say that ‘Block Finality’ is guaranteed in the DPos network because new blocks become finalized before the subsequent blocks are created. We call this characteristic ‘Deterministic Finality.’
3.3 Chain Selection Rule
If a blockchain network that Finality is not guaranteed such that using PoW consensus, forked chains may occur. Therefore there should be a consensus algorithm on what chain should be accepted by the network participants.
3.3.1 Longest Chain Rule
We already applied Longest Chain Rule at ‘3.2.1 Probabilistic Finality.’
The above image shows that the network participants will accept the longest chain as the main chain. The chain consisting of red blocks may be selected in a situation like the above image.
However, because the Probabilistic Finality characteristic exists in PoW, each participant should decide what chain is longer rather than all participant do not decide it. Despite each participant creating blocks with self-decision, only one chain will finally be accepted by all participants because arduous efforts are needed to produce blocks in PoW.
Let’s see with an example. Return to the situation where the 3rd block has been propagated to Louis Network using PoW.
Suppose Louis and Dan found proper nonces for the 4th block simultaneously(not precisely the same time, but slightly the same). After 0.2 seconds had elapsed, Tim received the red block from Louis, and Ben received the blue block from Dan. Then the red and blue blocks propagated to all network participants. Finally, forked chains occurred.
As different from images of the previous stories, the blue blocks owned by Ben and Dan are shown upper than the red ones. It means the priority of chains of each network participant. Easily say that Louis and Tim will try to connect the following block to the red ones, and Ben and Dan will try to connect the following block to the blue ones.
If Ben finds a proper nonce for the 5th block and propagates a new block, the blue blocks might be appended to the chains of the participants, as shown in the above image. Then Louis and Tim raise the priority of the blue chain to connect the new blue block because the blue fork chain is the longest.
Therefore, Louis Network reached an amicable consensus because Louis, Tim, Ben, and Dan will try to connect new blocks to the blue chain!
Bitcoin adopted the ‘Longest Chain Rule,’ We call the Longest Chain Rule ‘GHOST.’ GHOST is an abbreviation of ‘Greedy Heaviest Object subTree.’
3.3.2 Modified GHOST Protocol
When Ethereum uses PoW, they adopted ‘Modified GHOST.’
Bitcoin protocol using PoW adjusts the difficulty to get around 10 minutes between block producing. Ethereum fixed the average block-producing time to 12 seconds. The probability of occurring forks becomes as higher as a shorter block-producing time. For a short block-producing time, the difficulty of PoW for Ethereum is easier than that of Bitcoin. So forks occur more than in Bitcoin in Ethereum.
In this situation, if Ethereum adopted GHOST just as Longest Chain Rule, the chain made by some attackers could be accepted to the blockchain network. So Ethereum adopted the ‘Modified GHOST Protocol.’
At just GHOST, ‘heaviest chain’ means ‘longest chain.’ At Modified GHOST, the meaning of the ‘heaviest chain’ changes to ‘chain having most blocks.’
Let’s dive deep into the difference between GHOST and Modified GHOST protocol.
Occurring forks like the above situation are possible in Ethereum. If the network belongs to the GHOST protocol, the bottom chain is composed of red blocks by the Longest Chain Rule. However, suppose it follows the Modified GHOST protocol. The chain with the most blocks of each fork level will be accepted.
See the first fork, blue and red blocks. At the blue block, there are 4 green, 1 orange, 1 sky blue, 2 yellow, and 2 purple blocks connected with the blue block. 4+1+1+2+2 = 10. The blue block has 10 blocks except itself. And the red block has 7 blocks. So, according to the Modified GHOST protocol, the blue block will be accepted as the canonical chain.
Afterward, the network participants can choose among the green, orange, and purple blocks. There are 3 blocks at the green block. There are 3 blocks at the orange block and 1 block at the purple block. As a result, the green and orange blocks will be chosen because they have the same number of blocks. The participants will make a consensus on whether the green or the orange chain is canonical after the next block creation.
Then, why should be the Modified GHOST protocol in Ethereum? An attacker may choose the one forked chain of his forgery blocks at just GHOST protocol. Suppose he has good computing power(that can be used to find a proper nonce). In that case, the attacker’s chain may be the longest because the other forked chain may have many additional forked chains.
Suppose the attacker’s computing power is 30% of the total computing power of the network participants. It means the number of forgery blocks that could be made by the attacker would be 30 in the situation the number of blocks made by entire participants is 100. Then, 70 blocks are regular, but the chains consisting of the 70 blocks have many forks. So the longest chain’s length might be lower than 30. Simply think that 3 forks occurred for the 70 blocks. The longest chain length is 70/3 (about 23) in the average case. It is lower than 30. But if we use the Modified GHOST protocol, don’t worry. The length of the longest chain is useless. The chains consisting of 70 blocks will be accepted as canonical chain because the chain has the most blocks.
If you have any questions, please follow my Twitter and tweet me.
Louis’ Twitter
New to trading? Try crypto trading bots or copy trading
