Monday, April 2, 2018

Basic Primer: Blockchain Consensus Protocol


Basic Primer: Blockchain Consensus Protocol guide. A blockchain is a decentralized peer-to-peer system with no central authority figure. While this creates a system that is devoid of corruption from a single source, it still creates a major problem.
  • How are any decisions made?
  • How does anything get done?
Think of a normal centralized organization.
All the decisions are taken by the leader or a board of decision makers. This isn’t possible in a blockchain because a blockchain has no “leader”. For the blockchain to make decisions, they need to come to a consensus using “consensus mechanisms”.
So, how do these consensus mechanisms work and why did we need them? What are some of the consensus mechanisms used in cryptocurrencies?

We will answer these questions in this guide. Basic Primer: Blockchain Consensus Protocol

Basic Primer: Blockchain Consensus Protocol
What are consensus mechanisms?
This is how Wikipedia defines consensus decision-making:

“Consensus decision-making is a group decision-making process in which group members develop, and agree to support a decision in the best interest of the whole. Consensus may be defined professionally as an acceptable resolution, one that can be supported, even if not the “favourite” of each individual. Consensus is defined by Merriam-Webster as, first, general agreement, and second, group solidarity of belief or sentiment.”

In simpler terms, consensus is a dynamic way of reaching agreement in a group. While voting just settles for a majority rule without any thought for the feelings and well-being of the minority, a consensus on the other hand makes sure that an agreement is reached which could benefit the entire group as a whole.
From a more idealistic point-of-view, Consensus can be used by a group of people scattered around the world to create a more equal and fair society.
A method by which consensus decision-making is achieved is called “consensus mechanism”.
So now what we have defined what a consensus is, let’s look at what the objectives of a consensus mechanism are (data taken from Wikipedia).
  • Agreement Seeking: A consensus mechanism should bring about as much agreement from the group as possible.
  • Collaborative: All the participants should aim to work together to achieve a result that puts the best interest of the group first.
  • Cooperative: All the participants shouldn’t put their own interests first and work as a team more than individuals.
  • Egalitarian: A group trying to achieve consensus should be as egalitarian as possible. What this basically means that each and every vote has equal weightage. One person’s vote can’t be more important than another’s.
  • Inclusive: As many people as possible should be involved in the consensus process. It shouldn’t be like normal voting where people don’t really feel like voting because they believe that their vote won’t have any weightage in the long run.
  • Participatory: The consensus mechanism should be such that everyone should actively participate in the the overall process.

Now that we have defined what consensus mechanisms are and what they should aim for, we need to think of the other elephant in the room.
Which consensus mechanisms should be used for an entity like blockchain.
Before bitcoin, there were loads of iterations of peer-to-peer decentralized currency systems which failed because they were unable to answer the biggest problem when it came to reaching a consensus. This problem is called “Byzantine Generals Problem”.

What is the Byzantine Generals Problem?

 Understanding Blockchain Consensus Protocols: Basic Guide
Image Courtesy: Medium
Ok so imagine that there is a group of Byzantine generals and they want to attack a city. They are facing two very distinct problems:
  • The generals and their armies are very far apart so centralized authority is impossible, which makes coordinated attack very tough.
  • The city has a huge army and the only way that they can win is if they all attack at once.

In order to make successful coordination the armies on the left of the castle send a messenger to the armies on the right of the castle with a message that says “ATTACK WEDNESDAY.” However, suppose the armies on the right are not prepared for the attack and say, “NO. ATTACK FRIDAY” and send back the messenger through the city back to the armies on the left.

This is where we face a problem.

A number of things can happen to the poor messenger. He could get captured, compromised, killed and replaced with another messenger by the city. This would lead to the armies getting tampered information which may result in an uncoordinated attack and defeat.
This has clear references to blockchain as well. The chain is a huge network; how can you possibly trust them? If you were sending someone 4 Ether from your wallet, how would you know for sure that someone in the network isn’t going to tamper with it and change 4 to 40 Ether?
What these generals need, is a consensus mechanism which can make sure that their army can actually attack as a unit despite all these setbacks.
We are now going to go through a list of consensus mechanisms which can solve the Byzantine Generals problem.

