Blockchain Consensus

Blockchain is a distributed peer-to-peer technology. All nodes in the network have to agree on the state of chain and what are its valid blocks. Since there's no centralized control, and nodes cannot be trusted, reaching this agreement is not trivial. Every blockchain implementation must therefore define what's called a consensus algorithm to arrive at an agreement. This is also called consensus protocol.

Consensus is not exclusive to blockchain. It's a classical problem in distributed computer systems. In fact,

Any algorithm that relies on multiple processes maintaining common state relies on solving the consensus problem.

Discussion

  • What's the purpose of a blockchain consensus algorithm?

    A permissionless blockchain is open. Anyone can be a node and remain anonymous. It's therefore possible for a node to tamper transactions and include them in a new block. Thus, the blockchain can end up with what we call a fork. For example, one fork in the chain contains the tampered transaction while the other contains only valid transactions. The purpose of a consensus algorithm is to avoid such forks so that everyone agrees to a single version of truth.

    With a permissioned blockchain, although participating nodes are known and chosen, consensus is still required because we can't assume that the nodes are trustworthy.

    From the general viewpoint of distributed systems, consensus is a challenge when nodes are either faulty (gone rogue) or unable to communicate reliably. The former is called Byzantine Generals Problem and the latter is called Two Army Problem. A consensus algorithm must therefore be fault tolerant.

  • How does Bitcoin achieve consensus?

    Bitcoin uses Proof of Work (PoW) for consensus. Before a new block can be added to the chain, a node must perform an expensive computation to arrive at a valid hash value for the block. All other nodes receiving this block can then quickly verify that this block is indeed a valid one. A valid block is therefore proof that the node submitting it has done the necessary work.

    In fact, all nodes do this work in parallel but whoever is fastest (has most compute power) will win the race. The winning node is rewarded with bitcoins. For this reason, the work done by nodes is called mining and the nodes themselves are called miners. We can therefore say that consensus in Bitcoin network is achieved via mining.

    Consensus is achieved by a simple rule that only the longest fork will survive. In other words, the fork on which most compute power has been expended (PoW) will survive. If two blocks are mined at the same time, there will be a fork. PoW therefore intentionally slows the mining process so that forks don't happen faster than they are discarded by the network.

  • What are some possible attacks on blockchain?

    The idea of any attack is to prevent nodes from reaching consensus or mislead them to a wrong consensus. Here are a few common attacks:

    • Denial of Service (DoS): Sending nodes lots of transactions will prevent them from working on legitimate ones. Distributed DoS is a variant of this.
    • 51% Attack: If the attacker controls more than 50% of the nodes, then he can influence the consensus process. He can include modified transactions, cause a fork and make that fork the longest. Even with less than 50% controlling power, some attacks can happen with 50% success rate.
    • Double-Spend: Applicable to cryptocurrencies, this is a case when the same coin is used for multiple transactions.
    • Sybil Attack: This happens when a node assumes multiple identities and tries to pass itself off as multiple nodes in the network.
    • Cryptographic Attack: Quantum computing will bring computing power 100 million times that of conventional computers. This shifts the balance in favour of nodes with such power.
    • Byzantine Attack: A single or few nodes prevent consensus.

    Bitcoin-specific attacks are noted in a 2017 survey paper.

  • What are the different types of blockchain consensus algorithms out there?
    Comparing PoW with PoS. Source: Rosic 2018.
    Comparing PoW with PoS. Source: Rosic 2018.

    There are plenty of them and the following are some well-known ones:

    • Proof of Work (PoW): An expensive computation is required and this can be verified by other nodes. Nodes can remain anonymous and anyone can join. PoW is synonymous with mining. Systems that don't use PoW can be said to be doing virtual mining.
    • Proof of Stake (PoS): Stakeholders are those having coins or smart contracts on the blockchain. Only they can participate. Those with high stakes are chosen to validate new blocks. They are rewarded with coins. While coins are "mined" in PoW, they are "minted" in PoS. Blocks may still need to be signed off by other nodes before added to the chain.
    • Delegated Proof of Stake (DPoS): In PoS, those with large stakes can take control. In DPoS, delegated nodes represent the interests of smaller nodes.

    Further examples of consensus algorithms are proof-of-activity, proof-of-burn, proof-of-capacity, Transaction As Proof Of Stake (TAPOS), delegated Byzantine Fault Tolerance (dBFT), Practical Byzantine Fault Tolerance (PBFT), Federated Byzantine Agreement (FBA), and proof-of-weight.

  • Could you explain Intel's proposed Proof of Elapsed Time (PoET)?

    Proof-of-work wastes electricity to do mining. Essentially, the idea is to delay the creation of new blocks so that the network has enough time to avoid forking. Intel's idea is to mimic PoW by guaranteeing that each node has waited long enough before creating a new block, as if they were "doing work". They achieve this by building in their hardware chips a trusted execution environment (TEE) that adds this delay. It's claimed that proof-of-elapsed-time can scale to thousands of nodes.

    One criticism of this consensus is that nodes have to put their trust in Intel, who is supplying the chips. This is against the ethos of blockchains that aims to avoid centralization in an trustless environment.

  • Could you name the consensus algorithms used by some well-known blockchains?
    A chart from KPMG illustrating consensus algorithms used by some well-known blockchains. Source: Seibold and Samman 2016, fig. 2.
    A chart from KPMG illustrating consensus algorithms used by some well-known blockchains. Source: Seibold and Samman 2016, fig. 2.

    Bitcoin uses PoW and so does Ethereum, Litecoin and Dogecoin. Since PoW is computationally expensive, Ethereum plans to move to PoS sometime in 2018. Tendermint, BlackCoin and NXT use PoS. Peercoin and Decred use PoS while Bitshares, Steemit and EOS use DPoS.

    Hyperledger uses PBFT while Stellar and Ripple use FBA. MultiChain uses a variant of PBFT where there's only one validator per block and multiple validators work in round-robin fashion. Chinese platform NEO uses Delegated BFT.

    Proof-of-authority is used by POA.Network and Ethereum Kovan testnet. Proof-of-weight is used by Algorand, Filecoin and Chia.

  • What are some essential criteria of a blockchain consensus algorithm?
    Important criteria in any distributed ledger technology (DLT). Source: Wang 2016.
    Important criteria in any distributed ledger technology (DLT). Source: Wang 2016.

    The most important one is perhaps decentralization. In this aspect, Bitcoin's PoW does better than other consensus protocols. Consensus algorithms have to consider scalability, privacy, security and fault tolerance. Security implies resistance to attacks. Node identity management, consensus finality, correctness proofs and assumptions about network synchrony are other parameters to consider.

    The algorithm must scale with number of nodes/clients. Bitcoin's PoW can support thousands of nodes/clients but suffers in terms of performance. BFT can support thousands of clients at better performance but is limited to less than 20 nodes. Performance relates to throughput (transactions per second or tps) and latency. It must be efficient in terms of power consumption, or in general, consumption of any resource.

    Current protocols often involve tradeoffs. PoS is more energy efficient and achieves higher throughput than PoW but is more centralized and vulnerable to Byzantine faults. Prometheus and Matrix are newer algorithms that aim to combine the best of both PoW and PoS.
  • I've heard of "blockchain killers". What are these?

    PARSEC is a blockchain-less open source, fully asynchronous, leaderless algorithm for reaching consensus in the presence of Byzantine faults in an asynchronous network. Algorithm correctness has been proved provided less than a third of the participating nodes are faulty. This model matches an agreement with probability of one.

    Directed Acyclic Graph (DAG) is a graph of nodes with topological ordering and no loops. DAGs are inspiring the next generation of "blockchains". Iota, Hashgraph and Nano are examples of DAG.

    Tangle is the DAG consensus algorithm used by Iota. To generate an Iota transaction, a node has to validate two previous transactions it's received.

    Nano uses block-lattice as its structure. Every transaction is made of send block on the sender's chain and receive block on the receiver's chain.

    Hashgraph builds a directed graph of events rather the traditional chain of blocks. Consensus is via gossip: nodes tell neighbours about events, which are ordered by timestamps. Hashgraph is claimed to be fair, faster, provable and resistant to Byzantine attacks. It's also called Swirlds hashgraph consensus algorithm. It may not suit open public networks.

