2017 IEEE International Conference on Systems, Man, and Cybernetics (SMC)

Banff Center, Banff, Canada, October 5-8, 2017

A Review on Consensus Algorithm of Blockchain

Du Mingxiao*, Ma Xiaofeng*, Zhang Zhe**, Wang Xiangwei*, Chen Qijun*

*Department of Control Science and Engineering, **Fintech Laboratory,
Tongji University QianBao Financial Services Company
Shanghai, China Beijing, China
Email: [email protected]

Abstract—Blockchain is the basic technology of bitcoin. With can save about $20 billion every year. World Economic Forum
the value appreciation and stable operation of bitcoin, blockchain predicts that 10% of the world's GDP will be stored on the
is attracting more and more attention in many areas. Blockchain blockchain network by 2027 [3].
has the characteristics of decentralization, stability, security, and
non-modifiability. It has the potential to change the network In the academic field, the blockchain technology is also
architecture. The consensus algorithm plays a crucial role in attracting more and more attention. The study of blockchain
maintaining the safety and efficiency of blockchain. Using a right can be divided into three categories. Firstly, study on the digital
algorithm may bring a significant increase to the performance of currency that based on blockchain, including the decentralized
blockchain application. In this paper, we reviewed the basic and centralized digital currency [4]. Secondly, study on the
principles and characteristics of the consensus algorithms and application of blockchain technology in non-digital currency
analyzed the performance and application scenarios of different scenarios such as the application of blockchain in smart city [5]
consensus mechanisms. We also gave a technical guidance of and medical information security management [6, 7]. Thirdly,
selecting a suitable consensus algorithm and summarized the study on underlying blockchain technology. More and more
limitations and future development of blockchain technology. researchers realize that the blockchain can be stripped out from
the digital currency to create a revolutionary technical
Keywords—blockchain; consensus; distributed system; digital architecture in other areas. Some researchers have begun to
currency; bitcoin
study the underlying technologies such as the difficulty control
I. INTRODUCTION of mining[8], the scalability of consensus algorithms [9] and
the smart contract [10].
The blockchain was firstly introduced in the treatise [1]
“Bitcoin: A peer-to-peer electronic cash system” by Satoshi Blockchain technology includes the point-to-point(P2P)
Nakamoto in 2008. It is the underlying technology of bitcoin. communication, consensus algorithms, distributed storage
The traditional transactions require a centralized trusted technology, encryption algorithms, and so on. But at present,
institution. The confirmation and record of the transactions the research on blockchain is mainly focused on the application
depend entirely on the trusted institution, which may cause of Bitcoin or blockchain in different areas. So in this paper, we
many problems of transaction cost, efficiency, and security. introduce the existing common consensus algorithms in chapter
Decentralization is the core feature of blockchain and it can be II and analysis the performance and shortcomings of the
used to solve these problems. All the nodes in the blockchain consensus algorithms. Then we give a guidance on how to
have equal status. These nodes achieve consensus by using the select the suitable consensus algorithm in different scenarios in
prior agreement of the rules and following the principle of chapter III. Finally, we summarize this paper in chapter IV.
majority dominance. They implement the functions of data
distributed storage and transaction information recognition in II. THE CONSENSUS ALGORITHMS
the situation that the other nodes are not fully trusted. So we In the applications of blockchain, we need to solve two
can effectively solve the transaction problems. problems- double spending and Byzantine Generals Problem
[11]. Double spending problem means reusing the currency in
Bitcoin is the first blockchain application in the financial
two transactions at the same time. The traditional currency is
field. With the development of the blockchain technology,
the entity, so we will not face the problem of double spending
blockchain has been concerned by the government, financial
while using traditional currency. We can also solve the double
institutions, and technological enterprises. For example, the
spending problem in the Internet transactions with the
British government issued the report [2] about blockchain to
centralized trusted institutions. Blockchain solves this problem
promote the application of blockchain in centralized digital
with the method of verifying the transactions by many
currency and government affairs in January 2016. All major
distributed nodes together. Byzantine Generals Problem is the
banks in the world are actively exploring the application of
problem in the distributed system. The data can be delivered
blockchain technology. In August 2016, UBS, Deutsche Bank,
between different nodes through peer-to-peer communications.
Bank of Santander and Bank of New York Mellon jointly
However, some nodes may be maliciously attacked, which will
developed a digital currency system with blockchain
lead to the changes of communication contents. Normal nodes
technology to help financial markets improve the speed of
need to distinguish the information that has been tampered and
payment. Bank of Santander, the largest bank in Spain,
obtain the consistent results with other normal nodes. This also
believes that if all banks in the world use the blockchain, they
needs the design of the corresponding consensus algorithm.

