Consensus Algorithm Analysis in Blockchain: PoW and Raft
Taotao Wang, Dongyan Huang, Shengli Zhang · 2021
This chapter theoretically and experimentally analyzes the consensus algorithms in blockchains. Consensus is one of the key problems in blockchains, and there are several candidate consensus algorithms for public and consortium/private blockchains with different security and performance levels. The first part of this chapter analyzes the proof-of-work (PoW) consensus algorithm. In PoW-based public blockchains, miners can conduct different mining strategies to selfishly increase their own revenues. Previously, the most profitable mining strategy was believed to be honest mining encoded in the default blockchain protocol. It was shown later that it is possible to gain more mining rewards by deviating from honest mining and conducting some malicious mining strategies. In particular, the mining problem can be formulated as a Markov decision process (MDP), which can be solved to give the optimal mining strategy. However, solving the mining MDP requires knowing the values of various parameters that characterize the blockchain network model. In real blockchain networks, these parameter values are not easy to obtain and may change over time. This hinders the use of the MDP model-based solution. In the first part of this chapter, we employ RL to dynamically learn a mining strategy with performance approaching that of the optimal mining strategy. Since the mining MDP problem has a nonlinear objective function (rather than linear functions of standard MDP problems), we design a new multi-dimensional RL algorithm to solve the problem. Experimental results indicate that, without knowing the parameter values of the mining MDP model, our multi-dimensional RL mining algorithm can still achieve optimal performance over time-varying blockchain networks. The second part of this chapter analyzes the Raft consensus algorithm that is usually adopted in the consortium/private blockchains. There are many articles analyzing the performance of threat models for blockchains. However, the issue of network stability has not received much attention, which in fact affects the blockchain performance. This part studies the performance of Raft in networks with non-negligible packet loss rate. In particular, we propose a simple but accurate analytical model to analyze the distributed network split probability. At a given time, we explicitly present the network split probability as a function of the network size, the packet loss rate, and the election timeout period. To validate our analysis, we implement a Raft simulator and the simulation results coincide with the analytical results. With the proposed model, one can predict the network split time and probability in theory and optimize the parameters in Raft consensus algorithm.