Milestones

1982

Researchers at the SRI International in California publish a paper titled "The Byzantine Generals Problem". The papers starts by stating that "reliable computer systems must handle malfunctioning components that give conflicting information to different parts of the system". The paper then abstracts this scenario for distributed computer systems.

1993

Researchers at the IBM Almaden Research Center propose the use of pricing functions and hash functions to tackle the problem of spam emails. The idea is that an email sender must be required to perform a moderately expensive computation and the recipient can verify easily that such a computation has been performed before accepting the email. This will deter spammers. The idea of modern proof-of-work can be traced back to this research.

1997

Adam Black invents Hashcash, a PoW system to tackle email spam and denial-of-service attacks. Hashcash can be credited with making PoW popular.

Feb
1999

At the 3rd Symposium on Operating Systems Design and Implementation, researchers from the MIT Laboratory for Computer Science present "Practical Byzantine Fault Tolerance" as a solution to the Byzantine Generals Problem. Unlike previous solutions, this works in asynchronous systems and improves response times. This is further detailed in an ACM paper published in 2002.

2009

Bitcoin is introduced as a peer-to-peer cryptocurrency. It uses Proof of Work (PoW) for consensus.

2012

Since PoW used by Bitcoin is wasteful, Proof of Stake is proposed as a more energy efficient alternative. This later gives birth to the Peercoin network. PoS however suffers from the "Nothing-at-stake" problem.