978-1-5386-1645-1/17/$31.00 ©2017 IEEE 2567

The consensus algorithm has been studied for many years in each node. The difficulty of mining is inversely proportional to
distributed system. There are some transplantable consensus coin age.
algorithms applied in blockchain. We make a detailed
description of the principles of these consensus algorithms in PoS encourages the coins holders to increase the holding
this section. time. With the concept of coin age, the blockchain is no longer
entirely relying on the proof of work. That effectively solves
A. PoW (Proof of Work) the resource wasting problem in PoW. The security of the
PoW is the consensus algorithm used in bitcoin. Its core blockchain using PoS improves with the increasing value in the
idea is to allocate the accounting rights and rewards through blockchain. The attackers need to accumulate a large number
the hashing power competition among the nodes. Based on the of coins and hold them long enough to attack the blockchain.
information of the previous block, the different nodes calculate This also greatly increases the difficulty of attack.
the specific solution of a mathematical problem. It’s difficult to Besides the PPCoin, there are also many other coins using
solve the math problem. The first node that solves this math PoS such as the Nxt [14] and BlackCion [15]. But they
problem can create the next block and get a certain amount of consider the rights of the nodes and use a random algorithm to
bitcoin reward. Satoshi Nakamoto used HashCash to design allocate accounting rights.
this mathematics problem in bitcoin [12]. The specific
calculation steps are as follows: C. DPoS(Delegated Proof of Stake)
In the initial design stage of bitcoin, Satoshi Nakamoto
1) Get the difficulty: After the production of every 2016
hoped that all the participants can use the CPU to mine. So the
blocks, bitcoin mining algorithm will dynamically adjust the hashing power can match the nodes and each node has the
difficulty value according to the hash rate of the whole opportunity to participate in the decision-making of the
network. blockchain. With the development of technology and the
2) Collect transactions: Collect all pending transactions appreciation of bitcoin, the machines that are specially
on the network after the production of the last block. Then designed for mining are invented. The hashing power is
calculate the Merkle Root of these transactions and fill in the grouped in the participants that have large numbers of mining
block version number, the 256-bit hash value of the previous machines. The ordinary miners rarely have the opportunity to
block, the current target hash value, Nonce random number create a block.
and other information. BitShares is an example of DPoS [16]. In the blockchain
3) Calculating: Traverse the Nonce from 0 to 232 and with DPoS, each node can select the witnesses based on its
calculate the double SHA256 hash value in step 2. If the hash stake. In the whole network, the top N witnesses that have
value is less than or equal to the target value, the block can be participated in the campaign and got the most votes have the
broadcasted. The node complete accounting After the accounting right. The number N of witnesses is defined such
verification of other nodes. that at least 50% of voting stakeholders believe there is
sufficient decentralization [17]. The elected witnesses create
4) Restarting: If the node can't work out the hash value at
new blocks one by one as assigned and get some rewards. The
a certain time, it repeats step two. If any other node completes witnesses need to ensure adequate online time. If a witness is
the calculation, then it restarts from step 1. unable to create its assigned block, the activity of that block
PoW takes the workload as the safeguard. The newly will be moved to the next block and the stakeholders will vote
created block is linked to the blocks in front of it. The length of for a new witness to replace it. The blockchain using DPoS is
the chain is proportional to the amount of workload. All nodes more efficient and power-saving than PoW and PoS.
trust the longest chain. If anyone wants to tamper with the
blockchain, he needs to control more than 50% of the world's D. PBFT(Practical Byzantine Fault Tolerance)
hashing power to ensure that he can become the first one to In distributed systems, Byzantine Fault Tolerance can be a
generate the latest block and master the longest chain. The good method to solve the transmission errors. But early
gains from tampering can be much greater than the cost. So the Byzantine system requires exponential operations. Until 1999,
PoW can effectively guarantee the safety of the blockchain. the PBFT(Practical Byzantine Fault Tolerance) system [18]
B. PoS(Proof of Stake) was proposed and the algorithm complexity was reduced to a
polynomial level, which greatly improved efficiency. The
PoS has been mentioned in the first bitcoin project, but it process of PBFT is shown in figure 1. It consists of five states:
was not used because of the robustness and other reasons. The
earliest application of PoS is PPCoin [13]. In PoS, the digital 1) Request: The client sends a request to the master server
currency has the concept of coin age. Coin age of a coin is its node, the master node gives the request a timestamp.
value multiplied by the time period after it was created. The 2) Pre-prepare: The master server node records the
longer one node holds the coins, the more rights it can get in request message and gives it an order number. Then the master
the network. Holders of the coins will also receive a certain node broadcasts a pre-prepare message to the other following
reward according to the coin age. In the design of PPCoin,
server nodes. The other server nodes initially determine
mining is also needed to get the accounting rights. The formula
is proofhash < coin age * target. The proofhash is a composed whether to accept the request or not.
hash value of the weight factor, the unspent output value and 3) Prepare: If a server node chooses to accept the request,
the fuzzy sum of current time. PoS limits the hashing power of it broadcasts a prepare message to all the other server nodes
and receives the prepare messages from the other nodes. After

