《共识算法与共识安全》白皮书 2023.pptx

目录;1共识算法介绍 1.1介绍 共识问题是社会科学和计算机科学等领域的经典问题，计算机科学领域的早期共识研 究一般聚焦于分布式一致性，即如何保证集群中所有节点中的数据完全相同并且能够对某 个提案(Proposal)达成一致，主要解决的问题是因节点失效、节点间网络故障及分布式 系统的运行速度的差异而带来的系统不一致问题。Fischer等在1985年提出了 FLP不可能 原理，即在网络可靠，但允许节点失效(即便只有一个)的最小化异步模型系统中，不存 在一个可以解决一致性问题的确定性共识算法［1］。Eric Brewer在1998年提出了 CAP理论, 指出在异步的网络模型中，所有的节点由于没有时钟，仅仅能根据接收到的消息作出判断, 系统最多只能同时满足一致性(Consistency)、可用性(Availability)和分区容忍性 (Partition Tolerance)这三项中的两项［2］。 FLP不可能性可以采用更弱的终止条件或者更强的网络假设解决，Ben-Or在1983年 提出了完全异步模型下概率终止的共识算法［3］, Dwork等人在1988年提出了部分异步模 型下的共识算法，保证在网络同步的时侯算法能够确定性终止［4］, Leslie等在1982年提出 了同步模型下的共识问题［5］。 早期的共识算法一般也称为分布式一致性算法，与目前主流的区块链共识算法相比， 分布式一致性算法主要面向分布式数据库操作、且大多不考虑拜占庭容错问题，即假设系 统节点只发生宕机和网络故障等非人为问题(CFT, Crash Fault Tolerance),而不考虑恶意 节点篡改数据等问题(BFT, Byzantine Fault Tolerance，拜占庭容错)。拜占庭容错问题是 Leslie在1982年提出的分布式领域容错问题，它是分布式领域中最复杂、最严格的容错模 型［5］。在该模型下，系统不会对集群中的节点做任何的限制，节点可以向其他节点发送随 机数据、错误数据，也可以选择不响应其他节点的请求.这些无法预测的行为使得容错这一 问题变得更加复杂。 1.2 CFT类共识算法 CFT类共识算法只保证分布式系统中节点发生宕机错误时整个分布式系统的可靠性， 而当系统中节点违反共识协议的时候无法保障分布式系统的可靠性，因此CFT共识算法 目前主要应用在企业内部的封闭式分布式系统中。目前流行的CFT共识算法主要有Paxos 算法及??衍生的Raft共识算法。此外，获得较多研究关注的共识算法还有两阶段提交 (Two-Phase Commit)算法、三阶段提交(Three-Phase Commit)算法、Zab> Kafka 等。;1.2.1 Paxos共识算法 Paxos共识算法是基于消息传递的一致性算法，由Leslie Lamport在1990年提出[6], 该算法基于同步性假设，通过引入超时(Timeout)概念规避了 FLP不可能问题，如果在 确认下个值的过程没有进展，Paxos会等到超时，然后重新进行共识的步骤。Paxos的算法 步骤如下： 阶段1：准备请求 1) 提案者选择新的提案号(n),然后向接收者发送“准备请求”。 2) 当接收者收到准备请求(“prepare," n),且n比已经接收到的其他准备请求大，接 收者会发出消息(“ack,” n,『，v')或(“ack,” n,八，八)。 3) 接收者承诺不会再接纳任何提案号小于n的准备请求。 4) 如果有的话，接收者会发出具有最高提案号的提案值(v),反之则发出空消息八。 阶段2：接收请求 1) 如果提案者收到大多数接收者的响应，则可以发出带有提案号n和价值v的接收请 求(" accept," n, v)。 2) n是准备请求中出现的数字。 3) v是响应中具有最高提案号的提案值。 4) 当收到接收请求(“accept,” n,v)时，除非接收者已经采纳了大于n的提案号，否 则接收者就会采纳这个请求。 阶段3：学习阶段 1) 每当接收者采纳了一个提案，就会向所有学习者返回(“accept,” n,v)o 2) 学习者从多数接收者那儿得到(“accept,” n,v),选定最终的值v,然后向其他学 习者发送(“decide," v)。 3) 学习者收到("decide," v)和最终决定的值v。;为了提供部署的灵活性，Paxos描述的许多主要特性都是开放式的，比如领导者选举、 侦错、日志管理等内容。这种设计选择后来成为Paxos最大的缺点之一，使得Paxos不仅 难以理解，而且难以实施。 1.2.2 RAFT共识算法 因为Paxos晦涩难懂，2013年Ongaro和Ousterhout为Raft复制状态机提出了一种新 型共识算法[7],其核心目标是可理解性，主要有两方面的改进： 1） 将整