Computer Science ›› 2018, Vol. 45 ›› Issue (2): 20-24.doi: 10.11896/j.issn.1002-137X.2018.02.004

Previous Articles     Next Articles

Byzantine Consensus Algorithm Based on Gossip Protocol

ZHANG Shi-jiang, CHAI Jing, CHEN Ze-hua and HE Hai-wu   

  • Online:2018-02-15 Published:2018-11-13

Abstract: Blockchain is a kind of distributed ledger system with peer-to-peer network,which has drawn widespread attention because of its characteristics such as decentralization,non-tempering,security and credibility.In a blockchain system,some nodes have the Byzantine errors such as operational errors,network latency,system crashes,malicious attacks,and so on.The existing consensus algorithms are less tolerant to the Byzantine nodes in the blockchain,and the scalability of the blockchain system is poor.In order to solve these problems,this paper proposed a Byzantine consensus algorithm based on Gossip protocol,which allows the system to tolerate less than half of the nodes as the Byzantine node and achieve the fault-tolerant performance of XFT consensus algorithm.This paper proved that the algorithm can reach consensus in a distributed system with Byzantine defects from the agreement,correctness and termination.At the same time,the system adopts the uniform data structure,and thus has better scalability and facilitates the right node to identify the Byzantine nodes in the blockchain system.In this algorithm,the proposed node is shifted with the change of the length of blockchain,so that all nodes in the system are in the same position,thus avoiding the single point of failure problem,and making the system have better dynamic load balancing performance.

Key words: Blockchain,Byzantine error,Consensus algorithm,Gossip protocol,Scalability

[1] YUAN Y,WANG F Y.Blockchain:The State of the Art and Future Trends [J].Acta Automatica Sinica,2016,42(4):481-494.(in Chinese) 袁勇,王飞跃.区块链技术发展现状与展望[J].自动化学报,2016,42(4):481-494.
[2] NAKAMOTO S.Bitcoin:A peer-to-peer electronic cash system .https://www.cs.bgu.ac.il/~crp161/wiki.files/Bitcoin-Paper.pdf.
[3] LAMPORT L,SHOSTAK R,PEASE M.The Byzantine Gene-rals Problem [J].Acm Transactions on Programming Langua-ges & Systems,2016,4(3):382-401.
[4] 邹均.区块链技术指南[M].北京:机械工业出版社,2016:109-128.
[5] MICALI S.ALGORAND:The Efficient and Democratic Ledger .http://pdfs.semanticscholar.org/0dc0/55052cda7179cd74d43e07479565121ef733.pdf.
[6] Larimer D.Transactions as proof-of-stake .[2017-07-05].https://bravenewcoin.com/assets/Uploads/TransactionsAsProofOfStake10.pdf.
[7] CASTRO M.Practical byzantine fault tolerance and proactiverecovery [J].Acm Transactions on Computer Systems,1999,20(4):398-461.
[8] ONGARO D,OUSTERHOUT J.In search of an understandable consensus algorithm [C]∥Usenix Conference on Usenix Technical Conference.USENIX Association,2014:305-320.
[9] LEI C J,LIN Y P,LI J G,et al.Research on Byzantine Fault Tolerance Under Volunteer Cloud Environment [J].Computer Engineering,2016,42(5):1-7.(in Chinese) 雷长剑,林亚平,李晋国,等.志愿云环境下的拜占庭容错研究[J].计算机工程,2016,2(5):1-7.
[10] LI J.Distributed Gossip algorithms for Quantized Consensus[D].Harbin:Harbin Institute of Technology,2013.(in Chinese) 李婧.基于量化共识的分布式Gossip算法研究[D].哈尔滨:哈尔滨工业大学,2013.
[11] ANDR A,DEMERS A,HOPCROFTT J E.Correctness of a gossip based membership protocol [C]∥Twenty-Fourth ACM Symposium on Principles of Distributed Computing.ACM,2005:292-301.
[12] GUREVICH M,KEIDAR I.Correctness of gossip-based membership under message loss [C]∥ACM Symposium on Principles of Distributed Computing.ACM,2009:151-160.
[13] GANSESH A J,KERMARREC A M,MASSOULI,et al.Peer-to-Peer Membership Management for Gossip-Based Protocols [J].IEEE Transactions on Computers,2003,52(2):139-149.
[14] 黄步添,王云霄,王从礼,等.一种应用于区块链的拜占庭容错共识方法:中国,CN106445711A [P].2017-02-22.
[15] 张铮文.一种用于区块链的拜占庭容错算法.[2017-07-03].http://www.onchain.com/paper/66c6773b.pdf.
[16] KERMARREC A M,MASSOULIE L,GANESH A J.Probabilistic reliable dissemination in large-scale systems [J].IEEE Transactions on Parallel & Distributed Systems,2003,14(3):248-258.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75 .
[2] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[3] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[4] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[5] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99 .
[6] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105 .
[7] LIU Bo-yi, TANG Xiang-yan and CHENG Jie-ren. Recognition Method for Corn Borer Based on Templates Matching in Muliple Growth Periods[J]. Computer Science, 2018, 45(4): 106 -111 .
[8] GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping. Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph[J]. Computer Science, 2018, 45(4): 112 -116 .
[9] CUI Qiong, LI Jian-hua, WANG Hong and NAN Ming-li. Resilience Analysis Model of Networked Command Information System Based on Node Repairability[J]. Computer Science, 2018, 45(4): 117 -121 .
[10] WANG Zhen-chao, HOU Huan-huan and LIAN Rui. Path Optimization Scheme for Restraining Degree of Disorder in CMT[J]. Computer Science, 2018, 45(4): 122 -125 .