×

浅谈共识算法的理论基础

标签: 暂无标签
本帖最后由 RickMQ 于 2018-11-15 14:49 编辑

共识算法的理论基础,做了一些整理,和大家分享下

1、FLP不可能定理

因为同步通信中的一致性被证明是可以达到的,因此一直有人尝试各种算法解决异步环境的一致性问题。然而Fischer, Lynch and Patterson三位作者于1985年发表了一篇论文,提出并证明了一个定理,即“FLP不可能定理”:

在网络可靠,存在节点失效(即便只有一个)的最小化异步模型系统中,不存在一个可以解决一致性问题的确定性算法。

FLP不可能定理论证了最坏的情况是没有下限,要实现一个完美的容错的异步的一致性系统是不可能的。

2、CAP定理

但FLP不可能定理只是说明了100%保证一致性是不可能的,这并不影响我们对分布一致性的探索。例如99%以上的一致性还是完全有可能做到的;又如放宽时间限制,即要求系统在一段时间后最终达到一致性(达不成一致则系统不可用),也是可以做到的;再如,将部分通信改成同步的,牺牲一定的可用性和吞吐量,就能得到一个一致性较强的协议。

CAP定理即描述了分布式系统中关于一致性和可用性的关系:

一个分布式系统最多只能同时满足(强)一致性(Consistency)、可用性(Availability)和分区容错性(Partition tolerance)这三项要素中的两项。

CAP定理起源于计算机科学家埃里克·布鲁尔在2000年的分布式计算原则研讨会(Symposium on Principles of Distributed Computing(PODC))上提出的一个猜想。在2002年,麻省理工学院(MIT)的Nancy Lynch(跟证明FLP定理的Lynch是同一位) 和 SethGilbert发表了布鲁尔猜想的证明,使之成为一个定理。

对于分布式数据系统,分区容错性是基本要求,因为故障的存在是必然的。因此设计分布式数据系统,就是在一致性和可用性之间取一个平衡。

3、拜占庭将军问题

拜占庭将军问题(ByzantineGenerals Problem),是由莱斯利·兰波特在其同名论文中提出的分布式对等网络通信容错问题,对网络中存在作恶节点的情况进行建模。由于作恶节点的存在,拜占庭将军问题被认为是容错性问题中最难的问题类型之一。

莱斯利·兰波特在其论文中描述了如下问题:

一组拜占庭将军分别各率领一支军队共同围困一座城市。为了简化问题,将各支军队的行动策略限定为进攻或撤离两种。因为部分军队进攻部分军队撤离可能会造成灾难性后果,因此各位将军必须通过投票来达成一致策略,即所有军队一起进攻或所有军队一起撤离。因为各位将军分处城市不同方向,他们只能通过信使互相联系。在投票过程中每位将军都将自己投票给进攻还是撤退的信息通过信使分别通知其他所有将军,这样一来每位将军根据自己的投票和其他所有将军送来的信息就可以知道共同的投票结果而决定行动策略。

但问题在于,将军中可能出现叛徒,他们不仅可能向较为糟糕的策略投票,还可能选择性地发送投票信息。假始那些忠诚(或是没有出错)的将军仍然能通过多数决定来决定他们的战略,便称达到了拜占庭容错。在此,票都会有一个默认值,若消息(票)没有被收到,则使用此默认值来投票。

上述的故事映射到计算机系统里,将军便成了计算机,而信差就是通信系统。虽然上述的问题涉及了电子化的决策支持与信息安全,却没办法单纯的用密码学与数字签名来解决。因为不正常的电压仍可能影响整个加密过程,这不是密码学与数字签名算法在解决的问题。因此计算机就有可能将错误的结果提交去,亦可能导致错误的决策。

在分布式对等网络中需要按照共同一致策略协作的成员计算机即为问题中的将军,而各成员计算机赖以进行通讯的网络链路即为信使。拜占庭将军问题描述的就是某些成员计算机或网络链路出现错误、甚至被蓄意破坏者控制的情况。

4、DSS猜想

不同于中心化的分布式系统,去中心化是区块链系统的一个核心特性。去中心化的系统中,为了保证数据可信,需要所有节点参与共识、避免被攻击(如51%攻击)、任何节点都要有能力验证交易的合法性、所有交易要按顺序执行和验证、所有节点都要保存所有的交易数据等。

在分布式系统中,可扩展性是指系统的总体性能随着节点的增多而提升。在中心化的分布式系统设计中,可扩展性是的、最基本要求之一。对于中心化的系统,要保证可扩展性也是相对简单的。

而去中心化的全量共识和存储的要求,是难以扩展的。因为若要可扩展性,就不能要求节点执行全量、全量存储,而是要分散计算和存储,每个节点只保存部分数据,即每个交易数据只存储在少数节点中,但这样一来,安全性就无法保证,因为攻击者只要攻击少数节点,即能控制区块数据。例如数据分成100份保存在不同节点,那攻击者只要实施1%攻击,即能控制其中1份区块数据,攻击难度大大降低。

由于去中心化的要求,区块链的分布式系统也有自身特有的理论,其中一个描述了去中心化与可扩展性之间的矛盾,它尚未被严格证明,只能被称为猜想,但实际系统设计过程中却能感觉到时时受其挑战:

DSS猜想:去中心化(Decentralization),安全性(Security)和可扩展性(Scalability)这三个属性,区块链系统最多只能三选其二。

共识算法的理论基础.png

上图演示了区块链如何在这三个因素之间作选择及对应的策略,例如若若要满足安全性与去中心化,则需要所有节点参与共识、计算、全量存储,但由此带来的问题是失去可扩展性,也就是系统的总体性能无法随着节点的增多而提升;若要满足可扩展性与安全性,则需要中心化管理,需要保证参与共识的节点是可信的;若要满足可扩展性与去中心化,则采用分散存储、计算的策略,不做全量共识,则攻击网络的难度降低,安全性难以保证。

5、共识算法应该满足的条件

尽管算法多种多样,可以根据需要采用各种策略,但大家公认的理想的共识算法应该满足的条件包括:

1) 可终止性(Termination):一致的结果在有限时间内能完成。

2) 共识性(Consensus):不同节点最终完成决策的结果应该相同。

3) 合法性(Validity):决策的结果必然是其它进程提出的提案。

细讲还是有很多内容的,真是只能浅谈,还是希望和大家多多交流,如果大家希望了解更多,欢迎留言

RickMQ

写了 2 篇文章,拥有财富 12,被 0 人关注

反对反对
回复

使用道具

B Color Link Quote Code Smilies

成为第一个吐槽的人

Archiver|手机版|小黑屋|迅雷链开发者社区
Copyright©2018 onethingcloud.com All Rights Reserved 深圳市网心科技有限公司版权所有 粤ICP备14008884号-23
返回顶部