2568
having collected 2f+1 messages, if a majority of nodes choose
to accept the request, then it will enter the commit state.
4) Commit: Each node in commit state sends a commit
message to all the other nodes in the server. At the same time,
if a server node receives 2f+1 commit messages, it could
believe that most nodes reach a consensus to accept the
request. Then the node executes the instructions in the request
message.
5) Reply: the server nodes reply to the client. If the client
does not receive a reply because of the network delay, the
request is resent to the server nodes. If the request has been
executed, the server nodes only need to send the reply message Fig. 2. States transfer of RAFT
repeatedly.
ledger of the whole network. The system is stable as long as
E. Raft the longest chain is guaranteed by the honest nodes. We take
After the Byzantine Generals Problem was raised, Lamport PoW as an example to provide a proof of safety.
proposed Paxos algorithm to solve the consistency problem in Hypothesis: the total hashing power in the network is H0,
certain conditions in 1990. the average time for creating a new block is T0, the total
But because the content of the paper is difficult to hashing rate of honest nodes is pH0 and the total hashing rate of
understand, it was not accepted. Lamport republished the paper malicious nodes qH0. The difficulty is changeless when
[19] in 1998 and the Paxos was briefly reintroduced in calculating the double spending probability. One transaction is
2001[ 20]. Then Paxos occupies the dominant position in the verified after n blocks.
field of consistency algorithm. Many other algorithms are Firstly, we calculate the probability Pz for a malicious node
derived from it. But Paxos algorithm is too theoretical. The to catch up with the honest chain in the case of z blocks falling
people have great difficulty in understanding it and engineering behind. It is analogous to the Binomial Random Walk with an
implementation. In 2013, Standford’s Ongaro and others absorbable wall. There is a particle on the x-axis. The particle
published the paper and proposed Raft algorithm[21]. Raft can move unit distance with the probability q to the left or p to
achieves the same effect as Paxos and is more convenient in the right (p+q=1) each time. Initially, the particle is located at x
engineering implementation and understanding. = z. The particle will stop moving if it arrives at x = 0. Pz
Raft cluster generally contains 5 server nodes. Up to two equals the probability of arriving at x = 0. So:
nodes are allowed to crash at the same time. The server node as
shown in figure 2 has three states: leader, follower, and  𝑃0 = 1，limz→∞ 𝑃𝑧 = 0 
candidate. There is only one leader in a term and the leader is
responsible for handling all clients’ requests.  𝑃𝑧 = 𝑝𝑃𝑧+1 + 𝑞𝑃𝑧−1 ，𝑧 = 1,2, ⋯ , ∞ 
III. ANALYSIS OF THE CONSENSUS ALGORITHMS
If q < p, use
All the consensus algorithms have their own characteristics.
In this chapter, we analysis the safety, verification speed,  𝐶𝑧 = 𝑃𝑧+1 − 𝑃𝑧 ，r = 𝑞/𝑝 
throughput (transactions per second, TPS), fault tolerance,
scalability and shortcomings of the consensus algorithms and From formula (2), we get
the usage in different scenarios.
A. Performance 1−𝑟 𝑧
 𝑃𝑧 − 𝑃0 = ∑𝑧−1
