Journal of Information Processing Systems

Korea Information Processing Society (한국정보처리학회)
권호 표지
DOI QR코드

DOI QR Code

A Survey about Consensus Algorithms Used in Blockchain

  • Nguyen, Giang-Truong (School of Electronics and Computer Engineering, Chonnam National University) ;
  • Kim, Kyungbaek (School of Electronics and Computer Engineering, Chonnam National University)
  • Received : 2017.11.17
  • Accepted : 2017.01.03
  • Published : 2018.02.28
Download PDF
⟨ Previous Next ⟩

Abstract

Thanks to its potential in many applications, Blockchain has recently been nominated as one of the technologies exciting intense attention. Blockchain has solved the problem of changing the original low-trust centralized ledger held by a single third-party, to a high-trust decentralized form held by different entities, or in other words, verifying nodes. The key contribution of the work of Blockchain is the consensus algorithm, which decides how agreement is made to append a new block between all nodes in the verifying network. Blockchain algorithms can be categorized into two main groups. The first group is proof-based consensus, which requires the nodes joining the verifying network to show that they are more qualified than the others to do the appending work. The second group is voting-based consensus, which requires nodes in the network to exchange their results of verifying a new block or transaction, before making the final decision. In this paper, we present a review of the Blockchain consensus algorithms that have been researched and that are being applied in some well-known applications at this time.

Keywords

E1JBB0_2018_v14n1_101_f0001.png 이미지

Fig. 1. How a verifying system checks if the transaction is requested by the true sender.

E1JBB0_2018_v14n1_101_f0002.png 이미지

Fig. 2. An example of Blockchain [22].

E1JBB0_2018_v14n1_101_f0003.png 이미지

Fig. 3. The fields inside a block.

E1JBB0_2018_v14n1_101_f0004.png 이미지

Fig. 4. The process for handling with the nonce: guessed secret value.

E1JBB0_2018_v14n1_101_f0005.png 이미지

Fig. 5. How Bitcoin handles the forking problem.

E1JBB0_2018_v14n1_101_f0006.png 이미지

Fig. 6. A script for double spending attack [33].

E1JBB0_2018_v14n1_101_f0007.png 이미지

Fig. 7. Strategy for choosing the main chain when fork appears. Adapted from Sompolinsky and Zolar,“Secure high-rate transaction processing in bitcoin,” in Financial Cryptography and Data Security.Heidelberg: Springer, 2015, with the permission of Springer [40].

E1JBB0_2018_v14n1_101_f0008.png 이미지

Fig. 8. Rounds for verifying transactions in Hyperledger fabric. Adapted from Sukhwani et al.,“Performance modeling of PBFT consensus process for permissioned blockchain network (HyperledgerFabric),” in Proceedings of the IEEE 36th Symposium on Reliable Distributed Systems, Hong Kong,China, 2017, with the permission of IEEE [69].

E1JBB0_2018_v14n1_101_f0009.png 이미지

Fig. 9. BFT-SMaRt execution. Adapted from Bessani et al., “State machine replication for the masseswith BFT-SMART,” in Proceedings of 2014 44th Annual IEEE/IFIP International Conference onDependable Systems and Networks, Atlanta, GA, 2014, with the permission of IEEE [72].

E1JBB0_2018_v14n1_101_f0010.png 이미지

Fig. 10. Example of quorum slice in Stellar.

E1JBB0_2018_v14n1_101_f0011.png 이미지

Fig. 11. Node's role transition in Raft [80].

Table 1. Comparisons between PoW, PoS, and their Hybrid form

E1JBB0_2018_v14n1_101_t0001.png 이미지

Table 2. Comparisons between vote-based consensus and proof-based consensus algorithms

E1JBB0_2018_v14n1_101_t0002.png 이미지

Table 3. Summary of surveyed consensus algorithms in this paper

E1JBB0_2018_v14n1_101_t0003.png 이미지