#1 Proof Of Work

Satoshi Nakamoto, Bitcoin’s creator, was able to bypass the problem by inventing the proof of work protocol.
First let’s see how it work in context of the Byzantine Generals problem.
Suppose the army on the left want to send a message called “ATTACK MONDAY” to the army on the right, they are going to follow certain steps.

  • Firstly, they will append a “nonce” to the original text. The nonce can be any random hexadecimal value.
  • After that, they hash the text appended with a nonce and see the result. Suppose, hypothetically speaking, the armies have decided to only share messages which, on hashing, gives a result which starts with 5 zeroes.

  • If the hash conditions are satisfied, they will send the messenger with the hash of the message. If not, then they will keep on changing the value of the nonce randomly until they get the desired result. This action is extremely tedious and time consuming and takes a lot of computation power.

  • If the messenger does get caught by the city and the message is tampered with, according to hash function properties, the hash itself will get drastically changed. If the generals on the right side, see that the hashed message is not starting with the required amount of 0s then they can simply call off the attack.

However, there is a possible loophole.

No hash function is 100% collision free. So what if the city gets the message, tampers with it and then accordingly change the nonce until they get the desired result which has the required number of 0s? This will be extremely time consuming but it is still possible. To counter this, the generals are going to use strength in numbers.
Suppose, instead of just one general on the left sending messages to one general on the right, there are 3 generals on the left who have to send a message to the ones on the right. In order to do that, they can make their own message and then hash the cumulative message and then append a nonce to the resulting hash and hash it again. This time, they want a message which starts with six 0s.
Obviously, this is going to be extremely time consuming, but this time, if the messenger does get caught by the city, the amount of time that they will take to tamper the cumulative message and then find the corresponding nonce for the hash will be infinitely more. It may even take years. So, eg. if instead of one messenger, the generals send multiple messengers, by the time the city is even halfway through the computation process they will get attacked and destroyed.
The generals on the right have it pretty easy. All they have to do is to append the message with the correct nonce that will be given to them, hash them, and see whether the hash matches or not. Hashing a string is very easy to do. That in essence is the process behind proof-of-work.

  • The process behind finding the nonce for the appropriate hash target should be extremely difficult and time consuming.
  • However, the process of checking the result to see if no malpractice has been committed should be very simple.

So, if we are to summarize how Proof Of Work Protocol works with the blockchain.

  • The miners solve cryptographic puzzles to “mine” a block in order to add to the blockchain.
  • This process requires immense amount of energy and computational usage. The puzzles have been designed in a way which makes it hard and taxing on the system.
  • When a miner solves the puzzle, they present their block to the network for verification.
  • Verifying whether the block belongs to the chain or not is an extremely simple process.

The proof-of-work mechanism definitely answered a lot of questions when it came to solving the Byzantine General’s Problem, but unfortunately there are some issues with proof-of-work.

  • First and foremost, proof of work is an extremely inefficient process because of the sheer amount of power and energy that it eats up.
  • People and organizations that can afford faster and more powerful ASICs usually have better chance of mining than the others.
  • As a result of this, bitcoin isn’t as decentralized as it wants to be. Let’s check the hashrate distribution graph: Understanding Blockchain Consensus Protocols: Basic Guide Image Credit: Blockchain.info
As you can see, ~65% of the hashrate is divided among 5 mining pools alone!
  • Theoretically speaking, these big mining pools can simply team up with each other and launch a 51% on the bitcoin network.

Notable Crypto That Uses This Protocol: Bitcoin

#2 Proof Of Stake


Ethereum is soon planning to move on from Proof of Work (POW) to Proof of Stake (POS).
Proof of stake will make the entire mining process virtual and replace miners with validators.
This is how the process will work:

  • The validators will have to lock up some of their coins as stake.
  • After that, they will start validating the blocks. Meaning, when they discover a block which they think can be added to the chain, they will validate it by placing a bet on it.
  • If the block gets appended, then the validators will get a reward proportionate to their bets.
 Understanding Blockchain Consensus Protocols: Basic Guide