𝑘=0(𝑃𝑘+1 − 𝑃𝑘 ) = 𝐶0  
1−𝑟
PoW and PoS solve the safety problem by using the share
Then, with formula (1) we can get:
𝑞
 𝑃𝑧 = 𝑟 𝑧 = ( )𝑧 , 𝑞 < 𝑝 
𝑝

It is easy to prove

 𝑃𝑧 = 1, 𝑞 ≥ 𝑝 

So we can conclude

Fig. 1. Steps of PBFT[18]

2569
 1，𝑞 ≥𝑝
 𝑃𝑧 = {(𝑞 )𝑧 ，𝑞 < 𝑝 
𝑝

We can see in (7): if the total hashing power of malicious is

more than 50% of the whole network hashing power, the
double spending attack will finally success. Then we need to
calculate the probability of success in double spending with n
blocks to wait while q < p.
We assume that a node will restart hashing if it fails to
work out the right hash in t time. The honest nodes’ total
probability of success in t time is tp/T0 and the malicious
nodes’ is tq/T0.
If the malicious nodes want to succeed in double spending
attack, they have to wait for n blocks until the transactions have Fig. 3. Relationship between hashing power ratio and double spending
been verified. In this period, both the honest nodes and the
malicious nodes have tried nT0/tp times and the honest nodes an error or the system cannot complete the client's request in a
have success n times. So the malicious nodes’ successful times long time. As the nodes in PBFT need to communicate with
λ will be a Poisson distribution with expected value: every node to reach the agreement, the scalability is limited.
PBFT is more suitable for the permissioned blockchain system
 λ = 𝑛𝑞/𝑝  with high-speed network and a small number of nodes.

So the malicious nodes’ success probability of double spending Raft has high efficiency and simplicity and it has been
is widely used in the distributed systems. In the blockchain with
RAFT, the leader occupies an absolutely dominant position.
The blockchain cannot tolerate malicious nodes and can
𝜆𝑘 𝑒 −𝜆 𝑞 𝑛−𝑘 𝜆𝑘 𝑒 −𝜆
 𝑃 = ∑𝑛𝑘=0 ( ) + ∑𝑛𝑘=𝑛+1   tolerate up to 50% nodes of crash fault. It is important to
𝑘! 𝑝 𝑘!
guarantee the absolute security of the leader node. The
Equal to throughput is limited by the maximum performance of one
node. The scalability is limited by the architecture of RAFT.
𝜆𝑘 𝑒 −𝜆 𝑞 𝑛−𝑘 The comparison of the five consensus algorithms is shown
  𝑃 = 1 − ∑𝑛𝑘=0 [1 − ( ) ] 
𝑘! 𝑝 in table I.

We visualize the results of formula (9) with different n in B. Limitation

figure 3. It’s easy to conclude from the result that the PoW also has weaknesses such as waste of resources, slow
transaction is safe only if we wait for enough blocks to confirm speed of transaction verification and concentration of hashing
the transaction. The blockchain using PoW or PoS can tolerate power:
up to 50% malicious nodes.
1) Waste of resources: the nodes which have high hashing
For the purpose of reducing bifurcation and waiting for power can get the corresponding bitcoins as rewards. This is
enough blocks to confirm, the throughput of blockchain using the main way to get the bitcoin, which forces people to
PoW or PoS is limited. In this blockchain, all the nodes can upgrade the hardware. Participants need to spend a lot of
mine according to the pre-set rules. The throughput and money to buy the special mining machines and the machine
verification speed is not related to the number of nodes.
needs to consume a large amount of electricity in the process
Therefore, such a blockchain network has almost unlimited
scalability. of calculation. These characteristics also make the application
of PoW some limitations.
In the blockchain using DPoS, the elected witnesses are
responsible for creating blocks and confirming transactions. TABLE I. COMPARISON OF THE FIVE CONSENSUS ALGORITHMS
For the reduction of verification nodes, the blockchain with
DPoS can accelerate the speed of creating the blocks and consensus algorithms
characteristics
verifying the transactions. The throughput and transaction PoW PoS DPoS PBFT RAFT
verification speed of DPoS are faster than PoW or PoS. The Byzantine fault
50% 50% 50% 33% N/A
scalability is also unlimited. tolerance
crash fault
The blockchain using PBFT consists of 3f+1 server nodes 50% 50% 50% 33% 50%
tolerance
and each node needs to collect 2f+1 messages in the verification speed >100s <100s <100s <10s <10s
communication. So this blockchain system can tolerate at most
33% malicious nodes. PBFT also contains the mechanism of throughput( TPS) <100 <1000 <1000 <2000 >10k
view change. The view change mechanism is to replace the
scalability strong strong strong weak weak
master node with a following node when the master node has

