A Crash Course on Consensus Protocols

Consensus Protocol is the backbone of any blockchain based decentralized application. Any publicly decentralized environment is always vulnerable to the adversary attacks from the malicious nodes. Thus any consensus protocol must have the sufficient resilience to withstand such attacks. For large scale public adoption they should be immune enough to handle the DDoS , Sybil and other cyber attacks . Additionally they must meet the Byzantine Fault Tolerance requirements.

There have been lots of research and experiments going on this subject for last few years . Many researchers have come up with the exciting solutions and innovative approaches to deal with the consensus problem.The academic curiosity of the last decades is taking shape in the form of real world applications. I have tried to briefly summaries these approaches at one place.

Proof of Work (PoW)

Implemented : Bitcoin and its Forks , Ethereum , Bytecoin 
Brief : Participating nodes must compete with each other to solve a cryptographic puzzle. This requires lots of computational efforts by the nodes. Once solved the solver publishes the solution which is validated by all other nodes. The race for for next solution is started by taking the reference from the previous solution. The linkage between these solutions creates a continuous chain called blockchain. Tempering with any transaction requires the re-writing of whole chain from that transaction onward , which is realistically not possible today. 
Pros : Secure , inbuild incentive for fair play , Cryptographically , matured PoW are less Vulnerable , Difficult to Fork 
Cons :High Latency , Difficult to scale , Wasteful work , prone to 51% attack , Environment impact , Quantum computing threat , Cartelization of Minors

Proof of Stake (PoS)

Implemented : First Peercoin in 2012 , Cardano(ADA) 
Brief : The concept behind Proof-of-Stake is that a block chain should be secured by those who have financial interest in the chain. This is a mining-less consensus mechanism. A leader or a slot leader is democratically elected based on the voting mechanism where all the nodes vote to choose a leader among themselves. Only Those who are holding the tokens can add the blocks in the blockchain. The chances of one’s getting selected for the block creation is directly proportional to the number of tokens possessed by the node. 
Pros : Low latency , High Scalability, 
Cons : “Nothing-at-Stake” problem , “Long Range Attacks”, Leads to Centralization, Leads to Oligarchy

Ethereum Community is contemplating to replace their PoW with the PoS mechanism in the phased manner . In this regard there are two main proposals which have been part of their road map to achieve this transition called Casper project.

Casper FFG (Friendly Finality Gadget)

Proposed by Vitalik Butarin , its hybrid version of PoS and PoW. Infact PoS is running in the top of the PoW . Validators of PoS will be placing the checkpoints after every 50 blocks (1 epoch) . These checkpoints will define the finality means any block after finality will be technically a Genesis block. This is a 51% resistant mechanism .

Casper TFG (The Friendly Ghost)

Proposed by Vlad Zamfir — Its security deposit based PoS mechanism . A validator has to put certain amount of ETH as a deposit to participate in the PoS. Any malicious attempt by the validator may invoke a smart contract (slashing) to confiscate/destroy the deposited amount. Thus the assumption is that the fear of penalty will maintain the validator’s honesty.

Few other Variants of PoS Consensus are below :

Tendermint

Invented by Jae Kwon . It has multi-round validation process . Validators take turns proposing blocks at each new block height. Tendermint requires 100% up time from a super-majority of its validators because if ⅓ or more are offline or partitioned then the network may halt. It prioritizes safety and finality over liveness. Meaning before adding a new block the previous block’s finality should be achieved first.
 You can learn more about Tendermint Here :

Other similar concepts like Honeybadger, Tezos and Ouroboros can be accessed here.

Delegated Proof of Stake (DPoS)

Invented by Dan Larimer , its first successful application is in Bitshares’ and Lisk. It is kind of representative democracy where stakeholders (token holders) vote for the validators. The validator with the most weight gets to become the delegate, validating the transaction and collecting the rewards for doing so.

LPoS (Leased Proof of Stake)

Small token holders are very unlikely be chosen for block creation . This means that many holders with small balances do not have any reward to run a node. It reduces the network size and restrict decentralization to only limited players. LPoS allows holders to lease their balances to staking nodes. Leased coins increase the ‘weight’ of the staking node, increasing its chances of being allowed to add a block of transactions to the blockchain. The rewards are shared proportionally with the leasers.

TPoS (Transactions as Proof of Stake)

Every transaction on the network carries with it an implicit Proof-of-Stake in the network. Transactions sender and receiver are the immediate stakeholders in the system . Every transaction will carry the hash of the previous block thus making the blockchain secure from the 51% attack . However many proposals of such consensus are available , but so far it has not achieved the industry level application acceptance .

Proof of Importance

Implemented in NEM (XEM) . Anyone with 10000 XEM vested from their account could become NEM’s harvester . These harvesters are assessed on the basis of the amount of the stake they vest and NEM assigns consensus addresses and importance scores to everyone on the network. Chance of successfully verifying the network is not solely dependent on how much you have at stake — rather, it is based on how many transactions you have made in the past, and the quality of those transactions.

Proof of Weight

Likelihood of discovering the next block depends on the certain weightage such as reputation , data storage, transaction history . NEM’s Proof of Importance is a kind of proof of Weight method.

Proof of Authority

The term was coined by Gavin Wood, co-founder of Ethereum and Parity Technologies. Transactions are validated by verified accounts (like admin) . This makes this a centralized consensus.

Proof of Elapsed Time(POET)

