As you have reached this far of reading my articles the first thing I wanna do is give a plaudit for you all. As I have promised in the last article ,"consensus in blockchains" will be the cynosure of this entire article. Before we instigate moving onto consensus in blockchains I would like to elucidate the fundamentals of consensus.
What is consensus
Simply consensus is a general agreement agreed upon by several users who operate in the same environment such that the state of a resource remains consistent throughout the system.
As we know quite a lot about distributed computing systems, I will put precisely a few words to explain contextually how consensus is achieved in those systems. As we know these distributed systems agree on a common memory and are connected through the memory bus. So its understandable that when multiple users operate on a shared resource (say for example a common variable) then any manipulations on this resource by more than one user tend to affect the unanimous state of the variable. For easier understanding if the user A tends to add 1 to the variable and the other user B subtracts 1 from the variable what will the resultant value in the variable. This is where the consensus comes into the play. As far as this scenario is concerned consensus helps in finding some way so that the users A and B operating on the shared resource will not affect the resultant value of the shared resource. With this ample knowledge about consensus we will now move onto acknowledging consensus in blockchains.
Before dealing with consensus in blockchain I would like to brief about the ever prominent Byzantine Generals Consensus Problem. Imagine several divisions of the army are camped outside an enemy city, each having its own commanding authority more formally an army general. In this scenario the generals can falsify the status of their troop and lead to the loss in a war. To avoid this problem voting is done among all the generals to decide whether to start war on the enemy or abandon it. This fault tolerance mechanism is a typical example for consensus.
Consensus in blockchain
To put in a precise way since too many users operate on a blockchain and the nodes of the blockchain simultaneously get updated by the transactions of the several users we need a general agreement to ensure the genuineness of the block or the corresponding node. Some of the common and simple consensus mechanisms in blockchain include,
- Proof of Work
- Proof of Stake
- Proof of Elapsed Time
- Simplified Byzantine Fault Tolerance
- Proof of Authority
- Proof of Property
Proof of Work
Kuldeski Security report 2016 describes the PoW consensus algorithm as,
"Proof of Work (PoW) is the outcome of a succesful mining process and although the proof is hard to create it is easy to verify."
Ofir Beigel descibes PoW in a very specific and precise manner as,
"guessing a combination to a lock is a proof to a challenge. It is very hard to produce this since you will need to guess many different combinations; but once produced it is easy to validate. Just enter the combination and see if the lock opens."
From all these great opinions one could easily figure out that in PoW the blockchain miners or simply the miners of a block would try to explore the cryptographic hash of the particular block. The exploration process is mathematically and computationally almost impossible since it requires a lot of time guessing the probable key to break into the node. For this purpose a huge computation power is also required. Say for instance if the cryptographic hash is of size 512 (usually SHA algorithms have definite size output for varied input messages and they are the most promising algorithms since they avoid birthday attack ) . So miners use supercomputers with high processing power in standby mode to break through into the cryptographic hash. Though PoW is criticized for computationally expensive mining it is the simplest method by which the transaction can be validated easily (high latency for transaction validation). PoW is skeptic to the "51% attack" which is the scenario of group of miners controlling more than 50% of the computing power in a network by which they can attack the blockchain by interfering in the process of recording new blocks. They can prevent other miners from completing blocks, theoretically allowing them to monopolize the mining of new blocks and earn all of the rewards.
Proof of Stake
This is more likely close to the PoW mechanism but the way to reach the end goal is completely different. There are no miners in a blockchain with PoS consensus whereas they are called as validators. They need not use huge computational resources to solve the block. Instead they have some of the ethers( the fuel for a ethereum blockchain) locked up as their own stake in the ecosystem. They bet those ethers by guessing where the new blocks will get added and the validator with more stake (ethers) is called for validation. Upon a correct guess they will recieve rewards (ethers) in proportion to their stake. There will be a validator pool where everybody with stake can join and only one forger with huge stake will be allowed to validate the transaction. This indeed reduces the risk of 51% attack as in PoW and also reduces the computational efforts that are required to mine the transactions. Also if the forger creates an invalid block his reputation and rewards will be lost.
Proof of Elapsed Time
This consensus mechanism is developed by Intel. This mechanism is a hybrid of both PoS and PoW meaning that the validator of a block is selected on a random and First Come First Serve (FCFS) basis. Also Hyperledger Framework has a component called Sawtooth which implements PoET as the consensus mechanism. In PoET each validator is given a random wait time and the elected leader will continue to create the next block on the chain. Sawtooth implementation of electing a leader is based on the following rule that,
"The validator with the shortest wait time for a particular transaction block is elected the leader".
Simplified Byzantine Fault Tolerance
It is a mere implementation of the practical Byzantine Fault tolerance algorithm. Unlike in a PoW algorithm a single validator bundles the proposed transactions and forms a new block. The validator is a known party here in this implementation since it works only in the permissioned Distributed Ledger Frameworks. Since only a minimum number of nodes can ratify the new block this implementation ensures the consensus of the chain. Given a system with 'f' number of faults atleast 2f+1 nodes should reach consensus with 3f+1 total nodes in the system. Say (f=1) for instance if the total number of nodes in the system is 4 atleast 3 nodes should reach the consensus for 1 fault. The practical implementation of this paradigm is ByzCoin and has a high latency for committing the transactions.
Proof of Authority
It is a consensus mechanism that can be used only in permissioned blockchains. The "authorities" are the set of designated nodes that are allowed to create new blocks and secure the ledger. So it is a consensus mechanism that functions based on the reputation of each node in the block. It is as same as that of PoS but the validators need not stack their transactions (ethers in the context of ethereum) instead they stack their reputation. It is a highly scalable system since it depends only on a limited number of validators whereas in a PoS there is a pool of validators in the system. Particularly in case of Supply Chain Management if blockchains are used for recording the transaction PoA is a better and reasonable solution since only the authoritative persons could validate the transactions in each block. Microsoft Azure implements PoA consensus for its service blockchain and leverages it to the companies eliminating the need for native currency like ethers since no mining is required.
The proof that the input addresses of a certain transaction own enough coins to fulfill the stated transaction is known as the proof of property. This is the baseline for PoP consensus mechanism. Unless like PoW and PoS it is a lightweight and scalable mechanism meaning that the users are able to extract a proof that the content of a certain node in this tree was not manipulated without presenting each and every data in the tree. All they need is to have their own cryptographic hash value and the hashes of all of the siblings and all parent nodes and their siblings up to the root node to prove the correctness of a given property. Unlike other PoW and PoS implementing blockchains it utilizes a different data structure called the Merkle Patricia Tree which is a hybrid of both Merkle and Patricia Trees. The main advantage of Patricia trees over the Merkle trees is that any new node inserted will not change the structure of the tree and hence the root hash is also not changed. This property helps users to refer to nodes in a previous tree without explicitly including them and it also avoids the manipulation of the calculated root hash value. The end resultant is that each address or node could be associated with a certain property that it owns and based on the property that is owned the node user will be permitted to add a new transaction to the block.
With this I hope that I have delivered sufficient information about the common consensus algorithms utilized in a blockchain enviroment. Await the next edition for more interesting and a simple hands-on work using Ethereum blockchains.