2570
 2) The slow speed of transactions: In order to reduce the
production of single block or branch of the chain, the
calculating time of each block must not be too short. The
average calculating time of the block is 10 minutes. But the
time interval between the two blocks is not sure. The largest
interval in history is more than one hour while the minimum
interval is less than one second. This time has a great
limitation in the application of instant payment.
3) The concentration of hashing power: With the increase
of mining difficulty, it’s hard for a single one to figure out the
math problem. In order to solve this problem, some
organizations have set up the "mining pool", and the miners in
a mining pool solve the math problem together. After a pool
solving the math problem and obtaining the bitcoin as
rewards, the miners allocated the bitcoin according to their Fig. 4. Ratios of the mining pools[22]
contribution. But because of the existence of the mining pool,
the global hashing power become concentrated. If the hashing Private blockchain means that the owner of the blockchain
power of one pool or some combined pools is more than 50%, has the highest authority to change the information. The rest of
they can easily have a monopoly on accounting. figure 4 the nodes have limited access to read. Compared to the public
shows the monthly hashing power rankings. At present, the blockchain, the private blockchain has the characteristics of
global top six mining pools’ hashing power has been more easy modification and low transaction cost. Transaction
than 50% of global hashing power. verification of the private blockchain only need some
PoS is similar to PoW. The miners also need to work out designated high credit nodes. Private blockchain is applied to
the right hash to create new blocks and they have to wait for a more closed networks such as the intranet. It is more important
certain number of blocks to confirm the transactions. PoS did to solve the crash faults than Byzantine faults. We can use
not essentially solve the problem of resources wasting, slow PBFT and RAFT consensus mechanisms according to the
trading and concentration of hashing power in PoW. Besides, network size.
the coin age is also destroyed in usual transactions, which may Permissioned blockchain means that the blockchain is
make participants more interested in collecting the coins composed of many parties and the main nodes are pre-specified
instead of using them. by the participants. The members of the permissioned
In the blockchain with PBFT, the verification functions are blockchain do not fully trust the others. Each participant selects
done in the server. One server node needs to communication its own consensus node according to the rules. Transactions
with all the other nodes. The data processing size and time need to be recognized by most consensus nodes. The degree of
consumption are huge. As the size of the network increases, the openness and centralization of the consortium blockchain lies
efficiency of consensus will drastically decrease. Besides, between the public and private blockchain. The permissioned
PBFT server nodes need to have a high degree of confidence, blockchain is suitable for the semi-closed network, which is
so PBFT cannot be used in the permissioned blockchain. built by different enterprises. There may be conflicts among
different enterprises and some nodes can become malicious
In Raft, the leader occupies an absolute dominance. It’s nodes, so it is better to use PBFT in this scenario.
very important to defend the safety of the leader. Once the
leader is maliciously controlled, the system will be completely IV. SUMMARY
destroyed. In addition, the system performance is limited by Blockchain has the characteristics of decentralization,
the maximum throughput of the node. stability, security, non-modifiability and so on. With the
C. Application Scenarios development of technology, the blockchain is attracting more
The blockchain can be divided into three categories: public and more attention in different areas. This paper makes a
blockchain, private blockchain, and permissioned blockchain. systematic review of the usual consensus algorithms used in
According to the previous section, it is better to use the the blockchain. Consensus algorithm is the core technology of
corresponding consensus algorithm in different scenarios. blockchain, but current research of the consensus mechanism is
still in its infancy. The consensus algorithm specially designed
A public blockchain means that it is accessible to all the for different scenarios is still very rare. How to make the
people in a public area. Everyone can become one of the nodes blockchain performance better in a particular scenario? We still
and make contributions to obtain the rewards following the need further research.
rules. There are no trust relationships among the nodes. Public
blockchain is completely open and decentralized. All ACKNOWLEDGMENT
transactions on the public blockchain can never be changed or This research is affiliated with the Tongji-QianBao Joint
revoked. PoW, PoS, and DPoS consensus algorithms are Fintech Laboratory of Tongji University.
common choices of public blockchain.

