【作者】 李彬；

【导师】 姜建国；

【作者基本信息】 北京交通大学 ， 信息安全， 2021， 博士

【摘要】 近几年,全球主要的信息技术强国都在加快布局区块链技术的发展,区块链技术应用现已延伸到数字金融、移动通信、物联网、供应链安全管理、资产交易等多个行业。公有链、私有链、联盟链等各种区块链技术的研究与应用得到了政府部门、研究机构和商业公司的重点关注。国家主席习近平同志在主持中央政治局学习会议时特意讲到,区块链技术的创新应用在未来技术革新和产业变革中将起到非常重要的作用,要把区块链作为核心自主创新技术的重要突破口,加大投入力度,聚力攻克关键核心技术难关,加快推动这项技术和相关产业创新发展。无代币区块链是指不以代币进行价值交换作为依赖的区块链。它作为区块链技术的一种,其主要功能是在去中心化的分布式系统中保证数据记录的一致性和不可篡改性,运用到的关键技术包括共识算法、智能合约和加密算法等。在不存在拜占庭问题的无代币区块链中,共识算法基本等同于分布式一致性算法(以下简称:一致性算法),而一致性算法目前还面临各种各样的问题和挑战。一方面是部分一致性算法存在运行效率低、通信负载高,甚至“活锁”等问题;另一方面是对于一致性算法在应用部署过程中缺少多维度的安全性分析;此外,涉及Leader选举的一致性算法还存在操控选举过程而无法保证去中心化属性的隐患。本文从上述三个方面出发,首先通过对经典的、影响最广泛的基础Paxos(Basic Paxos)一致性算法进行改进,缩短了其达成共识时间、减少了形成―活锁‖的概率、节约了通信成本、提升了数据更新效率。然后,基于博弈论对采用Paxos算法的分布式系统进行安全性分析,提出了此类系统在实际应用中可能产生的计算资源困境问题,推导出了为达成算法机制设计目标而不偏离节点既定策略的安全条件,并验证了此安全条件的有效性。最后,分析得出涉及Leader选举的一致性算法存在通过操纵Leader选举破坏去中心化属性的风险,并提出了一种可以有效降低此类安全性问题的新型选举机制。本文的主要研究内容及其贡献包括以下三方面:(1)通过优化算法中的角色行为对基础Paxos算法进行改进该工作从提高一致性算法运行效率的目的出发,通过对基础Paxos算法执行过程中各角色在各阶段的行为动作进行分析,在继承原算法基本机制设计前提下,提出了四项改进措施来优化原算法中proposer和acceptor角色的行为。首先,剖析了原始算法中每个角色在每个阶段中的具体行为。随后,采用距离关联等待机制、分阶段向审批委员会发送审核提案、减少决议广播范围和acceptor自学习等改进措施对原算法进行优化。从理论上证明了改进算法的正确性和安全性,并比较分析了这两个算法在正常执行时的消息传递个数。最后,通过实验对这两个算法的容错性、运行时间、消息传递个数、提案提交失败个数和平均每秒提案提交数进行了分析比较。本研究提出的Adv Paxos对比基础Paxos,在同等集群规模下拥有相同的容错能力,并具有更低的通信负载和更高运行效率,能够有效提高服务器集群间达成共识的速度。而且因为Adv Paxos继承了基础Paxos的机制设计,是其他类Paxos的工程实现算法运行过程中需要调用的支撑算法,具备高扩展性,所以该算法对于提升类Paxos的其他工程实现算法的执行效率也将起到很好的效果。(2)基于博弈论对采用Paxos算法的分布式系统进行安全性分析该工作从采用Paxos算法的分布式系统的安全运行角度出发,通过分析典型系统中各节点间的博弈关系,发现系统运行时各节点会产生的一种自私行为:想获得数据更新的同时,又不愿当选Leader而过多消耗自身计算资源。系统因为此种自私行为的存在将形成一种博弈,本文称之为计算资源困境博弈。接着,通过支付矩阵和建立效用函数模型分析得出计算资源困境博弈存在帕累托最优的纳什均衡是需要满足一定安全条件的结论。各博弈节点若不满足安全条件,将做出不合作的选择,而不合作的选择可能引发连锁反应,导致系统无法正常工作。最后,通过求解计算资源困境博弈的子博弈精炼纳什均衡解来进行推导,得出了系统为达成Paxos算法机制设计目标(节点不偏离既定的触发策略或两期策略)所需的安全条件,并通过实验证明了安全条件的有性效。本研究能够帮助采用Paxos算法的联盟链运营方评估系统运行风险和制定系统准入条件,有助于意向加入此类联盟链的单位在实际收益与消耗成本之间进行权衡考虑。(3)分析研究在一致性算法中实现少数赢这种更安全的选举机制该工作从Leader节点产生机制的安全性角度出发,分析得出传统的多数赢选举中存在因控制Leader选举投票而会丧失系统去中心化属性的安全隐患,并提出采用逐步淘汰选择一致多数派(少数赢)这种更安全的Leader节点选举机制。首先,研究了少数赢选举机制可能面对的绝对控制攻击、团队攻击和欺诈攻击的攻击方式、攻击影响以及攻击成功的可能性,并发现了在某些特定节点数量时会存在绝对控制攻击成功所需受控率低值现象及低值出现的规律。接着,描述了少数赢选举机制在基于Leader选举的一致性算法中的具体实现方法,解决了算法存活性、算法容错、决赛方式等难点问题。最后,通过理论分析和实验进一步验证了此种选举机制对比传统的多数赢选举机制,在没有明显增加选举时间的基础上,面对绝对控制攻击具有更好的安全性。本文研究提出的少数赢选举机制,在常见的区块链分布式系统(4参与节点以上)中,要想完成绝对控制攻击少数赢需要控制80%以上的节点,相比多数赢50%的控制率,至少提升了60%攻击难度。并且通过枚举方式分析出:在少数赢选举实施绝对控制攻击的难度还将随着参与节点的增多而持续增加。更多还原