Implemented : used by the Hyperledger Sawtooth . 
Brief : This lottery-like algorithm was contributed by the Intel. Each participant waits for a random amount of time. First participant to finish waiting gets to be leader for the new block. It relies upon a special CPU instruction set called Intel Software Guard Extensions (SGX) which ensures that the each node is behaving as per the non-tampered timer running on their machine. 
Limitation : Relies on the specialized Intel hardware for attestation for the trust of the code.

dBFT (Delegated Byzantine Fault tolerance)

Implemented : NEO
Brief : Delegates are chosen by voting by the participants . A speaker is randomly assigned among the group of delegates. The proposal of the speaker is then voted by the delegates . The proposal (adding a block) is approved after 66% or more agree else re-voting happens. 
Advantage : Scalability
Limitation : Consensus halts if participation drops below 2/3 . 
More to learn on the reddit page below :

Proof of Capacity

Implemented : Burst coin
Brief : The ability to use empty space on your hard drive to mine the coins. A process called Plotting uses a very slow hash known as Shabal. Shabal hashes are hard to calculate, minors pre-compute them and store them on a hard drive. The more space you allocate the more chance of you having the required nonce on your hard drive. 
for more explanation click below :

Proof of Burn

Implemented : Slimcoin
Brief : The minors should prove that they the have burned some coins by sending them to verifiable unspendable addresses. The idea is to make the minor deplete their resources to earn the trust of the network.

PBFT (Practical Byzantine Fault tolerance)

Implemented : Hyperledger fabric
Brief : In Hyperledger it only applies to the ordering of transactions in Fabric. Its job is to ensure that every peer has the same list of transactions on its ledger. Few nodes per -selected by the membership service runs the validation process. 
Advantage : High transaction throughput
Limitation : Centralized/permissioned
for more explanation click below :

FBA (Federated Byzantine Agreement

Implemented : Stellar and Ripple 
Brief : Steller’s application of FBA called SCP (Stellor Consensus Protocol) allows each node to select their list of validator nodes called quorum slices . Many quorum slices make a quorum. In order to ensure that the no quorum slice is isolated from the network it applies the concept of quorum intersection. For example , if i am connecting as a node of on the Stellar then i will choose the real world trusted validators such as large bank or big corporation. This type of consensus is more effective in the case of Ripple where the membership on the ripple network is not open to the public.

Proof of Signature (PoSign)

Implemented : XTRABYTES (XBY)
Brief : PoSign employs a proprietary alert system named PULSE (Ping Unified Leger Synchronization Equalizer) to communicate with network nodes, thereby determining when a transaction block should be verified.
Its a patent algorithm so not much is known about the process of consensus . 
Check below link to learn on this :

Hashgraph

Implemented : Swirlds Hashgraph and Hedera Hashgraph
Brief : Its also called asynchronous Byzantine fault tolerance. It utilizes two technologies Gossip protocol and Virtual Voting. Gossip protocol means relaying information to the randomly chosen neighbors who in turn pass on this information to their neighbors . This process continues until whole network is aware of it. Further, by performing virtual voting, each node can determine if a transaction is valid based on whether it has over two-thirds of nodes in the network as witnesses. It runs on the assumption that less than one third of the nodes are malicious or at least two third nodes are honest nodes.
Learn more :

DAG (Directed Acyclic Graph)

Implemented : Tangle consensus used in IOTA is based on DAG other implementations are IoT Chain (ITC), and Byteball
Brief : In mathematics and computer science, a directed acyclic graph (DAG), is a finite directed graph with no directed cycles. That is, it consists of finitely many vertices and edges, with each edge directed from one vertex to another, such that there is no way to start at any vertex v and follow a consistently-directed sequence of edges that eventually loops back to v again. Equivalently, a DAG is a directed graph that has a topological ordering, a sequence of the vertices such that every edge is directed from earlier to later in the sequence.
In short , it is blockless directed graph data structure that uses a topological ordering. For example in IOTA if you want to send a transaction you must validate two previous transactions , this activity is counted as your contribution to the fee-less network.

Key feature of this consensus is that more the the number of transactions securer is the system . ne third of the transactions can control the network (~34% attack) .Thus for IOTA(tangle) there is a coordinator node in place which monitors each transaction till the network matures and popular.
 
 You can learn more about the DAG on the Bitcoin form as below :

Block Lattice

Implemented : Nano
Brief : Its more of a structure than a consensus protocol. Each account has one blockchain which is controlled by the account’s private keys, and each blockchain is replicated to all peers in the network. Balances are transferred between blockchains through send and receive blocks. This arrangement a called block lattice. On the top of it , To deal with the double spend Nano used the DPoS link to study more as below ;

SPECTRE

(Serialization of Proof-of-work Events: Confirming Transactions via
Recursive Elections )
Implemented : It is mix of PoW and PoS , still in the research labs. 
Brief : It focuses on building a directed acyclic graph (DAG) structure to allow concurrent and parallel block creation on the block DAG. The palatalization is exhibited by the separation between the mining and consensus portions of the protocol. 
To Learn more click below :

Phantom

This is again a proposed academic research so far. 
Brief : Phantom protocol confirms transactions with recursive voting of previous blocks. However, unlike SPECTRE, PHANTOM will use a “greedy algorithm” on a BlockDAG protocol to create a more linear block structure by “distinguishing between blocks mined properly by honest nodes and those mined by non-cooperating nodes that deviated from the DAG mining protocol.” Transactions issued by an honest user gain fast confirmations . Once a transaction is accepted it is a near-finality entry. 
To Learn more click below :

Thanks for reading , This is a work in progress post . Any new developments in the consensus frameworks will be subsequently updated here.