본문 바로가기
KERD
논문KCI 등재

A Survey about Consensus Algorithms Used in Blockchain

김경백|Giang-Truong Nguyen
한국정보처리학회|2018.02|JIPS(Journal of Information Processing Systems) (Journal of Information Processing Systems)|제14권 제1호|pp. 101-128|DOI https://doi.org/10.3745/JIPS.01.0024

0

조회

0

다운로드

12

인용

0

참고문헌

키워드

BlockchainConsensus Algorithm

초록

Thanks to its potential in many applications, Blockchain has recently been nominated as one of thetechnologies exciting intense attention. Blockchain has solved the problem of changing the original low-trustcentralized ledger held by a single third-party, to a high-trust decentralized form held by different entities, orin 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 todo the appending work. The second group is voting-based consensus, which requires nodes in the network toexchange 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 beingapplied in some well-known applications at this time.

Abstract

Thanks to its potential in many applications, Blockchain has recently been nominated as one of thetechnologies exciting intense attention. Blockchain has solved the problem of changing the original low-trustcentralized ledger held by a single third-party, to a high-trust decentralized form held by different entities, orin 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 todo the appending work. The second group is voting-based consensus, which requires nodes in the network toexchange 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 beingapplied in some well-known applications at this time.

참고문헌 (82)

  1. S. Haber, "How to time-stamp a digital document", Journal of Cryptology, 3(2), pp.99~111 (1991)
  2. "Bitcoin: a peer-to-peer electronic cash system" (2008)[URL]
  3. "The great chain of being sure about things" (2015)[URL]
  4. "Genesis block" (2017)[URL]
  5. "Digital signatures" (2017)[URL]
  6. "Ethereum"[URL]
  7. S. Popov, "A probabilistic analysis of the Nxt forging algorithm", Ledger, 1, pp.69~83 (2016)[DOI]
  8. "Whitepaper: Nxt" (2016)[URL]
  9. "A short guide to consensus building"[URL]
  11. "Proof of Stake" (2014)[URL]
  12. "Sawtooth v1.0.1" (2017)[URL]
  13. M. Milutinovic, "Proof of luck: an efficient Blockchain consensus protocol", Proceedings of the 1st Workshop on System Software for Trusted Execution (2016)
  14. "Spacecoin: a cryptocurrency based on proofs of space" (2017)[URL]
  15. C. Cachin, "Architecture of the hyperledger blockchain fabric", Proceedings of ACM Workshop on Distributed Cryptocurrencies and Consensus Ledgers (2016)
  16. "QuorumChain Consensus"[URL]
  17. L. Lamport, "Paxos made simple", ACM Sigact News, 32(4), pp.51~58 (2001)
  18. M. Castro, "Practical Byzantine fault tolerance", Proceedings of the Third Symposium on Operating Systems Design and Implementation, pp.173~186 (1999)
  19. M. Castro, "Byzantine fault tolerance, U.S. Patent 6671821 B1", ~ (2003)
  20. "How the private and public key pair works" (2017)[URL]
  21. "Elliptic curve digital signature algorithm" (2017)[URL]
  22. "Can someone explain how the Bitcoin Blockchain works?" (2017)[URL]
  23. "Block hashing algorithm" (2015)[URL]
  24. R. C. Merkle, "A digital signature based on a conventional encryption function", Advances in Cryptology- CRYPTO'87, pp.369~378 (1987)
  25. "SHA-256" (2016)[URL]
  26. "Cuckoo cycle: a memory-hard proof-of-work system" (2015)[URL]
  27. "Cuckoo Hashing"[URL]
  28. "Primecoin: cryptocurrency with prime number proof-of-work" (2013)[URL]
  29. "Cunningham chain" (2017)[URL]
  30. M. Liskov, "Encyclopedia of Cryptography and Security", pp.221~221 (2005), Springer
  31. "Irreversible transactions" (2017)[URL]
  32. "Weaknesses" (2017)[URL]
  33. "Two new models for double spending attacks on Bitcoin's Blockchain" (2016)[URL]
  34. "What are bitcoin mining pools?" (2014)[URL]
  35. "How to disincentivize large bitcoin mining pools" (2014)[URL]
  36. "Preventing the 51%-attack: a stochastic analysis of two phase proof of work in bitcoin" (2015)[URL]
  37. A. Miller, "Nonoutsourceable scratch-off puzzles to discourage bitcoin mining coalitions", Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, pp.680~691 (2015)
  38. I. Eyal, "Bitcoin-NG: a scalable blockchain protocol", Proceedings of the 13th Usenix Conference on Networked Systems Design and Implementation, pp.45~59 (2016)
  39. "Accelerating Bitcoin's transaction processing: fast money grows on trees, not chains" (2013)[URL]
  40. Y. Sompolinsky, "Financial Cryptography and Data Security", pp.507~527 (2015), Springer
  41. "Forking-free hybrid consensus with generalized proofof- activity" (2017)[URL]
  42. "Topic: Proof of stake instead of proof of work" (2011)[URL]
  43. I. Bentov, "Financial Cryptography and Data Security", pp.142~157 (2016), Springer
  44. A. Russell, "Perfect information leader election in log* n+O(1) rounds", Proceedings 39th Annual Symposium on Foundations of Computer Science, pp.576~583 (1998)
  45. M. Ben-Or, "Collective coin flipping" (1990), Institute of Mathematics and Computer Science, The Hebrew University
  46. "Ouroboros: a provably secure proof-of-stake blockchain protocol" (2016)[URL]
  47. A. Kiayias, "Ouroboros: a provably secure proof-of-stake blockchain protocol", Advances in Cryptology-CRYPTO 2017, pp.357~388 (2017)
  48. "Delegated Proof-of-Stake (DPOS)" (2014)[URL]
  49. "PPcoin: peer-to-peer crypto-currency with proof-of-stake" (2012)[URL]
  50. "Blackcoin's proof-of-stake protocol v2" (2014)[URL]
  51. "Proof of stake velocity: building the social currency of the digital age" (2014)[URL]
  52. "2-hop Blockchain: combining proof-of-work and proof-of-stake securely" (2016)[URL]
  53. "TwinsCoin: a cryptocurrency via proof-of-work and proof-of-stake" (2017)[URL]
  54. I. Bentov, "Proof of activity: extending bitcoin's proof of work via proof of stake", ACM SIGMETRICS Performance Evaluation Review, 42(3), pp.34~37 (2014)[DOI]
  55. J. Blocki, "Theory of Cryptography", pp.517~546 (2016), Springer
  56. "Slimcoin: a peer-to-peer crypto-currency with proof-of-burn" (2014)[URL]
  57. S. Dziembowski, "Proofs of space", Advances in Cryptology- CRYPTO 2015, pp.585~605 (2015)
  58. "The second coming of blockchain" (2017)[URL]
  59. "Hyperledger Sawtooth"[URL]
  60. M. Sabt, "Trusted execution environment: what it is, and what it is not", Proceedings of 2015 IEEE Trustcom, ISPA, pp.2015[DOI]
  61. "Intel Software Guard Extensions (Intel SGX)"[URL]
  62. "Multichain"[URL]
  63. "MultiChain Private Blockchain" (2015)[URL]
  64. A conceptual framework for system fault tolerance, "W. L. Heimerdinger", Defense Technical Information Center, ~, pp.Technical Report CMU (1992), SEI-92-TR-033
  65. L. Lamport, "Paxos made simple", ACM SIGACT News, 32(4), pp.18~25 (2014)
  66. L. Lamport, "The Byzantine generals problem", ACM Transactions on Programming Languages and Systems, 4(3), pp.382~401 (1982)[DOI]
  67. "Hyperledger"[URL]
  68. "Hyperledger fabric"[URL]
  69. H. Sukhwani, "Performance modeling of PBFT consensus process for permissioned blockchain network (Hyperledger Fabric)", Proceedings of the IEEE 36th Symposium on Reliable Distributed Systems, pp.253~255 (2017)
  70. "Symbiont"[URL]
  71. "Corda"[URL]
  72. A. Bessani, "State machine replication for the masses with BFT-SMART", Proceedings of 2014 44th Annual IEEE, 2014, 355~362
  73. "Hyperledger iroha"[URL]
  74. "Sumeragi"[URL]
  75. S. Duan, "Principles of Distributed Systems", pp.91~106 (2014), Springer
  76. "The Ripple protocol consensus algorithm" (2014)[URL]
  77. F. Armknecht, "Trust and Trustworthy Computing", pp.163~180 (2015), Springer
  78. "Ripple"[URL]
  79. "The Stellar Consensus Protocol: a federated model for internet-level consensus" (2015)[URL]
  80. D. Ongaro, "In search of an understandable consensus algorithm", Proceedings of 2014 USENIX Annual Technical Conference, pp.305~319 (2014)
  81. "Raft-based consensus for Ethereum/Quorum"[URL]
  82. "Federated Consensus"[URL]