【Abstract】 In recent years,major information technology powers in the world are speeding up the development of blockchain technology.The application of blockchain technology has extended to digital finance,mobile communication,Internet of things,supply chain management,digital asset trading and other fields.The research and application of various blockchain technologies,such as public chain,private chain and alliance chain,have attracted the attention of government departments,research institutions and commercial companies.Xi Jinping,President of People’s Republic of China,emphasized that the integrated application of blockchain technology played an important role in new technological innovation and industrial transformation,we should take blockchain as an important breakthrough in independent innovation of core technologies,increase investment,strive to tackle key core technologies,and accelerate the development of blockchain technology and industrial innovation.Token-less blockchain refers to a blockchain that does not rely on token for value exchange.As a kind of blockchain technology,its main function is to ensure the consistency and non-tamperability of data records in decentralized distributed system.The key technologies of token-less blockchain include consensus mechanism,smart contract and encryption algorithm.In token-less blockchain without Byzantine problem,consensus algorithm is basically equivalent to distributed consistency algorithm(hereinafter referred to as: consistency algorithm).At the same time,the consistency mechanism still faces various problems and challenges.First,some consensus mechanisms have the problems of slow consensus building speed and high communication load.Second,there is a lack of multi-dimensional security analysis for consistency algorithm.Third,the consistency algorithm involving leader election has the hidden trouble of manipulating the election process and cannot ensuring decentralization.This paper will be required from the above three aspects.Firstly,by improving the classical Paxos consistency algorithm,which has the widest influence,it speeds up the time of reaching consensus,reduces the probability of "livelock",cuts down the communication cost.Then,by using game theory it analyzes the security and reliability of Paxos algorithm,and puts forward the problem of possible computing resource dilemma.It analyzes that Paxos algorithm can run continuously and reliably only when it meets certain security conditions,and proves the correctness of Paxos mechanism design by using game theory.Finally,analysis shows that the consistency algorithm involving Leader election has the problem of destroying decentralization by manipulating Leader election,and proposes a new election mechanism that can effectively reduce such security issues.The main research contents and contributions of this paper include the following three aspects:(1)Improving Basic Paxos algorithm by optimizing the role behavior of the algorithmIn order to improve the running efficiency of the consistency algorithm,this paper analyzes the behavior of each role in each phase of Basic Paxos algorithm,and proposes four improvement measures to optimize the behavior of Proposer and acceptor roles in the original algorithm on the premise of inheriting the basic mechanism design of the original algorithm.Firstly,the specific behavior of each role in each phase of the original algorithm is analyzed.Then,the original algorithm is optimized by distance association waiting mechanism,sending the approval proposal to acceptors in stages,broadcast reduction and acceptors self-learning.The correctness and security of the improved algorithm are proved theoretically,and the number of message passing between the two algorithms in normal execution is compared and analyzed.Finally,the fault tolerance,running time,number of message passing,number of proposal submission failures and average number of proposal submission per second of the two algorithms are analyzed and compared from the experiments.Compared with Basic Paxos,Adv Paxos proposed in this study can effectively improve the speed of reaching consensus among server clusters on the basis of the same fault tolerance under the same cluster scale,and has lower communication load and higher operating efficiency.Adv Paxos inherits the mechanism design of Basic Paxos,it is a supporting algorithm that needs to be called during the operation of other Paxos like engineering implementation algorithms,and has high scalability,so the optimized algorithm will also play a good role in improving the execution efficiency of other Paxos like engineering implementation algorithms.(2)Analyzing the security of the distributed system using Paxos algorithm by game theoryFrom the perspective of the safe operation of the distributed system using Paxos algorithm,this paper analyzes the game relationship among the nodes in the typical system,and finds that each node will emerge a selfish behavior when the system is running:To get data updates,but do not to be elected leader and excessive consumption of their own computing resources.Because of this selfish behavior,the system will form a kind of game which is called computing resource dilemma game in this paper.Then,by analyzing the payoff matrix and establishing the utility function model,it is found that Pareto optimal Nash equilibrium in the game needs to meet certain security conditions.If the security conditions are not met,each game node will make the uncooperative choice,and the uncooperative choice may cause chain reaction,which will cause the system to work abnormal eventually.Finally,by solving the perfect Nash equilibrium solution of the subgame in the game,the security conditions for achieving the purpose(nodes no not deviate from the set trigger strategy or two-phase strategy)of Paxos mechanism design are obtained.And the effectiveness of the security conditions is proved by experiments.This study is helpful for the designers who adopt Paxos algorithm alliance chain to establish the system access conditions,as well as the enterprise who want to join the system to weigh the actual benefits and consumption costs.(3)Analyzing and researching the more secure election mechanism of minority win in the consistency algorithmThe purpose of this work is to analyze the security of the leader node generation mechanism,find out the hidden danger of losing the decentralized attribute of the system due to the control of voting in the traditional majority win election,and propose the more secure leader node election mechanism of phase out the majority with the same choice(minority win).First,by studying the attack methods,attack effects and the possibility of attack success that minority win election mechanism may face,such as absolute control attack,team attack,fraud attack.Then,it is concluded that there will be a phenomenon of low control rate and the regularity of low control rate when the number of nodes is certain.And the implementation approches of the minority win election mechanism in the leader election based consistency algorithm are described.Some difficult problems such as liveness,fault tolerance and final are solved.Finally,through theoretical analysis and experiments,it is further verified that this kind of election mechanism has better security in the face of absolute control attack,compared with the traditional majority win election mechanism,without significantly increaseing the election time.In the common blockchain distributed system(more than 4 nodes),in order to complete the absolute control attack,adversariesneed to control more than 80%of the nodes.Compared with the control rate of 50% of majority win,minority win can increase the attack difficulty by at least 60%.Moreover,by enumeration analysis,we can see that the difficulty of absolute control attack in minority win elections increases with the number of participating nodes.更多还原