As you can see, the POS protocol is a lot more resource-friendly than POW. In POW you NEED to waste a lot of resources to go along with the protocol, it is basically resource wastage for the sake of resource wastage.

The Biggest Roadblock to Proof of Stake

Ethereum developers always planned to eventually move on to proof of stake, that was always their plan. However, before they could do so, they had to address one of the biggest flaws of proof of stake(POS).
Consider this scenario for a moment:
 Understanding Blockchain Consensus Protocols: Basic Guide
Suppose we have a situation like the one above.  There is a main blue chain and a red chain which sort of branches from the main itself. What is there to stop a malicious miner from mining on the red blocks and force a hardfork?
In a proof-of-work(POW) system, this risk can be mitigated.
Suppose malicious miner Alice wants to mine on the red chain. Even if she dedicates all of her hash power to it, she won’t get any other miner to join her on the new chain. Everyone else will still continue to mine on the blue chain, because it is more profitable and risk-free to mine on the longer chain.
Now remember, POW is extremely expensive resource-wise.
It makes no sense for a miner to waste so much resource on a block that will be rejected by the network anyway. Hence chain splits are avoided in a proof of work system because of the amount of money that the attacker will have to waste.
However, things look a little different when you bring in POS.
If you are a validator, then you can simply put your money in both the red chain and blue chain without any fear of repercussion at all. No matter what happens, you will always win and have nothing to lose, despite how malicious your actions maybe.

This is called the “Nothing at Stake” problem.


In order to incorporate the POS consensus system, cryptocurrencies need to address this issue and Ethereum is going to do this in a very interesting way by adapting their Casper protocol.
Casper is the POS protocol that Ethereum has chosen to go with. While there has been an entire team busy creating it, Vlad Zamfir is often credited as being the “Face of Casper”.
 Understanding Blockchain Consensus Protocols: Basic Guide
Image Credit: Blocknomi.

So how is Casper different from other Proof of Stake protocols?

Casper has implemented a process by which they can punish all malicious elements. This is how POS under Casper would work:

  • The validators stake a portion of their Ethers as stake.
  • After that, they will start validating the blocks. Meaning, when they discover a block which they think can be added to the chain, they will validate it by placing a bet on it.
  • If the block gets appended, then the validators will get a reward proportionate to their bets.
  • However, if a validator acts in a malicious manner and tries to do a “nothing at stake”, they will immediately be reprimanded and all of their stake is going to get slashed.

As you can see, Casper is deigned to work in a trustless system and be more Byzantine Fault Tolerant.
Anyone who acts in a malicious/Byzantine manner will get immediately punished by having their stake slashed off. This is where it differs from most other POS protocols. Malicious elements have something to lose so it is impossible for there to be nothing at stake.
Flawlessly implementing Casper and Proof Of Stake will be critical if Ethereum plans to scale up.

Notable Crypto That Uses This Protocol: Ethereum (in the near future)

#3 Delegated Proof Of Stake


Now we come to an interesting form of Proof Of Stake called DPOS or Delegated Proof Of Stake. EOS is using this consensus mechanism to scale up to millions of transactions per second.
If they can actually pull it off, then they will have DPOS to thank.
Firstly, anyone who holds tokens on a blockchain integrated in the EOS software can select the block producers through a continuous approval voting system. Anyone can participate in the block producer election and they will be given an opportunity to produce blocks proportional to the total votes they receive relative to all other producers.

How does it work?


  • Blocks are produced in the rounds of 21.
  • At the start of every round 21 block producers are chosen. Top 20 are automatically chosen while the 21st one is chosen proportional to the number of their votes relative to the other producers.
  • The producers are then shuffled around using a pseudorandom number derived from the block time. This is done to ensure that a balance connectivity to all other producers is maintained.
  • To ensure that regular block production is maintained and that block time is kept to 3 seconds, producers are punished for not participating by being removed from consideration. A producer has to produce at least one block every 24 hours to be in consideration.