Dec
2013

Daniel Larimer, founder of BitShares, proposes a new type of PoS in which stakeholders elect nodes who can sign the blocks. This is the genesis of Delegated Proof of Stake consensus. Elected nodes are called witnesses and they are trusted to behave correctly. The voting process is decentralized and fair. DPoS scales well because nodes need not wait for a minimum number of untrusted nodes to verify a block, which needs to be only signed by one or more trusted nodes.

Aug
2015

Vlad Zamfir of Ethereum announces that they have been working on a new consensus called Casper. It's a PoS type of consensus. Casper has mechanism in place to punish nodes that try to do exploit the "Nothing-at-stake" situation. Ethereum is expected to switch from PoW to PoS in 2018.

Apr
2016

Intel announces details of Sawtooth Lake project, a platform for running distributed ledgers. This talks about two consensus protocols: (a) Proof of Elapsed Time (PoET) that avoids the energy inefficiency of PoW. (b) Quorum Voting that adapts PBFT protocol and uses it for apps that require immediate transaction finality. In January 2018, Hyperledger Sawtooth 1.0 is released and PoET is part of it.

May
2018

MaidSafe announces a new consensus protocol called PARSEC (Protocol for Asynchronous, Reliable, Secure and Efficient Consensus) to power its SAFE Network. PARSEC is a "completely decentralised, open source, highly asynchronous, Byzantine Fault Tolerant consensus mechanism".