2571
 REFERENCES Problems in Network Security, iNetSec 2015, October 29, 2015 -
October 29, 2015, 2016, pp. 112-125.
[1] S. Nakamoto, "Bitcoin: A peer-to-peer electronic cash system,"
Consulted, 2009. [10] F. Idelberger, G. Governatori, R. Riveret, and G. Sartor, "Evaluation of
Logic-Based Smart Contracts for Blockchain Systems,", Cham,
[2] "Distributed ledger technology: beyond block chain,", 2016. Switzerland, 2016, pp. 167-83.
[3] P. Rizzo, "World Economic Forum Survey Projects Blockchain 'Tipping [11] L. Lamport, R. Shostak and M. Pease, "The Byzantine Generals
Point' by 2023,", 2015. Problem," Acm Transactions on Programming Languages & Systems,
[4] G. Danezis and S. Meiklejohn, "Centrally Banked Cryptocurrencies," vol. 4, pp. 382-401, 1982.
2015. [12] A. Back, "Hashcash - A Denial of Service Counter-Measure," in
[5] K. Biswas and V. Muthukkumarasamy, "Securing smart cities using USENIX Technical Conference, 2002.
blockchain technology," in 18th IEEE International Conference on High [13] S. King and S. Nadal, "PPCoin: Peer-to-Peer Crypto-Currency with
Performance Computing and Communications, 14th IEEE International Proof-of-Stake,", 2012.
Conference on Smart City and 2nd IEEE International Conference on
[14] Nxtwiki, "Whitepaper:Nxt,", 2015.
Data Science and Systems, HPCC/SmartCity/DSS 2016, December 12,
2016 - December 14, 2016, 2016, pp. 1392-1393. [15] P. Vasin, "BlackCoin's Proof-of-Stake Protocol v2,".
[6] P. T. S. Liu, "Medical record system using blockchain, big data and [16] "https://bitshares.org/,".
tokenization," in 18th International Conference on Information and [17] "https://bitshares.org/technology/delegated-proof-of-stake-consensus/,".
Communications Security, ICICS 2016, November 29, 2016 - [18] M. Castro and B. Liskov, "Practical Byzantine fault tolerance," in
December 2, 2016, 2016, pp. 254-261. Symposium on Operating Systems Design and Implementation, 1999,
[7] Y. Xiao, H. Wang, D. Jin, M. Li, and J. Wei, "Healthcare Data pp. 173--186.
Gateways: Found Healthcare Intelligence on Blockchain with Novel [19] L. Lamport, "The part-time parliament," Acm Transactions on Computer
Privacy Risk Control," Journal of Medical Systems, vol. 40, p. 218, Systems, vol. 16, pp. 133-169, 1998.
2016.
[20] L. Lamport, "Paxos Made Simple," Acm Sigact News, vol. 32, 2001.
[8] D. Kraft, "Difficulty control for blockchain-based consensus systems,"
Peer-to-Peer Networking and Applications, vol. 9, pp. 397-413, 2016- [21] D. Ongaro and J. Ousterhout, "In search of an understandable consensus
01-01 2016. algorithm," Draft of October, 2013.
[9] M. Vukoli, "The quest for scalable blockchain fabric: Proof-of-work vs. [22] "http://qukuai.com/,".
BFT replication," in IFIP WG 11.4 International Workshop on Open

2572