본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

Journal of information processing systems v.14 no.1, 2018년, pp.101 - 128  
본 등재정보는 저널의 등재정보를 참고하여 보여주는 베타서비스로 정확한 논문의 등재여부는 등재기관에 확인하시기 바랍니다.

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  );
  • 초록

    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.


  • 주제어

    Blockchain .   Consensus Algorithm.  

  • 참고문헌 (82)

    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. 
    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. 
    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. 
    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. 
    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. 

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 이용한 콘텐츠
이 논문과 함께 출판된 논문 + 더보기