References

  1. Abraham, Rohan. 2018. "Can hashgraph succeed blockchain as the technology of choice for cryptocurrencies?" The Hindu, March 25. Accessed 2018-03-28.
  2. Avdyusheva, Yuliya. 2018. "Matrix Reveals a Brand New PoW/PoS Consensus Algorithm." Cointelegraph, January 29. Accessed 2018-03-28.
  3. Baird, Leemon. 2016. "The Swirlds Hashgraph Consensus Algorithm: Fair, Fast, Byzantine Fault Tolerance." SWIRLDS-TR-2016-01, pp. 1-28, May 31. Updated 2018-03-18. Accessed 2018-03-28.
  4. Balaban, David. 2018. "Blockchain Networks: Possible Attacks and Ways of Protection." nfoSec Institute, January 22. Accessed 2018-03-31.
  5. Batlin, Alex. 2016. "Crypto 2.0 Musings - Proof of Elapsed Time." LinkedIn Pulse, April 30. Accessed 2018-03-28.
  6. BitShares Docs. 2018. "Delegated Proof of Stake." BitShares 2.0. Accessed 2018-03-30.
  7. Bitcoin Wiki. 2018. "Weaknesses." February 4. Accessed 2018-03-31.
  8. Castor, Amy. 2017. "A (Short) Guide to Blockchain Consensus Protocols." CoinDesk, March 4. Updated 2017-05-17. Accessed 2018-03-28.
  9. Castro, Miguel, and Barbara Liskov. 1999. "Practical Byzantine Fault Tolerance." Proceedings of the Third Symposium on Operating Systems Design and Implementation, New Orleans, USA, February. Accessed 2018-03-30.
  10. Castro, Miguel, and Barbara Liskov. 2002. "Practical Byzantine Fault Tolerance and Proactive Recovery." ACM Transactions on Computer Systems, Vol. 20, No. 4, pp. 398-461, November. Accessed 2018-03-28.
  11. Chevalier, Pierre, Bartlomiej Kaminski, Fraser Hutchison, Qi Ma, Spandan Sharma, Andreas Fackler, and William J Buchanan. 2019. "Protocol for Asynchronous, Reliable, Secure and Efficient Consensus (PARSEC) Version 2.0." arXiv, v1, July 26. Accessed 2020-05-03.
  12. Conti, Mauro, Sandeep Kumar E, Chhagan Lal, and Sushmita Ruj. 2017. "A Survey on Security and Privacy Issues of Bitcoin." arXiv, December 25. Accessed 2018-04-03.
  13. Data Driven Investor. 2018. "Blockchain Consensus Algorithm: PoW, PoS, and Beyond." CryptoNinjas, February 27. Accessed 2018-03-28.
  14. Dwork, Cynthia, and Moni Naor. 1993. "Pricing via Processing or Combatting Junk Mail." Advances in Cryptology, CRYPTO'92: Lecture Notes in Computer Science No. 740. Springer: pp. 139–147. Accessed 2018-03-30.
  15. Flaxman, Michael. 2017. "The Blockchain is Evolutionary not Revolutionary." Paxos Engineering Blog, February 23. Accessed 2018-03-30.
  16. Hammerschmidt, Chris. 2017a. "Consensus in Blockchain Systems. In Short." Medium, January 27. Accessed 2018-03-28.
  17. Hammerschmidt, Chris. 2017b. "An introduction to understanding attacks and dishonesty on proof-of-work blockchains." Medium, March 8. Accessed 2018-03-31.
  18. Hardesty, Linda. 2018. "Hyperledger Sawtooth 1.0 Includes Unique Consensus Software." SDxCentral, January 30. Accessed 2018-03-28.
  19. King, Sunny, and Scott Nadal. 2012. "PPCoin: Peer-to-Peer Crypto-Currency with Proof-of-Stake." August 19. Accessed 2019-09-23.
  20. Krzyzanowski, Paul. 2011. "Consensus: Reaching agreement." CS 417: Distributed Systems, Department of Computer Science, Rutgers University, October. Updated 2017-02-23. Accessed 2018-03-28.
  21. Lamport, Leslie, Robert Shostak, and Marshall Pease. 1982. "The Byzantine Generals Problem." ACM Transactions on Programming Languages and Systems (TOPLAS), vol. 4, no. 3, pp. 382-401, July. Accessed 2018-03-30.
  22. MaidSafe. 2018. "PARSEC: A Paradigm Shift for Asynchronous and Permissionless Consensus." Medium, May 24. Accessed 2018-05-25.
  23. Maxim, Orlovsky. 2017. "Defining Criteria for Consensus Algorithms." Medium, December 6. Accessed 2018-03-28.
  24. MultiChain. 2017. "Which consensus protocol multichain use?" Developer Q & A, Multichain, January 23. Accessed 2018-03-28.
  25. Rosic, Ameer. 2018. "Basic Primer: Blockchain Consensus Protocol." Blockgeeks, January 30. Accessed 2018-03-28.
  26. Rouse, Margaret. 2017. "Consensus algorithm." TechTarget, August. Accessed 2018-03-28.
  27. Seibold, Sigrid, and George Samman. 2016. "Consensus: Immutable agreement for the Internet of value." KPMG. Accessed 2018-03-30.
  28. Vukolić, Marko. 2015. "The Quest for Scalable Blockchain Fabric: Proof-of-Work vs. BFT Replication." IBM Research. Accessed 2018-03-30.
  29. Wang, Gabriel. 2016. "Building Business Cases With Distributed Ledger Technology: Things to Know." Aite Group, August 3. Accessed 2018-03-28.
  30. Wikipedia. 2018. "Hashcash." Accessed 2018-03-30.
  31. Witherspoon, Jane. 2018. "A Hitchhiker’s Guide to Consensus Algorithms." Hackernoon, February 13. Accessed 2018-03-28.
  32. Zamfir, Vlad. 2015. "Introducing Casper “the Friendly Ghost”." Ethereum Blog, August 1. Accessed 2018-03-28.
  33. bytemaster. 2013. "Transactions as Proof-of-Stake & The End of Mining: Reply #57." Bitshares Talk, December 8. Accessed 2018-03-28.