The DPOS system doesn’t experience a fork because instead of competing to find blocks, the producers will have to co-operate instead. In the event of a fork, the consensus switches automatically to the longest chain.

Confirming Transactions in DPOS?


A DPOS blockchain typically has 100% block producer participation. A transaction is usually confirmed within 1.5 seconds from the time of broadcast by a 99.9% certainty. In order to have absolute certainty over the validity of a transaction, a node need only to wait for 15/21 (i.e. a 2/3 majority) producers to arrive to a consensus.
So what happens in the event of a fork caused by negligence or malicious intent?
All the nodes will, by default, not switch to a fork which doesn’t include any blocks not finalized by 15/21 producers. This will stand true regardless of chain length. Each block must gain a 15/21 approval to be considered a part of the chain.
Because of the short block creation time, it is possible to warn nodes of whether they are in the major or minor chain within 9 seconds. The reason why that is so is simple. Remember, the average time elapsed between each block is 3 seconds.
If a node misses 2 consecutive blocks there is a 95% chance that they in a minority fork.
If a node misses 3 blocks, then there is a 99% chance of them being on a minority chain.

What is TAPOS?

Transaction As Proof Of Stake or TAPOS is a feature of the EOS software. Every transaction in the system is required to have the hash of the recent block header. This does the following:
  • Prevent transaction replay on different chains.
  • Signaling the network that a user and their stake is on a particular fork.
This prevents validators from acting maliciously on other chains.
Ok, so that sounds pretty fascinating.
You have a Proof-of-stake protocol which is fast and efficient.

Where is the catch?

For that, let’s bring in the insights of Ethereum co-founder Vitalik Buterin. According to him, the DPOS system fails the co-ordination game.
What is Co-ordination game theory?
Consider this matrix:

 Understanding Blockchain Consensus Protocols: Basic Guide
Now, if you see this matrix, there are two Nash Equilibria: (A,A) and (B,B), deviation from either of the state won’t benefit them. The idea of this game is how can you convince people to go from (A,A) to (B,B)? If there are a small group of people involved then that is relatively simple, you can simply coordinate via phone or emails. But, this changes when we are talking about a huge group of people.
The fundamental difference between prisoner’s dilemma and co-ordination problem is that in prisoner’s dilemma, both the players had to choose (B,B) because that was the choice that had the most payoff even though (A,A) is a morally better solution. In Co-ordination problem, it is not about the morality or the payoff, it is about the incentive for a person to go from one state to another. Why should a huge group of people change the way they do things?
A co-ordination game fails when only minority of the group change their state and the majority don’t and inversely, it is a success when majority of the group changes their state. Let’s see that with an example.
  • Suppose we want to change the language to a symbol based language. Eg:
  • Original statement: “Give me your number?”
  • New statement: “#?”

If only you speak using this language, it will be a failure because the majority won’t understand what you are talking about and you will be shunned from conversations aka the payoff for you is very low and you have no incentive to change.
However, if the majority of your society shifts to this language and use it exclusively, you will have to change your language otherwise you will never be able to fit in. Now the incentive for you to join is high.
The DPOS system could use the co-ordination game theory to its disadvantage. There could be a scenario where a certain situation is favoured by the block producers which are not in accordance with the the rest of the nodes.
Suppose the master nodes want to transition the chain from state A to state B. It could be a very hard task for them to help the entire chain do the same transition along with them especially if the other nodes are opposed to state B.
Only time will tell if EOS can properly and flawlessly integrate DPOS or not.

Notable Crypto That Uses This Protocol: EOS

#4 Delegated Byzantine Fault Tolerance (dBFT)


Now we come to Consensus mechanism of choice for NEO.
Imagine that there is a country “Blockgeeks” and this country has a lot of citizens. Each of these citizens would elect a Delegate to represent them and to make them happy. The job of these delegates is to pass laws that will make the citizens happy, if they are not good at their job then the citizens can simply vote for another delegate the next time.

