Consensus Algorithms in Blockchains

Problems?

An overarching problem that cryptocurrencies must address is called the Byzantine General's Problem. The problem is that several Byzantine generals and their respective portions of the Byzantine army and have surrounded a city. They must decide in unison whether or not to attack. If some generals attack without the others, their siege will end in tragedy. The generals are usually separated by distance and have to pass messages to communicate.

The Byzantine General's Problem essentially simplifies down to: How do you prevent data from being corrupted or falsified in a network where there are nodes that have economic incentive to lie about the data?

Solutions

1. Proof of Work (PoW)

Proof of Work was the first blockchain consensus algorithm. Devised by Satoshi Nakamoto for use in the Bitcoin blockchain, we have PoW to thank for the massive mining operations and power consumption we see around the world.

PoW operates on the principle that it is expensive to add a tranche of new transactions to the blockchain, but very easy to check if the transactions are valid due to the transparent nature of the ledger. Miners collectively verify the entire blockchain, and transactions aren’t considered to be fully ‘confirmed’ until several new blocks have been added on top of them.

Bitcoin uses the SHA-256 Algorithm, which is one of many hashing programs that can hash like that.
For example, the SHA-256 hash of the word "apple" is
3a7bd3e2360a3d29eea436fcfb7e44c735d117c42d1c1835420b6b9942dd4f1b
yet the SHA-256 hash of "applf" (incrementing the 'e' to an 'f') is
75721aa556fe5e5c8dddd399a7ede960b73b619e96b0db1d7b7482ba3b74fd6f
These strings look super different, and that's intended—there's no quick or easy way to go from the first to the second.

If a malicious actor tries to spend coins fraudulently, those transactions will be ignored by the rest of the network. The only way that an attacker could commit such a fraud is to possess a huge amount of computational power, such that they could mine block after block, winning the proof of work competition time after time. This is known as a ‘51% attack’ due to the need to possess more than half of total network hashrate. The reality is that no miner has such a proportion of total hashing power. Thus attempting such a fraud is 1) extremely expensive (since it costs as much as the hardware and energy required, plus the opportunity cost of not supporting the valid version of the blockchain and receiving rewards in return) and 2) extremely unlikely to succeed. Consequently it is better (i.e. more profitable) for miners to remain honest.

2. Proof of Stake (PoS)

Proof of Stake (PoS) is similar to PoW except for the fact that participants "stake" their holdings in order to get a chance to mine a block. In PoS, participants still require computational power to participate, but the computational power is much less. Instead of using it to solve mathematical problems, participants only need to use computational power to prove how much they have at stake and a well designed random number generator will choose the winning participant.

The common argument against proof-of-stake is the Nothing at Stake problem. The concern is that since it costs validators almost no computational power to support a fork unlike PoW, validators could vote for both sides of every fork that happens. Forks in PoS could then be much more common than in PoW, which some people worry could harm the credibility of the currency.

Some people, like Ethereum supporters, think Proof of Stake is more efficient and fair compared to Proof of Work for reasons such as the above. Additionally, anyone could become a PoS miner technically given they had some amount of the coin, however getting into Bitcoin mining generally requires expensive hardware and commitment.

3. Delegated Proof of Stake (DPoS)

Delegated Proof of Stake (DPoS) is the fastest, most efficient, most decentralized, and most flexible consensus model available. DPoS leverages the power of stakeholder approval voting to resolve consensus issues in a fair and democratic way. All network parameters, from fee schedules to block intervals and transaction sizes, can be tuned via elected delegates. Deterministic selection of block producers allows transactions to be confirmed in an average of just 1 second. Perhaps most importantly, the consensus protocol is designed to protect all participants against unwanted regulatory interference.

DPoS is the brain-child of Daniel Larimer, and is actually very different from PoS. In DPoS, token hodlers don’t vote on the validity of the blocks themselves, but vote to elect delegates to do the validation on their behalf. There are generally between 21–100 elected delegates in a DPoS system. The delegates are shuffled periodically and given an order to deliver their blocks in. Having few delegates allows them to organize themselves efficiently and create designated time slots for each delegate to publish their block. If delegates continually miss their blocks or publish invalid transactions, the stakers vote them out and replace them with a better delegate.

