Framework and algorithms for identifying honest blocks in blockchain

doi:10.1371/journal.pone.0227531

CSpace > 应用数学研究所

	Framework and algorithms for identifying honest blocks in blockchain
	Wang, Xu 1,2,3; Gan, Guohua 3,4,5; Wu, Ling-Yun1,2,3
	2020-01-08
发表期刊	PLOS ONE
ISSN	1932-6203
卷号	15 期号:1 页码:14
摘要	Blockchain technology gains more and more attention in the past decades and has been applied in many areas. The main bottleneck for the development and application of blockchain is its limited scalability. Blockchain with directed acyclic graph structure (BlockDAG) is proposed in order to alleviate the scalability problem. One of the key technical problems in BlockDAG is the identification of honest blocks which are very important for establishing a stable and invulnerable total order of all the blocks. The stability and security of BlockDAG largely depends on the precision of honest block identification. This paper presents a novel universal framework based on graph theory, called MaxCord, for identifying the honest blocks in BlockDAG. By introducing the concept of discord, the honest block identification is modelled as a generalized maximum independent set problem. Several algorithms are developed, including exact, greedy and iterative filtering algorithms. The extensive comparisons between proposed algorithms and the existing method were conducted on the simulated BlockDAG data to show that the proposed iterative filtering algorithm identifies the honest blocks both efficiently and effectively. The proposed MaxCord framework and algorithms can set the solid foundation for the BlockDAG technology.
DOI	10.1371/journal.pone.0227531
收录类别	SCI
语种	英语
资助项目	Laboratory of Big Data and Blockchain, National Centerfor Mathematics and Interdisciplinary Sciences, Chinese Academy of Sciences
WOS研究方向	Science & Technology - Other Topics
WOS类目	Multidisciplinary Sciences
WOS记录号	WOS:000534337700049
出版者	PUBLIC LIBRARY SCIENCE
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/51489
专题	应用数学研究所
通讯作者	Wu, Ling-Yun
作者单位	1.Chinese Acad Sci, Key Lab Management Decis & Informat Syst, Inst Appl Math, Acad Math & Syst Sci, Beijing, Peoples R China 2.Univ Chinese Acad Sci, Sch Math Sci, Beijing, Peoples R China 3.Chinese Acad Sci, Lab Big Data & Blockchain, Natl Ctr Math & Interdisciplinary Sci, Beijing, Peoples R China 4.Beijing Taiyiyun Technol Co Ltd, Beijing, Peoples R China 5.Univ Sci & Technol Beijing, Beijing, Peoples R China
推荐引用方式 GB/T 7714	Wang, Xu,Gan, Guohua,Wu, Ling-Yun. Framework and algorithms for identifying honest blocks in blockchain[J]. PLOS ONE,2020,15(1):14.
APA	Wang, Xu,Gan, Guohua,&Wu, Ling-Yun.(2020).Framework and algorithms for identifying honest blocks in blockchain.PLOS ONE,15(1),14.
MLA	Wang, Xu,et al."Framework and algorithms for identifying honest blocks in blockchain".PLOS ONE 15.1(2020):14.