So how do the delegates pass laws?

One of the delegates is randomly chosen as a speaker.
The Speaker then look at all the demands of the citizens and creates a law. They then calculate a “Happiness Factor” of these laws to see if the number is enough to satisfy the citizen’s needs or not. They then pass that down to the delegates.
The delegates then individually check the Speaker’s calculations. If the the speaker’s number matches the Delegate’s then they give their approval, if not then they give their disapproval.
66% of the delegates need to give their approval for the law to pass. If the majority is not sealed, then a new leader is chosen and the process starts again.
So, let’s see how this applies in the blockchain.
The citizens are whoever owns NEO tokens aka ordinary nodes.
Delegates are the bookkeeping nodes. In order to be a bookkeeping node you need to satisfy a certain amount of qualifications: having special equipment, dedicated internet connections and a certain amount of GAS (1000 according to basiccrypto’s article).

  • The “demands of the citizens” are basically the various transactions made by the token holders.
  • The “law” is the current block that is to be added to the blockchain.
  • The “happiness factor” is the hash of the current block.

Now, there are two cases where the one of the participants may act in a malicious manner. Let’s check it out:
Case #1: The Speaker is malicious
 Understanding Blockchain Consensus Protocols: Basic Guide
Image credit: basiccrypto Steemit article

In this case, the speaker has sent a malicious message B to two delegates and an accurate message to one.  This scenario can be easily mitigated because of the majority rule. The two delegates will see that their hash is not matching up with that of the speaker while one delegate will see that their hash matches up perfectly. However, 2 out of 3 will disapprove the proposal and consensus won’t be reached. The speaker will henceforth be removed.

Case 2: One of the delegates is malicious
 Understanding Blockchain Consensus Protocols: Basic Guide
Image credit: basiccrypto Steemit article

The speaker sends the correct message to all the delegates, however one of the delegates decides to act in a malicious manner and declares that their number isn’t matching up with the speaker’s.
However, since 2 out of the 3 delegates are non-malicious, they will approve the law which will then be passed since a 66% consensus has been reached.
So as can be seen, dBFT presents a very interesting form of consensus mechanism.

Notable Crypto That Uses This Protocol: NEO

These are 4 of the most common consensus mechanisms that are used in cryptocurrencies. However, there are some more that you can checkout which provide interesting alternatives. They are:
  • Proof Of Activity.
  • Proof Of Burn.
  • Proof Of Elapsed Time.
  • Proof Of Capacity.

Conclusion: Basic Primer: Blockchain Consensus Protocol

Without consensus mechanisms we wouldn’t have a Byzantine Fault Tolerant decentralized peer-to-peer system.
It is as simple as that. While, proof of work and proof of stake are definitely the more popular choices, there are newer mechanisms coming up every now and then. There is no “perfect” consensus mechanism, and chances are that there never will be, but it is interesting to see these newer cryptocurrencies coming out with their own protocols.

11 comments:

  1. Excellent Blog, I like your blog and It is very informative. Thank you
    ReactJs
    React Native

    ReplyDelete

  2. Activation of amazon Prime video can be done from either link amazon com code or www.primevideo.com/mytv. Both links amazon prime allow for activation and sign in to Amazon. Before logging in to amazon.com/mytv, the user must have a 6 Digit Amazon Activation Code. Amazon prime video subscription can start after you login to these link primevideo.com/mytv.


    amazon com code
    amazon code
    Play.google.com/redeem
    amazon com code
    Prime video mytv

    ReplyDelete
  3. What location would you choose if you had the power to make it disappear? Masters Study

    ReplyDelete
  4. Get Inspired at Coworking Spaces in Bangalore - Foster Collaboration and Innovation.

    ReplyDelete
  5. Excellent Blog, I like your blog and It is very informative. Thank you.
    dot-net-full-stack-developer-training-in-hyderabad

    ReplyDelete