In DPoS, miners can collaborate to make blocks instead of competing like in PoW and PoS. By partially centralizing the creation of blocks, DPoS is able to run orders of magnitude faster than most other consensus algorithms.

4. Byzantine Fault Tolerance

Practical Byzantine Fault Tolerance (PBFT): One of the first solutions to this problem was coined Practical Byzantine Fault Tolerance. Currently in use by Hyperledger Fabric, with few (< 20, after that things get a little ) pre-selected generals PBFT runs incredibly efficiently. Pros: High transaction throughput Cons: Centralized/permissioned

Federated Byzantine Agreement (FBA): FBA is another class of solutions to the Byzantine generals problem used by currencies like Stellar and Ripple. The general idea (heh), is that every Byzantine general, responsible for their own chain, sorts messages as they come in to establish truth. In Ripple the generals (validators) are pre-selected by the Ripple foundation. In Stellar, anyone can be a validator so you choose which validators to trust.

For its incredible throughput, low transaction cost, and network scalability, I believe the FBA class of consensus algorithms are the best we’ve discovered for distributed consensus.

5. Directed Acylic Graphs (DAGs)

DAGs are a form of consensus that doesn’t use the blockchain data structure and handles transactions mostly asynchronously. The big pro is theoretically infinite transactions per second, but DAGs have strengths and weaknesses like any other consensus.

Examples: Tangle, Hashgraph, Block-lattice, SPECTRE, etc.

DAGs have no mining, no blocks and no transaction fees. The security and consensus of the network is not divided among miners, validators, and users. Users of the network validate a number of old transactions (via proof of work) in order to be able to conduct one of their own. No one receives a reward and no one has to pay transaction fees. It also eliminates the need for a miner-centralization like in Bitcoins or in Ethereums network. All users of a given DAG-based ledger confirm transactions for one another rather than rely on outside “miners.” Hashgraph’s ledger doesn’t bundle transactions, while Bitcoin blockchain requires them to be packaged in 1 megabyte blocks, which, during days of heavy traffic, can take days of work by miners to confirm and record.

In spite of its promising future, it is way too early to say that hashgraph will replace blockchain and hashgraph is patented and not open source like blockchain. That's why not everyone is using DAGs for now.

Implementations, pros and cons of consensus algorithms

Name	Proof of Work	Proof of Stake	Delegated Proof of Stake	Byzantine Fault Tolerance	Directed Acylic graphs
Popular Examples	Bitcoin, Ethereum, Litecoin, Dogecoin, (Most of them)	Decred, Ethereum (soon), Peercoin	Steemit, EOS, BitShares	Hyperledger, Stellar, Dispatch, Ripple	Iota, Hashgraph, Raiblocks/Nano
Pros	Most well known	Attacks more expensive; More decentralized; Energy efficient	Cheap transactions; scalable; energy efficient	High throughput; low cost; scalable	Network Scalability; low cost
Cons	Slow throughput; killing the planet	Nothing at Stake	Partially centralized	Semi-trusted	Depends on implementation

References

https://hackernoon.com/a-hitchhikers-guide-to-consensus-algorithms-d81aae3eb0e3
https://steemit.com/bitcoin/@mooncryption/guide-proof-of-work-pow-vs-proof-of-stake-pos-vs-delegated-proof-of-stake-dpos
https://blockgeeks.com/guides/proof-of-work-vs-proof-of-stake/
https://seekingalpha.com/article/4132934-ethereums-casper-protocol-will-address-problems-proof-stake
https://bitshares.org/technology/delegated-proof-of-stake-consensus/
https://medium.com/@DebrajG/how-the-byzantine-general-sacked-the-castle-a-look-into-blockchain-370fe637502c
https://techstartups.com/2018/03/14/future-of-blockchain-will-hashgraph-make-blockchain-obsolete/