<mark id="3h7ik"></mark><tt id="3h7ik"></tt>
    1. 
      

      論文協議

      [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-trust-
      each-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.
      Giang-Truong Nguyen and Kyungbaek Kim
      J Inf Process Syst, Vol.14, No.1, pp.101~128, February 2018 | 125
      [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/Quorum
      Chain-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-bitcoin-
      blockchain-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-bitcoins-
      blockchain/.
      [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-a-
      stochastic-analysis-of-two-phase-proof-of-work-in-bitcoin.pdf.
      A Survey about Consensus Algorithms Used in Blockchain
      126 | J Inf Process Syst, Vol.14, No.1, pp.101~128, February 2018
      [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 proof-
      of-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/blackcoin-
      pos-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.
      Giang-Truong Nguyen and Kyungbaek Kim
      J Inf Process Syst, Vol.14, No.1, pp.101~128, February 2018 | 127
      [58] R. Echevarria, “The second coming of blockchain,” 2017 [Online]. Available: https://software.intel.com/en-
      us/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.

      www.kips.or.kr Copyright© 2018 KIPS
      A Survey about Consensus Algorithms
      Used in Blockchain
      Giang-Truong Nguyen* and Kyungbaek Kim*
      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
      Blockchain, Consensus Algorithm
      1. Introduction
      First introduced by Haber and Stornetta [1], Blockchain is recently considered as one of the
      technologies with the most potential. It has attracted intense attention only after the introduction of
      Bitcoin by Nakamoto [2]. This is because Bitcoin has the ability to solve a problem in the traditional
      payment method: that of trust in a single third party. Normally, when people make payments, they have
      to trust a third party, who would verify the validity of their transactions, before putting them into
      action. Unfortunately, this middle party is doubted, whether it could be exploited to cheat its users or
      not [3]. The problem comes from formal centralization, in which everything depends on a single
      organization, causing trust to be insufficient. The solution to this problem is using multiple
      independent organizations to verify transactions, which changes the view from centralization to
      decentralization.
      Motivated by this idea, there is a ledger in Bitcoin and other later variants of Blockchain that records
      every transaction which has been successfully verified. For example, Bob sends Mary 5 dollars, Mary
      ※ This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/3.0/) which
      permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
      Manuscript received November 17, 2017; first revision December 27, 2017; accepted January 3, 2017.
      Corresponding Author: Kyungbaek Kim (kyungbaekkim@jnu.ac.kr)
      * School of Electronics and Computer Engineering, Chonnam National University, Gwangju, Korea (truongnguyengiang.bk@gmail.com,
      kyungbaekkim@jnu.ac.kr)
      J Inf Process Syst, Vol.14, No.1, pp.101~128, February 2018 ISSN 1976-913X (Print)
      https://doi.org/10.3745/JIPS.01.0024 ISSN 2092-805X (Electronic)
      A Survey about Consensus Algorithms Used in Blockchain
      102 | J Inf Process Syst, Vol.14, No.1, pp.101~128, February 2018
      sends Carl 10 dollars. So, based on this ledger, it is possible to know how much money a person owns.
      In order to make the system trustful by the decentralization method, this ledger is held by many
      organizations, which can be termed nodes or parties. Satoshi has proposed a design of this ledger that
      introduces a so-called block, which contains successfully verified transactions. The mentioned ledger
      above is re-established, and contains many blocks with transactions inside. This is the reason for the
      name “Blockchain”. The first block in the chain is called the genesis block [4], which contains the first
      transactions of the Bitcoin.
      When any transaction is proposed, its validity is verified by some nodes. If it is valid, which means
      the sender has enough money to send (proved by the past transactions in the old blocks), and also the
      sender has confirmed this transaction by signing his or her digital signature [5] inside the transaction, it
      will be included in a block. From here, in order to make a transaction really valid, the block containing
      this transaction should be added to the chain, which must be recognized by all the other nodes. A node
      will try to append a block containing many transactions by broadcasting it to the rest, which proposes
      to them to add this one to their current chain. However, if the transactions are verified in this way, there
      could be confusion when every node tries to broadcast their found block. In order to prevent this
      situation, an agreement, which is called consensus algorithm, should be made between all nodes about
      which blocks should be appended, and which nodes are permitted to append their proposed blocks. To
      date, many consensus algorithms have been proposed.
      Many variants of Bitcoin have been introduced since 2009, like Ethereum [6], and Nxtcoin [7,8]. The
      common characteristic of these variants is that anyone wanting to maintain the ledger can join, as well
      as withdraw anytime. Therefore, these kinds are called Public Blockchains. Because of this joining
      freedom, the idea of applying human real-life consensus [9], in which the results should be collected
      from all the nodes before making the final decision, is difficult. The reason is the unknown number of
      nodes, and their un-manageable execution. When there are too many nodes, the communication to
      exchange agreements between them would be very complicated. Worse, because it is possible to manage
      those nodes, taking agreement from all of them would lead to many possible risks, which could
      potentially harm the ledger holding procedure. Consequently, in order to append a block to the chain,
      all the nodes have to show they are more “qualified” than the others to do this work. Therefore, a
      consensus algorithm of this kind could be named a “proof-based consensus”. In public Blockchain, in
      order to encourage nodes to maintain the ledger, the node will receive some rewards, after appending a
      block to the chain.
      Motivated by the former research of Back [10], the first variant of a proof-based consensus algorithm
      is proof of work (PoW) [2]. In this kind of consensus algorithm, nodes are only permitted to broadcast
      their blocks when they have performed a lot of effort by their computing power. Based on the drawback
      of PoW [11], proof of stake (PoS) employs the stake of each node, and a lucky factor to decide the block
      appending one. At the time of writing, PoW- and PoS-based consensus algorithms are the most popular
      ones used in research and applications. Besides these two, there are also other proposed algorithms, like
      proof of elapsed time [12], proof of luck [13], and proof of space [14].
      Realizing the potentiality of Blockchain, many giant enterprises and organizations, like IBM and JP
      Morgan, have started to research this technology [15,16]. Based on the main rule that only permitted
      nodes could join the verifying system, many new platforms of Blockchain have been created, which
      include consortium Blockchains and private Blockchains. Specifically, while the former includes
      Giang-Truong Nguyen and Kyungbaek Kim
      J Inf Process Syst, Vol.14, No.1, pp.101~128, February 2018 | 103
      verifiers from different consortia, only a single organization is included in the latter. Thanks to the
      limited number of manageable nodes, these variants could employ a consensus algorithm that simulates
      a real-life situation: the final decision is made based on the results of the majority. This is the basis for
      giving these variants the name “voting-based consensus algorithms”. If a node wants to append a block
      to its chain, a requirement must be satisfied: this node will have to make sure that at least T nodes (T is
      a threshold, which varies depending on the system, and T should be more than 50% of all the nodes)
      will append the same block to it. In order to avoid bad situations that could harm the final results, some
      fault tolerance techniques [17,18] should be applied. Nodes executing the voting based consensus
      algorithm follow two popular systems: crush fault tolerance [17], and Byzantine fault tolerance [19].
      From here, we wish to emphasize that the proof-based consensus algorithm is not only applicable to
      public Blockchains, but also to private and consortium ones. The reverse case is also true with voting-
      based consensus in private and consortium Blockchains. However, the proof-based consensus
      algorithms are suitable for applying in the network having a lot of nodes. Meanwhile with only a limited
      number of nodes, employing a real-life solution with voting-based consensus algorithms should be
      preferable.
      In this paper, we present a survey of many variants of consensus algorithm inside Blockchain, which
      could be categorized into two main types. The first type is the proof-based consensus algorithm, which
      is often used in public Blockchain. The second type is the voting-based consensus algorithm, which is
      often used in private and consortium Blockchain. The rest of this paper is organized as follows: Section
      2 overviews some of the main entities inside Blockchain. Section 3 presents the main content of the
      paper about different consensus algorithms, which have been researched and proposed in Blockchain.
      Section 4 discusses the proof-based and voting-based consensus algorithms. Finally, Section 5
      concludes the paper.
      2. Overview of Blockchain
      This section provides an overview of Blockchain, which includes the transactions verification and
      block architecture inside Blockchain.
      2.1 Transactions Verification
      The first work that every system has to do is to verify the identity of the sender, to make sure of one
      thing: the transaction between the sender and the receiver is requested by the sender, and not by anyone
      else. For example, when Bob sends Alice 10 dollars, then the request of this transaction comes to a
      third-party verifier; this middleman has to make sure that this message does indeed come from Bob.
      Fig. 1 shows an overview of this verification. In order to do this work, two definitions are employed:
      public and private keys [20], which are known as digital signatures. When any user makes a transaction,
      he or she has to use his or her private key to “sign” the transaction, which could be understood that the
      transaction and his or her private key are used as inputs to a sign function to create a signature. In
      Bitcoin, the algorithm used for creating a signature for each transaction is the elliptic curve digital
      signature algorithm [21]. Then the transaction combines with this signature to become a request
      A Survey about Consensus Algorithms Used in Blockchain
      104 | J Inf Process Syst, Vol.14, No.1, pp.101~128, February 2018
      transaction. The verifier will check if this entity belongs to the correct person or not, by using the
      sender’s public key, which is known by everybody. Afterward, the transaction, sender’s signature, and
      his or her public key will be inputted together to a verify function to get the result: true or false. If the
      result is true, then the requester is the true sender in the transaction, and vice versa. Because the
      signature in each transaction contains 256 bits, if anyone wants to fake this signature to make a
      fraudulent transaction, he or she has to guess 2 256 cases, which is impossible.
      Besides checking the validity of the sender, the verifier also has to check the validity of the transaction
      as to whether the sender has enough money to send to the receiver, or not. This work could be done by
      looking at the ledger, which holds information about every past successful transaction.
      Fig. 1. How a verifying system checks if the transaction is requested by the true sender.
      2.2 Blockchain Architecture
      As mentioned before, the key phenomenon giving rise to the name Blockchain is the series of blocks,
      which connect sequentially to each other like a chain. Each block contains many transactions, which are
      validated, as shown in the previous section. Fig. 2 describes an example of the Blockchain. In Fig. 2,
      only some main entities inside the block header are described.
      Giang-Truong Nguyen and Kyungbaek Kim
      J Inf Process Syst, Vol.14, No.1, pp.101~128, February 2018 | 105
      Fig. 2. An example of Blockchain [22].
      Specifically, Fig. 3 describes the architecture inside a block. Besides the list of transactions contained
      inside the block, the block contains some fields in the block header:
      •  Prev_Hash: this field can be known as a reference to parents, which is a link of a block to its
      previous one in the chain. All the information inside the previous block will be inputted to a
      hash function to get a value, then this value will be assigned to the field Prev_Hash in the new
      block. In Bitcoin, a 256-bit hash function is used to get this value [23].
      •  Timestamp: the time when the block was found.
      •  Tx_Root: this field, which is also known as the Merkle root [24], contains the hash value of all
      validated transactions of the block. As seen from the example in Fig. 2, all the transactions are
      hashed into a hash value; then they combine with each other pair-by-pair, and are inputted to
      another hash function. This work is repeated, until there is only a single entity, which stands for
      the Merkle root.
      •  Version: this field contains the protocol version used by the node proposing the block to the
      chain.
      •  Nonce: this field is used in PoW, which proves the efforts that a node has paid for getting the
      right to append his block to the chain. This field will be presented in the next section.
      •  Bits: this field indicates the difficulty level of the PoW, which will be introduced in the next
      section.
      Fig. 3. The fields inside a block.
      A Survey about Consensus Algorithms Used in Blockchain
      106 | J Inf Process Syst, Vol.14, No.1, pp.101~128, February 2018
      3. Blockchain Consensus Algorithm
      This section will finish some definitions that are offered in the previous sections without much
      clarification, like the nonce field, bits field in Section 2.2, and PoW which is proposed for appending a
      new block to the chain. Further, the main focus of this section is on how nodes in the verifying network
      agree with each other about the ledger that they hold. This section is divided into two main sub-
      sections: proof-based consensus algorithm and vote-based consensus algorithm.
      3.1 Proof-Based Consensus Algorithm
      This subsection introduces the proof-based consensus algorithm. The original work is PoW,
      proposed by Nakamoto [2]. To date, many variants of proof-based consensus algorithms have been
      proposed, which are based on PoW, PoS, their hybrid form, and other variants that are made
      independently from these two major ones. The basic concept of proof-based consensus algorithm is that
      among many nodes joining the network, the node that performs sufficient proof will get the right to
      append a new block to the chain, and receive the reward.
      3.1.1 PoW-based consensus algorithm
      3.1.1.1 Original proof of work
      As mentioned, in the Blockchain network, if every node tries to broadcast their blocks containing the
      verified transactions, confusion could possibly arise. For example, consider a transaction that is verified
      by many nodes, who will then put it into their blocks, and broadcast to other nodes. If the broadcasting
      work is free, this transaction could be duplicated in different blocks, then the ledger is meaningless. In
      order to get agreement between all nodes about the newly added block, the PoW requires each node to
      solve a difficult puzzle with adjusted difficulty, to get the right to append a new block to the current
      chain. The first node who solves the puzzle will have this right.
      Specifically, before solving this puzzle, all the verifying nodes would have to put their verified
      transactions, as well as other information like Prev_Hash and Timestamp, into a block. Then they start
      solving this puzzle, by guessing a secret value, which is the nonce field as introduced in Section 2.2, then
      put it into the block. All the information inside the block header will be combined together, and
      inputted to an SHA-256 hash function [25]. If the output of this function is below a given threshold T,
      which is designated by the difficulty, the secret value is accepted. Otherwise, the node has to make
      another guess of the secret value, until he gets the answer. The difficulty of the puzzle will be adjusted
      after every 2016 blocks are appended, so that the average speed for adding a new block in the chain is 1
      block per 10 minutes. Also, the more difficult the puzzle is, the smaller the threshold T is. Fig. 4
      describes the processing for handling the guessed value. Thanks to the usage of SHA-256, guessing this
      value is extremely difficult, which makes every node guess many times to get the answer, unless they are
      lucky enough. Because of the efforts paid for guessing the right value, this work is called the PoW. Also,
      the node joining the network using PoW can be called a miner, and the action of finding a suitable
      nonce is called mining.
      Giang-Truong Nguyen and Kyungbaek Kim
      J Inf Process Syst, Vol.14, No.1, pp.101~128, February 2018 | 107
      Fig. 4. The process for handling with the nonce: guessed secret value.
      When a node finds the secret value, he broadcasts his proposed block with this value to other nodes,
      to notify them that the answer has been found. Right after that, all the miners receiving this message,
      who have still not found the secret answer for their puzzles, will stop guessing. Instead, they check the
      broadcasted block for whether all the transactions are valid; if the block contains the Prev_Hash value is
      the hash value of the last block in their chain, the validity of the nonce field … If all the verifications are
      correct, then these nodes will append the proposed block to their current chain, and re-start guessing
      the secret value, by repeating the steps above again.
      However, there is a rare case when more than 1 miner finds the answers for the puzzle, before it being
      noticed that another miner has also found another suitable answer. At that time, these miners will still
      broadcast their block with the found nonce. Then, other miners who receive the first coming block will
      ignore the others coming later. This work leads to the forking problem: in the verifying network, there
      are different chains of blocks (they should be the same). Satoshi proposed that those miners will keep
      mining a new block on their forks, until one fork is made longer than the others. So at this time, all
      nodes have to follow this longest fork. Fig. 5 describes the forking problem and the PoW solution to
      handle it. Whenever a block is recognized in the chain by all the nodes, the miner appending this block
      will receive some bitcoins as a reward.
      Fig. 5. How Bitcoin handles the forking problem.
      A Survey about Consensus Algorithms Used in Blockchain
      108 | J Inf Process Syst, Vol.14, No.1, pp.101~128, February 2018
      3.1.1.2 Variants based on PoW
      Unfortunately, there are many works and research efforts that state the drawbacks of PoW, which
      include some security issues and usage issues. Therefore, many variants are made to mitigate those
      drawbacks.
      Thanks to modern hardware, the block appending speed increases day-by-day, which makes the
      difficulty of the puzzle harder. Therefore, in order to be the first puzzle solver, the miners have to invest
      more in the hardware. This investment results in other miners, who do not have good condition, being
      unable to compete effectively. Tromp [26] have proposed replacing puzzle work with an idea employing
      the Cuckoo hash function [27], which allows miners to pay fewer efforts, but win the right to append
      the block easier. The authors’ idea is using a hash table with two different hash functions that have all
      the possible results findable on the hash table. Then, some values are inputted to these hash functions,
      which results in two positions in the hash table. If one of the two positions is blank, the hashed result
      will be put into one of them. But if none is blank, then the newly hashed result will remove the old one
      in the hashed position of the first hash function, and replace it. Afterwards, the old replaced result is
      inputted to the two hash functions above, and the procedure is repeated as before. This repetition will
      be done until a definite loop is made, or there is no longer a blank position in the hash table. The work
      of the Cuckoo hash function can create a graph, in which the vertices are the hashed position or the
      replaced position, with edges being the values that have been removed. To replace the puzzle work in
      the original PoW, a miner will have to guess many nonces, which are then inputted to the defined hash
      functions. When the graph created by these guessed nonces has sufficient cycles, the miner will
      broadcast his block with his guessed nonces inside.
      King [28] proposed the idea that instead of finding a meaningless nonce satisfying the below-
      threshold requirements, all the miners will have to find the longest chain of primes, which has to satisfy
      some requirements. The first requirement is its length has to be larger than a given value. Then the
      second requirement is that it has to be in the form of a Cunningham chain [29]. Finally, it has to have a
      defined origin value; which is the center of the two first primes in the chain, being divisable by a
      required number. When a node broadcasts his block, other miners will check this chain by using an
      algorithm called the Fermat Primality Test [30]. Besides the main aim of verifying the transactions, this
      kind of PoW variant is also supposed to dedicate to mathematics by finding the distribution of the
      Cunningham prime chain.
      Being proposed by many researches, one of the PoW’s drawback is a problem called the Double
      spending attack [31], whose script is described in Fig. 6. In short, an attacker would try to reverse a
      transaction that has been verified by some nodes, by making another transaction that could make the
      first one invalid in another fork, then try his best to make this fork longer than the others. In order to
      do this work, he or she has to have at least 51% computing power of the verifying network [32].
      Therefore, the double spending attack can also be called the 51% attack. It is quite difficult for any
      individual node to have such computing power.
      However, with the appearance of so-called pool mining [34], this kind of attack could be possible. In
      pool mining, instead of each individual miner trying to guess the nonce value, they gather into a group,
      then vote for a pool operator and find the nonce together, which makes the work much easier. The
      rewards would appear in a place called the coin-base, so that afterwards, every miner joining this pool
      can receive their incentives, which are equal for each of them. Eyal and Sirer [35] have presented the
      Giang-Truong Nguyen and Kyungbaek Kim
      J Inf Process Syst, Vol.14, No.1, pp.101~128, February 2018 | 109
      risk of a 51% attack with this kind of mining group. They proposed a method to prevent this kind of
      risk: before finding the nonce of the block, every node has to own the private signature of the coin-base.
      Then they have to sign this signature in their created blocks. This work is considered to be too
      dangerous, because the miners inside the pool can freely transfer the rewards to someone else [36].
      Otherwise, if the private signature is not provided, this group has to solve an extra PoW puzzle with
      different difficulty, which is much more difficult than a single puzzle. When the block header with a
      found nonce satisfies the first requirement, the output value of the SHA-256 hash function will be
      inputted into this function again to satisfy another requirement like before, with different difficulty.
      Fig. 6. A script for double spending attack [33].
      In order to discourage pool mining, Miller et al. [37] have proposed a mechanism for changing
      original puzzles into so-called non-outsourceable puzzles, which provide the miner inside any pool with
      the chance of winning the rewards, without making any effort to solve the puzzle. This kind of puzzle
      evolves using a signing key, which could be exploited to execute illegal work against the pool.
      Besides the security issues, PoW is supposed by Eyal et al. to be unsuitable for real-time payment [38].
      Consider a case when a person goes out and buys a cup of coffee, then because of the creating speed of a
      block, has to wait for around 10 minutes to have his or her coffee, because the sellers need nodes to
      verify his or her payment. Therefore, the need to reduce the latency for transactions is very necessary.
      Two possible solutions have previously been proposed: increasing the block size for containing more
      transactions, and reducing the difficulty for solving the puzzle. While the former takes longer time to
      propagate the block on the network, the latter reduces the time for creating a block, but could lead to
      inconsistency forking of the chain and double spending attack. Eyal et al. [38] have proposed a new
      consensus model called Bitcoin-NG, which separates the traditional block into two different kinds,
      called key block and micro block. When a miner finds a suitable nonce for his puzzle, he will broadcast
      his key block to other miners, and become a so-called leader, until another miner finds another suitable
      nonce. During the time of being leader, this node will publish some micro blocks that contain
      A Survey about Consensus Algorithms Used in Blockchain
      110 | J Inf Process Syst, Vol.14, No.1, pp.101~128, February 2018
      information about the transactions. The transactions can be verified quicker, because while waiting for
      a new leader to create a new key block, there could be many micro blocks created.
      Sompolinsky and Zolar [39,40] suggested reducing the time for appending a new block to the chain
      with a strategy for handling the fork and preventing the double spending attack problem. This so-called
      GHOST strategy keeps all the forking blocks that have not been chosen for the main chain. Then
      instead of choosing the longest fork, the one with the most PoW contributing to it will be chosen. Fig. 7
      describes this choosing strategy. The figure shows that the proposed GHOST protocol makes the main
      chain “defeat” the attacker chain, because it contains more blocks, which proves that there is more PoW
      contributing to it.
      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].
      Liu et al. [41] have proposed a generalized Proof of Work consensus algorithm based on PoW. The
      block is not appended by a single miner, but by a committee of miners with a luck factor. The difficulty
      in this work is set much easier than the original PoW, which enables the miners to be able to find many
      possible nonces with their computing power. In each round of appending, each miner will have to find
      as many nonces as possible for their created block. After any nonce is found, its finder will send the
      block, including this nonce, to a committee, including some other miners, who have the responsibility
      to validate the received block, and put the valid block into a temporary array. At the end of the round, a
      random number is chosen. The miner having the block whose index in the array is equal to this random
      number is chosen to not only append the block to the chain, but to also be a new member in the
      committee. After a duration, some members in the committee will be rotated, to make sure that the
      number of members is not too large. After each round, the rewards will be given equally to all the
      members inside the committee.
      3.1.2 PoS-based consensus
      The proposed PoW is supposed to be unfair: while some miners owning modern and powerful
      equipment could find the suitable nonce easier, others with poorer condition could find it very difficult
      to be the first one to find a suitable nonce. PoS is supposed to deal with this inequality. Being firstly
      introduced and discussed in Bitcoin forum from 2011 [42], PoS has had some variants and research
      contribution to it. The basic idea of these consensus algorithms is using the stake to decide who will get
      Giang-Truong Nguyen and Kyungbaek Kim
      J Inf Process Syst, Vol.14, No.1, pp.101~128, February 2018 | 111
      the chance to mine the next block of the chain. Using stake as a proof has an advantage: anyone who
      owns much stake would be more trustful. He or she would not want to perform any fraudulent actions
      to attack the chain that contains much of his or her profits. Furthermore, using PoS would require any
      attackers to own at least 51% of all stakes in the network to perform a double spending attack, which is
      very difficult.
      There are currently two popular kinds of consensus using PoS: the kind using pure stake to make
      consensus, and the hybrid kind, which combines PoS and PoW.
      3.1.2.1 Pure stake-based consensus
      The pure PoS form could be seen in Nextcoin [8] (aka. Nxtcoin, http://nxtcrypto.org/). In this
      platform, the more stake a miner owns, the more chance he has to mine a new block. Specifically, if
      there are a total b coins from all the miners, and miner M owns a coins (a < b), the chance for miner M
      getting the right to mine a new block is a/b. The lucky miner picking work is executed every 60 minutes,
      and this work is made randomly based on the stake of each miner, as mentioned. Once a miner gets the
      chance to mine a new block, he will verify the transactions, collect them into a block, then broadcast it
      to the other miners, and receive the rewarding fee.
      Being similar to Nextcoin, Bentov et al. [43] proposed a method for finding the miner based on the
      pure stake he owns: the more stake a miner has, the more chance he will get to become the block
      appender. However, the miner getting this chance is chosen based on the state of the block. Also they
      proposed a definition called follow-the-Satoshi procedure, and they considered a Satoshi value, which is
      the smallest currency unit. Follow-the-Satoshi procedure will get input as a Satoshi index, which is
      between 0 and the total number of Satoshi, then it will find the block that created this Satoshi, which
      could be understood as the rewards for a miner to create this block. Afterwards, all the transactions
      including this satoshi will be found out, to identify the last owner of this satoshi, who will become the
      one appending the next block. The work of choosing the Satoshi is based on a hash function, which
      takes some inputs based on the current status of the chain. The first input parameter is a value that is
      gotten from a so-called comb function owning inputs as some bits. Each of them is the first bit gotten by
      hashing each existed block in the chain sequentially. The second input is taken from the number of
      current blocks in the chain, and the third input is a random integer. Bentov et al. [43] also proposed a
      solution to handle the problem, in which the owner of a chosen Satoshi does not create a block when he
      has the chance. If a chosen satoshi after 3 consecutive chosen times could not experience a new created
      block, it will be blacklisted. Function comb is chosen to satisfy that it would be difficult to influence the
      choosing of satoshi, which has been issued by Russell and Zuckerman [44] with collective sampling, and
      Ben-Or and Linial [45] with leader election and collective coin-flipping.
      Kiayias et al. [46,47] also employed the idea of Bentov, follow-the-Satoshi procedure to execute the
      PoS consensus. They claim that the leader election should be done randomly by calculating an entropy
      value. This calculation should be secure enough, so that it would be difficult to simulate the protocol to
      predict the calculation, and manipulate the leader election. Kiayias et al. considered the work of Bentov
      et al. [43] for leader election as a way to calculate entropy based on the current status of the Blockchain.
      The first difference of Kiayias et al.’s work from Bentov et al.’s is that they snapshot the stake of each
      stake holder after an interval called an epoch. In each epoch, a collection of stake holders will be chosen
      to execute the so-called coin-flipping protocol. Based on these results, the leaders and the stake holders
      A Survey about Consensus Algorithms Used in Blockchain
      112 | J Inf Process Syst, Vol.14, No.1, pp.101~128, February 2018
      executing this protocol in the next epoch will be chosen, which makes sure that the entropy calculation
      is difficult to simulate. Also, in order to raise the equality, the leader will have to create the block only,
      while the work of adding transactions belongs to a group of stake holders called endorsers, who are
      voted like the leader. The rewards will be divided equally to those leader and endorsers.
      Using the stake as a proof for voting, not for getting the chance to mine a new block, is the idea of
      Larimer [48]. This kind of consensus algorithm is called delegated proof of stake. In this platform, there
      are many people who hold stake, and they will have to vote for a delegation, which includes some
      “witnesses”, who are miners verifying the transactions and maintaining the chain. The more stake a
      person owns, the more powerful voting he has to assign the witness. After the verifying congress is
      made, the witnesses inside will verify the transactions, and produce blocks, including the valid ones.
      The list of witnesses is always shuffled. With the creating speed of 2 seconds per block, the witness in
      the list will have to produce blocks sequentially. If any witness fails to produce his block, he would
      potentially be removed from the delegation. Whenever a witness creates a block to append to the chain,
      he will receive a reward.
      3.1.2.2 Hybrid form of PoW and PoS
      Being officially introduced in a paper by King and Nadal [49], PPcoin could be considered as the first
      variant of PoS, but it still uses PoW. These authors have proposed a definition called the ‘coin age’ of
      each miner, which is calculated by his stake multiplied by the time that the miner has owned it. For
      example, Bob receives 10 coins from Alice and keeps them for 10 days; consequently, he has 100 coin-
      day, and if he sends 2 coins to anyone, the coin age of these 2 coins accumulated will be destroyed. In
      order to get the right to append a new block to the chain, the miner creates a kind of block called a coin
      stake, which like before, holds many transactions, but includes a special one from that miner to himself.
      The amount of money spent on this transaction will provide the miner more chance to mine a new
      block. Afterwards, he will have to do a puzzle, like PoW. The more money he spends on the transaction,
      the easier the puzzle he has to solve. If any miner solves the puzzle first, he will get 1% of the amount of
      coins he has spent in the transaction, but the coin age accumulated by these coins will be reset to 0.
      Being dissimilar to King and Nadal [49], Vasin [50] do not employ coin age with their Blackcoin,
      because they suppose that using coin age could provide the attacker the chance to accumulate enough
      value to cheat the network. Worse yet, there could be some miners who hold their stake until they have
      a lot of coin age, while staying offline from the verifying system. Therefore, Vasin [50] propose using
      the raw stake instead of coin age for providing miners the chance to mine a new block, which could
      encourage more nodes to be online to get the rewards. Being noticeable with the offline miner, Ren [51]
      propose using an exponential decay function with the coin age: the more the miner waits for the
      increase of the coin age, the less speed of increase it has.
      The problem of double spending attack is again shown by Duong et al. [52]. The problem with
      miners owning more than 51% mining power raises a high alert for the security of Blockchain. They
      proposed a method for mitigating the double spending attack by combining PoW and PoS. The aim of
      this action is to make sure that even if a miner owns more than 51% of the mining power, he still does
      not have much chance to make a fraudulent action. These authors propose using the PoW first for
      choosing a winner, who is the first one getting the answer of the puzzle. Subsequently, this winner will
      not only append a block called PoW block to the chain as usual, but he will also provide a basis to
      Giang-Truong Nguyen and Kyungbaek Kim
      J Inf Process Syst, Vol.14, No.1, pp.101~128, February 2018 | 113
      choose another miner who owns stake. This basis is: if the return value of a hash function, whose input
      parameters are the newly appended PoW block and stake owner’s private key, is below a threshold, the
      chosen miner will have the chance to append a so-called PoS block to the chain. Duong et al. [52] claim
      that each PoS block is linked to a single PoW block, and each PoW block is linked to a previous PoS
      block. Consequently, it is difficult to make a double spending attack. The reason is that assuming that
      an attacker could own more than 51% of the computing power, then he could get the right to be the
      miner appending the illegal PoW block to the chain. However, right after that, there is still a PoS block
      appended by another miner chosen by the mentioned base. This stake miner will see the longest chain
      at that time, and realize that the latest one is a PoS block, which he could not append his PoS block to.
      As a result, the attack fails. The double spending attack is supposed to happen only when the attacker
      owns not only more than 51% of the computing power, but also more than 50% of all the stake holders.
      This kind of consensus is not based on the amount of stake, but only for miners owning stake.
      As an improvement of [52], Chepurnoy et al. [53] have pointed out a problem with their former
      research. Firstly, the executing environment is static, because at each round, the invested physical
      hardware for mining the resources and virtual resources known as stake remain the same; which
      assumption does not equate with reality. Also, the usage of stake has not been employed, which would
      not be fair for the stakeholders who own more stake than others. The authors suggest that there should
      be a difficulty adjustment for both the PoW and PoS when the environment changes. Therefore,
      Chepurnoy et al. [53] propose adjusting the difficulty based on the environment—the rate of block
      creation. Specifically, their proposed difficulty for proof of work follows the original Bitcoin’s one, while
      the PoS difficulty is inverse to the stake that the stake owner has. For example, if a miner owning 1 coin
      has the hash value mentioned from [52] below threshold t, then another miner owning b coin will only
      have to satisfy the hash value below t * b.
      Bentov et al. [54] propose a solution called Proof of Activity. This combines PoW and PoS in order to
      not only solve the double-spending attack, but also handle some tragedies made by PoW called the
      tragedies of the common. The first mentioned tragedy is that only the miners solving the puzzle get the
      reward, while the others who have the role of preserving the ledger, update it and validate the new
      block; they do not receive anything. The second one is that miners can co-operate with others to raise
      the transaction fee to be high to charge the users. This action could make the Blockchain useless,
      because nobody would want to use it. In order to deal with these tragedies, these authors proposed
      creating an empty block by PoW first: all the miners will try to find a nonce with a block without any
      transactions. After finding a suitable nonce, the miner will broadcast the block containing it to other
      miners, who will verify the validation of their received ones. Also, they will check if they are the winner
      of another lottery, which is designed based on the block they receive. This lucky chance is like follow-
      the-Satoshi procedure in [43]. A hash function is suggested to be used N times, which input parameters
      are the hash value of the received block, the hash of the latest appended block, and a random number,
      which is randomized N times. N miners who see that they own the N chosen Satoshi will continue the
      work: the (N – 1) first miners will sign into this empty block, their signature proving that they own the
      chosen Satoshi, then broadcast this signature. The last miner will include not only the required
      signature, but also as many transactions as he wants, then broadcast the block to other miners. The
      block creater and N chosen miners will get equal rewards. Besides preventing a double spending attack,
      this kind of consensus also encourages miners to stay online to collect the rewards.
      A Survey about Consensus Algorithms Used in Blockchain
      114 | J Inf Process Syst, Vol.14, No.1, pp.101~128, February 2018
      3.1.3 Comparisons between PoW, PoS and their hybrid forms
      Table 1 shows the comparisons between PoW, PoS and their hybrid form. As can be seen, using
      electric power to guess the secret value executing PoW, a lot of money should be spent on not only
      hardware devices, but also on the energy to execute them. In contrast, PoS does not employ any puzzle,
      so these two investments are much lower.
      Table 1. Comparisons between PoW, PoS, and their Hybrid form
      Criteria  PoW PoS
      Hybrid form of
      PoW and PoS
      Energy efficiency  No  Yes  No
      Modern hardware  Very important  No need  Important
      Forking
      When two nodes find the
      suitable nonce at the
      same time
      Very difficult
      Probably
      Double spending
      attack
      Yes
      Difficult
      Yes, but less serious
      than in PoW
      Block creating speed  Low, depends on variant Fast  Low, depends on variant
      Pool mining
      Yes, but it can be
      prevented
      Yes, and it is difficult to
      prevent
      Yes
      Example  Bitcoin  Nextcoin  PPcoin, Blackcoin
      In PoW, forking can happen if two miners find a suitable nonce at the same time. Meanwhile with
      PoS, it is very difficult, happening only when a miner can own up to 51% of all stake in the whole
      verifying network [49]. By employing both PoW and PoS, although their hybrid form can still make a
      fork, the probability of causing a double spending attack is much lower, compared to the pure PoW.
      Considering the speed of creating a new block in the chain, overall almost all variants of PoW require
      much time to append a new block to the chain, while with PoS, the block creating speed is lower,
      because no node has to solve any puzzle.
      What could make PoS less attractive is the work with pool mining: for PoW, the miners joining pool
      are trackable, and the fraudulent work is preventable, as in [35,37]. But in PoS, it would be very difficult
      to prevent the miners inside a pool delegating their stake to a single miner as pool operator.
      3.1.4 Other kinds of proof-based consensus algorithm
      Blocki and Zhou [55] pointed out the same problem as King [28]: The PoW wastes too much energy
      in finding the nonce, and also it is meaningless in everyday human life. Worse yet, it is not fair for the
      miners having poorer condition to purchase modern hardware, which makes their chance of mining a
      new block very low. Therefore, Blocki and Zhou [55] proposed using some kinds of puzzle for
      education and social activities, which would be easy for computers to solve, but difficult for human to
      solve. It is for the human to solve the puzzle to mine a new block, instead of using hardware. This
      difference would be fair for everybody, whether they could or could not invest in new modern
      equipment.
      Giang-Truong Nguyen and Kyungbaek Kim
      J Inf Process Syst, Vol.14, No.1, pp.101~128, February 2018 | 115
      Proof of burn [56] and proof of space [14,57] are other kinds of proof-based consensus algorithms
      that do not employ the idea of PoW and PoS. In proof of burn, miners have to send their coins to an
      address to “burn” them, which means these coins could not be used by anyone else. The miner who
      burns the largest amount of coin during a duration will be the one getting the right to mine a new block.
      With Proof of Space, miners will have to invest their money on hard disk, which is much cheaper than
      computing devices for PoW. During the work, the proof of space algorithm will generate many large
      datasets called plots on the hard dish. The more plots a node has, the more chance he will get to mine a
      new block.
      Proposed by Intel [58], proof of elapsed time [12] is used in a blockchain platform called Sawtooth
      Lake [59]. This kind of consensus is executed in a special environment called the trusted execution
      environment (TEE) [60], with a special device of Intel known as Intel Software Guard Extensions (XGS)
      [61]. In order to conduct the consensus algorithm, each miner will at the same time request a wait-time
      from a trusted enclave, which is also known as a trusted function inside XGS hardware. Subsequently,
      all the miners will receive their responded wait-time from the enclave, and together will wait until their
      received time elapses. When a miner waits enough time, but has found no one has finished the waiting
      match, he will broadcast to all other miners that he is the winner, which provides him a chance to mine
      new block. In short, the miner owning the shortest received wait-time will be the one to mine a new
      block. In order to support this kind of consensus, two functions are used: function CreateTime will
      inform the miners of the time they need to wait, and function CheckTimer will check whether or not
      the miner has waited enough time. Because this consensus is executed in TEE provided by XGS devices,
      it is supposed that cheating with the work of the two above functions is very difficult.
      Milutinovic et al. [13] proposed a kind of consensus, which is also executed in TEE and with XGS
      devices, called proof of luck. To execute it, after all the ledgers from all the miners are synchronized,
      each miner will create for themselves a new block to append to their current chain, then a random
      number ranged from 0 to 1 will be assigned for each created block, which could be considered a lucky
      value. All of the nodes will have to agree that the chain with the total largest lucky value would be the
      main chain. As a result, proof of luck is considered to be fair for all the miners. Furthermore, it would
      be very difficult to make attacks, like double spending attack, because the attacker should be very lucky
      to perform their illegal actions successfully.
      Multichain [62,63] is a kind of consensus algorithm, which is quite similar to PoW with the work of
      mining and fork handling. However, multichain does not apply PoW for choosing the node to append
      block to the chain; instead, it applies a round-robin schedule to make nodes create blocks in rotation.
      Specifically, a parameter p (0 < p < 1) called the mining diversity is used. In each phase, all the nodes
      have to wait for a duration, then start checking their rights to append new block to the chain. If among
      p*N (N is the number of participating nodes) blocks that are created most recently, no block is created
      by a supposed node A, then node A could append his proposed block to his current chain, then
      broadcast this block to other miners. In the case that fork happens, like PoW, the longest one would be
      chosen.
      3.2 Voting Based Consensus
      In order to execute the voting based consensus algorithm, the nodes inside the verifying network
      should be known and adjustable, so that they can exchange the message easier. This is the main
      A Survey about Consensus Algorithms Used in Blockchain
      116 | J Inf Process Syst, Vol.14, No.1, pp.101~128, February 2018
      difference compared to proof-based consensus algorithms, which nodes are often free to join and
      withdraw from the verifying network. Also, in voting-based consensus algorithm, besides maintaining
      the ledger, all the nodes in the network would have to verify together the transactions or blocks. They
      will communicate with others, before deciding to append their proposed blocks to their chain or not. In
      almost all of these variants, nodes are required to see at least T nodes having the same proposed block
      with them to do the appending work (T is a given threshold).
      Executing voting-based consensus algorithms is very similar to traditional methods for tolerating
      faults used in the distributed system [64]. Therefore, voting based consensus should be designed to
      resist some bad cases:
      • Some nodes are crashed.
      • Some nodes are not only crashed, but also subverted.
      In crashing cases, nodes will wait for the messages from other nodes. However, there are some nodes
      that do not run, then the normal nodes do not receive enough evidence to make the decision. Therefore,
      in order to prevent the crashing case with f nodes, there should be at least f + 1 nodes operating
      normally [65].
      In subverting cases, nodes could act strangely, which could make the results inaccurate. This problem
      can be presented by a classical problem called Byzantine generals proposed by Lamport et al. [66]: a
      group of Byzantine generals attacked an enemy’s camp. They decided to divide their army into N
      groups led by N generals, which would attack the enemy from different sites. If they attacked at the
      same time, they would win; otherwise, they would lose. Consequently, they had to make an agreement
      with each other about the attacking time by exchanging messages, and following the decision of the
      majority. Unfortunately, there were some traitors inside the general group, and they wanted to cheat
      other generals by telling different decisions to the others. Therefore, the results could be made
      inaccurate, which made some generals attack, while others did not, leading to failure. Lamport et al.
      [66] have proved that in order to tolerate f subverted generals, there should be at least another 2f + 1
      normal generals to accompany them.
      Coming back to the Blockchain, when each node executes the consensus work, some nodes can be
      subverted, which sends different results to other nodes. Then the worst case is the network could not
      resist them, causing the ledger to be different in different nodes. Considering the crashing cases, if
      nodes are crashed, then they could not send their results to other nodes, which makes it difficult to
      make the final decision.
      Consequently, based on these bad situations, the voting based consensus algorithms could be
      classified into two main kinds:
      • Byzantine fault tolerance based consensus: a kind of consensus that could prevent the cases of
      crashing nodes and subverted nodes.
      •  Crash fault tolerance based consensus: a kind of consensus that could only prevent the cases of
      crashing nodes.
      All consensus algorithms in these two sub-categories will have to make a trust assumption: among N
      nodes, there should be at least t nodes (t < N) operating normally. While in crash fault tolerance-based
      consensus, t is usually set equal to [N/2 + 1], in Byzantine fault tolerance-based consensus, t is usually
      assigned equal to [2N/3+1].
      Giang-Truong Nguyen and Kyungbaek Kim
      J Inf Process Syst, Vol.14, No.1, pp.101~128, February 2018 | 117
      3.2.1 Byzantine fault tolerance based consensus
      The famous Hyperledger Blockchain platform [67] has been used by many enterprises. IBM is one of
      them, with Hyperledger Fabric [68]. A kind of Byzantine fault tolerance called Practical Byzantine Fault
      Tolerance (PBFT) proposed by Castro and Liskov [18] was used for Hyperledger Fabric [15,69]. In
      PBFT, there are two kinds of nodes: A leader node, and some validating peers (nodes); and these peers
      will execute some rounds for appending a block to the chain, which is described in Fig. 8 [69]. Initially,
      the clients send their requests for transactions to their corresponding validating peers. From here, the
      receiving peer will validate the transactions, then broadcast them to other peers, including the leader.
      After the number of transactions reaches a threshold called batch size, or after an interval, the leader
      node will order the transactions by their created time, putting them into a block. Afterwards, three
      phases of PBFT are executed. Firstly, in the Pre-prepare phase, the leader broadcasts his proposed block
      to other peers. They will receive and store the block locally. Then in order to make sure that the
      received block from the leader is the same, they make a double-check by broadcasting it in the Prepare
      phase and Commit phase. After the Prepare phase, if any node receives the blocks, which are the same
      as what they have stored locally before, from more than 2/3 of all the nodes, they will execute the
      Commit phase. Then the same procedure is recorded after the Commit phase, which is the requirement
      for any node to execute the transactions in the proposed block, and append it to their current chains.
      Fig. 8. Rounds for verifying transactions in Hyperledger fabric. Adapted from Sukhwani et al.,
      “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, with the permission of IEEE [69].
      A Survey about Consensus Algorithms Used in Blockchain
      118 | J Inf Process Syst, Vol.14, No.1, pp.101~128, February 2018
      Another two popular Blockchain platforms, which use Byzantine fault tolerance-based consensus
      algorithms, are Symbiont [70] and R3 Corda [71]. They employ a consensus algorithm called BFT-
      SMaRt proposed by Bessani et al. [72]. Fig. 9 describes this algorithm. Basically, this algorithm is similar
      to PBFT, but uses different names (Propose–Write–Accept vs. Pre-prepare–Prepare–Commit in PBFT).
      Besides executing the consensus work, Bessani et al. [72] also propose a mechanism for storing the log
      of executed operations in a single machine, which is used for gaining the last current state, when a node
      fails, and needs to restart.
      Fig. 9. BFT-SMaRt execution. Adapted from Bessani et al., “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, with the permission of IEEE [72].
      Iroha [73] is another Hyperledger based Blockchain platform, which has the consensus algorithm
      called Sumeragi [74], being “heavily inspired” by Bchain by Duan et al. [75]. With Bchain, all the nodes
      will be arranged linearly, so that a given node will only receive message from his previous node, and
      send messages to his next node in the chain. Because the broadcasting work can be avoided, the load
      among the nodes is balanced, but with the higher cost of time execution and time for reconfiguring if
      faults happen. Being similar to PBFT and BFT-SMaRt, implementing Bchain requires at minimum
      [2N/3+1] nodes operating normally.
      Ripple [76-78] is a Blockchain platform whose consensus algorithm is made by the new Blockchain
      comers. Consequently, Ripple consensus algorithm is supposed to improve on the weakness of Bitcoin.
      In Ripple, the chain of blocks is not used, but rather a raw ledger is employed; and after some verified
      rounds, transactions will be added directly to the ledger. Like the original Bitcoin, this ledger is
      maintained by some nodes, which run Ripple Server Software. Ripple adds new transactions to the
      ledger if they are verified successfully by at least 80% of all servers. To handle the verification of
      requested transactions, Ripple ledger has two main forms: last-closed ledger, which indicates that all the
      transactions in it are verified successfully by sufficient servers (80%); and open ledger, which has
      transactions verified by insufficient servers. To make the verification, instead of broadcasting the
      transactions to others, each server has their own list, called a unique node list (UNL), which includes
      some other servers. Following Ripple, the intersection of UNL by any two different servers should be at
      least 1/5 of all the servers over the network. These servers will only communicate with others in their
      UNL. Initially, in the consensus algorithm, there would be many transactions created by many clients
      broadcasted to some servers. Then they would validate each of the received ones, putting the correct
      ones temporarily in their ledger to change its status to open-ledger. Also, they aggregate all the correct
      transactions into a so-called candidate set. At this time, there would be some rounds to make an open-
      Giang-Truong Nguyen and Kyungbaek Kim
      J Inf Process Syst, Vol.14, No.1, pp.101~128, February 2018 | 119
      ledger to become a last-closed-ledger. In the first round, each server would aggregate all the candidate
      sets from other servers in his UNL into his candidate set, then verify the transactions inside this set. A
      “yes” vote will be put to each of the transactions if they are verified successfully. Subsequently, in the
      next following rounds, any transactions that do not receive enough “yes” votes will be discarded from
      the candidate set (the final rounds require at least 80% of yes votes for each transaction). David et al.
      [59] have stated that in order to maintain the correctness, there should be only a maximum (n–1)/5
      subverted nodes among n nodes in the network.
      As a variant of Ripple, Stellar [79] uses a group, which is similar to UNL in Ripple, called quorum
      slice for communicating between verifying nodes (validator nodes in Ripple). The validator nodes can
      belong to one or many different quorum slices. For a given transaction, if a node wants to confirm a
      given transaction to be valid, he will have to ask the other nodes in his quorum slice. If the transaction is
      verified successfully by all nodes in his quorum slice, he will consider this transaction to be valid. Fig. 10
      describes an example of quorum slices in Ripple, which are organized by hierarchical structure, similar
      to the example in [79]. Considering “Node 1” in the example, it makes a quorum slice with two other
      different nodes in “Group 1”, and another node among all nodes from “Group 2”. Specifically, Nodes
      (1,2,3,5) and Nodes (1,2,4,6) are two of the quorum slices among many in this example. Also, Group 1
      and Group 2 are the top levels; transactions have to be verified first from these two levels. It could be
      imagined that Group 1 contains some banks, while Group 2 consists of some verification services, and
      Group 3 is the set of users using the payment service. In order for Node 10 to verify a given transaction,
      he would have to ask other members in his quorum slice, which could be Node 1, Node 2, and Node 7.
      If all of them agree with this transaction, Node 10 could consider it to be valid.
      Fig. 10. Example of quorum slice in Stellar.
      3.2.2 Crash fault tolerance based consensus
      Motivated by the classical and difficult-to-understand consensus algorithm called Paxos [65], Raft
      [80] is a consensus algorithm that is used by Quorum [81] to tolerate crashes. Being different from
      Paxos, Raft was created to be easier to understand and use in practical systems. Like Paxos, Raft is made
      based on an assumption that every time, [n/2 + 1] of the total nodes work normally. To execute the Raft
      consensus algorithm, verifying nodes can belong to three different roles, which are follower, candidate,
      and leader. These nodes communicate with each other by two main kinds of message: RequestVote for
      voting a leader node, and AppendEntries for transferring the requests to other nodes. Fig. 11 describes
      how nodes change their roles with different situations. Basically, there would be some sequential-
      A Survey about Consensus Algorithms Used in Blockchain
      120 | J Inf Process Syst, Vol.14, No.1, pp.101~128, February 2018
      numbered terms of time, in which a node holding leader role will retain its responsibility until the end
      of the term, then switch back to the follower role. Initially, all the nodes start as follower role. These
      nodes remain in this state, until they do not receive any AppendEntries messages from the leader node
      (there is no leader node at first, or the leader is crashed in the following terms). Then after election
      timeout period, all follower nodes will start election to vote for a leader node, by transferring their role
      to candidate, and increasing the term number. Each candidate elects their wanted leader by
      broadcasting a RequestVote message, accompanied by their current term number. When a candidate
      receives the RequestVote message, first of all, he would have to check if the received term number is
      equal to his current term number; and if his is larger, the received message is discarded. After
      aggregating all the messages, if a node receives the vote from the majority of the candidates, he will
      become leader; otherwise, he will return to the follower role. In the special case that a node could not
      decide who he will be, because he is voted by 50% of all the nodes, the new election round will start
      again. The leader will be recognized by every node, because the RequestVote message is broadcasted.
      Fig. 11. Node's role transition in Raft [80].
      During the consensus execution, the leader receives some requested transactions sent from many
      clients, then he will write them to a list called log entry. Afterwards, he sends to all followers the
      AppendEntries message containing each logged transaction r and the index of the previous transaction
      pi in the list. For example, if the leader sends the 5th transaction, then he will also have to send the 4 th as
      the index of the previous transaction in the list. When a follower receives AppendEntries message, if pi
      is the index of the last transaction he received, he will write r to his log entry list. Otherwise, the leader
      will have to find the latest transaction that he and the contradicting follower have in common, then this
      follower will delete all transactions after the found transaction, and start synchronizing the log entry list
      again with the leader. These processes are made to make sure transactions are ordered the same in all
      verifying nodes. After knowing that the transaction lists are the same in all nodes, the leader node will
      choose an index in the list, then commit all the transactions before this index, which verifies the
      transaction, and put the valid ones into a block. Afterwards, he will append the block into his chain, and
      broadcast the results to other follower nodes in the network, who will see the result, and make the same
      commitment like the leader.
      Another Blockchain platform called Chain [82], employs the crash fault tolerance consensus
      algorithm named federated. In this one, among n nodes in the verifying network, there is a node called
      ‘block generator’, and other nodes called ‘block signers’. The block generator receives transactions from
      Giang-Truong Nguyen and Kyungbaek Kim
      J Inf Process Syst, Vol.14, No.1, pp.101~128, February 2018 | 121
      clients, then verifies each of them, and stores the valid ones in a temporary list. After each duration, the
      block generator will sequentially take some requested transactions to put into blocks, which will be sent
      to all block signers. These signers will validate the received blocks, and sign into them if they are valid,
      then send them back to the block generator. If a block is signed by more than m (m < n) different block
      signers, the block generator will append the block to his current chain, and propose this block to other
      nodes. Following this method, Chain could resist the crash fault if the block signer does not work.
      However, if this case happens with the block generator, the network would be halted.
      4. Discussion
      Table 2 shows some overall comparisons between the proof-based and vote-based consensus
      algorithms. First of all, it is evident that executing the vote based consensus algorithm should not be
      free, which limits the number of nodes in the verifying network. This is because if there are too many
      nodes joining the verifying network, it would be very complicated to exchange messages between them.
      Also, if nodes are able to join freely, it would be impossible to make the trust assumption, which makes
      the ledger unreliable. Meanwhile, with the proof-based consensus algorithm, nodes can join and
      withdraw from the verifying network whenever they want, which makes the number of nodes executing
      the consensus algorithm unknown. Therefore, showing enough eligibility to append a new block to the
      chain is suitable for this freedom to join.
      Table 2. Comparisons between vote-based consensus and proof-based consensus algorithms
      Criterion  Vote-based consensus algorithm Proof-based Consensus algorithm
      Agreement making basement
      From majority of the
      node decisions
      Following nodes performing enough
      proof (PoW, PoS, etc.)
      Nodes can join freely  No  Mostly
      Number of nodes executing  Limited  Mostly unlimited
      Decentralization  Low  Mostly high
      Trust  Less trustful  More trustful
      Nodes identities are managed  Yes  No
      Security threat  Less serious  More serious
      Award  Mostly no  Yes
      Moreover, vote-based consensus is often conducted in private and consortium Blockchain, in which
      the decentralization degree is lower than in public Blockchain with proof-based consensus.
      Consequently, trust in the proof-based one would be higher. Clearly, the more freely that nodes can join
      the verifying network, the more decentralized the verifying network is.
      In contrast, a tradeoff is recorded between the freedom and security issues. The more nodes that join
      the verification network, the more risk the verification network has. In vote-based consensus, all the
      nodes are manageable, which makes it safer to control the security risk. While with the proof-based
      consensus algorithm, some threats, like double spending attack, could always possibly happen.
      Finally, with proof-based consensus algorithm, in order to encourage nodes to maintain the ledger,
      A Survey about Consensus Algorithms Used in Blockchain
      122 | J Inf Process Syst, Vol.14, No.1, pp.101~128, February 2018
      award is often given to any nodes who mine a new block. Following Satoshi, the more blocks that are in
      the chain, the fewer awards a node can receive after mining a new block in the future. We suppose that
      lately, if the mining award and the incentive for verifying transactions are too small, nodes will have no
      motivation like current time to maintain the ledger anymore. Meanwhile, with vote-based consensus,
      there is no necessity to give any award to a node. Using decentralization to increase the reliability is the
      only aim for this kind of algorithm.
      To wrap up all the consensus algorithms surveyed in this paper, Table 3 is presented with brief
      overview of each algorithm.
      Table 3. Summary of surveyed consensus algorithms in this paper
      Brief working mechanism description
      Proof-based consensus algorithms
      PoW-based consensus algorithms
      Pure PoW [2]
      Nodes have to solve a difficult puzzle to get the right to append
      new blocks to the chain and get the rewards.
      Cuckoo hash function-based PoW [27]
      The puzzle in pure PoW is replaced by another task: finding a
      graph established by a Cuckoo hash function.
      Prime number finding-based PoW [28]  The puzzle is finding a chain of Cunningham prime numbers.
      Double puzzles-based PoW [35]  Two consequential puzzles are created to prevent pool mining.
      Non-outsourceable puzzles [37]
      The puzzle is re-designed so miners inside pool can get all the
      rewards without mining (prevents pool mining).
      Bitcoin-NG [38]
      When a node creates a key block, he could continuously make
      some micro blocks with transactions, until another node creates
      a new key block.
      GHOST strategy [39,40]
      The forking problem is solved by choosing the brand having
      most PoW contributes to.
      Generalized PoW [41]
      Each node will find as many nonces as possible. Then the block
      adder will be chosen based on a lucky factor with their created
      nonces.
      PoS-based consensus algorithms
      Pure PoS (Nextcoin [8])
      After every 60 seconds, a random number is chosen. The node
      who owns the coin whose index is equal to the chosen number
      gets the right to append his proposed block.
      State of the block-based PoS
      Based on the state of the current chain, a random Satoshi
      (smallest currency unit) is chosen. The miner owning this
      Satoshi is chosen to append his proposed block to the chain.
      PoS by coin flipping from many nodes
      Many nodes perform coin-flipping protocol to choose the block
      adder.
      Delegated PoS
      A delegation including nodes will be voted by other nodes. The
      more stake a node owns, the more powerful voting power he has
      to assign the witness. This group will do the main appending
      job.
      Hybrid forms of PoW and PoS
      Coin age-based PoW difficulty
      re-designation (PPcoin [49])
      A so-called coin age is calculated by multiplying the number of
      coins a miner has, and the duration he keeps them. Based on the
      coin age spent on a self-transaction, the node solves a PoW
      puzzle with different difficulty.
      Stake-based PoW difficulty re-designation
      (Blackcoin [50])
      The node solves a PoW puzzle based on the coin he owns.
      Giang-Truong Nguyen and Kyungbaek Kim
      J Inf Process Syst, Vol.14, No.1, pp.101~128, February 2018 | 123
      Table 3. Continued
      Brief working mechanism description
      Coin age with an exponential decay
      function [51]
      Coin age is used again in this algorithm, but the increasing speed
      is lower by the decay function of time.
      Combining PoW and PoS to append
      blocks sequentially [52]
      After the PoW puzzle is solved, the solver appends a new so-
      called PoW block to the chain, and provides a base to choose
      another stake holder to append another so-called PoS block.
      [52] with difficulty adjustment [53]
      The PoW and PoS difficulty from [52] are adjusted with the
      environment.
      Proof of activity [54]
      Initially, a block without transactions is made with a suitable
      nonce. Then, N nodes will be chosen randomly by the stake they
      have. The last one will add transactions to the block.
      Other kinds of proof-based consensus algorithms
      Puzzles designed for human PoW [55]
      The puzzle is designed in a way that is easy for computers to
      solve, but difficult for human to do.
      Proof of burn [56]
      Nodes have to send their coins to an address to mine a new
      block. The miner sending the largest number of coins get the
      chance to mine a new block.
      Proof of space [14,57]
      The algorithm generates some so-called plots. The miner storing
      the most number of plots can mine a new block.
      Proof of elapsed time [12]
      All nodes receive different waiting time duration, and the node
      with shortest duration will mine a new block.
      Proof of luck [13]
      All the nodes make their own blocks with different lucky
      numbers, and append it to their chains. The chain having the
      largest total value of lucky numbers is chosen as the main one.
      Multichain [62,63]  Round-robin is used to choose the block appender.
      Vote-based consensus algorithms
      Byzantine fault tolerance-based consensus
      Hyperledger with practical Byzantine
      fault tolerance [67]
      This consensus algorithm employs three rounds of PBFT to
      double-check that the blocks they will append are the same.
      Symbiont, R3 Corda with BFT-SMaRt
      [70,71]
      This is similar to PBFT, with the support of restoring after any
      nodes crash.
      Iroha with Sumeragi [73,74]
      This algorithm uses chain architecture for nodes to exchange
      messages.
      Ripple [76-78]
      Transactions verified by a node are broadcasted to others in his
      own defined list. Transactions verified by at least 80% of all the
      nodes are appended to the ledger.
      Stellar [79]
      If any transactions are verified to be valid by all nodes in a node’s
      quorum slice, this node will confirm these transactions to be
      valid.
      Crash fault tolerance-based consensus
      Quorum with Raft [65]
      A synchronization between the leader and other nodes is made
      to make sure the orders of transactions are the same for all
      nodes, before executing them.
      Chain [82]
      A block generator will verify a block, and broadcast it to some
      other nodes. If this block is verified to be valid by more than a
      threshold of nodes, it would be appended to the chain.
      A Survey about Consensus Algorithms Used in Blockchain
      124 | J Inf Process Syst, Vol.14, No.1, pp.101~128, February 2018
      5. Conclusion
      Overall, our survey has highlighted some consensus algorithms used in Blockchain, which are
      categorized into two main kinds: proof-based and vote-based consensus algorithms. In the former,
      nodes have to show they have performed sufficient proof to get the right to do the appending work, and
      get the rewards. Meanwhile, in the latter, nodes will exchange messages with others to make an
      agreement about the blocks or transactions to be appended to the ledger. We also make comparisons
      between these two types based on some of their highlighted characteristics, which illustrates the
      advantages and drawbacks of each category. It could be observed that besides the original public
      Blockchain with proof-based consensus algorithms, the newly developed consortium and private
      Blockchain has much potential with vote-based ones at this time.
      Acknowledgement
      This research was supported by Basic Science Research Program through the National Research
      Foundation of Korea (NRF) funded by the Ministry of Science, ICT & Future Planning (No. NRF-
      2017R1A2B4012559).
      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.
      [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-trust-
      each-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.
      Giang-Truong Nguyen and Kyungbaek Kim
      J Inf Process Syst, Vol.14, No.1, pp.101~128, February 2018 | 125
      [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/Quorum
      Chain-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-bitcoin-
      blockchain-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-bitcoins-
      blockchain/.
      [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-a-
      stochastic-analysis-of-two-phase-proof-of-work-in-bitcoin.pdf.
      A Survey about Consensus Algorithms Used in Blockchain
      126 | J Inf Process Syst, Vol.14, No.1, pp.101~128, February 2018
      [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 proof-
      of-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/blackcoin-
      pos-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.
      Giang-Truong Nguyen and Kyungbaek Kim
      J Inf Process Syst, Vol.14, No.1, pp.101~128, February 2018 | 127
      [58] R. Echevarria, “The second coming of blockchain,” 2017 [Online]. Available: https://software.intel.com/en-
      us/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.
      Giang-Truong Nguyen https://orcid.org/0000-0002-6034-1013
      He received B.S. degree in School of Information and Communication Technology
      from Hanoi University of Science and Technology in 2015. Since March 2017, he is
      with the School of Electronics and Computer Engineering from Chonnam National
      University as an M.S. student.
      A Survey about Consensus Algorithms Used in Blockchain
      128 | J Inf Process Syst, Vol.14, No.1, pp.101~128, February 2018
      Kyungbaek Kim https://orcid.org/0000-0001-9985-3051
      He received B.S., M.S., and Ph.D. degrees in School of Electrical Engineering and
      Computer Science from Korea Advanced Institute of Science and Technology in
      1999, 2001, and 2007, respectively. Since 2012, he is with the School of Electronics
      and Computer Engineering from Chonnam National University as a Professor.

      大學數學網 www.ningguojc.com.cn 制作維護;2014-2025     
      歡迎您是第位訪問者   
      鄭重聲明: 本站系統上的所有所有軟件和資料來源于互聯網,僅供學習和研究使用.

      渝ICP備13002528號-11

      渝公網安備 50010802003195號

      购彩