Further Reading

  1. Witherspoon, Jane. 2018. "A Hitchhiker’s Guide to Consensus Algorithms." Hackernoon, February 13. Accessed 2018-03-28.
  2. Hammerschmidt, Chris. 2017a. "Consensus in Blockchain Systems. In Short." Medium, January 27. Accessed 2018-03-28.
  3. Chan, Ronald. 2016. "Consensus Mechanisms used in Blockchain." LinkedIn Pulse, May 2. Accessed 2018-03-28.
  4. Lamport, Leslie, Robert Shostak, and Marshall Pease. 1982. "The Byzantine Generals Problem." ACM Transactions on Programming Languages and Systems (TOPLAS), vol. 4, no. 3, pp. 382-401, July. Accessed 2018-03-30.
  5. Castro, Miguel, and Barbara Liskov. 2002. "Practical Byzantine Fault Tolerance and Proactive Recovery." ACM Transactions on Computer Systems, Vol. 20, No. 4, pp. 398-461, November. Accessed 2018-03-28.
  6. Vukolić, Marko. 2015. "The Quest for Scalable Blockchain Fabric: Proof-of-Work vs. BFT Replication." IBM Research. Accessed 2018-03-30.

Article Stats

Author-wise Stats for Article Edits

Author
No. of Edits
No. of Chats
DevCoins
User avatar sangeetha-prabhu
4
0
2427
Avatar of user arvindpdmn arvindpdmn
5
1
81
User avatar piluso
1
0
70
Avatar of user devbot5S devbot5S
1
2
38
Avatar of user tintin tintin
1
0
7
DevCoins due to articles, chats, their likes and article hits are included.
1932
Words
5
Authors
12
Edits
3
Chats
9
Likes
21K
Hits

Cite As

Devopedia. 2022. "Blockchain Consensus." Version 12, February 15. Accessed 2023-11-12. https://devopedia.org/blockchain-consensus
Contributed by
5 authors

Last updated on
2022-02-15 11:50:40
algorithms networking cryptography

See Also