관련 논문AI추천

블록체인 기술 및 응용사례신현준, 유재필한국엔터프라이즈아키텍처학회 · 정보화연구2018 · 제15권 제3호블록체인 기반 암호화폐의 조사김준상한국컴퓨터정보학회 · 한국컴퓨터정보학회논문지2019 · 제24권 제2호평가항목 제안 및 분석을 통한 블록체인 분산합의 알고리즘 성능 개선김기영, 김도균, 오진태, 최진영한국산업경영시스템학회 · 한국산업경영시스템학회지2018 · 제41권 제4호A Survey of the Application of Blockchain in Multiple Fields of Financial Services정동원, Dae-Kyoo Kim, Yiran Wang한국정보처리학회 · JIPS(Journal of Information Processing Systems)2020 · 제16권 제4호The Dilemma of Parameterizing Propagation Time in Blockchain P2P Network노시완, 이경모, 이경현, Bruno Joachim Kweka, Sandi Rahmadika한국정보처리학회 · JIPS(Journal of Information Processing Systems)2020 · 제16권 제3호블록체인 기술의 사물인터넷 적용에 대한 조사 연구-적용 환경, 합의 알고리즘, 플랫폼 중심으로김미희, 이기훈한국지식정보기술학회 · 한국지식정보기술학회 논문지2020 · 제15권 제1호

이 간행물의 다른 논문 (17건)

Practical Approaches Based on Deep Learning and Social Computing박종혁pp. 1-5A Survey on Passive Image Copy-Move Forgery DetectionZhi Zhang, Xiao Zhou, Chengyou Wangpp. 6-31A Comparative Analysis of Music Similarity Measures in Music Information Retrieval SystemsKuldeep Gurjar, 문양세pp. 32-55Black Hole along with Other Attacks in MANETs: A SurveyHua-Pei Chiang, Han-Chieh Chao, Fan-Hsun Tsengpp. 56-78A Survey on Automatic Twitter Event SummarizationDwijen Rudrapal, Amitava Das, Baby Bhattacharyapp. 79-100
원문 보기