Table 3. Continued

E1JBB0_2018_v14n1_101_t0004.png 이미지

References

  1. S. Haber and W. S. Stornetta, "How to time-stamp a digital document," Journal of Cryptology, vol. 3, no. 2, pp. 99-111, 1991. https://doi.org/10.1007/BF00196791
  2. S. Nakamoto, "Bitcoin: a peer-to-peer electronic cash system," 2008 [Online]. Available: https://bitcoin.org/ bitcoin.pdf.
  3. The Economist, "The great chain of being sure about things," 2015 [Online]. Available: https://www. economist.com/news/briefing/21677228-technology-behind-bitcoin-lets-people-who-do-not-know-or-trusteach-other-build-dependable.
  4. Bitcoinwiki, "Genesis block," 2017 [Online]. Available: https://en.bitcoin.it/wiki/Genesis_block.
  5. E. Robert, "Digital signatures," 2017 [Online]. Available: http://cs.stanford.edu/people/eroberts/courses/ soco/projects/public-key-cryptography/dig_sig.html.
  6. Ethereum [Online]. Available: https://www.ethereum.org.
  7. S. Popov, "A probabilistic analysis of the Nxt forging algorithm," Ledger, vol. 1, pp. 69-83, 2016. https://doi.org/10.5195/LEDGER.2016.46
  8. Nxt wiki, "Whitepaper: Nxt," 2016 [Online]. Available: https://nxtwiki.org/wiki/Whitepaper:Nxt.
  9. The Public Disputes Program, "A short guide to consensus building," [Online]. Available: http://web.mit.edu/publicdisputes/practice/cbh_ch1.html.
  10. A. Back, "Hashcash: a denial of service counter-measure," 2002 [Online]. Available: ftp://sunsite.icm.edu.pl/site/replay.old/programs/hashcash/hashcash.pdf.
  11. Bitcoinwiki, "Proof of Stake," 2014 [Online]. Available: https://en.bitcoin.it/wiki/Proof_of_Stake.
  12. Intel, "Sawtooth v1.0.1," 2017 [Online]. Available: https://sawtooth.hyperledger.org/docs/core/releases/latest/introduction.html.
  13. M. Milutinovic, W. He, H. Wu, and M. Kanwa, "Proof of luck: an efficient Blockchain consensus protocol," in Proceedings of the 1st Workshop on System Software for Trusted Execution, New York, NY, 2016.
  14. S. Park, K. Pietrzak, A. Kwon, J. Alwen, G. Fuchsbauer, and P. Gazi, "Spacecoin: a cryptocurrency based on proofs of space," 2017 [Online]. Available: https://eprint.iacr.org/2015/528
  15. C. Cachin, "Architecture of the hyperledger blockchain fabric," in Proceedings of ACM Workshop on Distributed Cryptocurrencies and Consensus Ledgers, Chicago, IL, 2016.
  16. QuorumChain Consensus [Online]. Available: https://github.com/jpmorganchase/quorum/wiki/QuorumChain-Consensus.
  17. L. Lamport, "Paxos made simple," ACM Sigact News, vol. 32, no. 4, pp. 51-58, 2001.
  18. M. Castro and B. Liskov, "Practical Byzantine fault tolerance," in Proceedings of the Third Symposium on Operating Systems Design and Implementation, New Orleans, LA, 1999, pp. 173-186.
  19. M. Castro and B. Liskov, "Byzantine fault tolerance," U.S. Patent 6671821 B1, Dec 30, 2003.
  20. C. Pommier, "How the private and public key pair works," 2017 [Online]. Available: https://www.symantec.com/connect/blogs/how-private-and-public-key-pair-works.
  21. Elliptic curve digital signature algorithm, 2017 [Online]. Available: https://en.bitcoin.it/wiki/Elliptic_Curve_Digital_Signature_Algorithm.
  22. Bitcoin Stack Exchange, "Can someone explain how the Bitcoin Blockchain works?," 2017 [Online]. Available: https://bitcoin.stackexchange.com/questions/12427/can-someone-explain-how-the-bitcoinblockchain-works.
  23. Bitcoinwiki, "Block hashing algorithm," 2015 [Online]. Available: https://en.bitcoin.it/wiki/Block_hashing_algorithm.
  24. R. C. Merkle, "A digital signature based on a conventional encryption function," in Advances in Cryptology- CRYPTO'87. Heidelberg: Springer, 1987, pp. 369-378.
  25. Bitcoinwiki, "SHA-256," 2016 [Online]. Available: https://en.bitcoin.it/wiki/SHA-256.
  26. J. Tromp, "Cuckoo cycle: a memory-hard proof-of-work system," 2015 [Online]. Available: https://eprint.iacr.org/2014/059.pdf.
  27. K. Schwarz, "Cuckoo Hashing," [Online]. Available: http://web.stanford.edu/class/cs166/lectures/13/Small13.pdf.
  28. S. King, "Primecoin: cryptocurrency with prime number proof-of-work," 2013 [Online]. Available: http://primecoin.io/bin/primecoin-paper.pdf.
  29. C. K. Caldwell, "Cunningham chain," 2017 [Online]. Available: http://primes.utm.edu/glossary/xpage/CunninghamChain.html.
  30. M. Liskov, "Fermat primality test," in Encyclopedia of Cryptography and Security. Boston, MA: Springer, 2005, pp. 221-221.
  31. Bitcoinwiki, "Irreversible transactions," 2017 [Online]. Available: https://en.bitcoin.it/wiki/Irreversible_Transactions.
  32. Bitcoinwiki, "Weaknesses," 2017 [Online]. Available: https://en.bitcoin.it/wiki/Weaknesses#Attacker_has_a_lot_of_computing_power.
  33. T. Sameeh, "Two new models for double spending attacks on Bitcoin's Blockchain," 2016 [Online]. Available: https://www.deepdotweb.com/2016/12/31/two-new-models-double-spending-attacks-bitcoinsblockchain/.
  34. CoinDesk Inc., "What are bitcoin mining pools?," 2014 [Online]. Available: https://www.coindesk.com/information/get-started-mining-pools/.
  35. I. Eyal and E. G. Sirer, "How to disincentivize large bitcoin mining pools," 2014 [Online]. Available: http://hackingdistributed.com/2014/06/18/how-to-disincentivize-large-bitcoin-mining-pools.
  36. M. Bastiaan, "Preventing the 51%-attack: a stochastic analysis of two phase proof of work in bitcoin," 2015 [Online]. Available: http://referaat.cs.utwente.nl/conference/22/paper/7473/preventingthe-51-attack%20-astochastic-analysis-of-two-phase-proof-of-work-in-bitcoin.pdf.
  37. A. Miller, A. Kosba, J. Katz, and E. Shi, "Nonoutsourceable scratch-off puzzles to discourage bitcoin mining coalitions," in Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, New York, NY, 2015, pp. 680-691.
  38. I. Eyal, A. E. Gencer, E. G. Sirer, and R. V. Renesse, "Bitcoin-NG: a scalable blockchain protocol," in Proceedings of the 13th Usenix Conference on Networked Systems Design and Implementation, Berkeley, CA, 2016, pp. 45-59.
  39. Y. Sompolinsky and A. Zohar, "Accelerating Bitcoin's transaction processing: fast money grows on trees, not chains," 2013 [Online]. Available: https://eprint.iacr.org/2013/881.pdf.
  40. Y. Sompolinsky and A. Zohar, "Secure high-rate transaction processing in bitcoin," in Financial Cryptography and Data Security. Heidelberg: Springer, 2015, pp. 507-527.
  41. Z. Liu, S. Tang, S. S. M. Chow, Z. Liu, and Y. Long, "Forking-free hybrid consensus with generalized proofof- activity," 2017 [Online]. Available: https://eprint.iacr.org/2017/367.pdf.
  42. Bitcoin forum, "Topic: Proof of stake instead of proof of work," 2011 [Online]. Available: https://bitcointalk.org/index.php?topic=27787.0.
  43. I. Bentov, A. Gabizon, and A. Mizrahi, "Cryptocurrencies without proof of work," in Financial Cryptography and Data Security. Heidelberg: Springer, 2016, pp. 142-157.
  44. A. Russell and D. Zuckerman, "Perfect information leader election in log* n+O(1) rounds," in Proceedings 39th Annual Symposium on Foundations of Computer Science, Palo Alto, CA, 1998, pp. 576-583.
  45. M. Ben-Or and N. Linial, "Collective coin flipping," Institute of Mathematics and Computer Science, The Hebrew University, Jerusalem, Israel, 1990.
  46. A. Kiayias, A. Russell, B. David, and R. Oliynykov, "Ouroboros: a provably secure proof-of-stake blockchain protocol," 2016 [Online]. Available: https://eprint.iacr.org/2016/889.pdf.
  47. A. Kiayias, A. Russell, B. David, and R. Oliynykov, "Ouroboros: a provably secure proof-of-stake blockchain protocol," in Advances in Cryptology-CRYPTO 2017. Cham, Switzerland: Springer, 2017, pp. 357-388.
  48. D. Larimer, "Delegated Proof-of-Stake (DPOS)," 2014 [Online]. Available: https://bitshares.org/technology/delegated-proof-of-stake-consensus/.
  49. S. King and S. Nadal, "PPcoin: peer-to-peer crypto-currency with proof-of-stake," 2012 [Online]. Available: https://decred.org/research/king2012.pdf.
  50. P. Vasin, "Blackcoin's proof-of-stake protocol v2," 2014 [Online]. Available: https://blackcoin.co/blackcoinpos-protocol-v2-whitepaper.pdf.
  51. L. Ren, "Proof of stake velocity: building the social currency of the digital age," 2014 [Online]. Available: https://www.reddcoin.com/papers/PoSV.pdf.
  52. T. Duong, L. Fan, and H. S. Zhou, "2-hop Blockchain: combining proof-of-work and proof-of-stake securely," 2016 [Online]. Available: https://eprint.iacr.org/2016/716.pdf.
  53. A. Chepurnoy, T. Duong, L. Fan, and H. S. Zhou, "TwinsCoin: a cryptocurrency via proof-of-work and proof-of-stake," 2017 [Online]. Available: https://eprint.iacr.org/2017/232.pdf.
  54. I. Bentov, C. Lee, A. Mizrahi, and M. Rosenfeld, "Proof of activity: extending bitcoin's proof of work via proof of stake," ACM SIGMETRICS Performance Evaluation Review, vol. 42, no. 3, pp. 34-37, 2014. https://doi.org/10.1145/2695533.2695545
  55. J. Blocki and H. S. Zhou, "Designing proof of human-work puzzles for cryptocurrency and beyond," in Theory of Cryptography. Heidelberg: Springer, 2016, pp. 517-546.
  56. P4Titan, "Slimcoin: a peer-to-peer crypto-currency with proof-of-burn," 2014 [Online]. Available: http://www.doc.ic.ac.uk/-ids/realdotdot/crypto_papers_etc_worth_reading/proof_of_burn/slimcoin_white paper.pdf.
  57. S. Dziembowski, S. Faust, V. Kolmogorov, and K. Pietrzak, "Proofs of space" in Advances in Cryptology- CRYPTO 2015. Heidelberg: Springer, 2015, pp. 585-605.
  58. R. Echevarria, "The second coming of blockchain," 2017 [Online]. Available: https://software.intel.com/enus/ blogs/2017/02/14/the-second-coming-of-blockchain
  59. Hyperledger Sawtooth [Online]. Available: https://sawtooth.hyperledger.org/docs/.
  60. M. Sabt, M. Achemlal and A. Bouabdallah, "Trusted execution environment: what it is, and what it is not," in Proceedings of 2015 IEEE Trustcom/BigDataSE/ISPA, Helsinki, Finland, 2015, pp. 57-64.
  61. Intel Software Guard Extensions (Intel SGX) [Online]. Available: https://software.intel.com/en-us/sgx.
  62. Multichain [Online]. Available: https://github.com/MultiChain/multichain.
  63. G. Greenspan, "MultiChain Private Blockchain," 2015 [Online]. Available: https://www.multichain.com/download/MultiChain-White-Paper.pdf
  64. W. L. Heimerdinger and C. B. Weinstock, "A conceptual framework for system fault tolerance," Defense Technical Information Center, Technical Report CMU/SEI-92-TR-033, 1992.
  65. L. Lamport, "Paxos made simple," ACM SIGACT News, vol. 32, no. 4, pp. 18-25, 2014.
  66. L. Lamport, R. Shostak, and M, Pease, "The Byzantine generals problem," ACM Transactions on Programming Languages and Systems, vol. 4, no. 3, pp. 382-401, 1982. https://doi.org/10.1145/357172.357176
  67. Hyperledger [Online]. Available: http://hyperledger.org/.
  68. Hyperledger fabric [Online]. Available: https://github.com/hyperledger/fabric.
  69. H. Sukhwani, J. M. Martinez, X. Chang, K. S. Trivedi, and A. Rindos, "Performance modeling of PBFT consensus process for permissioned blockchain network (Hyperledger Fabric)," in Proceedings of the IEEE 36th Symposium on Reliable Distributed Systems, Hong Kong, China, 2017, pp. 253-255.
  70. Symbiont [Online]. Available: https://symbiont.io/.
  71. Corda [Online]. Available: https://www.corda.net/.
  72. A. Bessani, J. Sousa, and E. E. P. Alchieri, "State machine replication for the masses with BFT-SMART," in Proceedings of 2014 44th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, Atlanta, GA, 2014, pp. 355-362.
  73. Hyperledger iroha [Online]. Available: https://github.com/hyperledger/iroha.
  74. Sumeragi [Online]. Available: https://github.com/hyperledger/iroha/wiki/Sumeragi.
  75. S. Duan, H. Meling, S. Peisert, and H. Zhang, "BChain: byzantine replication with high throughput and embedded reconfiguration," in Principles of Distributed Systems. Cham, Switzerland: Springer, 2014, pp. 91-106.
  76. D. Schwartz, N. Youngs, and A. Britto, "The Ripple protocol consensus algorithm," 2014 [Online]. Available: https://ripple.com/files/ripple_consensus_whitepaper.pdf.
  77. F. Armknecht, G. O. Karame, A. Mandal, F. Youssef, and E. Zenner, "Ripple: overview and outlook," in Trust and Trustworthy Computing. Cham, Switzerland: Springer, 2015, pp. 163-180.
  78. Ripple [Online]. Available: from https://ripple.com/.
  79. D. Mazieres, "The Stellar Consensus Protocol: a federated model for internet-level consensus," 2015 [Online]. Available: https://www.stellar.org/papers/stellar-consensus-protocol.pdf.
  80. D. Ongaro and J. K. Ousterhout, "In search of an understandable consensus algorithm," in Proceedings of 2014 USENIX Annual Technical Conference, Philadelphia, PA, 2014, pp. 305-319.
  81. Raft-based consensus for Ethereum/Quorum [Online]. Available: https://github.com/jpmorganchase/quorum/blob/master/raft/doc.md.
  82. Federated Consensus [Online]. Available: https://chain.com/docs/1.2/protocol/papers/federated-consensus.